498 Flow Control Chap.6 nodes A and B routing packets directly to each other as shown in Fig.6.2(a).If all the buffers of both A and B are full of packets destined for B and A,respectively. then the nodes are deadlocked into continuously retransmitting the same packets with no success,as there is no space to store the packets at the receiver.This problem can also occur in a more complex manner whereby more than two nodes arranged in a cycle are deadlocked because their buffers are full of packets destined for other nodes in the cycle [see Fig.6.2(b)].There are simple buffer management schemes that preclude this type of deadlock by organizing packets in priority classes and allocating extra buffers for packets of higher priority ([RaH76]and [Gop85]).A typical choice is to assign a level of priority to a packet equal to the number of links it has traversed in the network, as shown in Fig.6.3.If packets are not allowed to loop,it is then possible to show that a deadlock of the type just described cannot occur. We finally note that when offered load is large,limited delay and buffer overflow can be achieved only by lowering the input to the network.Thus,there is a natural trade-off between giving sessions free access to the network and keeping delay at a level low enough so that retransmissions or other inefficiencies do not degrade network performance.A somewhat oversimplified guideline is that,ideally,flow control should not be exercised at all when network delay is below some critical level,and,under heavy load conditions,should reject as much offered traffic as necessary to keep delay at the critical level.Unfortunately.this is easier said than done,since neither delay nor throughput can be represented meaningfully by single numbers in a flow control context. Fairness.When offered traffic must be cut back,it is important to do so fairly. The notion of fairness is complicated,however,by the presence of different session priorities and service requirements.For example,some sessions need a minimum guar- anteed rate and a strict upper bound on network delay.Thus,while it is appropriate to consider simple notions of fairness within a class of"similar"sessions,the notion of Figure 6.2 Deadlock due to buffer overflow.In (a).all buffers of A and B are full of packets destined for B and A. D respectively.As a result,no packet can be accepted at either node.In(b).all buffers (b) of A.B.C.and D are full of packets destined for C.D.A.and B.respectively498 Flow Control Chap. 6 nodes A and B routing packets directly to each other as shown in Fig. 6.2(a). If all the buffers of both A and B are full of packets destined for B and A, respectively, then the nodes are deadlocked into continuously retransmitting the same packets with no success, as there is no space to store the packets at the receiver. This problem can also occur in a more complex manner whereby more than two nodes arranged in a cycle are deadlocked because their buffers are full of packets destined for other nodes in the cycle [see Fig. 6.2(b)]. There are simple buffer management schemes that preclude this type of deadlock by organizing packets in priority classes and allocating extra buffers for packets of higher priority ([RaH76] and [Gop85]). A typical choice is to assign a level of priority to a packet equal to the number of links it has traversed in the network, as shown in Fig. 6.3. If packets are not allowed to loop, it is then possible to show that a deadlock of the type just described cannot occur. We finally note that when offered load is large, limited delay and buffer overflow can be achieved only by lowering the input to the network. Thus, there is a natural trade-off between giving sessions free access to the network and keeping delay at a level low enough so that retransmissions or other inefficiencies do not degrade network performance. A somewhat oversimplified guideline is that, ideally, flow control should not be exercised at all when network delay is below some critical level, and, under heavy load conditions, should reject as much offered traffic as necessary to keep delay at the critical level. Unfortunately, this is easier said than done, since neither delay nor throughput can be represented meaningfully by single numbers in a flow control context. Fairness. When offered traffic must be cut back, it is important to do so fairly. The notion of fairness is complicated, however, by the presence of different session priorities and service requirements. For example, some sessions need a minimum guar￾anteed rate and a strict upper bound on network delay. Thus, while it is appropriate to consider simple notions of fairness within a class of "similar" sessions, the notion of (a) (b) Figure 6.2 Deadlock due to buffer overflow. In (a). all buffers of A and B are full of packets destined for B and A. respectively. As a result. no packet can be accepted at either node. In (b), all buffers of A. B. C. and D are full of packets destined for C. D, A. and B. respectively