Second Edition Data Networks DIMITRI BERTSEKAS Massachusetts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL.Englewood Cliffs,New Jersey 07632
Second Edition Data Networks DIMITRI BERTSEKAS Massachusetts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL. Englewood Cliffs, New Jersey 07632
6 WX Window size 3 Time at the Time at the transmitter receiver Permit returns Flow Control 6.1 INTRODUCTION In most networks,there are circumstances in which the externally offered load is larger than can be handled even with optimal routing.Then,if no measures are taken to restrict the entrance of traffic into the network,queue sizes at bottleneck links will grow and packet delays will increase,possibly violating maximum delay specifications. Furthermore,as queue sizes grow indefinitely,the buffer space at some nodes may be exhausted.When this happens,some of the packets arriving at these nodes will have to be discarded and later retransmitted,thereby wasting communication resources.As a result,a phenomenon similar to a highway traffic jam may occur whereby,as the offered load increases,the actual network throughput decreases while packet delay becomes excessive.It is thus necessary at times to prevent some of the offered traffic from entering the network to avoid this type of congestion.This is one of the main functions of flow control. Flow control is also sometimes necessary between two users for speed matching. that is,for ensuring that a fast transmitter does not overwhelm a slow receiver with more packets than the latter can handle.Some authors reserve the term"flow control"for this 493
6 j Time at the transm iller Window size = 3 j Time at the receiver Permit returns Flow Control 6.1 INTRODUCTION In most networks, there are circumstances in which the externally offered load is larger than can be handled even with optimal routing. Then, if no measures are taken to restrict the entrance of traffic into the network, queue sizes at bottleneck links will grow and packet delays will increase, possibly violating maximum delay specifications. Furthermore, as queue sizes grow indefinitely, the buffer space at some nodes may be exhausted. When this happens, some of the packets arriving at these nodes will have to be discarded and later retransmitted, thereby wasting communication resources. As a result, a phenomenon similar to a highway traffic jam may occur whereby, as the offered load increases, the actual network throughput decreases while packet delay becomes excessive. It is thus necessary at times to prevent some of the offered traffic from entering the network to avoid this type of congestion. This is one of the main functions of flow control. Flow control is also sometimes necessary between two users for speed matching, that is, for ensuring that a fast transmitter does not overwhelm a slow receiver with more packets than the latter can handle. Some authors reserve the term "flow control" for this 493
494 Flow Control Chap.6 type of speed matching and use the term "congestion control"for regulating the packet population within the subnetwork.We will not make this distinction in terminology;the type and objective of flow control being discussed will be clear from the context. In this chapter we describe schemes currently used for fow control,explain their advantages and limitations,and discuss potential approaches for their improvement.In the remainder of this section we identify the principal means and objectives of flow control.In Sections 6.2 and 6.3 we describe the currently most popular flow control methods;window strategies and rate control schemes.In Section 6.4 we describe flow control in some representative networks.Section 6.5 is devoted to various algorithmic aspects of rate control schemes. 6.1.1 Means of Flow Control Generally.a need for flow control arises whenever there is a constraint on the commu- nication rate between two points due to limited capacity of the communication lines or the processing hardware.Thus.a flow control scheme may be required between two users at the transport layer,between a user and an entry point of the subnet (network layer),between two nodes of the subnet(network layer),or between two gateways of an interconnected network (internet layer).We will emphasize flow control issues within the subnet,since flow control in other contexts is in most respects similar. The term "session"is used somewhat loosely in this chapter to mean any communi- cation process to which flow control is applied.Thus a session could be a virtual circuit, a group of virtual circuits (such as all virtual circuits using the same path),or the entire packet flow originating at one node and destined for another node.Often,flow control is applied independently to individual sessions,but there is a strong interaction between its effects on different sessions because the sessions share the network's resources. Note that different sessions may have radically different service requirements. For example,sessions transferring files may tolerate considerable delay but may re- quire strict error control,while voice and video sessions may have strict minimum data rate and maximum end-to-end delay requirements,but may tolerate occasional packet losses. There are many approaches to flow control,including the following: 1.Call blocking.Here a session is simply blocked from entering the network (its access request is denied).Such control is needed,for example,when the session requires a minimum guaranteed data rate that the network cannot provide due to limited uncommitted transmission capacity.A typical situation is that of the voice telephone network and,more generally,circuit switched networks,all of which use flow control of this type.However,a call blocking option is also necessary in integrated voice,video,and data networks,at least with respect to those sessions requiring guaranteed rate.In a more general view of call blocking one may admit a session only after a negotiation of some "service contract,"for example,an agreement on some service parameters for the session's input traffic (maximum rate,minimum rate,maximum burst size.priority level,etc.)
494 Flow Control Chap. 6 type of speed matching and use the tenn "congestion control" for regulating the packet population within the subnetwork. We will not make this distinction in tenninology; the type and objective of flow control being discussed will be clear from the context. In this chapter we describe schemes currently used for flow control, explain their advantages and limitations, and discuss potential approaches for their improvement. In the remainder of this section we identify the principal means and objectives of flow control. In Sections 6.2 and 6.3 we describe the currently most popular flow control methods; window strategies and rate control schemes. In Section 6.4 we describe flow control in some representative networks. Section 6.5 is devoted to various algorithmic aspects of rate control schemes. 6.1.1 Means of Flow Control Generally, a need for flow control arises whenever there is a constraint on the communication rate between two points due to limited capacity of the communication lines or the processing hardware. Thus, a flow control scheme may be required between two users at the transport layer, between a user and an entry point of the subnet (network layer), between two nodes of the subnet (network layer), or between two gateways of an interconnected network (internet layer). We will emphasize flow control issues within the subnet, since flow control in other contexts is in most respects similar. The tenn "session" is used somewhat loosely in this chapter to mean any communication process to which flow control is applied. Thus a session could be a virtual circuit, a group of virtual circuits (such as all virtual circuits using the same path), or the entire packet flow originating at one node and destined for another node. Often, flow control is applied independently to individual sessions, but there is a strong interaction between its effects on different sessions because the sessions share the network's resources. Note that different sessions may have radically different service requirements. For example, sessions transferring files may tolerate considerable delay but may require strict error control, while voice and video sessions may have strict minimum data rate and maximum end-to-end delay requirements, but may tolerate occasional packet losses. There are many approaches to flow control, including the following: 1. Call blocking. Here a session is simply blocked from entering the network (its access request is denied). Such control is needed, for example, when the session requires a minimum guaranteed data rate that the network cannot provide due to limited uncommitted transmission capacity. A typical situation is that of the voice telephone network and, more generally, circuit switched networks, all of which use flow control of this type. However, a call blocking option is also necessary in integrated voice, video, and data networks, at least with respect to those sessions requiring guaranteed rate. In a more general view of call blocking one may admit a session only after a negotiation of some "service contract," for example, an agreement on some service parameters for the session's input traffic (maximum rate, minimum rate, maximum burst size, priority level, etc.)
Sec.6.1 Introduction 495 2.Packer discarding.When a node with no available buffer space receives a packet, it has no alternative but to discard the packet.More generally,however,packets may be discarded while buffer space is still available if they belong to sessions that are using more than their fair share of some resource.are likely to cause congestion for higher-priority sessions,are likely to be discarded eventually along their path, and so on.(Note that if a packet has to be discarded anyway,it might as well be discarded as early as possible to avoid wasting additional network resources unnecessarily.)When some of a session's packets are discarded,the session may need to take some corrective action,depending on its service requirements.For sessions where all packets carry essential information (e.g..file transfer sessions), discarded packets must be retransmitted by the source after a suitable timeout; such sessions require an acknowledgment mechanism to keep track of the pack- ets that failed to reach their destination.On the other hand,for sessions such as voice or video,where delayed information is useless,there is nothing to be done about discarded packets.In such cases,packets may be assigned different levels of priority.and the network may undertake the obligation never to discard the highest-priority packets-these are the packets that are sufficient to support the minimum acceptable quality of service for the session.The data rate of the highest-priority packets (the minimum guaranteed rate)may then be negotiated between the network and the source when the session is established.This rate may also be adjusted in real time,depending on the congestion level in the net- work. 3.Packet blocking.When a packet is discarded at some node.the network resources that were used to get the packet to that node are wasted.It is thus preferable to restrict a session's packets from entering the network if after entering they are to be discarded.If the packets carry essential information,they must wait in a queue outside the network:otherwise,they are discarded at the source.In the latter case,however,the flow control scheme must honor any agreement on a minimum guaranteed rate that the session may have negotiated when it was first established. 4.Packer scheduling.In addition to discarding packets.a subnetwork node can ex- ercise flow control by selectively expediting or delaying the transmission of the packets of various sessions.For example,a node may enforce a priority service discipline for transmitting packets of several different priorities on a given outgo- ing link.As another example,a node may use a(possibly weighted)round-robin scheduling strategy to ensure that various sessions can access transmission lines in a way that is consistent both with some fairess criterion and also with the minimum data rate required by the sessions.Finally,a node may receive infor- mation regarding congestion farther along the paths used by some sessions,in which case it may appropriately delay the transmission of the packets of those sessions. In subsequent sections we discuss specific strategies for throttling sources and for restricting traffic access to the network
Sec. 6.1 Introduction 495 2. Packet discarding. When a node with no available buffer space receives a packet, it has no alternative but to discard the packet. More generally, however, packets may be discarded while buffer space is still available if they belong to sessions that are using more than their fair share of some resource, are likely to cause congestion for higher-priority sessions, are likely to be discarded eventually along their path, and so on. (Note that if a packet has to be discarded anyway, it might as well be discarded as early as possible to avoid wasting additional network resources unnecessarily.) When some of a session's packets are discarded, the session may need to take some corrective action, depending on its service requirements. For sessions where all packets carry essential information (e.g., file transfer sessions), discarded packets must be retransmitted by the source after a suitable timeout; such sessions require an acknowledgment mechanism to keep track of the packets that failed to reach their destination. On the other hand, for sessions such as voice or video, where delayed information is useless, there is nothing to be done about discarded packets. In such cases, packets may be assigned different levels of priority, and the network may undertake the obligation never to discard the highest-priority packets-these are the packets that are sufficient to support the minimum acceptable quality of service for the session. The data rate of the highest-priority packets (the minimum guaranteed rate) may then be negotiated between the network and the source when the session is established. This rate may also be adjusted in real time, depending on the congestion level in the network. 3. Packet blocking. When a packet is discarded at some node, the network resources that were used to get the packet to that node are wasted. It is thus preferable to restrict a session's packets from entering the network if after entering they are to be discarded. If the packets carry essential information, they must wait in a queue outside the network; otherwise, they are discarded at the source. In the latter case, however, the flow control scheme must honor any agreement on a minimum guaranteed rate that the session may have negotiated when it was first established. 4. Packet scheduling. In addition to discarding packets, a subnetwork node can exercise flow control by selectively expediting or delaying the transmission of the packets of various sessions. For example, a node may enforce a priority service discipline for transmitting packets of several different priorities on a given outgoing link. As another example, a node may use a (possibly weighted) round-robin scheduling strategy to ensure that various sessions can access transmission lines in a way that is consistent both with some fairness criterion and also with the minimum data rate required by the sessions. Finally, a node may receive information regarding congestion farther along the paths used by some sessions, in which case it may appropriately delay the transmission of the packets of those sessions. In subsequent sections we discuss specific strategies for throttling sources and for restricting traffic access to the network
496 Flow Control Chap.6 6.1.2 Main Objectives of Flow Control We look now at the main principles that guide the design of flow control algorithms. Our focus is on two objectives.First.strike a good compromise between throttling sessions (subject to minimum data rate requirements)and keeping average delay and buffer overfow at a reasonable level.Second.maintain fairness between sessions in providing the requisite qualiry of service. Limiting delay and buffer overflow.We mentioned earlier that for important classes of sessions,such as voice and video,packets that are excessively delayed are useless.For such sessions,a limited delay is essential and should be one of the chief concerns of the flow control algorithm;for example,such sessions may be given high priority. For other sessions.a small average delay per packet is desirable but it may not be crucial.For these sessions,network level flow control does not necessarily reduce delay; it simply shifts delay from the network layer to higher layers.That is,by restricting entrance to the subnet,flow control keeps packets waiting outside the subnet rather than in queues inside it.In this way.however.flow control avoids wasting subnet resources in packet retransmissions and helps prevent a disastrous traffic jam inside the subnet.Retransmissions can occur in two ways:first.the buildup of queues causes buffer overflow to occur and packets to be discarded;second,slow acknowledgments can cause the source node to retransmit some packets because it thinks mistakenly that they have been lost.Retransmissions waste network resources,effectively reduce network throughput.and cause congestion to spread.The following example (from [GeK80]) illustrates how buffer overflow and attendant retransmissions can cause congestion. Example 6.1 Consider the five-node network shown in Fig.6.1(a).There are two sessions.one from top to bottom with a Poisson input rate of 0.8.and the other from left to right with a Poisson input rate f.Assume that the central node has a large but finite buffer pool that is shared on a first-come first-serve basis by the two sessions.If the buffer pool is full,an incoming packet is rejected and then retransmitted by the sending node.For small f.the buffer rarely fills up and the total throughput of the system is 0.8+f.When f is close to unity (which is the capacity of the rightmost link).the buffer of the central node is almost always full,while the top and left nodes are busy most of the time retransmitting packets.Since the left node is transmitting 10 times faster than the top node.it has a 10-fold greater chance of capturing a buffer space at the central node.so the left-to-right throughput will be roughly 10 times larger than the top-to-bottom throughput.The left-to-right throughput will be roughly unity (the capacity of the rightmost link).so that the total throughput will be roughly 1.1.This is illustrated in more detail in Fig.6.1(b).where it can be seen that the total throughput decreases toward 1.I as the offered load f increases. This example also illustrates how with buffer overflow.some sessions can capture almost all the buffers and nearly prevent other sessions from using the network.To avoid this,it is sometimes helpful to implement a buffer management scheme.In such a scheme.packets are divided in different classes based,for example,on origin,destination
496 6.1.2 Main Objectives of Flow Control Flow Control Chap. 6 We look now at the main principles that guide the design of flow control algorithms. Our focus is on two objectives. First, strike a good compromise hetween throttling sessions (suhject to minimum data rate requirements) and keeping average delay and huller overflow at a reasonable level. Second, maintain fairness hetween sessions in providing the requisite qualit..... of service. Limiting delay and buffer overflow. We mentioned earlier that for important classes of sessions, such as voice and video, packets that are excessively delayed are useless. For such sessions, a limited delay is essential and should be one of the chief concerns of the flow control algorithm; for example, such sessions may be given high priority. For other sessions, a small average delay per packet is desirable but it may not be crucial. For these sessions, network level flow control does not necessarily reduce delay; it simply shifts delay from the network layer to higher layers. That is, by restricting entrance to the subnet, flow control keeps packets waiting outside the subnet rather than in queues inside it. In this way, however, flow control avoids wasting subnet resources in packet retransmissions and helps prevent a disastrous traffic jam inside the subnet. Retransmissions can occur in two ways: first, the buildup of queues causes buffer overflow to occur and packets to be discarded; second, slow acknowledgments can cause the source node to retransmit some packets because it thinks mistakenly that they have been lost. Retransmissions waste network resources, effectively reduce network throughput, and cause congestion to spread. The following example (from lGeK80]) illustrates how buffer overflow and attendant retransmissions can cause congestion. Example 6,1 Consider the five-node network shown in Fig. 6.1 (a). There are two sessions, one from top to bottom with a Poisson input rate of 0.8. and the other from left to right with a Poisson input rate f. Assume that the central node has a large but finite buffer pool that is shared on a first-come first-serve basis by the two sessions. If the buffer pool is full, an incoming packet is rejected and then retransmitted by the sending node. For small f, the buffer rarely tills up and the total throughput of the system is 0.8 +f. When f is close to unity (which is the capacity of the rightmost link), the buffer of the central node is almost always full, while the top and left nodes are busy most of the time retransmitting packets. Since the left node is transmitting 10 times faster than the top node. it has a la-fold greater chance of capturing a buffer space at the central node. so the left-to-right throughput will be roughly 10 times larger than the top-to-boltom throughput. The left-to-right throughput will be roughly unity (the capacity of the rightmost link). so that the total throughput will be roughly 1.1. This is illustrated in more detail in Fig. 6.i(b). where it can be seen that the total throughput decreases toward i.1 as the offered load f increases. This example also illustrates how with buffer overflow. some sessions can capture almost all the buffers and nearly prevent other sessions from using the network. To avoid this, it is sometimes helpful to implement a hutler management scheme. In such a scheme. packets are divided in different classes based, for example, on origin, destination