基于区分服务的拥塞控制算法研究.pdf

《基于区分服务的拥塞控制算法研究.pdf》由会员分享，可在线阅读，更多相关《基于区分服务的拥塞控制算法研究.pdf（58页珍藏版）》请在三一文库上搜索。

1、南京邮电大学硕士研究生学位论文 摘要 I 摘摘 要要 网络拥塞现象对于网络的产生与发展来说是如影随形的，也一直是制约和限制网络发展 的一大因素。由于网络资源与网络流量的分布不均衡性，网络拥塞现象是普遍存在的。网络 拥塞的出现会使网络吞吐量迅速下降，端到端的延迟增加，各业务流得不到足够有效的带宽， 使网络QoS保证面临挑战。如何实现网络拥塞控制管理，使网络在发生拥塞时能够提供有效 的QoS保证成为研究重点。特别是近年来随着网络规模的扩大，一些对实时性要求较高的音 频、视频业务的出现，对网络QoS保证提出了更高的要求。在区分服务下，分组调度技术是 保证网络QoS的核心技术，也是实现网络拥塞控制管理

2、、保证各业务带宽分配公平性的必要 手段，因此成为了本文的主要研究对象。 轮询调度是一种常见的分组调度策略，传统轮询调度 WRR 算法在分配带宽时存在一个 公平性问题， 并不适用于数据包长度可变的网络。 本文基于 WRR 算法提出一种改进的 CWRR （可变权值轮询调度）算法，新算法可以依据平均数据包长度自适应的改变权值，对网络环 境有更强的适应性。利用 NS2 通过仿真对新算法性能进行分析，结果表明 CWRR 的公平性 比 WRR 要好。 关键词：网络拥塞，区分服务，轮询调度，公平性 南京邮电大学硕士研究生学位论文 Abstract II ABSTRACT The issue of Netwo

3、rk Congestion exists throughout development of the Network technology, which is also one of its limiting factors. The Network Congestion happens due to the imbalanced allocation of the network resources and the flows. It will significantly decrease the network throughputs and increase the time of th

4、e End-to-End delay. In that case, the bandwidth is inadequate for each service flow which directly impacts the quality of service (QoS). Therefore, it has become a research hotspot that how we can manage the network congestion control and sustain the QoS in the presence of network congestion. The re

5、quirements of QoS are getting higher because of the network expansion and the advent of audios and videos with high real-time requirements. In Differentiated Service Model, the Packet Scheduling technique is a core of guaranteeing the QoS. It can also be used to control the Network Congestion and en

6、sure the fairness of the bandwidth allocation and therefore becomes the focusing point of this thesis. Round-robin scheduling is a common packet scheduling policy, and the traditional round-robin scheduling WRR has a fairness problem of bandwidth allocation. Therefore it is not possible to be applie

7、d in the variable-length packet network. This paper proposed an improved algorithm, based on the WRR, named CWRR (Changeable Weighted Round Robin). In CWRR, the weight of the CWRR varies adaptively depending on the average packet length, to make it more adaptable to the network environment. Addition

8、ally, through the simulation analyses of the performance of the new algorithm with NS2, it is shown that the fairness of CWRR becomes better than that of the WRR . Keywords: network congestion, DiffServ, round-robin scheduling, fairness 南京邮电大学硕士研究生学位论文 目录 III 目目 录录 摘 要.I ABSTRACTII 目 录III 第一章 绪论1 1.

9、1 课题研究的背景与意义1 1.2 服务质量（QOS）2 1.2.1 决定 QoS 的因素 2 1.2.2 端到端 QoS 服务模式 3 1.3 论文的主要研究内容与组织结构5 第二章 拥塞控制管理策略概述7 2.1 拥塞及其产生的原因7 2.2 研究拥塞控制管理的意义及策略9 2.3 TCP 拥塞控制10 2.4 基于中间节点的拥塞控制12 2.5 拥塞控制管理算法的评价标准12 2.6 队列机制与拥塞管理14 2.7 本章小结15 第三章 队列调度策略16 3.1 队列调度算法的功能及性能指标16 3.2 典型的队列调度算法17 3.3 队列调度算法比较25 3.4 本章小结25 第四章

10、一种改进的轮询调度算法 CWRR.26 4.1 CWRR 的设计背景26 4.2 CWRR 的算法思想27 4.3 CWRR 算法的具体描述27 4.4 WRR，DRR 和 CWRR 的分析比较30 4.5 本文基于区分服务的队列调度策略设计思想32 4.6 流量调节策略与令牌桶算法34 4.7 本章小结36 第五章 CWRR 算法仿真.38 5.1 NS2 网络仿真软件38 5.1.1 NS2 简介 .38 5.1.2 NS2 网络模拟的一般过程 .39 5.2 CWRR 算法仿真与性能分析41 5.2.1 仿真环境.41 5.2.2 仿真结果.42 南京邮电大学硕士研究生学位论文 目录 I

11、V 5. 3 本章小结.48 第六章 总结与展望49 6.1 论文工作总结49 6.2 以后的工作展望49 致 谢51 参考文献52 在校期间发表的学术论文55 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 课题研究的背景与意义课题研究的背景与意义 近些年来，由于计算机技术与互联网技术突飞猛进的发展，社会生活各种领域中的网络 应用也不断涌现，服务质量的要求也不断变高。这将不可避免的使得网络上传输处理的数据 类型大大增加并急剧变化着，除了以往传统的FTP、Telnet、Email、HTTP数据流外，还出现 了许多的视频、音频等多媒体数据流。同时，网络中的数据流

12、本身也具有突发性和自相似性， 大量不同类型的业务流汇集在网络中间路由节点处，将会给网络路由节点带来比较大的工作 负担1。由于网络硬件资源的增长速率远远低于网络资源需求的增加速率（主要由网络应用 增加造成），网络拥塞由此而生，在网络研究中也逐渐成为迫切需要解决的热点问题之一。 网络拥塞是由于网络客户对于包括链路带宽、 存储空间大小与处理器处理能力等网 络资源的需求超越了网络固有的能力而产生的一种持续过载的网络状态。网络的拥塞是 因为网络流量与网络资源分布不平衡而引发的，网络拥塞已成为影响网络正常平稳运行的重 要因素。当发生网络拥塞时，网络传输的吞吐量将迅速下滑，网络服务质量急剧下降，如果 没有进

13、行良好的拥塞控制管理，网络有可能会面临拥塞崩溃，致使网络通信全面瘫痪。在网 络处于拥塞崩溃状态时，任何微小的负载增量都有可能导致网络的有效吞吐量急剧下滑2。 虽然拥塞根源是网络资源的不足，但是片面增加网络资源并不能从根本上解决网络拥塞的问 题，有时甚至会适得其反。比如：如果增加网关缓冲，相应的报文通过网关的延迟就会增大， 假如总延迟时间比端系统重传时钟值大的话，将会导致报文的重发，进而加重拥塞的程度3。 网络拥塞是网络发展的一大“瓶颈”，而拥塞控制管理是保证网络服务质量的关键所在。 在网络拥塞时，如何去保证网络服务质量，并将其从拥塞状态中恢复出来是解决网络拥塞的 关键。队列管理与队列调度是基于

14、中间节点拥塞控制的核心技术，传统的队列管理算法主要 有RED算法4、ARED算法5、SRED算法6，而队列调度算法主要有WFQ算法7，WRR 算法8，DRR算法9等。本文将着重介绍队列调度在实现拥塞控制管理，保证网络服务质量 方面的作用。 伴随着英特网和各种网络业务的快速发展，特别是语音、图像等多媒体业务的飞速发展， IP网络也集多种业务于一体，已不再是单纯的数据网。多业务网络需要有更高的服务质量保 证，但传统IP网络并不能提供足够的服务质量保证。为此，业界提出了IP QoS的概念，就 是希望在IP网络上能对不同业务提供相应的QoS保证10。而区分服务是将数据流按照业 南京邮电大学硕士研究生学

15、位论文 第一章 绪论 2 务对服务质量的要求划分等级，使不同的业务流获得不同的服务等级，合理共享网络资源， 减小资源竞争，实现良好拥塞管理，提高网络服务质量。区分服务因具有很好的鲁棒性与扩 展性11，而且易于实现，成为保证IP QoS的首选方式，区分服务中的分组调度策略也成为 研究重点之一。 1.2 服务质量（服务质量（QoS） 服务质量（Quality of Service, QoS）用来衡量网络运行情况与服务实用性保证的评 价标准。网络质量QoS是基于网络基础实现的，稳定可靠的网络基础构造是保证QoS的 必要前提。 1.2.1 决定1.2.1 决定 QoS 的因素 的因素 端到端 （End

16、 to end） QoS是指网络中从发送端到接收端整个过程的QoS。 端到端QoS 也指数据在网络中传输过程中所能获得的服务质量，能够决定网络中端到端QoS主要包 含有以下几个因素： （1）丢包率（Loss）：在数据包传输过程中，丢失的数据包与总数据包的比值12。 丢包率是考察一个网络系统可靠性的重要指标，如果一个网络的可靠性比较好，当网络 中没有拥塞状况发生时，网络的丢包率理论上应为零；然而当网络中发生网络拥塞状况 时，丢包率将会增大，如果网络支持QoS准则，则可根据QoS需求选择性的丢弃一些数 据包以缓解网络中的拥塞状况。 （2）带宽（Bandwidth）：带宽就是指网络节点或者网络链路在

17、单位时间内发送数 据量，它描述了网络传输数据的能力。带宽越大，则说明网络传输数据的能力越强，越 能保证QoS。 （3）端到端延迟（Delay）：指分组从发送端发出到接收端接收到此分组所经历的 有限时间。这就像是一句话从说话人口中发出到听者听到这句话所经历的时间。端到端 延迟越小， 则表明网络的服务质量越好， 如果延迟时间过长， 则保证不了网络服务质量。 （4）抖动（Jitter）：又称时延抖动，指两个分组从发送端到达接收端的延迟之差。 假如一个分组从发送端到达接收端用了50ms，而另一个分组从发送端到达接收端用了 65ms，那么抖动就为15ms。现在网络终端的一些软件可以利用缓冲区来应对抖动所

18、造 成的服务质量下降，从一定程度上保证QoS。 现在网络日趋复杂，与人们日常工作生活已密不可分，随着网络应用的大量涌现， 南京邮电大学硕士研究生学位论文 第一章 绪论 3 特别是对延迟敏感的高品质视频和语音等，这些应用给网络服务提出了更高的要求。他 们要求网络能够对端到端延迟、带宽、丢包率和抖动进行管理，以提供可预测、可保证 的可信服务13。 网络QoS就是实现这个目标的重要手段。QoS力求为用户提供一个聚合且透明的网 络平台14。在这个网络平台中，各种业务公平地共享网络资源，并实现对不同性质业务 的区别对待，为重要数据赋予更高的优先级，使重要数据获得更多的服务机会，以保证 网络的服务质量。

19、1.2.2 端到端1.2.2 端到端 QoS 服务模式 服务模式 QoS服务模式（Ssrvice Model）就是指为网络提供QoS服务能力的模式，通过什么 样的方式转发数据和提供QoS服务，不同服务模式之间是存在很大差异的。以下为三种 常见的QoS服务模式。 （1）尽力而为服务模型 尽力而为服务模型（Best-Effort Model）是一种最为简单的QoS服务模型，在互联 网诞生之初尽力而为服务模型就已经出现，在这种服务模型中，网络应用可以在它认为 必要的时候发出任意数据，它既不需要对网络进行通知，也不需要获得网络许可，随意 性较大。网络则尽最大能力转发这些数据，对这些数据实行先到先服务的

20、原则，同等对 待，没有优先级的区分。在英特网中，尽力而为仍是默认的服务类型，适用于E-Mail、 FTP等网络应用中。 但随着互联网的广泛应用，大量的网络应用层出不穷，特别是对延迟、抖动等比较 敏感的高质量视频、音频的出现，尽力而为的服务模式已不能满足要求。尤其是网络中 出现拥塞状况时，这些对QoS要求比较高的应用将会受到很大影响，这就需要网络能够 提供更好的网络服务质量。 （2）集成服务模型 集成服务模型（Interated Service Model）是基于多服务的QoS服务模型。在应用程 序发送数据之前先要向网络申请网络资源，并将所有发送数据的简要状态（profile）报 告给网络，包括

21、时延，带宽等等。当应用程序获得网络的反馈信息后，确认已经为所要 发送数据分配了网络资源，便可执行发送任务。网络通过这种形式实现对业务的QoS保 证。 集成服务模型是通过资源预留协议（Resource Reservation Protocol, RSVP）15实现 南京邮电大学硕士研究生学位论文 第一章 绪论 4 为所要发送数据流进行资源申请的。RSVP可以实现两种类型的服务请求，一种是可以 在网络负载比较轻的情况下提供比尽力而为更好的服务质量，另一种是对端到端的带 宽、延迟等实行更严格的保证。 IntServ也存在这以下几个缺陷： 1）在使用IntServ提供服务时，数据包所经过的所有网络节点

22、都必须能够执行RSVP 信令。 2）在数据包传输沿途节点上预留的网络资源必须定期更新，如果更新信息通信不 畅，预留资源就有可能会超时而无法提供服务。 3）数据包传输沿途的每个节点都要对数据流状态进行监视，但是在网络核心中， 每秒钟都要处理大量的流，造成了不易于扩展的问题。 (3)区分服务模型 上个世纪九十年代末，“DiffServ工作组”提交了RFC2475和RFC2474两份文件16， 这两份文件为区分服务模式（Differentiated Service Model）奠定了基础。在文件中指出 需要为网络中数据提供一种简单粗略的有区别对待的服务模型， 以满足网络中各种应用 的需求。在Diff

23、Serv中，网络中节点并不都需要对数据流状态进行监管，也不需要所有 节点都拥有处理RSVP信令的能力。 DiffServ服务模型的主要流程如下： 1）IP报文头中的TOS字段将会在网络边界根据QoS需要被标记，以区分数据的优先 级别。网络边界有可能是管理边界、自治系统边界或主机。 2）当数据包发送至网络内节点时，节点将根据被标记的信息和预先设定的策略决 定对数据包进行如何转发。 3）数据包将会在网络边界被调整，到达与规则所需求的一致。 DiffServ的原理是每次服务的规则与要求是依据管理策略对其设置的，网络中的节 点使用分类器根据之前标记字段来选择数据包， 并与队列管理和队列调度机制一起对不

24、 同的数据包采取有区别的服务行为。DiffServ具体拓扑结构如图1-1所示。 南京邮电大学硕士研究生学位论文 第一章 绪论 5 图 1-1 DiffServ 拓扑结构示意图 1.3 论文的主要研究内容与组织结构论文的主要研究内容与组织结构 拥塞控制管理是IP网络QoS服务的重要内容，是保证网络正常稳定运行，保证网络服务 质量的重要方式， 而队列调度算法是实现拥塞控制管理， 保证网络服务质量(QoS)的核心技术。 本论文在对当前流行的主要队列调度算法深入分析的基础上，基于WRR算法提出一种改进算 法，命名为CWRR。传统轮询调度WRR算法存在一个带宽分配的公平性问题，并不适用于数 据包长度可变

25、的网络，改进后的CWRR算法可以依据平均数据包长度自适应的改变权值，以 适应数据包长度变化带来的带宽分配不公平现象。并通过理论分析与实验仿真证明CWRR对 于带宽分配的公平性比WRR要好。 本论文各章节的主要内容安排如下： 第一章介绍了本文的研究背景与意义，并对网络服务质量（QoS）的概念进行了介 绍，其中区分服务模型作为主要的QoS服务模式，是当今业界研究的热点。 第二章对拥塞控制管理的概念进行了介绍，阐述了几种主流的拥塞控制方式及队列机制 与拥塞控制管理的关系。其中队列调度是实现拥塞控制管理，保证网络服务质量的核心技术， 也是本论文的重点研究对象。 第三章首先对队列调度算法的功能及性能指标

26、进行了介绍，并对当前流行的经典队列调 度算法进行了分析比较。 第四章提出一种改进算法CWRR，使其可以依据平均数据包长度自适应的改变权值，以 弥补WRR的不足。本章介绍了CWRR的设计背景，算法思想与设计实现，并与WRR，DRR 南京邮电大学硕士研究生学位论文 第一章 绪论 6 算法做了分析比较。然后介绍了本文基于区分服务队列调度策略的设计思想，本论文将采用 PRI算法与改进算法CWRR结合的方式设计队列调度模型，充分融合了两者的优点，提高区分 服务的质量。 第五章首先介绍了网络仿真工具NS2，并利用NS2对提出的新算法CWRR进行了仿真实 验，通过仿真结果的对比，证实CWRR对于带宽分配的公

27、平性比WRR要好。 第六章对于论文整体工作进行了总结，并对未来工作进行了展望。 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 7 第二章第二章 拥塞控制管理策略拥塞控制管理策略 当网络中出现拥塞状况时，网络的吞吐率会大幅下降，并出现大量丢弃数据包的情况， 各节点之间的链路利用率急剧下滑，端与端的延迟增加，严重影响网络通信的畅通，使网络 服务质量下降，严重的更有可能会导致网络的完全瘫痪。而当前网络中的应用基本上都是基 于拥有拥塞相应的TCP协议17，所以网络拥塞成为重要研究热点之一。 2.1 拥塞及其产生的原因拥塞及其产生的原因 自从互联网（Internet）诞生至今，网络流量与

28、网络资源的分布不均衡而产生的拥塞始终 是网络发展面临的最大问题。随着网络应用的日益丰富和规模的不断扩展，网络拥塞的问题 也变得日趋突出。在某段时间内，如果网络中对某一资源的供给小于对该资源的需求时，网 络的性能就要变坏，这种状况就叫做“拥塞” 18。假如不能够对网络拥塞采取合适的方法进行 控制，网络的稳定运行将得不到保障。事实上，这种被称为“拥塞崩溃”现象在八十年代初期 就已经出现了。 网络资源包括网络节点的缓存、通信网络的链路容量和处理器19。假如网络资源的容量 与网络节点的处理能力小于此时网络用户对于网络提供的负载，即对资源的需求大于网络可 用资源，网络拥塞就有可能会发生，网络会变得不通畅

29、，服务质量下降。 负载 膝点 崖点 吞 吐 量 (a) 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 8 (b) 图2-1 吞吐量、响应时间与负载之间的关系 图2-1(a)(b)分别显示了吞吐量、响应时间与网络负载之间的关系。当负载较轻时，网络吞 吐量随着负载成正比增加，当负载到达一定值时，吞吐量的增加量变小，响应时间大幅上升， 当负载增加到网络的最大容量时，吞吐量将不会继续增加，假如负载继续增加，网络吞吐量 将会迅速大幅下降，接近零值，这一现象就被称作“拥塞崩溃”20，并把负载增加后响应时间 迅速变大而吞吐量增加量减少的那一点称作拥塞临界点（膝点），把负载增大吞吐量急剧降 低

30、的这一点称作拥塞崩溃点（崖点）。 由图2-1可以看出，负载在膝点处，网络资源的利用率最高。基于中间节点的拥塞控制就 是网络节点采取必要的措施，以避免拥塞的发生或对拥塞的发生做出一定反应来保障网络服 务质量。 图2-2清楚的指出了导致网络拥塞的直接原因，图中链路带宽容量，路由器缓存大小及通 信处理器都是网络资源，但同时网络资源的有限也是导致网络拥塞产生的直接原因。 网络拥塞经常在网络资源比较短缺的部分发生。 图2-3(a)反映的是链路带宽分布的不均衡 导致拥塞的过程。 当A端以2Mb/s的速率向B端发出数据时， 在网关R变会发生网络拥塞。 图2-3 （b）反映的是数据流量分布的不均衡导致网络发生

31、拥塞的现象。当C端和D端分别以2Mb/S 的速度同时向E端发送数据时，也同样会导致网络拥塞的产生。 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 9 图2-2 导致网络拥塞的因素 (a) （b） 图2-3 拥塞产生原因示意图 2.2 研究拥塞控制管理的意义及策略研究拥塞控制管理的意义及策略 网络拥塞一直伴随着互联网的产生与发展，如今的互联网更加复杂化，对于拥塞控制的 要求也就更高了。网络拥塞会使网络吞吐量与时延等网络性能指标下滑，从而导致中间节点 缓存、链路带宽等网络资源的利用率下降。如何利用有限的网络资源，控制网络流量的输入， 提高共享链路资源的合理公平利用，提高网络时延、抖

32、动、吞吐率等性能指标，保证网络服 务质量，使有限网络资源得到最优化的利用是拥塞控制管理的主要目标。因此，对拥塞控制 管理的研究对于网络的发展具有至关重要的作用。 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 10 由上一节的分析我们可以看出，网络拥塞是一个动态过程，而仅仅依靠增加网络资源这 种静态方式并不能有效解决网络拥塞的问题，甚至在有可能会使拥塞的状况更为严重。解决 网络拥塞的问题还需要运用动态的拥塞控制策略予以配合。 当前，拥塞恢复（Congestion Recovery）21与拥塞避免(Congestion Avoidance)22技术是 两种运用于网络拥塞控制的主要策

33、略。拥塞恢复的目标是在网络陷入拥塞时能够保障网络的 各项性能指标，并将网络从拥塞的状态逐渐恢复到畅通的状态。拥塞避免是为了让网络不陷 入拥塞的状态，避免拥塞状况的发生，使网络始终保持低延迟、高吞吐率23。基于中间节点 的拥塞控制与TCP拥塞控制是依据在网络中的工作位置不同来划分的两种拥塞控制方法。基 于中间节点的拥塞控制是工作在网络节点处，它对网络进行早期检测，并且及时向源节点处 发回反馈信息，保障网络服务质量与网络通畅性，这种技术从属于拥塞避免的范畴。TCP拥 塞控制可以根据发回的反馈信息，对源端节点发送报文的速度进行适当调整，它工作在源端 节点处，从属于拥塞恢复的范围。 2.3 TCP 拥

34、塞控制拥塞控制 TCP协议作为互联网（Internet）中被广泛采用的传输通信协议，依据MCI的统计，网络上 90%的总数据报文数和95%的字节总数都是运用TCP协议进行传输的24。 TCP拥塞控制机制是 依据网络中节点发回的网络信息对源端的数据发送速度进行合理调整，利用时间滑动窗口来 对进入网络的报文进行控制，从而使拥塞状况得到缓解。“拥塞避免”(Congestion Avoidance) 与“慢启动”(Slow Start) 25算法，在八十年代后期首先被Van Jacobson提出应用于弥补拥塞控 制方面的缺陷，这两种算法均包含于早期的TCP Tahoe中，其中还包含了快速重传(Fast

35、 Retransmit)策略。而随后创立的TCP Reno又加入了快速恢复(Fast Recovery)策略，使得TCP拥 塞控制日趋成熟。 图 2-4 展示了 TCP 拥塞控制策略过程，其中包含慢启动、拥塞避免、快速重传和快速恢 复四个阶段26，下面将分别对其做进一步介绍。 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 11 拥塞窗口 拥塞避免、快速重传和恢复 慢启动 cwnd cwnd/2 时间 图 2-4 TCP 拥塞控制策略 （1）慢启动 如果在源端不能获知网络状况的情况下，TCP一旦建立连接就向网络中大量注入数据报， 会使网络迅速过载，网络资源耗尽，造成网络拥塞现象，

36、网络吞吐率迅速下降。因此在这种 情况下， TCP连接在建立之初不能立刻向网络中发送过多数据， 而是利用拥塞窗口(Congestion Window，cwnd)值由小至大的逐步扩大发送量，以此达到控制注入网络数据流量的目的，这 便是慢启动算法。也就是说，在TCP建立之初，源端按照cwnd值大小发送数据，并在初始时 将cwnd值设置为一个数据包的大小。当源端每收到一个新的ACK确认信息后，cwnd的值就会 增加一个报文值。用这种慢启动方法可以使发送进入网络的数据量随时间逐渐增加，降低了 拥塞发生的可能性。 （2）拥塞避免 在慢启动算法中，TCP连接对网络中发送的数据量是随时间呈指数增长的，增长速度

37、过 快，过大的cwnd值同样会造成网络拥塞的产生。当TCP源端发现发送的数据报超时时，就默 认网络发生了拥塞状况， 随即进入拥塞避免阶段。 即设置一个慢启动门限值ssthresh进行控制。 当cwndssthresh时，源端每接收到一个ACK确认信息便增加1/cwnd，这样在每个往返时 间RTT内，cwnd只增加1，即cwnd值将随时间呈线增长趋势，有效降低缓解了拥塞状况。 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 12 （3）快速重传 当TCP的接收端发现某一报文丢失时，会将所接收到所有错序报文全部发送重复确认， 当源端接收到3个重复的确认信息后，不需要等待传输超时，立即

38、重发丢失报文。 （4）快速恢复 当发送端确认报文丢失并重发此报文后，将会设置 ssthresh 值为 cwnd/2，开始拥塞避免 过程。 2.4 基于中间节点的拥塞控制基于中间节点的拥塞控制 随着计算机网络的不断扩大与发展，网络应用的不断丰富，互联网也变得日趋复杂化， 对于网络拥塞控制管理的要求也更加严格，单纯依靠 TCP 拥塞控制的方式去解决网络拥塞的 问题已经捉襟见肘了，这就要求基于网络中间节点的拥塞控制也必须加入其中。 基于中间节点的拥塞控制策略主要包含队列管理与队列调度技术，队列管理策略是为到 达节点的报文进行储存空间的分配，并在特定时候按照一定算法合理丢弃某些分组，已到达 控制队列长

39、度的目的；队列调度策略是将队列中的分组按照一定算法有选择的按一定顺序发 送至网络中，它是保障网络服务质量，实现拥塞控制管理的必要手段，是本文的研究对象。 2.5 拥塞控制管理算法的评价标准拥塞控制管理算法的评价标准 在对设计和评价任何一个算法时，都需要一定的评价标准来对算法的性能和实用性进行 分析，同样拥塞控制算法也不例外。在评价一个拥塞控制算法时，连接的丢失率、端系统的 吞吐率和端到端的延迟等都是重要的评价标准27。拥塞控制算法是运用在网络系统中，对整 个网络的正常运行起着至关重要的作用，因此，对拥塞控制算法的评价也应该从整个系统出 发。 （1）吞吐量（Throughout）：指单位时间内有

40、多少数据进入网络，可用峰值速率和平均 速率进行描述。网络资源分配的不均衡导致并加重网络拥塞情况，而网络的吞吐量描述的就 是业务流的有效带宽。通过对网络中业务流吞吐量的研究，可以得出网络资源是否得到公平 分配。 （2）端到端的时延（Delay）：指分组从源端到达接收端的时间间隔，传播时延、节点 处理时延、排队时延和传输时延构成了主要的端到端的时延28。 （3）时延抖动（Jitter）：指端到端传输时延的变化，即相邻两个分组从源端到达接受端 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 13 时间间隔之差。尽管两个大小相同的分组进过相同的路径从发送端到达接受端，它们的传输 延迟和传

41、播延迟将基本相同。但由于网络是一个复杂的整体，总是在动态变化着的，在不同 的网络负载下，分组在每个节点的排队延迟和处理延迟都会有很大不同，因此都会出现一定 的时延抖动。当网络中发生拥塞现象时，网络的时延抖动会突然变大。 （4）丢包率（Loss）：指在分组传输过程中，丢失的分组数与传输的总的分组数之比。 如果分组在传输过程中出现了网络拥塞情况，那么分组将先进入网络节点的缓冲区中进行缓 存。但如果网络拥塞比较严重，拥塞时间过长，缓冲区中的分组会越来越多，可能会耗尽缓 存资源，超出缓存空间的分组将会被丢弃掉。因此，丢包率也是考察拥塞控制算法性能的重 要指标之一。 因为网络拥塞对网络QoS影响巨大，所

42、以更需要从整个网络系统去考察拥塞控制算法的 性能。资源分配的公平性29和分配的效率30是两个主要的系统评价标准。 （1）资源分配的效率(Efficiency)：在研究中，可以使用Power函数实现对资源分配效率 的评价31。Power函数被定义为： /PowerThroughputResponseTime = (2-1) 式（2-1）中，Throughput 表示吞吐量，ResponseTime 表示反应时间，默认取1=。但如果在 评价时更偏重于对反应时间的考察，则取1。得到的 Power 的值如果越大，那么资源分配的效率就越高1。 power 负载 膝点崖点 图 2-5 Power 函数示意

43、图 图 2-5 为 Power 函数示意图，由图中可以看出，当网络负载处于 Knee 时，Power 具有最 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 14 大值。另外，但 Power 函数一般只用于单用户、单资源的系统中，而且是假设处于缓存空间 没有限制，队列为 M/M/1 的网络中。所以 Power 函数还是有一定局限性的32。 (2)资源分配的公平性：当存在多个用户共享网络资源时，就需要考虑网络资源分配的 公平性问题。常见的公平性评价方法有Fairness Index ,Max-Min Fairness和 Proportional Fairness。 Fairness

44、 Index的公平性被如下定义： 2 () ( ) i i x F x nx = （2-2） 假设网络中共有f个用户， 其中有i(if)个用户能够平均拥有网络资源,而剩余( fi ） 个 用户完全不拥有网络资源，那么公平度为 / if 。 Max-Min Fairness并不能给出公平程度的定值，是一种处于理想状况下的公平性准则。它 被定义为：每个用户都要拥有和其他的瓶颈用户相同的吞吐量。 公平性的研究对象是网络资源的分配，在对公平性进行评价时，首先要对网络资源的概 念有所认识。在评价公平性时，大多数研究是将吞吐量作为主要的网络资源研究的，但这并 不完全符合网络资源的状况。网络资源主要包括链路

45、带宽、网关处理能力与节点的缓冲等， 全面的公平性评价应从这些方面整体考虑。 2.6 队列机制与拥塞管理队列机制与拥塞管理 当网络工作在低负载状态下时，分组到达节点接口就会被立刻转发出去，而不会产生网 络拥塞现象；当节点接口转发分组的速度低于分组到达网络接口的速率时，接口来不及转发 所有分组，就会产生网络拥塞现象。当使用了网络拥塞管理特性时，接口会依据到达分组的 优先级和队列机制进行排队，根据一定算法确定哪些分组应该进入相应队列，并按照合理的 先后顺序将分组转发出去。 拥塞管理特性是依据业务性质优先级来决定分组转发顺序。它生成队列空间，依据分组 性质的进行分类并送入不同队列，最后根据队列的优先级

46、将分组按照合理顺序转发出去以实 现拥塞管理的目的，它包含包括队列管理策略和队列调度策略。在网络中的各种应用不断涌 现，各种业务流共同竞争有限的网络资源，队列调度技术是保障不同业务流公平获得合理网 络资源，保障网络服务质量，达到拥塞控制管理目的的有效手段，也是本文研究的重点。下 面将重点介绍队列调度策略。 南京邮电大学硕士研究生学位论文 第二章 拥塞控制管理策略概述 15 2.7 本章小结本章小结 网络拥塞自网络诞生至今一直伴随其左右，是网络中普遍存在的一个现象，也在一定程 度上制约着网络的发展。本章主要介绍了网络拥塞现象及对拥塞进行控制管理的策略。首先 介绍了拥塞对于网络通信质量的影响及拥塞产

47、生的原因，网络流量与网络资源的分配不均衡 是导致网络拥塞的根本原因。接着对研究拥塞控制管理的意义及控制策略进行了介绍，拥塞 控制管理策略主要包括 TCP 拥塞控制及基于中间节点的拥塞控制策略。 TCP 拥塞控制过程主 要包括慢启动，拥塞避免，快速重传与快速恢复阶段；基于中间节点的拥塞控制策略包含队 列管理与队列调度技术。最后对研究拥塞控制管理中常见的评价标准进行了说明，对队列机 制与拥塞控制管理的关系进行了阐述。 南京邮电大学硕士研究生学位论文 第三章 队列调度策略 16 第三章第三章 队列调度策略队列调度策略 队列调度机制能够有效解决多业务共同竞争有限网络资源的问题，被广泛应用于管理资 源之中。队列管理策略解决的只是分组的排队问题，即是对缓存资源的合理分配，而在网络 节点中，更为重要的是输出带宽资源的分配问题，从而完成排队与转发的整体过程，确保带 宽资源的公平合理分配，这是队列调度策略所要解决的问题。其目标就是分组在网络传输过 程中对其合理分配带宽资源，以满足用户需求。 队列调度机制是根据优先级的不同按照一定规则确定下次对哪个队列中排队的分组进行 调度，并将其发送出去，以此来保障各种不同性质业务合理获得链路带宽资源，而服务规则 是根据网络环境与服务需求而确定。比如轮询调度策略（Round