《路由算法补充知识》ppt课件

《《路由算法补充知识》ppt课件》由会员分享，可在线阅读，更多相关《《路由算法补充知识》ppt课件（47页珍藏版）》请在金锄头文库上搜索。

1、路由技术,确定路由算法 设计目标 选择类型 定义最佳路径的度量准则 实现路由协议 路由传输协议（Routed Protocol） 网间经路由被传输的协议：IP，OSI，Netware 路由选择协议（Routing Protocol） 实现路由选择算法的协议：RIP，OSPF，BGP,1. 路由算法需要考虑的基本因素,1）路由算法的设计目标 2）选择最佳路由的度量参数,1）路由算法的设计目标,优化：根据一定的优化准则选择最佳路径的能力 简单：利用最少的物理资源、提供最有效的功能 稳定：经受得住各种恶劣环境的考验，故障率低 收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由 灵活：快

2、速、准确地适应各种网络环境和变化,2）选择最佳路由的度量参数,路径长度 由网络管理员定义每条网络链路的代价（cost），从源到宿的代价总和为路径长度。 以路径中的站点（hop）为单位，从源到宿的站点数之和为路径长度。 可靠性 链路数据传输的可靠性（误码率） 延迟 数据包从源到宿需要花费的传输时间 带宽 链路的最大传输能力以及网络流量 负载 网络资源（例如路由器的CPU）的使用率 通信代价 占用通信线路的费用,2. 路由选择算法,1）缺省路径 2）静态路由 3）动态路由距离向量法 4）动态路由链路状态法,1）缺省路径（Default Route）,什么是缺省路径？ 对那些在路由表中未包含其路由选

3、择信息的信宿（网络/主机）设定的缺省路径 在路由表中信宿地址取值0.0.0.0(Default) 缺省路径的作用 对所有自治系统以外的信宿都采用缺省路径 简化路由计算，提高寻径效率，缩短表长,缺省路径举例,网络A,网络D,Rd,b0,c0,f0,e0,Default Rd e0,Default Rd f0,Default Ra b0,Default Ra c0,Ra,Rc,Rb,Rf,Re,2）静态路由,静态路由的概念 静态路由工作原理 路由配置举例 故障举例（网络拓扑结构变化） 用人工修改配置排除故障,静态路由的概念,由网络管理员设置路由表 简单、有效，适于结构简单的网络 不适于拓扑结构和传

4、输流量经常改变的复杂网络,静态路由举例,网络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,链路发生故障,网络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,解决办法：人工修改,网络A,网络C

5、,网络B,Rb路由表 网络A Rc b2 网络C Rc b2,Rc路由表 网络B Rb c2 网络A Ra c3,a1,a3,a2,c3,c2,c1,b2,b3,b1,！,！,不适于网络变化！,Ra路由表 网络B Rc a3 网络C Rc a3,Ra,Rb,Rc,静态路由算法,洪泛（flooding）算法：向着除了进入链路以外的其他链路转发； 随机算法：随机选择下一跳； （概率）分流算法：按照链路（静态）带宽（速率）选择下一跳,3）距离向量算法,Distance-Vector D-V算法的基本概念 D-V算法的动态特性 D-V算法的收敛性问题及其解决办法 D-V算法小结,A 路由表,距离向量算

6、法的基本概念,周期性地相互传递信息 每个路由器向与它相邻的站点发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价） 维护各自的路由表 路由器根据邻居发送的距离向量的动态信息启动算法，更新路由表,D,C,A,B 路由表,C 路由表,B,D-V路由选择算法举例,距离向量法的计算举例,A,D,E,C,B,7,1,8,2,2,1,计算从E经相邻站点A、B和D到达信宿A、B、C和D的最小代价D (destination,neighbor) 得从E到达信宿的最佳路径（最小代价）路由表,最小代价D (des,nei),E的路由表,距离向量路由算法,D-V网络发现过程剖析,1 1,A,C,B,40

7、.0.0.0 up,到达信宿40.0.0.0的路由变化,如果网络中的最长路径为N，则算法经过N次迭代计算后收敛。即第N步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。,D-V发现链路断开,1 1,A,C,B,40.0.0.0 down,到达信宿40.0.0.0的路由变化,C与B之间的对话： 我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达信宿吗？ 我可以到达信宿，距离为1。（传播了一条过时的错误信息） 既然如此，我选择经过你到达信宿的路径，距离为2。,距离向量法的收敛性问题及解决办法,问题 逐站传递更新信息，算法的收敛速度慢 有可能出现各站路由信息不一致 后果

8、在站点间构成更新路由的路径环（Routing Loops） 计数至无穷大（Count to Infinity） 解决办法 定义路径代价的最大值（Maximum） 提高收敛速度,1 1,A,C,B,40.0.0.0 down,到达信宿40.0.0.0的路由变化,路径环（Routing Loop）问题,这条错误的路由信息在C与B之间不断复制和修改，并在网络中传播（殃及A），形成路径传播的环路。,1 1,A,C,B,40.0.0.0 down,到达信宿40.0.0.0的路由变化,严重后果：计数至无穷大,1 1,A,C,B,40.0.0.0 down,到达信宿40.0.0.0的路由变化（定义Hop最大

9、值为16）,解决办法：定义距离的最大值,收敛！,加速收敛的方法,水平分割（Split Horizon） 毒性逆转（Poison Reverse） 保持计时（Hold-Down Timers） 触发更新（Triggered Updates） 加速方法的综合应用举例,距离向量算法小结,路径选择采用最短路径准则，计算D信宿(距离，下站)； 每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法； 算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大； 当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；

10、各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生； 在具体的路由协议中，各种加速收敛方法往往综合使用。,4）链路状态（Link-State）算法,L-S算法的基本概念 L-S算法的动态特性 L-S算法的性能分析 L-S算法与 D-V算法的比较 OSPF协议,链路状态算法的基本概念,链路状态算法的基本概念 链路状态法的计算举例 Dijkatra算法计算结果,每个路由器周期性地收集和发送信息 主动测试其到所有邻居的链接状态（度量值） 向所有的路由器发送（广播）自己拥有的状态信息 得到一个全网的、动态的逻辑链路状态（L-S）图 每个路由器刷新自己的路由表 当L-S变化时，

11、用最短路径优先(SPF)算法重新计算本地路由,D,C,A,B,链路状态算法的基本概念,_ _ _ _ _,路由表,SPF 算法,拓扑数据库（L-S图）,SPF树,L-S包,A,E,D,C,B,2,1,2,1,1,3,Dijkatra最短路径算法 计算加权无向图（即L-S图）中两个结点之间的最短路径 对每结点赋以标注D(v),NP(v),链路状态法的计算举例,F,3,5,5,2,其中 自变量v：无向图中的结点 函数D(v)：到目前为止，从源点到结点v的最短路径（边长之和） 函数NP(v)：沿源点到结点v的最短路径中与V相邻的前一结点,Dijkatra算法计算结果,A,E,D,C,B,2,1,2,

12、1,1,3,源点A到所有结点的最短路径,F,3,5,5,2,D,F,E,A,B,C,1,1,2,1,2,L-S图,SPF树,L-S算法的动态特性,建立路由表的初始过程 发现新的网络 路由表的维护 发现拓扑变化 修改拓扑数据库 计算SPF树 修改路由表,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建立路由表的初始过程,A,C,B,40.0.0.0,L-S网络发现过程剖析,C发现直连网络30.0.0.0和40.0.0.0 构造包含发现信息的L-S报文(LSP)向全网广播 接收全网的其他路由器发来的L-S报文 根据收集

13、的信息建立拓扑数据库 启动SPF算法以C为源点计算SPF树 建立到达所有信宿的路由表（端口和代价）,c1,LSP,30.0.0.0,c0,（1）发现拓扑变化,A,E,D,C,B,F,Net X,Net X Down,Net X Down,LSP,LSP,发现网络X不可达 构造LSP 向全网广播,发现网络X不可达 构造LSP 向全网广播,（2）修改拓扑数据库,A,E,D,C,B,F,Net X,全网具有相同的L-S逻辑图。,A,E,D,C,B,F,Net X,（3）各自重新计算SPF树,2,2,3,3,1,1,5,2,5,1,A,E,D,C,B,F,Net X,根据各自计算的SPF树刷新路由表,

14、（4）修改各自的路由表,a0,a1,a2,Net Y,路由表,路由表,路由表,路由表,路由表,2,2,1,L-S算法的性能分析,优点 代价 路由刷新问题 线路传输速率不同 网络运行状态不同 解决办法,L-S算法的优点,所有路由器具有相同的网络拓扑知识（L-S图） 一次性、无修改地向全网广播LSP 路由器根据全局信息维护各自的路由表 保证链路状态信息的单向传播 保证算法的收敛性,L-S算法的代价,SPF算法计算和拓扑数据库需要更多的CPU和内存资源 网络启动时的扩散路由信息（flood）需要占用很多带宽资源,线路传输速率不同产生的影响,E应该选择哪棵SPF树？,Net X Down,Net X

15、up,Net X Down,来自D,来自A,慢,Net X,E收到的LSP,开始 Net X down 后来 Net X up,网络的一部分已经启动，而另一部分正待启动 网络的一部分刷新速度快，而另一部分刷新速度慢 造成网络的不同部分拥有不同的L-S图,网络运行状态不同产生的影响,L-S对问题的解决办法,减少对资源的需求 尽可能降低路由刷新频度 用Multicast取代Broadcast(flood) 将网络拓扑结构划分为不同层次和区域 在层次间和区域交接处交换路由信息 协调L-S刷新 对LSP加时间戳标识 对LSP加序列号标识 用分级路由管理网络的逻辑分组,D-V和L-S算法的比较,D-V 通过与邻居的信息交换获得网络拓扑知识 路由计算是增加路由器之间的站点数（hops） 定期刷新路由：收敛慢 向相邻站点传送路由表的副本,L-S 全网获得共同的全局性网络拓扑知识（L-S图） 计算到达其他站点的最短路径（SPF准则） 触发刷新：收敛快 向其他站点发送链路状态的动态变化,思考题,如果路由表包含全部到达信宿的路径信息显然有助于作出最优选择，是否可行？会带来什么问题？ 如果路由表只包含相邻站点的路由信