路由算法的分类

路由算法是算法设计的一个重要方面，根据网络节点对网络拓扑和通信量变化的自适应能力的不同，路由选择算法可以分为静态路由选择算法与动态路由选择算法两大类，其中：

◆ 静态路由选择算法：也叫作非自适应路由（Non Adaptive Routing）选择算法，在静态路由选择算法中，网络节点不根据实测或估计的网络当前通信量和拓扑结构来进行路由选择，网络节点之间的路由是事先计算好的。其特点是简单和开销较小，但不能及时适应网络状态的变化。代表性的静态路由选择算法有最短路径（Shortest Path）路由选择算法与洪泛（Flooding）路由选择算法等。

◆ 动态路由选择算法：也称为自适应的路由（Adaptive Routing）选择算法，在动态路由选择算法中，网络节点根据实测或估计的网络当前通信量和拓扑结构来进行路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。代表性的动态路由选择算法有距离矢量（Distance Vector）路由选择算法和链路状态（Link-State）路由选择算法等。

根据网络节点的路由决策方式不同，路由选择算法可以分为集中式路由（Centralized Routing）选择算法与分布式路由（Distributed Routing）选择算法两大类，其中：

◆ 集中式路由选择算法：在集中式路由选择算法中，每个网络节点都拥有网络中所有其他路由器的全部信息以及整个网络的流量状态，因此网络节点能够依据网络的全局信息来进行路由决策。

◆ 分布式路由选择算法：在分布式路由选择算法中，每个网络节点只有与它直接相连的路由器的信息，而没有网络中的每个路由器的信息，因此，网络节点只能依据网络的局部信息来进行路由决策。

根据网络节点的组织结构与功能作用的不同，路由选择算法又可以分为平面路由（Flat Routing）选择算法与层次路由（Hierarchical Routing）选择算法两大类，其中：

◆ 平面路由选择算法：在平面路由选择算法中，所有网络节点具有完全相同的地位和功能。其优点是路由算法设计简单，健壮性好，但缺点是路由的建立、维护开销很大，数据传输跳数多，因此主要适合小规模的网络。

◆ 层次路由选择算法：在层次路由选择算法中，网络节点按照不同的分簇方法分为不同的簇（Cluster），网络的逻辑结构是层次的，普通节点只需要负责簇内的路由（称作一级路由），每个簇内只有少部分节点负责簇间的路由（称作二级路由）。

根据网络节点所选取的传输路径数量的不同，路由选择算法可以分为单路径路由（Unipath Routing）选择算法与多路径路由（Multi-path Routing）选择算法两大类，其中：

◆ 单路径路由选择算法：在单路径路由选择算法中，网络节点一般只利用一条路径来进行数据传输。其优点是算法设计简单，易于管理和配置，但缺点是无法并行或并发地发送数据，导致网络传输效率较低，延迟增加，网络的负载不平衡，容易造成网络拥塞，无法很好地支持QoS。

◆ 多路径路由选择算法：在多路径路由选择算法中，网络节点利用多条路径来进行数据传输，可以为不同的服务质量要求提供不同的路径，也可以为同一种类型的服务提供多条路径，经聚集可实现更高的服务质量。多路径路由可以将原本集中在一条路径上的负载分配到几条不同的路径上，平衡网络负载，这样就能够充分利用网络资源，从而改善了通信性能。

1.最短路径路由选择算法

最短路径路由选择算法是一种集中式的静态路由算法，其基本思想是：将整个网络看作一个图，图中的每一个节点代表一台路由器，每一条弧线代表一条通信线路，而弧线上的数字则代表该线路的权重，该权重可以是通信距离、信道带宽、平均通信量、通信开销、队列长度、传播时延等。算法的目的就是要为图中任意一对给定的节点（路由器），找到一条最短（权重之和最小）的路径作为这对节点之间的实际路由路径。最短路径路由选择算法有很多种，其中最著名的是Dijkstra在1959年提出来的Dijkstra算法。

Dijkstra算法要求每个节点用从源节点沿已知最佳路径到本节点的距离来标注。开始时由于一条路径也不知道，故所有的节点都标注无穷大。随着算法的进行和不断找到的路径，标注随之改变，使之反映出较好的路径。一个标注可以是暂时性的（可更改的），所有标注最初都是暂时的，但一旦发现标注代表了从源节点到该节点的最短可能路径时，就使之成为永久性的，不再进行修改。如图4.7所示，Dijkstra算法的具体路由过程如下：

步骤1：每个节点都有一个标记（X，Y，Z），其中，X表示从源节点到达该节点的最短距离，Y表示到达该节点的上一跳节点，Z表示该标记的状态（包括暂时状态T和永久状态P）。

步骤2：初始时，因所有路径均为未知，因此，源节点A的标记为（0，-，P），而其余所有节点的标记均为（∞，-，T）。并将A作为工作节点。

步骤3：依次检查工作节点的每个邻节点，并且用它们与A之间的距离来更新其标记。

步骤4：检查图中所有状态为T的节点，将其中具有最小标记的那个节点的状态更新为P。

步骤5：若该节点为D，则算法结束，否则，将该节点作为工作节点，然后转步骤3。

图4.7　Dijkstra算法原理

2.洪泛路由选择算法

图4.8　洪泛路由选择算法原理

洪泛路由选择算法是一种分布式的路由选择算法，其基本思想是：如图4.8所示，每个网络节点均采用广播的方式来转发收到的分组，若收到重复分组，则丢弃该分组。显然，洪泛路由选择算法会产生大量的重复分组，从而使得使路由器和链路的资源过于浪费，以致效率很低。但洪泛路由选择算法由于不要求维护网络的拓扑结构和相关的路由计算，因此，在节点运动剧烈、进出网络频繁变化的场景下，全网洪泛是一种有效的方式，具有极好的健壮性，可用于军事应用，也可以作为衡量标准来评价其他路由算法。

3.距离矢量路由选择算法

距离矢量路由选择算法是以R.E.Bellman，L.R.Ford和D.R.Fulkerson所做的工作为基础的，因此也称为Bellman-Ford或者Ford-Fulkerson算法。其基本思想是：每个路由器维护一张矢量表（X，Y），其中，X表示当前已知的到每个目标路由器的最佳距离，Y表示所使用的线路（即到达该节点的上一跳节点）。通过邻居之间相互交换信息，路由器可以不断地更新各自维护的矢量表。

距离矢量路由算法示例：如图4.9所示，假定J通过测量知道其与各邻居节点A、I、H、K之间的延迟分别为8、10、12和6 ms。则J可通过以下方法来更新其矢量表中到G的路径信息（J要到达G，必须通过其四个邻居节点A、I、H、K之一）：

通过A到G：到达G的延迟=J到A的延迟+A到G的延迟=8+18=26。

通过 I 到G：到达G的延迟=J到I的延迟+I到G的延迟=10+31=41。

通过H到G：到达G的延迟=J到H的延迟+H到G的延迟=12+6=18。

通过K到G：到达G的延迟=J到K的延迟+K到G的延迟=6+31=37。

图4.9　距离矢量路由算法原理

（a）网络拓扑；（b）J的路由表更新过程

因此，J将更新其矢量表中到G的路径信息为（18，H）。

距离矢量路由选择算法是一种动态路由选择算法，如上所述，虽然在理论上可以工作，但在实践中却存在一个严重的缺陷：如图4.10所示，该算法的收敛速度非常慢，尤其是对于坏消息的反应非常迟缓，而且还存在无穷计数（Counting to Infinity）问题。

图4.10无穷计数问题

（a）A新上线的情形；（b）A断线的情形

例如：一种常用于在单一自治系统AS（Autonomous System）内进行路由决策的内部网关协议（Interior Gateway Protocol，IGP）“路由信息协议RIP（Routing Information Protocol）”就是一种典型的距离向量路由选择协议。在该协议中，选择了跳数作为距离的度量值，设定的最大跳数是15跳，如果一个分组被转发的距离大于15跳，RIP协议就会丢弃该分组。

4.链路状态路由选择算法

链路状态路由选择算法是目前使用最广的一类域内路由协议，通过采用一种类似“拼图”的设计策略来实现路由选择，即每个路由器将其到所有邻居节点的链路状态向全网的其他路由器进行广播，于是，一个路由器在收到从网络中所有其他路由器发送过来的信息之后，即可对这些链路状态进行拼装，并最终生成一个全网的拓扑视图，进而可以通过最短路径算法来计算其到其他任意路由器的最短路径。

运行链路状态路由选择算法的路由器仅在链路状态发生变化时，才将变化后的状态信息发送给其他所有路由器，然后，每台路由器将使用收到的信息重新计算前往每个网络的最佳路径，并同时将这些信息存储到自己的路由选择表中。链路状态路由选择算法的工作原理可以用以下5个基本步骤进行描述：

步骤1：节点（路由器）在新上线之后，首先要发现自己的邻居节点，并获知其网络地址。

步骤2：测量到各邻居节点的延迟或者开销。

步骤3：构造一个分组，如图4.11所示，该分组中应包含其刚刚获知的各邻居节点的网络地址以及到各邻居节点的延迟或开销等消息。

步骤4：将构造的分组发送给网络中所有的其他节点。

步骤5：计算出到每个其他节点的最短路径。

图4.12给出了一个具有6个路由器的网络中各个路由器所构造的链路状态分组情形，其中，每个路由器所对应的链路状态分组除了邻居节点及其延迟或者开销字段之外，还应包括以下两个字段：

◆ 序号：链路状态分组一般采用扩散法进行发布，序号的作用是判断到达的分组是新的还是重复的。若为新分组，则转发到到达线路之外的所有其他线路；若为重复的分组，则将它丢弃。从而达到控制扩散过程的目的。

◆ 年龄：一个分组经过每个路由器后均将递减年龄，若一个分组的Age为0，则它将被路由器丢弃。因此，年龄可确保所有分组都将在定长时间内消失。

图4.11 链路状态分组结构

图4.12 链路状态分组构造示意

（a）网络拓扑；（b）各节点构造的链路状态分组

例如：另一种常用于在单一自治系统AS内进行路由决策的内部网关协议“开放式最短路径优先OSPF（Open Shortest Path First）路由选择协议”就是一种典型的链路状态路由选择协议，在OSPF协议中，所选择的路由度量标准为带宽与延迟。相比RIP，OSPF更适合用于大型网络。

5.层次路由选择算法

层次路由算法思想如图4.13所示。路由器被划分为区域，每个路由器知道如何将分组路由到自己所在区域内的目标路由器，以及如何将分组路由到其他区域，但对其他区域的内部结构毫不知情。

图4.13　层次路由算法思想

（a）网络拓扑；（b）1A的完全路由表；（c）1A的层次路由表

6.广播路由选择算法

广播路由算法的基本思想是给网络中的所有主机发送分组。目前，代表性的广播路由选择算法有生成树算法STP（Spanning Tree Protocol）与逆向路径转发RPF（Reverse Path Forwarding）算法两种。

◆ 生成树算法：生成树算法是由Sun公司的著名工程师拉迪亚·珀尔曼博士（Radia Perlman）发明的，其国际标准是IEEE 802.1b。生成树是子网的一个子集，它包含所有的路由器，但是不包含任何环。如果每个路由器都知道它的哪些线路属于生成树，那么，它就可以将一个进来的广播分组复制到除了该分组到来的那条线路之外的所有生成树线路上，这种方法可以最佳地使用带宽，并且所生成的分组也绝对是完成这项任务所需要的最少数量的分组。唯一的问题是，每个路由器必须预先构造一棵汇集树（如图4.14（b）所示，采用生成树算法，整个广播只需要4跳、转发14个分组即可完成全网广播），然后，路由器即可将分组沿着汇集树发送。

◆ 逆向路径转发算法：当一个广播分组到达一个路由器的时候，该路由器对分组进行检查，若分组是一个新的分组，则路由器将会把该分组转发到除了到来的那条线路之外的所有其他线路上，否则，路由器会将该分组丢弃（因为是重复分组）。显然，采用逆向路径转发算法时，路由器不需要事先构造一棵汇集树（如图4.14（c）所示，采用逆向路径转发算法，整个广播需要5跳、转发24个分组才可完成全网广播）。

图4.14　两种主要的广播路由算法

（a）网络拓扑；（b）生成树算法；（c）逆向路径转发算法

7.多播路由选择算法

多播路由算法的主要思想是给网络中的一组给定的主机发送分组。多播路由要求对组进行管理，首先要有一种办法创建和销组，并且允许进程加入或者离开组。路由算法关心的是当一个进程加入组的时候，它需要把这个事实告诉它的主机。对于路由器来说，它们的哪些主机属于哪些组是非常重要的。当主机与组之间的从属关系发生变化的时候，主机必须将这些变化告诉路由器，或者由路由器定期询问它们的主机。无论采用哪一种形式，路由器必须知道它们的哪些主机属于那些组，再告诉它们的邻居，所以主机与组的从属信息在整个子网中传播开来。为了实现多播路由，目前，代表性的多播路由算法为生成树算法，其算法执行过程如图4.15所示。

图4.15 多播路由生成树算法示意图

（a）一个子网；（b）最左边路由器X的生成树；
（c）组播组1修剪过的生成树；（d）组播组2修剪过的生成树

8.移动主机的路由选择算法

如图4.16所示，移动主机的路由选择算法的基本思想如下：

步骤1：当一个分组发送给移动主机的时候，分组将被路由到该主机归属的本地局域网之中（即主场所）。

步骤2：然后，本地局域网中的主代理（又称为本地代理，本地代理记录了所有主场所在该区域，但当前正在访问其他区域的移动主机进程）查找该移动主机的新（临时）场所，并找到管理该移动主机的外地代理地址（外地代理记录了所有当前正在访问该区域的移动主机进程，当移动主机漫游到其他区域时，需要向新区域的外地代理申请注册，外地代理将与移动主机的主代理进行联系，告之移动主机的当前位置信息）。

步骤3：主代理将收到的分组封装到另一个外送分组的净荷域中，通过隧道机制发送到外地代理。外地代理得到封装的分组后，将从净荷域中提取原来的分组，并将它当作数据链路帧发送给移动主机。

步骤4：主代理告诉发送方，以后给该移动主机发送的新分组可通过外地代理直接路由到移动主机，不需要再发送到移动主机的主场所。

图4.16 移动主机路由示意图

（a）网络拓扑；（b）移动主机的路由过程