计算机网络体系结构之路由选择

通信子网为网络源节点和目的节点提供了多条传输路径的可能性。网络节点在收到一个分组后，要确定向下一节点传送的路径，这就是路由选择。在数据报方式中，网络节点要为每个分组路由做出选择；而在虚电路方式中，只需在连接建立时确定路由。确定路由选择的策略称路由算法。设计路由算法时要考虑诸多技术要素。首先，考虑是选择最短路由还是选择最佳路由；其次，要考虑通信子网是采用虚电路的还是采用数据报的操作方式；其三，是采用分布式路由算法，即每节点均为到达的分组选择下一步的路由，还是采用集中式路由算法，即由中央节点或始发节点来决定整个路由；其四，要考虑关于网络拓扑、流量和延迟等网络信息的来源；最后，确定是采用静态路由选择策略，还是动态路由选择策略。

1.静态路由选择策略

静态路由选择策略不用测量也不需利用网络信息，这种策略按某种固定规则进行路由选择，其中还可分为泛射路由选择、固定路由选择和随机路由选择三种算法。

（1）泛射路由选择法。这是一种最简单的路由算法。一个网络节点从某条线路收到一个分组后，再向除该条线路外的所有线路重复发送收到的分组。结果，最先到达目的节点的一个或若干个分组肯定经过了最短的路径，而且所有可能的路径都被尝试过。这种方法可用于诸如军事网络等强壮性要求很高的场合。即使有的网络节点遭到破坏，只要源、目间有一条信道存在，则泛射路由选择法仍能保证数据的可靠传送。另外，这种方法也可用于将一个分组从数据源传送到所有其它节点的广播式数据交换中。它还可被用来进行网络的最短路径及最短传输延迟的测试。

（2）固定路由选择。这是一种使用较多的简单算法。每个网络节点存储一张表格，表格中每一项记录着对应某个目的节点的下一节点或链路。当一个分组到达某节点时，该节点只要根据分组上的地址信息，便可从固定的路由表中查出对应的目的节点及所应选择的下一节点。一般，网络中都有一个网络控制中心，由它按照最佳路由算法求出每对源、目节点间的最佳路由，然后为每一节点构造一个固定路由表并分发给各节点。固定路由选择法的优点是简便易行，在负载稳定，拓扑结构变化不大的网络中运行效果很好。它的缺点是灵活性差，无法应付网络中发生的阻塞和故障。

（3）随机路由选择。在这种方法中，收到分组的节点，在所有与之相邻的节点中为分组随机选择一个出路节点。方法虽然简单，但实际路由不是最佳路由，这会增加不必要的负担，而且分组传输延迟也不可预测，故此法应用不广。

2.动态路由选择策略

节点的路由选择要依靠网络当前的状态信息来决定的策略，称动态路由选择策略。这种策略能较好地适应网络流量、拓扑结构的变化，有利于改善网络的性能。但由于算法复杂，会增加网络的负担。独立路由选择、集中路由选择和分布路由选择是三种动态路由选择策略的具体算法。

（1）独立路由选择。在这类路由算法中，节点仅根据自己搜集到的有关信息做出路由选择的决定，与其它节点不交换路由选择信息。这种算法虽然不能正确确定距离本节点较远的路由选择，但还是能较好地适应网络流量和拓扑结构的变化。一种简单的独立路由选择算法是Barm在1964年提出的热土豆（Hot Potato）算法：当一个分组到来时，节点必须尽快脱手，将其放入输出队列最短的方向上排队，而不管该方向通向何方。

（2）集中路由选择。集中路由选择也像固定路由选择一样，在每个节点上存储一张路由表。不同的是，固定路由选择算法中的节点路由表由人工制作，而在集中路由选择算法中的节点路由表由路由控制中心RCC（Routing Control Center）定时根据网络状态计算、生成并分送各相应节点。由于RCC利用了整个网络的信息，所以得到的路由选择是完美的，同时也减轻了各节点计算路由选择的负担。

（3）分布路由选择。在采用分布路由选择算法的网络中，所有节点定期地与其每个相邻

节点交换路由选择信息。每个节点均存储一张以网络中其它节点为索引的路由选择表，网络中每个节点占用表中一项。每一项又分为两个部分，一部分是所希望使用的到目的节点的输出线，另一部分是估计到目的节点所需要的延迟或距离。度量标准可以是毫秒或链路段数、等待的分组数、剩余的线路和容量等。