动态路由算法与拥塞控制337982ppt课件-PPT课件.ppt

1、主要内容（2）7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由7.2路由算法（28）7.2.5 距离向量路由算法（DV：Distance Vector Routing）属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP(Routing Information Protocol)协议采用。基本思想每个路由器维护一张表，表中给出了到每个目的地的已

2、知最佳距离和线路，并通过与相邻路由器相邻路由器交换距离信息来更新表；以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；7.2路由算法（29）-每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；-邻居结点X向路由器Y发来的表中，X到路由器Zi的距离为Li，路由器Y到X的距离为m，则路由器Y经过X到Zi的距离为Li+m。根据不同邻居发来的信息，计算Li+m，并取最小值，更新Y路由器的路由表；-注意：Y路由器中的老路由表在计算中不被使用ABCDEFGHIJKL路由器ABCDEFGHIJKL012

3、2540142318172192429ABCEDFGHIJKLA2436182772031200112233I2031198301960147229H2128362422403119221009K新估计从J出发的延时J到A的延迟为8J到I的延迟为10J到H的延迟为12J到K的延迟为6J从它的四个邻居路由器上收到的向量J的新路由表A820A28I20H17I30I18H12H10I06K15K7.2路由算法（30）无限计算问题算法的缺陷：对好消息反应迅速(好消息：网络上加入一个路由器）对坏消息反应迟钝（坏消息：网络上减少一个路由器）ABCDE初始时1第一次交换后12第二次交换后123第三次交换后

4、1234第四次交换后对好消息反应迅速ABCDE1234初始时3234第一次交换后3434第二次交换后5454第三次交换后5656第四次交换后7676第五次交换后7878第六次交换后 对坏消息反应迟钝：引起无穷计算问题7.2路由算法（31）为什么会出现无穷计算问题：因为路由器A通过路由器B才能到达路由器C，虽然路由器A已经下线，C仍然向B报告了以前C到A的距离。解决无穷计算问题的方法：水平分裂算法工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告，使得坏消息传播的也快。7.2路由算法（32）ABCDE234第一次交换后34第二次交换后4第三次交换后第四次交换后123初始时

5、47.2路由算法（33）虽然广泛使用，但有时候会失败。主要内容（2）7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由7.2路由算法（34）7.2.6链路状态路由算法（LS：Link State Routing）距离向量路由算法的主要问题选择路由时，没有考虑线路带宽；路由收敛速度慢(无穷计算)。7.2路由算法（35）链路状态路由算法发现邻居结点，并学习它们的网络地址；测量到每个邻居结点的延迟或开销；将所有学习到的内

6、容封装成一个包；将这个包发送给所有其它路由器；1)每个路由器独立计算到其它路由器的最短路径。7.2路由算法（36）发现邻居结点，并学习它们的网络地址；路由器启动后，通过发送HELLO包发现邻居结点；1)两个或多个路由器连在一个LAN时,引入人工结点；7.2路由算法（37）7.2路由算法（38）测量到每个邻居结点的延迟或开销；一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。7.2路由算法（39）将所有学习到的内容封装成一个包；包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；列表中对应每个邻居结点，都有发送方到它们的延迟或开销；链路状态包定期创建或发生重大

7、事件时创建。7.2路由算法（40）7.2路由算法（41）将这个包发送给所有其它路由器；基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对(源路由器，序号)，当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；7.2路由算法（42）第4步中存在的问题序号循环使用会混淆路由器崩溃；序号出错；7.2路由算法（43）解决这些问题的办法序号循环使用会混淆，解决办法：使用32位序号；路由器崩溃后，序号重置；增加年龄（age）域，每秒钟年龄减1，为零则丢弃。链路状态包到达后，延迟一段时间，并与其它已到达

8、的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；序号出错 链路状态包需要应答；BCDFEA源点 顺序号 年龄 ACFACF数据发送标志应答标志A2160011100F2160110001E2159010101C2060101010D21591000117.2路由算法（44）计算到每个其它路由器的最短路径。根据Dijkstra算法计算最短路径；实用协议Internet网络协议：内部网关路由协议开放最短路径优先OSPF（Open Shortest Path First）IS-IS7.2路由算法（45）距离向量算法（DV）和链路状态算法（LS）的比较路由信息的复杂性DV仅在邻居节点之间交

9、换LS路由信息向全网发送N节点，E个连接的情况下，每个节点发送O(nE)的报文7.2路由算法（46）收敛（Convergence）速度DV收敛时间不定：可能会出现路由循环LS使用最短路径优先算法，算法复杂度为O(n2)（n个结点（不包括源结点），需要n*(n+1)/2 次比较），如果使用更有效的实现方法，算法复杂度可以达到O(nlogn)可能存在路由振荡（oscillations）7.2路由算法（47）健壮性:如果路由器不能正常工作会发生什么?DV结点会广播错误的路径开销每个结点的路由表被别的结点使用，错误会传播到全网LS结点会广播错误的链路开销每个结点只计算自己的路由表主要内容（2）7.1网

10、络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由7.2路由算法（48）7.2.7分层路由（Hierarchical Routing）网络规模增长带来的问题路由器中的路由表增大；路由器为选择路由而占用的内存、CPU时间和网络带宽增大。7.2路由算法（49）分层路由分而治之的思想；根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups）Fig.5-17，路由表由17项减为7

11、项。分层路由带来的问题路由表中的路由不一定是最优路由。7.2路由算法（50）主要内容（2）7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由7.2路由算法（51）7.2.8 移动主机的路由需要解决的问题为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。网络结构示意图7.2路由算法（52）一些基本概念 移动用户（mobile users）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户 家乡

12、位置（home location）：所有用户都有一个永久的家乡位置，用一个地址来标识；外部代理（foreign agent）：每个区域（一个LAN或一个wireless cell）有一个或多个外部代理，它们记录正在访问该区域的移动用户；家乡代理（home agent）：每个区域有一个家乡代理，负责记录家乡在该区域，但是目前正在访问其它区域的用户。7.2路由算法（53）外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外部代理的地址 移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息；外部代理与移动主机的

13、家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；家乡代理检查安全信息，通过，则给外部代理确认;外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。l 移动用户进入一个新区域时，必须首先向外部代理注册7.2路由算法（54）移动用户的路由转发过程 当一个包发给移动用户时，首先被转发到用户的家乡局域网；该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址；家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理；家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理；外部代理收到包后，将净荷

14、封装成数据链路帧发给移动用户。主要内容（2）小结（1）7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由主要内容（2）小结（2）最优化原则路由算法的目的是找出并使用汇集树。静态路由算法最短路径路由算法洪泛算法基于流量的路由算法主要内容（2）小结（3）动态路由算法距离向量路由算法将自己（路由结点）对全网拓扑结构的认识告诉给邻居无穷计算问题，水平分裂算法链路状态路由算法将自己（路由结点）对邻居的认识洪泛给全网分层路由移

15、动主机的路由主要内容（3）7.3拥塞控制算法7.3.1 拥塞控制的基本原理7.3.2 拥塞控制算法7.4网络互连 7.4.1 级联虚电路 7.4.2 无连接网络互连 7.4.3 隧道技术 7.4.4 互联网路由 7.4.5 分段 7.4.6 防火墙主要内容（3）7.3拥塞控制算法7.3.1 拥塞控制的基本原理7.3.2 拥塞控制算法7.3拥塞控制算法（1）拥塞（congestion）网络上有太多的包时，性能会下降，这种情况称为拥塞拥塞。拥塞产生的原因多个输入对应一个输出；慢速处理器；低带宽线路。7.3拥塞控制算法（2）解决办法针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅

16、仅是转移了影响性能的瓶颈；需要全面考虑各个因素。7.3拥塞控制算法（3）拥塞控制与流量控制的差别拥塞控制（congestion control）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素；流量控制（flow control）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。发送的分组转发的分组子网的最大传输容量完美效果理想效果拥塞后实际效果7.3拥塞控制算法（4）7.3.1拥塞控制的基本原理根据控制论，拥塞控制方法分为两类开环控制通过好的设计来解决问题，避免拥塞发生；拥塞控制时，不考虑网络当前状态。闭

17、环控制基于反馈机制；工作过程监控系统，发现何时何地发生拥塞；把发生拥塞的消息传给能采取动作的站点调整系统操作，解决问题。7.3拥塞控制算法（5）衡量网络是否拥塞的参数缺乏缓冲区造成的丢包率；平均队列长度；超时重传的包的数目；平均包延迟；包延迟变化（Jitter）。7.3拥塞控制算法（6）反馈方法向负载发生源发送一个告警包；包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警；主机或路由器主动地、周期性地发送探报（probe），查询是否发生拥塞。主要内容（3）7.3拥塞控制算法7.3.1 拥塞控制的基本原理7.3.2 拥塞控制算法7.3拥塞控制算法（7）7.

18、3.2拥塞控制算法拥塞预防策略拥塞预防策略流量整形（流量整形（Traffic Shaping）流说明（流说明（Flow Specification）虚电路子网中的拥塞控制虚电路子网中的拥塞控制抑制包（抑制包（Choke Packets）加权公平队列（加权公平队列（Weighted Fair Queueing）逐跳抑制包（逐跳抑制包（Hop-by-Hop Choke Packets）负载丢弃（负载丢弃（Load Shedding）7.3拥塞控制算法（8）拥塞预防策略开环控制影响拥塞的网络设计策略7.3拥塞控制算法（9）层影响拥塞的策略运输层重发策略重发策略乱序缓存策略乱序缓存策略确认策略确认策略

19、流量控制策略流量控制策略超时终止超时终止网络层子网是虚电路或数据报子网是虚电路或数据报分组排队和服务策略分组排队和服务策略分组丢弃策略分组丢弃策略路由选择算法路由选择算法分组生命周期管理分组生命周期管理数据链路层重发策略重发策略乱序缓存策略乱序缓存策略确认策略确认策略流量控制策略流量控制策略7.3拥塞控制算法7.3拥塞控制算法（7）7.3.2拥塞控制算法拥塞预防策略拥塞预防策略流量整形（流量整形（Traffic Shaping）流说明（流说明（Flow Specification）虚电路子网中的拥塞控制虚电路子网中的拥塞控制抑制包（抑制包（Choke Packets）加权公平队列（加权公平队列

20、（Weighted Fair Queueing）逐跳抑制包（逐跳抑制包（Hop-by-Hop Choke Packets）负载丢弃（负载丢弃（Load Shedding）7.3拥塞控制算法（10）流量整形（Traffic Shaping）开环控制基本思想造成拥塞的主要原因是网络流量通常是突发性的；强迫包以一种可预测的速率发送；在ATM网中广泛使用。7.3拥塞控制算法（11）漏桶算法（The Leaky Bucket Algorithm）将用户发出的不平滑的数据包流转变成网络中平滑的数据包流；可用于固定包长的协议，如ATM；也可用于可变包长的协议，如IP，使用字节计数；无论负载突发性如何，漏桶算

21、法强迫输出按平均速率进行，不灵活。7.3拥塞控制算法（12）令牌桶算法（The Token Bucket Algorithm）漏桶算法不够灵活，因此加入令牌机制；基本思想：漏桶存放令牌，每T秒产生一个令牌，令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；7.3拥塞控制算法（13）漏桶算法与令牌桶算法的区别流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。流量最大到25MB/s流量为2MB/s漏桶算法/令牌桶算

22、法比较时间t流量漏桶输入的流量25MB/s 持续40ms漏桶输出的流量2MB/s 持续500ms25时间t流量2漏桶算法25MB/s 持续40ms令牌桶输出的流量25MB/s 持续约11ms时间t流量令牌桶输入的流量25容量为250KB的令牌桶算法时间t流量2252MB/s 持续364ms25MB/s 持续40ms令牌桶输出的流量25MB/s 持续约22ms时间t流量令牌桶输入的流量25容量为500KB的令牌桶算法时间t流量2252MB/s 持续228ms25MB/s 持续40ms令牌桶输出的流量25MB/s 持续约33ms时间t流量令牌桶输入的流量25容量为750KB的令牌桶算法时间t流量2

23、252MB/s 持续92ms25MB/s 持续约11ms时间t流量2252MB/s 持续364ms25MB/s 持续约22ms时间t流量2252MB/s 持续228ms25MB/s 持续约33ms流量2252MB/s 持续92ms7.3拥塞控制算法（14）漏桶/令牌桶组合方法：令牌桶漏桶一般设定为漏桶的速率比令牌桶的最低速率大，比网络的最大速率小。25MB/s 持续40ms时间t流量令牌桶输入的流量25容量为500KB的令牌桶+10MB/s的漏桶7.3拥塞控制算法（15）令牌桶输出的流量25MB/s 持续22ms时间t流量2252MB/s 持续228ms10MB/s 持续62ms漏桶输出的流量

24、时间t流量2102MB/s 持续190ms7.3拥塞控制算法（16）流说明（Flow Specification）当发送者、接收者和子网都达到一致性后，通信量整形才能发挥最佳效果。要达成一致，必须以一种精确的方式来通知各方，说明通信量模式，即采用流说明的方式。7.3拥塞控制算法（17）一个数据流的发送方、接收方和通信子网三方认可的、描述发送数据流的模式和希望得到的服务质量的数据结构，称为流说明流说明。对发送方的流说明，子网和接收方可以做出三种答复：同意、拒绝、其它建议。7.3拥塞控制算法（18）输入的特性想要的服务最大分组大小（字节数）丢失敏感性（字节数）令牌桶速率（B/s)丢失间隔（微秒）令

25、牌桶大小（字节数）突发丢失敏感性（分组数）最大传输速率（B/s)最小通知延迟（微秒）最小延迟变化（微秒）质量保证一个流说明的例子7.3拥塞控制算法（19）虚电路子网中的拥塞控制许可控制（admission control），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。7.3拥塞控制算法（21）抑制包（Choke Packets）基本思想路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态；每个新包到来，检查

26、它的输出线路是否处于警戒状态；若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址。同时将原包打上标记（为了以后不再产生抑制包），正常转发；7.3拥塞控制算法（22）源主机收到抑制包后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。7.3拥塞控制算法（23）使用抑制包的方法的问题：源端主机是否采取行动是自愿的，假设一个路由器由于被多个主机超

27、量发送的流量而形成拥塞；路由器会向所有的源端主机都发送抑制包；有些主机可能会减慢发送速度，但有些主机不一定会减慢发送速度；结果是遵守规则的主机反而得到了比以前少的带宽。解决这种问题的办法是采用加权公平队列7.3拥塞控制算法（24）加权公平队列（Weighted Fair Queueing）公平队列（Fair Queueing）算法路由器的每个输出线路有多个队列；路由器循环扫描各个队列，发送队头的包；所有队列具有相同优先级；一些ATM交换机、路由器使用这种算法；一种改进：对于变长包，由逐包轮循改为逐字节轮循38C49D1317510E141816A11151927B1216O分组完全输出时间AB

28、CDE191681718路由器7.3拥塞控制算法（25）7.3拥塞控制算法（26）加权公平队列算法给不同主机以不同的优先级；优先级高的主机在一个轮循周期内获得更多的时间片。7.3拥塞控制算法（27）逐跳抑制包（Hop-by-Hop Choke Packets）在高速、长距离的网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制包算法。基本思想抑制包对它经过的每个路由器都起作用；能够迅速缓解发生拥塞处的拥塞；上游路由器要求有更多的缓冲区；BCDFEA第一步第二步第三步第四步BCDFEABCDFEABCDFEA抑制包算法的过程BCDFEA第五步第六步第七步BCDFEABCD

29、FEA抑制包算法的过程BCDFEA第一步第二步第三步第四步BCDFEABCDFEABCDFEA逐跳抑制包算法的过程第五步BCDFEA逐跳抑制包算法的过程7.3拥塞控制算法（28）负载丢弃（Load Shedding）上述算法都不能消除拥塞时，路由器只得将包丢弃；针对不同服务，可采取不同丢弃策略文件传输，优先丢弃新包，wine策略；多媒体服务，优先丢弃旧包，milk策略；早期丢弃包，会减少拥塞发生的概率，提高网络性能。7.3拥塞控制算法（29）小结7.3.1 拥塞控制的基本原理7.3.2拥塞控制算法拥塞预防策略拥塞预防策略流量整形（流量整形（Traffic Shaping）流说明（流说明（Flow Specification）虚电路子网中的拥塞控制虚电路子网中的拥塞控制抑制包（抑制包（Choke Packets）加权公平队列（加权公平队列（Weighted Fair Queueing）逐跳抑制包（逐跳抑制包（Hop-by-Hop Choke Packets）负载丢弃（负载丢弃（Load Shedding）