路由生产算法调研

青旅半醒 2022-06-12 01:52 154阅读 0赞

路由算法是路由选择协议的核心。路由算法指明了计算机网络中的结点机（或路由器）在接收到一个分组之后，应该选择哪条输出链路的策略。当采用虚电路通信时，路由是在建立呼叫链接是确立的，即一次性选择路由，后继的分组均沿着这条既定的路由传送。当采用数据报通信时，路由器要为每个分组做出路由选择。因此通信子网采用不同的通信方式，路由算法的使用额度是不一样的。  
一个实际的路由算法不可能做到尽善尽美，只能比较接近理想的路由算法。而一个理想的路由算法应该具有以下的特点：  
1、正确性：指路由算法指明的 路由最终一定能够到达目的网络和目的主机。  
2、简单性：简单的路由算法不仅可以缩短路由器进行路由选择时的计算时间，还能减少为路由选择计算而增加的网络通信开销  
3、适应性：指路由选择算法能够适应包括通信流量和软硬件故障在内的网络状态变化，自适应的改变路由，确保网络仍能正常运行  
4、稳定性：当网络通信量和拓扑结构发生变化时，稳定性将能使路由算法得到一个收敛可接受的解，不止于发生震荡，这是一个十分重要却容易被忽视的特性。  
5、公平性：算法对所有的用户都公平对待，以达到网络内部流量的平均分布  
6、最佳性：指实现路由算法所花费的开销最低。衡量开销的因素可以是跳数、带宽、时延、负载、费用等。当然不存在绝对的最佳路由算法。

常见的路由算法：  
距离向量算法：距离向量算法是基于Bellman-Ford算法，Bellman-Ford算法的基本要点是：设X是节点A到节点B的最短路径中的一个节点，把路径A—>B拆分成两段路径，即A—->X和X—->B，那么每一段路径A—->X和X—->B也分别是节点A到X和节点X到B的最短路径。

已知路由器R5的路由表如图a所示，现路由器R5收到相邻路由器R4发来如图b所示的路由更新信息。试问路由器R5如何更新它的路由表？  
![这里写图片描述][SouthEast]  
先把图b中的距离都加1，并把下一跳的路由器都改为R4得到更新后的路由表b如图c,下面将它与图a中各表行的项目相对照，可得到如下结论：第1行和第4行更新信息在图a中没有，因此应该添加到图a中，第二行的跟更新信息虽然在图a中也有，虽然下一跳也是R4，但是它的距离增大为5，所以也要更新，第三行的更新信息在图a中也有，但下一跳路由器应该为R4，并且距离缩短为2，因此也要更新，更新后的路由表如图d所示：  
![这里写图片描述][SouthEast 1]

2、链路-状态路由选择算法

链路-状态算法(link-status,简称L-S)，也叫最短路径优先(shortest path first SPF)算法，它的主要做法如下：

a、首先由路由器向相邻路由器发送查询报文，测试和它相邻路由器的链路状态。如果可以收到相邻路由器发回的响应，则说明该相邻路由器和这个路由器之间可以正常通信。  
b、在收到该路由器和其他相邻路由器的链路状态后，还向系统中所有参加最短路径优先算法的路由器发送链路状态报文。  
c、各路由器收到其他路由器发来的链路状态报文后，根据报文中的数据刷新本路由器所保存的网络拓扑结构图。如果链路发生变化，路由器将启用Dijkstra算法生成新的最短路径优先数，并刷新本地路由表。

3:Dijkstra算法( 又叫狄克斯特拉算法)  
1 : 路由器建立一张网络图,并且确定源节点和目的节点,我们假定为V1和V2,然后路由器建立一个矩阵. 称”邻接矩阵”.在这个矩阵中,各矩阵元素表示权值,如\[i,j\]是节点之间链路权值如果节点Vi和节点VJ之间没有链路直接相连,它们的权值设为”无穷大”  
2：路由器为网络中每一节点建立一组状态记录.次记录包括三个字段  
前序字段–表示当前节点之前的节点  
长度字段–表示从源节点到当前节点的权值之和  
标号字段–表示节点的状态.每个节点都处于一个状态模式:”永久”或”暂时”  
3 : 路由器初始化(所有节点的)状态记录集参数,将它们的长度设为”无穷大”,标号设为”暂时”  
4 : 路由器设置一个T节点.例如,如果设V1是源T节点,路由器将V1的标号更改为”永久”,当一个标号更改为”永久”后,它讲不再改变,一个T节点仅仅是一个代理而已  
5 : 路由器更新与源T节点直接相连的所有暂时性节点的状态记录集  
6：路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。  
7：如果这个节点不是V2（目的节点），路由器则返回到步骤5。  
8：如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

[SouthEast]: /images/20220612/a7fa11186daf47fa991cf95ea56ea53e.png
[SouthEast 1]: /images/20220612/1a1e67d7ee614aebb181b33420c29e26.png