拥塞控制机制与网络传输服务质量计算机毕业论文

课题来源： 指导教师给定课题研究的目的和意义：以TCP/IP协议为基础的Internet自从20世纪90年代以来，其网络规模、用户数量及业务量都呈现爆炸式的增长，新型网络应用也不断涌现，网络的参数(如激活的连接数、回路往返时间)动态变化，这些使得网络拥塞的状况愈加严重和复杂。拥塞容易造成传输时延和吞吐量等服务质量(QoS)性能指标下降，严重影响带宽、缓存等网络资源的利用率。因此，拥塞控制一直是网络研究领域的热点问题。网络拥塞控制的目的不是要完全避免拥塞的发生，而是通过拥塞控制，提高网络的性能及数据处理能力，保障网络的稳定和持续运行，并且保证数据传输的公平性。我们知道，网络拥塞的根本原因在于端系统发出的数据超出了网络的处理能力，而拥塞控制算法的基本思想则是解决这一问题，通常的方法就是TCP拥塞控制算法。以TCP为代表的端到端拥塞控制机制对互联网的稳定运行起了很大的作用。但是随着互联网规模的增长，互连网上的用户和应用都在快速增长，它在很多方面己经不能满足复杂网络中各种应用的需求，拥塞已经成为一个十分重要的问题。因此分析网络拥塞控制协议,寻找最优算法有着深远的目的和意义。国内外同类课题研究现状及发展趋势：随着计算机和通信技术的发展，Internet网络在过去十几年中经历了爆炸式的增长。但是，信息传送量的逐渐增大和网络组成的日益复杂使得网络负载超过了网络的处理能力，越来越严重的网络拥塞问题随之而来。互联网采用的是无连接的端到端数据包交换，提供尽力而为(best effort)的服务。端到端拥塞控制是目前Internet的一个研究热点。这种机制的最大优势是设计简单，可扩展性强。互联网在过去的十几年中经历了爆炸式的增长，这已经充分证明了这种设计机制的成功。然而这种优势并不是没有代价的，随着互联网用户数量的膨胀，网络的拥塞问题也越来越严重。例如由于队列溢出，互联网路由器会丢弃约10的数据包。在最初的TCP协议中只有流控制(flow control)而没有拥塞控制，接收端利用TCP报头将接收能力通知发送端。这样的控制机制只考虑了接收端的接收能力，而没有考虑网络的传输能力，导致了网络崩溃(congestion collapse)的发生。1986年10月，由于拥塞崩溃的发生，美国LBL到UC Berkeley的数据吞吐量从32 Kbps跌落到40 bps。据统计，互联网上95的数据流使用的是TCP/IP协议，因此，互联网上主要的互连协议TCP/IP的拥塞控制(congestion control)机制对控制网络拥塞具有特别重要的意义。拥塞控制是确保互联网鲁棒性(robustness)的关键因素，也是各种管理控制机制和应用(如多媒体通信中QoS控制、区分服务(differentiated services)的基础，因此关于互联网的拥塞控制问题一直是网络研究的一个热点，拥塞控制算法对保证Internet的稳定具有十分重要的作用。课题研究的主要内容和方法，研究过程中的主要问题和解决办法：目前拥塞控制的研究一般分为TCP层的拥塞控制和IP层的拥塞控制，TCP层的拥塞控制主要是基于窗口的和式增加积式减少的拥塞控制机制，TCP基于窗口的端到端拥塞控制对于Internet的鲁棒性起到了关键作用，并且在现实的互联网中，拥塞控制的大部分工作都是由TCP来完成的，所以研究TCP层的拥塞控制对于网络拥塞有相当大的意义。随着Internet本身的迅速发展，网络规模越来越庞大，结构越来越复杂，仅仅依靠TCP拥塞控制机制来提高网络服务质量还不够。网络必须参与资源的控制工作，因此需要采用路由器端的拥塞控制方法，即IP拥塞控制问题，通常也称之为队列管理机制，通过排队算法决定哪些包可以传输，通过丢弃策略决定哪些包被丢弃以此分配缓存。未来的网络拥塞控制的方向应该是，以TCP层拥塞控制为基础，结合IP层的队列管理策略，共同解决网络拥塞问题。第一：拥塞控制的基本知识研究。第二：TCP协议实现中一般都包含有四个相互关联的拥塞控制算法的研究：慢作。因此，仅仅依靠TCP协议无法控制拥塞，最有效的拥塞检测和回避是在路由器中实现的。第三：路由器中采用的拥塞控制算法通过检测缓冲区的使用情况及队列长度来判断拥塞，通过丢弃缓冲队列中的数据包来控制拥塞。 解决办法：查找资料、请教导师、请教学者课题研究起止时间和进度安排：起止时间：2012年1月22日2012年5月20日进度安排：2012年1月22日2012年3月1日 确定论文题目，收集资料,写开题报告。2012年3月2日2012年3月31日 收集资料、相关知识，对论文内容进行系统研究。2012年4月1日2012年4月15日 实现算法并应用，进行多次修改研究。2012年4月16日2012年5月1日 撰写论文，准备答辩。课题研究所需主要设备、仪器及药品：计算机外出调研主要单位，访问学者姓名：指导教师审查意见：指导教师 （签字） 2012年3 月 教研室（研究室）评审意见：_教研室（研究室）主任 （签字） 2012年3 月系（部）主任审查意见：_系（部）主任 （签字） 2012年3 月摘要：以TCP/IP协议为基础的Internet自从20世纪90年代以来，其网络规模、用户数量及业务量都呈现爆炸式的增长，新型网络应用也不断涌现，网络的参数(如激活的连接数、回路往返时间)动态变化，这些使得网络拥塞的状况愈加严重和复杂。拥塞容易造成传输时延和吞吐量等服务质量(QoS)性能指标下降，严重影响带宽、缓存等网络资源的利用率。因此，拥塞控制一直是网络研究领域的热点问题。Internet主要依赖TCP端到端拥塞控制来避免网络拥塞，以TCP为代表的端到端拥塞控制机制对互联网的稳定运行起了很大的作用。但是随着互联网规模的增长，互连网上的用户和应用都在快速增长，它在很多方面己经不能满足复杂网络中各种应用的需求，拥塞已经成为一个十分重要的问题。近年来，在拥塞控制领域开展了大量的研究工作，拥塞控制算法可以分为两个主要部分：在端系统上使用的源算法和在网络设备上使用的链路算法。在路由器中引入适当的队列管理机制，可以有效地对拥塞进行监测和预防，路由器中的拥塞控制策略己经成为一个研究热点。本文首先对拥塞现象的产生进行了说明，分析了拥塞现象产生的根源，总结了源算法和链路算法。接着，讨论了几种主要的TCP拥塞控制算法以及一些经典的路由器拥塞控制策略以及对比了这两种控制策略，并阐述了网络拥塞控制的部分最新研究方法和成果。通过归纳、总结互联网拥塞控制的研究现状，主要对TCP层的网络拥塞控制问题进行了分析与研究。然后，在此基础上，提出了一种改进的拥塞控制算法，通过实验结果分析，此算法减少了网络的丢包数和提高网络的吞吐量，最后，分析了进一步的研究方向。关键词：拥塞控制；算法；TCP/IP；路由器目 录第一章 引言11.1课题背景11.2网络中的拥塞现象及原因11.3 网络拥塞控制算法及存在的问题2第二章 拥塞现象及拥塞控制算法研究42.1 拥塞现象42.2 拥塞现象产生的原因52.3 拥塞控制算法的概况62.3.1 Internet的网络模型72.3.2拥塞控制算法设计的困难72.3.3拥塞控制算法7第三章 拥塞控制算法比较93.1 TCP/IP体系结构93.2 TCP层拥塞控制算法103.2.1 TCP Tahoe113.2.2 TCP Reno123.2.3 TCP New Reno123.2.4 TCP Sack123.2.5 TCP Vegas123.3 IP层拥塞控制算法133.3.1 先进先出（FIFO）133.3.2 公平排队（FQ）和加权公平排队（WFQ）133.3.3 随机检测算法（RED）143.2 两类算法比较153.5 其他拥塞控制算法163.5.1 基于方程的拥塞控制算法163.5.2 适应性虚拟队列163.5.3 TCP Westwood16第四章 拥塞控制算法改进184.1 各阶段算法改进184.1.1慢启动184.1.2“超时重传”和“快速重传”194.2 对目的端点主机的拥塞控制策略的改进224.3 对目的端点主机的拥塞控制策略的改进23第五章 结束语27参考文献28Abstract29第一章 引言1.1课题背景随着计算机和通信技术的发展，Internet网络在过去十几年中经历了爆炸式的增长。但是，信息传送量的逐渐增大和网络组成的日益复杂使得网络负载超过了网络的处理能力，越来越严重的网络拥塞问题随之而来。互联网采用的是无连接的端到端数据包交换，提供尽力而为(best effort)的服务。端到端拥塞控制是目前Internet的一个研究热点。这种机制的最大优势是设计简单，可扩展性强。互联网在过去的十几年中经历了爆炸式的增长，这已经充分证明了这种设计机制的成功。然而这种优势并不是没有代价的，随着互联网用户数量的膨胀，网络的拥塞问题也越来越严重。例如由于队列溢出，互联网路由器会丢弃约10的数据包。在最初的TCP协议中只有流控制(flow control)而没有拥塞控制，接收端利用TCP报头将接收能力通知发送端。这样的控制机制只考虑了接收端的接收能力，而没有考虑网络的传输能力，导致了网络崩溃(congestion collapse)的发生。1986年10月，由于拥塞崩溃的发生，美国LBL到UC Berkeley的数据吞吐量从32Kbps跌落到40bps。据统计，互联网上95的数据流使用的是TCP/IP协议，因此，互联网上主要的互连协议TCP/IP的拥塞控制(congestion control) 机制对控制网络拥塞具有特别重要的意义。拥塞控制是确保互联网鲁棒性(robustness)的关键因素，也是各种管理控制机制和应用(如多媒体通信中QoS控制、区分服务的基础，因此关于互联网的拥塞控制问题一直是网络研究的一个热点，拥塞控制算法对保证Internet的稳定具有十分重要的作用。1.2网络中的拥塞现象及原因 当在网络中存在过多的报文时，网络的性能会下降，这种现象称为拥塞。使用图1来描述拥塞的发生。当负载较小时，吞吐量的增长和负载相比基本呈线性关系，延迟增长缓慢；在负载超过Knee之后，吞吐量增长缓慢，延迟增长较快；当负载超过Cliff之后，吞吐量急剧下降，延迟急剧上升。由图1.1得出，负载在Knee附近时网络的使用效率最高。拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反应。在图1.1中就是使负载保持在Knee附近，和流控制相比，拥塞控制主要考虑端节点之间的网络环境，目的是使负载不超过网络的传送能力；而流控制主要考虑接收端，目的是使发送端的发送速率不超过接收端的接收能力。网络中的拥塞来源于网络资源和网络流量分布的不均衡性。拥塞不会随着网络处理能力的提高而消除。网络的吞吐量与通信子网负荷(即通信子网中正在传输的分组数)有着密切的关系。当通信子网负荷比较小时,网络的吞吐量(分组数/秒)随网络负荷(每个节点中分组的平均数)的增加而线性增加。当网络负荷增加到某一值后,若网络吞吐量反而下降,则表征网络中出现了拥塞现象。在一个出现拥塞现象的网络中,到达某个节点的分组将会遇到无缓冲区可用的情况,从而使这些分组不得不由前一节点重传,或者需要由源节点或源端系统重传。当拥塞比较严重时,通信子网中相当多的传输能力和节点缓冲器都用于这种无谓的重传,从而使通信子网的有效吞吐量下降。由此引起恶性循环,使通信子网的局部甚至全部处于死锁状态,最终导致网络有效吞吐量接近为零。 KneeCliff 吞吐量 负载 响应时间 负载 图1.1 负载与吞吐量、响应时间关系曲线网络发展到今天，其应用领域不断拓宽，各种应用模式不断涌现，像音频和视频这样的对网络资源要求较高的多媒体应用更是呈现出爆炸性的增长趋势。而目前的网络资源相对于快速增长的网络应用模式是远远不够的。因此如何使相对有限的网络资源更加高效的利用，尽最大可能满足这些应用需求，避免拥塞崩溃的发生。这正是拥塞控制研究的目的和意义。1.3 网络拥塞控制算法及存在的问题拥塞控制算法包含拥塞避免(congestion avoidance)和拥塞控制(congestion control)这两种不同的机制。拥塞控制是“恢复”机制，它用于把网络从拥塞状态中恢复出来；拥塞避免是“预防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟的状态下。由网络拥塞产生的原因可知，虽然拥塞的产生源于资源短缺，但单方面增加资源并不能避免拥塞的发生，有时甚至会加重拥塞程度。例如，增加网关缓存会增大报文通过网关的延迟，当数据包经过长时间的排队完成转发时它们早己超时，而源端认为这些数据包已经被丢弃，开始重传，但这些数据包仍在网络中传输，反而浪费了网络资源且加重了网络拥塞。又如，处理机的处理速率太慢可能导致网络拥塞，但单纯提高该处理器的性能，网络的瓶颈又会转移到其它地方，导致系统各部分的不匹配。总而言之，拥塞控制算法的设计存在以下几方面的困难：(1) 算法的分布性：拥塞控制算法的实现分布在不同的网络层次以及多个网络节点 中，采用分布式的拥塞控制算法可以降低单个节点的处理复杂度，同时提高网络的稳健性。(2) 算法的可扩展性：网络中各处的性能有很大的差异，对于不同的网络条件，如网络规模的变化，带宽的变化，链路传输时延的变化，不同的端系统状况，以及存在多种数据流时，拥塞控制算法都应具有相对较好的性能指标。(3) 算法的性能要求：拥塞控制算法对性能有很高的要求，包括算法的效率、公平性、稳定性、鲁棒性和收敛性。通常的拥塞控制策略只能达到部分的性能要求，因此对这些指标需要综合考虑。(4) 算法的易实现性：拥塞控制算法的设计与实现要尽可能简单，不仅要尽量减少附加的网络流量，而且要减少反馈信号的复杂度。同时拥塞控制算法的设计还必须尽可能降低该算法在网络节点的计算量和实现的复杂度。(5) 拥塞的复杂性：计算机网络已发展成为一个庞大的复杂性系统，其复杂性在于网络拓扑结构的复杂性，网络数据流的复杂性如自相似，自组织临界和拥塞相变现象等。目前，一些与复杂性研究相关的理论和方法被广泛地应用于网络拥塞演化规律的研究中，其中，网络动力学己经发展成为一个新的跨学科领域。拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控制算法的设计具有很高的难度。到目前为止，拥塞问题还没有得到很好的解决。第二章 拥塞现象及拥塞控制算法研究2.1 拥塞现象拥塞现象是指到达通信子网中某一部分的分组数量过多，使得该部分网络来不及处理，以致引起这部分乃至整个网络性能下降的现象，严重时甚至会导致网络通信业务陷入停顿，即出现死锁现象。这种现象跟公路网中经常所见的交通拥挤一样，当节假日公路网中车辆大量增加时，各种走向的车流相互干扰，使每辆车到达目的地的时间都相对增加(即延迟增加)，甚至有时在某段公路上车辆因堵塞而无法开动(即发生局部死锁)。 网络的吞吐量与通信子网负荷(即通信子网中正在传输的分组数)有着密切的关系。当通信子网负荷比较小时，网络的吞吐量(分组数/秒)随网络负荷(每个节点中分组的平均数)的增加而线性增加。当网络负荷增加到某一值后，若网络吞吐量反而下降，则表征网络中出现了拥塞现象。在一个出现拥塞现象的网络中，到达某个节点的分组将会遇到无缓冲区可用的情况，从而使这些分组不得不由前一节点重传，或者需要由源节点或源端系统重传。当拥塞比较严重时，通信子网中相当多的传输能力和节点缓冲器都用于这种无谓的重传，从而使通信子网的有效吞吐量下降。由此引起恶性循环，使通信子网的局部甚至全部处于死锁状态，最终导致网络有效吞吐量接近为零。 计算机网络(Computer network)就是把分布在不同地点的具有独立功能的多台计算机系统通过通信线路和网络设备互相连接在一起，按照一定的网络协议进行信息通信，实现资源共享的计算机通信系统，它是计算机技术与通信技术结合的产物。20世纪80年代出现的互联网(Internet)是现在全世界最大的计算机网络。以TCP/IP(Transfer control protocol/Internet protocol)网络协议为基础的互联网在过去几十年经历了爆炸式发展。1980年ARPA网(Internet的前身)只包含200台计算机，从1986年接入6000台计算机开始，5年后数量就达到了60万，一直到上一世纪末，全球互联网用户达到2亿多。现在互联网的容量与规模仍以惊人的速度继续向前发展。通过互联网可以轻易实现远程信息访问、用户间通讯、交互式娱乐、电子商务等。互联网在社会各个领域的广泛应用使得传统的信息获取、传送、存储和处理方式发生了根本性的变化，改变了人们的生活与工作方式，对世界经济发展和社会生活方式产生了重大影响。自从互联网诞生以来，网络资源和网络流量分布的不均衡使得拥塞问题一直困扰着其发展。伴随着网络规模的日益扩大和应用类型的丰富，网络拥塞也变得越来越严重。为易于扩展，网络端节点要求尽可能简单，其不对数据流的状态进行记录和管理，导致网络无法对用户的发送行为进行约束。当不存在一种对数据流进行隔离的机制并且用户又不对自身的发送行为进行约束时，网络的运行就面临着瘫痪的危险。如果不及时采用适当的方法来控制网络拥塞，网络的稳定性将无法得到保障。实际上，这个现象在八十年代初就已经出现，并被称为“拥塞崩溃”(Congestion collapse)。计算机网络中的链路容量、网络节点中的缓存和处理器等都是网络的资源，在某段时间内如果用户提供给网络的负载大于网络资源容量和网络节点的处理能力，网络便会产生阻塞，性能变坏，这就是网络中的拥塞现象。可以用如下关系式表示：资源需求网络可用资源网络产生拥塞时，网络的性能便会降低，甚至有可能使整个系统发生崩溃，具体表现在网络吞吐量和效率的降低、路由器缓冲队列的急剧增加、报文延时的增加、报文的丢失、报文到达的延时抖动剧烈等方面。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急剧下降。图1.1清楚地表述了网络负载与吞吐量和延迟之间的关系。当网络的负载较小时，随着负载增加，吞吐量相应增加。当负载接近网络的容量时，吞吐量将会停止增加，如果负载继续增加，就会导致分组丢弃，这时网络的吞吐量会突然降低，并接近于0。把吞吐量接近于0的现象称为拥塞崩溃(congestion collapse)，并且把拥塞崩溃点称为cliff，因为负载超过这一点后吞吐量会突然降低，而把负载增加后吞吐量增加很少但传输延迟迅速增加的那点称为拥塞临界点(knee)。而拥塞避免(congestion avoidance)工作在knee处，它鼓励用户增加负载，只要不会使延迟增加就可以。当网络轻载时，随着负载的增加，吞吐量随之迅速增加，延迟增长缓慢；当过了Knee点之后，负载增加时吞吐量增加趋于平缓， 延迟增长较快；当超过Cliff点后负载增加时吞吐量急剧下降，延迟急剧上升。拥塞时网络的具体表现为数据包经受的时延增大，丢弃概率增高。而发送放在遇到大时延时进行的不必要重传会引起路由器利用其链路带宽来转发不必要的分组拷贝。数据包丢弃概率的增加也会引起发送方执行重传因缓存溢出而丢弃的数据包。这些都导致链路传输容量的浪费，有效利用率降低。2.2 拥塞现象产生的原因拥塞发生的原因是“需求”大于“供给”。网络中有限的资源由多个用户共享使用。由于没有“接纳控制”算法，网络无法根据资源的情况限制用户的数量；缺乏中央控制，网络也无法控制用户使用资源的数量。目前Internet上用户和应用的数量都在迅速增长。如果不使用某种机制协调资源的使用，必然会导致网络拥塞。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞的发生，有时甚至会加重拥塞程度。例如：增加网关缓冲会增大报文通过网关的延迟，如果总延迟超过端系统重传时钟的值，就会导致报文重传，反而加重了拥塞。拥塞总是发生在网络中资源“相对”短缺的位置。拥塞发生位置的不均衡反映了Internet的不均衡性。首先是资源分布的不均衡。图2.1(a)中带宽的分布是不均衡的，当以1Mb/s的速率从S向D发送数据时，在网关R会发生拥塞。其次是流量分布的不均衡。图2.1(b)中带宽的分布是均衡的，当A和B都以1Mb/s的速率向C发送数据时，在网关R也会发生拥塞。Internet中资源和流量分布的不均衡都是广泛存在的，由此导致的拥塞不能使用增加资源的方法来解决。 DRS 1Mb 100Kb (a)AC 1Mb 1MbRBD 1Mb 1Mb (b) 图2.1 拥塞产生原因示意网络产生拥塞的根本原因在于用户提供给网络的负载大于网络资源的容量和处理能力。拥塞产生的直接原因主要表现在如下三点：(1) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端口就会建立排队。如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流更是如此。增加存储空间在某种程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥塞只是会变得更坏，而不是更好，因为在网络鬼数据包经过长时间排队完成转发时，它们早已超时，发送端认为它们己经被丢弃，而这些数据包还会继续向下一个路由器转发，从而浪费网络资源且加重了网络拥塞。(2) 带宽容量不足。根据香农信息理论，任何信道带宽最大值即信道容量C=Blog2(1+S/N)(其中N为信道白噪声的平均功率，S为信源的平均功率，B为信道带宽)。所有信源发送的速率R必须小于或等于信道容量C。如果RC，则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。由于互联网的设计机制导致其缺乏“接纳能力”，因此在网络资源不足时不能限制用户数量，而只能靠降低服务质量来继续为用户服务，也就是尽力而为的服务。拥塞发生后，表现为端到端时延加大、数据包被丢弃概率增大、网络服务质量下降、甚至整个系统崩溃等。1984年Nagle报告了由于TCP连接中没有必要的重传所诱发的拥塞崩溃，1986-1987年间这种现象曾经多次发生，严重在端到端拥塞控制的实现中包括终端系统机制和路由器机制两个有机部分。目前在Internet中，最主要的拥塞控制机制是由终端系统的TCP协议完成的，这也是网络能保持鲁棒性的主要原因。本文研究以TCP层拥塞控制为基础，结合IP层的队列管理策略，共同解决网络拥塞问题。2.3 拥塞控制算法的概况拥塞控制方法：(1) 缓冲区预分配法。该法用于虚电路分组交换网中。在建立虚电路时，让呼叫请求分组途经的节点为虚电路预先分配一个或多个数据缓冲区。若某个节点缓冲器已被占满，则呼叫请求分组另择路由，或者返回一个“忙”信号给呼叫者。这样，通过途经的各节点为每条虚电路开设的永久性缓冲区(直到虚电路拆除)，就总能有空间来接纳并转送经过的分组。此时的分组交换跟电路交换很相似。当节点收到一个分组并将它转发出去之后，该节点向发送节点返回一个确认信息。该确认一方面表示接收节点已正确收到分组，另一方面告诉发送节点，该节点已空出缓冲区以备接收下一个分组。上面是“停一等”协议下的情况，若节点之间的协议允许多个未处理的分组存在，则为了完全消除拥塞的可能性，每个节点要为每条虚电路保留等价于窗口大小数量的缓冲区。这种方法不管有没有通信量，都有可观的资源(线路容量或存储空间)被某个连接占有，因此网络资源的有效利用率不高。这种控制方法主要用于要求高带宽和低延迟的场合，例如传送数字化语音信息的虚电路。(2) 分组丢弃法。该法不必预先保留缓冲区，当缓冲区占满时，将到来的分组丢弃。若通信子网提供的是数据报服务，则用分组丢弃法来防止拥塞发生不会引起大的影响。但若通信子网提供的是虚电路服务，则必须在某处保存被丢弃分组的备份，以便拥塞解决后能重新传送。有两种解决被丢弃分组重发的方法，一种是让发送被丢弃分组的节点超时，并重新发送分组直至分组被收到；另一种是让发送被丢弃分组的节点在尝试一定次数后放弃发送，并迫使数据源节点超时而重新开始发送。但是不加分辨地随意丢弃分组也不妥，因为一个包含确认信息的分组可以释放节点的缓冲区，若因节点元空余缓冲区来接收含确认信息的分组，这便使节点缓冲区失去了一次释放的机会。解决这个问题的方法可以为每条输入链路永久地保留一块缓冲区，以用于接纳并检测所有进入的分组，对于捎带确认信息的分组，在利用了所捎带的确认释放缓冲区后，再将该分组丢弃或将该捎带好消息的分组保存在刚空出的缓冲区中。(3) 定额控制法。这种方法在通信子网中设置适当数量的称做“许可证”的特殊信息，一部分许可证在通信子网开始工作前预先以某种策略分配给各个源节点，另一部分则在子网开始工作后在网中四处环游。当源节点要发送来自源端系统的分组时，它必须首先拥有许可证，并且每发送一个分组注销一张许可证。目的节点方则每收到一个分组并将其递交给目的端系统后，便生成一张许可证。这样便可确保子网中分组数不会超过许可证的数量，从而防止了拥塞的发生。2.3.1 Internet的网络模型 拥塞现象的发生和Internet的设计机制有着密切的联系。Internet的网络模型可以用以下几点来抽象：(1) 报文交换(packet-switched)网络。和电路交换(circuit-switched)相比，报文交换通过共享提高了资源的利用效率。但在共享方式下，如何保证用户的服务质量是一个很棘手的问题；在报文交换网络中可能出现报文“乱序”现象，对乱序报文的处理增加了端系统的复杂性。(2) 无连接(connectionless)网络。Internet的节点之间在发送数据之前不需要建立连接。无连接模型简化了网络的设计，在网络的中间节点上不需要保存和连接有关的状态信息。但是使用无连接模型难以引入“接纳控制”(admission control)算法，在用户需求大于网络资源时难以保证服务质量；在无连接模型中对数据发送源的追踪能力很差，给网络的安全带来了隐患；无连接也是网络中乱序报文出现的一个主要原因。(3) best-effort的服务模型。best-effort即网络不对数据传输的服务质量提供保证。这个选择和早期网络中的应用有关。传统的网络应用主要是FTP、Telnet、SMTP等，它们对网络性能(带宽、延迟、丢失率等)的变化不敏感，best-effort模型可以满足需要。但best-effort模型不能很好满足新出现的多媒体应用的要求，这些应用对延迟、速率等性能的变化比较敏感。这要求网络在原有服务模型的基础上进行扩充。2.3.2拥塞控制算法设计的困难 拥塞控制算法的设计困难体现在以下方面：(1) 算法的分布性。拥塞控制算法的实现分布在多个网络节点中，必须使用不完整的信息完成控制，并使各节点协调工作，还必须考虑某些节点工作不正常的情况。(2) 网络环境的复杂性。Internet中各处的网络性能有很大的差异，算法必须具有很好的适应性；另外由于Internet对报文的正确传输不提供保证，算法必须处理报文丢失、乱序到达等情况。(3) 算法的性能要求。拥塞控制算法对性能有很高的要求，包括算法的公平性、效率、稳定性和收敛性等。某些性能目标之间存在矛盾，在算法设计时需要进行权衡。(4) 算法的开销。拥塞控制算法必须尽量减少附加的网络流量，特别是在拥塞发生时。在使用反馈式的控制机制时，这个要求增加了算法设计的困难。算法还必须尽量降低在网络节点(特别是网关)上的计算复杂性。目前的策略是将大部分计算放在端节点完成，在网关上只进行少量的操作，这符合Internet的基本设计思想。2.3.3拥塞控制算法在设计和比较拥塞控制算法时，需要一定的评价方法。从用户的角度出发，可以比较端系统的吞吐率、丢失率和延迟等指标，这些是用户所关心的。由于拥塞控制算法对整个网络系统都有影响，在评价算法时更应该从整个系统的角度出发进行考虑。两个重要的评价指标是资源分配的效率和资源分配的公平性。 1、资源分配的效率资源分配的效率可以用Power函数来评价。Power函数定义为： Power=ThroughputResponse Time 在上式中，一般取a=l。如果评价偏重吞吐量，则取al；如果评价偏重反应时间，则Power取al。Knee Cliff Power Load 图2.2 Power函数示意图2.2示意当负载位于Knee时Power取最大值。使用Power函数有一定的局限性。它主要基于M/M/1队列的网络，并假设队列的长度为无穷。Power函数一般在单资源、单用户的情况下使用。 2、资源分配的公平性多用户情况下需要考虑资源分配的公平性。公平性评价的主要方法包括Max-Min Fairness，Fairness Index等。Max-min fairness被非正式的定义为：每个用户的吞吐量至少和其它共享相同瓶颈的用户的吞吐量相同。Max-Min Fairness是一种理想的状况，但是它不能给出公平的程度。Fairness Index提供了一个计算公式，可以计算公平的程度。它定义为： Fairness Index的计算结果位于0和l之间，并且结果不受衡量单位的影响。它的一个性质是：如果n个用户中只有k个用户平均共享资源，而另(n-k)个用户没有任何资源，计算结果为k/n。由于公平性是针对资源分配而言的，所以在评价前首先要确定“资源”的含义。目前大多数研究在评价公平性时都针对吞吐量，这是从用户的角度出发考虑的，并不完全适合网络中的资源状况。网络中的资源包括链路带宽、网关的缓冲和网关的处理能力等，在考察公平性时应当将这些资源的分配情况综合考虑。第三章 拥塞控制算法比较3.1 TCP/IP体系结构TCP/IP(Transmission Control Protocol/Internet Protocol)即传输控制协议互连网络协议，是ARPANET最有影响力的研究成果之一，现时的TCP/IP协议已成为一组完整的协议，构成网络体系结构，除传输控制协议(TCP)和互连网络协议(IP)外，还包括工具性协议、管理性协议及应用协议等多种其它协议，TCP/IP协议己经成为事实上的因特网上的通信标准，也是事实上的国际标准和工业标准。TCP/IP协议的体系结构可以用一个四层的分层模型来描述，分成网络接口层、IP层、运输层和应用层。如图所示：应用层运输层（TCP/UDP层）IP层网络接口层 图3.1TCP/IP体系结构网络接口层又称数据链路层，定义了特定介质的物理连接特性，及在该介质上发生、接收的信息帧的格式。其作用是传输经IP层处理过的信息，并提供一个主机与实际网络的接口，TCP/IP支持的数据链路技术很多，其特色在于它可以在任何一种物理网络上运行。IP层采用的是IP协议，负责IP数据报从主机发往任何网络，到达其目的地。IP层为每一个IP数据报分配一个全网惟一的传送地址(IP地址)，并据此IP地址段的信息把IP数据报转发到其目的地。另外IP层还具有分组路由和拥塞控制等功能。 运输层(TCP/UDP层)提供的是端到端的通信功能，主要由两个协议构成。TCP协议提供的是面向连接的、可靠的传输服务；用户数据报协议UDP提供的是无连接的、不可靠的传输服务。TCP协议还具有差错检测、流量控制、拥塞控制等功能。应用层包含了所有的高层协议，例如：远程登录的虚拟终端协议(Telnet)、文件传输协议(FTP)、Web传输协议(HTTP)和邮件传输协议(SMTP)等，为各种用户提供了所需的服务。目前拥塞控制的研究一般分为TCP层的拥塞控制和IP层的拥塞控制，TCP层的拥塞控制主要是基于窗口的和式增加积式减少的拥塞控制机制，TCP基于窗口的端到端拥塞控制对于Internet的鲁棒性起到了关键作用，并且在现实的互联网中，拥塞控制的大部分工作都是由TCP来完成的，所以研究TCP层的拥塞控制对于网络拥塞有相当大的意义。随着Internet本身的迅速发展，网络规模越来越庞大，结构越来越复杂，仅仅依靠TCP拥塞控制机制来提高网络服务质量还不够。网络必须参与资源的控制工作，因此需要采用路由器端的拥塞控制方法，即IP拥塞控制问题，通常也称之为队列管理机制，通过排队算法决定哪些包可以传输，通过丢弃策略决定哪些包被丢弃以此分配缓存。未来的网络拥塞控制的方向应该是，以TCP层拥塞控制为基础，结合IP层的队列管理策略，共同解决网络拥塞问题。 NSPSMHTTPFTPDNSTELENT. UDP TCP RARP ARP IP ICMP局域网X.25网无线网电话网.应用层运输层 IP层网络接口层图3.2 TCP/IP体系结构中各层所应用的主要协议口3.2 TCP层拥塞控制算法互联网最初源于美国国防部的ARPANET计划。上世纪60年代中期正是冷战的高峰，美国国防部希望有一个命令和控制网络，以确保在核战争的条件下幸免于难，而传统基于电路交换的电话网络则过于脆弱。国防部指定其下属的高级研究计划局解决这个问题，从而诞生ARPANET，其最大特点是采用无连接的端到端报文交换服务。到了80年代中期，演变为互联网。TCP协议最初只是作为NSFNET的程序规范，即RFC 793，这也是最早的较为完整且齐全的TCP规范。这个规范简单描述了如何进行主机到主机的可靠传输，并描述了传输控制协议执行的功能，相应的实现程序及程序接口。TCP协议在设计之初就被赋予了很高的使命，需要成为报文交换计算机网络和这些网络互联系统中的高可靠性传输协议。需要明确的是，网络中的可靠传输包括两方面：首先是数据的正确，由于以前的传输介质质量很差，所以在传输层及以下各层协议中都实现了校验和计算；其次是数据的完整保序，这个特性需要TCP执行复杂的操作来实现，通常我们强调TCP的可靠传输时主要指后者。目前在Internet上实际使用的拥塞控制基本上是建立在TCP窗口控制基础之上的，据统计，Internet上的95的数据流使用的是TCP协议，因此TCP拥塞控制一直是网络拥塞控制研究的重点。TCP拥塞控制的基本框架是在文中提出的，文中Van Jacobson指出用显式的方法来实现基于窗口的运输层协议会导致端系统对网络拥塞的错误反应，并提出了一系列算法来解决这一问题，这些算法包括：RRT的估计重传计数器的指数回退、慢启动、拥塞窗口的动念调整等。正是这些算法奠定了TCP拥塞控制的基础。TCP/IP一般通过Internet串行线路协议SLIP或点对点协议PPP在串行线上进行数据传送。TCP/IP协议的基本传输单位是数据包 (datagram)。TCP协议负责把数据分成若干个数据包/段，并给每个数据包加上包头，IP协议在每个包头上再加上接收端主机地址，这样数据找到自己要去的地方。如果传输过程中出现数据丢失、数据失真等情况，TCP协议会自动要求数据重新传输并重新组包。TCP协议保证数据传输的质量，总之IP协议保证数据的传输。数据在传输时每通过一层就要在数据上加个包头，其中数据供接收端同一层协议使用，而在接收端每经过一层要把用过的包头去掉，这样来保证传输数据的格式完全一致。TCP/IP协议需要针对不同的网络进行不同的设置，且每个节点一般需要一个“IP地址”、一个“子网掩码”、一个“默认网关”。不过可以通过动态主机配置协议（DHCP），给客户端自动分配一个IP地址，这样避免了出错也简化了TCP/IP协议的设置，我们可以指定一台计算机具有多个IP地址，因此在访问互联网时不要以为一个IP地址就是一台计算机；另外通过特定的技术，也可以使多台服务器共用一个IP地址，这些服务器在用户看起来就像一台主机似的。在TCP/IP中所有的协议都被封装在IP分组中通过IP网间网传输。IP是一个路由协议这就意味着使用IP通信的两个节点不必连接到同一物理线路上(不进行路由)。拥塞控制的方法，无论什么形式都可以分为两类：开环控制和闭环控制。开环控制是预先设计一个好的网络，确保它不会发生拥塞，而网络在运行过程中不再采取措施。比较典型的例子就是资源预留协议(RSVP)，这类控制机制较适用于简单的音频和活动图像业务。但是网络的业务流量通常是很难精确控制对于复杂的网络系统来说是远远不够的。显然，对网络这样不断变化的复杂系统，开环系统并不是理想的选择。TCP是目前Internet上应用广泛的传输层协议，实施拥塞控制是TCP的两个主要任务之一，由于IP层在发生拥塞时不向端系统提供任何显式的反馈信息，因而TCP拥塞控制采用的是基于窗口的端到端的闭环控制方式。闭环控制能够根据网络中反馈至端系统的拥塞指示信息，依据一定的控制策略，及时调整源端系统的数据传输速率，避免网络状况的恶化，既保证了传输的质量又能充分利用网络资源。在TCP拥塞控制的算法中，有以下几个重要参数：拥塞窗口(cwnd)：拥塞控制的关键参数，控制源端在拥塞情况下一次最多能发送多少数据包。通告窗口(awnd)：接收端对源端发送窗口大小所做的限制，在建立连接时由接收方通过ACK确认捎带给源端。慢启动阈值(ssthresh)：用来控制源端从慢启动阶段转换到拥塞避免阶段的门限值。回路响应时间(RTT)：一个数据包从源端发送到接收端，直至源端收到目的端对该数据包确认信息所经历的时间间隔。超时重传计数器(RTO)：描述数据包从发送到失效的时间间隔，是源端用来判断数据包是否丢失和网络拥塞的重要参数，通常设为2RTT或5RTT。TCP的拥塞控制由慢启动、拥塞控制、快速重传和快速恢复四个核心算法组成。这四个基本算法互相联系，经过大量的事实证明，它对Internet上大批量文件传输等服务具有良好的适应性，成为目前在Internet上主要使用的端系统拥塞控制机制。此后的TCP拥塞控制方法基本上都是在此基础上的一些改进。以下是对这些改进中的典型算法的分析。3.2.1 TCP TahoeTahoe算法由3个主要部分组成，和式增加积式减少(AIMD)、慢启动、快速重传。“和式增加”用来谨慎地探测端到端路径上的可用带宽，具体表现为TCP发送方在无丢包事件发生时，每收到一个ACK，就将拥塞窗口增加一点，直到丢包事件发生，这个线性增长阶段也称为拥塞避免。“积式减少”方法在丢包事件发生时将当前的拥塞窗口值减半，这样就降低了发送方的发送速率，从而减轻拥塞程度。慢启动是数据发送的初始化阶段，发送方以很慢的速率开始发送，但以指数的速度快速增加其发送速率，从而减小初始阶段因发送方发送窗口过小而造成的带宽浪费。快速重传是当发送方收到3个冗余的ACK而检测到丢包时不必等到重传超时而立即重传丢失的包。这些方法正是TCP拥塞控制的基础，以后的各种改进都依赖于此基础。3.2.2 TCP RenoTCP Reno是在Tahoe的基础上增加了“快速恢复”阶段。和Tahoe相比较，Reno在快速重传后并不将拥塞窗口减至1MSS，进入慢启动阶段。而是将拥塞窗口减半，进入拥塞避免阶段，这是因为与发生超时事件不同，收到冗余的ACK表明发送的其它包已经被接收方收到，两个端系统间仍有数据的流动，网络处于轻度拥塞。因此，发送端直接将拥塞窗口减至1MSS是不合适的，但Reno算法也存在缺点，当发送端检测到拥塞后，要重传数据包丢失到检测到丢失时发送的全部数据包，这其中包括已正确传输到接收端，不必重传的包。下面的New Reno和Sack算法正式针对Reno算法的这一缺点的改进。3.2.3 TCP New RenoNew Reno对Reno的改进是通过尽量避免Reno在快速恢复阶段的许多重传超时，利用一个ACK来确定部分发送窗口，立即重传余下的数据包，从而提高网络性能。目前，在Internet中最广泛使用的是New Reno算法。然而New Reno算法也存在着不足，文分析并指出了New Reno在高速远距离网络中不能有效利用带宽的不足，并给出了解决方法。3.2.4 TCP Sack如前所述，Sack算法也是对Reno的改进，当检测到拥塞后，不用重传数据包丢失到检测到丢失时发送的全部数据包，而是对这些数据包进行有选择的确认和重传，从而避免不必要的重传，减少延时，提高网络吞吐量。由于使用选择重传，所以在一个窗口中数据包多丢失的情况下，Sack性能优于New Reno，但是Sack的主要缺点是要修改接收端TCP。 3.2.5 TCP VegasTCP Vegas算法和以前的算法大不相同，它是通过观察以前TCP连接中的RRT值的改变来控制拥塞窗口的，如果RRT值变大，TCP Vegas就认为网络发生拥塞，就减小拥塞窗口；反之，则增大拥塞窗口。这样做的好处是拥塞控制机制的出发只和RRT的改变有关，而与包的具体时延无关。为了提高吞吐率、降低分组丢弃率，TCP Vegas采用了3种与众不同的技术：(1) 新的重传机制，它将引发重传的重复应答(ACK)数从3个减少到2个或者1个，因此TCP能够对分组丢弃做出更快速响应。(2) 新的拥塞避免机制，它改变了TCP Reno、TCP Tahoe等版本中通过分组丢弃来检测网络拥塞的基本思想，而是通过观察己发送分组的RRT的变化来判断网络的拥塞状况，即：如果观察到RTT变大，则认为网络开始拥塞，因此减小发送窗口值，如果RRT变小，TCP Vegas认为网络正变得畅通，因此增大发送窗口值。(3) 扩展的“慢启动”(slow-start)机制，在Reno等版本的“慢启动”阶段，发送窗13以指数增长方式更新，而Vegas“慢启动”阶段的发送窗口增长速度为Reno等版本的1/2，主要目的是在这一阶段利用(2)所描述的方法检测和避免拥塞。由于TCP Vegas只和RTT的改变有关，RRT的准确度对于Vegas来说非常重要，事实上，在其实现中也采取了许多措施来保证RTT计量的精确度，如更细粒度的时问计算等。但是，它忽略了一个事实，即TCP分组长度对于RTT是有影响的， 相同网络条件下，较大TCP分组的RTT会较大。TCP Vegas虽然在一定程度上提高了吞吐量，降低了丢包率，但是存在错误估算往返传播时延的可能，从而导致算法性能下降的问题。表3.1 TCP典型拥塞算法比较优点缺点TCP Tahoe建立了TCP拥塞控制的基础，避免了拥塞崩溃的发生没有快速恢复，轻度拥塞时，拥塞窗口减小过太（减至1）降低了吞吐量TCP Reno增加r快速恢复，轻度拥塞时候保持较高拥塞窗口检测到丢包，重传所有丢失与检测到丢事件所有的包TCP New Reno利用一个ACK确认部分发送窗口，避免了过多的重传在高速网络中不能有效利用带宽（其实这也是所有现行TCP共同的缺点）TCP Sack检测到拥塞时，选择性的重传包，避免了不必要的重传要修改TCP接收端，实现复杂3.3 IP层拥塞控制算法TCP基于窗口的拥塞控制机制对于Internet的鲁棒性起到了关键性的作用。然而，随着Internet本身的迅猛发展，其规模越来越庞大，结构也日趋复杂，研究者们也认识到仅仅依靠TCP端到端的拥塞控制是不够的，网络也应该参加资源的控制工作。网络本身要参与到拥塞控制中，已经成为了一个不可回避的问题。现在，IP层拥塞控制的研究也越来越多已经形成了一个新的热点研究方向。IP层拥塞控制就其本质来说是通过对路由器缓冲区队列中的分组实施调度和管理来影响TCP拥塞控制的动态性能以达到目的的。已经出现了一系列的队列调度和管理的算法来实现拥塞控制。下面我们会对其中的一些典型算法进行详细描述。3.3.1 先进先出（FIFO） FIFO又叫先到先服务(FCFS)，即第一个到达的包将被首先服务由于路由器的缓存总是有限的，当缓冲区满后，随后到达的包将被丢弃。由于FIFO总是丢弃到达队尾的包，所以经常和去尾(Drop-Tail)算法在概念上被混淆。FIFO是一种包的调度策略，Drop-Tail是一种包的丢弃策略。由于FIFO和Drop-Tail实施起来比较简单，因而目前去尾的先入先出是Internet上最广泛使用的队列调度管理方式。然而去尾的FIFO自身存在一些问题，例如：它不能区分不同的数据流，也不提供强制数据流遵守拥塞控制的机制，这就有可能让某些数据流强占大量带宽，引发公平性问题。例如UDP