搜索
网络层之拥塞控制北京大学计算机系严伟yanwei@cs.pku.edu.cn2本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途网络层之拥塞控制●拥塞控制概述●漏桶算法●令牌桶算法3本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●包交换网络是排队网络♦如果包到达和排队的速率超出包被发送的速率，队列的长度就会无限制地增长。输入缓冲输出缓冲5321节点44本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●包交换网络的交换过程♦排在输入缓冲区♦做路由决策♦排队输出统计TDM5本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●拥塞产生♦低带宽的线路♦多个输入去往同一个输出♦路由器的处理能力来不及作路由决策和清空缓冲区●饱和时的处理♦简单地丢弃入境包♦节点对其邻接节点实行某种流量控制6本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●包交换网络中队列的相互作用231♦网络中某一点的拥塞将很快波及到一个区域甚至整个网络。♦必须以控制整个网络交通的方式来使用流量控制工具。6457本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述拥塞控制技术无法达到理论上的理想值。●拥塞的影响提交的负载(发出的包)吞吐量(被传送的包)0.81.0无拥塞控制拥塞控制理想开销1.0要求所有的站点都能知道提交给网络的包的时间和速率当不同节点的队列长度增加时实际吞吐量呈下降趋势。限制每个节点的队列长度以避免吞吐量崩溃。8本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●拥塞的影响.0提交的负载(发出的包)有控制理想无控制平均包的延迟初始时，无控制的策略所导致的延迟比有控制策略低；但无控制策略在网络负载很低时即达到饱和。无论采用什么技术，包的平均延迟随着网络负载接近系统的容量会无限增长。0.819本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●包交换网络中拥塞控制♦发生拥塞的节点向某些或全部源节点发送一个控制包♦依赖于路由信息用链路延迟信息影响新包产生的速率在拥塞期间需要额外的交通延迟变化太快无法有效用于拥塞控制10本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●包交换网络中拥塞控制♦采用端-端的探询(probe)包♦在包中增加拥塞信息在拥塞的相反方向，使源节点减少流向网络的包在拥塞方向，目标端请求源端调整负载加剧网络负担11本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途拥塞控制概述●流量控制与拥塞控制的区别♦流控只与发送者和接收者之间的点-点通信有关1000Gbps1000Gbps超级计算机1Gbps必须进行流量控制12本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途涉及所有主机、路由器(及路由器的存储-转发能力)拥塞控制概述●流量控制与拥塞控制的区别♦拥塞控制是全局问题无需流量控制但要拥塞控制。100Kbps1Mbps1Mbps100Kbps13本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—漏桶算法●通信量整形强迫包以某种可预见性的速率传送。即调整数据传输的平均速率。♦滑动窗口协议：只能限制一次传送的数据量，而无法限制这些数据的传输速率。♦虚电路子网：用户与子网协商一种通信模式用户按协商结果发送包，子网负责传输。此时通信量整形可减少拥塞。适用于实时数据的传输。♦数据报子网：可在传输层的连接中使用通信量整形方法。14本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—漏桶算法●漏桶现象♦从桶底小孔向外漏的速率恒定♦一旦桶空外漏速率为0♦桶一满水从上面溢出任意速率水流匀速水流15本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—漏桶算法接口包含一个漏桶network●漏桶算法将主机用户进程输出的不规则包流转换为输入网络的均速包流♦主机与网络的接口为一个漏桶♦漏桶就是一个有限的内部队列无规律的包流漏桶装包有规律的包流Q：包大小可变怎么办？16本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—漏桶算法●字节计数漏桶算法♦每节拍初始时，计数器为n；♦如队列第一个包的字节数当前计数器的值，则将其发送并修改计数器的值♦如果队列第一个包的字节数当前计数器的值，则停止传输，等待下一节拍的开始。●漏桶算法的缺点不管突发通信量的大小，输出速率保持不变。17本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—漏桶算法●实例1计算机产生包的速率为25MBps；突发数据长度为1MB；网络运行速率为25MBps；路由器平均最佳工作速率≤2MBps；漏桶速率ρ＝2MBps容量C＝1MB突发数据持续时间25MB/s,40ms100ms200ms300ms2MB/s,500ms100ms200ms300ms400ms500ms漏桶输出速率18本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—令牌桶算法●令牌桶算法无规律的包流漏桶中装令牌每隔△T秒生成一个令牌networknetwork19本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—令牌桶算法●与漏桶算法的区别♦令牌桶算法可积累发送数♦桶满时会丢失令牌而不会丢失包允许多达n个包的突发通信20本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—令牌桶算法●基本令牌桶算法的实现♦令牌以包为单位设置一计数器每隔△t加1每发送一包减1当计数器为0时禁止发送包♦令牌代表k个字节每隔△t加k，每发送一个包减去该包长度。21本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—令牌桶算法●实例2令牌桶容量C=250KB；令牌到达速率ρ=2MBps；网络最大传输率M=25MBps；假设：突发数据长为1MB，到达时令牌桶已满。设：突发时间为S；令牌到达速率ρ；突发数据最大输出为C＋ρ·SC＋ρ·S=M·SS=CM-ρ22本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—令牌桶算法当C=250K；M=25MBps；ρ=2MBps；S=250K/230000K≈10.8ms在S秒内以25MBps的速率突发一部分；其余的数据只能以2MBps的速率发送；T=1-S*25MBps2MBps=364ms100ms200ms300ms400ms500ms25MB/s,11ms2MB/s,364ms突发数据持续时间漏桶输出速率23本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—流说明●流说明(flowspecification)：说明通信模式♦通信量模式♦应用所需服务质量●基本原理♦连接建立/发送数据报前源端向子网提交流说明请求特定服务；♦子网可接受、拒绝或提出一种折中意见；♦一旦发送者与子网达成共识再征求接收者的意见；24本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—流说明●输入特性♦最大包(B)♦令牌桶速率(B/s)♦令牌桶容量(B)♦最大传输速率(B/s)说明了包的最大尺寸如果桶输出速率为rBps，桶的容量为bB，则在任意时间△t内可传送的最大字节数为：b+r·△t说明了主机产生数据的最高速率25本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途通信量整形—流说明●应用程序所需的服务♦丢失敏感性(B)♦丢失间隔(us)♦突发丢失敏感性(P)♦最小注意延迟(us)♦最大延迟变化(us)♦质量保证说明了可接受的丢失率说明了可忍受连续丢多少包超出这个值的延迟将引起应用程序注意说明端-端传输延迟的变化说明上述条件是否一定要满足26本幻灯片未授权除北京大学以外的任何单位或个人用作任何用途