路由选择

一、理想的路由算法
路由算法：网络节点在收到一个分组后，决定在那一条输出链路上传送
下去所使用的策略。
理想的路由算法的一些特点：
(1)正确性。必须是信息快速、正确的传输。
(2)简单性。计算简单可以减少时延。另外，路由选择的计算不应使网络的通信量增加太多的额外开销。
(3)坚固性。算法应能适应通信量和网络拓扑的变化，要有自适应性。有时称这种自适应性为“健壮性”(robustness)。
(4)稳定性。当通信量和网络拓扑发生变化时，路由算法应收敛于一个可以接受的解，而不应产生过多的振荡。
(5)公平性。算法应对所有用户（除对少数优先级高的用户）都是平等的。
(6)最佳性。是指以最低的费用来实现路由算法。实际上，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
二、最短通路路由选择
例：寻找从源节点A到网络中其他各节点的最短通路。
令D(ν)为源节点(节点A)到节点ν的距离；
令N表示网络节点的集合，初始时令N＝{A}；
令l(i，j)为节点i至节点j之间的距离。

算法：
(1)初始化
D(ν)= (A , ν) 若节点ν与节点A直接相连
∞ 若节点ν与节点A不直接相连
(2)寻找一个不在N中的节点ω，其D(ω)值为最小，把ω加入到N中，然后对所有不在N中的节点，用D(ν)和[D(ω)+λ(ω，ν)]中的较小的值去更新原有的D(ν)值，即：
D(ν)←min[D(ν)，D(ω)+λ(ω，ν)]
(3)重复步骤(2)，直到所有的网络节点都在N中为止。

三、路由选择的不同策略
1.非自适应路由选择——简单、开销小
(1)洪泛法(flooding)
策略：当某个网络节点从某条输入线路收到一个不是发给它的分组时，就向所有与此节点相连的其它链路转发出去。
优点：①算法简单，几乎不需要什么计算；
②可以在最短的时间内接收方收到信息；
③方便实现广播通信和多址通信，具有良好的健壮性，广泛应用于军事网中。
缺点：①造成分组无休止的传输；
②使接收方收到多个重复的分组；
③网络中分组数目迅速增长，结果导致网络出现拥塞现象。
改进：采用计数器或登记表法控制网络中分组数目的增长。
(2)有选择的洪泛法
策略：仅在满足某些事先确定的条件的链路上转发分组。
好处：分组不会向不希望去的方向转发。
(3)固定路由法
策略：在每个节点上保存一张由此节点到网络中其他节点的固定路由表（由网络设计人员或管理人员根据网络拓扑结构、流量分布和其他因素编制的，并且在此后的一段相当时间保持固定不变），表中规定一条或多条输出线。
适用：当网络拓扑固定不变并且通信量也相对稳定时。
(4)随机走动法(random walk)
策略：当分组到达某个节点时就随机地选择应当走哪条链路作为转发的路由，因此又称为随机徘徊。
适用：在非自适应的路由策略中，若可能发生节点或链路的故障，那么随机走动法巳被证明是非常有效的，它使得路由算法具有较好的健壮性。
(5)分散通信量法(traffic bifurcation)或查表选择路由(directory routing)
策略：事先在每个节点的内存中设置一个路由表，路由表中给出几个可供采用的输出链路，并且对每条链路赋予一个概率；当一个分组到达该节点时，此节点即产生一个从0.00到0.99的随机数，然后按此随机数的大小，查表找出相应的输出链路。

2．自适应路由选择
当网络拓扑发生变化时及网络某个节点或链路发生故障时，在网络的某个局部范围做出调整路由的决定。
(1)孤立的路由选择策略
策略：只根据本节点的状态来选择路由，而不和其它节点交换状态信息。
“热土豆”算法：当收到一个分组时，不管其目的地址如何，把刚收到的分组以最快速度发往各链路中等待队列长度最短的等待队列中排队等候发送。 缺点：不准确，有时队列最短的方向井非正确的转发路由。
改进：令队列长度为Q，在每个队列增加一个对于某一目的地址的偏移数B，取Q+B值为最小的队列作为转发方向。
例如：对应于F，E，D和C的B值若分别为0，6，5和8．则算出相应的Q十B值分别为5，7，9和10，因此应把收到的分组送到发往F的队列中。

(2)分布式路由选择策略——是目前应用最广泛的路由算法
特点：适应性较好，每个节点周期性地从相邻的节点获得网络状态信息，同时也将本节点做出的决定周期性地通知周围的各节点，以使这些节点不断地根据网络新的状态更新其路由选择决定。
例：ARPANET使用算法是在每一个节点保持两个向量，即：

Di——节点i的时延向量； d_ij——节点i至节点j的最小时延当前估值(d_ij=0)； n—— 网络中的节点数； S_i——节点i的后继节点向量； S_IJ——后继节点(节点i到节点j当前最小时延路由中的第二个节点。对于任一节点k每隔128ms与其所有相邻节点交换时延向量，按以下方法对本节点的时延向量和后继节点向量进行修改： d_ki＝ [d_ki+d_ij-] S_ki==i，用这个i使[d_ki+d_ij-]为最小。
A——节点k的所有相邻节点的集合； d_ki——节点k到节点i的时延的当前估值。

(3)集中式路由选择策略
策略：利用网控中心NCC，专门收集各节点定期发来的状态信息，然后由它根据这些状态信息及网络拓扑结构，动态的计算出每个节点现时的路由选择表，再将新的路由选择表同时送回各个节点使用。
优点：算法能定期按拓扑结构和信息量变化修改各节点的路由选择表； 容易得到精确的路由，消除了分组在网内“兜圈子” 及路由“振荡”的现象； 可起到对进入网络通信量的某种流量控制作用。
缺点：在报告状态-计算-送回路由选择表的过程中花费了不少时间，因此在系统变化较快的网络中很难获得理想的控制效果；NCC的工作量大，因此需要采用速度快、可靠性高的机器；由于采用集中控制，因而NCC工作的可靠性尤为重要，所以应采用若干个级别的NCC协同控制，一旦高一级的NCC出现故障，低一级的NCC马上接替工作，但这种方法花费较大且仍不能满足全部要求；网中负载不平衡，靠近NCC的链路负担重，而远离NCC的链路负载较轻。
(4)混合式路由选择策略