计算机网络拥塞控制算法综述

刘晓飞

（ 安庆师范大学 计算机与信息学院，安徽 安庆 246133 ）

计算机网络拥塞控制算法综述

刘晓飞

（ 安庆师范大学 计算机与信息学院，安徽 安庆 246133 ）

网络参数的动态变化使网络拥塞变得严重和复杂，拥塞控制一直是个重要的研究内容。目前主要采用以TCP为代表的端到端拥塞控制机制，然而，随着互联网上的应用和用户的增多，这个机制已不能满足网络中各种复杂应用的需求，网络拥塞已成为一个迫在眉睫的问题。文章探讨了网络拥塞出现的原因，分析了TCP拥塞控制的原理及四个TCP拥塞控制算法的性能，论述了TCP拥塞控制面临的问题及相应算法的改进措施，提出了其进一步的研究方向。

拥塞控制； TCP/IP网络； PID； 主动队列管理

计算机网络已有几十年的历史，其发展历史表明：用户需求是推动网络技术发展的原动力[1]。在90年代初期，用户抱怨接入速度过慢；90年代中期，主干网传输速度受到了质疑[2]；90年代后期，用户对网络多媒体服务和服务质量要求日趋强烈，网络拥塞也愈加严重，研究拥塞控制技术对计算机网络体系结构发展有极为深远的意义[3]。

1. 网络拥塞的概念及产生原因

由于网络中传输的数据包数量超过带宽，导致网络传输性能下降，这种现象称为拥塞[4]。如图1所示。随着负载的增加，吞吐量与传输延迟也同步增加，当网络中出现拥塞后，即到达涯点，吞吐量与延迟急剧增大[5]。

1.1.拥塞控制算法的作用点

我们定义拥塞控制算法的作用点为拥塞控制算法的程序实体所运行的物理环境和软件协议环境，它包括物理作用点与协议作用点两个子集。物理作用点是指拥塞控制算法实体所运行的物理主机与设备[6-7]；协议作用点是指拥塞控制算法实体在TCP/IP协议栈内，垂直方向的位置。

1.2.网络拥塞产生的原因

（1）存储空间不够。如果没有足够的存储空间来存储，数据包将被丢弃。发送端会对这些被丢弃的数据包重新传输，这样一来网络资源的浪费增加了网络拥塞。

（2）带宽信息通道窄。信息理论提示到，任何信道带宽最大值就是信道容量C=Blog2(1+S/N)，所有从源率R发送的字母必须小于或等于该信道容量C。如果R>C，则在理论上不可能存在无差别传输，它可以在网络中将形成以低速链路带宽瓶颈，当不能满足要求时，将导致网络拥塞[8-9]。

根据产生网络拥塞的原因可知，虽然源于资源短缺而产生拥塞，但单方面的增加资源有时只能加重拥塞程度[10-11]。比如说，有时为了增大报文通过网关的延迟而增加网关的缓存，在数据包转发完成时，其已超时，但是源端却认为这些数据包已经被丢弃，于是开始重新传输，从而加重了拥塞。

2.TCP/IP拥塞控制结构

对于现有的拥塞控制机制，根据该层级和网络的网络模型实现的位置，可分为基于通信子网的拥塞控制策略和基于源主机的拥塞控制策略[12]（如图2所示）。两种类型的拥塞控制原理如图3和4所示。

图1 网络负载与吞吐量及响应时间的关系

图2 TCP/IP网络拥塞控制策略结构图

图3 基于端主机的拥塞控制模型

图4 主动队列管理策略控制模型

3. 控制算法比较

3.1.TCP拥塞控制算法

最初的NSFNET程序规范的TCP协议，这是RFC793。这个规范对如何进行主机到主机的可靠传输进行了简单描述，也介绍了一些传输控制协议执行的功能，实现了相应的方案和程序接口。

需要明确的是，如表1所示，互联网络中的可靠传输起码包括这两方面：第一个是正确的数据，这是由于以前的传输介质的传输质量较差，所以需要校验和计算，在传输层和下面实现的协议层[13]；第二是拥塞控制实际上是在Internet上使用的TCP来实现的，95%的互联网使用对数据流的TCP协议。

3.2.IP拥塞控制算法

TCP基于窗口的拥塞控制机制的因特网的鲁棒性方面发挥了关键作用。然而，随着迅猛发展的Internet本身，它越来越庞大的规模，日益复杂的结构，使仅依靠端的TCP拥塞控制是不够的，互联网络也应该参加控制资源的工作。为了实现拥塞控制，出现了一系列的队列管理算法[14]（如表2所示）。

表1 TCP典型拥塞算法比较

表2 IP典型拥塞算法比较

3.3.两大类算法比较

两类算法的比较如表3所示。

表3 拥塞控制算法的比较

图5是一个典型的互联网实例，包括IP控制的Hop-by-Hop类型和TCP控制的End-and-End类型。可以看出，本质上，拥塞控制方法是基于TCP的。显然，这种拥塞控制方法具有相当大的延迟[15-16]，在感知拥塞现象后采取行动，在传输数据量小的情况下，也能够将拥塞信息反馈到源结点。

图5 典型互联网实例

4.其它拥塞控制算法

（1）基于方程的拥塞控制(equation-based congestion control)。它把发送速率作为丢失事件率的函数运算，给出可接收的最大发送速率并使用控制方程显示得到[17]。因此该算法中的一个关键部分是丢失事件率的计算。

（2）TCP Westwood。TCP Westwood是一种来调整拥塞窗的TCP协议，且是由发送方采用。它的主要目的不是在少量丢包时拥塞窗口减半来提高连接吞吐量而是对拥塞窗口进行定量的减少[18]。

用来调整拥塞窗口的伪代码如下，收到3个冗余的ACK时：

当发生超时事件时：

其中ssthresh就是慢启动阈值，cwnd是拥塞窗口的大小，BWE估计带宽连接，最小RTTmin被测量到的往返时间，SEG大小是数据包的解释的大小[19-21]。

结果表明，TCP Westwood的整体性能比TCP要好，可获得更高的吞吐量和更多更好的信息。但该算法也风险不可避免的问题，一些连接问题，可能因为带宽高估导致的。

5.存在的问题及改进方法

TCP/IP拥塞控制机制在网络中发挥了不可或缺的作用，但TCP/IP拥塞控制算法本身有不能忽视的问题：（1）从发生拥塞到端系统实施控制之间存在明显的时间延迟，而且终端系统对动态数据传输过程也认识不足，无法预知网络资源的具体使用情况；（2）慢启动算法存在尤为突出的问题。首先，由于发送方无法理解慢启动阶段瓶颈链路的带宽，会造成网络资源利用率降低及延迟增加，特别是在网络可用带宽较大时；其次，TCP/ IP为短小数据流服务时，往往需要若干时间的RTT来检测网络带宽，传输延迟经常需要几个RTT时间来检测相应的网络带宽，传输延迟这里是不太可靠的。

针对TCP/IP拥塞控制出现了上面的几个问题，近几年来，很多人对他们进行了各种各样的探讨和改进，以便更好地符合各种网络应用的需要、适应网络动态变化的特性，使网络运行在最佳状态[22]。

使用累计确认、超时重传和后退等机制只是早期TCP的实现。Nagle指出[23-24]，可以根据源端相邻节点之间的比例，扩大两者之间的上限值，适当增大新回合中慢启动的绝对阈值，通过加大慢启动回合数来提高网络发送速率。这样保证了发送方的发送速率，可以使整个网络的拥塞现象得到极大的缓解。

6.结语

本文阐述了拥塞控制研究的现状、拥塞控制的原理，揭示拥塞控制所面临的问题，并进行了研究与综述。通过对拥塞控制算法现状的分析，探讨了现行的TCP拥塞控制算法在各个阶段存在的一些不可忽视的问题，并总结了改进方法。

[1] 罗万明，林闯，阎宝平.TCP拥塞控制研究[J].计算机学报，2001，24（1）：1-18.

[2] 邓亚平，叶凌伟，陈雁.TCP／IP拥塞控制算法的改进[J].计算机科学，2001，28（4）：110-113.

[3] 包俊杰，王刚，李波.TCP拥塞控制综述[J].重庆教育学院报，2003，16（6）：30-33.

[4] 谢希仁.计算机网络（第三版）[M].大连：大连理工大学出版社，2000.

[5] 林闯，刘卫东.TCP网络中的拥塞控制[J].计算机世界，2001，PBl-B1.

[6] 张故辕，谢剑英，傅春.一种基于模糊逻辑的主动队列管理算法[J].电子学报，2002，30（8）：1246-1249.

[7] 单玉峰，柴乔林.TCP友好拥塞/速率控制算法及其在多发媒体数据传输中的应用[J].计算机学报，2001，（8）：886-990.

[8] 章淼，吴建平，林闯.互联网端到端拥塞控制研究综述[J].软件学报，2002，13（3）：354-363.

[9] 陈尚兵.IP网络中拥塞控制和可扩展组播路由研究[D].杭州：浙江大学，2003.

[10] 杨凯锋，洪佩琳，束永安，李津生.Internet由器中的拥塞控制策略[J].小型微型计算机系统，2000，2l （4）：353-356.

[11] Jacobson V. Congestion Avoidance and Control [C]. In: Proceeding of SIOCOM, 312-329.

[12] Floyd S, Jacobson V. On Traffic Phase Effects in Packet-Switched [J]. Gateways, 1992, 3(3): 115-156.

[13] 王德锁，舒勤.TCP拥塞控制机制在高速网络中的局限性[J].中国测试技术，2004，（3）.

[14] 张贤达，保铮等.通信信号处理[M].北京：国防工业出版社，2000.

[15] 胜美，赵春明.基于最小二乘算法及子空间方法的盲多用户检测算法[J].通信学报，2003，24（5）：129-132.

[16] 薛强，吴伟陵.衰落信道中基于CMA的自适应多用户检测算法[J].重庆邮电学院学报，2001，13（1）：17-19.

[17] 张浩亮，段炼，薛强，等.一种新的基于CMA的盲自适应多用户检测算法[J].北京邮电大学学报，2003，26（1）：78-81.

[18] 朱小刚，潘理，诸鸿文等.盲恒模多用户检测算法的实现和性能优化[J].通信技术，2002，（8）：9-11.

[19] 冯熳，廖桂生.恒模算法：进展与展望[J].信号处理，2003，19 （5）：441-445.

[20] 方晨，刘昊，时龙兴. 一种基于自适应竞争窗口的无线传感器网络拥塞缓解策略[J].东南大学学报（自然科学版），2013，43 （4）：687-689.

[21] 潘守伟，蒋道霞.无线传感器网络中基于路由协议的拥塞控制技术研究[J].科技创新导报，2014，（5）：11-13.

[22] 赵正伟，许刚，毕经平. 基于优先级的时限感知的数据中心网络拥塞控制算法[J].高技术通讯，2014，24（6）：587-595.

[23] 许建真，曹欢欢，宋爱玲. 基于访问控制的无线传感网链式分层路由协议[J].计算机与现代化，2015，（4）：14-19.

[24] 韩存武，刁奇，常舒瑞，等.基于降维状态观测器的最优拥塞控制研究[J].高技术通讯，2015，25（12）：1047-1052.

Research and Review of Computer Network Congestion Control Algorithm

LIU Xiaofei
( Anqing Normal University, Anqing Anhui 246133, China )

The dynamic changes of network parameters make the congestion of the network become more and more serious and complex, and the congestion control is always an important research direction. At present, the end to end congestion control mechanism based on TCP is mainly adopted. With the application of Internet and the increase of users, this mechanism has been unable to fully meet the needs of complex applications in the network. Network congestion has become an urgent problem. This paper discusses the cause of network congestion, then analyzes the performance of TCP congestion control principle and four TCP congestion control algorithm, and then focuses on the improvement of TCP congestion control facing problem and the corresponding algorithm, and finally puts forward the direction of further research.

congestion control, TCP/IP network, PID, control active queue management

TP338

A

1673-9639 (2016) 04-0109-05

（责任编辑 田 波）（责任校对 毛 志）

2016-03-09

刘晓飞（1980-），男，安徽安庆人，副教授，硕士，研究方向：计算机应用技术。