路由选择：分组能够通过多条路径从源点到达终点，交换机必须决定选择一条最合适的路由。
路由选择算法：是交换机收到一个分组后，决定下一个转发的中继节点是哪一个、通过哪一条输出链路传送所使用的策略。
1.对路由选择算法的一般要求
（1）在最短时间内使分组到达目的地；
（2）算法简单，易于实现，以减少额外开销；
（3）使网中各节点的工作量均衡；
（4）算法应能适应通信量和网络拓扑的变化，即要有自适应性；
（5）算法应对所有用户都是平等的。
2.常见的几种路由选择算法
路由选择算法分为非自适应型和自适应型两大类。
非自适应型路由选择算法：
扩散式路由算法（属于非自适应路由算法）
静态路由表法（属于非自适应路由算法）
动态路由表法（属于自适应路由算法）
（1）扩散式路由算法（属于非自适应路由算法）
基本思路:
网内每一节点收下一个分组后就将它同时通过各条输出链路发往各相邻节点，只有在到达目的节点时，该分组才被移出网外传输给用户终端。为了防止一个分组在网内重复循回，规定一个分组只能出入同一节点一次，这样，不管哪一个节点或链路发生故障，总有可能通过网内某一路由到达目的节点（除非目的节点有故障）。
图1 扩散式路由算法示意图
优点: 简单、可靠性高。
缺点: 分组的无效传输量很大，网络的额外开销也大，网络中业务量的增加还会导致排队时延的加大。
（2）查表路由法
查表路由法是在每个节点中使用路由表，它指明从该节点到网络中的任何终点应当选择的路径。路由表的计算可以由网络控制中心（NCC）集中完成，然后装入到各个节点之中，也可由节点自己计算完成。
常用的确定路由的准则是
最短路径算法
最小时延算法等
查表路由法分:
静态路由表法（属于非自适应路由算法）
动态路由表法（属于自适应路由算法）
① 静态路由表法
静态路由表法是确定路由的准则是最短路径算法
基本思路：
最短路径算法确定路由表时，主要依赖于网络的拓扑结构，由于网络拓扑结构的变化并不是很经常的，所以这种路由表的修改也不是很频繁的（网络故障或更新时需要修改），因而这种路由表法称为静态路由表法。
具体说明如下：以图1所示的网络拓扑结构为例，根据最短路径的原则，由网络控制中心计算得到的全网总的路由表如表1所示。(图1未给出各段路径的长度，最短路径只能考虑转接段数最少）
图1 静态路由算法示意图
表1 最短路径路由表
(教材中只画出一条最短路径）
表1所示的路由表存储在网络控制中心的存储器中，当网络结构发生变化或网络故障时，网络控制中心自动地重新生成路由表，以反映新的网络结构。
网络控制中心还要负责为每个节点（交换机）装入各节点的路由表，该路由表来自表6-1所示路由表中相关的一行，各节点的路由表如图2所示。（图中只画出一条最短路径示意）
图2 各节点路由表
② 动态路由表法
动态路由表法确定路由的准则是最小时延算法
基本思路：
一般交换机中的路由表由交换机计算产生。最小时延算法的依据是网络结构（相邻关系）和两项网络参数：中继线速率（容量）和分组队列长度。其中网络结构和中继线速率通常是较少变化的，而分组的队列长度却是一个经常变化的因素，这将导致时延的变化，所以交换机的路由表要随时作调整。这种随着网络的数据流或其他因素的变化而自动修改路由表的方法称为动态路由表法,也称自适应路由选择算法。
|
