Sec.6.2 Window Flow Control 499 Class N-1 Class N-1 。年0 。。。 Class+1 Class Buffer space Buffer space for packets for packets 4。t that have that have travelled Class 1 Class 1 travelled klinks +1 links Class 0 Class 0 Figure 6.3 Organization of node memory in buffer classes to avoid deadlock due to buffer overflow.A packet that has traveled k links is accepted at a node only if there is an available buffer of class or lower.where k ranges from 0 to N-I (where N is the number of nodes).Assuming that packets that travel more than N-I links are discarded as having traveled in a toop.no deadlock occurs.The proof consists of showing by induction (starting with k=N-1)that at each node the buffers of class k cannot fill up permanently. fairness between classes is complex and involves the requirements of those classes.Even within a class,there are several notions of fairness that one may wish to adopt.The example of Fig.6.4 illustrates some of the contradictions inherent in choosing a fairness criterion.There are n+I sessions each offering I unit/sec of traffic along a sequence of n links with capacity of I unit/sec.One session's traffic goes over all n links,while the rest of the traffic goes over only one link.A maximum throughput of n units/sec can be achieved by accepting all the traffic of the single-link sessions while shutting off the n-link session.However,if our objective is to give equal rate to all sessions,the resulting throughput is only (n+1)/2 units/sec.Alternatively,if our objective is to give equal resources to all sessions,the single link sessions should get a rate of n/(n +1) units/sec,while the n-link session should get a rate of 1/(n+1)units/sec. Generally,a compromise is required between equal access to a network resource and throttling those sessions that are most responsible for using up that resource.Achiev- ing the proper balance,however,is a design decision that may be hard to quantify:often such decisions must be reached by trial and error. n-link user 1 unit/sec n links each with capacity 1 unit/sec Single link user Single link user Single link user Single link user 1 unit/sec 1 unit/sec 1 unit/sec 1 unit/sec Figure 6.4 Example showing that maximizing total throughput may be incompatible with giving equal throughput to all sessions.A maximum throughput of n units/sec can be achieved if the n-link session is shut off completely.Giving equal rates of 1/2 unit/sec to all sessions achieves a throughput of only (n+1)/2 units/sec.Sec. 6.2 Window Flow Control 499 Bu ffer space for packets that have travelled k + , links (~":~-~ f-C_I_as_.s_.N_._-_'--t '\ -- Class k + , Class k L-~-----I-ff-------i [ \ Class' ) \ Class' J ~Clas----ls a ~Clas----ls a L~~L~~-t/7-----""",,,~~ / ----- Buffer space for packets that have travelled k links Figure 6.3 Organization of node memory in buffer classes to avoid dcadlock due to buffer overflow. A packet that has traveled k links is accepted at a node only if thcre is an available buffer of class k or lower. wherc k ranges from 0 to IV - I (where IV is the numbcr of nodes). Assuming that packets that travel more than IV - I links are discarded as having traveled in a loop. no deadlock occurs. Thc proof consists of showing by induction (starting with k = IV - I) that at each node the buffers of class k cannot fill up permanently. fairness between classes is complex and involves the requirements of those classes. Even within a class, there are several notions of fairness that one may wish to adopt. The example of Fig. 6.4 illustrates some of the contradictions inherent in choosing a fairness criterion. There are n + 1 sessions each offering I unit/sec of traffic along a sequence of n links with capacity of 1 unit/sec. One session's traffic goes over all n links, while the rest of the traffic goes over only one link. A maximum throughput of n units/sec can be achieved by accepting all the traffic of the single-link sessions while shutting off the n-link session. However, if our objective is to give equal rate to all sessions, the resulting throughput is only (n + 1)12 units/sec. Alternatively, if our objective is to give equal resources to all sessions, the single link sessions should get a rate of nl(n + 1) units/sec, while the fl.-link session should get a rate of I/(n + 1) units/sec. Generally, a compromise is required between equal access to a network resource and throttling those sessions that are most responsible for using up that resource. Achiev￾ing the proper balance, however, is a design decision that may be hard to quantify; often such decisions must be reached by trial and error. n-link user , unit/sec \ n links each with capacity' unit/sec p: (~I • 1C: Single link user ~ingle link user Single link user , unit/sec , unit/sec , unit/sec Figure 6.4 Example showing that maximizing total throughput may be incompatible with giving equal throughput to all sessions. A maximum throughput of n units/sec can be achieved if the It-link scssion is shut off completely. Giving equal rates of 1/2 unit/sec to all sessions achieves a throughput of only (It T 1)/2 units/scc-