最新-路由算法补充知识-课件

路由技术确定路由算法设计目标选择类型定义最佳路径的度量准则实现路由协议路由传输协议（RoutedProtocol）网间经路由被传输的协议：IP，OSI，Netware路由选择协议（RoutingProtocol）实现路由选择算法的协议：RIP，OSPF，BGP路由技术确定路由算法1. 路由算法需要考虑的基本因素1）路由算法的设计目标2）选择最佳路由的度量参数1. 路由算法需要考虑的基本因素1）路由算法的设计目标1）路由算法的设计目标优化：根据一定的优化准则选择最佳路径的能力简单：利用最少的物理资源、提供最有效的功能稳定：经受得住各种恶劣环境的考验，故障率低收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由灵活：快速、准确地适应各种网络环境和变化1）路由算法的设计目标优化：根据一定的优化准则选择最佳路径的2）选择最佳路由的度量参数路径长度由网络管理员定义每条网络链路的代价（cost），从源到宿的代价总和为路径长度。以路径中的站点（hop）为单位，从源到宿的站点数之和为路径长度。可靠性 链路数据传输的可靠性（误码率）延迟 数据包从源到宿需要花费的传输时间带宽 链路的最大传输能力以及网络流量负载 网络资源（例如路由器的CPU）的使用率通信代价 占用通信线路的费用2）选择最佳路由的度量参数路径长度2. 路由选择算法1）缺省路径2）静态路由3）动态路由—距离向量法4）动态路由—链路状态法2. 路由选择算法1）缺省路径1）缺省路径（DefaultRoute）什么是缺省路径？对那些在路由表中未包含其路由选择信息的信宿（网络/主机）设定的缺省路径在路由表中信宿地址取值0.0.0.0(Default)缺省路径的作用对所有自治系统以外的信宿都采用缺省路径简化路由计算，提高寻径效率，缩短表长1）缺省路径（DefaultRoute）什么是缺省路径？缺省路径举例网络A网络DRdb0c0f0e0DefaultRde0DefaultRdf0DefaultRa b0DefaultRa c0RaRcRbRfRe缺省路径举例网络A网络DRdb0c0f0e0Default2）静态路由静态路由的概念静态路由工作原理路由配置举例故障举例（网络拓扑结构变化）用人工修改配置排除故障2）静态路由静态路由的概念静态路由的概念由网络管理员设置路由表简单、有效，适于结构简单的网络不适于拓扑结构和传输流量经常改变的复杂网络静态路由的概念由网络管理员设置路由表静态路由举例网络A网络C网络BRa路由表网络B Rb a2网络C Rc a3Rb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1RaRbRc静态路由举例网络A网络C网络BRa路由表Rb路由表Rc路由表链路发生故障网络A网络C网络BRb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1??Ra路由表网络B Rb a2网络C Rc a3RaRbRc链路发生故障网络A网络C网络BRb路由表Rc路由表a1a3a解决办法：人工修改网络A网络C网络BRb路由表网络A Rc b2网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1！！不适于网络变化！Ra路由表网络B Rc a3网络C Rc a3RaRbRc解决办法：人工修改网络A网络C网络BRb路由表Rc路由表a1静态路由算法洪泛（flooding）算法：向着除了进入链路以外的其他链路转发；随机算法：随机选择下一跳；（概率）分流算法：按照链路（静态）带宽（速率）选择下一跳静态路由算法洪泛（flooding）算法：向着除了进入链路以3）距离向量算法Distance-VectorD-V算法的基本概念D-V算法的动态特性D-V算法的收敛性问题及其解决办法D-V算法小结3）距离向量算法Distance-VectorA路由表距离向量算法的基本概念周期性地相互传递信息每个路由器向与它相邻的站点发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价）维护各自的路由表路由器根据邻居发送的距离—向量的动态信息启动算法，更新路由表DCAB路由表C路由表BA距离向量算法的基本概念周期性地相互传递信息DCABCBD-V路由选择算法举例D-V路由选择算法举例距离向量法的计算举例ADECB718221计算从E经相邻站点A、B和D到达信宿A、B、C和D的最小代价D(destination,neighbor)得从E到达信宿的最佳路径（最小代价）路由表最小代价D(des,nei)E的路由表距离向量法的计算举例ADECB718221计算从E经相邻站点距离向量路由算法原路由不经过N但距离大新路由不一定最优，但，原路由可能故障原路为无穷大，则取代为经N、长度为C的路由距离向量路由算法原路由不经过N但距离大新路由不一定最优，但，D-V网络发现过程剖析 1 1 ACB40.0.0.0up到达信宿40.0.0.0的路由变化如果网络中的最长路径为N，则算法经过N次迭代计算后收敛。即第N步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。D-V网络发现过程剖析 1 D-V发现链路断开 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化C与B之间的对话：我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达信宿吗？我可以到达信宿，距离为1。（传播了一条过时的错误信息）既然如此，我选择经过你到达信宿的路径，距离为2。D-V发现链路断开 1 距离向量法的收敛性问题及解决办法问题逐站传递更新信息，算法的收敛速度慢有可能出现各站路由信息不一致后果在站点间构成更新路由的路径环（RoutingLoops）计数至无穷大（CounttoInfinity）解决办法定义路径代价的最大值（Maximum）提高收敛速度距离向量法的收敛性问题及解决办法问题 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化路径环（RoutingLoop）问题这条错误的路由信息在C与B之间不断复制和修改，并在网络中传播（殃及A），形成路径传播的环路。 1 1 ACB 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化严重后果：计数至无穷大 1 1 ACB 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化（定义Hop最大值为16）解决办法：定义距离的最大值收敛！ 1 1 ACB加速收敛的方法水平分割（SplitHorizon）毒性逆转（PoisonReverse）保持计时（Hold-DownTimers）触发更新（TriggeredUpdates）加速方法的综合应用举例加速收敛的方法水平分割（SplitHorizon）距离向量算法小结路径选择采用最短路径准则，计算D信宿(距离，下站)；每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生；在具体的路由协议中，各种加速收敛方法往往综合使用。距离向量算法小结路径选择采用最短路径准则，计算D信宿(距离，4）链路状态（Link-State）算法L-S算法的基本概念L-S算法的动态特性L-S算法的性能分析L-S算法与D-V算法的比较OSPF协议4）链路状态（Link-State）算法L-S算法的基本概念链路状态算法的基本概念链路状态算法的基本概念链路状态法的计算举例Dijkatra算法计算结果链路状态算法的基本概念链路状态算法的基本概念每个路由器周期性地收集和发送信息主动测试其到所有邻居的链接状态（度量值）向所有的路由器发送（广播）自己拥有的状态信息得到一个全网的、动态的逻辑链路状态（L-S）图每个路由器刷新自己的路由表当L-S变化时，用最短路径优先(SPF)算法重新计算本地路由DCAB链路状态算法的基本概念__________________________________________________________________________________________路由表SPF算法拓扑数据库（L-S图）SPF树L-S包每个路由器周期性地收集和发送信息DCAB链路状态算法的基本概AEDCB212113Dijkatra最短路径算法计算加权无向图（即L-S图）中两个结点之间的最短路径对每结点赋以标注{D(v),NP(v)}链路状态法的计算举例F3552其中自变量v：无向图中的结点函数D(v)：到目前为止，从源点到结点v的最短路径（边长之和）函数NP(v)：沿源点到结点v的最短路径中与V相邻的前一结点AEDCB212113Dijkatra最短路径算法链路状态法Dijkatra算法计算结果AEDCB212113源点A到所有结点的最短路径F3552DFEABC11212L-S图SPF树Dijkatra算法计算结果AEDCB212113源点A到所L-S算法的动态特性建立路由表的初始过程发现新的网络路由表的维护发现拓扑变化修改拓扑数据库计算SPF树修改路由表L-S算法的动态特性建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1 b0 b1 c0 c1L-S建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.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.0c0ACB40.0.0.0L-S网络发现过程剖析C发现直连网络3（1）发现拓扑变化AEDCBFNetXNetXDownNetXDownLSPLSP发现网络X不可达构造LSP向全网广播发现网络X不可达构造LSP向全网广播（1）发现拓扑变化AEDCBFNetXNetXDow（2）修改拓扑数据库AEDCBFNetX全网具有相同的L-S逻辑图。（2）修改拓扑数据库AEDCBFNetX全网具有相同的LAEDCBFNetX（3）各自重新计算SPF树2233115251AEDCBFNetX（3）各自重新计算SPF树22331AEDCBFNetX根据各自计算的SPF树刷新路由表（4）修改各自的路由表a0a1a2NetY路由表路由表路由表路由表路由表221AEDCBFNetX根据各自计算的SPF树刷新路由表（4L-S算法的性能分析优点代价路由刷新问题线路传输速率不同网络运行状态不同解决办法L-S算法的性能分析优点L-S算法的优点所有路由器具有相同的网络拓扑知识（L-S图）一次性、无修改地向全网广播LSP路由器根据全局信息维护各自的路由表保证链路状态信息的单向传播保证算法的收敛性L-S算法的优点所有路由器具有相同的网络拓扑知识（L-S图）L-S算法的代价SPF算法计算和拓扑数据库需要更多的CPU和内存资源网络启动时的扩散路由信息（flood）需要占用很多带宽资源L-S算法的代价SPF算法计算和拓扑数据库需要更多的CPU和线路传输速率不同产生的影响E应该选择哪棵SPF树？NetXDownNetXupNetXDown来自D来自A慢NetXE收到的LSP开始NetX down后来NetX up线路传输速率不同产生的影响E应该选择哪棵SPF树？NetX网络的一部分已经启动，而另一部分正待启动网络的一部分刷新速度快，而另一部分刷新速度慢造成网络的不同部分拥有不同的L-S图网络运行状态不同产生的影响网络的一部分已经启动，而另一部分正待启动网络运行状态不同产生L-S对问题的解决办法减少对资源的需求尽可能降低路由刷新频度用Multicast取代Broadcast(flood)将网络拓扑结构划分为不同层次和区域在层次间和区域交接处交换路由信息协调L-S刷新对LSP加时间戳标识对LSP加序列号标识用分级路由管理网络的逻辑分组L-S对问题的解决办法减少对资源的需求D-V和L-S算法的比较D-V通过与邻居的信息交换获得网络拓扑知识路由计算是增加路由器之间的站点数（hops）定期刷新路由：收敛慢向相邻站点传送路由表的副本L-S全网获得共同的全局性网络拓扑知识（L-S图）计算到达其他站点的最短路径（SPF准则）触发刷新：收敛快向其他站点发送链路状态的动态变化D-V和L-S算法的比较D-VL-S思考题如果路由表包含全部到达信宿的路径信息显然有助于作出最优选择，是否可行？会带来什么问题？如果路由表只包含相邻站点的路由信息，有何优缺点，能否保证得到全局最优解？指出默认路由的作用。指出静态路由与动态路由的区别。如何解决D-V算法和L-S算法的问题？思考题如果路由表包含全部到达信宿的路径信息显然有助于作出最优对如图所示的网络采用D-V水平分割法计算路由，能否避免产生路径环？从以下几方面描述D-V的工作原理如何传播路由更新信息什么样的知识需要被传播什么时候传播这样的知识怎样存放路由更新信息思考题（续）DBCA断开对如图所示的网络采用D-V水平分割法计算路由，能否避免产生路路由技术确定路由算法设计目标选择类型定义最佳路径的度量准则实现路由协议路由传输协议（RoutedProtocol）网间经路由被传输的协议：IP，OSI，Netware路由选择协议（RoutingProtocol）实现路由选择算法的协议：RIP，OSPF，BGP路由技术确定路由算法1. 路由算法需要考虑的基本因素1）路由算法的设计目标2）选择最佳路由的度量参数1. 路由算法需要考虑的基本因素1）路由算法的设计目标1）路由算法的设计目标优化：根据一定的优化准则选择最佳路径的能力简单：利用最少的物理资源、提供最有效的功能稳定：经受得住各种恶劣环境的考验，故障率低收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由灵活：快速、准确地适应各种网络环境和变化1）路由算法的设计目标优化：根据一定的优化准则选择最佳路径的2）选择最佳路由的度量参数路径长度由网络管理员定义每条网络链路的代价（cost），从源到宿的代价总和为路径长度。以路径中的站点（hop）为单位，从源到宿的站点数之和为路径长度。可靠性 链路数据传输的可靠性（误码率）延迟 数据包从源到宿需要花费的传输时间带宽 链路的最大传输能力以及网络流量负载 网络资源（例如路由器的CPU）的使用率通信代价 占用通信线路的费用2）选择最佳路由的度量参数路径长度2. 路由选择算法1）缺省路径2）静态路由3）动态路由—距离向量法4）动态路由—链路状态法2. 路由选择算法1）缺省路径1）缺省路径（DefaultRoute）什么是缺省路径？对那些在路由表中未包含其路由选择信息的信宿（网络/主机）设定的缺省路径在路由表中信宿地址取值0.0.0.0(Default)缺省路径的作用对所有自治系统以外的信宿都采用缺省路径简化路由计算，提高寻径效率，缩短表长1）缺省路径（DefaultRoute）什么是缺省路径？缺省路径举例网络A网络DRdb0c0f0e0DefaultRde0DefaultRdf0DefaultRa b0DefaultRa c0RaRcRbRfRe缺省路径举例网络A网络DRdb0c0f0e0Default2）静态路由静态路由的概念静态路由工作原理路由配置举例故障举例（网络拓扑结构变化）用人工修改配置排除故障2）静态路由静态路由的概念静态路由的概念由网络管理员设置路由表简单、有效，适于结构简单的网络不适于拓扑结构和传输流量经常改变的复杂网络静态路由的概念由网络管理员设置路由表静态路由举例网络A网络C网络BRa路由表网络B Rb a2网络C Rc a3Rb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1RaRbRc静态路由举例网络A网络C网络BRa路由表Rb路由表Rc路由表链路发生故障网络A网络C网络BRb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1??Ra路由表网络B Rb a2网络C Rc a3RaRbRc链路发生故障网络A网络C网络BRb路由表Rc路由表a1a3a解决办法：人工修改网络A网络C网络BRb路由表网络A Rc b2网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1！！不适于网络变化！Ra路由表网络B Rc a3网络C Rc a3RaRbRc解决办法：人工修改网络A网络C网络BRb路由表Rc路由表a1静态路由算法洪泛（flooding）算法：向着除了进入链路以外的其他链路转发；随机算法：随机选择下一跳；（概率）分流算法：按照链路（静态）带宽（速率）选择下一跳静态路由算法洪泛（flooding）算法：向着除了进入链路以3）距离向量算法Distance-VectorD-V算法的基本概念D-V算法的动态特性D-V算法的收敛性问题及其解决办法D-V算法小结3）距离向量算法Distance-VectorA路由表距离向量算法的基本概念周期性地相互传递信息每个路由器向与它相邻的站点发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价）维护各自的路由表路由器根据邻居发送的距离—向量的动态信息启动算法，更新路由表DCAB路由表C路由表BA距离向量算法的基本概念周期性地相互传递信息DCABCBD-V路由选择算法举例D-V路由选择算法举例距离向量法的计算举例ADECB718221计算从E经相邻站点A、B和D到达信宿A、B、C和D的最小代价D(destination,neighbor)得从E到达信宿的最佳路径（最小代价）路由表最小代价D(des,nei)E的路由表距离向量法的计算举例ADECB718221计算从E经相邻站点距离向量路由算法原路由不经过N但距离大新路由不一定最优，但，原路由可能故障原路为无穷大，则取代为经N、长度为C的路由距离向量路由算法原路由不经过N但距离大新路由不一定最优，但，D-V网络发现过程剖析 1 1 ACB40.0.0.0up到达信宿40.0.0.0的路由变化如果网络中的最长路径为N，则算法经过N次迭代计算后收敛。即第N步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。D-V网络发现过程剖析 1 D-V发现链路断开 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化C与B之间的对话：我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达信宿吗？我可以到达信宿，距离为1。（传播了一条过时的错误信息）既然如此，我选择经过你到达信宿的路径，距离为2。D-V发现链路断开 1 距离向量法的收敛性问题及解决办法问题逐站传递更新信息，算法的收敛速度慢有可能出现各站路由信息不一致后果在站点间构成更新路由的路径环（RoutingLoops）计数至无穷大（CounttoInfinity）解决办法定义路径代价的最大值（Maximum）提高收敛速度距离向量法的收敛性问题及解决办法问题 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化路径环（RoutingLoop）问题这条错误的路由信息在C与B之间不断复制和修改，并在网络中传播（殃及A），形成路径传播的环路。 1 1 ACB 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化严重后果：计数至无穷大 1 1 ACB 1 1 ACB40.0.0.0down到达信宿40.0.0.0的路由变化（定义Hop最大值为16）解决办法：定义距离的最大值收敛！ 1 1 ACB加速收敛的方法水平分割（SplitHorizon）毒性逆转（PoisonReverse）保持计时（Hold-DownTimers）触发更新（TriggeredUpdates）加速方法的综合应用举例加速收敛的方法水平分割（SplitHorizon）距离向量算法小结路径选择采用最短路径准则，计算D信宿(距离，下站)；每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生；在具体的路由协议中，各种加速收敛方法往往综合使用。距离向量算法小结路径选择采用最短路径准则，计算D信宿(距离，4）链路状态（Link-State）算法L-S算法的基本概念L-S算法的动态特性L-S算法的性能分析L-S算法与D-V算法的比较OSPF协议4）链路状态（Link-State）算法L-S算法的基本概念链路状态算法的基本概念链路状态算法的基本概念链路状态法的计算举例Dijkatra算法计算结果链路状态算法的基本概念链路状态算法的基本概念每个路由器周期性地收集和发送信息主动测试其到所有邻居的链接状态（度量值）向所有的路由器发送（广播）自己拥有的状态信息得到一个全网的、动态的逻辑链路状态（L-S）图每个路由器刷新自己的路由表当L-S变化时，用最短路径优先(SPF)算法重新计算本地路由DCAB链路状态算法的基本概念__________________________________________________________________________________________路由表SPF算法拓扑数据库（L-S图）SPF树L-S包每个路由器周期性地收集和发送信息DCAB链路状态算法的基本概AEDCB212113Dijkatra最短路径算法计算加权无向图（即L-S图）中两个结点之间的最短路径对每结点赋以标注{D(v),NP(v)}链路状态法的计算举例F3552其中自变量v：无向图中的结点函数D(v)：到目前为止，从源点到结点v的最短路径（边长之和）函数NP(v)：沿源点到结点v的最短路径中与V相邻的前一结点AEDCB212113Dijkatra最短路径算法链路状态法Dijkatra算法计算结果AEDCB212113源点A到所有结点的最短路径F3552DFEABC11212L-S图SPF树Dijkatra算法计算结果AEDCB212113源点A到所L-S算法的动态特性建立路由表的初始过程发现新的网络路由表的维护发现拓扑变化修改拓扑数据库计算SPF树修改路由表L-S算法的动态特性建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1 b0 b1 c0 c1L-S建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.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.0c0ACB40.0.0.0L-S网络发现过程剖析C发现直连网络3（1）发现拓扑变化AEDCBFNetXNetXDownNetXDownLSPLSP发现网络X不可达构造LSP向全网广播发现网络X不可达构造LSP向全网广播（1）发现拓扑变化AEDCBFNetXNetXDow（2）修改拓扑数据库AEDCBFNetX全网具有相同的L-S逻辑图。（2）修改拓扑数据库AEDCBFNetX全网具有相同的LAEDCBFNetX（3）各自重新计算SPF树2233115251AEDCBFNetX（3）各自重新计算SPF树22331