ch04-2.

1第4讲网络层版本：A11.09Outline•5.1网络层设计要点•5.2路由算法•5.3拥塞控制算法•5.4服务质量•5.5网络互联•作业：如何提高网络服务质量5.3拥塞控制算法•拥塞:当一个子网或子网一部分出现太多分组的时候，网络的性能急剧下降的情况。–分组太多–处理器慢•出现资源拥塞的条件：对资源需求的总和可用资源•路由器有足够的内存来存放分组，是否还会发生拥塞?ExampleDestination1.5-MbpsT1linkSource2Router仍然会拥塞CongestionControl提供的负载吞吐量理想的拥塞控制拥塞死锁（吞吐量=0）无拥塞控制实际的拥塞控制轻度拥塞0拥塞控制:采取措施，防止网络出现拥塞.CongestionControlVS.flowcontrol•拥塞控制是一个全局性问题–所有主机和路由器–存储-转发处理过程–所有可能会削弱子网承载容量的其他因素•流控制只涉及到发送方和接收方之间的点到点流量–限制传输速率–接收方向发送方发送反馈信息CongestionControlVS.flowcontrol•Example:需流量控制需拥塞控制•讨论：道路交通中如何处理拥堵？–拓宽道路–绕行（根据实时交通状况）–限行（禁止部分车辆出行）–主动放弃出行（根据实时交通状况）–在还没堵死时就开始采取措施–实时监测+信息通告CongestionControlAlgorithms•流量感知路由：根据流量定制路由（流量工程）•准入控制：不允许进入网络•流量调整：根据网络拥塞情况调整发送速度•负载丢弃：拥塞时丢弃数据包解决办法：增加资源，减少负载资源保障供给流量感知路由准入控制流量调整负载丢弃准入控制•用于虚电路网络•一旦出现拥塞，则不再创建任何虚电路.•当虚电路建立的时候，在主机和子网之间进行协商以达成一致的约定–协商服务质量–reserveresource(预留资源)•绕开有问题的区域建立新的虚电路主机H1和H2分别向主机H3和H4发送数据1.5Mb/s链路H1H2H3H4R2R1H1H21.5Mb/s链路输出队列1Mb/s的实时数据总数据率已超过了1.5Mb/s链路的带宽让一个数据流通过1.5Mb/s的链路，而阻止另一个数据流的通过七系三教计算机网络课程组流量调节•动态调整发送速度–a)监视系统–b)将监视的信息传递到能够采取行动的地方•Thewarningbit(警告位)•Chokepacket(抑制分组)•Hop-by-hopchokepacket(逐跳抑制分组)–c)调整系统的运行以解决问题监视系统•输出线路的使用情况•队列长度•缓冲区使用情况•丢弃分组的数量•超时分组的数量μ新=aμ旧+(1-a)f七系三教计算机网络课程组传递拥塞信息•Thewarningbit(警告位)•Chokepacket(抑制分组)•Hop-by-hopchokepacket(逐跳抑制分组)警告位•路由器–监视平均队列长度–当路由器处于警告状态时，在转发分组的头部设置二进制警告位•源主机–目标端将警告位送回源主机–源主机监视设置了警告位的分组比例•超过阈值，源主机减少发送抑制分组•每一个路由器都监视输出线路的使用率•当使用率达到阈值，向源主机发送抑制分组•源主机将减慢到相同目标端的分组传输速率–调整策略参数，按一定比例减少发向特定目的地的流量–在一段时间间隔内，忽略所有指向同一目标的抑制分组•若在监听周期内没有收到抑制包，则增加负载•流量增减策略是：减少时，按比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。逐跳抑制分组•抑制分组：只会影响到源主机，响应太慢•逐跳抑制分组：让经过的路由器减慢分组流chokeReducedflow18逐跳抑制分组(cont)•抑制包对它经过的每个路由器都起作用–能够迅速缓解发生拥塞处的拥塞–上游路由器要求有更多的缓冲区chokeReducedflow5.3.5负载丢弃•拥塞的时候丢弃一些分组来消除拥塞•丢弃哪些分组?–葡萄酒策略•老的分组比新的分组更有价值–例如，文件传输–牛奶策略•新的分组比老的分组更有价值–例如，流媒体–源主机标明哪些分组更重要.(优先级)•什么时候丢弃？早期检测—拥塞预警•当一开始检测到有拥塞可能的时候就采取措施比等到拥塞严重影响工作之后再采取措施更有效•在实际耗尽所有的缓冲区空间之前就开始丢弃分组•在有些传输协议（包括TCP）中，针对分组丢失的响应措施是源主机减慢传输速度，这样可以减少拥塞什么时候丢弃？•希望–流量小：不丢弃–有拥塞可能：部分丢弃–拥塞：丢弃七系三教计算机网络课程组随机的早期检测(cont)•拥塞预警时，以一定的概率丢弃•两个队列长度阈值：预警值，拥塞值–ifAvgLen=MinThresholdthen•分组加入队列排队，等候被转发–ifMinThresholdAvgLenMaxThreshold•计算概率P•以概率P丢弃到达的分组–ifAvgLen=MaxThresholdthen•丢弃分组随机早期检测(cont)P(drop)1.0MaxPMinThreshMaxThreshAvgLen5.4QualityOfService•5.4.1需求•5.4.2获得好的服务质量所使用的技术•5.4.3综合服务•5.4.4区分服务5.4.1Requirements什么是服务质量?•使用者的观点:–确保源端到目标端的服务•e.g.保证延迟(VoIP),保证带宽(VPN)•网络的观点:–区别服务：不同分组不同处理–可以提供端到端的服务质量保证•e.g.只有很少的高优先级数据包WhatisQoS(cont)•QoS基本参数:–延迟–抖动–带宽–可靠性:位出错率、分组丢失率、建立连接失败率etc.确保服务质量必须解决的问题：•应用程序需要什么样的服务质量？•如何规范进入网络的流量？•为了保障性能如何在路由器预留资源？•网络能否安全地接受更多资源？为什么我们要获得好的服务质量?•让一些使用者与其他的区别开来•使服务质量与应用需求联系起来–在网络负载过重的时候消除竞争–e.g.•交互应用需要最低的延迟•文件传输和电子邮件需要最高的可靠性•Web访问对两者要求很很高(!?)ApplicationsthatneedQoSApplicationClasses•灵活性:在没有确保及时传递数据情况下，一些应用也能很好的工作。–Telnet,FTP,email,Webbrowser,etc.•实时性:对延迟敏感–延迟的数据毫无价值•音频和视频的应用、工业控制等等.–Hardreal-time:datalate=disaster–Softreal-time:datalate=headacheApplicationClasses(cont)•ATM–位速率恒定的应用•例如：电话–位速率可变的实时应用•例如：视频会议–位速率可变的非实时应用•例如：通过Internet观看电影–最大可用位速率的应用•例如：文件传输Approaches•针对流还是数据类型提供QOS？–流：从一个源到目标的分组流•细粒度:针对应用或者数据流提供QOS–综合服务:由IETF制定的资源预留协议（ResourceReservationProtocol，RSVP)•粗粒度:针对数据大类提供QOS–区分服务（DifferentiatedServices）IP网络提供尽力而为服务提供附加的服务是很难的！5.4.2TechniquesforAchievingGoodQOS•Overprovisioning(过渡提供资源)•Buffering(缓冲)•Trafficshaping(流量整形)•Resourcereservation(资源预留)•AdmissionControl(准入控制)•Proportionalrouting(比例路由)•PacketScheduling(分组调度)Overprovisioning•过度提供资源：–Routercapacity（路由器容量）–Bufferspace（缓冲区空间）–Bandwidth（宽带）•问题：–代价昂贵Buffering•在接受方，数据流在被递交之前可以先缓存起来–不影响可靠性和宽带–会增加延迟•消除抖动分组发出123456t分组到达123456t分组个数654321t设置缓存时间增大缓存时间立即还原Trafficshaping（流量整形）•拥塞一般是由于突发通信量•流量整形的目的：使数据流平稳–以均衡的速率发送数据–在服务器端对流量进行平滑处理主机H1和H2分别向主机H3和H4发送数据1.5Mb/s链路H1H2H3H4R2R1H1H21.5Mb/s链路输出队列数据率异常的实时音频数据FTP文件数据路由器应能将对数据流进行通信量的管制(policing),使该数据流不影响其他正常数据流在网络中通过例如，可将H1的数据率限定为1Mb/sR1不停地监视H1的数据率，只要其数据率超过规定的1Mb/s，R1就将其中的某些分组丢弃。Trafficshaping(cont)•Servicelevelagreement(服务等级协定)–用户和通信子网（运营商）就流量模式达成的协议•Trafficpolicing（流量监管）–是否达到协议要求•流量整形算法：–Theleakybucketalgorithm（漏桶算法）–Thetokenbucketalgorithm（令牌桶算法）Theleakybucketalgorithm漏桶OutputPacketsfrominput漏桶算法(cont)•将主机内用户进程发送出来的一个不均匀分组流变成了网络上的一个均匀分组流•实现:–漏桶是由一个有限队列构成的–当一个分组到达时•如果队列中还有空间，则被添加到队列末尾•否则，该分组被丢弃七系三教计算机网络课程组42漏桶法问题•不允许突发传输•有时，允许短暂的突发分组进入网络层，并不需要平滑处理•因此，用到漏桶算法的改进方法：令牌桶算法七系三教计算机网络课程组令牌桶算法•Theleakybucket（漏桶法）–输出保持严格的均匀速率•Thetokenbucket（令牌桶法）–漏桶中保存令牌–令牌每隔∆T秒产生一个–要使一个分组被传送出去，必须要抓住并销毁一个令牌令牌桶算法beforeafter七系三教计算机网络课程组45令牌桶算法•实现：–计数器:counttokens•每隔∆T秒，计数器加一•当一个分组被发送出去的时候，计数器减一•当计数器减到零时，就不能再发送分组允许突发流量,但是不得超过一个预定的最大长度。七系三教计算机网络课程组46令牌桶+漏桶•使流量平滑：–在令牌桶之后再插入一个漏桶–漏桶的速率应该高于令牌桶的ρ值，但低于网络的最大速率Resourcereservation（资源预留）•假设：–一个流具有特定的路径•Resourcereservation（资源预留）–Bandwidth（宽带）–Bufferspace（缓冲区空间）–CPUcycles（CPU周期）AdmissionControl（准入控制）•接受或拒绝一个分组流–数据流要预先声明所需的服务质量–路由器根据可利用资源和对其他流做出的承诺，决定允许或者拒绝该分组流•如何决定Qos的参数?–时延、带宽等比较容易确定，但有些资源并不好估计，比如缓冲区、CPU周期等。所以需要协商AdmissionControl(cont)•Flownegotiation(流协商)–Flowspecification(流规范)•规范相应的参数，如平均速率、峰值速率、突发长度等七系三教计算机网络课程组Proportionalrouting（比例路由）•运用多种路径–没有唯一最好路径–将到达每个目标节点的流量分散到多条路径七系三教计算机网络课程组PacketScheduling（分组调度）•“调度”就是指排队的规则。•分组调度算法–公平队列–加权公平队列•默认排队规则是先进先出FIFO(FirstInFirstOut)–当队列已满时，后到达的分组就被丢弃。–不能区分时间敏感分组和一般数据分组七系三教计