绪论
计算机网络在过去十几年中经历了爆炸式的增长，随着互联网技术的迅猛发展，越来越多的用户使用网络中的资源，虽然网络带宽等资源也在不断增加!但与日益增长的用户数量比起来仍然不能满足用户的需求，网络拥塞问题逐渐暴露出来。网络拥塞问题得到全世界的关注始于1986年10月，当时美国LBL到UC Berkeley网络由于发生严重的网络拥塞导致网络崩溃，使得数据吞吐量从32kbps跌落到40bps，至此以后，拥塞控制成为一个热点研究领域。如今,网络拥塞已经成为制约网络发展和应用的一个瓶颈，如何更好的预防和控制拥塞，使网络具有低丢包率和低时延的同时达到资源的最大效用是近年来网络研究的热点问题。
目前Internet实际使用的拥塞控制机制基本建立在TCP的窗口控制基础之上，IP层的路由器所起作用相对较小。根据MCI的统计，互联网上95%的数据流使用的是TCP/IP协议。TCP/IP的拥塞控制机制对控制拥塞具有特别重要的意义，是确保Internet鲁棒性（robustness）的关键因素，基于 TCP/IP的网络拥塞控制机制是一个复杂而艰难的任务。在近十年中学术界对此问题做了大量的研究，进行了不少的理论方面的实验，产生了许多非常有用的结果。
1 TCP/IP 协议概述早在70 年代中期, Appanet(互联网的前身“阿帕网”) 为了实现异种网络之间的互联与互通,推出了TCP/ IP 体系结构和协议规范。时至今日, TCP/IP 协议已经成为了Internet 的通信标准,并由单纯的TCP/ IP协议发展成为一系列以IP 为基础的TCP/ IP 协议簇。TCP/ IP协议簇为互联网提供了基本的通信机制。TCP/ IP 以其两个主要协议———传输控制协议( TCP) 和网络互联协议( IP) 而得名。TCP 协议提供面向连接的、可靠的、全双工的、点对点的通信服务,它可以保证数据按照顺序、没有重复地、可靠地到达。由于TCP 建立的连接是由软件实现的逻辑上的连接而并非物理连接,故TCP 建立的连接叫做虚连接(virtual connection) 。互联网采用的是无连接的端到端数据包交换,提供“尽力而为”(best effort) 服务模型的设计机制。这种机制的最大优势是设计简单,可扩展性强。互联网在过去的十几年中经历了爆炸式的增长,这已经充分证明了这种设计机制的成功。然而这种优势并不是没有代价的,随着互联网用户数量的膨胀,网络的拥塞问题也越来越严重。例如由于队列溢出,互联网路由器会丢弃约10 %的数据包。据统计,互联网上95 %的数据流使用的是TCP/ IP 协议,因此,互联网上主要的互连协议TCP/ IP 的拥塞控制(congestioncontrol) 机制对控制网络拥塞具有特别重要的意义。拥塞控制是确保互联网鲁棒性( robustness) 的关键因素,也是各种管理控制机制和应用的基础,因此关于互联网的拥塞控制问题一直是网络研究的一个热点。
2 网络拥塞的定义及产生的原因
2.1 网络拥塞
当主机传送到通信子网中的分组数量在其传输容量之内时，它们将全部传送到目的地。然而在系统的运行过程中，会出现网络通信故障，或网络负载超过了可用资源，出现数据包丢失，导致传输延时增大，网络吞吐量下降甚至网络完全瘫痪等现象，即发生网络拥塞。在网络发生拥塞时,会导致吞吐量下降,严重时会发生“拥塞崩溃”( congestion collap se)现象。由于Internet采用的是统计复用( StatisticalMultiplexing) 技术, 大量的数据流共享一条链接,其运行环境在不断发生变化, 基于TCP/IP协议栈的网络通信协议是Internet中的主流通信协议, 这种网络采用的是尽力而为( Best- Effort) 的服务模型, 所有的数据流被不加区分地在网络中传输, 网络无法给用户一个定量的性能指标,如吞吐量、时延、丢失率等, 因此, 在目前网络带宽有限, 数据传输的需求量远远超过网络的瓶颈带宽时, 必定会产生拥塞, 此拥塞控制机制显得尤为重要。我们用图1来描述拥塞的发生。当负载达到网络容量时,吞吐量呈现出缓慢增长,而响应时间急剧增加,这一点称为Knee。如果负载继续增加,路由器开始丢包,当负载超过一定量时,吞吐量开始急剧下降,这一点称为Cliff。拥塞控制机制实际上包含拥塞避免( congestion avoidance)和拥塞控制( con-gestion control)两种策略。拥塞避免的目的是使网络运行在Knee附近,避免拥塞的发生;而拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反应,目的则是使得网络运行在Cliff的左侧区域。前者是一种“预防”措施,文持网络的高吞吐量、低延迟状态,避免进入拥塞;后者是一种“恢复”措施,使网络从拥塞中恢复过来,进入正常的运行状态。在图1中就是使负载保在Knee附近。
2.2 拥塞产生的原因网络产生拥塞的根本原因在于用户提交给网络的负载（LOAD）大于网络资源节点容量和处理能力（overload）。拥塞发生时，网络系统会表现出数据包时延增加、丢弃概率增大、上层应用系统性能下降等。下图2显示了拥塞发生的情况。
拥塞产生的直接原因有以下3点：
( 1) 存储空间不足。
几个输入数据流共同需要同一个输入端口, 在这个端口就会建立排队, 如果没有足够的存储空间, 数据包就会丢弃, 对突发数据流更是如此。增加存储空间在一定程度上可以缓解这一矛盾, 但如果路由器有无限存储空间, 拥塞只可能变得更坏, 而不是更好-----因为网络中的数据包经过长时间排队后才通过路由器完成转发, 均已远远超时,源端会认为它们已经被丢弃,但实际上,这些数据包还在继续向下一个路由器转发,从而造成网络资源的浪费,加剧了网络拥塞。
( 2) 带宽不足。
低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论, 在网络低速链路处会形成带宽瓶颈, 当其满足不了所有信源带宽要求时, 网络就会发生拥塞。
( 3) 处理器能力弱、速度慢。
如果路由器的CPU在执行排队缓存、更新路由表等功能时, 处理速度跟不上高速链路, 也会产生拥塞。同样, 低速链路对高速CPU也会产生拥塞。
分析网络的拥塞问题，需要对以上3点原因综合考虑。例如，低速链路对高事CPU也会产生拥塞，提高链路速率而不改变处理器，只会转移网络瓶颈，而不能避免拥塞，因此拥塞往往是系统各部分不匹配的结果。而随着网络规模的膨胀和复杂度的增加，要求一个数据流传输过程中涉及的各个部分达到完全匹配是几乎不可能实现的。对于频繁发生的数据传输业务，这样的匹配就完全不可能实现。拥塞是不可避免的，而拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的缓存，它就必须丢弃新到的数据包，当数据包丢弃时，源节点会重传该包。由于没有得到确认，源节点端只能保留数据包，结果缓存会进一步消耗，加重拥塞。
因此, 网络中拥塞现象发生的根本原因是“需求”大于“供给”。网络中有限的资源由多个用户共享使用。由于没有“接纳控制”策略, 网络无法根据资源的情况限制用户的数量; 同时, 互联网络是一个分控制系统, 由于缺乏中央集成控制, 网络无法控制用户使用资源的数量。所以，采用合理的算法与机制确保网络不因传入数据流过大耗尽网络资源节点而导致崩溃，就成为极为重要的工作。
3 拥塞控制机制及其分类3.1 网络拥塞控制机制技术通过上述分析可以知道网络拥塞是不可完全避免的。只能采取恰当的算法与机制来避免网络不会因传入数据过大而耗尽网络资源节点，这种技术就是拥塞控制技术。
网络传输控制技术包括分段与重组、连接控制、按序交付、流量控制、差错控制、寻址、多路复用、传输服务等几个方面。目前的绝大多数的网络是基于TCP/IP协议的，这个协议经过长期的应用实践，可靠性和稳定性都得到认可。因此当前研究网络传输控制的重点是在TCP/IP网络的拥塞控制上，探求如何通过有效辟免拥塞的发生达到提高网络传输的服务质量。
3.2 拥塞控制技术的目标
拥塞控制的主要目标是控制进入网络的数据流量!保证通信网络不会被用户发送的数据流阻塞! 并合理地使用瓶颈资源"拥塞控制可以在网络协议的各个层次上实施"由于数据链路层靠近拥塞的发生点! 所以在数据链路层进行控制可以快速的对拥塞做出反应! 但它只能对短期的拥塞现象进行控制" 一般来说!不同网络层次中的控制机制具有不同的目标!拥塞现象持续的时间越长!实现控制的层次也应该越高" 所以,塞控制主要在网络层和传输层实现。
3.3 拥塞控制的分类
从控制理论的角度来看待这个问题,拥塞控制方法可以分为两类：开环控制和闭环控制。当流量特征可以准确规定、性能要求可以事先获得时, 适于使用开环控制。它是在事先设计一个“健壮”的网络，确保它不发生拥塞，而网络一旦运行起来，就不再采取措施。这类控制机制较适用于音频和活动图像业务" 例如：如果两个终端允许一个最小的数据率通过! 则发送端可以在不考虑其他进程的通信量的情况下!以这个速度来发送数据而不会发生数据丢失"如果发送端有剩余的链路容量和空闲的可用缓存! 则网络资源没有得到充分的利用!达不到最大效用。显然对网络这样不断变化的复杂系统，开环控制并不是理想的选择。当流量特征不能准确描述或者当系统不提供资源预留时, 适于使用闭环控制。它就是在源端或接收端通过反馈的方式得到网络状态，并能根据这些信息做出适当的调整。Internet中主要采用闭环控制方式, 以动态的适应网络的变化, 其设计关键是如何生成反馈信息和如何对反馈信息进行响应。闭环拥塞控制模型如图示所示：
闭环控制一般包括以下措施：①监测网络系统以便检测到拥塞地址；②将拥塞发生的信息传送到可采取行动的地方；③调整网络系统运行以解决出现的问题。闭环的拥塞控制可以动态的适应网络的变化, 但算法性能受到反馈延迟的严重影响。当拥塞发生点和控制点之间的延迟很大时, 算法性能会严重下降。
目前在Internet上实际使用的拥塞控制基本上是建立在TCP层的窗口控制基础之上的,即基于窗口的端到端的闭环控制方式, 根据MCI的统计, 总字节数的95%和总报文数的90%使用TCP传输。TCP中使用的拥塞控制算法已经成为保证Internet稳定性的重要因素。IP层的拥塞控制主要在网络中间节点如路由器上及链路上实施资源控制, IP层所起的作用相对较小。
3.4 网络拥塞控制的基本原理造成网络拥塞的重要因素是系统存在的瓶颈和源端无限制的数据发送。前者是由网络系统结构决定的,并随网络结构的发展而不断完善。然而网络的物理资源相对用户需求总是不足的,因而要解决拥塞问题必须在共享资源管理的基础上控制源端的数据发送率。合理使用瓶颈处的资源,避免网络发生拥塞或将网络从拥塞状态恢复正常工作状态,就是网络拥塞控制的基本思想。
3.5 TCP拥塞控制机制TCP的拥塞控制采用的是基于窗口的端到端的闭环控制方式。目的节点正确地接收到包后将向信源发出确认(ACK)信息。每个信源有一个大小可变的窗口,使用窗口大小来确定还没有收到确认信息包的数量。当窗口已满,信源在发送一个新包前必须等待一个确认信息。TCP算法有两个重要特征:一个是“自定时”特征,当网络出现拥塞且确认信息出现延迟时自动放慢信源的发送速率;另一个是使用窗口大小来控制信源速率,大约每个往返时间发送一个窗口的数据包。TCP拥塞控制由慢启动( slow start) 、拥塞避免( congestion avoidance ) 、快速重传( fast retransmit)和快速恢复( fast recovery)四个核心部分组成。TCP使用的是加式增加积式减少(A IMD)的基于窗口的端到端的拥塞控制机制,即如果一个数据包丢失,发送窗口就要减半;否则就简单地增加一个数据包的发送量。大量的实践证明,这种拥塞控制机制对In2ternet上大批量文件传输等尽力型( best2effect)服务具有较好的适应性。
3.6 IP拥塞控制机制TCP拥塞控制机制本质上是端到端的控制机制,它默认为IP层对拥塞的发生和拥塞的控制不进行任何支持。当前随着Internet业务的迅猛发展,仅依靠单一的端到端的拥塞控制机制不可能有效地解决拥塞问题,另外期望所有用户在Internet应用中都遵守这种端到端的拥塞控制也是不现实的,这要求网络本身也必须参与对资源的管理与控制。基于此,提出了在路由器中采用排队算法和数据包丢弃的策略,即IP拥塞控制机制。