动态路由算法与拥塞控制337982课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,主要内容（,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),协议采用。,基本思想,每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与,相邻路由器,交换距离信息来更新表；,以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；,7.2,路由算法（,29,）,每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；,邻居结点,X,向路由器,Y,发来的表中，,X,到路由器,Z,i,的距离为,L,i,，,路由器,Y,到,X,的距离为,m,，则路由器,Y,经过,X,到,Z,i,的距离为,L,i,+ m,。根据不同邻居发来的信息，计算,L,i,+ m,，并取最小值，更新,Y,路由器的路由表；,注意：,Y,路由器中的老路由表在计算中不被使用,A,B,C,D,E,F,G,H,I,J,K,L,路由器,A,B,C,D,E,F,G,H,I,J,K,L,0,12,25,40,14,23,18,17,21,9,24,29,A,B,C,E,D,F,G,H,I,J,K,L,A,24,36,18,27,7,20,31,20,0,11,22,33,I,20,31,19,8,30,19,6,0,14,7,22,9,H,21,28,36,24,22,40,31,19,22,10,0,9,K,新估计从,J,出发的延时,J,到,A,的延迟为,8,J,到,I,的延迟为,10,J,到,H,的延迟为,12,J,到,K,的延迟为,6,J,从它的四个邻居路由器上收到的向量,J,的新路由表,A,8,20,A,28,I,20,H,17,I,30,I,18,H,12,H,10,I,0,6,K,15,K,7.2,路由算法（,30,）,无限计算问题,算法的缺陷：,对好消息反应迅速,(,好消息：网络上加入一个路由器）,对坏消息反应迟钝（坏消息：网络上减少一个路由器）,A,B,C,D,E,初始时,1,第一次交换后,1,2,第二次交换后,1,2,3,第三次交换后,1,2,3,4,第四次交换后,对好消息反应迅速,A,B,C,D,E,1,2,3,4,初始时,3,2,3,4,第一次交换后,3,4,3,4,第二次交换后,5,4,5,4,第三次交换后,5,6,5,6,第四次交换后,7,6,7,6,第五次交换后,7,8,7,8,第六次交换后,对坏消息反应迟钝：引起无穷计算问题,7.2,路由算法（,31,）,为什么会出现无穷计算问题：,因为路由器,A,通过路由器,B,才能到达路由器,C,，虽然路由器,A,已经下线，,C,仍然向,B,报告了以前,C,到,A,的距离。,解决无穷计算问题的方法：水平分裂算法,工作过程与距离向量算法相同，区别在于到,X,的距离不向真正通向,X,的邻居结点报告，使得坏消息传播的也快。,7.2,路由算法（,32,）,A,B,C,D,E,2,3,4,第一次交换后,3,4,第二次交换后,4,第三次交换后,第四次交换后,1,2,3,初始时,4,7.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,）,链路状态路由算法,发现邻居结点，并学习它们的网络地址；,测量到每个邻居结点的延迟或开销；,将所有学习到的内容封装成一个包；,将这个包发送给所有其它路由器；,每个路由器独立计算到其它路由器的最短路径。,返回,7.2,路由算法（,36,）,发现邻居结点，并学习它们的网络地址；,路由器启动后，通过发送,HELLO,包发现邻居结点；,两个或多个路由器连在一个,LAN,时,引入人工结点；,7.2,路由算法（,37,）,7.2,路由算法（,38,）,测量到每个邻居结点的延迟或开销；,一种直接的方法是：发送一个要对方立即响应的,ECHO,包，来回时间除以,2,即为延迟。,7.2,路由算法（,39,）,将所有学习到的内容封装成一个包；,包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；,列表中对应每个邻居结点，都有发送方到它们的延迟或开销；,链路状态包定期创建或发生重大事件时创建。,7.2,路由算法（,40,）,7.2,路由算法（,41,）,将这个包发送给所有其它路由器；,基本思想：,洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加,1,。,路由器记录信息对,(,源路由器，序号,),，当一个链路状态包到达时，若是新的，则分发；,若是重复的，则丢弃；,若序号比路由器记录中的最大序号小，则认为过时而丢弃；,7.2,路由算法（,42,）,第,4,步中存在的问题,序号循环使用会混淆,路由器崩溃；,序号出错；,7.2,路由算法（,43,）,解决这些问题的办法,序号循环使用会混淆，解决办法：使用,32,位序号；,路由器崩溃后，序号重置；,增加年龄（,age,）域，每秒钟年龄减,1,，为零则丢弃。,链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；,序号出错,链路状态包需要应答；,B,C,D,F,E,A,源点,顺序号,年龄,A,C,F,A,C,F,数据,发送标志,应答标志,A,21,60,0,1,1,1,0,0,F,21,60,1,1,0,0,0,1,E,21,59,0,1,0,1,0,1,C,20,60,1,0,1,0,1,0,D,21,59,1,0,0,0,1,1,7.2,路由算法（,44,）,计算到每个其它路由器的最短路径。,根据,Dijkstra,算法计算最短路径；,实用协议,Internet,网络协议：,内部网关路由协议,开放最短路径优先,OSPF,（,Open Shortest Path First,）,IS-IS,7.2,路由算法（,45,）,距离向量算法（,DV,）和链路状态算法（,LS,）的比较,路由信息的复杂性,DV,仅在邻居节点之间交换,LS,路由信息向全网发送,N,节点，,E,个连接的情况下，每个节点发送,O(nE),的报文,7.2,路由算法（,46,）,收敛（,Convergence,）速度,DV,收敛时间不定：可能会出现路由循环,LS,使用最短路径优先算法，算法复杂度为,O(n,2,),（,n,个结点（不包括源结点），需要,n*(n+1)/2,次比较），如果使用更有效的实现方法，算法复杂度可以达到,O(nlogn),可能存在路由振荡（,oscillations,）,7.2,路由算法（,47,）,健壮性,:,如果路由器不能正常工作会发生什么,?,DV,结点会广播错误的路径开销,每个结点的路由表被别的结点使用，错误会传播到全网,LS,结点会广播错误的链路开销,每个结点只计算自己的路由表,主要内容（,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,路由算法（,48,）,7.2.7,分层路由（,Hierarchical Routing,）,网络规模增长带来的问题,路由器中的路由表增大；,路由器为选择路由而占用的内存、,CPU,时间和网络带宽增大。,7.2,路由算法（,49,）,分层路由,分而治之的思想；,根据需要，将路由器分成区域（,regions,）、聚类（,clusters,）、区（,zones,）和组（,groups,）,Fig. 5-17,，路由表由,17,项减为,7,项。,分层路由带来的问题,路由表中的路由不一定是最优路由。,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,）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户,家乡位置（,home location,）：所有用户都有一个永久的家乡位置，用一个地址来标识；,外部代理（,foreign agent,）：每个区域（一个,LAN,或一个,wireless cell,）有一个或多个外部代理，它们记录正在访问该区域的移动用户；,家乡代理（,home agent,）：,每个区域有一个家乡代理，负责记录家乡在该区域，但是目前正在访问其它区域的用户。,7.2,路由算法（,53,）,外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外部代理的地址,移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息；,外部代理与移动主机的家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；,家乡代理检查安全信息，通过，则给外部代理确认,;,外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。,移动用户进入一个新区域时，必须首先向外部代理注册,7.2,路由算法（,54,）,移动用户的路由转发过程,当一个包发给移动用户时，首先被转发到用户的家乡局域网；,该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址；,家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理；,家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理；,外部代理收到包后，将净荷封装成数据链路帧发给移动用户。,主要内容（,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,）,动态路由算法,距离向量路由算法,将自己（路由结点）对全网拓扑结构的认识告诉给邻居,无穷计算问题，水平分裂算法,链路状态路由算法,将自己,（路由结点）,对邻居的认识洪泛给全网,分层路由,移动主机的路由,主要内容（,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,）,解决办法,针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈；,需要全面考虑各个因素。,7.3,拥塞控制算法（,3,）,拥塞控制与流量控制的差别,拥塞控制（,congestion control,）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素；,流量控制（,flow control,）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。,发送的分组,转发的分组,子网的最大传输容量,完美效果,理想效果,拥塞后实际效果,7.3,拥塞控制算法（,4,）,7.3.1,拥塞控制的基本原理,根据控制论，拥塞控制方法分为两类,开环控制,通过好的设计来解决问题，避免拥塞发生；,拥塞控制时，不考虑网络当前状态。,闭环控制,基于反馈机制；,工作过程,监控系统，发现何时何地发生拥塞；,把发生拥塞的消息传给能采取动作的站点,调整系统操作，解决问题。,7.3,拥塞控制算法（,5,）,衡量网络是否拥塞的参数,缺乏缓冲区造成的丢包率；,平均队列长度；,超时重传的包的数目；,平均包延迟；,包延迟变化（,Jitter,）。,7.3,拥塞控制算法（,6,）,反馈方法,向负载发生源发送一个告警包；,包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警；,主机或路由器主动地、周期性地发送探报（,probe,），,查询是否发生拥塞。,主要内容（,3,）,7.3,拥塞控制算法,7.3.1,拥塞控制的基本原理,7.3.2,拥塞控制算法,7.3,拥塞控制算法（,7,）,7.3.2,拥塞控制算法,拥塞预防策略,流量整形（,Traffic Shaping,）,流说明（,Flow Specification,）,虚电路子网中的拥塞控制,抑制包（,Choke Packets,）,加权公平队列（,Weighted Fair Queueing,）,逐跳抑制包（,Hop-by-Hop Choke Packets,）,负载丢弃（,Load Shedding,）,7.3,拥塞控制算法（,8,）,拥塞预防策略,开环控制,影响拥塞的网络设计策略,7.3,拥塞控制算法（,9,）,层,影响拥塞的策略,运输层,重发策略,乱序缓存策略,确认策略,流量控制策略,超时终止,网络层,子网是虚电路或数据报,分组排队和服务策略,分组丢弃策略,路由选择算法,分组生命周期管理,数据链路层,重发策略,乱序缓存策略,确认策略,流量控制策略,7.3,拥塞控制算法,7.3,拥塞控制算法（,7,）,7.3.2,拥塞控制算法,拥塞预防策略,流量整形（,Traffic Shaping,）,流说明（,Flow Specification,）,虚电路子网中的拥塞控制,抑制包（,Choke Packets,）,加权公平队列（,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,，使用字节计数；,无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。,7.3,拥塞控制算法（,12,）,令牌桶算法（,The Token Bucket Algorithm,）,漏桶算法不够灵活，因此加入令牌机制；,基本思想：漏桶存放令牌，每,T,秒产生一个,令牌，令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；,7.3,拥塞控制算法（,13,）,漏桶算法与令牌桶算法的区别,流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。,漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。,流量最大到,25MB/s,流量为,2MB/s,漏桶算法,/,令牌桶算法比较,时间,t,流量,漏桶输入的流量,25MB/s,持续,40ms,漏桶输出的流量,2MB/s,持续,500ms,25,时间,t,流量,2,漏桶算法,25MB/s,持续,40ms,令牌桶输出的流量,25MB/s,持续约,11ms,时间,t,流量,令牌桶,输入的流量,25,容量为,250KB,的,令牌桶,算法,时间,t,流量,2,25,2MB/s,持续,364ms,25MB/s,持续,40ms,令牌桶输出的流量,25MB/s,持续约,22ms,时间,t,流量,令牌桶,输入的流量,25,容量为,500KB,的,令牌桶,算法,时间,t,流量,2,25,2MB/s,持续,228ms,25MB/s,持续,40ms,令牌桶输出的流量,25MB/s,持续约,33ms,时间,t,流量,令牌桶,输入的流量,25,容量为,750KB,的,令牌桶,算法,时间,t,流量,2,25,2MB/s,持续,92ms,25MB/s,持续约,11ms,时间,t,流量,2,25,2MB/s,持续,364ms,25MB/s,持续约,22ms,时间,t,流量,2,25,2MB/s,持续,228ms,25MB/s,持续约,33ms,流量,2,25,2MB/s,持续,92ms,7.3,拥塞控制算法（,14,）,漏桶,/,令牌桶组合方法：,令牌桶,漏桶,一般设定为漏桶的速率比令牌桶的最低速率大，比网络的最大速率小。,25MB/s,持续,40ms,时间,t,流量,令牌桶,输入的流量,25,容量为,500KB,的,令牌桶,+10MB/s,的漏桶,7.3,拥塞控制算法（,15,）,令牌桶,输出的流量,25MB/s,持续,22ms,时间,t,流量,2,25,2MB/s,持续,228ms,10MB/s,持续,62ms,漏桶,输出的流量,时间,t,流量,2,10,2MB/s,持续,190ms,7.3,拥塞控制算法（,16,）,流说明（,Flow Specification,）,当发送者、接收者和子网都达到一致性后，通信量整形才能发挥最佳效果。,要达成一致，必须以一种精确的方式来通知各方，说明通信量模式，即采用,流说明,的方式。,7.3,拥塞控制算法（,17,）,一个数据流的发送方、接收方和通信子网三方认可的、描述发送数据流的模式和希望得到的服务质量的数据结构，称为,流说明,。,对发送方的流说明，子网和接收方可以做出三种答复：同意、拒绝、其它建议。,7.3,拥塞控制算法（,18,）,输入的特性,想要的服务,最大分组大小（字节数）,丢失敏感性（字节数）,令牌桶速率（,B/s),丢失间隔（微秒）,令牌桶大小（字节数）,突发丢失敏感性（分组数）,最大传输速率（,B/s),最小通知延迟（微秒）,最小延迟变化（微秒）,质量保证,一个流说明的例子,7.3,拥塞控制算法（,19,）,虚电路子网中的拥塞控制,许可控制（,admission control,），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；,另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；,资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。,7.3,拥塞控制算法（,20,）,7.3,拥塞控制算法（,21,）,抑制包（,Choke Packets,）,基本思想,路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态；,每个新包到来，检查它的输出线路是否处于警戒状态；,若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址。同时将原包打上标记（为了以后不再产生抑制包），正常转发；,7.3,拥塞控制算法（,22,）,源主机收到抑制包后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；,通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。,7.3,拥塞控制算法（,23,）,使用抑制包的方法的问题：,源端主机是否采取行动是自愿的，假设一个路由器由于被多个主机超量发送的流量而形成拥塞；路由器会向所有的源端主机都发送抑制包；,有些主机可能会减慢发送速度，但有些主机不一定会减慢发送速度；结果是遵守规则的主机反而得到了比以前少的带宽。,解决这种问题的办法是采用,加权公平队列,7.3,拥塞控制算法（,24,）,加权公平队列（,Weighted Fair Queueing,）,公平队列（,Fair Queueing,）算法,路由器的每个输出线路有多个队列；,路由器循环扫描各个队列，发送队头的包；,所有队列具有相同优先级；,一些,ATM,交换机、路由器使用这种算法；,一种改进：对于变长包，由逐包轮循改为逐字节轮循,3,8,C,4,9,D,13,17,5,10,E,14,18,1,6,A,11,15,19,2,7,B,12,16,O,分组,完全输出时间,A,B,C,D,E,19,16,8,17,18,路由器,7.3,拥塞控制算法（,25,）,7.3,拥塞控制算法（,26,）,加权公平队列算法,给不同主机以不同的优先级；,优先级高的主机在一个轮循周期内获得更多的时间片。,7.3,拥塞控制算法（,27,）,逐跳抑制包（,Hop-by-Hop Choke Packets,）,在高速、长距离的网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制包算法。,基本思想,抑制包对它经过的每个路由器都起作用；,能够迅速缓解发生拥塞处的拥塞；,上游路由器要求有更多的缓冲区；,B,C,D,F,E,A,第一步,第二步,第三步,第四步,B,C,D,F,E,A,B,C,D,F,E,A,B,C,D,F,E,A,抑制包算法的过程,B,C,D,F,E,A,第五步,第六步,第七步,B,C,D,F,E,A,B,C,D,F,E,A,抑制包算法的过程,B,C,D,F,E,A,第一步,第二步,第三步,第四步,B,C,D,F,E,A,B,C,D,F,E,A,B,C,D,F,E,A,逐跳抑制包,算法的过程,第五步,B,C,D,F,E,A,逐跳抑制包,算法的过程,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,）,