计算机网络技术 王宇新 大连理工大学
第六章 网络层与IP协议 第四节 分组交付与路由选择
一、分组交付和路由选择的基本概念 分组交付(forwarding) 互联网中主机、路由器转发IP分组的过程。 分为两类：直接交付和间接交付。
分组交付的过程 默认路由器 （第一跳路由器） 多数主机先接入一个局域网，再通过一个路由器接入互联网。这台路由器即为局域网主机的默认路由器。 路由器根据分组的目的地址与源地址是否属于同一个网络，判断是直接交付还是间接交付。
路由选择 路由器从路由表中找到下一个路由器的IP地址，然后将分组传给下一个路由器。 路由选择的核心是路由选择算法，为生成路由表提供算法依据。 2、评价路由选择的依据 算法必须是正确、稳定和公平的；算法应该尽量简单，节约路由器资源；算法必须能够适应网络拓扑和通信量的变化；算法应该是“最佳”的，转发开销要低。
路由选择算法的主要参数 少 高 低 大 跳数 — 一个分组从源结点到达目的结点经过 的路由器的个数 带宽 — 链路的传输速率 延时 — 一个分组从源结点到达目的结 点花费 的时间 负载 — 通过路由器或线路的单位时间通信量 可靠性 —传输过程中的误码率 开销 — 传输过程中所耗费的链路带宽、通信 费用等
二、路由选择算法 互联网中每一台路由器都保存一个路由表，存储可能的目的地址与如何到达目的地址的信息。 路由器采用表驱动的路由选择算法，路由选择通过查表的方式进行。 从路由选择算法对网络拓扑和通信量变化的自适应能力的角度划分，分为静态和动态两大类。
静态路由表 由人工方式建立，网管人员将每个目的地址的路径输入路由表。 网络结构发生变化时，路由表无法自动地更新。 静态路由表一般只用在小型的、结构不会经常改变的局域网系统中，或者是故障查找的试验网络中。
动态路由表 在网络系统运行时，系统将自动运行动态路由选择协议，建立路由表。 当互联网结构变化时，动态路由选择协议就会自动更新所有路由器中的路由表。 不同规模的网络需选择不同的动态路由选择协议。 大型互联网络通常采用动态路由表；当互联网结构变化时，例如当某个路由器出现故障或某条链路中断时。
1. 标准路由选择算法 标准路由表中保存着多个网络的IP地址与下一跳路由器的序偶对(N,R)。 N表示目的主机所在的网络IP地址，P表示网络N的路径上的下一跳路由器的IP地址。
一个通过3个路由器连接的4个网络的例子 Router2的路由表 本地网络 要到达的网络 下一个路由器 20.0.0.0 直接交付 30.0.0.0 10.0.0.0 20.0.0.1 40.0.0.0 30.0.0.3 本地网络
2. 子网的路由选择 另一个通过3个路由器连接的4个网络的例子 路由表中的内容，序偶对(N,R) 变成三元组(M,N,R)。
Router2的路由表，序偶对(N,R) 变成三元组(M,N,R) 子网掩码 要到达的网络 下一个路由器 255.255.0.0 10.2.0.0 直接交付 10.3.0.0 10.1.0.0 10.2.0.1 10.4.0.0 10.3.0.3 假设收到目的地址为10.2.12.1的分组； 网络地址：10.2.0.0：直接交付 假设收到目的地址为10.4.112.10的分组； 网络地址：10.4.0.0，向Router3发送。
三、IP路由汇聚 CIDR路由汇聚的例子： S0,S1：串行专线 E0,E1,E2：以太网接口 RE,RF：汇聚路由器 RA~RD：接入路由器 CIDR路由汇聚的例子： 核心路由器RG通过两条专线S0,S1与两台汇聚路由器RE,RF连接。路由器RE,RF分别通过两个以太网与4台接入路由器连接，又分别连接8个子网。使用CIDR协议后，IP分组的路由就通过与子网划分的相反过程进行汇聚。加上核心\汇聚路由器的四个子网，一共12个子网。 如果静态路由需要12*7（个路由器）个条目。
汇聚之前 路由器RG 的路由表 路由器 输出接口 156.26.63.240/30 S0（直接连接） 156.26.63.244/30 156.26.63.0/28 S0 156.26.63.16/28 S1 156.26.0.0/24 156.26.1.0/24 156.26.2.0/24 156.26.3.0/24 156.26.56.0/24 156.26.57.0/24 156.26.58.0/24 156.26.59.0/24 汇聚之前 路由器RG 的路由表 路由表可以简化。
地址汇聚过程 路由选择遵循“最长前缀匹配”的原则。寻找156.26.0.0/24～156.26.3.0/24等4项的最长相同的前缀，只要观察地址中的第3个字节： 第3个字节的前6位都是相同的，4项中最长相同的前缀为22位；路由表中这4项可以合并成：156.26.0.0/22。 0=00000000 1=00000001 2=00000010 3=00000011
观察 156.26.56.0/24～156.26.59.0/24 的第3个字 节： 第3字节的前6位都是相同的。也就是说，4项的 最长相同的前缀是22位。因此，在路由表中这4 项条目可以合并成156.26.56.0/22。 56=00111000 57=00111001 58=00111010 59=00111011
汇聚之后路由器RG的路由表 路由器 输出接口 156.26.63.240/30 S0（直接连接） 156.26.63.244/30 156.26.63.0/28 S0 156.26.63.16/28 S1 156.26.0.0/22 156.26.56.0/22 汇聚后路由器RG的路由表，路由条目由12减少到6。
四、路由器功能、结构与工作原理 路由器功能 1. 建立并维护路由表 路由表数据库与网络路由状态数据库； 路由器定期更新路由表； 2. 提供网络间的分组转发功能 检查报文分组的源地址与目的地址； 根据路由表数据库的相关信息，决定分组传送路径。 (1)为了实现分组转发功能，路由器内部有一个路由表数据库与一个网络 路由状态数据库；路由器定期更新路由表； (2)当一个分组进入路由器时，路由器检查报文分组的源地址与目的地址 ，然后根据路由表数据库的相关信息，决定该分组应该传送给哪个路 由器或主机。 19
路由器的结构与工作原理 路由器是一种具有多个输入端口和多个输出端口，完成分组转发功能的专用计算机系统； 由“路由选择处理机”和“分组处理与交换”两部分组成。
路由选择处理机 路由选择部分又称为控制部分，其核心构件是路由选择处理机。 路由选择处理机的任务是根据所选定的路由选择协议构造路由表，同时从相邻路由器交换路由信息，更新和维护路由表。
分组处理与交换部分 分组处理与交换部分主要包括：交换结构、一组输入端口和一组输出端口； 交换结构根据转发表对分组进行处理，将输入端口进入的分组从合适的输出端口转发出去。 路由器每个输入和输出端口中，各有三个模块，对应于物理层、数据链路层和网络层。 如果接收的分组是交换的路由信息的分组（如RIP或OSPF分组），则将这种分组送交路由选择处理器；如果接收到的是数据分组，则按照分组头中的目的地址查找转发表，决定合适的输出端口。
转发分组的速率 衡量路由器性能的重要参数是路由器每秒钟能够转发分组的速率。 最理想的状况是路由器分组处理速率等于输入端口的线路传送速率，人们将路由器的这种能力称为线速（line speed）。 如果使用的是OC-48链路，速率为2.488Gbps，分组长度为256字节。如果路由器的处理能力达到线速，就要求路由器每秒钟能处理1.2148×106个分组，记作1.2148Mpps。 OC-48(Optical Carrier)第48级光载波 ,是SONET光缆基本速率OC-1的48倍 2.488 / 8 *1000 / 256 =1.2148 ？？ 字节 M 分组
排队队列 当一个分组到达一个输入端口时需要在输入队列中排队等待处理。 路由器输出端口设有缓存，存储等待转发的输出分组队列。 只要路由器的接收分组速率、处理分组速率、输出分组速率小于线速，无论是输入端口、处理分组过程与输出端口都会出现排队等待，产生分组转发延时，严重时会由于队列长度不够而溢出，造成分组丢失。