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

课题来源： 指导教师给定课题研究的目的和意义：以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。如果R>C，则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。由于互联网的设计机制导致其缺乏“接纳能力”，因此在网络资源不足时不能限制用户数量，而只能靠降低服务质量来继续为用户服务，也就是尽力而为的服务。拥塞发生后，表现为端到端时延加大、数据包被丢弃概率增大、网络服务质量下降、甚至整个系统崩溃等。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=Throughput³Response Time 在上式中，一般取a=l。如果评价偏重吞吐量，则取a>l；如果评价偏重反应时间，则Power取a<l。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