Skip to main content

2004 | Buch

The Mathematics of Internet Congestion Control

verfasst von: R. Srikant

Verlag: Birkhäuser Boston

Buchreihe : Systems & Control: Foundations & Applications

insite
SUCHEN

Über dieses Buch

Congestion control algorithms were implemented for the Internet nearly two decades ago, but mathematical models of congestion control in such a large-scale network are relatively new. This text presents models for the development of new protocols that can help make Internet data transfers virtually loss- and delay-free. Introduced are tools from optimization, control theory, and stochastic processes integral to the study of congestion control algorithms.

Intended for graduate students and researchers in systems theory and computer science, the text assumes basic knowledge of first-year, graduate-level control theory, optimization, and stochastic processes, but the key prerequisites are summarized in an appendix for quick reference. The work's wide range of applications to the study of both new and existing protocols and control algorithms make the book of interest to researchers and students concerned with many aspects of large-scale information flow on the Internet.

Inhaltsverzeichnis

Frontmatter
1. Introduction
Abstract
The Internet has evolved from a loose federation of networks used primarily in academic institutions, to a global entity which has revolutionized communication, commerce and computing. Early in the evolution, it was recognized that unrestricted access to the Internet resulted in poor performance in the form of low network utilization and high packet loss rates. This phenomenon known as congestion collapse, led to the development of the first congestion control algorithm for the Internet [39]. The basic idea behind the algorithm was to detect congestion in the network through packet losses. Upon detecting a packet loss, the source reduces its transmission rate; otherwise, it increases the transmission rate. The original algorithm has undergone many minor, but important changes, but the essential features of the algorithm used for the increase and decrease phases of the algorithm have not changed through the various versions of TCP, such as TCP-Tahoe, Reno, NewReno, SACK [17, 54]. An exception to this is the TCP Vegas algorithm which uses queueing delay in the network as the indicator of congestion, instead of packet loss [14]. One of the goals of the book is to understand the dynamics of Jacobson’s algorithm through simple mathematical models, and to develop tools and techniques that will improve the algorithm and make it scalable for networks with very large capacities, very large numbers of users, and very large round-trip times.
R. Srikant
2. Resource Allocation
Abstract
Consider a network where each source r is identified by an origin and a destination between which the user of source r is transferring data. In addition, we suppose that each source r uses a fixed route between its origin and destination, and that the route is specified by a sequence of links. Thus, the index r can be used to denote both the source and the route used by the source. Let x r be the rate (bits/sec. or bps) at which source r is allowed to transmit data. Each link l in the network has a capacity c l bps. Given the capacity constraints on the links, the resource allocation problem is one of assigning rates {x r } to the users in a fair manner. To illustrate the difficulties in destination, a fair resource allocation, we consider the following simple example of a network with three links and two sources.
R. Srikant
3. Congestion Control: A decentralized solution to the resource allocation problem
Abstract
For the development in this section, it is convenient to represent the capacity constraints (2.2) in vector form. To this end, let R be a matrix that is defined as follows: the (r, l)th entry of R is 1 if source r’s route passes through link l and is zero otherwise. Thus, R is an | S| × |L| routing matrix which provides information on the links contained in all the source’s routes in the network. Let y l be the total arrival rate of traffic at link l.
R. Srikant
4. Relationship to Current Internet Protocols
Abstract
Consider a single source accessing a link which has the capacity to serve c packets-per-second. Let us also suppose for simplicity that all packets are of equal size. To ensure that congestion does not occur at the link, the source should transmit at a maximum rate of c. One way to ensure this is using a window flow control protocol. A source’s window is the maximum number of unacknowledged packets that the source can inject into the network at any time.
R. Srikant
5. Linear Analysis with Delay: The single link case
Abstract
In the previous chapters, we have studied the relationship between congestion control and resource allocation, and studied the stability of congestion control algorithms in the absence of feedback delay. We will now study the stability of congestion control algorithms in the presence of delay. In this chapter, we restrict our attention to the case of a single link accessed by one or many sources to get acquainted with the tools and techniques used to study stability. In the next chapter, we will extend these results to the case of general topology networks, accessed by a set of heterogeneous sources.
R. Srikant
6. Linear Analysis with Delay: The network case
Abstract
In this chapter, we extend the delay analysis of Chapter 5 to the case of a network. As in Chapter 5, we linearize the system around its equilibrium point and derive conditions for local stability. We consider three main classes of controllers:
1.
We consider different variants of the primal controllers introduced in Chapter 3 with delays in both the forward and backward paths. We also consider the AVQ algorithm to achieve full utilization.
 
2.
Next, we consider the dual controllers introduced in Chapter 3. Unlike the case with no delays, when delays are introduced into the network, we will see that, to ensure the stability of the dual controllers, only a certain class of source utility functions is allowed. However, borrowing the key idea from AVQ, we will see that a parameter in each source’s utility function can be dynamically chosen so that the network equilibrium can be interpreted as maximizing the sum of arbitrary source utilities. Another difference between the dual and primal controllers is that the congestion feedback in the dual algorithm is the delay in the network, whereas in the primal algorithm, the congestion feedback is in the form of packet marks or losses.
 
3.
Finally, we will consider primal-dual algorithms which allow one to model today’s Internet, by allowing the source control algorithms to be like TCP- Reno while the congestion feedback is closely related to the RED algorithm.
 
R. Srikant
7. Global Stability for a Single Link and a Single Flow
Abstract
In the previous two chapters, we obtained stability conditions for various congestion control and congestion indication algorithms by linearizing around the equilibrium point. However, such an analysis does not guarantee convergence to equilibrium, starting from an arbitrary initial condition. In this chapter, we consider the global stability problem. However, little is known about the global stability of such controllers in general. Therefore, we confine ourselves to the special case of proportionally-fair controllers for a single link accessing a single link and derive conditions for global stability. While the global stability question is open for general topology networks, the analysis in this chapter and extensive simulations of various controllers in many papers in the congestion-control literature suggest that the conditions obtained from a linear analysis may indeed be sufficient conditions for stability even if the initial conditions lie in a large region of attraction around the equilibrium point.
R. Srikant
8. Stochastic Models and their Deterministic Limits
Abstract
In the previous chapters, we have used deterministic models to derive congestion control schemes and AQM schemes that are fair and achieve high utilization. However, in the real Internet, there are many sources of randomness:
  • unresponsive flows which do not respond to congestion indication,
  • the probabilistic nature of packet marking by an AQM scheme,
  • asynchronous updates among sources,
  • the inability to precisely model window flow control mechanism, and
  • the initial ramp-up phase (for example, slow start in TCP flow control) of the congestion control mechanism.
R. Srikant
9. Connection-level Models
Abstract
In this chapter, we study simple models of the dynamics of a network at the connection level, i.e., at the level of file arrivals and departures. In all the previous chapters, we assumed that the number of controlled flows in the network is a constant and studied the congestion control and resource allocation problem for a fixed number of flows. In reality, connections or files or flows arrive and depart from the network. We assume that the amount of time that it takes for the congestion control algorithms to drive the source rates close to their equilibrium is much smaller than the inter-arrival and inter-departure times of files. In fact, we assume that compared to the time-scale of connection dynamics, the congestion control algorithm operates instantaneously, providing a resource allocation dictated by the utility functions of the users of the network. In the following sections of this chapter, we will study the impact of flow-level resource allocation on connection-level stochastic stability for this time-scale separated model.
R. Srikant
10. Real-time Sources and Distributed Admission Control
Abstract
In the previous chapters, we have considered only elastic users, i.e., those users that are characterized by concave utility functions. In this chapter, we will consider a specific type of inelastic users: those which require an average bandwidth (say, 1 unit) and a QoS guarantee (e.g., an upper bound on the probability of packet loss or the probability that the delay exceeds some threshold) from the network. In other words, these users would not be willing to use the network if the amount of bandwidth available is less than one unit, and further, will not use any excess bandwidth if more than one unit is provided to them. An example of such sources are voice calls, which generate packets at a rate of 8 kbps to 64 kbps, depending on the codec (coding and decoding algorithm) used, and require the delay, jitter and packet loss in the network to be small to ensure good quality of the audio at the receiver.
R. Srikant
11. Conclusions
Abstract
In this book, we have summarized the exciting advances in the field of mathematical modelling of Internet congestion control over the last few years. As mentioned in the Introduction, this subject is vast and we have confined our attention to only those topics that lead to simple, decentralized schemes. We have concentrated our attention on algorithms that directly result from a convex programming view of congestion control as a mechanism for resource allocation. While this viewpoint is sufficiently rich in allowing us to model many practical aspects of window-flow control as implemented in the Internet, it does not address two important algorithms implemented within TCP, namely, slow start and timeout. For practical implementation of any congestion controller, the slow-start phase and a timeout mechanism are important and are worth further study. We have also not characterized the robustness of virtual queue-based marking mechanisms in this book. Compared to marking based on the contents of the real-queue, virtual-queue-based marking has many advantages. The reader is referred to [32, 31, 51, 66] for an analysis of the properties of virtual-queue-based congestion feedback. Another important problem not discussed in this book is the development of algorithms to limit the impact of users who do not obey congestion signals on the users who reduce their rates in response to congestion feedback from the network. This problem has been addressed in [86, 85, 24].
R. Srikant
Backmatter
Metadaten
Titel
The Mathematics of Internet Congestion Control
verfasst von
R. Srikant
Copyright-Jahr
2004
Verlag
Birkhäuser Boston
Electronic ISBN
978-0-8176-8216-3
Print ISBN
978-1-4612-6498-9
DOI
https://doi.org/10.1007/978-0-8176-8216-3