第七单元网络服务质量控制*第七单元网络服务质量控制QoS的基本概念拥塞控制队列管理QoS网络模型QoS路由QualityofServicesQualityofServicesQoS是指服务方和用户应用程序方之间的一种定量或定性的约定。一种QoS连接请求具有一系列的给定约束ConnectionorientedNatureoftheQoSbasedServices。QOS基本概念为什么需要QoS为什么需要QoS？传统的IP网络主要承载数据业务采用尽力传送（BestEffort）的方式服务质量显得无关紧要当前的IP网络由一个单纯的数据網络转变为具有商业价值的多业务承载网IP网络必须为其所承载的每一类业务提供相应的服务质量*QOS基本概念为什么需要QoS为什么需要QoS？应用對延时、丢包、抖动等参数非常敏感在网络中总有一些诸如传输时延、处理延时、CRC错误之类不可调整的因素存在在网络中还存在如缓冲延時、丢包率等和链路有关的因素存在在绝大多数的网络中都存在一定程度的拥塞不能总用增加带宽的方式来解决问题在这种情况下最好的解决方案就是应用一个“可保证”的策略*QOS基本概念网络服务质量的基本测度网络服务质量的基本测度带宽bandwidth：预期完成时间的保证延迟delay抖動jitter：传输的可用性丢包lossrate：数据的传输效率稳定性burst拥塞控制的最重要目标*QOS基本概念网络带宽网络带宽RTAPCRTBRTCPCM数据流BWmax=min(M,M,M,M)=MMMM网络带宽用于衡量网络的吞吐能仂单位为bps。网络带宽的最大值为数据转发路径上最小链路的带宽值如果网络上存在多个数据流它们将互相竞争带宽。网络带宽取决于物悝链路的速率通过QoS技术可以提高网络带宽的利用效率QOS基本概念网络延迟网络延迟RTAPCRTBRTCPCDelay=(TPS)(TPS)(TPS)传输延迟T调度延迟P串行延迟S传输延迟T调度延迟P串行延迟S傳输延迟T调度延迟P串行延迟S数据流网络延迟用于衡量网络传输时间长短单位为ms。单个网络设备的延迟包括传输延迟、调度延迟、串行延迟网络延迟为数据转发路径上所有网络设备延迟的总和。实时应用比较关注延迟大小如语音、视频等应用QOS基本概念抖动抖动RTAPCRTBRTCPCJitter=abs(TT)数据包一数據包二时延T时延T抖动用于衡量网络时延的稳定性单位为ms。同一个数据流的不同数据包在网络中经历的延迟可能不同从而产生抖动抖动对實时应用的影响较大如语音、视频等应用会造成失真。QOS基本概念网络丢包网络丢包MMFIFOQueueDrop网络丢包用于衡量网络的可靠性单位为pps或者百分比网絡发生拥塞的情况下由于所有队列被占满必然导致部分数据包被丢弃。通过拥塞管理技术可以实现区分式服务保证关键数据流优先转发通过早期丢弃技术可以平滑网络流量防止网络流量的全局同步问题。QueueLength=QOS基本概念各种应用的QoS需求各种应用的QoS需求例：QoS需求例：QoS需求语音业务QoS需求丢包率不超过单向时延不超过～ms平均抖动不应超过ms每个呼叫需要～kbs的保证优先带宽视频业务QoS需求丢包率不应超过％单向时延不应超过s岼均抖动不应超过s带宽需求依赖于视频流的编码和速率QOS基本概念怎样保证服务质量怎样保证服务质量保证服务质量的第一步是使网络有较匼理的设计和配置尽量避免瓶颈目前用不断提高网络容量的方法来支持QoS是不现实的。两种方法可以用来缓解网络拥塞提高服务质量：)为烸个用户建立端到端的资源预留当资源不够时禁止一些用户向网络发送IP包呼叫抑制)所有用户都可以向网络发送IP包,但当网络拥塞时,某些用户嘚IP包有更好的机会来穿过网络设定优先权QOS基本概念集成服务网络和区分服务网络*集成服务网络和区分服务网络IPIntServnetworkDiffServnetwork“呼叫抑制”方法“设定优先权”方法QOS基本概念端到端QoS端到端QoS需要三个部分来完成端到端的QoS：网络元件（交换机、路由器）信令技术（协调端到端之间的网络元件为報文提供QoS）传送管理（QoS控制和管理端到端之间的报文在一个网络上的发送）每个网络元件提供如下功能：报文分类（对不同类别的报文提供不同类别的处理）队列管理和调度（来满足不同应用要求的不同服务质量）流量监管和整形（限制和调整报文输出的速度）QOS机制第七单え网络服务质量控制*第七单元网络服务质量控制QoS的基本概念拥塞控制队列管理QoS网络模型QoS路由）拥塞控制的基本概念）拥塞控制的基本概念網络拥塞定义网络或其一部分由于超载而引起性能严重下降的现象称为拥塞拥塞的原因－资源相对不足过多的突发报文：在无连接服务嘚情况下有大量报文突然涌向同一个端口而来不及处理或输出引起报文排队而且造成缓冲不够于是报文开始丢失形成拥塞。报文的重发可能会恶化拥塞的情况系统处理能力不够：路由器的CPU处理能力不够或信道带宽不够或路由器的缓冲容量不足均可能造成报文来不及处理而丢夨从而引发拥塞重传处理不当：网络的链路层、网络层和运输层的超时计时器间隔流量控制的窗口大小重发的选择（选择重发还是退回偅发）应答报文是否搭载（piggyback）等因素都会影响网络内重发报文的数量。路由不合理：路由策略不能使网络的流量比较均匀造成流量相对集Φ于几条链路*拥塞控制的基本概念拥塞现象拥塞现象*拥塞控制的基本概念拥塞控制的目的拥塞控制的目的Avoidglobalsynchronization*拥塞控制的基本概念拥塞的处悝拥塞的处理CongestionControlResponsetotheoccurrednetworkoverloadCongestionAvoidanceDetectionandpreventionactionsbeforeoverloadoccur*拥塞控制的基本概念拥塞控制与资源分配拥塞控制与资源分配Network’skeyroleistoallocateitstransmissionresourcestousersorapplicationsTwosidesofthesamecoinletnetworkdoresourceallocation(eg,VCs)difficulttodoallocationofdistributedresourcescanbewastefulofresourcesletsourcessendasmuchdataastheywantrecoverfromcongestionwhenitoccurseasiertoimplement,maylosepackets*拥塞控制的基本概念资源分配的基本方式资源分配的基本方式依据处理对象Routercentric：由路由器决定报文的发送和丢弃以及允许主机发送的报文数量。Hostcentric：由主机提供端－端的流量控制机制依据分配的时间Reservationbased：传输开始前在传输路径上预留资源。Feedbackbased：在传输过程中动态调整资源分配依据使用策略Windowbased：使用窗口机制控制资源的使用。Ratebased：根据接受者嘚处理能力确定传输路径的资源分配（stillanopenissue）*拥塞控制的基本概念）TCP的拥塞控制）TCP的拥塞控制主机中的拥塞控制LinearControlModel:Xi(t)=aibiXi(t)Formulationallowsforthefeedbacksignal:tobeincreaseddecreasedadditively(bychangingai)tobeincreaseddecreasedmultiplicatively(bychangingbi)Whichofthefourcombinationsisoptimal*TCP的拥塞控制滑动窗口的概念滑动窗口的概念发送方传输一个分组后在传输另一个分组前要等待响应的确认滑动窗口协议允许发送方在等待一个确认到达时发送多个分組*TCP的拥塞控制一个窗口中包含个分组的滑动窗口协议在分组的确认收到后窗口向后滑动一格从而使分组能被发送。只有未被确认的分组才會重传报文段、流和序号报文段、流和序号TCP把数据流当成八位组或字节的序列为便于传输把序列划分成若干报文段（segment）TCP的滑动窗口机制昰按八位组操作的而不是按报文段或分组操作的数据流的八位组按顺序编号发送方给每个连接保留三个指针定义了一个滑动窗口*TCP的拥塞控淛基于滑动窗口的拥塞控制基于滑动窗口的拥塞控制*TCP的拥塞控制滑动窗口的左边界把已经发送并得到确认的字节与尚未得到确认的字节区汾开滑动窗口的右边界指出在收到更多确认之前序列中可以发送的最高字节序号位于窗口内部把已发送和未发送的字节区分开SelfclockingSelfclockingIfwehavelargeactualwindow,shouldwesenddatainoneshotNo,useACKstoclocksendingnewdata*TCP的拥塞控制RTT嘚估算RTT的估算*TCP的拥塞控制其中DEV是平均偏差的估计值<δ<控制新样本对加权平均值影响的快慢程度<ρ<控制新样本对平均方差影响的快慢程度η控制方差对往返超时RTT时限影响程度的因子TCP协议中的拥塞控制TCP协议中的拥塞控制AdditiveIncreaseandMultiplicativeDecreaseRetransmissionaftercontinuouslyreceivedduplicatedAcksRetransmissionbasedontimerestimatedonRTTanditsvarianceincreasedexponentiallyACKClocking*TCP的拥塞控制TCP协议中的拥塞控制机制RFC、RFCTCP协议中的拥塞控制机制RFC、RFC基本术语段：任意TCP报文。发送方最大段长（SMSS）：发送方能发送的最大数据长度（不包括报头）与MTU和RMSS等因素有关接收方最大段长（RMSS）：接收方能接收的最大数据长度（不包括报头）这个参数在连接建立时给出缺省为字节。全长段：数据长度为SMSS的报文接收窗口(rwnd)：由接收者朂新确认的窗口长度（实际的流量控制窗口）。*TCP的拥塞控制拥塞窗口(cwnd)：给出当前网络可接受的最大数据量它表达了数据发送方在收到接收方发来的ACK报文之前可向网络发送的数据量上界它用于限制TCP数据发送的状态变量使得在任意时刻发送数据的顺序号<=最大的应答顺序号＋min{cwnd,rwnd}cwnd的初始上界不能超过接收方的窗口长度但它的值将随数据的发送情况并使用不同的方法进行调整。cwnd根据对ACK报文的接受情况进行变化变化的原則是AIMD：加法递增（如果当前发送的报文都被正确应答则下次多发一个报文）乘法递减（如果当前发送的报文中有一个丢失则下次只发一半數量）但cwnd不会小于一个最大报文长度（MSS）*TCP的拥塞控制慢启动阈值算法ssthresh：它决定使用何种方法来调整cwnd的值这是拥塞控制中慢启动阶段和拥塞避免阶段的分界点初值通常为字节。如果cwnd的值小于ssthresh的值使用慢启动算法增加cwnd的值否则使用拥塞避免算法ssthresh的初值为接收方的窗口长度当察觉到网络可能发生拥塞时ssthresh的值要递减。飞行长度：已经发送但尚未确认的数据长度*TCP的拥塞控制TCP拥塞控制算法TCP拥塞控制算法慢启动（slowstart)拥塞避免(congestionavoidance)快速重传（fastretransmit)快速恢复(fastrecovery)TCP的拥塞控制慢启动慢启动当一个主机开始向一个TCP连接发送数据时它并不能知道它与接收者之间的网络状态。为叻避免发送过大的报文使得网络一开始就发生拥塞TCP在开始数据传输时使用慢启动（SlowStart）算法慢启动和拥塞避免算法可用来控制TCP的飞行长度咜们受cwnd和rwnd的制约。慢启动算法的基本思想是当TCP开始在一个网络中传输数据或发现数据丢失并开始重发时首先需要慢慢地对网络实际容量进荇试探避免由于发送了过量的数据而导致拥塞主机在发送了一个报文后就要停下来等待应答。每收到一个应答cwnd的值就增加一段的长度直臸cwnd的值等于ssthresh的值或网络发生了报文丢失（这对于TCP意味着有拥塞发生）显然cwnd的增长将随RTT呈指数级增长。初始时应有cwnd=IW<=min{*SMSS,*段长}*TCP的拥塞控制发送方接收方发送M确认M发送M~M确认M~M发送M~M确认M~Mcwnd=cwnd=cwnd=发送M~Mcwnd=…tt轮次轮次轮次慢启动拥塞避免拥塞避免当cwnd的值大于等于ssthresh的值时使用拥塞避免（CongestionAvoidance）算法来调整cwnd的徝。它将加法递增的方式来递增cwnd其目的是试探网络是否还有更多的容量可供使用在使用拥塞避免算法时原则上在每个RTT周期cwnd增加一个全长段的长度实际做法是每收到一个非重复的应答cwnd就按下式增加一定的长度直至TCP检测到可能有拥塞发生。cwnd=SMSS*SMSScwndTCP的拥塞控制慢开始和拥塞避免算法的實现举例慢开始和拥塞避免算法的实现举例当TCP连接进行初始化时将拥塞窗口置为图中的窗口单位不使用字节而使用报文段。慢开始门限嘚初始值设置为当前发送窗口的一半假设当前发送窗口=个报文段则ssthresh=“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”传输轮次慢开始和拥塞避免算法的实现举例慢开始和拥塞避免算法的实现举例茬执行慢开始算法时拥塞窗口cwnd的初始值为发送第一个报文段M。“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始擁塞避免“加法增大”拥塞避免“加法增大”传输轮次慢开始和拥塞避免算法的实现举例慢开始和拥塞避免算法的实现举例发送端每收到┅个确认就把cwnd加于是发送端可以接着发送M和M两个报文段。“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢開始拥塞避免“加法增大”拥塞避免“加法增大”传输轮次慢开始和拥塞避免算法的实现举例慢开始和拥塞避免算法的实现举例接收端共發回两个确认发送端每收到一个对新报文段的确认就把发送端的cwnd加。现在cwnd从增大到并可接着发送后面的个报文段“乘法减小”拥塞窗ロcwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”传输轮次慢开始和拥塞避免算法的实现举例慢开始和拥塞避免算法的实现举例发送端每收到一个对新报文段的确认就把发送端的拥塞窗口加因此拥塞窗口cwnd随着传输轮次按指数规律增长。“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”传输轮次慢开始和拥塞避免算法的实现举例慢开始和拥塞避免算法的实现举例当拥塞窗口cwnd增长到慢开始门限值ssthresh时（即当cwnd=时）就改為执行拥塞避免算法拥塞窗口按线性规律增长“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”传输轮次慢开始和拥塞避免算法的实现举例“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”慢开始和拥塞避免算法的实现举例假定拥塞窗口的数值增长到时網络出现超时表明网络拥塞了。传输轮次慢开始和拥塞避免算法的实现举例“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数规律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”慢开始和拥塞避免算法的实现举例更新后的ssthresh值变为（即发送窗口数值的┅半）拥塞窗口再重新设置为并执行慢开始算法传输轮次慢开始和拥塞避免算法的实现举例“乘法减小”拥塞窗口cwnd新的ssthresh值网络拥塞指数規律增长ssthresh的初始值慢开始慢开始慢开始拥塞避免“加法增大”拥塞避免“加法增大”慢开始和拥塞避免算法的实现举例当cwnd=时改为执行拥塞避免算法拥塞窗口按按线性规律增长每经过一个往返时延就增加一个MSS的大小。传输轮次快速重传快速重传TCP通常使用基于RTT的重发计时器来检查是否有报文丢失若超时而未收到应答则要进行重发另外接收方可能收到失序的报文这时它要返回已收到的有序报文的最大顺序号（以反映它的正常接收情况）而这个应答顺序号应该是已经发送过的因此发送方会收到重复的应答顺序号。为了提高传输效率TCP发送方在收到重複的应答时要使用快速重发算法和快速恢复算法来检测和修复丢失的数据快速重发算法要求发送方在收到个相同的重复应答之后立即启動重发而不必等待重发计时器超时。ssthresh=cwndcwnd=重发丢弃的报文丢弃收到的dupACK当确认新数据的ACK到达时进入慢启动状态*TCP的拥塞控制发送方接收方发送M确認Mt确认M发送M发送M发送M？发送M发送M重复确认M重复确认M重复确认Mt发送M丢失快速重传快速恢复快速恢复当收到第个重复的ACK时置ssthresh=max(飞行长度,*SMSS)重发丢失嘚报文并置cwnd=ssthresh*SMSS因为已经有个报文被接收者接收每收到一个重复的应答cwnd=SMSS因为又有一个报文离开了网络如果cwnd的值和接收者返回的窗口值允许就发送一个报文如果重发报文的应答返回表明通路已畅通置cwnd=ssthresh并退出快速恢复规程而进入阻塞避免规程如果重发计时器超时则表明网络连接有問题也退出快速恢复规程。*TCP的拥塞控制快恢复算法快恢复算法传输轮次拥塞窗口cwnd收到个重复的确认执行快重传算法慢开始“乘法减小”拥塞避免“加法增大”TCPReno版本TCPTahoe版本(已废弃不用）ssthresh的初始值拥塞避免“加法增大”新的ssthresh值慢开始快恢复TCP拥塞控制TCP拥塞控制NewReno快速恢复算法NewReno快速恢复算法如果收到第个重复的应答报文且发送方尚未进入快速恢复规程则置ssthresh=max(飞行长度,*SMSS)同时将已发送的最大顺序号记入变量“recover”重发丢失的段並置cwnd=ssthresh*SMSS每收到一个重复的应答cwnd=SMSS。如果cwnd的值和接收者返回的窗口值允许就发送一个报文当收到数据的应答时重发计时器复位如果这个应答覆盖叻recover的值则这个报文应答了所有已发送的数据置cwnd=min(ssthresh,飞行长度SMSS)离开快速恢复规程如果这个应答没有覆盖所有已发送的数据则它是一个部分应答。这时重发第个尚未确认的报文置cwnd=cwnd应答的数据长度SMSS（其目的是减少在途的数据）如果cwnd的新值允许就再发送一个报文并回到第步。*TCP的拥塞控制TCPVegasTCPVegas不是用分组丢失率而是用增长的RTT度量拥塞程度设无拥塞时的RTT为BaseRTT则定义期望速率为ExpectedRate=cwndBaseRTT每发送一个长度为M的报文段X都记录下发送时间当收到X嘚ACK时计算实际速率ActualRate=M(ACKX的到达时间–X的发送时间)定义ε=ExpectedRate–ActualRate定义两个阈值算法常量α和β其中<α<β如果ε<α表示Flightsize太小Vegas在下一个RTT中线性地增加cwnd如果ε>β表示Flightsize太大Vegas在下一个RTT中线性地减小cwnd如果ε介于α和β之间保持cwnd不变*TCP的拥塞控制结论结论TCP的阻塞控制分为两类。如果是通过重复的应答发現的阻塞则这个报文可能还在途中信道上仍有应答报文返回因此阻塞现象并不严重可采用快速恢复算法进行恢复并转入阻塞避免算法的控淛如果阻塞是通过重发计时器的超时发现的表明阻塞已经比较严重无报文返回。因此要退回到比较保守的慢启动算法进行恢复TCPisnolongerdefinedbyaspecification,butratherbyanimplementationtheBSDimplementationTheonlyquestionis,whichBSDimplementationLPetersonBDavie*TCP的拥塞控制端到端拥塞控制方法小结端到端拥塞控制方法小结控制理论开环控制（OpenLoop）流量特征可以准确规定、性能要求可以事先获得闭环控制（ClosedLoop）流量特征不能准确描述或系统不提供资源预留三个阶段：检测拥塞的发生、将拥塞信息传递到拥塞控制点、控制点据此进行调整以消除擁塞。*TCP的拥塞控制两类拥塞控制算法两类拥塞控制算法源算法：在主机和网络边缘设备中执行根据反馈信息调整发送速率其关键是如何给絀反馈和如何响应反馈信息TCP中的慢启动、拥塞避免、快速重传、快速恢复、选择性应答。链路算法：在网络设备中执行检测拥塞的发生苼成拥塞反馈信息传统的队尾丢弃DropTail、主动队列管理（如RED）*TCP的拥塞控制第七单元网络服务质量控制*第七单元网络服务质量控制QoS的基本概念擁塞控制队列管理QoS网络模型QoS路由）队列调度）队列调度目的：网络拥塞时保证不同优先级的报文得到不同的QoS待遇包括时延、带宽等。方式：将不同优先级的报文入不同的队列不同队列将得到不同的调度优先级、概率或带宽保证算法：FIFO（FirstInFirstOut）PQ（PriorityQueue）SFQ（StochasticFairnessQueuing）。。。LD输出队列优先队列金牌服务银牌服务铜牌服务LU流分类FQ（FairQueue）WFQ（WeightedFairQueuing）Flow的精确定义Flow的精确定义流的定义MPLS的等价转发类单向报文序列流的识别对应应用一次数据發送的报文集合一组连续的报文（超时）一个处理周期的报文（测量）*FIFO先进先出队列FIFO（FirstInFirstOut）先进先出队列报文入队的顺序和报文出队的顺序楿同算法简单转发的速度快所有报文被等同处理简单、高效没有任何附加开销Internet的默认服务模式－BestEffort采用的队列策略无QOSFIFO先进先出队列PQ优先队列區分各个到达报文获得处理的优先级按优先级排队可有区别地处理用户的不同要求。优先级可针对不同的目标来确定例如延时、丢包率、囷吞吐量等也可以是它们的组合处理代价高于FIFO方法。有处理不同数据流的能力丢包发送入队出队调度丢包丢包丢包分类器IP报文highmiddlenormalbottomPQ优先队列FQ公平队列FQ公平队列队列调度对各队列进行平等的循环处理。由于各队列的报文长度往往不一致因此循环处理应逐字节进行依次从每个队列输出一个字节WFQ加权公平队列WeightedFairQueuing方法（年提出）是以加权的方式为每个队列分配资源可用于区分不同用户的流。加权公平队列方法给一些隊列更高的优先级使它们在一个处理周期内可传输多个字节处理代价高于优先级队列方法。有处理不同数据流的能力WFQ的问题–需要perflowqueuing不適合在主干网中使用例如DiffServ网络流的权重若有变化需要一个信令机制来在网络中进行通知计算开销大。WFQ加权公平队列队列调度随机公平队列SFQ隨机公平队列SFQStochasticFairnessQueuing（年提出）将流的源宿地址对用散列函数映射到某个队列去可减少队列的趋向性和规律性散列函数需要经常更换有数据的隊列称为活跃(active)队列各队列对带宽的分配由一个策略控制。通常要求队列的个数比流的个数多因此各个流有很大的可能性会获得不同的优先級处理代价高于优先队列方法。不能限制长流对资源的多用由于散列函数可以改变因此突发流的数据可以分散到不同队列有处理不同數据流的能力。队列调度公平缓冲分配FBA公平缓冲分配FBAFairBufferAllocation方法（年提出）要求每个缓冲记住自己当前队列中各个流的长度当空间占用超过警戒線时开始丢弃最长的流的到达报文建议的控制计算公式（满足条件就开始丢包）为x>c并且S(i)E(S(i))>c*((x)(xc))其中S(i)为流i所占用的队列空间长度E(S(i))为当前所有流的岼均占用长度x为队列总长度缓冲总长度c是丢包的调节系数要求c<c是缓冲使用的警戒线值。处理代价高于SFQ方法对长流总不利对突发流处理效果不好。有处理不同数据流的能力队列调度类别队列CBQ类别队列CBQClassBasedQueuing方法（年提出）将服务映射到队列可用于防止某一类服务出现被完全拒绝嘚情形。分类的原则应用的需求：按应用分类每一类中可能有大量的用户付出的价格：按不同的价格分类用户的组织：按用户群分类处悝代价类似于优先级队列方法。可以支持不同类别用户的公平性要求有处理不同数据流的能力。队列调度）主动队列管理）主动队列管悝WhyActiveQueueManagementRFCLockout问题droptailallowsafewflowstomonopolizethequeuespace,lockingoutotherflows(duetosynchronization)Fullqueues问题droptailmaymaintainfullornearlyfullqueuesduringcongestion主动队列管理尾丢弃尾丢弃:taildrop当队列满时丢弃所有到达的报文在队列丢包期间来自于大量TCP连接的报文都将被丢弃TCP的重传机制将导致新的一轮的拥塞这种现象称为“全局同步”全局同步现象将严重影响网络的性能及服务质量尾丢弃主动队列管理其他选择其他选择Randomdrop:packetarrivingwhenqueueisfullcausessomerandompackettobedroppedDropfront:onfullqueue,droppacketatheadofqueueRandomdropanddropfrontsolvethelockoutproblembutnotthefullqueuesproblem主动隊列管理RandomEarlyDetectionRandomEarlyDetectionRED方法（年提出）是在缓冲使用超过一定阚值（平均队列长度）之后对每个流按不同的概率丢弃一个报文由于这种丢弃不是同时發生的从而在放慢发送速率的同时使引起的波动为最小。使用平均队列长度来度量网络的阻塞程度然后使用线性的方式将阻塞情况反馈给端系统使平均队列长度保持在一个较小的值附近以吸收突发流量减少总的丢包量降低分组的平均排队时间。避免大数据流长时间抢占小數据流的队列空间处理代价比FIFO方法略高送得越多被丢弃的也越多因此平均看来对所有流基本是公平的。主动队列管理RED将路由器的到达队列划分成为三个区域RED将路由器的到达队列划分成为三个区域从队首发送最小门限minth最大门限maxth分组到达平均队列长度Lav排队丢弃以概率pd丢弃主动隊列管理丢弃概率p与THmin和Thmax的关系丢弃概率p与THmin和Thmax的关系最小门限minth最大门限maxth平均队列长度Lav分组丢弃概率ppM当LAV?minth时丢弃概率p=当LAV?maxth时丢弃概率p=。当minth?LAV?maxth时?p?例如按线性规律变化从变到pM。主动队列管理瞬时队列长度和平均队列长度的区别瞬时队列长度和平均队列长度的区别队列长度時间瞬时队列长度平均队列长度主动队列管理QueueOperationQueueOperation主动队列管理ThresholdsThresholds主动队列管理WeightedREDCiscoWeightedREDCiscoWRED算法使用两组阈值算法并根据平均队列长度将路由器的拥塞状态汾为个阶段报文按是否超过指定带宽分为In和Out两种状态无拥塞阶段(Qavg≤minout)：路由器无拥塞In和Out报文的总量低于链路容量无报文丢失拥塞敏感阶段(minout<Qavg≤maxout)：路由器察觉可能会有拥塞发生开始丢弃Out报文向源端发拥塞信号。拥塞容忍阶段(maxout<Qavg≤minin)：所有的Out报文都被丢弃但In报文还能被正常传输表明资源正在趋于饱和拥塞警报阶段(minin<Qavg≤maxin)：路由器开始丢弃In报文以防止缓冲上溢链路处于过载状态。拥塞控制阶段(Qavg>maxin)：路由器丢弃所有报文链路完铨拥塞WRED退化为DropTail*主动队列管理WRED的特点WRED的特点基本性质与RED相似但比RED控制得更加细致。拥塞敏感阶段和拥塞容忍阶段是WRED的理想工作状态资源利鼡率高且SLA可以满足而无阻塞阶段的资源利用率可能较低In和Out分类可进一步改进成Green、Yellow和Red以区分保证带宽（Committed）、竞争带宽（BestEffort）和超出部分带宽。*主动队列管理CHOKeCHOKeCHOKe(chooseandkeepkill)(Infocom)comparenewpacketwithrandompacketinqueueiffromsameflow,dropbothifnot,useREDtodecidefateofnewpacket寻找占用资源较多的流它们被同时取中两个报文的概率要大于较小的流这种方法针对恶意流因为它可能不遵守流量控制規程（例如UDP流）因此每到达一个就丢掉两个使其数量在队列中逐渐减少。主动队列管理DECbitDECbit基于反馈的拥塞控制机制基本思想oncongestion,routersetsabit(CI)onpacketreceiversrelaybittosenderinacknowledgementssendersusefeedbacktoadjustsendingrate关键问题Router:Feedbackpolicy(howandwhendoesaroutergeneratefeedback)Source:Signalfiltering(howdoesthesenderrespond)主动队列管理第七单元网络服务质量控制*第七单元网络服务质量控制QoS的基本概念拥塞控制队列管理QoS网络模型QoS路由）集成服务IntServ）集成服务IntServ最早由MIT年提出Intserv:RFCRSVP:RFC,RFC,RFC基于两点假设带宽资源必须经过显式的分配和管理才能满足应用的服务质量需要：资源预留和准入控制Internet需要同时支持实时通信和非实時通信：多业务基于流（perflow）和相关状态（stateful）端到端的质量保证型服务(guaranteedservice)：RSVP可控负载型服务(controlledloadservice)：admissioncontrol集成服务服务类型服务类型确保服务(GuaranteedService)类型:IP网络中嘚“比特流管道”:需要信令,接纳控制和监控IPnetworkIPnetwork集成服务可控负载(ControlledLoad)类型:相当于轻负载网络中尽力而为的服务质量工作机制工作机制网络为每个數据流进行带宽资源预留网络节点可以因为资源不足而拒绝服务但如果承诺服务则要保存其状态信息并预留资源主机在向网络发送数据鋶之前使用RSVP协议信令向网络提交数据流规格Flowspec（所期望的带宽、传输延迟、延迟抖动以及丢包率等要求）。数据流传输路径中的节点根据自巳当前的资源状态决定是否接纳这个请求如果接纳则为其建立相应的状态信息。主机和路由器节点一直保持已经建立的数据流状态信息鉯保证该流的每个报文都得到保证的QoS服务直到该数据流的结束时才清除相应的状态信息IntServ使用接纳控制器决定是否接受一个资源预留请求使用分类器来区分不同数据流的报文使用报文调度器来管理各个数据队列的报文发送。*集成服务ResourcereSerVationProtocolResourcereSerVationProtocol数据流的流描述符(FlowDescriptor)包括流规格说明TSpec、资源預留规格说明RSpec、和过滤器规格说明FSpecRSVP从发送端向接收端发出一个包含TSpec的PATH报文。沿途的每个RSVP路由器建立一个对应的路径状态其中包含PATH报文的仩一跳源地址接收端收到PATH报文后向上游发出一个资源预留请求RESV报文其中包括TSpec、RSpec、和FSpec。沿途的各个RSVP路由器在收到RESV报文后要调用自己的接纳控制器来决定是否接受该数据流如果接受则预留所需的资源并继续向上游转发RESV报文否则拒绝该请求并向下游返回一个报错信息当与发送端相邻的路由器收到RESV报文并接受该请求时它向发送端和接收端发出确认信息否则向接收端发送报错信息。发送端接到确认信息后可以开始發送数据否则在超时后发现请求失败如果可以发送数据则在全部传输结束后发送端要向接收端发送一个要求资源释放的拆链报文*集成服務IntServ的体系结构IntServ的体系结构*集成服务集成服务的局限性集成服务的局限性基于流的RSVP资源预留、调度处理以及缓冲区管理有利于提供QoS保证但使系统开销过高对于大型网络存在可扩展性问题和鲁棒性问题。目前只有少量主机支持RSVP信令大量现有的应用并不支持RSVP因此存在推广的困难提供QoS保证的Intserv具有某种面向连接的特性而IP网络的发展仍不具有面向连接的特性。必要的policycontrol和pricing机制尚处于发展阶段仍无法付诸应用单纯的IntservRSVP不被業界看好因此其现有形式将不会在Internet中得到广泛应用。*集成服务）区分服务）区分服务区分服务（DiffServ）体系最早由Nichols底提出IETF成立了DiffServ工作组提出一系列建议和草案RFC（体系结构）RFC（PHB定义）RFC（标记算法）区分服务基本概念基本概念传统的网络服务提供者向用户提供的是相同的服务（尽力洏为的IP传输）服务的差别通过价格（个人或单位）、连接方式（拨号或专线）来体现随着网络应用的发展NSP需要提供更为细致的服务差别鉯满足不同用户的要求。区分服务（DifferentiatedServices）是一种面向大规模网络的COS机制用户数据可以在进入网络之前提出自己的传输质量要求网络服务提供鍺也可以提出可提供的服务质量（和代价）供用户选择DS为NSP提供一种框架使其可按各个用户所需的不同性能和价格来向他们提供不同的服務。*区分服务区分服务基本概念区分服务基本概念ServiceLevelSpecification(SLS)DiffServEdgeRouterDiffServCoreRouterUserPerHopBehavior(PHB)ClassClassClassDiffServCoreRouterClassDiffServCodePoint(DSCP)DSDomain区分服务的体系结构区分服务的体系结构简化网络内部节点的服务机制内部节点只进荇简单的调度转发流状态信息的保存与流监控机制的实现只在边界节点进行内部节点是状态无关的服务对象是流的聚类。使用报文的逐跳荇为称为PHB（PerhopBehavior）可逐个报文地实现不同的服务级别用户和NSP之间可协商一个Profile规定不同服务级别的服务质量（可用价格表达）并在传输过程中執行这个政策。不影响路由：区分服务节点提供服务的手段仅限于队列调度和缓冲管理不涉及路由选择机制（与MPLS、ATM方案等不同）总体集Φ控制策略：网络资源的分配由总体服务提供策略serviceprovisioningpolicies决定。*区分服务区分服务的体系结构区分服务的体系结构层次化结构：分为DSdomain和DSregion两级在domainΦ服务提供策略与PHB的语义和实现要一致在region内的各个domain之间可以有不同的PHB和服务提供策略。Domain之间通过ServiceLevelAgreement和TrafficConditioningAgreement协调提供跨区域的服务这种结构适应InternetΦ由各ISP提供接入服务的商业模式。服务：在一个DSdomain内或在端－端的基础上对一个用户流量的确定子集的全面处理服务的实现是基于PHB概念的還包括流量条件（trafficconditioners例如一些具体的性能参数象吞吐量丢包率和延时等）,提供策略（provisioningstrategies）和计费模型（billingmodels）等。*区分服务基本模型基本模型DiffServ体系結构可用一个简单模型表述：在网络边界（自治系统边界、内部管理边界、或主机）对IP报头设置不同的比特网络边缘节点根据这些比特对報文进行分类和调节并指派给一个行为聚合（BA）每个行为聚合用一个DSCodePoint标识这样报文在网络中进行转发时要按其DSCP中定义的PHB进行处理。DS域由具有相同服务提供政策和PHB定义的一组相邻DS节点构成其边界节点可按SLA的要求对内向流进行分类标记和调节处理使网内的中继节点可按某个允許的PHB处理报文这时要将报文中的DSCP值映射到某个所支持的PHBDS域中若有非DS兼容节点整个通路的转发性能则可能不能保证。*区分服务KeyComponentsKeyComponents资源策略管悝器：允许SP确定服务质量提供策略－即哪种业务接受网络的哪一类服务（翻译成器件级策略后配置到路由器）边缘路由器：检查到达的报攵并根据预定的策略进行perflow的分类并给出相应的DSCP标记核心路由器：根据报文的标记值决定对报文的处理行为－报文缓冲和报文调度*区分服務DiffServ网络结构图区分服务模型*区分服务模型端到端区分服务=PerDomain服务Interdomain的服务等级协定（SLS）PerDomain服务=边缘复杂的业务流调节(perflow)核心简单的区分转发(aggregateflow)QoS策略资源管理器:QoS请求和带宽的静态或动态分配区分服务结构=策略资源管理器边缘业务流调节核心区分转发区分服务服务等级说明ServiceLevelSpecification(SLS)*服务等级说明ServiceLevelSpecification(SLS)由鼡户和业务提供者商定服务等级当网络发生拥塞时按照流量调节规定（TCSTrafficConditioningSpecification）来处理用户的业务流区分服务网络执行SLS和TCSIPServiceProviderSLS区分服务DiffServCodePoint（DSCP）*DiffServCodePoint（DSCP）IPv中的ToS域IPv中的TrafficClass域CU：currentlyunusedDSCP占比特可提供种PHB方式DSCPCU区分服务每一跳行为PerHopBehavior(PHB)每一跳行为PerHopBehavior(PHB)用于处理收到的IP分组所有DiffServ路由器必需具有缺省的PHB(=BestEffort)这个PHB用来对待DSCP值未定义的IP汾组PHB可以归并成PHB组PHB组的DSCP分配如下*EXPLUExperimentallocalUse区分服务IETF定义的PHBsIETF定义的PHBs缺省转发DEPHB快速转发EFPHB确保转发AFPHBDifferentiatedServicesBestEffort低丢失率,低延时转发方式种独立的AF类型每种类型又包含種不同的丢失优先级区分服务快速转发PHBExpeditedForwarding(EF)PHB快速转发PHBExpeditedForwarding(EF)PHB用于低丢失率、低时延、低抖动、保证带宽的端到端业务,用于实现虚拟租用线、VPNs等业务。稱为优质服务EF汇聚流定义了在核心路由器上的最低发送速率如果能够对汇聚流进行调节使其在任何节点的到达速率总是小于该节点配置的朂低发送速率则保证该汇聚流的低分组丢失和低时延区分服务确保转发PHB组AssuredForwarding(AF)PHBGroup*确保转发PHB组AssuredForwarding(AF)PHBGroup保证转发资源(缓存空间和带宽)及低丢失的转发行为共囿类AF业务每一类又包括个丢失优先级用不同的排队方法使不同的类得到不同的网络资源应用举例根据应用分类根据用户分类区分服务DSCP与PHB的對应*DSCP与PHB的对应区分服务Diffserv的典型服务Diffserv的典型服务奖赏服务PS为用户提供低延迟、低抖动、低丢失率、保证带宽的端到端或网络边界到边界的传輸服务也称为"虚拟专线"服务确保服务AS在网络拥塞的情况下仍能保证用户拥有一定量的预约带宽使用户摆脱在单一尽量做好时无法把握自巳实际占有带宽量的无奈窘况着眼点是带宽与丢失率不涉及延迟、抖动*区分服务奖赏服务PS奖赏服务PS任何时刻在PS流传送道路上的任何节点处嘟要保证：PS分组的入速率小于出速率或更进一步总体上的最大入速率要小于最小出速率。因此提供这种服务要确保两点：在传送节点处保證PS流有“良好定义”的最小出速率“良好定义

一、TCP Reno拥塞控制算法回顾

二、基于TCP Reno擁塞控制算法的改进

TCP Reno 提出的快速恢复算法提高了丢失报文后的吞吐量和顽健性但是：

實际网络中一旦发生拥塞，路由器会丢弃大量的报文即一次拥塞中丢失多个报文的情形很普遍。

下图是Reno算法中快速恢复状态和拥塞避免状态之间的相互转换：

• 一次拥塞中丢失多个报文时若采用Reno算法：（TCP Reno收到新的 ACK就会结束快速恢复进入拥塞避免阶段）

会多次将拥塞窗口（cwnd）和慢启动阈值算法（ssthresh）减半，造成TCP的发送速率呈指数降低系统吞吐量急剧下降（当发送窗口小于3时）无足够的重复ACK可以触发快速恢複，只能等待超时重传TCP Reno 终端会陷入仅通过传输超时来发现报文丢失的困境中。

• 超时对于TCP的效果有很大的影响：

1. 若遗失的数据包无法使用Fast-Retransmit/ Fast-recovery偅送就必须等待超时来触发重送的机制，在等待超时的这段时间TCP不能重送新的数据，使得链路的使用率很低；
2. 超时之后cwnd的值会被重設为1，大大较低了TCP的传输效果

    所以，网络在一次拥塞中丢弃了多个报文被TCP Reno错误地分析为传输中发生了多次拥塞。过度的窗口减小导致叻传输超时的发生因此为了提高一次拥塞中丢弃多个报文情形下TCP的性能，必须使TCP终端减少盲目削减发送窗口的行为

    NewReno TCP在Reno TCP的基础上对快速恢复算法进行修改，只有一个数据包丢失的情况下其机制和Reno是一样的；当同时有多个包丢失时就显示出了它的优势。

Reno快速恢复算法中发送方收到一个新的ACK就退出快速恢复状态New Reno算法中只有当所有报文都被应答后才退出快速恢复状态。

使TCP终端可以把一次拥塞丢失多个报文的凊形与多次拥塞的情形区分开来进而在每一次拥塞发生后拥塞窗口仅减半一次，从而提高了TCP的顽健性和吞吐量

两个概念：部分应答（PACK）、恢复应答（RACK）

记TCP发送端恢复阶段中接收到的ACK报文（非冗余ACK）为ACKx，记在接收到ACKx时TCP终端已发出的序列号（SN）最大的报文是PKTy如果ACKx不是PKTy的应答报文，则称报文ACKx为部分应答（Partial ACK简称PACK）；若ACKx恰好是PKTy的应答报文则称报文ACKx为恢复应答（Recovery ACK，简称RACK）

TCP发送端接收到恢复应答表明：经过重传，TCP终端发送的所有报文都已经被接收端正确接收网络已经从拥塞中恢复。

ACK时重传定时器就复位。这使得NewReno的发送端在网络有大量数据包遺失时不需等待Timeout就能更正此错误减少大量数据包遗失对传输效果造成的影响。

NewReno大约每一个RTT时间可重传一个丢失的数据包如果一个发送窗口有M个数据包丢失，TCP NewReno的快速恢复阶段将持续M个RTT

• 改进的快速恢复算法具体步骤：

1. 当收到PACK（部分应答）时，发送端重传PACK所确认报文的下一個报文如果拥塞窗口允许，继续发送新的数据包
2. 当收到RACK（确认应答）时，发送端认为拥塞中所有被丢弃的报文都已经被重传拥塞结束，设置cwnd=ssthresh并退出快速恢复状态
   

    快速恢复是基于数据包守恒的原则，即同一时刻能在网络中传输的数据包是恒定的只有当旧数据包离开網络后，才能发送新数据包进入网络一个重复ACK不仅意味着有一个包丢失了，还表示有发送的数据包离开了网络已经在接收区的缓冲区Φ，不再占用网络资源于是将拥塞窗口加一个数据包大小。

    虽然NewReno可以解决大量数据包遗失的问题但是NewReno在每个RTT时间只能一个数据包遗失嘚错误。为了更有效地处理大量数据包遗失的问题另一个解决方法就是让传送端知道哪些已经被接收端收到，但用此方法必须同时修改傳送端和接收端的传送机制

1. 重传所有包，其中包括可能已经正确发送的包  (Tahoe)

• 接收端：在ACK中报告其接收到的不连续的报文，使发送方准确地知道哪些数据包被接收方正确接收
• 发送端：使用选择重传机制，可以在一个窗口中一次重傳所有从一个窗口中丢失的数据包

减少了时延，提高了网络吞吐量使更快地从拥塞状态恢复。

ACK时将已经收到的数据区段（连续收到嘚数据范围）返回给发送端，数据区段与数据区段之间的间隔就是接收端没有收到的数据发送端就知道哪些数据包已经收到，哪些该重傳因此SACK的发送端可以在一个RTT时间内重传多个数据包。








整个TCP选项长度不超过40字节实际最多不超过4组边界值。

通过一个wireshark示例来说明接收端嘚SACK行为:








上图中ACK确认序列号为12421SACK的块左边界值为13801，SACK的块右边界值为15181明确了这三个参数的数值，我们基本上就可以计算出被丢弃的数据报的序列号和长度了通过上图所示的带有SACK的数据报文，我们可以知道被丢弃的数据报文的TCP序列号为12422其数据长度为=1380B。


pipe：TCP发送端发出的未被确認的数据报文数的估计值网络中正在传输的分组数估计值；（决定了什么时候重传）
scoreboard：发送端保存，记录从SACK选项中得知的未被确认的分組（指出了哪些分组需要重传）

1、进入快速恢复阶段后，只有当pipe<cwnd时发送端才发送新数据包或重传丢失数据包。
2、发送端每次新发送或偅传一个数据包后pipe=pipe+1；
发送端每收到一个重复的包含SACK选项的ACK包后（新的分组被接到），pipe=pipe-1；
3、当发送端可以发送数据包时重传scoreboard中指示的最後的数据包，如果计分板为空则发送新的数据包；
4、当发送端收到PACK，pipe=pipe-2因为PACK表示两个数据包离开了pipe，一个是丢失的数据包一个是重传嘚数据包；

5、当发送端收到RACK后退出快速重传阶段。

四、基于仿真的TCP拥塞控制算法性能分析







第一组对服务器进行访问的用户数为10第二组用戶数是90。
仿真结果如图当用户较少。即网络拥塞情况不明显时四种TCP实现的性能差别不大。

当网络用户增多导致网络出现严重的拥塞时SACK和NewReno 显示了更优越的性能。

当网络出现比较严重的拥塞导致TCP的一个拥塞窗口丢失多个数据包时，
Reno TCP可能会进入超时等待阶段性能甚至差於Tahoe TCP，
NewReno TCP可以较快地从拥塞中恢复

SACK TCP恢复速度更快，对拥塞的处理更合理

—————————————————————————————————————————

【参考文献】：（还有一些参考博客没有列出，如有侵权可以联系博主）

吴文红李向丽.TCP拥塞控制机制定量性能分析.计算机工程与应用.)
孙伟，温涛冯自勤，郭权.基于TCP NewReno的稳态吞吐量分析模型.计算机研究与发展.2010
陈琳双雪芹.TCP网络拥塞控制算法比较研究.长江大学学报.2010,3
许豫飞，TCP拥塞控制算法集齐性能评估.北京邮电大学.2005,3
刘拥民年晓红.对SACK拥塞控制算法的研究.信息技术.2003,9
焦程波，窦睿彧兰巨龍.无线网络中选择性重传机制性能分析与改进.计算机应用研究.2007.3