[科普中国]-目录式路由选择

概述

网络层概念是建立在互联网基础上的。互联网是各种通信子网通过网络层互连设备(如路由器)和协议相互连接。形成一个很大的逻辑网络，实现端到端的数据通信，互联网模型如右图所示。

在互联网模型中，端节点主要完成数据的分组和组装．中间节点则基于存储一转发技术，负责选择适当的路由来转发这些数据分组；对于面向连接的传输方式，中间节点只是在建立连接时选择一次路由，以后每个数据分组都沿着该路由进行传输；对于无连接的传输方式，中间节点要为每个数据分组选择路由，每个数据分组的传输路径可能是不同的。

因此，路由选择是中间节点网络层的重要功能之一。中间节点在选择路由时主要基于如下原理：每个中间节点都采用适当的路由选择算法支持路由选择。并维持一·个路由表来记录有关路由信息。如端节点地址与线路(或端口)对应关系、路由开销等。在转发数据分组时，路由器将根据数据分组的目的地址查找路由表获取有关路由信息，并采用某种路由选择算法计算最佳路由，然后按该路由转发数据分组。2

在现在的大多数分组交换网络中，比较广泛地采用目录式路由选择技术，目录式路由选择是报文或包的一种路由选择方法，其通信网络中的每个节点均有一个到达各目的地的最佳、次佳路由的通信录以供选择。1

目录有时又称为路由表，其中包含交换机为每个分组进行路由选择的指示。根据目录的组织方式不同，可以有固定(静态)式目录、集中自适应目录和分散自适应目录三种3

目录式路由选择的质量关键在于目录式路由选择算法，目录式路由算法是—种采用较多的简单算法，也称为固定式算法。

目录分类固定(静态)式目录在采用固定式目录路由选择时，在网络内的每个节点交换机内都保存有一个从此节点到其它节点的路由表，表中可规定一条或多条出线。该表由网络设计者根据网络拓扑或其他因素人工编制，在网络投入运行之前就存入节点交换机的存储器内，网络在运行中此表始终不变。右图给出了一个例子，（a）为网络结构示意图，（b）为节点 交换机内的路由选择表，在表中列出了从节点 到网络内其它所有节点的三条出线。如从 到 的三条出线分别为 、 和 ，当节点 交换机收到去目的地 的分组时，先产生一个从0.00到0.99之间的随机数，当随机数在0.00—0.50之间时，选择去H的出线；当随机数在0.50—0.75之间时，选择去 的出线；当随机数在0.75以上时，选择去 的出线。从上看出，它把H出线认为是最佳选择， 出线为次最佳选择， 出线为最差选择。

固定目录路由选择方法的最大优点是算法简单、易于实现，在网络拓扑结构和信息分布均匀的情况下，能给出较好的性能。其缺点是缺乏灵活性，不能随网络的状态变化(如拥塞、故障等)而动态变更路径。

集中自适应目录同上述的固定式目录一样，在网络中的每个节点交换机都有一个路由选择表，但产生这路由选择表的方法则不同。在采用集中自适应式的网络内，由网络控制中心(NCC)决定各节点交换机内的路由表，并定时予以更新。具体方法是，由NCC收集各节点定期送来的状态信息，然后根据这些状态信息及网络拓扑结构，动态地计算出每个节点现时的路由表，再把新的路由表送回各节点交换机使用。所以，在每个交换机内都保存一张当前的状态信息表，内含在线的相邻节点、各输出线待转发分组的排队长度、近期处理过的信息量等。

采用这种路由选择方法的优点是适应性好，能定期地按拓扑结构和信息量的变化修改各节点的路由表。但也存在不少缺点：

(1)对NCC的可靠性要求很高，要求对NCC提供备用；

(2)要求NCC有很强的计算能力，以适应网络内信息量的快速变化；

(3)NCC每隔一定的时间都要把路由表送向各节点交换机，由于各节点离NCC的距离不同，远离NCC的节点交换机要比靠近NCC的节点交换机晚收到新的路由表，如果不采取适兰措施，则可能离近的节点已按新的路由表选择路由，而远离NCC节点，由于未收到新路由长而仍按老的路由表选择路由。这种失调会增大分组的传输时延；

(4)NCC向各节点发送路由表和各节点向NCC报告状态信息，使网络的负荷增加，而且离NCC越近，这种额外负荷越重。

分散自适应目录分散自适应是另一类自适应路由选择方法，它不依靠NCC来获得一条分组传输的最佳路径，而是由网络内的各个节点交换机依据当前的状态、信息量的分布等计算出各自的路由表。下面介绍其中的两种方法。 ·

（一）孤立法

它是分散式路由计算方法中最为简单的一种。各节点交换机在决定路由时不与其他节点交换机交换信息，故把它称为孤立法。

在最早提出孤立法时，其设计的中心思想是使到达节点的分组尽快地离开本节点，故接收分组的交换机在其所有的出线中，寻找一条排队最短的出线把陔分组发送出去。从表面上看，这种方法使分组在每个节点内的停留时间最短，但由于不管分组目的地的盲目传送，使分组总的传输时延较大。所以，在实际应用中往往与固定目录方式相结合使用，一般有三种结合的方法。 ·

(1)根据分组查找固定路由表，从固定路由表的最佳路由选择开始，检查对应出线的排队长度，只要长度未超过规定值，就把分组从该出线中输出；否则依次往后寻找次佳路由选择。重复上述工作；

(2)找出排队最短的出线，然后根据分组查找固定路由表，观察对应出线的利用率是否达到规定值，如达到规定值就选用该出线，否则继续寻找排队长度第二、第三最短的出线，重复上述工作；

(3)把固定路由表中的出线按其利用率进行1、2、3…的编号，然后把出线按其队长进行1、2、3…的编号，最后取一条在两个排列中编号之和为最小的出线。

对于上述三种改进型孤立法，不管使用哪一种，都应使输出线的选择满足下述条件，即在轻负载时，一般出线的队列较短，应选用利用率最高的出线(即最佳选择对应的输出线)；而在重负载下，应选用队列最短的输出线，以均匀网络的负载。

注意，对同一网络的同一节点来说，把分组传送到同一目的节点，采用集中式路由选择得到的路径和采用上述改进型孤立法得到的路径不一定相同，因为前者是由NCC根据整个网络的全部情况所得出的最佳路由，而后者则仅仅考虑了本节点的情况。但是，这并不意味着前者效果一定优于后者。因为集中式路由选择情况下，路由表是依据一段时间之前的网络状态得出的，网络中的各节点根据路由表得到的路径对于那时来说是最佳的，在经过一段时间(其中包括NCC收集节点状态表的时间、路由表计算时间和各节点发送时间等)后，网络状态已发生了变化，这时得出的路径也不一定是最佳的了。所以，在实践中有时把集中式路由选择与孤立法结合起来使用，获得较好的效果。

（二）分布式自适应法

分布式自适应法是一种适应较好并旦得到广泛应用的路由选择方法。在采用这种方法时，网络中的每个节点交换机周期性地与其相邻的节点交换机之间交换路由选择信息，然后根据这些信息来修改自己的路由表。虽然在每次修改中仅反映了相应节点的情况，但经过几次修改后，即可反映出第n次相邻节点的变化情况。所以，分布式自适应路由选择算法可以适应整个网络的变化。不过，它对近处节点的情况反应快，而对远处节点反应慢。

在不同网络中，采用这种算法时的设计准则不同，路由表的构成和交换机之间传递的状态参数也不同，常用的参数可以是时延、传输距离、中继段数目或者至目的节点的排队总长度等，下面以时延作为参数来进行说明。这时，网络中的各节点可以通过向相邻节点发送—-个所谓“回波”分组来测试至相邻节点的传输时延，被测节点交换饥在收到“回波”分组后，收到的时间标志后马上回送到发送节点。因此网络内的各节点可以知道至相邻节点的分组传递时间。然后，网络中的每一个节点交换机相隔周期T向相邻节点交换机发送-—张至其余目的节点的时延估计表，同时各节点交换机也收到来自各相邻节点的类似的表格。这样，各节点根据收到的时延占计表和由“回波”分组测得的至相邻节点的分组传输时延，可以计算出最短时延路由，得到一张新的路由表。3

目录式路由选择算法这是—种采用较多的简单算法，也称为固定式算法。在此算法中，各节点要事先建立一张路由选择表或路由选择数据库，建表或建库的原则是依据链路代价函数，各节点可依据此表进行路由选择。路由表一般可提供几种可能的选择。在该策略中，发信站在发送一个报文分组之前，先要产生一个随机数，待寻径节点根据其路由表和此随机数作出路由选择。其选择的依据基本上是以算法分析中的最优化原理为基础。这种方法简便，易于实现，当网络拓扑和信息量较稳定时，它能呈现较好的性能，且能较好地利用给定路由的信道带宽；其缺点是对节点或链路故障缺乏坚定性和自适应性。4