非适应型路由选择在计算机网络原理中的应用

1、洪泛式

洪泛式（Flooding）是一种最简单的路由选择算法。在进行路由选择决策时，它不需要任何网络状态的信息。由于它在每一个结点上都将分组向除到达时所经过的线路以外的所有输出线上转发，从而必然产生洪水泛滥般的重复分组。如果不采用某种方法来停止分组的连续不断的重复，分组的数目便会无限增长。

止住“洪水”的方法之一是在每个分组的报头上设一个段计数值，分组每通过一段，该计数值便减1，当计数值减到0时，这个分组便被丢弃不再转发。理想情况下，该计数值以源到目的地的段数为初始值，如果发送端不知道这段道路有多长，也可用子网的最大“直径”来代替。另一种方法是让每个结点记住已发送的分组的标识，当重复的分组到达时，便将其丢弃。

洪泛式路由选择算法有两个值得注意的性质：

①从源点到终点的所有可能的路由都经过试用，因此，不管发生了什么样的链路或结点故障，只要存在一条从源点到终点的路由，分组总可以送达终点；

②由于所有的路由都经过试用，故到达终点的分组的各副本中，至少有一个使用了最少段数（跳跃数）的路由，至少有一个采用的路由延迟最短。

由性质一知，洪泛式路由选择算法高度可靠，因而可用来发送那些不允许丢失的信息，这在军用网中具有明显的应用价值。当军用网的部分遭受破坏时，为保证信息送达，就需要大量泛滥出来的重复分组，并尽快地利用未损坏的网络部分，将其送达终点。第二种性质则可被用来作为其它路由算法的参考，例如，确定最短路由、最短延时，甚至可以利用它建立最短路由的虚电路。

由洪泛方法稍加变化而得出的选择洪泛式（Selective Flooding）较为实用。在这种算法中，各结点不再把入站的分组向所有输出线路上转发，而是只向与正确方向大致相同的传输线路上转发。这是因为，除非拓扑结构过份特殊，将向西的分组发往向东的线路上是没有多大意义的。

2、随机走动式

随机走动式（Random Walking）是另外一种简单的路由选择方法，它也不需要任何网络状态的信息。采用此法时，结点把所到达的分组由随机选择的一条出站线路（一般不包括分组到达时的链路）发送出去，该分组在网中以类似于分子“布朗运动”的方式到达终点。对于分组的传送，纯粹的随机走动法是不实用的，但在有些方面，它具有重要用途。例如均匀地在网中分配某种许可证分组以限制网络总流量等等。

一般需对随机走动方式进行某种改进，使它不做完全随机的选择，而是能够选定某些可能性，把分组引向基本正确的方向上去，同时留出一个重要的随机因素来对付链路或结点可能发生故障。例如，给每一个链路确定一个概率，并且根据这个概率来选择路由。概率可以根据数据速率确定，在此情况下，有

Pi=Pi/∑jRj

式中，Pi为选择链路i的概率，Rj为链路 j上的数据速率。

当然，概率也可以根据其它原则确定，如固定的链路代价等。

3、固定式

(www.xing528.com)

图5.2.2　范例子网

固定式（Static）又称目录式（Directory），是一种得到广泛应用的简单路由选择算法。在这种方法中，每个CCP中都维持一张对各个可能目的地所应走链路的表格，当分组到达时，CCP将根据目的地址从表中查找出该分组所应走的链路，并将其发送出去。表是在对网络运行或设计的参数进行综合考虑后建立的，并定期地修正后分发给各个CCP.

第一种固定式路由表比较简单：它的行对应于各个目的结点，它的列则对应各个源结点，表中所填的则是所应走的链路名（用下一CCP名代替）。有两个链路名的前者为第一选择，后者为第二选择。对应于图5.2.2所示范例子网的固定路由表如表5.2.1所示。这张表是一个全表，事实上，每一个CCP只需使用其中的一列即可。在正常情况下，从每一个结点出发的分组将都沿着一条路由传送，此时，数据报和虚电路的路由选择将没有任何差别。

另一种经改进的固定式路由选择方法称为加权固定路由选择。在它使用的路由表中引入了随机数。采用此法时，网中每一结点中的路由表都不相同，且对应各个目的结点，从优到劣排着从该结点到目的结点的若干个输出链路；每一个链路都被赋于一权数，在送出分组之前，CCP将产生一个均匀分布的随机数，并利用该随机数所落入的区间进行路由选择。范例子网的结点J的加权固定路由表如表5.2.2所示。例如J收到一个以A为目的地的报文，即产生一个在0.0～0.99范围内的随机数，如果此数低于0.63，选出境线A，此数在0.63和0.83之间，选出境线I，否则，选出境线H.

表5.2.1　范例子网的固定式路由表

表5.2.2中的权数是拼凑出来的。较好但也较复杂的方法是利用最低代价公式统一进行权衡考虑，也可以利用网络的统计参数经调整后生成。路由表生成后放入CCP中，如果有需要可以重新更换。

固定式路由表决定了分组从本结点向下一结点转发的路由，但从一个结点发到另一个结点的分组是否一定可沿路由表指示的道路到达终点呢？即会不会有的结点认为走这条路最优，而另外一些结点却不这么认为呢？

表5.2.2　结点J的加权固定路由表

假设已进行了某些选择，且路由表中每一项只表示一条唯一的输出链路，那么该表的意义就是：对于某个目的终点来说，一个分组要经过的路由是根据它当时所在的结点位置决定的，而不是根据它怎样到达该结点决定的。这个条件称为马尔柯夫约束条件，因为它类似于马尔柯夫过程。事实上，假设CCPJ在CCPI到CCPK的最优道路上，那么从CCPJ到CCPK的最优道路也将沿着这条道路，这个原则被称为最优性原则。根据以上条件和最优原则，可以得出一个结论：所有朝向同一目的地的最优道路将构成一个树（Tree），树的根结点为目的结点，这个树被称为收树（Sink Tree）。由于收树也是一个树，故它不含有环。因而沿此收树传输的分组所经跳跃（段）数便有界，且总能到达终点。当然，因路由表的编制错误导致的分组送不到将是另外一回事。对于有多个可选出站链路的路由表，也可以用多个收树解释它的可行性，此处不再详述。图5.2.2所示范例子网的以A为目的结点的收树如图5.2.3所示。其中生成标准按照段数，同样段数的则按字母顺序。

图5.2.3　范例子网以A为目的结点的收树

固定式路由选择的最大优点在于简单、实用、易于理解。如果网络的拓扑及流量的变化不大，它可以具有很好的性能。但是由于它不能动态地对网络状态作出反应，故不能很好地适应突发的拓扑及流量的变化，往往需要人工加以处理，所以也有它的局限性。