因特网络拥塞控制机制的数学架构研究

徐 辉，宁国强

（西安通信学院 陕西 西安 710106）

因特网技术是人类进入信息化社会最为关键的技术之一，随着因特网用户数的日益增加，业务种类越来越多，要实现因特网对用户业务需求的良好满足，拥塞控制是主要技术之一。从因特网设计的初衷来看，该网络是被设计为一种“尽力而为”（Best Effort）服务，是由所有网络用户来竞争网络的有限资源，但是，随着因特网业务的发展和用户数的激增，现在因特网所处环境和其设计之处，发生了巨大的变化，因特网需要利用有限的资源为用户提供多样化服务，拥塞控制机制是因特网满足用户服务需求，保证网络资源合理化使用的重要手段之一，在因特网技术研究中一直占据重要地位。但是，由于因特网规模大，结构复杂，因此，传统拥塞控制多采用基于经验和实验方式，使得具有很大主观性和片面性；随着拥塞控制技术的发展，为了提高其科学合理性，多种数学工具被引入到拥塞控制的设计中，文中对现有因特网拥塞控制机制的数学模型进行了分析，提出了一个用于因特网的分析和设计的统一的数学框架，对研究热点问题了进行了分析和研究，为进一步研究奠定了基础。

1 拥塞控制数学框架构建

在因特网拥塞控制技术的研究中，最初采用基于采用经验加技巧的方式进行，由于其构造和评价过程过于依赖试验和仿真，所以这种方法具有很大的主观和片面性。对因特网拥塞控制进行数学建模，然后根据数学模型进行设计和分析，则是较先进的方式。采用这种方式，由于将拥塞控制问题转化为精确的数学模型进行求解，因而提高了算法的理论保证，同时便于为拥塞控制算法的设计提供一个统一的理论构架。在因特网拥塞控制技术的发展中，先后有经济学模型、最优化理论、博弈论和控制论等多种数学模型提出，通过对这些模型的分析发现，因特网拥塞控制的本质是如何控制网络业务接入以最优化使用网络有限资源，最大化满足网络用户业务需求，因此，控制论和最优化理论是因特网拥塞控制理论建模的关键，其统一数学架构可由图1所示结构来表示。在该结构中包括拥塞控制算法的设计和拥塞控制算法的分析两个部分。

拥塞控制算法的设计问题就是根据最优化模型确立拥塞控制源端算法和链路算法的过程。在这方面的研究中，Low[1-3]等 人 剖 析 了 常 见 的 TCPAQM策 略 （RenoDrop Tail、RenoRED、RenoREM、VegasDrop Tail和 Vega sREM），定义了一组对偶的拥塞控制算法：

其中Fs表示TCP源端算法的更新方程，Gl表示AQM链路算法的更新方程，qr为源端接收到的聚合定价，这样拥塞控制算法便可以通过一个3元组（F，G，U）来描述。为每种策略定义了3元组（F，G，U），并根据每个三元组详细讨论了这些算法的具体性能在获知拥塞控制的对偶算法式（1）后，便可根据控制论知识或优化理论来分析该拥塞控制算法的动力学特性和均衡特性。拥塞控制的分析问题就是对当前拥塞控制进行理论分析，其关键之处在于根据当前的拥塞控制算法建立合适的对偶算法式（1），然后进行动力学特性和均衡分析。常见的描述拥塞控制算法的动力学特性参数有稳定性、收敛性和可扩展性等，常见的均衡特性参数有吞吐量、丢失率、时延、排队长度和公平性等。

图1几乎涵盖了所有的理论研究和拥塞控制算法的问题，囊括了绝大多数的有关因特网拥塞控制建模的研究要点，但此处仅就当前研究的热点加以介绍。

图1 因特网拥塞控制数学模型的体系结构Fig．1 Architecture of themathematicmodeling about internet congestion controlmechanism

2 因特网拥塞控制研究热点分析

2.1 公平性特性的研究

有关公平性的研究一直是因特网拥塞控制建模领域的热点，它表征了不同用户使用网络资源的差异，反映了因特网资源的配置情况。最常见的公平性准则是最大最小公平（Max-Min Fairness）或称为瓶颈最优准则[4]。该公平性准则给每个用户相同的权限，确保了共享同一瓶颈的用户能获得相同的资源。为了表征不同的用户在面对相同的拥塞时表现出不同的响应，Kelly[5]建议了一种比例公平准则（Proportional Fairness），该准则要求网络资源的分布同自身的业务相关。从网络传输时延角度考虑，文献[6]提出了一种最小潜在时延的公平性准则（Potential Delay Minimization）。 更一般的，文献[7]提出了一种通用公平性准则——基于效用函数的公平性，在文中，作者定义了一类特殊的效用函数：

作者指出，不同的参数α将会使网络获得不同的公平性：

α=0，网络将获得最大吞吐量的资源配置；

α=1，网络将获得比例公平的资源配置；

α=2，网络将获得最小潜在时延的资源配置；

α→∞，网络的资源配置将趋近于最大最小公平。

在文献[7]的基础上，文献[8]从更深层次上对公平性进行了研究并指出最优化模型 （2）最终会使网络的资源配置达到Pareto最优[9]，并且作者还找寻到了常见公平性准则的物理意义：

最大吞吐量公平性准则会使用户吞吐量的算术平均值（Arithmetic Mean）最大；

比例公平准则会使用户吞吐量的几何平均值（Geometric Mean）最大；

最小潜在时延公平准则会使用户吞吐量的调和平均值（Harmonic Mean）最大。

对于实际因特网所满足的公平性准则，Kelly[5]指出TCPAQM算法最终能使网络达到加权比例公平。而Low[1]通过对偶理论的研究，指出当前的基于TCPRenoRED的因特网应当满足加权最小潜在时延的公平性准则。

2.2 稳定性的研究

稳定性是表征网络是否健壮的参数，有关因特网稳定性的研究也一直是因特网理论研究领域的热点。

Kelly[5]基于最优化理论提出了一类拥塞控制框架，并利用Lyapunov稳定性理论分析了拥塞控制系统的稳定性。

文献 [10]使用了流的思想和随机微分方程理论为TCPAQM拥塞控制算法建立了一个动态的微分方程系统：

其中，R（t）=q（t）/C+Tp，W 为 TCP 窗口，q 为拥塞队列长度，R为RTT时间，C为排队容量，Tp为传输时延，N为TCP的会话数目，p为包丢失概率。

结合上述微分动力系统，文献[11]使用了经典控制理论对拥塞控制的稳定性进行了分析，建立了一个通用的线性时延反馈控制系统（图2）。在这个模型当中，反馈控制系统包含有：Plant，代表一个子系统的组合，包括TCP源、链路以及TCP接收端；AQM控制器，产生分组丢弃概率pd作为一个控制信号来控制进入路由器队列的分组到达速率；作为Plant变量的路由器的队列长度（就是受控制的变量）Qt；路由器中期望的队列长度 Qref；反馈信号（采样的系统输出）e（t）=Qref-Qt。根据这一模型，只要确定该模型中的各个要素，便会很容易的判定网络的稳定特性。

图2 拥塞控制的线性时延反馈控制系统Fig．2 Linear time-delay feedback control system for internet congestion control

不同于文献[11]的研究，Low等人建立了一个基于对偶理论的控制论模型[1]（图3）。该模型是一个拉普拉斯域上的多变量的鲁棒控制系统，在该模型中，源端的发送速率x同链路定价p互为对偶；源端接收到的聚合定价q同链路上的聚合速率 y互为对偶，Af（s）和 Ab（s）分别为前向和后向的传输矩阵，F（·）和G（·）分别为源端算法和链路算法。在文献[12]中，Paganini使用了现代控制理论和奈奎斯特准则对该模型进行了讨论和分析。

图3 拥塞控制的鲁棒控制系统Fig．3 Robust control system about internet congestion control

3 结束语

文中主要对因特网拥塞控制的统一数学构建进行了研究，分析了其主要研究热点，从对因特网进行简单的考虑开始，到对其进行成熟的建模，这里面包含了众多的研究成果，但是，由于因特网的复杂性和不断发展，对因特网拥塞控制建立准确的数学模型不可能一蹴而就，还有很多问题尚待研究。对整个因特网的公平性、稳定性、可扩展性的分析由于受复杂网络的影响，很难进行全局的动力学理论分析。像因特网这样的一个复杂的系统，对其分析与控制，只有通过通信、

控制、经济学和数学等多学科的共同努力，才有望获得突破性的成果。

[1]Low SH， Paganini F，Doyle JC．Internet congestion control[J]．IEEE Control Systems Magazine，2002，22（1）：28-43．

[2]Low S H．A duality model of TCP and queue management algorithms[J]．IEEE/ACM Trans．on Networking，2003，11（4）：525-536．

[3]Low SH，Srikant R．A mathematical framework for designing a low-loss， low-delayinternet[J]．Networkand SpatialEconomics，2004，4（1） ：75-102．

[4]Jaffe JM．Bottleneck flow control[J]．IEEE Trans，1981，29（29）：954-962．

[5]Kelly F P，Maulloo A，Tan D．Rate control in communication networks：shadow prices， proportional fairness and stability[J]．Journal of the Operational Research Society，1998（49）：237-252．

[6]Massoulie L，Roberts J．Bandwidth sharing：objectives and algorithms[C]//Proc．of the IEEE INFOCOM’99，March 1999：1395-1403．

[7]Mo J，Walrand J．Fair end-to-end window-based congestion control[J]．IEEE/ACM Transactions on Networking，2000，8（5）：556-567．

[8]Bonald T，Massoulie T．Impact of fairness on Internet performance[C]//In Proceedings of ACM Sigmetrics，2001：82-91．

[9]瓦里安．微观经济学 [M]．3版．北京：经济科学出版社，1997．

[10]Misra V，Gong W B，Towsley D．Fluid-based analysis of a network of AQM routers supporting tcp flows with an application to RED[C]//Proc．ACM SIGCOMM，2000：151-160．

[11]Hollot C V．A Control Theoretic Analysis of RED[C]//Proc．INFOCOM 2001，2001：1510-1519．

[12]Paganini F．A global stability result in network flow control[J]．Systems and Control Letters，2002，46（3）：153-163．