[科普中国]-路由选择语句

静态路由选择算法

静态路由选择算法是指采用某种路由选择算法预先计算出每个路由器的路由表，在路由器加电启动时加载到路由器中。在路由器工作过程中，路由表内容保持不变。如果网络拓扑结构或其他网络参数发生变化，则需要重新预先计算出各个路由器的路由表，并重新加载到路由器中。这种路由选择算法也称固定路由选择算法。

在静态路由选择算法中，有最短路径(Shortest Path，SP)和基于流量的路由选择(Flow—based Routing，FR)等。

最短路径选择在最短路径选择中，根据网络拓扑结构将一个通信网络表示成一个加权无向图。

图中每个节点代表网络中的路由器，连线代表通信线路，连线上标注的数字代表线路的权值。权值可以用线路长度、信道带宽、平均通信量、通信费用、队列长度、线路延时以及占用可用资源数量等加权函数计算出来。SP算法就是根据线路的加权值寻找出最短路径。SP算法最初是由Dijkstra提出的，故也称Dijkstra算法。

SP算法是一个逐步搜索过程，其搜索过程如下。

(1)假如在第m步已经搜索到一个最短路径，该路径上有n个距离源节点最近的节点，它们构成了一个节点集合N；

(2)在第m+1步，继续搜索不属于N的距离源节点最近的节点，并搜索到的节点加入到N中；

(3)继续搜索，直至到达目的节点，N中的节点集合便是从源节点到目的节点的最短路径。

在搜索过程中，每个节点用从源节点沿已知的最短路径到本节点的距离来标注，例如，在B(2，A)标注中，B表示本节点名，2表示在最短路径上源节点到本节点的距离(权值累加)，A表示最短路径上的上游节点名。在初始时，由于最短路径是未知的，故所有节点都标注为无穷大()。随着算法的进展和不断搜索到最短路径，节点的标注值也随之改变，反映出一个较好的路径。

每个路由器节点按照上述的SP算法计算出节点间的最短路径，形成路由表，在路由器加电启动时加载到路由器中。在路由器工作过程中，将根据数据分组中的目的地址查找路由表，找出最短的路径来转发数据分组。

基于流量的路由选择SP算法只是根据网络拓扑结构计算最短路径，而没有考虑通信流量或负载。FR算法则考虑网络拓扑结构和通信流量两方面因素进行路由选择。

在一些网络中，节点之间的通信流量是相对稳定和可预测的。如果预先知道节点之间平均通信流量的条件下，采用适当的算法对通信流量进行数学分析，可以优化路由选择。FR算法的基本条件是：

(1)必须知道网络拓扑结构；

(2)必须知道节点之间平均通信流量；

(3)必须知道各条线路的容量；

FR算法的基本原理是：对于一个给定的线路，如果已知该线路的负荷量和平均流量，则可以用队列理论计算出该线路的平均分组延迟。由所有的线路平均延迟可直接计算出流量加权平均值，从而得到整个网络的平均分组延迟。于是，路由选择问题就可归结为如何找出产生网络最小延迟的路由选择算法。1

动态路由选择算法网络的拓扑结构和通信量是动态变化的，如路由器的加入或退出，网络发生拥挤或阻塞等。如果路由器能够及时获得这些网络动态变化情况，并以此作为路由选择的依据，则会有助于路由器优化路由选择。动态路由选择算法就是采用这一机理进行路由选择的．它也称自适应路由选择算法。

现代计算机网络系统通常采用动态路由选择算法。在动态路由选择算法中，最常用的有距离矢量路由选择和链路状态路由选择两种算法。

距离矢量路由选择距离矢量路由选择(Distance Vector Routing，DVR)算法的基本原理是每个路由器都维护一个路由表，表中记录有通向目的节点的最佳距离和线路，每个路由器都要与相邻的路由器交换路由信息来更新路由表，使路由表中的信息总是反映网络最新的动态变化情况。

DVR算法最初应用于ARPANET中，后被其他网络所采用，如DECnet、Novell的IPX协议、Apple的AppleTalk协议以及Cisco路由器等。著名的路由选择信息协议(Routing Information Protocol，RIP)也是基于该算法开发的。

在DVR算法中，每个路由器都维护一个路由表，表中的每个表项都对应网络中的一个路由器，每个表项包含两部分内容：一是通往目的节点的输出线路；二是到达目的节点的距离或所需时间估算值，估算值的度量标准可以是节点数、时间延迟估算值、该路由的队列长度等。路由器要选择一种度量标准来估算本节点与目的节点之间的距离，如果选择节点数，则一个距离长度为一个节点；如果选择队列长度，则路由器检查每个队列；如果选择时间延迟，则路由器可以通过向相邻路由器发送一个特殊的回应(Echo)分组请求对方回送带有时间标记的分组来获得时间延迟值。

在一个网络系统中．每个路由器都按约定(或路由协议)采用某种度量标准来估算它到达目的节点的距离，并传送给相邻路由器；同时，它也会从相邻路由器中得到类似的估算值，并以此更新路由表。这样，路由器就可以从路由表上这些估算值中找出最佳值，该估算值对应的输出线路便是最佳路由，并选择该路由转发数据分组。

链路状态路由选择DVR算法存在两个主要缺陷：一是在选择路由时没有考虑线路带宽，而线路带宽随着网络技术的发展在不断地提高；二是算法在获取路由信息时需要耗费很多的时间。因此，DVR算法后来被链路状态路由选择(Line State Routing，LSR)算法所取代。现在，各种各样的LSR算法广泛应用于现代网络系统中，著名的开放最短路径优先(Open Shortest Path First，OSPF)协议采用的就是LSR算法，而OSPF协议广泛应用于Internet中。

每个路由器上的LSR算法都要执行如下过程。

(1)发现相邻路由器，获取其网络地址。当一个路由器加入网络后，首先向每个相邻路由器发送一个特殊的Hello分组，目的是声明它的存在，并希望得到相邻路由器的响应。各个相邻路由器接收到Hello分组后，都回应一个包含本路由器地址的响应分组。每个路由器地址应是一个全局唯一的地址。

(2)测量到各个相邻路由器的时间延迟或线路开销。一个路由器可通过发送Echo分组来测量到各个相邻路由器的延迟，各个相邻路由器接收到Echo分组后，都回应一个包含时间标记的响应分组。从发送Echo分组开始到接收到响应分组所经历时间除以2，便是该线路的延迟时间估算值。它反映了线路带宽状况，线路带宽越大，延迟时间越小；反之，线路带宽越小，延迟时间越大。

(3)将测量值通告给其他的路由器。路由器在获得有关路由器和链路状态信息后，构造一个特殊的链路状态(LS)分组来发布链路状态信息，该分组包含发送者地址、序号、生存期以及各个相邻路由器地址和对应的延迟时间估算值等信息。该分组可以周期性地发送。也可以在网络发生重大事件时发送，并采用如下的传递机制。

①路由器采用扩散法周期地向所有的线路广播LS分组，每发送一个新的LS分组，分组的序号加1。

②相邻路由器接收到LS分组后，通过核对发送者地址和序号来判断LS分组是否是重复的或过时的。如果是新的LS分组，则在路由表中记录新的链路状态信息，并向除输人线路之外的所有线路扩散，传播给其他的路由器；如果是重复的LS分组．说明它已从其他的路径接收到了该分组，则丢弃该分组；如果LS分组的序号小于以前曾收到的来自同一发送者的LS分组序号，说明该分组是一个过时的LS分组，则丢弃该分组。为了避免序号冲突问题。序号采用较长位数，如32位，序号以232为模，循环周期为232。

③链路状态信息以软状态方式保存在路由器中，路由器定期地(如每隔ls)检查它所记录的LS分组的生存期，并减1。如果一个LS分组的生存期减至0，则删除来自该LS分组的链路状态信息。这样就避免了无效的或出错的链路状态信息长期占据路由器的存储空间。

这样，一个路由器所测量的链路状态信息通过上述的传递机制发布给网络中所有的路由器。每个路由器用接收到的LS分组来建立和更新其路由表。

(4)最短路径。各个路由器在建立路由表后，可采用Dijkstra算法计算到达目的节点的最短路径，并按该路径转发数据分组。1

特点在路由器启动之后，立刻与其相邻路由设备建立路由关系。该初始通信的目的是为了识别相邻设备，开始进行通信并学习网络结构。建立相邻关系的方法和对拓扑结构的初始学习随路由选择协议选择的不同而不同。

路由选择协议会定期交换HELLO消息或路由更新数据包，以维持相邻设备间的可达性。一个理想的路由选择算法应具有以下特点：

(1)路由算法必须具有正确性和完整性。一个数据包能根据路由算法所生成的路由表把该数据包指引到最终的目的网络和目的主机。

(2)简单性。路由选择算法在生成路由表时在计算上应该简单，且不应使网络的通信流量增加太多的额外开销。

(3)适应性。路由选择算法能根据目前网络的状态和网络的流量动态地改变路由以均衡网络各链路的负载。即当网络的某个节点、链路发生故障不能正常工作时，或者修理好了再投入运行时，算法也能及时地改变路由。

(4)稳定性。在网络通信量和网络拓扑相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使路由不停地变化。

(5)公平性。路由选择算法对所有用户都是平等的。

(6)最佳性。最佳性是指以最低的代价来实现路由算法。这里的代价是指由一个或几个综合因素决定的度量(Metric)，如链路长度、数据率、链路容量、传播时延等。所以这里的最佳性只能是相对于某一种特定要求下得出的较为合理的选择而已。2