第4章 网络路由设计 本章要点： 4.1 路由选择算法 4.2 路由选择协议

4.1 路由选择算法 4.1.1 路由选择的概念 4.1.2 路由选择算法及目标 4.1.3 路由选择的参数 4.1.4 路由表 4.1 路由选择算法 4.1.1 路由选择的概念 4.1.2 路由选择算法及目标 4.1.3 路由选择的参数 4.1.4 路由表 4.1.5 IP路由选择与路由汇聚 4.1.6 路由选择的评价

4.1.1 路由选择的概念 1．路由选择 路由器的主要工作就是为经过路由器的每个数据帧寻找一条最佳传输路径，并将该数据有效地传送到目的站点。 2．分组转发 分组转发即是指在互联网络中，路由器转发IP分组的物理传输过程与数据报转发机制。分组转发可以分为直接转发与间接转发两种。

图4-1 分组转发的过程

4.1.2 路由选择算法及目标 1. 路由选择算法 2．路由选择算法的目标 （1）静态路由选择算法 （2）动态路由选择算法 （1）最优化 （2）简洁性 （3）坚固性 （4）快速收敛 （5）灵活性

4.1.3 路由选择的参数 （1）带宽 带宽即指一条链路的传输速率，一般表示为Mb/s。 （2）跳数 4.1.3 路由选择的参数 （1）带宽 带宽即指一条链路的传输速率，一般表示为Mb/s。 （2）跳数 跳数即为一个分组从其源主机到目的主机所要经过的路由器的个数，显而易见，经过的路由器的个数越少，即跳数越小，这个路径越好。 （3）时延 时延即为一个分组从其源主机到目的主机所要经历的时间。当然，时间越短，即时延越小，也说明这个路径越好。

（4）负载 负载指的是单位时间内通过路由器或是线路的通信量。 （5）可靠性 可靠性的衡量标准即为分组传输过程中的误码率，误码率是数据传输精确性的指标。误码率=传输中的误码/所传输的总码数*100%，当然误码率越小，说明其可靠性越高。 （6）花费 花费即为分组传输过程中的开销。

4.1.4 路由表 路由表是随着路由选择算法的产生而产生的，路由器要传输IP分组时，必须查询路由表来决定分组发送的下一个地址。 1．静态路由表 由系统管理员事先设置好固定的路由表称之为静态路由表，管理员将每一个目的地址的路径都输入到这个路由表中，因此，它一般是在系统安装时就根据网络的配置情况预先设定的，它不会随着网络结构的改变而改变，其更新工作必须由管理员手工完成。

2．动态路由表 动态路由表是路由器根据网络系统的运行情况而自动调整的路由表。路由器根据路由选择协议提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。

4.1.5 IP路由选择与路由汇聚 IP分组的路由在使用CIDR协议后，就通过子网的划分的相反过程来汇聚。路由表的项目由“网络前缀”和“下一跳地址”两项内容组成，因此，选择路由应当从匹配结果中选择具有最长网络前缀的路由。 图4-2即为CIDR的路由汇聚图。图中，核心路由器通过两条专线S1与S2与两台汇聚路由器连接。两台汇聚路由器又分别通过Ethernet各连接了4台接入路由器，得到了8个子网。

图4-2 CIDR的路由汇聚图

表4-1 核心路由器的路由表 表4-2 汇聚后的核心路由的路由表 路由器 接口 172.18.54.240/30 S1 表4-1 核心路由器的路由表 表4-2 汇聚后的核心路由的路由表 路由器 接口 172.18.54.240/30 S1 172.18.54.244/30 S2 172.18.54.0/28 172.18.54.16/28 172.18.0.0/24 172.18.1.0/24 172.18.2.0/24 172.18.3.0/24 172.18.44.0/24 172.18.45.0/24 172.18.46.0/24 172.18.47.0/24 路由器 接口 172.18.54.240/30 S1 172.18.54.244/30 S2 172.18.54.0/28 172.18.54.16/28 172.18.0.0/22 172.18.1.44/22

4.1.6 路由选择的评价 1．算法简单、正确、最佳 路由算法尽量简单以减少路由资源的耗费和分组转的时延；分组沿着路由表所指引的路径能够到达正确的目的地址；分组转发的算法开销尽可能的低，它应在衡量各方面因素后，得到一个相对较为合适的传输路径。 2．稳定、公平 在网络的拓扑和通信量相对稳定的情况下，路由算法收敛于一个较好的解，并且算法应该对所有的用户都是公平的。 3．适应网络拓扑、通信量的变化 当网络拓扑、通信量的变化时，算法能自动进行更新，改变路由，以均衡各链路的负载。

4.2 路由选择协议 4.2.1 路由选择协议的概念 4.2.2 路由选择协议的分类 4.2.3 内部网关协议 4.2.4 外部网关协议

4.2.1 路由选择协议的概念 1．自治系统 2．路由选择协议 4.2.1 路由选择协议的概念 1．自治系统 Internet采用分层的路由选择协议，并将整个Internet划分为许多较小的自治。自治系统就是处于一个管理机构控制之下的路由器和网络群组。自治系统的想法是把Internet的路由分成两层。 2．路由选择协议 路由选择协议是一种网络层协议，它通过提供一种共享路由选择信息的机制，它允许路由器通过与其他路由器的来更新和维护自己的路由表，并确定最佳的路由选择路径。

4.2.2 路由选择协议的分类 1. 内部网关协议 内部网关协议是用于自治系统内部的路由选择协议，目前主要的内部网关协议有： 4.2.2 路由选择协议的分类 1. 内部网关协议 内部网关协议是用于自治系统内部的路由选择协议，目前主要的内部网关协议有： （1）地址解析协议 它是一个TCP／IP协议，它为内部路由器传递数据报提供方法。 （2）路由选择信息协议 它是一种分布式的、基于距离向量路由选择协议。 （3）优先开放最短路径 它是一种链路状态路由选择协议，它优于路由选择信息协议。现在是Internet网中最常用的内部网关协议。

（4）端系统到中间系统 它帮助端系统寻找定位路由器，并提供一种方法使路由器告知端系统它们的存在。 （5）中间系统到中间系统 它为一个域内两个路由器之间传送信息分组提供动态路由。 （6）内部网关路由选择协议 是一种距离向量路由选择协议，由Cisco公司开发。

2. 外部网关协议 外部网关协议在自治系统的边界是路由器其它路由器之间交换信息时被使用。它包括以下协议： （1）边界网关协议 它提供有关相邻点可达性信息。同时也提供了基于策略的算法，使网络管理者对路由选择有较多的控制权。 （2）域间路由选择协议 它包含路由选择的策略，但它不大可能在Internet上代替边界网关协议。

图4-3 自治系统、内部网关协议与外部网关协议的关系 图4-3 自治系统、内部网关协议与外部网关协议的关系

4.2.3 内部网关协议 1．路由信息协议RIP 当路由器收到包含某表项的更新的路由更新信息时，就更新其路由表：该路径的跳数值加上1，发送者记为下一跳。同时记录该路由器可以到达的目的网络或目的主机的矢量标识。路由信息协议路由器只维护其到目的路由器的最佳路径即具有最小跳数值的路径。更新了自己的路由表后，路由器立刻发送路由更新把变化通知给其它路由器，这种更新是与周期性发送的更新信息无关的。并且，路由信息协议通过对从源地址到目的地址的最大跳数的限制来防止路由环，最大值为15。如果路由器收到新更新信息，且把跳数值加1后成为16，就认为该目的网络不可到达。

路由信息协议的工作主程主要分为路由表的建立和路由表信息的更新两步。 （1）路由表的建立 首先获取一个初始路由表，有三种方式 方式一 路由器系统启动时，从外存读入一个完整的路由表，长驻内存使用；系统关闭时再将当前路由表写回外存，供下次使用。 方式二 系统启动时，只提供一个空表，通过执行显式命令来填充这个路由表。 方式三 系统启动时，从与本路由器直接相连的各网络地址中，推导出一组初始路由。

设路由器1与路由器2是相邻的两个路由器，它们在同一个自治系统内。 表4-3 路由器1的更新前的路由表 （2）路由表的更新 设路由器1与路由器2是相邻的两个路由器，它们在同一个自治系统内。 表4-3 路由器1的更新前的路由表 目的网络 距离 路由 10.0.0.0 直接 30.0.0.0 5 路由器2 40.0.0.0 路由器3 60.0.0.0 9 113.0.0.0 3 路由器6 128.0.0.0 7 136.0.0.0 13 路由器7 140.0.0.0 路由器8

表4-5 路由器1更新过以后的路由表 表4-4 路由器2发送的报文 目的网络 距离 10.0.0.0 2 20.0.0.0 3 表4-5 路由器1更新过以后的路由表 表4-4 路由器2发送的报文 目的网络 距离 10.0.0.0 2 20.0.0.0 3 30.0.0.0 4 50.0.0.0 8 128.0.0.0 5 136.0.0.0 目的网络 距离 路由 10.0.0.0 直接 20.0.0.0 4 路由器2 30.0.0.0 5 40.0.0.0 路由器3 50.0.0.0 9 60.0.0.0 113.0.0.0 3 路由器6 128.0.0.0 6 136.0.0.0 140.0.0.0 路由器8

2．开放最短路径优先协议OSPF （1）概念 （2）最短路径优先算法 （3）自治系统内的区域划分 （4）开放最短路径优先协议的执行 路由器的初始化 网络的运行 （5）开放最短路径优先协议的特点

图4-4 一个自治系统划分的情况

4.2.4 外部网关协议 1．外部网络协议的设计 外部网关协议是自治系统间的路由协议，它交换的网络可达性信息提供了足够的信息来检测路由回路并根据性能优先和策略约束对路由进行决策。 1989年，主要的外部网关协议：边界网关协议（BGP）发布后，即越来越被广泛的应用，1995年发布了新版本BGP-4。

2．外部网关协议的路由选择协议 BGP有4种分组类型： （1）打开分组 打开分组用来与相邻的BGP发言人建立连接。 （2）更新分组 用来通告可达路由和撤销无效路由。 （3）存活分组 确认打开报文，以周期性地确保连接的有效性。 （4）通告分组 当检测到一个差错时，发送通告分组。

图4-5 BGP发言人与自治系统的关系示意图

图4-6 某个BGP发言人所构造的自治系统连接的树形结构