Internet Congestion Control provides a description of some of the most important topics in the area of congestion control in computer networks, with special emphasis on the analytical modeling of congestion control algorithms.
The field of congestion control has seen many notable advances in recent years and the purpose of this book, which is targeted towards the advanced and intermediate reader, is to inform about the most important developments in this area. The book should enable the reader to gain a good understanding of the application of congestion control theory to a number of application domains such as Data Center Networks, Video Streaming, High Speed Links and Broadband Wireless Networks. When seen through the lens of analytical modeling, there are a number of common threads that run through the design and analysis of congestion control protocols in all these different areas, which are emphasized in this book. The book also cuts a path through the profusion of algorithms in the literature, and puts the topic on a systematic and logical footing.
Internet Congestion Control provides practicing network engineers and researchers with a comprehensive and accessible coverage of analytical models of congestion control algorithms, and gives readers everything needed to understand the latest developments and research in this area.
- Examines and synthesizes the most important developments in internet congestion control from the last 20 years.
- Provides detailed description on the congestion control protocols used in four key areas; broadband wireless networks, high speed networks with large latencies, video transmission networks, and data center networks.
- Offers accessible coverage of advanced topics such as Optimization and Control Theory as applied to congestion control systems.
This chapter is an introduction to the subject of congestion control and covers some basic results in this area, such as the Chiu-Jain result on the optimality of additive increase/multiplicative decrease (AIMD) control and descriptions of fundamental congestion control algorithms such as TCP Reno, TCP Vegas, and Random Early Detection (RED)-based Active Queue Management (AQM). A detailed description of TCP Reno is provided, including algorithms such as Congestion Avoidance, Fast Retransmit and Fast Recovery, Slow Start, and TCP Timer operation. AQM techniques are introduced, and the RED algorithm is described.
Congestion Control definition and objectives; TCP Reno; TCP Vegas; Active Queue Management; AQM; Random Early Detection; RED; Congestion Avoidance; Fast Retransmit; Fast Recovery; Slow Start
The Transmission Control Protocol (TCP) is one of the pillars of the global Internet. One of TCP's critical functions is congestion control, and the objective of this book is to provide an overview of this topic, with special emphasis on analytical modeling of congestion control protocols.
TCP's congestion control algorithm has been described as the largest human-made feedback-controlled system in the world. It enables hundreds of millions of devices, ranging from huge servers to the smallest PDA, to coexist together and make efficient use of existing bandwidth resources. It does so over link speeds that vary from a few kilobits per second to tens of gigabits per second. How it is able to accomplish this task in a fully distributed manner forms the subject matter of this book.
Starting from its origins as a simple static-window-controlled algorithm, TCP congestion control went through several important enhancements in the years since 1986, starting with Van Jacobsen's invention of the Slow Start and Congestion Avoidance algorithms, described in his seminal paper . In addition to significant developments in the area of new congestion control algorithms and enhancements to existing ones, we have seen a big increase in our theoretical understanding of congestion control. Several new important application areas, such as video streaming and data center networks (DCNs), have appeared in recent years, which have kept the pace of innovation in this subject area humming.
The objective of this book is twofold: Part 1 provides an accessible overview of the main theoretical developments in the area of modeling of congestion control systems. Not only have these models helped our understanding of existing algorithms, but they have also played an essential role in the discovery of newer algorithms. They have also helped us explore the limits of stability of congestion control algorithms. Part 2 discusses the application of congestion control to some important areas that have arisen in the past 10 to 15 years, namely Wireless Access Networks, DCNs, high-speed links, and Packet Video Transport. Each of these applications comes with its own unique characteristics that has resulted in new requirements from the congestion control point of view and has led to a proliferation of new algorithms in recent years. Several of these are now as widely deployed as the legacy TCP congestion control algorithm. The strong theoretical underpinning that has been established for this subject has helped us greatly in understanding the behavior of these new algorithms.
The rest of this chapter is organized as follows: Section 1.2 provides an introduction to the topic of congestion control in data networks and introduces the idea of additive increase/multiplicative decrease (AIMD) algorithms. Section 1.3 provides a description of the TCP Reno algorithm, and Section 1.4 discusses Active Queue Management (AQM). TCP Vegas is described in Section 1.5, and Section 1.6 provides an overview of the rest of the chapters in this book.
1.2 Basics of Congestion Control
The problem of congestion control arises whenever multiple distributed agents try to make use of shared resources (Figure 1.1). It arises widely in different scenarios, including traffic control on highways or air traffic control. This book focuses on the specific case of packet data networks, where the high-level objective of congestion control is to provide good utilization of network resources and at the same time provide acceptable performance for the users of the network. Figure 1.1
The congestion control problem.
The theory and practice of congestion control for data networks have evolved in the past 3 decades to the system that we use today. The early Internet had very rudimentary congestion control, which led to a series of network collapses in 1986. As a result, a congestion control algorithm called TCP Slow Start (also sometimes called TCP Tahoe) was put into place in 1987 and 1988, which, in its current incarnation as TCP Reno, remains one of the dominant algorithms used in the Internet today. Since then, the Internet has evolved and now features transmissions over wireless media, link speeds that are several orders of magnitudes faster, widespread transmission of video streams, and the recent rise of massive data centers. The congestion control research and development community has successfully met the challenge of modifying the original congestion control algorithm and has come up with newer algorithms to address these new types of networks.
1.2.1 The Congestion Control Problem Definition
To define the congestion control problem more formally, consider the graph in Figure 1.2 in which the throughput of a data source has been plotted on the y-axis and the network traffic load from the source has been plotted on the x-axis. We observe the following:
If the load is small, the throughput keeps up with the increasing load. After the load reaches the network capacity, at the "knee" of the curve, the throughput stops increasing. Beyond the knee, as the load increases, queues start to build up in the network, thus increasing the end-to-end latency without adding to the throughput. The network is then said to be in a state of congestion.
If the traffic load increases even further and gets to the "cliff" part of the curve, then the throughput experiences a rather drastic reduction. This is because queues within the network have increased to the point that packets are being dropped. If the sources choose to retransmit to recover from losses, then this adds further to the total load, resulting in a positive feedback loop that sends the network into congestion collapse. Figure 1.2
Throughput versus load.
To avoid congestion collapse, each data source should try to maintain the load it is sending into the network in the neighborhood of the knee. An algorithm that accomplishes this objective is known as a congestion avoidance algorithm; a congestion control algorithm tries to prevent the system from going over the cliff. This task is easier said than done and runs into the following challenge: The location of the knee is not known and in fact changes with total network load and traffic patterns. Hence, the problem of congestion control is inherently a distributed optimization problem in which each source has to constantly adapt its traffic load as a function of feedback information it is receiving from the network as it tries to stay near the knee of the curve.
The original TCP Tahoe algorithm and its descendants fall into the congestion control category because in the absence of support from the network nodes, the only way they can detect congestion is by filling up the network buffers and then detecting the subsequent packet drops as a sign of congestion. Many routers today implement a more sophisticated form of buffer management called Random Early Detection (RED) that provides early warnings of a congestive situation. TCP in combination with RED then qualifies as a congestion avoidance algorithm. Algorithms such as TCP Vegas operate the system around the knee without requiring special support in the network nodes.
Some of the questions that need to be answered in the design of a congestion control algorithm include the following (all of the new terms used below are defined in this chapter):
Should the congestion control be implemented on an end-to-end or on a hop-by-hop basis?
Should the traffic control be exercised using a windows-based mechanism or a rate-based mechanism?
How does the network signal to the end points that it is congested (or conversely, not congested)?
What is the best Traffic Rate Increment rule in the absence of congestion?
What is the best Traffic Rate Decrement rule in the presence of congestion?
How can the algorithm ensure fairness among all connections sharing a link, and what measure of fairness should be used?
Should the congestion control algorithm prioritize high link utilization of low end-to-end latency?
There is a function closely related to congestion control, called flow control, and often the two terms are used interchangeably. For the purposes of this book, flow control is defined as a function that is used at the destination node to prevent its receive buffers from overflowing. It is implemented by providing feedback to the sender, usually in the form of window-size constraints. Later in this book, we will discuss the case of video streaming in...