路由算法.doc

教学导入:TCP/IP网络中路由器的基本工作原理,介绍了IP路由器的几大功能,给出了静态路由协议和动态路由协议,以及内部网关协议和外部网关协议的概念,同时简要介绍了目前最常见的RIP、OSPF、BGP和BGP-4这几种路由协议。
教学内容:
1距离向量算法
2 链路状态算法
3平衡混合路由算法

一距离向量法(Distance Vector Routing)
在距离向量法中,相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时,路由器之间也将及时地相互通知有关变更信息。
在图1中,每一个路由器从与之直接相邻的路由器处获得对方的路由表。例如,路由器B从路由器A和C获得路由信息后,对自己的路由表进行加工,加工后的路由表再传送给路由器A和C。路由器通过这种方法不断地积累路由信息,直到最终收敛为止。
图1 路由表传递示意
1. 路由表的建立与更新
在图2中,有三个路由器:A、B和C。;;。
图2 路由表内容列表
如图2中各路由器路由表的前两行所示,通过路由器的网络接口到与之直接相连的网段的网络连接,其向量距离设置为0。这即是最初的路由表。
当路由器B和A以及B和C之间相互交换路由信息后,它们会更新各自的路由表。例如,路由器B通过网络端口S1收到路由器C的路由信息(,S0,0)和(,E0,0)后,在自己的路由表中增加一条(,S1,1)路由信息。该信息表示: ,其向量距离为1,该向量距离是在路由器C的基础上加1获得的。同样的道理,路由器B还会产生一条(,S0,1)路由,这条路由是通过网络端口S0从路由器A获得的。如此反复,直到最终收敛,形成图2所示的路由表。
1》概括地说,距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其他路由器。
2》路由表中的每一条记录(路由信息都包括):
目标逻辑地址
相应的网络接口
该条路由的向量距离。

3》距离矢量算法路由更新的方法:
当一个路由器从它的邻居处收到更新信息时,它会将更新信息与本身的路由表相比较。如果该路由器比较出一条新路由或是找到一条比当前路由更好的路由时,它会对路由表进行更新:将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。
4》代表算法:IP RIP IPX RIP和IGRP
2. 收敛
所谓收敛,是指直接或间接交换路由信息的一组路由器在网络的拓扑结构方面或者说在网络的路由信息方面达成一致。路由协议必须通过某种算法使各路由器尽快达到收敛状态。
二链路状态算法(Link-State Routing)
链路状态算法,有时也称为最短路径优先算法(SPF,Shortest Path First)。与向量距离算法不同的是,这种算法需要每一个路由器都保存一份最新的关于整个网络的网络拓扑结构数据库,因此路由器不仅清楚地知道从本路由器出发能否到达某一指定网络,而且在能够到达的情况下,还可以选择出最短的路径以及采用该路径将经过的路由器。使用链路状态算法的路由协议有NLSP、OSPF和IS-IS。
链路状态算法使用LSP(链路状态数据包,Link-State Packets)、网络拓扑数据库、SPF路径选择算法、SPF树,最终计算出从该路由器到其他目标网络的最短路径,这些路径就构成了路由表。该算法要求每个路由器具备唯一的名字或标识。
1. 链路状态网络发现机制
该机制用于创建整个网络的一幅全景图,所有的路由器都保存该图的一个副本,从而保持一致。其具体工作过程如下。
(1) 每个路由器都必须知道它的邻居是谁,这一点需要相邻的路由器之间互相通知。
(2) 每个路由器都将LSP(链路状态数据包)发送给网络上其他的路由器,LSP的内容包括该路由器通过哪些网络与哪些路由器直接连接,以及相应连接的传输代价。以图2中所示的网络为例,路由器B向外发送的LSP包括((B,A,),(B,C,)),,(这里假设相邻路由器之间的传输代价为1)。
(3) 路由器根据收到的LSP逐步地构建起网络的拓扑数据库(即SPF树,树的根接点为该路由器本身)。
(4) 路由器根据网络的拓扑结构数据库判断目标网络是否可到达以及确定其最短