PETERSON-AND-DAVIE 12-ch06-478-577-9780123850591 2011/11/1 21:50 Page 479 #2 Congestion Control and Resource Allocation The hand that hath made you fair hath made you good. –William Shakespeare B y now we have seen enough layers of the network protocol hierarchy to understand how data can be transferred among pro- cesses across heterogeneous networks. We now turn to a problem that spans the entire protocol stack—how to effectively and fairly allocate resources among a collection of competing users. The resources being shared include the bandwidth of the links and the buffers on the routers or switches where packets are queued awaiting transmission.
Packets contend at a router for the use of a link, with each contending packet placed in a queue waiting its turn to be transmitted over the link. When PROBLEM: ALLOCATING RESOURCES too many packets are contending for the same link, the queue overflows and packets have to be dropped. When such drops become common events, the network is said to be congested. Most networks provide a congestion-control mechanism to deal with just such a situation.
Congestion control and resource allocation are two sides of the same coin. On the one hand, if the network takes an active role in allocating resources—for example, scheduling which virtual circuit gets to use a given physical link during a certain Computer Networks: A Systems Approach.00006-5 Copyright © 2012 Elsevier, Inc. All rights reserved. 479 PETERSON-AND-DAVIE 12-ch06-478-577-9780123850591 2011/11/1 21:50 Page 480 #3 480 CHAPTER 6 Congestion control and resource allocation period of time—then congestion may be avoided, thereby making congestion control unnecessary.
Allocating network resources with any precision is difficult, however, because the resources in question are distributed throughout the network; multiple links connecting a series of routers need to be scheduled. On the other hand, you can always let packet sources send as much data as they want and then recover from congestion should it occur. This is the easier approach, but it can be disruptive because many packets may be discarded by the network before conges- tion can be controlled. Furthermore, it is precisely at those times when the network is congested—that is, resources have become scarce relative to demand—that the need for resource allocation among competing users is most keenly felt.
There are also solutions in the middle, whereby inexact allocation decisions are made, but con- gestion can still occur and hence some mechanism is still needed to recover from it. Whether you call such a mixed solution congestion control or resource allocation does not really matter. In some sense, it is both. Congestion control and resource allocation involve both hosts and network ele- ments such as routers.
In network elements, various queuing disciplines can be used to control the order in which packets get transmitted and which packets get dropped. The queuing discipline can also segregate traffic to keep one user’s packets from unduly affecting another user’s packets. At the end hosts, the congestion- control mechanism paces how fast sources are allowed to send packets. This is done in an effort to keep congestion from occurring in the first place and, should it occur, to help eliminate the congestion.
This chapter starts with an overview of congestion control and resource alloca- tion. We then discuss different queuing disciplines that can be implemented on the routers inside the network, followed by a description of the congestion-control algo- rithm provided by TCP on the hosts. The fourth section explores various techniques involving both routers and hosts that aim to avoid congestion before it becomes a problem. Finally, we examine the broad area of quality of service.
We consider the needs of applications to receive different levels of resource allocation in the network and describe a number of ways in which they can request these resources and the network can meet the requests.1 ISSUES IN RESOURCE ALLOCATION Resource allocation and congestion control are complex issues that have been the subject of much study ever since the first network was designed. They are still active areas of research. One factor that makes these issues complex is that they are not isolated to one single level of a protocol PETERSON-AND-DAVIE 12-ch06-478-577-9780123850591 2011/11/1 21:50 Page 481 #4 6.1 Issues in resource allocation 481 hierarchy. Resource allocation is partially implemented in the routers, switches, and links inside the network and partially in the transport protocol running on the end hosts.
End systems may use signalling pro- tocols to convey their resource requirements to network nodes, which respond with information about resource availability. One of the main goals of this chapter is to define a framework in which these mecha- nisms can be understood, as well as to give the relevant details about a representative sample of mechanisms. We should clarify our terminology before going any further. By resource allocation, we mean the process by which network elements try to meet the competing demands that applications have for network resources— primarily link bandwidth and buffer space in routers or switches.
Of course, it will often not be possible to meet all the demands, meaning that some users or applications may receive fewer network resources than they want. Part of the resource allocation problem is deciding when to say no and to whom. We use the term congestion control to describe the efforts made by network nodes to prevent or respond to overload conditions. Since con- gestion is generally bad for everyone, the first order of business is making congestion subside, or preventing it in the first place.
This might be achieved simply by persuading a few hosts to stop sending, thus improv- ing the situation for everyone else. However, it is more common for congestion-control mechanisms to have some aspect of fairness—that is, they try to share the pain among all users, rather than causing great pain to a few. Thus, we see that many congestion-control mechanisms have some sort of resource allocation built into them. It is also important to understand the difference between flow con- trol and congestion control.
Flow control, as we have seen in Section 2.5, involves keeping a fast sender from overrunning a slow receiver. Con- gestion control, by contrast, is intended to keep a set of senders from sending too much data into the network because of lack of resources at some point. These two concepts are often confused; as we will see, they also share some mechanisms.1 Network Model We begin by defining three salient features of the network architecture. For the most part, this is a summary of material presented in the previous chapters that is relevant to the problem of resource allocation.
PETERSON-AND-DAVIE 12-ch06-478-577-9780123850591 2011/11/1 21:50 Page 482 #5 482 CHAPTER 6 Congestion control and resource allocation Packet-Switched Network We consider resource allocation in a packet-switched network (or inter- net) consisting of multiple links and switches (or routers). Since most of the mechanisms described in this chapter were designed for use on the Internet, and therefore were originally defined in terms of routers rather than switches, we use the term router throughout our discussion. The problem is essentially the same, whether on a network or an internetwork. In such an environment, a given source may have more than enough capacity on the immediate outgoing link to send a packet, but somewhere in the middle of a network its packets encounter a link that is being used by many different traffic sources.1 illustrates this situation— two high-speed links are feeding a low-speed link.
This is in contrast to shared-access networks like Ethernet and wireless networks, where the source can directly observe the traffic on the network and decide accordingly whether or not to send a packet. We have already seen the algorithms used to allocate bandwidth on shared-access networks (Chap- ter 2). These access-control algorithms are, in some sense, analogous to congestion-control algorithms in a switched network. Note that congestion control is a different problem than routing.
While it is true that a congested link could be assigned a large edge weight by the routing pro- tocol, and, as a consequence, routers would route around it, “routing around” a congested link does not generally solve the congestion problem. To see this, we need look no further than the simple network depicted in Figure 6.1, where all traffic has to flow through the same router to reach the destination. Although this is an extreme example, it is common to have a certain router that it is not possible to route around.1 This router can become congested, and there is noth- ing the routing mechanism can do about it. This congested router is sometimes called the bottleneck router.
Connectionless Flows For much of our discussion, we assume that the network is essentially connectionless, with any connection-oriented service implemented in the transport protocol that is running on the end hosts. (We explain the qualification “essentially” in a moment.) This is precisely the model of the 1 It is also worth noting that the complexity of routing in the Internet is such that sim- ply obtaining a reasonably direct, loop-free route is about the best you can hope for. Routing around congestion would be considered icing on the cake. PETERSON-AND-DAVIE 12-ch06-478-577-9780123850591 2011/11/1 21:50 Page 483 #6 6.1 Issues in resource allocation 483 Source 1 Destination Queue 100-Mbps Ethernet Router Source 2 1.1 A potential bottleneck router.
Internet, where IP provides a connectionless datagram delivery service and TCP implements an end-to-end connection abstraction. Note that this assumption does not hold in virtual circuit networks such as ATM and X. In such networks, a connection setup message traverses the network when a circuit is established. This setup message reserves a set of buffers for the connection at each router, thereby pro- viding a form of congestion control—a connection is established only if enough buffers can be allocated to it at each router.
The major shortcom- ing of this approach is that it leads to an underutilization of resources— buffers reserved for a particular circuit are not available for use by other traffic even if they were not currently being used by that circuit. The focus of this chapter is on resource allocation approaches that apply in an internetwork, and thus we focus mainly on connectionless networks. We need to qualify the term connectionless because our classification of networks as being either connectionless or connection oriented is a bit too restrictive; there is a gray area in between. In particular, the assump- tion that all datagrams are completely independent in a connectionless network is too strong.
The datagrams are certainly switched indepen- dently, but it is usually the case that a stream of datagrams between a particular pair of hosts flows through a particular set of routers. This idea of a flow—a sequence of packets sent between a source/destination pair and following the same route through the network—is an important abstraction in the context of resource allocation; it is one that we will use in this chapter. PETERSON-AND-DAVIE 12-ch06-478-577-9780123850591 2011/11/1 21:50 Page 484 #7 484 CHAPTER 6 Congestion control and resource allocation One of the powers of the flow abstraction is that flows can be defined at different granularities. For example, a flow can be host-to-host (i., have the same source/destination host addresses) or process-to-process (i., have the same source/destination host/port pairs).
In the latter case, a flow is essentially the same as a channel, as we have been using that term throughout this book. The reason we introduce a new term is that a flow is visible to the routers inside the network, whereas a channel is an end- to-end abstraction.2 illustrates several flows passing through a series of routers. Because multiple related packets flow through each router, it some- times makes sense to maintain some state information for each flow, information that can be used to make resource allocation decisions about the packets that belong to the flow. This state is sometimes called soft state; the main difference between soft state and hard state is that soft state need not always be explicitly created and removed by signalling.