路由算法补充知识.ppt

Dijkatra算法计算结果AEDCB212113源点A到所有结点的最短路径F3552DFEABC11212L-S图SPF树??第31页，共48页，星期日，2025年，2月5日L-S算法的动态特性建立路由表的初始过程发现新的网络路由表的维护发现拓扑变化修改拓扑数据库计算SPF树修改路由表第32页，共48页，星期日，2025年，2月5日ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1 b0 b1 c0 c1L-S建立路由表的初始过程第33页，共48页，星期日，2025年，2月5日ACB40.0.0.0L-S网络发现过程剖析C发现直连网络30.0.0.0和40.0.0.0构造包含发现信息的L-S报文(LSP)向全网广播接收全网的其他路由器发来的L-S报文根据收集的信息建立拓扑数据库启动SPF算法以C为源点计算SPF树建立到达所有信宿的路由表（端口和代价）c1LSP30.0.0.0c0第34页，共48页，星期日，2025年，2月5日（1）发现拓扑变化AEDCBF?NetXNetXDownNetXDownLSPLSP发现网络X不可达构造LSP向全网广播发现网络X不可达构造LSP向全网广播第35页，共48页，星期日，2025年，2月5日（2）修改拓扑数据库AEDCBF?NetX全网具有相同的L-S逻辑图。第36页，共48页，星期日，2025年，2月5日AEDCBF?NetX（3）各自重新计算SPF树2233115251第37页，共48页，星期日，2025年，2月5日*网络与分布式系统研究室(DisNetLabofNWU)*关于路由算法补充知识第1页，共48页，星期日，2025年，2月5日1. 路由算法需要考虑的基本因素1）路由算法的设计目标2）选择最佳路由的度量参数第2页，共48页，星期日，2025年，2月5日1）路由算法的设计目标优化：根据一定的优化准则选择最佳路径的能力简单：利用最少的物理资源、提供最有效的功能稳定：经受得住各种恶劣环境的考验，故障率低收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由灵活：快速、准确地适应各种网络环境和变化第3页，共48页，星期日，2025年，2月5日2）选择最佳路由的度量参数路径长度由网络管理员定义每条网络链路的代价（cost），从源到宿的代价总和为路径长度。以路径中的站点（hop）为单位，从源到宿的站点数之和为路径长度。可靠性 链路数据传输的可靠性（误码率）延迟 数据包从源到宿需要花费的传输时间带宽 链路的最大传输能力以及网络流量负载 网络资源（例如路由器的CPU）的使用率通信代价 占用通信线路的费用第4页，共48页，星期日，2025年，2月5日2. 路由选择算法1）缺省路径2）静态路由3）动态路由—距离向量法4）动态路由—链路状态法第5页，共48页，星期日，2025年，2月5日1）缺省路径（DefaultRoute）什么是缺省路径？对那些在路由表中未包含其路由选择信息的信宿（网络/主机）设定的缺省路径在路由表中信宿地址取值0.0.0.0(Default)缺省路径的作用对所有自治系统以外的信宿都采用缺省路径简化路由计算，提高寻径效率，缩短表长第6页，共48页，星期日，2025年，2月5日缺省路径举例网络A网络DRdb0c0f0e0DefaultRde0DefaultRdf0DefaultRa b0DefaultRa c0RaRcRbRfRe第7页，共48页，星期日，2025年，2月5日2）静态路由静态路由的概念静态路由工作原理路由配置举例故障举例（网络拓扑结构变化）用人工修改配置排除故障第8页，共48页，星期日，2025年，2月5日静态路由的概念由网络管理员设置路由表简单、有效，适于结构简单的网络不适于拓扑结构和传输流量经常改变的复杂网络第9页，共48页，星期日，2025年，2月5日静态路由举例网络A网络C网络BRa路由表网络B Rb a2网络C Rc a3Rb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1RaRbRc第10页，共48页，星期日，