The Mathematics of Internet Congestion Control
The Mathematics of Internet Congestion Control
复制标题
DOI：
10.1109/tac.2004.841398
复制
发表时间：
2005
影响因子：
6.8
通讯作者：
Derong Liu
中科院分区：
文献类型：
--
作者：
Derong Liu
在过去的几年中，计算机网络经历了爆炸式增长，随之而来的是严重的拥塞问题。例如，现在常见的情况是互联网网关由于本地缓冲区溢出而丢弃10%的传入数据包[5]。拥塞是一种网络持续过载的状态，即对资源的需求在较长一段时间内超过了供应。拥塞事件将导致大量数据包连续丢失。当用户检测到一个丢失的数据包时，通常会重新传输该丢失的数据包。因此，拥塞会减慢网络流量，而且一旦开始，往往会变得更加严重。在过去的二十年中，拥塞避免和控制一直是一个热门的研究课题，研究人员已经研究了一些算法，这些算法可以使网络（包括互联网）的吞吐量最大化，并使数据包丢失率最小化。对于许多控制研究人员和工程师来说，计算机网络（尤其是互联网）的研究并不是很贴近他们的领域。主要原因是计算机网络的研究通常涉及的数学严谨性和推导比我们在控制文献中常见的要少得多。这本书可能有助于缩小这一差距。这本书是关于控制理论中的一些著名成果在互联网拥塞控制研究中的应用。读者会在整本书中发现数学方程式和推导。控制研究人员熟悉的结果，包括凸优化、李雅普诺夫稳定性理论和奈奎斯特准则，是本书使用的主要工具。本书所研究问题的起源来自雅各布森[5]，其中第一个互联网拥塞控制算法作为传输控制协议（TCP）的一部分被发表用于实施。本书使用控制工程师熟悉的数学工具来理解雅各布森算法的动态并改进该算法。第1章简要介绍了本书所研究的互联网拥塞控制问题。本章使用基于[2]中所开发算法的两个简单示例来说明问题的定义以及问题表述中所涉及的数学知识。李雅普诺夫第二方法被用作得出这两个示例分析结果的工具。第2章关注资源/带宽分配问题，该问题被视为一个优化问题[7]。通过引入一类通用的效用函数，文献中针对凸优化所开发的方法被应用于解决当前的资源分配优化问题。所考虑的网络资源分配的具体情况包括最小潜在延迟公平性、比例公平性和最大 - 最小公平性[6]。本章末尾的附录中介绍了一些凸优化的现有结果。第3章研究分散式资源分配问题的情况。第2章中引入的被表述为约束优化问题的资源分配问题在本章中作为一个无约束优化问题来解决，该无约束优化问题通过在效用函数中使用惩罚项来纳入约束条件。
Computer networks have experienced an explosive growth over the past years and with that growth have come severe congestion problems. For example, it is now common to see Internet gateways drop 10% of the incoming packets because of local buffer overflow [5]. Congestion is a state of sustained network overload, when the demands for resources exceed the supply for an extended period of time. A congestion event will cause a significant number of packets to be lost consecutively. When a user detects a dropped packet, it typically retransmits the dropped packet. Thus, congestion slows down network traffic flow and it tends to get more severe once it starts. Congestion avoidance and control has been a hot research topic in the past two decades and researchers have investigated algorithms that maximize the throughput of the network and minimize the packet-loss rate for networks including the Internet. To many control researchers and engineers, research in computer networks, especially the Internet, is not very close. The main reason is that research in computer networks typically involves much less mathematical rigor and derivations than what we are used to see in the control literature. This book may help to close this gap. This book is about the application of some well-known results in control theory to the study of Internet congestion control. Readers will find mathematical equations and derivations throughout the book. Results that are familiar to control researchers including convex optimization, Lyapunov stability theory, and the Nyquist criterion are the main tools used in this book. The origin of the problem studied in this book came from Jacobson [5] where the first Internet congestion control algorithm was published for implementation as part of the transmission control protocol (TCP). Mathematical tools familiar to control engineers are used in this book to understand the dynamics of Jacobson’s algorithm and to improve the algorithm. Chapter 1 provides a brief introduction to the problem of Internet congestion control that is studied in this book. Two simple examples based on the algorithm developed in [2] are used in this chapter to illustrate the problem definition and the mathematics involved in the problem formulation. The Second Method of Lyapunov is used as a tool in arriving at the analysis results of the two examples. Chapter 2 is concerned with the problem of resource/bandwidth allocation which is viewed as an optimization problem [7]. With the introduction of a general class of utility functions, approaches developed in the literature for convex optimization are applied to solving the present optimization problem for resource allocation. Specific cases of network resource allocation considered include minimum potential delay fairness, proportional fairness, and max–min fairness [6]. Some existing results from convex optimization are introduced in an Appendix at the end of the chapter. Chapter 3 studies the case of the decentralized resource allocation problem. The resource allocation problem introduced in Chapter 2 which is formulated as a constrained optimization problem is solved in this chapter as an unconstrained optimization problem that incorporates the constraints using a penalty term in the utility function.