距离向量路由算法

题目

距离向量路由算法

答案

距离向量路由算法(Bellman-Ford Routing Algorithm),也叫做最大流量演算法(Ford-Fulkerson Algorithm),相应的图片
其被距离向量协议作为一个算法,如RIP,BGP,ISO IDRP,NOVELL IPX.使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”),它告诉在网络中每个节点的最远和最近距离.在距离表中的这个信息是根据临近接点信息的改变而时时更新的.表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的.这个表中的列代表直接和它相连的邻居,行代表在网络中的所有目的地.每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”).这个在那个算法中的度量公式是跳跃的次数,等待时间,流出数据包的数量,等等.　　在距离向量路由算法中,相邻路由器之间周期性地相互交换各自的路由表备份.当网络拓扑结构发生变化时,路由器之间也将及时地相互通知有关变更信息.
路由表的建立和更新
　　如上图,有三个路由器,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网段上； 　　如上图中各路由表的前两行所示,通过路由表的网络接口到与之直接相连的网 　　络的网络连接,其向量距离设置为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 　　获得的.如此反复,直到最终收敛,形成图中所示的路由表.　　概括地说,距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由 　　器.路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离.当一个路 　　由器从它的相邻处收到更新信息时,它会将更新信息与本身的路由表相比较.如果该路由器比较出一条 　　新路由或是找到一条比当前路由更好的路由时,它会对路由表进行更新：将从该路由器到邻居之间的 　　向量距离与更新信息中的向量距离相加作为新路由的向量距离.
参与运算信息
　　目的地址：在算法的IP实现中,这指的是主机或的IP 地址.下一跳地址：到信宿的路由中的第一个路由器.接口：用于到下一跳物理.metric值：一个数,指明本路由器到信宿的开销.定时器：路由项最后一次被修改的时间.路由标记：区分路由为内部路由协议的路由还是外部路由协议的路由的标记.
运算
　　路由器间交换的最重要的信息是修改报文,参加路由维护计划的路由器发送当前存在于实体的描述路由库的路由修改报文.仅通过相邻路由器间交换路由信息是可以维护整个系统的最佳路由的,这在接下来的讨论中会逐步得到证明.距离向量算法总是基于一个这样的事实：路由库中的路由已是目前通过报文交换而得到的最佳路由.同时,报文交换仅限于相邻的实体间,也就是说,实体共享同一个.当然,要定义路由是最佳的,就必须有衡量的办法,这就用到前面所说的“metric”.RIP简单的中,通常用可行路由所经的路由器数简单地计算metric值.在复杂的中,metric一般代表该路由传输报的延迟或其它发送开销.令D代表从实体i到实体j的最佳路由的metric值,d（i,j）代表从i直接到j的开销,因为开销是可加的,算法中最佳路由如此获取表示：D（i,i）=0,对所有的i D（i,j）=MIN[d（i,j）+D（k,j）,当i不等于k时 实体i从相邻路由器k收到k到j的开销的估计D,i将D（i,j）加上i到k的开销估计d（i,j）,i比较从所有相邻路由器得到的数值,取得最小数,就得到了它到j的最佳路由.