502 Flow Control Chap.6 simplify the following exposition,assume that all packets have equal transmission time and equal round-trip delay.) The case where flow control is active is shown in Fig.6.7.Here d>WX and the round-trip delay d is so large that the full allocation of I'packets can be transmitted before the first permit returns.Assuming that the source always has a packet waiting in queue,the rate of transmission is W'/d packets/sec. If the results of Figs.6.6 and 6.7 are combined,it is seen that the maximum rate of transmission corresponding to a round-trip delay d is given by r=min x a (6.1) Figure 6.8 illustrates the flow control mechanism;the source transmission rate is reduced in response to congestion and the attendant large delay.Furthermore,assuming that II'is relatively small,the window scheme reacts fast to congestion-within at most I packets'transmission time.This fast reaction,coupled with low overhead,is the major advantage of window strategies over other (nonwindow)schemes. Limitations of end-to-end windows.One drawback of end-to-end windows is that they cannot guarantee a minimum communication rate for a session.Thus win- dows are inadequate for sessions that require a minimum guaranteed rate,such as voice and video sessions.Other drawbacks of the end-to-end window strategy have to do with window sizes.There is a basic trade-off here:One would like to make window sizes small to limit the number of packets in the subnet,thus avoiding large delays and congestion,and one would also like to make window sizes large to allow full-speed transmission and maximal throughput under light-to-moderate traffic conditions.De- termining the proper window size and adjusting that size in response to congestion is not easy.This delay-throughput trade-off is particularly acute for high-speed networks, where because of high propagation delay relative to packet transmission time,window sizes should be large to allow high data rates [cf.Eq.(6.1)and Fig.6.8].One should re- member,however,that the existence of a high-speed network does not necessarily make W> Window size 3 Permit Figure 6.6 Example of full-speed returns transmission with a window size '=3. The round-trip delay d is less than the time Time at the Time at the I'X required to transmit the full window transmitter receiver of packets
502 Flow Control Chap. 6 simplify the following exposition, assume that all packets have equal transmission time and equal round-trip delay.) The case where flow control is active is shown in Fig. 6.7. Here d > ~FX and the round-trip delay d is so large that the full allocation of H' packets can be transmitted before the first permit returns. Assuming that the source always has a packet waiting in queue, the rate of transmission is ~F / d packets/sec. If the results of Figs. 6.6 and 6.7 are combined, it is seen that the maximum rate of transmission corresponding to a round-trip delay d is given by r = min{~. W} X'd (6. I) Figure 6.8 illustrates the flow control mechanism; the source transmission rate is reduced in response to congestion and the attendant large delay. Furthermore, assuming that n- is relatively small, the window scheme reacts fast to congestion-within at most n' packets' transmission time. This fast reaction, coupled with low overhead, is the major advantage of window strategies over other (nonwindow) schemes. Limitations of end-to-end windows. One drawback of end-to-end windows is that they cannot guarantee a minimum communication rate for a session. Thus windows are ihadequate for sessions that require a minimum guaranteed rate, such as voice and video sessions. Other drawbacks of the end-to-end window strategy have to do with window sizes. There is a basic trade-off here: One would like to make window sizes small to limit the number of packets in the subnet, thus avoiding large delays and congestion, and one would also like to make window sizes large to allow full-speed transmission and maximal throughput under light-to-moderate traffic conditions. Determining the proper window size and adjusting that size in response to congestion is not easy. This delay-throughput trade-off is particularly acute for high-speed networks, where because of high propagation delay relative to packet transmission time, window sizes should be large to allow high data rates [cf. Eq. (6. I) and Fig. 6.8]. One should remember, however, that the existence of a high-speed network does not necessarily make Permit returns Time at the transmitter Window size = 3 J Time at the receiver Figure 6.6 Example of full-speed transmission with a window size H' = 3. The round-trip delay d is less than the time H'X required to transmit the full window of W packets
Sec.6.2 Window Flow Control 503 WX Window size =3 Time at the Time at the transmitter receiver Permit returns Figure 6.7 Example of delayed transmission with a window size W=3.The round- trip delay d is more than the time l'X required to transmit the full window of M packets.As a result,window flow control becomes active.restricting the input rate to W/d. Full speed transmission rate -IX Y Point where flow control begins 0 WX Round-Trip Delay d Figure 6.8 Transmission rate versus round-trip delay in a window flow control system. This oversimplified relationship assumes that all packets require equal transmission time at the source and have equal round-trip packet/permit delay. it desirable for individual sessions to transmit at the full network speed.For high-speed networks,it is generally true that the window size of the session should be proportional to the round-trip propagation delay for the session.However,the window size should also be proportional to the session's maximum desired rate rather than the maximum rate allowed by the network;cf.Eq.(6.1). End-to-end windows may also fail to provide adequte control of packet delay. To understand the relation between window size,delay,and throughput,suppose that there are n actively flow controlled sessions in the network with fixed window sizes 1,....IIn.Then the total number of packets and permits traveling in the network is
Sec. 6.2 Window Flow Control 503 Time at the transm itter Permit returns Window size = 3 t Time at the receiver ... 1 X cr: '" c: 0 :~ E '" c: '".= Figure 6.7 Example of delayed transmission with a window size ~V = 3. The roundtrip delay d is more than the time H"X required to transmit the full window of H' packets. As a result, window flow control becomes active, restricting the input rate to ~V jd. Full speed transm ission rate a WX Round-Trip Delay d Figure 6.8 Transmission rate versus round-trip delay in a window flow control system. This oversimplified relationship assumes that all packets require equal transmission time at the source and have equal round-trip packet/permit delay. it desirable for individual sessions to transmit at the full network speed. For high-speed networks, it is generally true that the window size of the session should be proportional to the round-trip propagation delay for the session. However, the window size should also be proportional to the session's maximum desired rate rather than the maximum rate allowed by the network; cf. Eq. (6.1). End-to-end windows may also fail to provide adequte control of packet delay. To understand the relation between window size, delay, and throughput, suppose that there are n actively flow controlled sessions in the network with fixed window sizes TVj , .•• , TFn . Then the total number of packets and permits traveling in the network is
504 Flow Control Chap.6 "W.Focusing on packets (rather than permits).we see that their number in the network is whereis a factor between 0 and I that depends on the relative magnitude of return delay for the permit and the extent to which permits are piggybacked on regular packets.By Little's Theorem,the average delay per packet is given by T=13, 入 where A is the throughput (total accepted input rate of sessions).As the number of sessions increases,the throughput A is limited by the link capacities and will approach a constant.(This constant will depend on the network.the location of sources and destinations,and the routing algorithm.)Therefore,the delay T will roughly increase proportionately to the number of sessions (more accurately their total window size)as shown in Fig.6.9.Thus,if the number of sessions can become very large,the end-to- end window scheme may not be able to keep delay at a reasonable level and prevent congestion. One may consider using small window sizes as a remedy to the problem of very large delays under high load conditions.Unfortunately,in many cases (particularly in low-and moderate-speed networks)one would like to allow sessions to transmit at maximum speed when there is no other interfering traffic,and this imposes a lower bound on window sizes.Indeed,if a session is using an n-link path with a packet transmission time X on each link.the round-trip packet and permit delay will be at least nX and considerably more if permits are not given high priority on the return channel. For example,if permits are piggybacked on return packets traveling on the same path in the opposite direction,the return time will be at least nX also.So from Fig.6.8, we see that full-speed transmission will not be possible for that session even under light load conditions unless the window size exceeds the number of links n on the path(see Fig.6.10).For this reason,recommended window sizes are typically between n and 3n. This recommendation assumes that the transmission time on each link is much larger than the processing and propagation delay.When the propagation delay is much larger than Average delay Figure 6.9 Average delay per packet per packet and throughput as a function of the number of actively window flow controlled sessions in the network.When the network is heavily loaded.the average delay per packet increases approximately linearly with the number of active sessions.while Throughput the total throughput stays approximately constant.(This assumes that there are no retransmissions due to buffer overflow and/or large permit delays.In the presence of retransmissions.throughput may decrease as the number of active sessions Number of Actively Flow Controlled Processes increases.)
504 Flow Control Chap. 6 L~~l W" Focusing on packets (rather than pennits), we see that their number in the network is L;~13i TVi , where ;3, is a factor between 0 and 1 that depends on the relative magnitude of return delay for the pennit and the extent to which pennits are piggybacked on regular packets. By Little's Theorem, the average delay per packet is given by T = L;'=13iWi A where A is the throughput (total accepted input rate of sessions). As the number of sessions increases, the throughput A is limited by the link capacities and will approach a constant. (This constant will depend on the network, the location of sources and destinations, and the routing algorithm.) Therefore, the delay T will roughly increase proportionately to the number of sessions (more accurately their total window size) as shown in Fig. 6.9. Thus, if the number of sessions can become very large, the end-toend window scheme may not be able to keep delay at a reasonable level and prevent congestion. One may consider using small window sizes as a remedy to the problem of very large delays under high load conditions. Unfortunately, in many cases (particularly in low- and moderate-speed networks) one would like to allow sessions to transmit at maximum speed when there is no other interfering traffic, and this imposes a lower bound on window sizes. Indeed, if a session is using an n-Iink path with a packet transmission time X on each link, the round-trip packet and pennit delay will be at least nX and considerably more if pennits are not given high priority on the return channel. For example, if permits are piggybacked on return packets traveling on the same path in the opposite direction, the return time will be at least nX also. So from Fig. 6.8, we see that full-speed transmission will not be possible for that session even under light load conditions unless the window size exceeds the number of links n on the path (see Fig. 6.10). For this reason, recommended window sizes are typically between nand 3n. This recommendation assumes that the transmission time on each link is much larger than the processing and propagation delay. When the propagation delay is much larger than o Average delay per packet Throughput Number of Actively Flow Controlled Processes Figure 6.9 Average delay per packet and throughput as a function of the number of actively window flow controlled sessions in the network. When the network is heavily loaded. the average delay per packet increases approximately linearly with the number of active sessions. while the total throughput stays approximately constanl. (This assumes that there are no retransmissions due to buffer overflow and/or large permit delays. In the presence of retransmissions. throughput may decrease as the number of active sessions increases.)
Sec.6.2 Window Flow Control 505 the transmission time,as in satellite links and some high-speed networks,the appropriate window size might be much larger.This is illustrated in the following example. Example 6.2 Consider a transmission line with capacity of 1 gigabit per second (10 bits/sec)connecting two nodes which are 50 miles apart.The round-trip propagation delay can be roughly esti- mated as I millisecond.Assuming a packet size of 1000 bits.it is seen that a window size of at least 1000 packets is needed to sustain full-speed transmission:it is necessary to have 1000 packets and permits simultaneously propagating along the transmission line to"keep the pipeline full,"with permits returning fast enough to allow unimpeded transmission of new packets.By extrapolation it is seen that Atlantic coast to Pacific coast end-to-end trans- mission over a distance of.say.3000 miles requires a window size of at least 60.000 packets! Fortunately,for most sessions.such unimpeded transmission is neither required nor desirable. Example 6.2 shows that windows should be used with care when high-speed trans- mission over a large distance is involved:they require excessive memory and they re- spond to congestion relatively slowly when the round-trip delay time is very long relative to the packet transmission time.For networks with relatively small propagation delays. end-to-end window flow control may be workable,particularly if there is no requirement for a minimum guaranteed rate.However,to achieve a good trade-off between delay and throughput,dynamic window adjustment is necessary.Under light load conditions,win- dows should be large and allow unimpeded transmission,while under heavy load condi- tions,windows should shrink somewhat,thereby not allowing delay to become excessive. This is not easy to do systematically.but some possibilities are examined in Section 6.2.5. End-to-end windows can also perform poorly with respect to fairness.It was argued earlier that when propagation delay is relatively small.the proper window size of a session should be proportional to the number of links on its path.This means that at a heavily loaded link,long-path sessions can have many more packets awaiting transmission than short-path sessions.thereby obtaining a proportionately larger throughput.A typical situation is illustrated in Fig.6.11.Here the windows of all sessions accumulate at the heavily loaded link.If packets are transmitted in the order of their arrival,the rate of transmission obtained by each session is roughly proportional to its window size,and this favors the long-path sessions. 一 mcom D mmom Permit Permit Permit Figure 6.10 The window size must be at least equal to the number of links on the path to achieve full-speed transmission.(Assuming equal transmission time on each link. a packet should be transmitted at cach link along the path simultaneously to achieve nonstop transmission.)If permit delay is comparable to the forward delay.the window size should be doubled.If the propagation delay is not negligible.an even larger window size is needed
Sec. 6.2 Window Flow Control 505 the transmission time, as in satellite links and some high-speed networks, the appropriate window size might be much larger. This is illustrated in the following example. Example 6.2 Consider a transmission line with capacity of I gigabit per second (109 bits/sec) connecting two nodes which are 50 miles apart. The round-trip propagation delay can be roughly estimated as I millisecond. Assuming a packet size of 1000 bits. it is seen that a window size of at least lOOO packets is needed to sustain full-speed transmission; it is necessary to have lOOO packets and permits simultaneously propagating along the transmission line to "keep the pipeline full," with permits returning fast enough to allow unimpeded transmission of new packets. By extrapolation it is seen that Atlantic coast to Pacific coast end-to-end transmission over a distance of. say. 3000 miles requires a window size of at least 60.000 packets! Fortunately, for most sessions, such unimpeded transmission is neither required nor desirable. Example 6.2 shows that windows should be used with care when high-speed transmission over a large distance is involved; they require excessive memory and they respond to congestion relatively slowly when the round-trip delay time is very long relative to the packet transmission time. For networks with relatively small propagation delays, end-to-end window flow control may be workable, particularly if there is no requirement for a minimum guaranteed rate. However, to achieve a good trade-off between delay and throughput, dynamic window adjustment is necessary. Under light load conditions, windows should be large and allow unimpeded transmission, while under heavy load conditions, windows should shrink somewhat, thereby not allowing delay to become excessive. This is not easy to do systematically, but some possibilities are examined in Section 6.2.5. End-to-end windows can also perform poorly with respect to fairness. It was argued earlier that when propagation delay is relatively small, the proper window size of a session should be proportional to the number of links on its path. This means that at a heavily loaded link, long-path sessions can have many more packets awaiting transmission than short-path sessions, thereby obtaining a proportionately larger throughput. A typical situation is illustrated in Fig. 6.11. Here the windows of all sessions accumulate at the heavily loaded link. If packets are transmitted in the order of their arrival, the rate of transmission obtained by each session is roughly proportional to its window size, and this favors the long-path sessions. --- ---- -G""""IIII' -0'111111111111 -0'"""1"111 -0-- IPermit I IPermit I IPermit I --- --- --- Figure 6.10 The window size must be at least equal to the number of links on the path to achieve full-speed transmission. (Assuming equal transmission time on each link. a packet should be transmitted at each link along the path simultaneously to achieve nonstop transmission.) If peffi1it delay is comparable to the forward delay. the window size should be doubled. If the propagation delay is not negligible. an even larger window size is needed
506 Flow Control Chap.6 The fairness properties of end-to-end windows can be improved if flow-controlled sessions of the same priority class are served via a weighted round-robin scheme at each transmission queue.Such a scheme should take into account the priorities as well as the minimum guaranteed rate of different sessions.Using a round-robin scheme is conceptu- ally straightforward when each session is a virtual circuit,but not in a datagram network, where it may not be possible to associate packets with particular flow-controlled sessions. 6.2.2 Node-by-Node Windows for Virtual Circuits In this strategy,there is a separate window for every virtual circuit and pair of adjacent nodes along the path of the virtual circuit.Much of the discussion on end-to-end windows applies to this scheme as well.Since the path along which flow control is exercised is effectively one link long,the size of a window measured in packets is typically two or three for moderate-speed terrestrial links.For high-speed networks,the required window size might be much larger,thereby making the node-by-node strategy less attractive. For this reason,the following discussion assumes that a window size of about two is a reasonable choice. Let us focus on a pair of successive nodes along a virtual circuit's path;we refer to them as the transmitter and the receiver.The main idea in the node-by-node scheme is that the receiver can avoid the accumulation of a large number of packets into its memory by slowing down the rate at which it returns permits to the transmitter.In the most common strategy,the receiver maintains a W-packet buffer for each virtual circuit and returns a permit to the transmitter as soon as it releases a packet from its W-packet buffer.A packet is considered to be released from the W-packet buffer once it is either delivered to a user outside the subnet or is entered in the data link control (DLC)unit leading to the subsequent node on the virtual circuit's path. Consider now the interaction of the windows along three successive nodes (i-1,i, and+1)on a virtual circuit's path.Suppose that the W-packet buffer of nodeiis full. Then node i will send a permit to node i-I once it delivers an extra packet to the DLC of the (i,i+1)link,which in turn will occur once a permit sent by node (+1)is received at node i.Thus,there is coupling of successive windows along the path of a virtual circuit. In particular,suppose that congestion develops at some link.Then the W-packet window Long path session Heavily loaded link Short path session Figure 6.11 End-to-end windows discriminate in favor of long-path sessions.It is nec- essary to give a large window to a long-path session to achieve full-speed transmission. Therefore.a long-path session will typically have more packets waiting at a heavily loaded link than will a short-path session,and will receive proportionally larger service (assuming that packets are transmitted on a first-come first-serve basis)
506 Flow Control Chap. 6 The fairness properties of end-to-end windows can be improved if flow-controlled sessions of the same priority class are served via a weighted round-robin scheme at each transmission queue. Such a scheme should take into account the priorities as well as the minimum guaranteed rate of different sessions. Using a round-robin scheme is conceptually straightforward when each session is a virtual circuit, but not in a datagram network, where it may not be possible to associate packets with particular flow-controlled sessions. 6.2.2 Node-by-Node Windows for Virtual Circuits In this strategy, there is a separate window for every virtual circuit and pair of adjacent nodes along the path of the virtual circuit. Much of the discussion on end-to-end windows applies to this scheme as well. Since the path along which flow control is exercised is effectively one link long, the size of a window measured in packets is typically two or three for moderate-speed terrestrial links. For high-speed networks, the required window size might be much larger, thereby making the node-by-node strategy less attractive. For this reason, the following discussion assumes that a window size of about two is a reasonable choice. Let us focus on a pair of successive nodes along a virtual circuit's path; we refer to them as the transmitter and the receiver. The main idea in the node-by-node scheme is that the receiver can avoid the accumulation of a large number of packets into its memory by slowing down the rate at which it returns permits to the transmitter. In the most common strategy, the receiver maintains a W -packet buffer for each virtual circuit and returns a permit to the transmitter as soon as it releases a packet from its W -packet buffer. A packet is considered to be released from the W -packet buffer once it is either delivered to a user outside the subnet or is entered in the data link control (DLC) unit leading to the subsequent node on the virtual circuit's path. Consider now the interaction of the windows along three successive nodes (i -1, i, and i + 1) on a virtual circuit's path. Suppose that the W -packet buffer of nodei is full. Then node i will send a permit to nodei - 1 once it delivers an extra packet to the DLC of the (i, i+ 1) link, which in tum will occur once a permit sent by node (i+ 1) is received at node i. Thus, there is coupling of successive windows along the path of a virtual circuit. In particular, suppose that congestion develops at some link. Then the W -packet window ~) Long path ~seSSion () () Heavily loaded link I Short path session Figure 6.11 End-to-end windows discriminate in favor of long-path sessions. It is necessary to give a large window to a long-path session to achieve full-speed transmission. Therefore. a long-path session will typically have more packets waiting at a heavily loaded link than will a short-path session, and will receive proportionally larger service (assuming that packets are transmitted on a first-come first-serve basis)