《数据通信与计算机网络-09路由选择和拥塞控制.ppt》由会员分享，可在线阅读，更多相关《数据通信与计算机网络-09路由选择和拥塞控制.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第9讲 路由选择与拥塞控制第第9 9讲讲 路由选择和拥塞控制路由选择和拥塞控制 课时授课计划 课 程 内 容第9讲 路由选择与拥塞控制内容：路由选择策略 拥塞控制 目的与要求：理解路由选择算法；了解拥塞控制策略方法 重点与难点：重点：路由选择算法；难点：路由选择算法。第9讲 路由选择与拥塞控制课堂讨论：路由选择？漏桶算法？现代教学方法与手段：投影 PowerPoint幻灯课件复习（提问）：虚电路和数据报服务？第9讲 路由选择与拥塞控制复习复习虚电路（Virtual Circuit）数据报（Datagram）ACBDEACDH1H2H4H3H5H6ACBDEACDH1H2H4H3H5H6(a)数
2、据报服务数据报服务(b)虚电路服务虚电路服务第9讲 路由选择与拥塞控制第第5 5章章 网络层网络层5.3路由选择5.4 拥塞控制5.5 X.25协议第9讲 路由选择与拥塞控制固定路由选择固定路由选择固定路由选择 在每个节点上保持一张路由表,表上标明对每一个目的地址应走哪条链路进行转发.路由表是在整个系统进行配置时生成的.配置时根据事先计算好的“网络中任意两个节点之间最短路径”,将这些最短通路制成路由表,存放在各个节点中.每一个分组都可在所到达的节点中查找下一步应转发到哪一个节点(下一站节点或后继节点).经典的求最短路径算法是Dijkstra算法.它的条件是已它的条件是已知网络的拓扑和各链路长度
3、知网络的拓扑和各链路长度,主要是通过计算任意两节点间的最小链路长度,求得从源节点到目的节点间最短通路.第9讲 路由选择与拥塞控制固定路由选择固定路由选择Dijkstra算法 对于一个无向图G=(V，E),其中V表示网络中所有节点的集合,E表示网络中所有链路的集合,D(v)为源节点到节点v的距离,l(i,j)为节点i至节点j之间的距离.(1)初始化 任选一个节点作为源节点,不妨不妨令 V=1,对所有不在V中的节点v,写出:1456232221113355图图 求最短路径算法的网络拓扑求最短路径算法的网络拓扑实际编程时一般取D(v)=1000代替.源源节点节点第9讲 路由选择与拥塞控制固定路由选择
4、固定路由选择(2)寻找一个不在V中的节点w,其D(w)值为最小.把w加入到V中.然后对所有不在V中的节点,用D(v),D(w)+l(w,v)中较小的值去更新原有的D(v)值,即:D(v)MinD(v),D(w)+l(w,v)(3)重复步骤(2),直到所有的网络节点都在V中为止.由Dijkstra算法可知,若将已知的各链路长度改为链路时延链路时延,跳数跳数,带宽或费用带宽或费用,就相当于求任意两节点之间具有最小时延,最少跳数,最大带宽或最小费用的通路.所以,求最短路径算法具有普遍的应用价值.第9讲 路由选择与拥塞控制固定路由选择固定路由选择基于左图的网络拓扑结构基于左图的网络拓扑结构,采采用用D
5、ijkstra算法算法,计算以节点计算以节点1为源节点的最短通路的过程为源节点的最短通路的过程.表中带圆圈的数字表示表中带圆圈的数字表示的是的是:在每一次执行步在每一次执行步骤骤(2)时时,所寻找到的所寻找到的具有最小值的具有最小值的D(w)值值.步骤步骤 V D(2)D(3)D(4)D(5)D(6)初始化初始化 1 2 5 1 1 1,4 2 4 2 2 1,4,5 2 3 1 4 3 1,2,4,5 3 1 2 4 4 1,2,3,4,5 2 1 2 4 5 1,2,3,4,5,6 2 3 1 2 1456232221113355第9讲 路由选择与拥塞控制固定路由选择固定路由选择 上述路由
6、表仅是以节点1为源节点,由Dijkstra算法计算得到节点1为根的通路树,然后生成节点1内存中的路由表这样的路由表每个节点都有一个这样的路由表每个节点都有一个,只需分别以这些节只需分别以这些节点为源点点为源点,重新执行算法即可重新执行算法即可.14562322111(0)(1)(2)(3)(4)(5)图图 基于基于Dijkstra算法生成的最短通路树算法生成的最短通路树图图 依据最短通路树生成节点依据最短通路树生成节点1的路由的路由表表目的节点目的节点 下一站下一站123456-24444目的节点目的节点 下一站下一站12*-24第9讲 路由选择与拥塞控制随机路由选择随机路由选择当分组到达某个
7、节点时就随机地选择一条链路作为转发的路由.当网络中的节点或链路发生故障时,采用随机走动法是最有效的,它使得路由算法具有较好的稳健性.AKLPEMNDCB信源信源信宿信宿0.50.50.20.20.30.30.30.3图图 随机走动算法示意图随机走动算法示意图0.20.20.20.30.30.30.30.30.30.30.3第9讲 路由选择与拥塞控制基于流量的路由选择基于流量的路由选择基本思想既考虑拓扑结构，又兼顾网络负荷；前提：每对结点间平均数据流是相对稳定和可预测的；根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。提前离线（off-line）
8、计算第9讲 路由选择与拥塞控制基于流量的路由选择基于流量的路由选择需要预知的信息网络拓扑结构；通信量矩阵Fij；线路带宽矩阵Cij；路由算法（可能是临时的）0第9讲 路由选择与拥塞控制第9讲 路由选择与拥塞控制第9讲 路由选择与拥塞控制拥塞控制拥塞控制拥塞控制的意义拥塞控制的意义1.意义意义 计算机网络中的链路容量,交换节点中的缓存和处理机等,都是网络的资源.在某段时间内,若对网络中的某一资源的需求超过了该资源所能提供的可用部分,网络的性能就变坏,这种情况称为网络拥塞(Networks Congestion).一般地可以表示成如下形式:网络拥塞的原因网络拥塞的原因:(1)网络中某个节点缓存的容
9、量太小网络中某个节点缓存的容量太小,造成到达该节造成到达该节点的分组因无空间暂存而不得不丢弃点的分组因无空间暂存而不得不丢弃.若将站点的容量扩展容量扩展到很大,所有到达的分组均可在此节点缓存,而由于链路的容量和处理机的速度并未提高,因此分组在队列中的排队时延将会很长排队时延将会很长,结果上层软件只好将它们进行重传(超时重发).所以简单地扩大缓存的存储空间同样会造成网络资源的严重浪费.对资源的需求对资源的需求对资源的需求对资源的需求 可用资源可用资源可用资源可用资源第9讲 路由选择与拥塞控制拥塞控制拥塞控制 图图 当通信量太大时当通信量太大时,会发生拥塞会发生拥塞,性能显著降低性能显著降低.发送
10、的分组发送的分组提交的分组提交的分组子网的子网的最大最大传输容量传输容量完美的完美的理想的理想的拥塞的拥塞的第9讲 路由选择与拥塞控制拥塞控制拥塞控制(2)处理机的处理速度太慢处理机的处理速度太慢 如果路由器的CPU处理速度太慢,以至于不能执行要求它们做的日常工作(缓冲区排队,更新路由表等),使得缓存中的队列变得很长,即使线路的容量还很富裕.(3)低带宽的链路低带宽的链路 由于带宽太低,造成链路上需要传输的分组太多,子网的性能降低.若升级带宽而不提高处理机性能都不会有多大的作用.只升级系统的一部分,而不是整体,往往只会把瓶颈转移到系统其它地方.只有当系统中的所有组件都相互平衡时只有当系统中的所
11、有组件都相互平衡时只有当系统中的所有组件都相互平衡时只有当系统中的所有组件都相互平衡时,网络拥塞才网络拥塞才网络拥塞才网络拥塞才会解决会解决会解决会解决.拥塞会导致恶性循环拥塞会导致恶性循环拥塞会导致恶性循环拥塞会导致恶性循环:如果路由器没有空余缓冲区,它必须丢掉新到来的分组.当扔掉一个分组时,发送该分组的路由器(一个邻居)可能会因为超时而重传此分组,或许会重发多次.由于发送方路由器在未收到确认之前不能扔掉该分组,故接收端的拥塞迫使发送者不能释放在通常情况下已释放了的缓冲区,这样拥塞加重.第9讲 路由选择与拥塞控制拥塞控制拥塞控制2.拥塞控制与流量控制的关系拥塞控制与流量控制的关系 图图 拥塞
12、控制所起的作拥塞控制所起的作用用输入负载输入负载吞吐量吞吐量子网的子网的最大最大传输容量传输容量理想的流理想的流量控制量控制实际的流量实际的流量控制控制0网络吞吐量网络吞吐量=网络负载网络负载吞吐量饱和吞吐量饱和无无流量流量控制控制轻度轻度拥塞拥塞拥塞拥塞死死锁锁当网络负载继续增大到某一数值时,网络的吞吐量就下降为零,网络已无法工作.这就是所谓的“死锁死锁死锁死锁”第9讲 路由选择与拥塞控制拥塞控制拥塞控制 死锁主要有两种:一种是直接死锁一种是直接死锁一种是直接死锁一种是直接死锁,另一种重装死锁另一种重装死锁另一种重装死锁另一种重装死锁.(1)直接死锁:即由互相占用了对方需要的资源而造成的死锁
13、.A分组1分组2分组3分组nB分组1分组2分组3分组m节点节点A的缓存已的缓存已满满节点节点B的缓存已的缓存已满满发送分组发送分组发送分组发送分组发送分组发送分组发送分组发送分组丢掉丢掉A 发来的发来的分组分组丢掉丢掉B 发来的发来的分组分组图图 直接死锁的例直接死锁的例节点节点节点节点A A 保留发给保留发给保留发给保留发给节点节点节点节点B B 的分组的的分组的的分组的的分组的副本副本副本副本,等待节点等待节点等待节点等待节点B B的应答的应答的应答的应答.同样同样同样同样,节节节节点点点点B B 也保留已发也保留已发也保留已发也保留已发送给节点送给节点送给节点送给节点A A 的分的分的分
14、的分组的副本组的副本组的副本组的副本,等待等待等待等待节点节点节点节点A A的应答的应答的应答的应答.谁谁谁谁也无法成功地发也无法成功地发也无法成功地发也无法成功地发出一个分组出一个分组出一个分组出一个分组.第9讲 路由选择与拥塞控制拥塞控制拥塞控制(2)重装死锁:由于路由器的缓存的拥塞而引起的死锁.设三个报文A,B和C经过路由器P,Q和R发往主机H.每一个报文由4个分组构成.又设每个路由器的缓存只能容纳4个分组.路由器路由器P路由器路由器Q路由器路由器RC3C2B4A3B3B2C1B1A4A2A1主机主机H路由器路由器R为报为报文文A 预留预留了了4个个分组的缓存分组的缓存.由由于分组于分组
15、3还未到还未到达达,报文报文A 还不还不能交付给主机能交付给主机H.分组分组A3还还暂暂存存在路由器在路由器P的的缓存中缓存中,它无法它无法转发到路由器转发到路由器Q中中.因为路由器因为路由器Q的缓存已满的缓存已满.路由器路由器Q的缓的缓存中的任何一个存中的任何一个分组都分组都不能向前不能向前转发转发,路由器路由器R的的缓存是为报文缓存是为报文A预留的预留的.图图 重装死锁的重装死锁的例例第9讲 路由选择与拥塞控制拥塞控制拥塞控制在实施拥塞控制在实施拥塞控制时时,拥塞控制算法拥塞控制算法向发送端发送控向发送端发送控制报文制报文,并告诉发并告诉发送端网络已出现送端网络已出现拥塞拥塞,必须放慢发必
16、须放慢发送速率送速率.这和流量这和流量控制控制“很像很像”.第9讲 路由选择与拥塞控制拥塞控制拥塞控制第9讲 路由选择与拥塞控制拥塞控制拥塞控制第9讲 路由选择与拥塞控制拥塞控制拥塞控制第9讲 路由选择与拥塞控制拥塞控制拥塞控制拥塞控制算法拥塞控制算法 根据数据交换方式(虚电路或数据报)的不同,拥塞控制算法采用不同的策略.1.1.面向虚电路的拥塞控制算法面向虚电路的拥塞控制算法源源主机主机目的主机目的主机连接请求连接请求转发转发转发转发转发转发连接请求连接请求连接请求分组中包括连接请求分组中包括:(1)最大分组长度最大分组长度(2)最大传输速率最大传输速率(3)分组序号分组序号(4)传输模式等
17、传输模式等应答分组应答分组转发转发转发转发转发转发应答分组应答分组应答分组对连接分组中应答分组对连接分组中的根据流量说明信息进的根据流量说明信息进行确定它能接受的流量行确定它能接受的流量传输模式传输模式.应答分组经过各路由器应答分组经过各路由器时时,对各路由器所记录对各路由器所记录的发送者流量说明信息的发送者流量说明信息进行确认进行确认.连接请求分组经过各路连接请求分组经过各路由器时由器时,各路由器记录各路由器记录流量说明信息流量说明信息.确认确认 转发转发转发转发转发转发确认确认 图图 虚电路交换的建立虚电路交换的建立第9讲 路由选择与拥塞控制拥塞控制拥塞控制 在数据传输过程中,路由器将根据
18、协商好的传输模式对该链路上的交通进行整形.交通整形交通整形交通整形交通整形(Traffic Shaping)(Traffic Shaping)(Traffic Shaping)(Traffic Shaping)是调整数据传输的平均速率,使数据按照传输模式规定的速率进行传输,尽量避免突发性增大通信量,导致产生拥塞问题.交通整形是对传输速率进行调整,而不是调整流量控制中一次可传送的数据量.交通整形主要采用两种算法:漏桶漏桶(Leaky(Leaky Bucket)Bucket)算法和令牌桶算法和令牌桶(Token Bucket)(Token Bucket)算法算法.(1)(1)漏桶算法漏桶算法第9讲
19、 路由选择与拥塞控制拥塞控制拥塞控制 图图 一个装水漏桶一个装水漏桶 图图 一个分组的漏桶模型一个分组的漏桶模型水龙头水龙头漏桶漏桶水以水以恒定速度恒定速度从孔中流出从孔中流出分组分组无无规则的规则的流流装有分组装有分组的漏桶的漏桶有规则的有规则的流流包含一个漏包含一个漏桶的接口桶的接口网络网络漏漏漏漏桶桶桶桶算法算法算法算法相当于在路由器内部相当于在路由器内部实现了一个有限长度队列实现了一个有限长度队列,路由路由器将以恒定速率从队列中取出分器将以恒定速率从队列中取出分组发送出去组发送出去,而进入路由器的分而进入路由器的分组被排到队列的尾部组被排到队列的尾部,一旦队列一旦队列饱和饱和,新来的分
20、组将被丢弃新来的分组将被丢弃.这种这种算法实际上是一种具有算法实际上是一种具有恒定服务恒定服务时间的单服务器排队系统时间的单服务器排队系统.主机主机系统也可采用该算法来整形分组系统也可采用该算法来整形分组的发送的发送,将上层应用进程不均匀将上层应用进程不均匀的数据流整形成均匀的分组流向的数据流整形成均匀的分组流向网络发送网络发送,平滑了突发的数据流平滑了突发的数据流,大大减少了发生拥塞的机会大大减少了发生拥塞的机会.第9讲 路由选择与拥塞控制拥塞控制拥塞控制(2)(2)令牌桶算法令牌桶算法 令牌桶算法与恒定输出速率的漏桶算法有所不同,它允许一定量的突发数据流.该算法以恒定速算法以恒定速率产生一
21、个个令牌放入桶内率产生一个个令牌放入桶内,每发送一个分组都要每发送一个分组都要获得和消耗一个令牌获得和消耗一个令牌,如果令牌消耗完如果令牌消耗完,则新来的分则新来的分组就要等待生成新令牌或被丢弃组就要等待生成新令牌或被丢弃.由于突发性的输入流往往导致拥塞的发生,因此获得令牌的分组将被快速地输出,使突发性的输入流得到迅速的疏导.在令牌桶算法中,使用一个令牌计数器来计数令牌数量.令牌计数器每隔t时间加1,表示新增加一个令牌;每发送一个分组,令牌计数器减1,表示已消耗一个令牌.当计数第9讲 路由选择与拥塞控制拥塞控制拥塞控制器减至0时,表示令牌已消耗完,不能再发送分组了.这两种交通整形算法既可用于平
22、滑主机向网络发送分组的通信量,也可用于两个路由器之间的交通整形.在在在在ATMATM交换机和交换机和交换机和交换机和RSVPRSVP协议中协议中协议中协议中,就是应用上述的交通整形算就是应用上述的交通整形算就是应用上述的交通整形算就是应用上述的交通整形算法来解决网络拥塞问题的法来解决网络拥塞问题的法来解决网络拥塞问题的法来解决网络拥塞问题的.2.面向数据报的拥塞控制算法面向数据报的拥塞控制算法 数据报服务是一种无连接传输方式。路由器一旦检测到系统可用资源(如链路利用率或队列长度)超过临界值,就会向源主机发送一个抑制分组,警告网络可能发生拥塞.源端主机定期地侦听抑制分组,如果在侦听期内收到抑制分
23、组,则会减少发送给目的主机的数据量.当减至在侦听期第9讲 路由选择与拥塞控制拥塞控制拥塞控制 图图 基于数据报服务的拥塞控制策略基于数据报服务的拥塞控制策略源源主机主机目的主机目的主机警告警告警告警告!抑制分组抑制分组抑制分组抑制分组抑制分组抑制分组抑制分组抑制分组主机收到主机收到抑制抑制分组分组后，逐步后，逐步减少发送给目减少发送给目的主机的分组的主机的分组数量，一般改数量，一般改变发送窗口或变发送窗口或采用漏桶输出采用漏桶输出率等。率等。第9讲 路由选择与拥塞控制拥塞控制拥塞控制 在侦听期内不再收到抑制分组后,可以逐渐增加通信量.主机可以通过调整其发送操作的相关参数(发送窗口或漏桶输出率)
24、来减少通信量,路由器通常采用加权公平队列算法来处理分组排队,检测是否超过临界值,以及何时发送抑制分组.在广域网环境下在广域网环境下在广域网环境下在广域网环境下,采用完全由远程的源端主机减采用完全由远程的源端主机减采用完全由远程的源端主机减采用完全由远程的源端主机减少通信量来缓解拥塞的方法并不是很有效的少通信量来缓解拥塞的方法并不是很有效的少通信量来缓解拥塞的方法并不是很有效的少通信量来缓解拥塞的方法并不是很有效的,因为距离远,反应慢.一种改进的方法是抑制分组途径的各个路由器都要抑制通信量,使通信量得到迅速控制,但中间路由器要提供一定数量的缓冲区空间用中间路由器要提供一定数量的缓冲区空间用中间路
25、由器要提供一定数量的缓冲区空间用中间路由器要提供一定数量的缓冲区空间用于暂存过量的分组于暂存过量的分组于暂存过量的分组于暂存过量的分组.当抑制分组到达源端主机后,由源端主机采取适当措施最终才能使通信第9讲 路由选择与拥塞控制拥塞控制拥塞控制 量降下来.在IP协议中,采用了抑制分组的方法来解决网络拥塞问题.当网络发生严重拥塞时当网络发生严重拥塞时当网络发生严重拥塞时当网络发生严重拥塞时,路由器往往需要采用载荷路由器往往需要采用载荷路由器往往需要采用载荷路由器往往需要采用载荷脱落脱落脱落脱落(Load Shedding),(Load Shedding),(Load Shedding),(Load
26、Shedding),即丢弃分组的方法来疏导交通即丢弃分组的方法来疏导交通即丢弃分组的方法来疏导交通即丢弃分组的方法来疏导交通.路由器一般采用按先来先服务的规则丢弃后到的分组,或按分组优先级的规则丢弃优先级低的分组等.被丢弃的分组要重传.按分组优先级的规则丢弃分组的方按分组优先级的规则丢弃分组的方按分组优先级的规则丢弃分组的方按分组优先级的规则丢弃分组的方法被很多网络系统或协议所采用法被很多网络系统或协议所采用法被很多网络系统或协议所采用法被很多网络系统或协议所采用,如如如如ATMATMATMATM网络网络网络网络,帧中继帧中继帧中继帧中继网络以及网络以及网络以及网络以及IPIPIPIP协议等协议等协议等协议等.在这些网络系统中,分组(或帧)中均设有一个优先级字段,说明在发生拥塞时,路由器将根据分组中所标记的优先级来选择要丢弃有分组.第9讲 路由选择与拥塞控制课堂小结课堂小结掌握下面的术语拥塞控制、流量控制、拥塞避免拥塞控制、流量控制、拥塞避免负载、闭环、开环、反馈负载、闭环、开环、反馈理解流量控制和拥塞控制的关系掌握漏桶算法和令牌桶算法理解静态路由策略第9讲 路由选择与拥塞控制HomeworkHomework预习第六章内容作业：第217页第5题第8题第10题第16题