路由算法.ppt

ROUTING ALGORITHMS
功能:将分组从源端机器经选定路由送到目的端机器
路由选择算法
希望具有的特征:
正确性、简单性、健壮性、稳定性、公平性和最优性
公平性与最优性之间的矛盾-[see fig 5-4]
2017/11/16
1
ROUTING ALGORITHMS
路由选择算法
数据报和虚电路采用不同的选择方法
算法分类:
非自适应算法-〉静态路由算法
自适应算法-〉动态路由算法
2017/11/16
2
1 The optimality principle
最优化原则
如果路由器J在从路由器I到K的最佳路由上,那么J到K的最佳线路就会在同一路由上
汇集树-[see fig 5-5]
从所有源端到目的端的最佳路由集合,形成了以目的地为根的树
2017/11/16
3
2 最短路由选择(Shortest path)
测量路径长度的方法(依据):
站点数量、距离、信道带宽、平均通信量、通信开销、队列平均长度、测量到的时延。。。
(Dijkstra)算法实例:计算从A到D的最短路径-[see fig 5-6]
从源到终节点
算法程序-[see fig 5-7]
从终结点到源节点
2017/11/16
4
2017/11/16
5
2017/11/16
7
3 扩散法(Flooding)
原理:将收到的每个分组,从除了分组到来的线路外的所有线路上发出
问题:产生大量的分组
抑制措施:
在分组头中包含“站点计数器”, 当其减到零时即被丢弃
记录下分组扩散的路径
改进:选择性扩散法
仅将分组扩散到与正确方向接近的线路上
应用:实际应用较少
2017/11/16
8
4 Distance vector routing
原理:
让每个路由器维护一张向量表,表中给出每个目的地已知的最佳距离和线路
通过与相邻路由器交换信息来更新表的信息
应用:、因特网、、Novell IPX、Cisco Routers 等
算法描述: -[see fig 5-10]
J-A:8
J-I:10
J-H:12
J-K:6
2017/11/16
9
4 Distance vector routing
无穷计算问题
算法的缺陷:算法收敛较慢。(对好消息反应迅速,对坏消息反应迟钝) -[see fig 5-11]
2017/11/16
10