路由算法补充知识.pptVIP

《计算机网络》第五章（3） 清华大学信息网络工程研究中心 Dijkatra算法计算结果 A E D C B 2 1 2 1 1 3 源点A到所有结点的最短路径 F 3 5 5 2 D F E A B C 1 1 2 1 2 L-S图 SPF树 ? ? 第三十一页，共47页。 L-S算法的动态特性 建立路由表的初始过程 发现新的网络 路由表的维护 发现拓扑变化 修改拓扑数据库 计算SPF树 修改路由表 第三十二页，共47页。 A C B 10.0.0.0 40.0.0.0 30.0.0.0 20.0.0.0 a0 a1 b0 b1 c0 c1 L-S建立路由表的初始过程 第三十三页，共47页。 A C B 40.0.0.0 L-S网络发现过程剖析 C发现直连网络30.0.0.0和40.0.0.0 构造包含发现信息的L-S报文(LSP)向全网广播 接收全网的其他路由器发来的L-S报文 根据收集的信息建立拓扑数据库 启动SPF算法以C为源点计算SPF树 建立到达所有信宿的路由表（端口和代价） c1 LSP 30.0.0.0 c0 第三十四页，共47页。 （1）发现拓扑变化 A E D C B F ? Net X Net X Down Net X Down LSP LSP 发现网络X不可达 构造LSP 向全网广播 发现网络X不可达 构造LSP 向全网广播 第三十五页，共47页。 （2）修改拓扑数据库 A E D C B F ? Net X 全网具有相同的L-S逻辑图。 第三十六页，共47页。 * 网络与分布式系统研究室(DisNet Lab of NWU) * 路由算法补充知识 第一页，共47页。 1. 路由算法需要考虑的基本因素 1）路由算法的设计目标 2）选择最佳路由的度量参数 第二页，共47页。 1）路由算法的设计目标 优化：根据一定的优化准则选择最佳路径的能力 简单：利用最少的物理资源、提供最有效的功能 稳定：经受得住各种恶劣环境的考验，故障率低 收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由 灵活：快速、准确地适应各种网络环境和变化 第三页，共47页。 2）选择最佳路由的度量参数 路径长度 由网络管理员定义每条网络链路的代价（cost），从源到宿的代价总和为路径长度。 以路径中的站点（hop）为单位，从源到宿的站点数之和为路径长度。 可靠性 链路数据传输的可靠性（误码率） 延迟 数据包从源到宿需要花费的传输时间 带宽 链路的最大传输能力以及网络流量 负载 网络资源（例如路由器的CPU）的使用率 通信代价 占用通信线路的费用 第四页，共47页。 2. 路由选择算法 1）缺省路径 2）静态路由 3）动态路由—距离向量法 4）动态路由—链路状态法 第五页，共47页。 1）缺省路径（Default Route） 什么是缺省路径？ 对那些在路由表中未包含其路由选择信息的信宿（网络/主机）设定的缺省路径 在路由表中信宿地址取值0.0.0.0(Default) 缺省路径的作用 对所有自治系统以外的信宿都采用缺省路径 简化路由计算，提高寻径效率，缩短表长 第六页，共47页。 缺省路径举例 网络A 网络D Rd b0 c0 f0 e0 Default Rd e0 Default Rd f0 Default Ra b0 Default Ra c0 Ra Rc Rb Rf Re 第七页，共47页。 2）静态路由 静态路由的概念 静态路由工作原理 路由配置举例 故障举例（网络拓扑结构变化） 用人工修改配置排除故障 第八页，共47页。 静态路由的概念 由网络管理员设置路由表 简单、有效，适于结构简单的网络 不适于拓扑结构和传输流量经常改变的复杂网络 第九页，共47页。 静态路由举例 网络A 网络C 网络B Ra路由表 网络B Rb a2 网络C Rc a3 Rb路由表 网络A Ra b3 网络C Rc b2 Rc路由表 网络B Rb c2 网络A Ra c3 a1 a3 a2 c3 c2 c1 b2 b3 b1 Ra Rb Rc 第十页，共47页。 链路发生故障 网络A 网络C 网络B Rb路由表 网络A Ra b3 网络C Rc b2 Rc路由表 网络B Rb c2 网络A Ra c3 a1 a3 a2 c3 c2 c1 b2 b3 b1 ? ? Ra路由表 网络B Rb a2 网络C Rc a3 Ra Rb Rc 第十一页，共47页。 解决办法：人工修改 网络A 网络C 网络B Rb路由表 网络A Rc b2 网络C Rc b2 Rc路由表 网络B Rb c2 网络A Ra c3 a1 a3 a2 c3 c2 c1 b2 b3 b1 ！ ！ 不适于网络变化