5. 3 路由（routing）在多站点、多路径网络化环境中寻找从某源到目的地的通路。 网络结构非规则的，不完全为星型、线型、规则的树型 不同的路径代价（cost）不同 网络的规模可能大 网络可能动态变化 全局和部分不保证有统一的管理和规划 要实现路由（选路）需要什么信息 如何得到这样的信息 以什么方法利用这些信息B222.1.1.222.1.1.1222.1.1.2222.1.1.3222.1.1.4R1222.1.2.5222.1.2.2222.1.2.1222.1.2.3222.1.2.4222.1.2.222.1.6.1222.1.5.1222.1.5.2222.1.6.2222.1.4.1222.1.4.2222.1.3.3222.1.3.2222.1.3.1R3R2222.1.3.LAN3N3N2222.1.4.222.1.5.222.1.6.N1LAN2LAN1互联网5.3.1 Internet路由的基本思想 利用部分信息路由一主机可对本局域网和本地路由器路由。路由器如何路由？ 分析例1： 设某人从A地要到达X地，出发后遇到第一个路标： 去B向右，去C向左，其余向前。向前，又走到一路标处 ： 去D向右，其余向前。 。 最后遇到一路标： 去X向右，去Y向左，其余向前。在这个例子中：每个路标只给出了本地路由信息。而整个路由信息是由众多路标共同给出的。局部而言，路由信息不完整；全局而言，路由信息是完整的。利用部分信息可以路由。极端：星型，中心节点必须具备所有路由信息每个路标给出所有目的的路径可提供完成、统一的路由，但不现实，不合理分析例2：两个地区相隔一条河，通过桥可以互通。东边的路标给出东边的目的信息，其余的默认为桥。西边的类似。这样也可以达到路由信息 统一、完整。该例 一方面 强调了默认路由的作用。 另一方面也体现了自治系统的特征。问题： 1）能否到达希望的目的？ 2）是否是最佳路径？R1R2Rn网1网2网n核心路由器主干网非核心路由器 核心路由器可采用默认路由（环状），不足是效率可能低。 核心路由器交换路由信息；形成非核心路由器默认路由为核心路由器系 统。问题：1）核心路由器路由信息一致性2）非核心路由部分还需要解决路由问题3）核心部分要交换路由信息，故不能覆盖太大范围。环路R1R2Rn主机1主干网1主干网2主机3主机2主机4核1核2默认路由可能产生环路（对非法目的的报文）利用最小信息进行路由在路由处理中，路由器很难包含大量的路由信息。希望根据信息隐 藏原理，利用最小信息进行路由。减小路由表的途径有：1）“下一跳”（Next Hop),不给出到达目的的全部路径信 息，而给出通往目的的下一站。 2）网络前缀，同一网络的主机有相同的网络前缀。 3）默认路径 多个表项的合并下一跳路由表包含一些偶序 (Pair) (N,R) N 目的网络； R 可到达N的路由器即路由表提供了到达N的下一步，未给出到达N的完整路径。简单的路由表DESTGETWAYFLAG 140.252.13.65140.252.13.35 UGH(可用/网关/主机 ） 127.0.0.1127.0.0.1 140.252.13.32140.252.13.34U 140.252.1.183140.252.1.29DEFAULT140.252.13.33UG10.0.0.010.0.0.4 20.0.0.020.0.0.920.0.0.7 30.0.0.030.0.0.130.0.0.240.0.0.040.0.0.420.0.0.030.0.0.010.0.0.040.0.0.0直接交付 0 直接交付 120.0.0.730.0.0.10 1 路由器转发分组的算法(1) 从收到的分组的首部提取目的 IP 地址 D，并计算网络前缀N。 (2) 先看直接连接的网络是否和地址D匹配。若匹配，则将分组直接交付 。否则就是间接交付，执行(3)。 (3) 若路由表中有目的地址为 D 的特定主机路由，则将分组传送给指明 的下一跳路由器；否则，执行(4)。 (4) 对路由表中的每一行的网络和 N相比较，若其结果与该行的目的网络 地址匹配，则将分组传送 给该行指明的下一跳路由器；否则，执行(5)。 (5) 若路由表中有一个默认路由，则将分组传送给路由表中所指明的默认 路由器；否则，执行(6)。 (6) 报告转发分组出错。5.3.2 划分子网和构造超网（一）子网三级 IP 地址nIP 地址空间的利用率有时很低。 n给每一个物理网络分配一个网络号会使路由表变得太大因而使 网络性能变坏。 n两级的 IP 地址不够灵活。从 1985 年起在 IP 地址中增加了一个“子网号字段”，使两级的 IP 地址变 成为三级的 IP 地址。 这种做法叫作划分子网(subnetting) 。IP地址 = , , 划分子网只是将 IP 地址的本地部分进行再划分，而不改变 IP 地址的因特网部分。 11000000 00001010 00000001 xxx yyyyy网络号 子网号 主机号11000000 00001010 00000001 00100000 - 192.10.1.3211000000 00001010 00000001 01000000 - 192.10.1.6411000000 00001010 00000001 01100000 - 192.10.1.9611000000 00001010 00000001 10000000 - 192.10.1.12811000000 00001010 00000001 10100000 - 192.10.1.16011000000 00001010 00000001 11000000 - 192.10.1.192子网掩码32比特，网络号(包括子网号)部分全为“1”，主机号部分全为“0”。11111111 11111111 11111111 11100000255 . 255 . 255 . 22411001010 01110101 00000001 110 01111主机地址 11111111 11111111 11111111 111 00000 子网掩码11001010 01110101 00000001 110 00000子网号子网地址为：202.117.1.192 主机号为：15网络号 net-id主机号 host-id两级 IP 地址网络号net-idhost-id三级 IP 地址主机号subnet-id子网号子网掩码因特网部分本地部分因特网部分本地部分划分子网时 的网络地址1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0net-idsubnet-idhost-id 为全 0145.13.3.11145.13.3.101145.13.7.34145.13.7.35145.13.7.56145.13.21.23 145.13.21.9 145.13.21.8子网 145.13.21.0子网 145.13.3.0子网 145.13.7.0网络 145.13.0.0R1R3R2所有到达网络 145.13.0.0 的分组均到达 此路由器145.13.3.10128.30.33.10接口 0 接口 1 R2255.255.255.128 255.255.255.128 255.255.255.0128.30.33.0 128.30.33.128 128.30.36.0下一跳子网掩码目的网络地址128.30.33.13H1子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128128.30.33.130R1 的路由表（未给出默认路由器）R11R2子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128H2128.30.33.13801128.30.33.129H3128.30.36.2子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0128.30.36.12划分子网后分组的转发示意在划分子网的情况下路由器转发分组的算法(1) 从收到的分组的首部提取目的 IP 地址 D。 (2) 先用各网络的子网掩码和 D 逐比特相“与”，看是否和相应的网络地址匹 配。若匹配，则将分组直接交付。否则就是间接交付，执行(3)。 (3) 若路由表中有目的地址为 D 的特定主机路由，则将分组传送给指明的下一 跳路由器；否则，执行(4)。 (4) 对路由表中的每一行的子网掩码和 D 逐比特相“与”，若其结果与该行的 目的网络地址匹配，则将分组传送 给该行指明的下一跳路由器；否则，执行(5) 。 (5) 若路由表中有一个默认路由，则将分组传送给路由表中所指明的默认路由 器；否则，执行(6)。 (6) 报告转发分组出错。（二）无分类编址 CIDR （Classless Inter Domain Routing）提出： Internet指数增长，IP地址即将用完，基于分类的IP地址空间的组织浪费了大量的地址因特网主干网上的路由表中的项目数急剧增长1987 年，RFC 1009 就指明了在一个划分子网的网络中可同时使用几个不 同的子网掩码。使用变长子网掩码 VLSM (Variable Length Subnet Mask) 可进一步提高 IP 地址资源的利用率。 在 VLSM 的基础上又进一步研究出无 分类编址方法，它的正式名字是无分类域间路由选择 CIDR (Classless Inter -Domain Routing)。CIDR 消除了传统的 A 类、B 类和 C 类地址以及划分子网的概念，因而可 以更加有效地分配 IPv4 的地址空间。 CIDR使用各种长度的“网络前缀”(network-prefix)来代替分类地址中的网 络号和子网号。 IP 地址从三级编址（使用子网掩码）又回到了两级编址。 无分类的两级编址的记法是：IP地址 = , nCIDR 使用“斜线记法”(slash notation)，它又称为CIDR记法，即在IP 地址后面加上一个斜线“/”，然后写上网络前缀所占的比特数（这个数值 对应于三级编址中子网掩码中比特 1 的个数）。故网络前缀是可变长 度的。n地址格式: a.b.c.d/x, x表示地址中网络号部分的位数nCIDR 将网络前缀都相同的连续的 IP 地址组成“CIDR地址块”。 例如：n128.14.32.0/20 表示的地址块共有 212 个地址（因为斜线后面 的 20 是网络前缀的比特数，所以主机号的比特数是 12）。 n这个地址块的起始地址是 128.14.32.0，最大地址：128.14.32.255 n在不需要指出地址块的起始地址时，也可将这样的地址块简称 为“/20 地址块”。 n全 0 和全 1 的主机号地址一般不使用。对于 /20 地址块，可理解为它的掩码是 20 个连续的 1。 斜线记法中 的数字就是掩码中1的个数。网络前缀越长，其地址块就越小。路由就越具体。128.14.32.0/20 表示的地址（212 个地址）10000000 00001110 00100000 00000000 10000000 00001110 00100000 00000001 10000000 00001110 00100000 000000