网络设施
2007-11-12 14:33    文章来源：网界网

浅析路由协议的实现算法

作者：CNW.com.cn

三、路由协议的实现算法
　
本文主要介绍两种基本的路由算法，即距离向量法（Distance Vector Routing）和链路状态算法（Link-State Routing）。路由协议和路由算法只针对动态路由。
　
（一）、距离向量法（Distance Vector Routing）
　
在距离向量法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。
　
在图3中，每一个路由器从与之直接相邻的路由器那儿获得对方的路由表。例如，路由器B从路由器A和C那里获得路由信息后，根据其所得到的信息对自己的路由表进行加工，然后将加工后的路由表再传送给路由器A和C。路由器通过这种方法不断地积累路由信息，直到最终收敛为止。值得一提的是，在这种算法中，路由器不可能获知整个网络确切的拓扑结构。路由器是如何根据收到的路由信息对自身路由表进行加工，又是如何达到收敛的呢？


 
1、路由表的建立与更新
　
在图4中，有三个路由器：A、B和C。路由器A的两个网络接口E0和S0分别连接在10.1.0.0和10.2.0.0网段上；路由器B的两个网络接口S0和S1分别连接在10.2.0.0和10.3.0.0网段上；路由器C的网络接口S0和E0分别连接在10.3.0.0和10.4.0.0网段上。

如图4中各路由器路由表的前两行所示，通过路由器的网络接口到与之直接相连的网段的网络连接，其向量距离设置为0。这即是最初的路由表。
　
当路由器B和A以及B和C之间相互交换路由信息后，它们会更新各自的路由表。例如，路由器B通过网络端口S1收到路由器C的路由信息（10.3.0.0,S0,0）和（10.4.0.0,E0,0）后，在自己的路由表中增加（10.4.0.0,S1,1）这样一条路由信息，表示通过路由器B的网络接口S1可以访问到10.4.0.0网段，其向量距离为1，该向量距离是在路由器C的基础上加1获得的。同样的道理，路由器B还会产生一条（10.1.0.0,S0,1）的路由，这条路由是通过网络端口S0从路由器A获得的。如此反复，直到最终收敛，形成图4所示的路由表。
　
概括地说来，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其他路由器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路由器从它的邻居那儿收到更新信息时，它将更新信息与本身的路由表相比较，如果它能从邻居那儿找到一条它以前不曾知道的新的路由或是找到一条比当前路由更好的路由时，路由器会对路由表进行更新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。上例中将相邻路由器之间的向量距离设置为1。
　
2、收敛
　
所谓收敛，是指直接或间接交换路由信息的一组路由器在网络的拓扑结构方面或者说在网络的路由信息方面达成一致。路由协议必须通过某种算法使各路由器尽快达到收敛状态。
　
要实现收敛，必须解决路由器之间的路由环路（Routing Loops）问题。下面的例子比较直观地讲述了路由环路问题的产生。假设在图4中，网络10.4.0.0发生故障，在网络发生故障前，路由器A、B、C的路由表已经收敛为图4的状态。情况按照下面的描述一步步发生：
　
（1）网络发生故障后，路由器C检测到故障，停止通过接口E0向外发送数据包，并通过接口S0通知路由器B。在路由器A没有收到故障通知前，它仍然相信可以通过路由器B访问到10.4.0.0（路由器A路由表的最后一行），这条路径的距离为2。
　
（2）由于路由器B的路由表中指示有一条通往10.4.0.0的路径，因此，如果路由器B在收到路由器C的故障通知前将路由表发送到C的话，C会认为通过B可以访问10.4.0.0,并在此基础上修改自己的路由表，将路由表中第二条记录修改为（10.4.0.0,S0,2）,其中S0表示通过接口S0可以访问10.4.0.0,其距离为2。
　
（3）这样一来，路由器A、B、C都认为通过其他的路由器存在着一条通往10.4.0.0的网络路径，结果导致目标地址为10.4.0.0的数据包在这三个路由器之间来回地传递，从而造成一条路由环路。
　
解决路由环路问题可以采用以下几种方法：
　
（1） 水平分割（split horizon）
　
这种方法规定，路由器必须有选择地将路由表中的路由信息发送给相邻的其他路由器，而不是发送整个路由表。具体一点，即对于某条路由信息来说，不将它发送给该条路由信息的来源方向。仍以图4为例。图5是图4中路由器B的路由表，通过图5中的注释可以看到，每一条路由信息都不通过该条路由信息中所指的网络端口向外发送。
　
这样就可以避免路由环路的产生。

1  2  3  4  5  
责任编辑：孙可

文章评论

发表评论
查看全部
评论加载中...请稍后

精彩专题