基本方式拥塞控制的典型算法拥塞控制机制拥塞控制概述队列调度队列管理本章小结第三章经典队列管理算法分析被动队列管理算法主动队列管理算法随机早期检测算法算法算法算法本章小结第四章基于链路负载自适应的算法算法的特点离散动态反馈模型算法原理丢弃概率计算函数的改进最大丢弃概率自适应调整本章小结第五章算法仿真网络仿真软件介绍的组成以及层次结构仿真的流程相关工具算法性能仿真网络仿真拓扑结构以及参数设置不同网络负载条件下队列长度变化及其稳定性有突发流的情况下队列长度变化及其稳定性万方数据算法丢包率时延和时延抖动链路吞吐量和利用率本章小结第六章总结与展望本文工作总结展望与后续工作参考文献攻读硕士学位期间取得的科研成果致谢万方数据南京邮电大学硕士研究生学位论文第章绪论第章绪论研究背景及意义互联网的前身是美国国防部的计划。为了满足军事研究的需求，最初的设计只是将几台用于军事指挥的计算机相互连接起来。通过不断的发展，当美国国家科学基金会的网络与网络实现互联互通以后，网络中的计算机数量迅猛增长，随着遍布世界各地的网络不断加入，彼此互联，人们将这种实现互联的网络称为互联网。伴随着通信技术计算机网络技术的不断发展，特别是在协议规范推出以来，不同网络环境之间实现了互联以及通信，互联网的规模爆发式增长。互联网的最初设计是基于分组交换的非面向连接网络，数据以分组数据包的形式，不加区分地在网络中传输，网络采用尽力而为的服务模式来传输每个数据包分组，虽然建立在这种服务模式上的传统网络应用和协议具有较强的灵活性以及适应性，但是这种网络服务体系早已不能满足用户对于网络服务质量的要求，网络拥塞问题开始变得越来越严重。许多学者提出在现有的网络体系结构中合理地使用拥塞控制机制来防止网络中出现严重的拥塞情况，同时指出，使网络运行在轻度拥塞的状态下，网络才能有更好的性能表现。通过研究拥塞控制算法，对于提升互联网的鲁棒性和稳定性具有非常重要的意义。然而互联网分布的复杂性拥塞控制算法的分布性以及对拥塞控制算法性能的要求，使得在拥塞控制算法在设计上有较大的难度。从人们认识到网络拥塞问题开始，大量的研究人员就参与到拥塞控制的研究中，并且提出了许多拥塞控制算法，但到目前为止，网络拥塞问题还没有得到很好的解决。中主要由两种业务流组成，分别是对源端拥塞控制信息做出响应的响应流和对源端拥塞控制信息不做任何反应的非响应流。协议在检测链路空闲带宽以及响应拥塞控制过程中，源端的发送速率在拥塞控制下波动较大，对基于业务服务质量的稳定性造成威胁，所以大部分的多媒但是伴随着互联网规模的迅猛发展，网络应用软件流量也突飞猛进。仅仅依靠端到端的拥塞控制已经很难满足人们对网络服务质量的要求，因此，考虑将网络本身加入到拥塞控制中，通过增强网络中间节点拥塞控制的能力，就显得很必要了。将基于端到端的拥塞控制研究同基于的拥塞控制研究相结合，已经成为新的研究热点，成为解决网络拥塞问题的个新的研究方向。基于的拥塞控制机制主要通过对路由器缓冲队列中的分组数据进行调度管理，同拥塞控制机制相结合，达到拥塞控制的目的。从功能的实现上可以分为两大类队列调度算法和队列管理算法。队列调度算法的研究重点在与如何高效率地发送缓冲区的数据包分组，以及如何在各业务流之间分配带宽资源等问题队列管理算法的研究重点在于网络发生拥塞的情况下，如何选择丢弃数据包，维持链路队列长度处于最佳的范围，保证网络链路的传输效率，以及降低链路的丢包情况等等。队列管理算法可以分为主动队列管理被动队列管理，其中主动队列管理算法是当前研究领域的热点问题。队列调度队列调度算法是网络资源有效管理方法的重要组成，针对不同的业务分配不同的链路带宽资源，同时为不同的业务进行优先级区分，是合理解决多个业务流竞争有限的网络资源的方法。通常，先制定系列的调度规则，按照调度规则决定数据分组接受服务的次序。下面简要介绍主要使用的队列调度算法。先进先出也叫“先来先服务”，。算法按照数据分组到达路由器的顺序将数据依次存放至缓存队列中，然后，调度算法对缓存队列的数据也是按照进入缓存的顺序依次进行处理。调度算法实现简单，并且带有存储转发功能，是目前网络中使用最为普遍的调度算法。调度算法的缺点是不能实现网络资源的公平性问题，主要万方数据南京邮电大学硕士研究生学位论文第二章拥塞控制基本机制体现在它通过对业务流占用队列的多少进行分配资源，因此无法实现公平性原则。时间片轮询，时间片轮询调度算法的基本原理是无区别地对待缓冲区中不同调度队列的分组，循环进行相应时间的队列处理。它的缺点同相同，在不同队列中分组长度不同时，不能保证公平性问题。另外它不能提供时延保证。公平队列调度为了有效解决轮询调度算法在处理可变长分组数据中存在的不公平性问题，在轮询调度算法的基础上，提出了近似的解决方案公平队列调度算法。通过计算每个数据包分组按传统轮询的方式发送所需时间来对数据进行排序，公平队列调度对各数据流的调度队列几乎是同时进行，能够独立于数据分组大小进行有效地带宽分配，对于解决公平性问题，这是个很好的方法。但是公平队列调度算法实现复杂，并且需要额外计算分组发送时间单独统计数据流状态等，这些都额外增加了路由器在队列调度时的负担。加权公平队列调度加权公平队列调度算法是在公平队列调度基础上的改进算法，主要实现对分组按照不同业务不同优先级等条件，用特定的哈希函数分成不同的队列，对不同的队列赋予不同的权值。需求较高的业务流可以通过设置高的优先级，以保证这些业务流能够被优先处理，另外也可以实现将带宽公平地分给其他低优先级的业务流。加权公平队列调度算法中所使用的权值可以由路由器在处理调度时候按需自行设定，也可以由源端在发送数据包分组时，通过信令的形式来通知路由器进行权值的设定。加权公平队列调度相比公平队列调度，在保证公平性的基础上，对于各数据流的优先级进行了充分考虑，满足了低时延的需求，但是也存公平队列调度相同的问题，路由器维护每个数据流的状态信息，增大了路由器处理数据分组的负担，并且原理复杂难以实现。随着互联网的发展，应用需求逐渐增大，网络公平性问题将会越来越被重视，基于中间节点的队列调度将会进步提升互联网性能。队列管理队列管理主要是在维护路由器缓存队列长度时采取不同的丢包策略，以此来实现对网络拥塞的控制，提升网络的整体性能以及稳定性。队列管理算法通常分为被动队列管理和主动队列管理。被动队列管理的基本原理是为链路中每个队列设置个最大队列长度阈值，在接收数据分组进入队列时，当队列长度小于最大队列长度，接收数据分组进入队列当队列长度大于万方数据南京邮电大学硕士研究生学位论文第二章拥塞控制基本机制最大队列长度，丢弃所有数据分组，直到队列长度小于最大队列长度再继续接收数据分组。这种方法就是弃尾算法。虽然弃尾算法在当前互联网中得到了广泛的应用，但是它存在着以下几个重要的问题满队列现象因为弃尾算法是在检测到缓存队列出现满队列时才发出拥塞控制信息给源端，在发出拥塞控制信息到实施拥塞控制算法的时间间隔里，队列的缓存区直是会处于满队列的状态，这样极大地增加了网络中端到端的时延。死锁现象因为受到全局同步和其他定时的作用影响，造成其他数据流不能进入队列中，而路由器的缓存队列始终由几个流长期占用的现象。全局同步当检测到路由器的缓存队列已满时，因为没有足够的缓存区再接收数据将会全部丢弃到达的数据，路由器向所有的源端发送拥塞反馈信息，导致多个响应的流同时缩小拥塞控制窗口，造成流量急剧下降。而当网络拥塞现象得到缓解，这些响应流又会同时增大拥塞控制窗口，来增加网络中数据包的传输量，又会造成网络流量突增，再次引发网络拥塞，而且这种全局同步现象会周期性地反复出现，甚至会造成网络崩溃。针对被动管理算法存在的问题，等人在上提出了主动队列管理思想。主动队列管理是种基于调度策略的反馈控制机制，基本原理是通过对网络流量的实时监控，并对缓冲区队列长度负载变化进行对比，在队列满之前就有选择地标记或者丢弃部分数据包分组，这样源端就可以在网络拥塞发生之前动态调整发送窗口，做出相应的反应，维持缓冲队列在合理的范围，获得较小的端到端链路时延以及较高的链路吞吐量。主动队列管理主要解决以下几个问题能够提前预测网络拥塞情况，并通过标记或者丢包等方式通知源端做出相应的措施来避免网络拥塞发生。能够在拥塞控制中防止多个流同步进入慢启动状态，引发全局同步。能够保持队列处于比较合理的区间，降低分组的排队时延和分组丢弃概率，并能吸收突发数据流，同时在低排队延时和高吞吐量之间做出合理的平衡。能够保证对流中的突发流短时流长时流等公平性处理。主动队列管理算法能够动态地将网络拥塞信息告知源端，可以通过丢弃数据包分组来隐式通知，或者通过显示拥塞标志标记数据包分组来告知发送端。通过网络中间节点的主动队列管理算法和源端滑动窗口机制同时对提供支持，在网络拥塞程度比较小的时候，主动队列管理算法并不对数据包分组进行丢弃，处理数据包的方式大致与被动队列管理相同，另外有选择地对数据包分组进行标记，同时通过确认信息将网络拥塞传递给发万方数据南京邮电大学硕士研究生学位论文第二章拥塞控制基本机制送端，这样发送端就可以根据网络拥塞信息来实时调整源端数据发送速率，降低拥塞情况对网络性能的影响。的出现为网络拥塞控制提供了种显式的反馈机制，能够不完全依赖定时器超时或者是要接收到多个相同的信息才能确定网络发生拥塞，这样极大地减少了网络的超时重传，并且发送端可以更迅速地获知网络拥塞信息。同时，通过合理地利用机制，主动队列管理算法能够在保证算法性能的基础上，降低数据包分组的丢弃概率，保证队列长度的稳定，提高链路的利用效率，并且降低了网络时延。本章小结本章在研究拥塞控制基本原理的基础上，介绍了基于端到端的拥塞控制机制，对其原理研究现状及发展趋势做了详细的分析随后着重介绍了基于的拥塞控制机制，并对队列管理和队列调度分别做了重点分析。主动队列管理算法是队列管理算法的重要组成部分，在结合基于拥塞控制机制的基础上，使网络中间节点的拥塞控制能力得到增强，有效地参与到网络拥塞控制中，通过利用显式机制，对网络拥塞状况做出提前预判，随机地将拥塞信息发送给源端，在网络拥塞现象发生之前提前