路由算法.ppt

2008级网络工程
攀枝花学院计算机科学学院
1. 路由算法的设计目标
最优化:指路由算法选择最佳路径的能力。
简洁性:算法设计简洁,利用最少的软件和开销,提供最有效的功能。
健壮性:路由算法处于非正常或不可预料的环境时(如硬件故障、负载过高或操作失误),都能正确运行。由于路由器分布在网络联接点上,所以在它们出现故障时会产生严重后果。最好的路由算法通常能经受时间的考验,并在任何网络环境下都是可靠的。
路由算法
2008级网络工程
攀枝花学院计算机科学学院
快速收敛性
收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时,路由器就发出更新信息。路由更新信息遍及整个网络,引发重新计算最佳路径,最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。
灵活性
路由算法可以快速、准确地适应各种网络环境。例如,某个网段发生故障,路由算法要能很快发现故障,并为使用该网段的所有路由选择另一条最佳路径。
2008级网络工程
攀枝花学院计算机科学学院
2. 静态路由算法
由网络管理员根据预知的网络拓扑和网络状态,按照一定的算法确定网络路由,然后将路由通过手工写入路由器的NVRAM中。
路由器启动时将该路由表加载到路由器的RAM中,不能根据实测或估计的网络当前流量和网络拓扑结构来做路由选择。
静态路由算法实现的路由效率高、速度快,但要求网络管理对网络的状态进行整体控制,当网络中出现故障时需要网络管理员干预并重新配置路由以解决网络故障,对网络的动态变化缺乏响应机制。
2008级网络工程
攀枝花学院计算机科学学院
静态路由算法适用于网络结构比较简单的环境。
如总线型、星型和扩展星型等非网状拓扑的网络,处于网络末端的路由通常情况下只有一条向上的单臂路由(默认路由),而没有其他的路由,此时使用简单的配置就完成了路由的设置。
静态路由算法不能根据网络状态的变化而得到通往目标网络的最优路由。
在IPv6协议中,采用静态路由算法的路由器利用“邻居发现”协议可以自动获得相应的默认路由。
2008级网络工程
攀枝花学院计算机科学学院
3. 动态路由算法
(1)矢量距离路由算法
矢量距离路由算法是最早实现的一个分布式动态路由算法。
在该算法中,每一个路由器维护一张矢量_距离表(通常称为V-D表)。
在(V,D)序偶中,V指出该路由器可以到达的目的(网络或主机),D代表往目的V的距离。距离D按照路径上的hop个数计算。每个路由器通过与相邻路由器交换信息来更新V-D表的信息,计算出到达每一个目的网络的路由。
2008级网络工程
攀枝花学院计算机科学学院
矢量距离算法的基本思想如下:
首先,当一个路由器启动时,对其V-D路由表进行初始化。然后各路由器周期性地向外广播其V-D路由表的内容,与之相连的路由器(假设为Gi)收到后,检查各相邻路由器的V-D报文,并作相应修改。
当网络中某一故障发生时,网络中的所有节点都必须采用相同方法重新计算路由表。
矢量-距离算法对路由器处理能力要求不高,常常用于规模较小、网络拓扑结构的变化不很频繁的网络环境。由于该算法使用较早,比较成熟。
矢量-距离路由算法主要运用于路由信息协议(RIP)和内部网关协议(IGRP)。
2008级网络工程
攀枝花学院计算机科学学院
例:矢量-距离路由算法应用实例,以图4-4为例,介绍典型的矢量-距离路由算法:Bellman-Ford算法的应用。(图中线路上的数字表示该条线路上的费用。)
算法定义:
dx(y) = 从x到y最低费用路径的费用,
则:
dx(y) = min {c(x,v) + dv(y) }
其中min对x的所有邻居。
计算过程如下:
dv(z) = 5, dx(z) = 3, dw(z) = 3
c(u,v)=2,c(u,x)=1,c(u,w)=5
而:du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) }
= min {2 + 5, 1 + 3, 5 + 3}
= 4
结果:du(z) = c(u,x) + dx(z)=c(u,x)+c(x,y)+c(y,z)
结果路由: U->X->Y->Z
2008级网络工程
攀枝花学院计算机科学学院
(2)链路状态路由算法
链路状态路由算法采用“最短路径优先(SPF)”算法来计算网络中每一个源节点与其他所有节点之间的最短路径。根据SPF的要求,路由器中路由表依赖于一张能表示整个网络拓扑结构的无向图G(V,E)。其中,节点V表示路由器,E表示连接路由器的链路。一般把G称L-S图。
L-S算法的计算包含下列3个步骤:
·   各路由器主动测试所有