第七章 网络互连 之 路由协议

1、路由协议（RIP，OSPF和BGP） “互联网络”（internet）是路由器连接而成的多个网络的组合体。当数据报从一个源端传送到一个目标端时，可能需要通过很多个路由器才到达与目标网络连接的路由器。 路由器的作用是从一个网络中接收数据包（packet，分组），然后将它传送给另一个网络。一个路由器通常与几个网络连接，这样，当它收到一个数据包时，应该将数据包转发给哪个网络呢？路由器是按最佳化原则进行判定：哪个可用的路径是最佳路径？ 人们用metric来表示通过某个网络时所指定的“成本”（cost，代价）。一个特定路由的总metric，等于包含了该路由的多个网络的metric之和。路由器根据最短（最

2、小）的metric来选择路由。Metric电信专业 n. 米制的,量度的计算机专业 度量，尺度；公制 分配给每个网络的metric取决于协议的类型。某些简单的协议，如“路由信息协议”（RIP），将每个网络同等处理，即通过每个网络的cost是一样的，或者说都是一个“跳数”（one hop count）。所以如果一个数据包通过10个网络才到达目标端，其总cost就是10个“跳数”。 其他协议，如“开放最短路径优先协议”（OSPF），则允许管理员根据所需的服务类型，为通过一个网络指定cost。通过某个网络的路由可以具有不同的cost（metric）。例如，如果所需的服务类型是“最大吞吐量”（thro

3、ughput），一条卫星链路就比一条光纤链路具有更低的metric。另一方面，如果所需的服务类型是“最小延迟”，一条光纤链路就比一条卫星链路具有更低的metric。OSPF允许每个路由器根据所需的服务类型拥有几个路由表。 其他协议定义metric的方法则完全不同。在“边缘网关协议”（BGP）中，评定的标准是可以由管理员设置的所谓“策略”（policy）。“策略”定义了应该选择的是哪个路径。 不管metric是如何确定的，路由器在准备转发数据包时，都必须使用路由表。路由表应为数据包规定最佳路径。不过，路由表可以是静态的，也可以是动态的。 “静态路由表”是那种不经常变化的路由表。 “动态路由表”是

4、那种当互联网络中的某处出现变化时能自动更新的路由表。 今天，互联网络需要的是动态路由表。这种路由表要求互联网络出现变化时即被尽快更新。例如，当某个路由关闭（down）时，需要进行更新；而当一个更好的路由建立后，也需要进行更新。 各种路由协议都是为了动态路由表的需要而制定的。 一个路由协议是一组规则和程序的组合， 用于使互联网络中的路由器们相互告知有关的变化情况。它使路由器们共享它们所掌握的互联网络或相邻路由器的情况。这种信息的共享使得武汉的某个路由器可以知道上海的网络出现故障了。 路由协议还包含了将从其他路由器接收的信息综合起来的处理程序。 内部和外部路由 今天，一个互联网络可能很大，以致一个

5、路由协议无法完成为所有路由器更新路由表的任务。为此，需要将一个互联网络分为若干“自治系统”（autonomous systems，AS）。 一个“自治系统”是指由同一个管理员管理的一组网络和路由器。 自治系统内部的路由称为“内部路由”， 自治系统之间的路由称为“外部路由”。 每个自治系统都可以选择一个内部路由协议来处理该自治系统内部的路由。但是，自治系统之间的路由通常只能使用一个外部路由协议来处理。 路由器R1，R2和R3使用一个内部路由协议和一个外部路由协议。其他路由器只使用内部路由协议。 阴影部分表示使用内部路由协议的各自治系统。细实线表示使用内部路由协议的各路由器间的通信连接。 粗实线表

6、示使用外部路由协议的各路由器间的通信连接。 现在使用的内部和外部路由协议很多。本章只介绍最常用的几种。下面讨论两个内部路由协议（RIP和OSPF）和一个外部路由协议（BGP）。 RIP和OSPF可用于自治系统内部路由表的更新。 BGP可用于为连接自治系统的各个路由器进行路由表更新。路由算法路由算法：根据网络拓扑计算路由的方法。：根据网络拓扑计算路由的方法。 或路由表的生成方法。或路由表的生成方法。两种路由算法：两种路由算法： 矢量矢量- -距离（距离（ V-DV-D）算法）算法 如如RIP（路由信息）（路由信息） 链路状态（链路状态（L-SL-S）算法）算法 如如OSPF（开放最短路径优先）（

7、开放最短路径优先）矢量-距离（ V-D）算法路由表中列出所有已知的路由启动时路由器对每个与自己直连的网络生成一个表项每个路由器周期地向直接相连的其他路由器发送自己的 路由表每个路由器根据其他路由器发来的路由更新消息，相应 修改自己的路由表周期性传送的信息包括： （目的网络地址(矢量)V，到达该网络的距离D） 这就是矢量-距离算法名称的来源不需要传送路由信息，只需： 1）检测所有相邻相邻路由器的状态(相邻：通过同一网络连接的两个路由器相邻：通过同一网络连接的两个路由器) -周期地向相邻路由器发送“Hello”报文，询问其工作状态 2）周期地向其他路由器通告自己了解到的链接状态信息 -链路类型、链

8、路标识、通告该链路的路由器地址每个路由器根据其他路由器发来的链路状态报文，相应地更新自己 的网络拓扑结构数据库最终每个路由器都具有同样的网络拓扑最终每个路由器都具有同样的网络拓扑 结构数据库（即共享一个公共的连接状态数据库），称为收敛结构数据库（即共享一个公共的连接状态数据库），称为收敛路由器使用Dijkstra最短路径算法对网络拓扑图求最短路径计 算到达其他网络的最短路径最后用计算出来的最短路径更新自己的路由表D-V和和L-S算法的比较算法的比较D-V 通过与邻居的信息交换通过与邻居的信息交换获得网络拓扑知识获得网络拓扑知识 路由计算是增加路由器路由计算是增加路由器之间的站点数（之间的站点数

9、（hops） 定期刷新路由：收敛慢定期刷新路由：收敛慢 向相邻站点传送路由表向相邻站点传送路由表的副本的副本L-S 全网获得共同的全局性全网获得共同的全局性网络拓扑知识（网络拓扑知识（L-S图）图） 计算到达其他站点的最计算到达其他站点的最短路径（短路径（SPF准则）准则） 触发刷新：收敛快触发刷新：收敛快 向其他站点发送链路状向其他站点发送链路状态的动态变化态的动态变化RIP（路由信息协议） 路由信息协议是一个用于自治系统内部的 “内部路由协议”。它是一种非常简单的协议，基于 “距离向量路由” 技术。 距离向量路由在“距离向量路由”中，每个路由器都定期地和其相邻的路由器们共享它们对整个互联网

10、络掌握的情况。理解这一算法的工作原理有三个关键，如下：1、 共享整个自治系统的情况 每个路由器都和其相邻的路由器们共享它们对整个互联网络掌握的情况。开始时，一个路由器掌握的情况可能是很少的，便是它知道多少并不重要；它发送它所知道的所有情况。2、 只和相邻的路由器共享 每个路由器只向相邻的路由器发送自己掌握的情况。它通过自己的所有端口发送自己知道的所有情况。3、 定期地共享 每个路由器都定期地（如每隔30秒）向相邻的路由器发送自己掌握的情况。术语“距离向量”起源于定期信息发送，一个报文包含有成对的列表（V，D），这里的V表示目的地（叫做向量），D是到达那个目的地的距离。注意距离向量是以第一人称报

11、告路由的，即我们把一个路由器送来的通告看成它在说：“我可以到达距离为D的目的地V”。 路由表每个路由器都保持一张路由表，表中为路由器知道的每一个目标网络设置一条记录。该记录由目标网络的IP地址、到达目标的最短距离（用“跳数”表示）和下一跳（为了到达最后目标应将数据包转送给它的下一个路由器）三个部分组成。跳数是指数据包到达最后目标所进入的网络数目。路由表中还含有诸如该记录最后更新时间等其他信息。示例如下：距离跳数下一跳其他信息163.5.0.07172.6.23.4 197.5.13.05176.3.6.17 189.45.0.04200.5.1.6 115.0.0.06131.4.7.19 R

12、IP更新算法路由表根据收到的RIP响应报文（message）进行更新。以下是RIP所使用的更新算法： 接收：一个RIP响应报文1 为每个advertised（被发布）的目标增加一个跳数值；2 对每个advertised的目标重复以下步骤： IF （目标不在路由表中） 将advertised的信息添加到路由表中。 ELSE IF （下一跳字段相同） 用advertised的记录替换表中的记录 ELSE IF（advertised跳数小于表中的跳数） 把它加到路由表中(更新） ELSE 什么都不做3 返回 报文由序偶（报文由序偶（IP网络地址，到达该网络的距离）组成网络地址，到达该网络的距离）组成

13、用步跳数表示到达目的网络的距离；用步跳数表示到达目的网络的距离；1-16，1表示直连，表示直连，16表示不可表示不可达（即只要步跳数大于等于达（即只要步跳数大于等于16就认为路径为无穷远）就认为路径为无穷远）路由器收到路由更新报文后应更新自己的路由表路由器收到路由更新报文后应更新自己的路由表 例如，例如，R2从从R1收到的路由更新报文为收到的路由更新报文为(net1,1)、(net2,2)、(net3,1)，则，则R2的路由表更新为的路由表更新为(net1,R1,2)、(net2,R1,3)、(net3,R1,2)RIP协议的时钟协议的时钟 路由刷新周期路由刷新周期 每个路由器每隔每个路由器每

14、隔30秒刷新和广播自己的路由表。秒刷新和广播自己的路由表。 路由失效计时路由失效计时 一条路由表项未被更新的时间达一条路由表项未被更新的时间达3分钟（分钟（180秒），秒），则视其为失效信息，将本路由表项的距离置为无穷则视其为失效信息，将本路由表项的距离置为无穷大（毒性逆转）。大（毒性逆转）。 路由保持计时路由保持计时 发现一条路由失效信息后，立即启动保持计时，发现一条路由失效信息后，立即启动保持计时，60秒之后删除此条目。秒之后删除此条目。算法不能明确的检测出循环路由，会产生慢收敛和无限计数问题算法不能明确的检测出循环路由，会产生慢收敛和无限计数问题步跳数不能反映链路的真实开销，例如步跳数为

15、步跳数不能反映链路的真实开销，例如步跳数为4的的LAN路径不一路径不一定比步跳数为定比步跳数为1的的64K DDN链路差。链路差。网络1R1R2R31.R1与网络与网络1直接相连。直接相连。2.通过周期性路由广播，通过周期性路由广播，R1、R2、R3都建立了到网络都建立了到网络1的路由的路由(a)3.某时刻，某时刻， R1到网络到网络1的路由消失的路由消失(b)4.但是但是R2对对R1的路由通告引起了选路的循环的路由通告引起了选路的循环: : 更新报文会在更新报文会在R1，R2来回传输直到距离值到达来回传输直到距离值到达RIP规定的上限。规定的上限。 网络1R1R2R3(a)(b)R1直接与网

16、络1相连，因此在路由表中具有一个到网络1的路由，跳数为0，在它广播后，R2获得到网络1的路由，跳数为0+1=1，最后R3则通过R2的广播得到到网络1的路由，跳数为1+1=2，同时，R1也会收到R2的广播，但是由于在R1中到网络1的跳数为0，比R2的小，因此不会更新。如果网络1到R1的连接故障，则R1把到网络1的跳数设为16，并广播，使其它路由器更新。但是，由于所有路由器都会周期性广播路由信息，因而可能会出现这种情况：在R1广播跳数16之前，先收到了来自 R2的广播，计算到网络1的跳数为1+1=2，比16小，因此在还没有广播之前已经被更新了，等到下一个广播周期时，R2的更新为2+1=3。到下一轮

17、广播，R1又是收到R2的广播跳数变为3+1=4，而后又广播给R2，使R2到网络1的跳数更新为4+1=5，如此，不断增加，要经过一个较长的时间（大于14*30秒）之后，才会发现网络1从这里是不可达的，而这段时间内到网络1的流量仍被引导到这个不可能的方向。这就是慢收敛问题 (坏消息传得慢)网络1R1R2R3网络1R1R2R3 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BC，3+1=4BA，3+1=4到达信宿到达信宿40.0.0.0的路由变化的路由变化

18、路径环（路径环（Routing Loop）问题）问题这条错误的路由信息在这条错误的路由信息在C与与B之间不断复制和修改，之间不断复制和修改，并在网络中传播（殃及并在网络中传播（殃及A），形成路径传播的环路。），形成路径传播的环路。 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BA，BC，3+1=4第第 3 步步454CB，4+1=5第第 13 步步141514CB，14+1=15第第 14 步步161516BA， BC， 15+1=16 Count

19、 to Infinity到达信宿到达信宿40.0.0.0的路由变化的路由变化严重后果：计数至无穷大严重后果：计数至无穷大 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BA，BC，3+1=4第第 3 步步454CB，4+1=5第第 13 步步141514CB，14+1=15第第 14 步步161516BA， BC， 15+1=16第第 15 步步不不可可达达16不不可可达达CB，15+1=16第第 16 步步不不可可达达扔扔弃弃到达信宿到达信宿40.

20、0.0.0的路由变化（定义的路由变化（定义Hop最大值为最大值为16）解决办法：定义距离的最大值解决办法：定义距离的最大值收敛！收敛！解决解决RIP存在的问题的几种方法存在的问题的几种方法v视野分离（水平分割）视野分离（水平分割） Split-Horizon 从一个接口收到的路由信息不会再通过该接口送回去从一个接口收到的路由信息不会再通过该接口送回去v毒性逆转毒性逆转 Poison Reverse 从一个接口收到的路由信息可以再通过该接口送回去，但距离为从一个接口收到的路由信息可以再通过该接口送回去，但距离为16v触发更新触发更新 Trigged updates 路由发生变化时，不必等到路由发

21、生变化时，不必等到30秒，可立即将更新报文广播出去秒，可立即将更新报文广播出去v抑制更新抑制更新 Hold-Down timers 收到某网络不可达的信息后，在一段时间内（收到某网络不可达的信息后，在一段时间内（60秒）忽略任何关于秒）忽略任何关于该网络的路由信息该网络的路由信息水平分割方法的思路水平分割方法的思路 1 1ACB40.0.0.0 down 分析路径环产生的原因分析路径环产生的原因 B向向C提供了一条过时的、错误的路由信息。提供了一条过时的、错误的路由信息。 能否避免事件发生？能否避免事件发生？ B必须经由必须经由C方可到达网络方可到达网络40.0.0.0，B不可能向不可能向C提

22、供任何有提供任何有价值的路由信息。价值的路由信息。 修改修改B对对C提供的路由，禁止提供的路由，禁止B向向C提供关于此信宿的路由信息。提供关于此信宿的路由信息。水平分割法水平分割法（Split Horizons） 1 1ACB40.0.0.0 down收敛！收敛！时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开21 C 主主动动改改距距离离为为 第第 1 步步2 CB， 第第 2 步步 BA， 到达信宿到达信宿40.0.0.0的路由变化的路由变化水平分割法利用的是路由报文发送的选择性；一个路由器必须识别不同的水平分割法利用的是路由报文发送的选择性；一个路由器必须识别

23、不同的端口。如果一个路由器已经从某个端口处接收到了路由更新信息，那么这端口。如果一个路由器已经从某个端口处接收到了路由更新信息，那么这同一个更新信息就不能通过此端口再发送回去。如果一个端口已经发送信同一个更新信息就不能通过此端口再发送回去。如果一个端口已经发送信息以帮助某个路由器进行更新，这种更新的信息不得回送；它是已知的，息以帮助某个路由器进行更新，这种更新的信息不得回送；它是已知的，所以是不需要的。所以是不需要的。l水平分裂虽然广泛使用，但有时候会失败。l如右图。n开始时，A和B到D的距离都为2，C到D的距离为1。n假设CD线路断了，使用水平分裂，A和B都告诉C，它们不能到达D，同时C自己

24、也发现直达D的线路断了，于是C很快认定D不可达了。n但是，A认为B有一条通向D长度为2的路径，通过B经过3个结点可到达D。类似，B也这样认为。于是两个结点每交换一次信息，到达D的距离就增加1，直至加大无穷。 1 1ACB40.0.0.0 down此法是水平分割法的一个变种。在本办法中，路由器收到的此法是水平分割法的一个变种。在本办法中，路由器收到的信息被用于更新路由表，然后转发到所有端口。但是，从某个信息被用于更新路由表，然后转发到所有端口。但是，从某个端口传来的路由表记录如果通过同一个端口出去，它的跳数值端口传来的路由表记录如果通过同一个端口出去，它的跳数值被设为被设为16。 反向抑制法反向

25、抑制法 (毒性逆转毒性逆转 Poison Reverse） 1 1ACB40.0.0.0 down 当当C发现网络发现网络40.0.0.0发生故障时，不等下一刷新周发生故障时，不等下一刷新周期到来，立刻更改路由为期到来，立刻更改路由为“信宿不可达信宿不可达” 引起全网的连锁反映，迅速刷新引起全网的连锁反映，迅速刷新触发刷新法触发刷新法网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达距离向量算法小结距离向量算法小结 路径选择采用最短路径准则，计算路径选择采用最短路径准则，计算D信宿信宿(距离，下站距离，下站)； 每个站点只知道自己和邻居

26、的局部信息，在自己的刷新每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；周期到来时，根据邻居的路由变化重新启动算法； 算法的收敛速度慢（特别是对网络崩溃）造成全网信息算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；的不一致，导致产生路径环，使计数至无穷大； 当路径环产生时，定义距离的最大值可防止算法进入死当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；循环，解决计数至无穷大问题； 各种加速收敛方法的目的在于避免路径环的形成，但不各种加速收敛方法的目的在于避免路径环的形成，但不能从根

27、本上杜绝这一现象的发生；能从根本上杜绝这一现象的发生； 在具体的路由协议中，各种加速收敛方法往往综合使用。在具体的路由协议中，各种加速收敛方法往往综合使用。开放最短路径优先（开放最短路径优先（OSPF）协议OSPF协议的基本概念协议的基本概念Open Shortest Path First 采用链接状态（采用链接状态（L-S）算法）算法 由由IETF工作小组研制工作小组研制 1990年成为标准（年成为标准（RFC1247） 改进改进RIP协议的问题协议的问题 计数至无穷大计数至无穷大 收敛速度慢收敛速度慢 开放最短路径优先（开放最短路径优先（OSPF）协议： 使用SPF算法，基于链路状态。 (

28、Shortest Path First) 提供路由服务类型：如可要求低延迟或高吞吐量，路由时不仅依据路由目的，还要依据服务类型要求 ，OSPF将均分负载给各个路径 提供网络的“域”划分能力，一个域对外部是透明的，因而可独立管理，这就提供了灵活的网络扩展能力，易于规模化 OSPF规定路由器之间的信息交换需要有授权，提高安全性。RIP中任意路由都可广播路由信息，易被利用。 支持指向特定主机、特定子网的路由，当然还有对网络的路由，以满足不同需要。 支持子网 支持CIDR 支持虚链路。 . 最短路径优先最短路径优先(Shortest Path First)算法： 该算法利用网络拓扑结构（基于链路状态）

29、，作如下抽象： 把网络中的每个路由器看成一个节点, 若两个路由器之间存在直接的连接,就认为它们之间存在一条边 这样整个网络拓扑就可抽象为一个只含有节点和边的图 参与SPF算法的路由器执行如下两个任务以获得网络拓扑结构： 周期性地测试与相邻路由器的连接状态 周期性地把连接状态广播给其他路由器 每个路由器在获得整个网络的拓扑结构后，就可以各自独立地使用Dijkstra最短路径算法来计算从本路由到其他路由的最短路。AEDCB212113Dijkatra最短路径算法最短路径算法F3552Dijkatra算法计算结果算法计算结果AEDCB212113计计算算BCDEF02,A5,A1,A ,- ,-12

30、,A4,D2,D ,-22,A4,D4,E33,E4,E44,E源点源点A到所有结点的最短路径到所有结点的最短路径F3552DFEABC11212L-S图图SPF树树 每个路由器周期性地收集和发送信息每个路由器周期性地收集和发送信息 主动测试其到所有邻居的链接状态（度量值）主动测试其到所有邻居的链接状态（度量值） 向所有的路由器发送（广播）自己拥有的状态信息向所有的路由器发送（广播）自己拥有的状态信息 得到一个全网的、动态的逻辑链路状态（得到一个全网的、动态的逻辑链路状态（L-S）图）图 每个路由器刷新自己的路由表每个路由器刷新自己的路由表 当当L-S变化时，用最短路径优先变化时，用最短路径优

31、先(SPF)算法重新计算本地路由算法重新计算本地路由DCAB链路状态算法的基本概念链路状态算法的基本概念_路路由由表表SPF算法算法拓扑数据库拓扑数据库（L-S图）图）SPF树树L-S包包OSPF划分编号区域（划分编号区域（Area）国家主干国家主干Area1Area0Area2AreaN地区主干地区主干主干路由器主干路由器域边界路由器域边界路由器域内路由器域内路由器.域内路由器域内路由器 只拥有本域的路由信息；只拥有本域的路由信息； 具有相同的具有相同的L-S图，采用相同的图，采用相同的SPF算法；算法； 采用扩散方式广播自己获得的网络知识采用扩散方式广播自己获得的网络知识（邻居和开销）；（邻居和开销）； 根据扩散的信息修改根据扩散的信息修改L-S图，计算到域内图，计算到域内其他路由器的最短路径；其他路由器的最短路径； 根据计算机结果维护各自的路由表。根据计算机结果维护各自的路由表。域边界路由器域边界路由器 具有域内路由器的功能；具有域内路由器的功能； 拥有相邻域的拥有相邻域的L-S信息，并计算到达相邻域的信息，并计算到达相邻域的最短路径；最短路径； 域间的分组交换都通过其进行路径选择和数据域间的分组交换都通过其进行路径选择和数据交换。交换。例如：例如： 本域的路由器通过域边界路由器把分组送往主