最短路径路由算法(ppt课件).ppt

第7章网络层
学习本章方法
本章是本书最重要的一章,.
1) 算法着重理解,也可自己发明新的算法或改进已有的算法,并能根据现有的算法编写程序
2) IP地址,子网的划分,超网的构造,路由选择
网络层是向传输层提供以下服务:
路由选择
拥塞控制
网络互联
第7 章网络层
ISO 定义
网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法,它使传送实体独立于路由选择和交换的方式。
网络层与数据链路层的区别:
网络层是将源端发出的分组经各种途径送到目的端。
而数据链路层仅将数据帧从传输介质的一端送到另一端。因此,网络层是处理端到端数据传输的最低层。
网络层要解决的关键问题
了解通信子网的拓扑结构,选择路由。
路由算法
•路由算法
–就是产生路由表的算法;
–是网络层软件的一部分。
–子网采用数据报方式,每个包都要做路由选择;
–子网采用虚电路方式,只需在建立连接时做一次
路由选择。
•理想的路由算法
–正确性(correctness):算法必须正确;
–简单性(simplicity): 算法开销小,效率高;
–健壮性(robustness): 算法能适应网络负荷和拓朴的变化;
–稳定性(stability): 算法必须收敛,不能振荡发散;
振荡:算法得出的路由是在一些路由之间回荡。
–公平性(fairness):算法对所有用户必须是平等的;
–最优性(optimality):算法应提供最佳路径选择;
最佳:链路长度、传输时延、数据速率、链路容量、链路
差错率、链路丢失率等。
路由算法分类
–非自适应算法(静态路由算法);
简单、开销小,但不能适应网络状态变化;
采用离线方式求出路由表。
–自适应算法(动态路由算法);
复杂、开销大,但能适应网络状态变化;
(optimality principle)
•从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树,称为汇集树(sink tree) ;
•路由算法的目的是找出并使用汇集树。
最短路径路由算法
属于静态路由算法
基本思想
构建子网的拓扑图,图中的每个结点代表一个路由器,每条弧代表一条通信线路。为了选择两个路由器间的路由,算法在图中找出最短路径。
测量路径长度的方法
结点数量
地理距离
传输延迟
距离、信道带宽等参数的加权函数
Dijkstra算法
采用标注的方式求出某一结点的汇集树和路由表。
①每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临时性标注和永久性标注;
②初始时,所有结点都为临时性标注,标注为无穷大;
③将源结点标注为0,且为永久性标注,并令其为工作结点;
④检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注,则用新计算得到的和重新标注该结点;
⑤在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并成为下一轮检查的工作结点;
重复第④、⑤步,直到所有结点成为工作结点;
请指出AD最短路径
Dijkstra算法程序