路由表的生成算法

已经知道,路由器使用路由算法来找到到达目的地的最佳路由。那么在考虑到,跳跃数、延时以及分组数据包的传输通信耗时时,最佳路由的算法有以下:

静态路由算法

Dijkstra算法(最短路径算法)

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。

Dijkstra算法执行下列步骤:
1)路由器建立一张网络图,并且确定源节点和目的节点,在这个例子里我们设为V1和V2。然后路由器建立一个矩阵,称为“邻接矩阵”。在这个矩阵中,各矩阵元素表示权值。例如,[i, j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连,它们的权值设为“无穷大”。
2)路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段:
前序字段——表示当前节点之前的节点。
长度字段——表示从源节点到当前节点的权值之和。
标号字段——表示节点的状态。每个节点都处于一个状态模式:“永久”或“暂时”。
3)路由器初始化(所有节点的)状态记录集参数,将它们的长度设为“无穷大”,标号设为“暂时”。
4)路由器设置一个T节点。例如,如果设V1是源T节点,路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后,它将不再改变。一个T节点仅仅是一个代理而已。
5)路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
6)路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
7)如果这个节点不是V2(目的节点),路由器则返回到步骤5。

8)如果节点是V2,路由器则向前回溯,将它的前序节点从状态记录集中提取出来,如此循环,直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

扩散法

事先不需要任何网络信息;路由器把收到的每一个分组,向除了该分组到来的线路外的所有输出线路发送。 将来会有多个分组的副本到达目的地端,最先到达的,可能是走了“最优”的路径
常见的扩散法是选择性扩散算法。

基于流量的路由算法

既考虑拓扑结构,又兼顾网络负荷;前提:每对结点间平均数据流是相对稳定和可预测的;根据网络带宽和平均流量,可得出平均包延迟,因此路由选择问题归结为找产生网络最小延迟的路由选择算法。提前离线(off-line)计算。

动态路由算法

距离向量路由算法

距离向量路由算法(Bellman-Ford Routing Algorithm),也叫做最大流量演算法(Ford-FulkersonAlgorithm),其被距离向量协议作为一个算法,如RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”),它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。

每一个相邻路由器发送过来的路由表都要经过以下步骤:
1)对地址为X的 路由器发过来的路由表,先修改此路由表中的所有项目:把”下一跳”字段中的地址改为X,并把所有”距离”字段都加1。
2)对修改后的路由表 中的每一个项目,进行以下步骤:
​ (1)将X的路由表(修改过的),与S的路由表的目的网络进行对比。若在X中出现,在S中没出现,则将X路由表中的这一条项目添加到S的路由表中。
​ (2)对于目的网络在S和X路由表中都有的项目进行下面步骤 :
​ (2.1)在S的路由表中,若下一跳地址是x ,则直接用X路由表中这条项目替换S路由表中的项目。
​ (2.2)在S的路由表中,若下一跳地址不是x ,若X路由表项目中的距离d小于S路由表中的距离,则进行更新。
3)若3分钟还没有收到相邻路由器的更新表,则把此相邻路由器记为不可到达路由器,即把距离设置为16。

链路状态最短路由优先算法SPF

1)发现邻居结点,并学习它们的网络地址;
2)测量到各邻居节点的延迟或者开销;
3)创建链路状态分组;
4)使用扩散法发布链路状态分组;
5)计算到每个其它路由器的最短路径。