第五章 路由算法

1、第五章第五章 路由算法路由算法5.1 路由算法概述路由算法概述 网络层的任务网络层的任务 建立、维持、中止网络的连接建立、维持、中止网络的连接 网络层的核心：路由算法网络层的核心：路由算法 路由算法的功能：指引分组通过通信子网到达目的节路由算法的功能：指引分组通过通信子网到达目的节点点 为源节点和目的节点对选择传输路径；为源节点和目的节点对选择传输路径； 将分组正确地送到目的节点。将分组正确地送到目的节点。5.1 路由算法概述路由算法概述5.1 路由算法概述路由算法概述 路由选择的优劣将直接影响网络的性能路由选择的优劣将直接影响网络的性能1.1.源节点源节点 1 1、2 2的输入业务的输入业务

2、量分别为量分别为 5 5个单位个单位2.2.源节点源节点 1 1的输入业务量的输入业务量分别为分别为 5 5个单位；源节个单位；源节点点 2 2的输入业务量分别的输入业务量分别为为 1515个单位；个单位； 轻负荷条件下，减少时延轻负荷条件下，减少时延 高负荷条件下，保证时延高负荷条件下，保证时延的前提下，增加网络通过的前提下，增加网络通过量量5.1.1 路由选择算法的分类路由选择算法的分类 决策地点决策地点 集中式集中式 分布式分布式 决策时间决策时间 分组（数据报）分组（数据报） 会话（虚电路）会话（虚电路） 性能评价准则性能评价准则 吞吐量吞吐量 时延时延 链路数链路数 设施代价设施代价

3、 路由选择所基于的信息源路由选择所基于的信息源 本地本地 相邻节点相邻节点 路径上的节点路径上的节点 所有节点所有节点 路由选择对网络的适应性路由选择对网络的适应性 静态静态 自适应自适应 根据负载、拓扑结构的变化自适应地调整根据负载、拓扑结构的变化自适应地调整路由路由5.1.2 对路由选择算法的要求对路由选择算法的要求 正确性正确性 到达目的地；交付给目的地，不再转发到达目的地；交付给目的地，不再转发 计算简单计算简单 运算量小；路由计算所需信息的获取过程占用带宽少运算量小；路由计算所需信息的获取过程占用带宽少 自适应性自适应性 业务量；拓扑业务量；拓扑 稳定性稳定性 震荡少震荡少 公平性公

4、平性用户用户 最优性最优性 基于某项性能准则基于某项性能准则 上述要求之间存在矛盾上述要求之间存在矛盾5.1.3 路由算法的实现路由算法的实现 路由表路由表 路由表：存储了分组的传送路径路由表：存储了分组的传送路径(下一跳下一跳)5.1.3 路由算法的实现路由算法的实现 路由表路由表 路由环路问题路由环路问题 路由表中的附加信息路由表中的附加信息5.1.4 路由算法与流量控制的关系路由算法与流量控制的关系 “流量控制流量控制”根据时延调整负载进入网络的吞吐量；根据时延调整负载进入网络的吞吐量； 路由算法影响分组的传输时延；路由算法影响分组的传输时延；5.2 常用路由算法常用路由算法 网内路由网

5、内路由 网际路由网际路由5.2.1 广域网中的路由算法广域网中的路由算法1. 广播广播接收节点常常是全网所有成员接收节点常常是全网所有成员传播公共信息、拓扑变化信息（节点移动，节电传播公共信息、拓扑变化信息（节点移动，节电开关、链路故障）开关、链路故障）路由算法路由算法洪泛洪泛生成树生成树单播单播Delivery: Broadcast RoutingSOURCEDATA洪泛算法洪泛算法Delivery: Broadcast RoutingSOURCEDelivery: Broadcast RoutingSOURCE5.2.1 广域网中的路由算法广域网中的路由算法 洪泛算法的问题洪泛算法的问题

6、分组的传输次数多分组的传输次数多 附加规则附加规则 不重复转发，用节点标识符和序号来保证不重复转发，用节点标识符和序号来保证 不回传不回传5.2.1 广域网中的路由算法广域网中的路由算法2. 最短路由最短路由3. 最佳路由最佳路由最短路由：一对节点之间的路径最优；最短路由：一对节点之间的路径最优；限制了网络的通过量；限制了网络的通过量；为避免震荡，适应业务变化的能力受限。为避免震荡，适应业务变化的能力受限。最佳路由基于平均指标的最优化，在全网搜索可最佳路由基于平均指标的最优化，在全网搜索可能的路径，可将流量分配在多条路径上。能的路径，可将流量分配在多条路径上。5.2.2 互连网中的路由算法互连

7、网中的路由算法 网关网关 WAN与与WAN之间之间 协议转换、路由协议转换、路由 网桥网桥 LAN与与LAN之间之间 Translate a packet from one format into another, e.g., ethernet to optical (FDDI) MAC层协议层协议 路由器路由器 connect and route between two networks 网络层网络层 网络规模扩大与路由器内存有限之间的矛盾网络规模扩大与路由器内存有限之间的矛盾 分级分级5.2.2 自组织网络中的路由算法自组织网络中的路由算法 自组织网络？自组织网络？ 路由算法分类路由算法分

8、类5.3 最短路由算法最短路由算法 图论基本概念图论基本概念 图：图：定义成空间中一些定义成空间中一些节点节点（顶点）和连接这些节点（顶点）和连接这些节点的的链路链路（边）的（边）的集合集合。 无向图：无向图：链路无方向链路无方向 有向图：有向图：链路有方向链路有方向 关联：关联：如果节点是链路如果节点是链路e的一个端点，则称边的一个端点，则称边e和顶和顶点节点相点节点相关联关联 方向性行走：方向性行走：指一个节点序列指一个节点序列 与该与该序列相关联的链路序列相关联的链路 为为G中中的链路的链路 方向性路径方向性路径（path）：无重复节点的方向性行走）：无重复节点的方向性行走12( ,)l

9、n nn1( ,),11iiln nnil 5.3 最短路由算法最短路由算法 图论基本概念（图论基本概念（2） 方向性环：源节点与目的节点相同的方向性路径方向性环：源节点与目的节点相同的方向性路径 强连通方向图：图中的每一对节点强连通方向图：图中的每一对节点i,j都有一条方向性都有一条方向性路径路径 连通方向图：方向图对应的无方向图是连通的。连通方向图：方向图对应的无方向图是连通的。5.3 最短路由算法最短路由算法 最短路径：最短路径： 给每条链路给每条链路 指定一个实数作为其长度指定一个实数作为其长度 一条方向性路径一条方向性路径 的长度为的长度为 最短路径问题就是寻找从最短路径问题就是寻找

10、从i到到m的最小长度方向性的最小长度方向性路径路径 链路长度可以是成本、时延、可靠性。链路长度可以是成本、时延、可靠性。( , )i jijdijjklmddd( , , , ,)pi j kl m5.3 最短路由算法最短路由算法 集中式最短路径算法集中式最短路径算法 Bellman-Ford算法算法 点对多点点对多点 Dijkstra算法算法 点对多点点对多点 Floyd-Warshall算法。算法。 多点对多点多点对多点 寻找网络中一个节点到其它寻找网络中一个节点到其它所有节点所有节点的的最短路由最短路由。 定义：最短（定义：最短（ ）行走（）行走（Walk）是指在下列约束条件下从）是指在

11、下列约束条件下从给定节点给定节点i到目的节点到目的节点1的最短的最短Walk。 该行走（该行走（Walk）中最多包括）中最多包括h条链路，即条链路，即Walk中包含的中包含的链路数至多为链路数至多为h条。条。 该行走（该行走（Walk）仅经过目的节点）仅经过目的节点1一次。一次。 最短行走最短行走Walk长度用长度用 表示。节点表示。节点i经过条链路到达目经过条链路到达目的节点的节点1的行走长度的行走长度 对所有的对所有的h，令，令 。 B-F算法的核心思想是通过下面的算法的核心思想是通过下面的公式进行迭代，即公式进行迭代，即Bellman-Ford算法算法hhiD01hDmin1hjijjh

12、DdDi1iBellman-Ford算法算法第一步：初始化。即对所有第一步：初始化。即对所有i （ ）令）令 。第二步：对所有的节点第二步：对所有的节点j（ ），先找出一条链路的最），先找出一条链路的最短（短（ ）的）的Walk长度；长度；第三步：对所有的节点第三步：对所有的节点j（ ），再找出经两条链路的），再找出经两条链路的最短（最短（ ）的）的Walk长度；长度；依次类推：如果对所有依次类推：如果对所有i有：有： （即继续迭代下去以（即继续迭代下去以后不会再有变化），则算法在后不会再有变化），则算法在h次迭代后结束。次迭代后结束。0iDmin01jijjDdDimin12jijjDdDi

13、1hihiDDmin1hjijjhDdDi最短最短Walk长度等于最短路径长度的充分必要条件长度等于最短路径长度的充分必要条件定理定理1：对于：对于B-F算法算法初始条件：对所有初始条件：对所有 ，有，有有：有： 由该算法产生的由该算法产生的 等于最短（等于最短（ ）Walk长度长度 当且仅当所有不包括节点当且仅当所有不包括节点1的环具有非负的长度，算的环具有非负的长度，算法在有限次迭代后结束。法在有限次迭代后结束。此外，如果算法在最多此外，如果算法在最多 次迭代后结束，则结束次迭代后结束，则结束时时 就是从就是从到到1的最短路径长度。的最短路径长度。1i 0iD hiDhkNhiD定理定理1

14、 1中中阐明了与最短（阐明了与最短（ ）WalkWalk的关系。的关系。阐阐明了算法何时结束，结束时所得的结果是否是最短路径。明了算法何时结束，结束时所得的结果是否是最短路径。hiDh最短最短Walk长度等于最短路径长度的充分必要条件长度等于最短路径长度的充分必要条件证明证明：我们采用归纳法证明（：我们采用归纳法证明（1）。）。 因为因为 ，所以显然有，所以显然有 等于最短（等于最短（ ）的）的Walk长度；长度； 假定假定 是等于最短（是等于最短（ ）的）的Walk长度，求证长度，求证 是等于最短（是等于最短（ ）的）的Walk长度。长度。h11iiDd1iD1hiDh1hiD1h证明证明：

15、从从i到到1的最短（的最短（ ）Walk包含的链路数有两种情况：包含的链路数有两种情况：一种情况是链路数小于一种情况是链路数小于h+1，在此情况下，有，在此情况下，有Walk长度长度等于等于 ；另一种情况是链路数等于另一种情况是链路数等于h+1。在后一种情况下，有最。在后一种情况下，有最短（短（ ）Walk长度长度 根据根据 等于最短（等于最短（ ）Walk的假设，对所有的有的假设，对所有的有 因此有因此有 最短（最短（ ）Walk长度长度 1hhiD1h11min,min,minhhhhiiiijjjDDDdDhiDhkh1kkjjDD11minminhhhhiijjijjijjDdDdDD

16、1h1hiD证明证明：（2）如果）如果B-F算法在算法在h次迭代后结束，即有次迭代后结束，即有 对所有对所有i和和 则我们不可能通过添加更多的链路来减少最短的则我们不可能通过添加更多的链路来减少最短的Walk长长度。（否则，算法没有结束。）度。（否则，算法没有结束。）也就是不可能存在一个负长度的（不包括目的节点）环。也就是不可能存在一个负长度的（不包括目的节点）环。因为这样的负长度的任意大次数的重复将使因为这样的负长度的任意大次数的重复将使Walk的长度的长度任意的小，这与上式相矛盾。任意的小，这与上式相矛盾。khiiDDkh证明证明：相反，假定所有的不包括相反，假定所有的不包括1的环具有非负

17、的长度。从最短的环具有非负的长度。从最短（ ）Walk中删除这些环，我们会得到长度相同或中删除这些环，我们会得到长度相同或更短的路径。因此，对每一个更短的路径。因此，对每一个i和和h，总存在一条从，总存在一条从i到到1的的最短（最短（ ）Walk，其相应的最短的路径长度等于，其相应的最短的路径长度等于 。由于路径中没有环，路径可能包括。由于路径中没有环，路径可能包括最多最多N-1条链路。因此条链路。因此 ，对所有，对所有i成立。即成立。即算法在最多算法在最多N次迭代后结束。次迭代后结束。 hhhiD1NNiiDD直接来构造最短的路径直接来构造最短的路径 假定所有不包括节点假定所有不包括节点1的

18、环具有非负的长度，用的环具有非负的长度，用Di表示从表示从节点节点i到达目的节点到达目的节点1的最短路径长度。根据前面的讨论，的最短路径长度。根据前面的讨论，当当B-F算法结束时，有算法结束时，有该式称为该式称为Bellman方程方程 。它表明从节点。它表明从节点i到达目的节点到达目的节点1的最短路径长度，等于的最短路径长度，等于i到达该路径上第一个节点到达该路径上第一个节点j的链路的链路长度，加上该节点长度，加上该节点j到达目的节点到达目的节点1的最短路径长度。从的最短路径长度。从该方程出发，只要所有不包括该方程出发，只要所有不包括1的环具有正的长度（而不的环具有正的长度（而不是是0长度）的

19、情况下，我们就可以很容易地找到最短路径长度）的情况下，我们就可以很容易地找到最短路径（而不是最短路径长度）。（而不是最短路径长度）。 miniijjjDdD1i 10D 具体方法如下具体方法如下 ：对于每一个节点对于每一个节点 ，选择一条满足，选择一条满足 的最小值的链路的最小值的链路 ，利用这些，利用这些N-1条链路组成一个子条链路组成一个子图，则图，则i沿该子图到达目的节点沿该子图到达目的节点1的路径即为最短路径。的路径即为最短路径。 1i miniijjjDdD( ,)ii j利用上面的构造方法，可以证明：如果没有利用上面的构造方法，可以证明：如果没有0长度（或负长度（或负长度）的环，则

20、长度）的环，则Bellman方程式有惟一解。方程式有惟一解。如果有不包括节点如果有不包括节点1的环的长度为的环的长度为0，则，则Bellman方程不方程不再具有惟一解。再具有惟一解。路径长度惟一，并不意味着路径惟一。路径长度惟一，并不意味着路径惟一。利用该结论，可以证明：即使初始条件利用该结论，可以证明：即使初始条件 ， 是任意是任意数（而不是数（而不是 ），），B-F算法都能正确工作，对于不算法都能正确工作，对于不同的节点，迭代的过程可以以任意顺序并行进行。同的节点，迭代的过程可以以任意顺序并行进行。 0iD1i 0iD B-F算法的运算量算法的运算量 设有设有N个节点，个节点， B-F算法

21、最多循环算法最多循环N次次 每次循环处理每次循环处理N-1个节点个节点 对每个节点求最小路径，有对每个节点求最小路径，有N-1种选择种选择 最坏情况下计算量为最坏情况下计算量为 ，表示为，表示为3N3()O N2 Dijkstra算法算法 Dijkstra算法算法也是一种典型的也是一种典型的点对多点点对多点的路由选的路由选择算法，即通过迭代，寻找某一节点到网络中其择算法，即通过迭代，寻找某一节点到网络中其它所有节点的最短路径。它所有节点的最短路径。假定所有链路的长度均为非负。假定所有链路的长度均为非负。Dijkstra算法算法思路思路显然有：节点显然有：节点1的最近的邻节点通过单条链路到的最近

22、的邻节点通过单条链路到达目的节点达目的节点1是最短路径中最短的。由于链路长是最短路径中最短的。由于链路长度非负，所以任何多条链路组成的路径的长度都度非负，所以任何多条链路组成的路径的长度都不可能短于第一条链路的长度。不可能短于第一条链路的长度。下一个最短的肯定是节点下一个最短的肯定是节点1的次最近的邻节点所的次最近的邻节点所对应的单条链路，或者是通过前面选定的节点的对应的单条链路，或者是通过前面选定的节点的有两条链路组成的路径，依次类推。有两条链路组成的路径，依次类推。Dijkstra算法算法Dijkstra算法算法Di为每个节点为每个节点i到达目的节点到达目的节点1的最短路径长度的预估值的最

23、短路径长度的预估值如果在迭代的过程中，如果在迭代的过程中，Di已变成一个确定的值，称节点已变成一个确定的值，称节点i为永久标定的节点，这些永久标定的节点的集合用为永久标定的节点，这些永久标定的节点的集合用P表示。表示。在算法的每一步中，在在算法的每一步中，在P以外的节点中，选择与目的节点以外的节点中，选择与目的节点1最近的节点加入到集合最近的节点加入到集合P中。中。 1. 初始化，初始化，如果如果 ，则，则 。2. 寻找下一个与目的节点最近的节点，寻找下一个与目的节点最近的节点， 置置 如果如果P包括了所有的节点，则算法结束。包括了所有的节点，则算法结束。3. 更改标定值，即对所有的更改标定值

24、，即对所有的 ，置，置 返回第返回第步。步。1P 10D 1jjDd1j ( ,1)jA1 jd iPminijj PDD PPijPmin,jjjiiiDD dDDijkstra算法算法Dijkstra算法运算量算法运算量有有N个节点，则有个节点，则有N-1次叠代，即次叠代，即N-1 个节点均成为永久节点；个节点均成为永久节点；每次叠代中，更改标定值，最多每次叠代中，更改标定值，最多N-1个点个点在最坏的情况下，在最坏的情况下，Dijkstra算法的复杂度为算法的复杂度为 ，B-F算法的复杂度为算法的复杂度为 。即。即Dijkstra算法的复杂度要低于算法的复杂度要低于B-F我们可以看到：我

25、们可以看到： ，对所有，对所有 。 对于每一个节点对于每一个节点j，Dj是从是从j到目的节点到目的节点1的最短距离。该路径使用的最短距离。该路径使用的所有节点（除的所有节点（除j以外）都属于以外）都属于P。2()O N3()O NijDD,iP jP3 Floyd-Warshall算法（算法（F-W算法）算法） B-F算法和算法和Dijkstra算法都是求解所有节点到一个特算法都是求解所有节点到一个特定的目的节点之间的最短路径，定的目的节点之间的最短路径， F-W算法则是多点对多点的路由选择算法。算法则是多点对多点的路由选择算法。 假设：假设： 链路的长度可正可负；链路的长度可正可负； 不存在

26、负长度的环；不存在负长度的环；3 Floyd-Warshall算法（算法（F-W算法）算法） 基本思想：基本思想：是在是在 的路径之间通过添加中间节点来减小路的路径之间通过添加中间节点来减小路径长度。径长度。 以单链路（无中间节点）的距离作为最短路径的初始以单链路（无中间节点）的距离作为最短路径的初始估计。估计。然后，在仅允许节点然后，在仅允许节点1作为中间节点的情况下，计算最作为中间节点的情况下，计算最短路径，短路径，接着，在允许节点接着，在允许节点1和节点和节点2作为中间节点的情况下计作为中间节点的情况下计算最短距离，算最短距离，依次类推。依次类推。 ij3 Floyd-Warshall算

27、法（算法（F-W算法）算法）具体算法描述如下：具体算法描述如下： 令令 是可以用是可以用1、2n作为中间节点的从作为中间节点的从i到到j的最短的最短路径长度，路径长度，算法开始时算法开始时 ，对所有，对所有i，j， 。对于对于 ，有，有上式假设上式假设i到到j的最短路径的最短路径 （以（以1，2n作为中间节点）作为中间节点）的条件，给出了计算在的条件，给出了计算在i到到j的最短路径上可添加节点的最短路径上可添加节点n+1后的最短路径长度。后的最短路径长度。 复杂度为复杂度为 。N个节点，每个节点叠代个节点，每个节点叠代N-1次，次，nijD0ijijDdij0,1,.,1nN1(1)(1)mi

28、n,nnnnijiji nnjDDDDijnijD3()O N 前面讨论的三种最短路由算法的构造方法，都是通过迭代的前面讨论的三种最短路由算法的构造方法，都是通过迭代的过程求得最终结果。但其主要差别是迭代的内容不同。过程求得最终结果。但其主要差别是迭代的内容不同。 在在B-F算法中，迭代的是路径中的链路数，即使用一条，两算法中，迭代的是路径中的链路数，即使用一条，两条，条，直到，直到N-1条链路。条链路。 在在Dijkstra算法中迭代的是路径的长度，即最短长度，次短长算法中迭代的是路径的长度，即最短长度，次短长度，度，。 而在而在F-W算法中，是对路径的中间节点进行的迭代，即一个中算法中，是

29、对路径的中间节点进行的迭代，即一个中间节点，两个中间节点，间节点，两个中间节点，。分布式最短路径算法分布式最短路径算法 集中式集中式路由算法是指网络的路由是由路由算法是指网络的路由是由路由控制中心路由控制中心计计算的，该中心周期性收集各链路的状态，经过路由计算的，该中心周期性收集各链路的状态，经过路由计算后周期性地向各网络节点提供路由表。算后周期性地向各网络节点提供路由表。 分布式分布式路由是指网络中所有节点通过相互交换路由信路由是指网络中所有节点通过相互交换路由信息，独立地计算到达各节点的路由。息，独立地计算到达各节点的路由。5.3.2 分布式最短路径算法分布式最短路径算法 分布式路由算法的

30、特点分布式路由算法的特点 节点用于存储网络拓扑结构的空间较少；节点用于存储网络拓扑结构的空间较少； 每个节点每个节点周期性周期性的从相邻的节点获得网络状态信息，同时的从相邻的节点获得网络状态信息，同时也将本节点做出的决定周期性的通知周围的各节点，以使也将本节点做出的决定周期性的通知周围的各节点，以使这些节点不断的根据网络新的状态更新其路由选择。这些节点不断的根据网络新的状态更新其路由选择。 各个节点的路由表相互作用；各个节点的路由表相互作用； 整个网络的路由经常处于一种整个网络的路由经常处于一种动态变化动态变化的状态。当网络状的状态。当网络状态发生变化时，会影响到许多节点的路由表。要经过一定态

31、发生变化时，会影响到许多节点的路由表。要经过一定的时间以后，各路由表中的数据才能达到稳定的数值。的时间以后，各路由表中的数据才能达到稳定的数值。 分布式路由选择算法的核心思想是各个节点独立的计算最分布式路由选择算法的核心思想是各个节点独立的计算最短路径。短路径。 典型的分布式最短路径选择算法有典型的分布式最短路径选择算法有距离矢量路由算法距离矢量路由算法和和链路链路状态路由算法状态路由算法。一一 距离矢量路由算法距离矢量路由算法 距离矢量路由算法距离矢量路由算法（Distance Vector Routing）算）算法法分布式分布式B-F算法算法的具体实现。的具体实现。 路由表结构路由表结构

32、在距离矢量路由表中，每个在距离矢量路由表中，每个路由器路由器维护一张维护一张路由路由表表，该表中记录了到网络中其它所有目的节点的，该表中记录了到网络中其它所有目的节点的路由信息。包括到该目的节点的路由信息。包括到该目的节点的下一跳节点下一跳节点（即（即本节点通过哪个邻节点到达指定的目的节点），本节点通过哪个邻节点到达指定的目的节点），和到达该目的节点所需的和到达该目的节点所需的“距离距离”的估计值。的估计值。一一 距离矢量路由算法距离矢量路由算法 算法：算法： 初始化初始化 每当收到邻节点路由信息每当收到邻节点路由信息 ，按下式更新路，按下式更新路由表由表 为节点为节点i 的邻居节点集合的邻居

33、节点集合 将更新的路由表通知其临界点将更新的路由表通知其临界点1i 0iD 010D ( )miniijjj N iDdDjD( )N i( )miniijjj N iDdD一一 距离矢量路由算法距离矢量路由算法 在表中使用的距离量度可以是在表中使用的距离量度可以是跳数、时延、某一路径排队的跳数、时延、某一路径排队的总分组数或者其它类似的量度总分组数或者其它类似的量度。每一个节点都确知它的每一。每一个节点都确知它的每一个邻节点的距离。个邻节点的距离。 如果采用时延作为距离的量度，每个节点应当能够利用一个如果采用时延作为距离的量度，每个节点应当能够利用一个特殊的特殊的“回声回声”（ECHO）分组

34、来直接测量该时延。接收节点）分组来直接测量该时延。接收节点收到收到“回声回声”分组后，只对它加上时间标记后就立即送回。分组后，只对它加上时间标记后就立即送回。 以时延作为距离的量度。每隔以时延作为距离的量度。每隔T秒，每个节点向它的每个邻节秒，每个节点向它的每个邻节点发送一个路由信息分组，该分组包括了发送节点已知的目点发送一个路由信息分组，该分组包括了发送节点已知的目的节点的下一跳节点和时延估计值。同样，每一个节点都会的节点的下一跳节点和时延估计值。同样，每一个节点都会收到它所有的邻节点发送来的路由信息分组。收到它所有的邻节点发送来的路由信息分组。一一 距离矢量路由算法距离矢量路由算法计数至无

35、穷问题（对链路故障反应较慢）计数至无穷问题（对链路故障反应较慢）它对好消息的反应迅速，但对坏消息却反应迟钝它对好消息的反应迅速，但对坏消息却反应迟钝 讨论坏消息的传播速度。讨论坏消息的传播速度。 在实际系统中，我们可以将无穷大设置为网络的在实际系统中，我们可以将无穷大设置为网络的最大跳数加最大跳数加1。但是当采用时延作为距离的长度时，。但是当采用时延作为距离的长度时，将很难定义一个合适的时延上界。该时延的上界将很难定义一个合适的时延上界。该时延的上界应足够大，以避免将长时延的路径认为是故障的应足够大，以避免将长时延的路径认为是故障的链路。链路。 2 水平分裂算法水平分裂算法 水平分裂算法与距离

36、矢量算法的工作过程基本一样，不同之水平分裂算法与距离矢量算法的工作过程基本一样，不同之处在于如果节点处在于如果节点I到达某一目的节点到达某一目的节点J的距离是通过节点的距离是通过节点X得到得到的，则节点的，则节点I将不会向节点将不会向节点X报告有关节点报告有关节点J的信息（即节点的信息（即节点I向向节点节点X报告的到达节点报告的到达节点J的距离为无穷大）。的距离为无穷大）。 平分割法虽然能够解决一些计数平分割法虽然能够解决一些计数至无穷问题，但有时候也不能正至无穷问题，但有时候也不能正常工作。常工作。IXJ二二 链路状态路由算法链路状态路由算法 在在1979年之前，年之前，ARPANET都是采

37、用的距离矢量路由都是采用的距离矢量路由算法。之后，就用链路状态路由算法（算法。之后，就用链路状态路由算法（Link State Routing）取代了距离矢量路由算法。）取代了距离矢量路由算法。 其主要原因有两个。其主要原因有两个。 第一，因为在距离矢量算法中，时延的度量是仅第一，因为在距离矢量算法中，时延的度量是仅仅是队列的长度，而并没有考虑后来链路带宽的仅是队列的长度，而并没有考虑后来链路带宽的增长；增长； 第二，距离矢量算法的收敛速度比较慢，即使是第二，距离矢量算法的收敛速度比较慢，即使是采用了类似于水平分割这样的技术，也需要耗费采用了类似于水平分割这样的技术，也需要耗费过多的时间用于记

38、录信息。过多的时间用于记录信息。 路由计算采用路由计算采用Dijkstra算法算法二二 链路状态路由算法链路状态路由算法 链路状态路由算法的思想非常简单，它包括以下五个部分：链路状态路由算法的思想非常简单，它包括以下五个部分： 发现邻节点，并获取它们的地址；发现邻节点，并获取它们的地址； 测量到达每一个邻节点的时延或成本；测量到达每一个邻节点的时延或成本； 构造一个分组来通告它所知道的所有路由信息；构造一个分组来通告它所知道的所有路由信息； 发送该分组到所有其它节点；发送该分组到所有其它节点； 计算到所有其它节点的最短路径。计算到所有其它节点的最短路径。 事实上，完整的拓扑结构和所有的时延都已

39、经分发到网络中事实上，完整的拓扑结构和所有的时延都已经分发到网络中的每一个节点。随后，每个节点都可以用的每一个节点。随后，每个节点都可以用DijkstraDijkstra算法来求算法来求得到其它所有节点的最短路径。得到其它所有节点的最短路径。二二 链路状态路由算法链路状态路由算法 发现邻节点发现邻节点 当一个路由器启动以后，它的第一个任务就是要知道当一个路由器启动以后，它的第一个任务就是要知道它的邻节点是谁。具体实现的方法是：该路由器在每它的邻节点是谁。具体实现的方法是：该路由器在每一个输出链路上广播一个特殊的一个输出链路上广播一个特殊的Hello分组，在这些分组，在这些链路另一端的路由器将会

40、发送回一个应答分组，告知链路另一端的路由器将会发送回一个应答分组，告知它是谁。所有路由器的名字（地址）必须是全球唯一它是谁。所有路由器的名字（地址）必须是全球唯一的。的。 二二 链路状态路由算法链路状态路由算法 当两个或多个路由器通过当两个或多个路由器通过LAN互连时，如图互连时，如图5-14（a）所）所示，这时我们把示，这时我们把LAN看成一个虚拟的节点看成一个虚拟的节点N，如图，如图5-14（b）所示。这时所示。这时A到到C的路由就可以看成是的路由就可以看成是ANC。 二二 链路状态路由算法链路状态路由算法 测量链路时延或成本测量链路时延或成本链路状态路由算法要求每个路由器确知到达每一个邻

41、节点链路状态路由算法要求每个路由器确知到达每一个邻节点的时延或对该时延有一个合理的估计。确定该时延的最直的时延或对该时延有一个合理的估计。确定该时延的最直接的方法是发送一个特殊的接的方法是发送一个特殊的ECHOECHO分组给每个邻节点，并要分组给每个邻节点，并要求每个邻节点立即发回该分组。将测量的来回时延除以求每个邻节点立即发回该分组。将测量的来回时延除以2 2就就可以得到该链路时延的估计。为了得到较好的结果，可测可以得到该链路时延的估计。为了得到较好的结果，可测量多次后取平均。量多次后取平均。在测量链路时延时，既可以考虑排队的时延（链路的负在测量链路时延时，既可以考虑排队的时延（链路的负荷）

42、，也可以不考虑排队的时延。考虑排队时延（链路负荷），也可以不考虑排队的时延。考虑排队时延（链路负荷）的优点是可以获得较好的性能，但是可能会引起路由荷）的优点是可以获得较好的性能，但是可能会引起路由的振荡。的振荡。二二 链路状态路由算法链路状态路由算法 构造链路状态分组构造链路状态分组 每个节点都构造一个自己的链路状态分组，它包括发送节每个节点都构造一个自己的链路状态分组，它包括发送节点的标号、该分组的序号和寿命，以及发送节点的邻节点点的标号、该分组的序号和寿命，以及发送节点的邻节点列表及发送节点到这些邻节点的链路时延。列表及发送节点到这些邻节点的链路时延。 何时构造这些分组。何时构造这些分组。

43、 一种方法是周期性地构造这些分组；一种方法是周期性地构造这些分组； 另一种方法是在链路状态变化（如故障、恢复工作或特另一种方法是在链路状态变化（如故障、恢复工作或特性改变）时才构造这些分组。性改变）时才构造这些分组。 二二 链路状态路由算法链路状态路由算法二二 链路状态路由算法链路状态路由算法 分发链路状态分组分发链路状态分组该算法的中最具技巧性的部分就是如何可靠的分发链路状态分组。当该算法的中最具技巧性的部分就是如何可靠的分发链路状态分组。当链路状态分组被发布后，首先得到该分组的路由器将改变其路由选择。链路状态分组被发布后，首先得到该分组的路由器将改变其路由选择。同时，别的路由器可能还在使用

44、不同的旧版本的链路信息，这样将导同时，别的路由器可能还在使用不同的旧版本的链路信息，这样将导致各节点对当前网络拓扑的看法不一致性，从而计算出的路由可能出致各节点对当前网络拓扑的看法不一致性，从而计算出的路由可能出现死循环、不可达或其它问题。现死循环、不可达或其它问题。链路状态分组分发的最基本方法是采用泛洪（链路状态分组分发的最基本方法是采用泛洪（FloodingFlooding）方式。为防）方式。为防止每个节点处理和中转过时的链路状态分组，在这些分组中引入了序止每个节点处理和中转过时的链路状态分组，在这些分组中引入了序号。每个节点仅中转序号大于已记录的最大序号的分组，为了防止序号。每个节点仅中

45、转序号大于已记录的最大序号的分组，为了防止序号出错，在分组中还引入了寿命，寿命每秒递减一次，如果寿命为号出错，在分组中还引入了寿命，寿命每秒递减一次，如果寿命为0 0，则该分组将被丢弃。则该分组将被丢弃。二二 链路状态路由算法链路状态路由算法 为了提高传输的可靠性，所有链路状态分组都需为了提高传输的可靠性，所有链路状态分组都需要应答。为了处理链路状态分组在泛洪中需要发要应答。为了处理链路状态分组在泛洪中需要发往哪些邻节点、需要对哪条链路的分组进行应答往哪些邻节点、需要对哪条链路的分组进行应答的问题，每个节点需构造一个分组存储数据结构。的问题，每个节点需构造一个分组存储数据结构。该图是图该图是图

46、5-15拓扑中节点拓扑中节点B的数据结构。图中每一的数据结构。图中每一行对应刚刚到达，但还没有完全处理的链路状态行对应刚刚到达，但还没有完全处理的链路状态分组。由于节点分组。由于节点B有三个邻节点有三个邻节点A、C和和F，所以发，所以发送标志指明应当发送给哪个邻节点，应答标志指送标志指明应当发送给哪个邻节点，应答标志指明应答哪个邻节点。明应答哪个邻节点。 二二 链路状态路由算法链路状态路由算法 计算新的路由计算新的路由 当每个节点获得所有的链路状态分组以后，它可以构造一当每个节点获得所有的链路状态分组以后，它可以构造一个完整的网络拓扑，此时每个节点就可以运行个完整的网络拓扑，此时每个节点就可以

47、运行Dijkstra算法算法来构造到达所有目的的节点的最短路由。来构造到达所有目的的节点的最短路由。 链路状态路由算法已广泛用于多种实际网络中，例如链路状态路由算法已广泛用于多种实际网络中，例如Internet中的中的OSPF采用了该算法，采用了该算法，ISO的无连接网络层协议（的无连接网络层协议（CLNP）使用的使用的IS-IS（Intermediate System-to-Intermediate System）协议也是采用该算法。）协议也是采用该算法。IS-IS中交换的信息是用于计中交换的信息是用于计算最短路由的网络拓扑图（而不仅仅是链路状态分组），它算最短路由的网络拓扑图（而不仅仅是链

48、路状态分组），它还可以支持多种网络协议（如还可以支持多种网络协议（如IP，IPX，AppleTalk等）。等）。5.4 自适应最短路由的稳定性分析自适应最短路由的稳定性分析自适应最短路由的稳定性分析自适应最短路由的稳定性分析 路由算法分类路由算法分类 确定型策略（确定型策略（Deterministic Algorithm） 基于网络拓扑和平均分组时延要求，以某一准则来选择基于网络拓扑和平均分组时延要求，以某一准则来选择分组的路径。这类策略包括：扩散式路由算法，随机式分组的路径。这类策略包括：扩散式路由算法，随机式路由算法，固定式最佳路由算法等。路由算法，固定式最佳路由算法等。 自适应型策略（自

49、适应型策略（Adaptive Algorithm）。）。 基于某一准则来确定在某一段时间内有效的路由，目的基于某一准则来确定在某一段时间内有效的路由，目的是为了适应业务和拓扑的变化。这类策略又可细分为：是为了适应业务和拓扑的变化。这类策略又可细分为：集中式自适应路由、分布式自适应路由算法。集中式自适应路由、分布式自适应路由算法。 如果在一段时间之后，算法最终是否可以有一个稳定的如果在一段时间之后，算法最终是否可以有一个稳定的解，会不会振荡？这就是我们要讨论的算法稳定性问题。解，会不会振荡？这就是我们要讨论的算法稳定性问题。 下面我们针对以链路长度最短为路由选择原则的自适下面我们针对以链路长度最

50、短为路由选择原则的自适应路由算法来分析其稳定性问题。这里，我们讨论一应路由算法来分析其稳定性问题。这里，我们讨论一种典型的情况，即链路的长度随着该链路的业务情况种典型的情况，即链路的长度随着该链路的业务情况变化而变化。很显然，业务量比较重的链路将会被指变化而变化。很显然，业务量比较重的链路将会被指定较大的链路长度。定较大的链路长度。 下面我们通过实例来看看数据报网络和虚电路网络的下面我们通过实例来看看数据报网络和虚电路网络的稳定性问题。稳定性问题。 1 数据报网络的稳定性数据报网络的稳定性 假定有一个网络如图假定有一个网络如图5-17所所示，它由示，它由16个节点组成，其个节点组成，其中节点中

51、节点16是惟一一个目的节是惟一一个目的节点。点。 网络中的每一个节点都可能有两条路径到达目的节点：一条网络中的每一个节点都可能有两条路径到达目的节点：一条是顺时针方向到达目的节点，另一条是逆时针方向到达目的是顺时针方向到达目的节点，另一条是逆时针方向到达目的节点。设链路节点。设链路 的长度的长度dij与链路上的流量与链路上的流量Fij成正比，这成正比，这里取里取 ，采用自适应最短路由准则。，采用自适应最短路由准则。 设节点设节点17、915输入的业务量为输入的业务量为1个单位，节点个单位，节点8输入的业输入的业务量为务量为 （ 是一个非常小的正数），网络每隔是一个非常小的正数），网络每隔T秒更

52、秒更新一次最短路由，即每个节点用前一个新一次最短路由，即每个节点用前一个T内的内的Fij决定当前决定当前T秒秒的路由。的路由。 ( , )i jijijdF0 出现上述振荡的原因是各链路的长度（流量）取决于路由的出现上述振荡的原因是各链路的长度（流量）取决于路由的选择，而路由的选择又取决于各链路的流量，这样就构成了选择，而路由的选择又取决于各链路的流量，这样就构成了反馈效应。在一般情况下，只要链路长度反馈效应。在一般情况下，只要链路长度dij是随着链路流量是随着链路流量Fij的增加而单调增长，且当的增加而单调增长，且当 时有，都会出现上述不稳定时有，都会出现上述不稳定的振荡现象。的振荡现象。

53、0ijF 为了消除或减缓上述振荡，一种方法是给每条链路的长度都为了消除或减缓上述振荡，一种方法是给每条链路的长度都增加一个正的常量增加一个正的常量 （ 称为偏置因子）。当称为偏置因子）。当 时时有有 。此时。此时 的选择就对路由的稳定性起着决定性的选择就对路由的稳定性起着决定性的作用。如果的作用。如果 相对于可能的链路长度足够大，则基本上是一相对于可能的链路长度足够大，则基本上是一个静态路由，且上述自适应最短路由就变成了一个最小跳数个静态路由，且上述自适应最短路由就变成了一个最小跳数的路由。此时，网络振荡的可能性很小，但网络对链路的阻的路由。此时，网络振荡的可能性很小，但网络对链路的阻塞将不敏

54、感。塞将不敏感。 另一种方法是引入一种机制，将链路长度在多个最短路由更另一种方法是引入一种机制，将链路长度在多个最短路由更新周期上平均，这样将改进路由算法的稳定性，但也降低了新周期上平均，这样将改进路由算法的稳定性，但也降低了网络对链路阻塞的敏感程度。网络对链路阻塞的敏感程度。 0ijF 0ijd5.5 路由信息的广播路由信息的广播路由信息的广播路由信息的广播 路由信息的交换是路由算法的基础。路由信息的交换是路由算法的基础。 在正常情况下，在正常情况下， 收集节点：收集网络路由信息的节点；收集节点：收集网络路由信息的节点； 路由信息广播：收集节点将路由信息发送到需要该信息的路由信息广播：收集节

55、点将路由信息发送到需要该信息的节点。节点。 分组的广播是一个难点问题。分组的广播是一个难点问题。这些困难主要体现在以下几个方面：这些困难主要体现在以下几个方面：1. 网络的拓扑信息必须通过链路来传输，而链路本网络的拓扑信息必须通过链路来传输，而链路本身可能有故障。在有中心的网络中，这个问题尤身可能有故障。在有中心的网络中，这个问题尤为严重。因为，当网络的部分节点通过一条可能为严重。因为，当网络的部分节点通过一条可能会故障的链路与网络中心相连时，如果该链路发会故障的链路与网络中心相连时，如果该链路发生了故障，则网络中的部分节点将会与网络中心生了故障，则网络中的部分节点将会与网络中心失去联系，从而

56、导致这些节点无法获知网络的拓失去联系，从而导致这些节点无法获知网络的拓扑信息。扑信息。 2. 网络中会存在多次拓扑变化（如链路断开后，又网络中会存在多次拓扑变化（如链路断开后，又在短时间内恢复正常），这就意味着们必须对旧在短时间内恢复正常），这就意味着们必须对旧的路由信息和新的路由信息加以区分。的路由信息和新的路由信息加以区分。如果网络采用泛洪的方式来广播拓扑变化信息，如果网络采用泛洪的方式来广播拓扑变化信息，当网络仅有一次拓扑变化时，泛洪方式可以正当网络仅有一次拓扑变化时，泛洪方式可以正常工作，但当网络有多次拓扑变化时，泛洪的常工作，但当网络有多次拓扑变化时，泛洪的方法将不能正常工作。方法将

57、不能正常工作。 链路链路n UPn UP链路链路n DOWNn DOWNCBA A (DOWN)CBA A (DOWN)链路链路n UPn UPCBA A (UP)CBA A (UP) CA A (DOWN) CA A (DOWN)链路链路CA DOWNCA DOWN过时的信息被当作新信息！过时的信息被当作新信息！3. 当正在执行最短路由算法时，新的拓扑信息到达，当正在执行最短路由算法时，新的拓扑信息到达，这时，要么路由算法能够处理拓扑变化带来的问这时，要么路由算法能够处理拓扑变化带来的问题，要么中止刚才进行的计算，开始重新计算路题，要么中止刚才进行的计算，开始重新计算路由。由。4. 当一条链

58、路修复之后，它可能会引起分离的网络当一条链路修复之后，它可能会引起分离的网络重新连接，这时每一个分离的部分都可能会有另重新连接，这时每一个分离的部分都可能会有另外一部分的过时拓扑信息。路由算法必须让这两外一部分的过时拓扑信息。路由算法必须让这两部分最终认识到正确的网络拓扑。部分最终认识到正确的网络拓扑。 前面的讨论告诉我们，网络中的每一个节点要在所有的时间前面的讨论告诉我们，网络中的每一个节点要在所有的时间内都得到正确的网络拓扑是不可能的。所以我们期望的最佳内都得到正确的网络拓扑是不可能的。所以我们期望的最佳值是：算法能够在有限的时间内处理有限次的拓扑变化。值是：算法能够在有限的时间内处理有限

59、次的拓扑变化。 为了便于讨论，我们作如下假设，这些假设可以保证拓扑变为了便于讨论，我们作如下假设，这些假设可以保证拓扑变化能够被正确的检测到。化能够被正确的检测到。 网络的链路能维持传输的顺序性和正确性。此外，各节网络的链路能维持传输的顺序性和正确性。此外，各节点能够维持其存储器中数据的完整性。点能够维持其存储器中数据的完整性。 链路的故障是由链路的两个端点检测的，但不一定要同链路的故障是由链路的两个端点检测的，但不一定要同时检测到。这就意味着链路的一个端点认为链路断开后，时检测到。这就意味着链路的一个端点认为链路断开后，另一个端点最终也会认为链路断开。必须注意的是，另一另一个端点最终也会认为

60、链路断开。必须注意的是，另一个端点认为链路断开必须在第一个点认为链路恢复之前。个端点认为链路断开必须在第一个点认为链路恢复之前。 有完善的数据链路层协议，能够识别链路何时再次工作。有完善的数据链路层协议，能够识别链路何时再次工作。如果链路的一个端点宣布链路恢复（如果链路的一个端点宣布链路恢复（UP），则在有限的时），则在有限的时间内，另一个端点要么宣布链路恢复，要么首先再次宣布间内，另一个端点要么宣布链路恢复，要么首先再次宣布链路故障（链路故障（DOWN）。）。 节点可以有故障。这种情况下，与它关联的每一条链路节点可以有故障。这种情况下，与它关联的每一条链路的另一个端点在有限的时间内必须宣布链