适应型路由选择-计算机网络原理

与非适应型路由选择不同，适应型路由选择能对网络状态（主要是拓扑、流量）的变化作出反应。根据网络状态信息的获得范围及路由表的修改方法，适应型路由选择方法又可分为多种形式，但任何一种形式都必须具有以下的功能：

①测量与路由选择有关的网络参数；

②将测得的信息送到路由选择决策的地点进行计算；

③生成路由表，并送至执行路由选择的地点；

④将路由表的信息转变为分组的路由选择决定。

下面简单地介绍几种适应型路由选择方法。

1、集中式

集中式（Centralized）路由选择方法很类似于固定式路由选择方法：它同样让每个CCP都使用一个路由表，并根据该表传送需要确定路由的分组，但集中式路由选择与固定式路由选择的表的修改方法不同。固定式路由选择方法的路由表需要事先编制，放入网中后一般不改变，要改变时也由人工进行，而在集中式路由选择方法的路由表由网络中的一中心结点来编制，并经常根据网络的状态进行修改，然后传送到各CCP中供使用。这个中心结点通常称为路由控制中心（Routing Conrtol Center，RCC）。各CCP都周期地向RCC报告所观测到的状态信息，例如它周围的CCP是否正常，目前的队列长度，线路上的通信量等等。RCC则根据得到的所有信息，从全网的角度计算出每个CCP到另一CCP的最优路由，并据此生成新的路由表，再传送给各CCP使用。

集中式路由选择方法的优点为：RCC掌握全局的信息，从而可作出最好的抉择，同时各个CCP不必再进行路由计算。但其也存在着一些十分严重的缺陷：首先，由于子网要适应流量的变化，路由的计算便十分频繁，而每次计算都要花费一定的时间，再加上传送路由表的时间，当CCP确实按此表工作时，网络的流量状态可能已经改变了。如果子网要适应拓扑的变化，也许时间上还来得及。其次是RCC的脆弱性，因RCC损坏，或因某条通信线路故障，导致RCC与网络的某部分断开，将使全网的路由选择陷入了困境。若采用两台计算机充当RCC，不但价格上可能不允许，而且还需要决定两个RCC的选择优先权。第三，因路由表在使用时间上的不一致，即近处的CCP先得到新路由表并按此执行，而远处的CCP尚未得到新路由表，仍在按旧路由表执行，从而导致计算结果与实际使用上的差异。第四，因各CCP都向RCC传送信息，而RCC又向各CCP提供路由表，但RCC的线路是有限的，从而将导致拥挤甚至阻塞等等。

2、孤立式

孤立式路由选择方法与集中式的主要差别在于：不是由RCC进行路由选择，而是由各个CCP独立地进行路由选择决策。在最简单的孤立式路由选择方法中，各CCP只根据自己收集到的信息来进行路由选择，而不用与其它CCP交换有关的信息，但它们还是力图适应网络和流量的变化。下面介绍几种最著名的孤立式路由选择方法。

（1）热土豆算法（Baran，1964）

所谓热土豆算法是指CCP收到一报文分组后，尽一切可能将其最快地送出，而不管送向何方的路由选择方法。采用此法时，CCP收到一个分组后，立即清点各个输出队列上的分组数，然后将新收到的分组送到最短的队列上去排队。也就是说，它仅以队列长度作为路由选择的唯一因素。图5.2.4中画出了CCPJ内的排队情况，对应四条输出线路共有四个队列，其中以去I的队列最短，热土豆算法便将新来的分组送到该队列去。

图5.24　CCPJ中的排队情况

这样做似乎不合适，但有时与其在结点内排队等待以致延迟较长，还不如到其它结点上去碰碰运气。这种方法是以分组的不停运动来完成传送的，故有时其效果不稳定，一个分组可能会在两个结点之间来回弹跳，或者反而离其终点越来越远。改进的方法之一是将热土豆法和固定式路由算法结合使用，当一个报文分组到达后，路由的选择将兼顾路由表和队列的长度。例如当队列较短时，使用固定式路由表，而队列较长时，则按热土豆法工作。这样，一般情况下，分组沿固定路由前进，而在载荷较重时，一部分流量被分配到其它不太忙碌的线路上去。这种方法有时也有来回弹跳的现象，或者围绕它所要到达的终点不停地转圈子。英国国家物理实验室通过实验发现：当“热土豆”一到达离终点只有一个跳跃的地方时，立即使其“冷却”下来，沿正确方向转送，会对算法有相当大的改进。

（2）后向学习法（Baran，1964）

所谓后向学习法是指CCP不主动向周围CCP询问路由的信息，而是根据到达分组带来的信息进行路由选择的方法。实现该算法的方法之一是在报文分组中放入源CCP的标志及每传一段便增1的计数器。如果某个CCP从线路K收到从CCPH来、计数器值为4的报文分组时，它便知道沿线路K到达CCPH的跳跃数不会多于4.如果它原记录的去CCPH的估计跳跃数大于4，它便将其修改为4.经过一段时间的运行后，所有的CCP便都会知道它到其它CCP的最短道路，并以此为决策依据，进行后续的路由选择。

但由于CCP只记录好的变化，而未记录线路的过载或故障，故其必须周期性地忘掉已陈旧的所“学到”的知识，而用较新的知识取代。遗忘的速度慢，适应过程也就慢；遗忘的速度太快，又可能使CCP对路由状况了解不够。所以，适当的遗忘速度是适应性的关键。

（3）δ—路由算法（Rudin，1976）(www.xing528.com)

δ—路由算法是孤立式与集中式路由算法的一种混合。在这种方法中，所有CCP都测量各条线路上的各种代价值（如延迟、队列长度、利用率等），并周期性地将这些值以报文分组形式送给RCC.RCC根据收到的信息，对所有的I，J计算出从CCPI到CCPJ的k条最优路由，然后令是从CCPI至CCPJ最优路由的总代价值，是从CCPI至CCPJ次最优路由的总代价值，…，是从CCPI至CCPJ的k条最优路由中最差路由的总代价值。若，则认为路由n与最优路由1等价（相差无几）；这个n可能有好几个，也就是说，存在有一组与路由1等价的路由。计算完毕后，RCC将这一组等价路由表送给各CCP，CCP就利用该表进行路由选择。

与固定路由算法中用的表十分相似，这张表也只指明出站线路，而后续路由由其它CCP中的表完成。CCP进行路由选择时，既可在这一组路由中任意选择，也可按顺序选择。通过调节k和δ的值，可使路由选择的决策权在RCC和各CCP之间进行转移。当δ→0时，其它路由与最优路由的差别加大。此时，因为RCC提供给各CCP的路由只有一条，故实际上路由选择的决策由RCC作出。当δ→∞时，因所有的路由趋于等价，故实际上路由选择的决策由各CCP在众多的（k条）路由中进行选择。仿真模拟结果表明，δ—路由算法要比纯集中式路由选择和纯孤立路由选择的方法都要好。法国的Transpac网中使用的就是δ—路由算法。

孤立式的路由选择总是以它内部可得到的信息作为决策依据的。除上述信息外，它还可以用其它信息作为决策依据。

3、分布式

在这一类算法中，所有的CCP都要周期性地与其邻站交换有关路由方面的信息，并根据这些信息修改自身的路由表。典型的做法是，在CCP中维持一个相邻CCP到各个目的地的记录估计值，并知道它到相邻CCP对同一指标的度量。这个用于比较的估计值可以是跳跃数、延迟时间或其它指标。如果是跳跃数，则显然该值为1；若是延迟，它只需发一个“回声”包，由接收方加上时间戮后送回便可知道。CCP根据邻站的信息及到邻站的度量值，可构成一组数。从这组数中找出最佳值，便是可供选择的路由。

例如，以延迟为度量指标，可定义第i个邻站点到n个目的结点的记录延迟矢量为

Di=［di1di2…din］T，　i=1，2，…，m

其中，i为第i个相邻结点，m为相邻结点数目，n为全部结点数目，显然dii=0.

再定义本结点到m个相邻结点的延迟测量值为

然后利用这两组值进行计算，得出本结点到各目的结点的延迟矢量S和对应的线路矢量R为

这样，S中便是本结点通过与邻站交换信息得出的各目的结点的新的延迟矢量，R中便是对应的新的出站线路矢量，二者便构成了本结点的新路由表。各个CCP之间不断地交换信息，路由表不断地被更新，即使是相邻较远的结点之间也通过这种交换交换了信息，最终使路由选择能较好地适应网络拓扑和流量等状态的变化。

图5.2.2所示范例子网中结点J的路由表的更新过程，如表5.2.3所示。表中的值为延迟，单位ms.

表5.2.3

结点J到相邻结点的延迟测量值为