Sec.5.1 Introduction 367 5 units 5 units Origin Origin All links have a capacity of 10 units Figure 5.5 Network for Example 5.1.All links have a capacity of 10 units.If all traffic is routed through the middle link (4.6),congestion occurs.If.instead.paths Destination (1-3→6)and(2一5一6)are used. the average delay is small. equal 10.Thus,the total throughput can be no more than 15 units.On the other hand. suppose that the traffic originating at node 2 is evenly split between the two paths 2-4-6 and 2-5-6,while the traffic originating at node I is routed along I-3-6.Then. the traffic arrival rate on each link will not exceed 75%of capacity.the delay per packet will be reasonably small,and (given a good flow control scheme)no portion of the offered load will be rejected.Arguing similarly,it is seen that when the offered loads at nodes I and 2 are both large,the maximum total throughput that this network can accommodate is between 10 and 30 units,depending on the routing scheme.This example also illustrates that to achieve high throughput,the traffic of some origin-destination pairs may have to be divided among more than one route. In conclusion,the effect of good routing is to increase throughput for the same value of average delay per packet under high offered load conditions and to decrease average delay per packet under low and moderate offered load conditions.Furthermore,it is evident that the routing algorithm should be operated so as to keep average delay per packet as low as possible for any given level of offered load.While this is easier said than done,it provides a clear-cut objective that can be expressed mathematically and dealt with analytically. 5.1.2 Wide Area Network Routing:An Overview The purpose of this section is to survey current routing practice in wide area networks. to introduce classifications of different schemes,and to provide a context for the analysis presented later. There are a number of ways to classify routing algorithms.One way is to divide them into centralized and distribured.In centralized algorithms,all route choices are made at a central node,while in distributed algorithms,the computation of routes is3 Sec. 5.1 5 units Introduction 5 units 5 All links have a capacity of 10 units 367 Figure 5.5 Network for Example 5.1. All links have a capacity of 10 units. If all traffic is routed through the middle link (4,6), congestion occurs. If, instead, paths (I --> 3 --> 6) and (2 --> 5 --> 6) are used, the average delay is small. equal 10. Thus, the total throughput can be no more than 15 units. On the other hand, suppose that the traffic originating at node 2 is evenly split between the two paths 2 4 6 and 2 --> 5 --> 6, while the traffic originating at node I is routed along 1 --> 3 --> 6. Then, the traffic arrival rate on each link will not exceed 75% of capacity, the delay per packet will be reasonably small, and (given a good flow control scheme) no portion of the offered load will be rejected. Arguing similarly, it is seen that when the offered loads at nodes I and 2 are both large, the maximum total throughput that this network can accommodate is between 10 and 30 units, depending on the routing scheme. This example also illustrates that to achieve high throughput, the traffic of some origin-destination pairs may have to be divided among more than one route. In conclusion, the effect ofgood routing is to increase throughput/or the same \'alue of average delay per packet under high offered load conditions and to decrease average delay per packet under low and moderate offered load conditions. Furthermore, it is evident that the routing algorithm should be operated so as to keep average delay per packet as low as possible for any given level of offered load. While this is easier said than done, it provides a clear-cut objective that can be expressed mathematically and dealt with analytically. 5.1.2 Wide Area Network Routing: An Overview The purpose of this section is to survey current routing practice in wide area networks, to introduce classifications of different schemes, and to provide a context for the analysis presented later. There are a number of ways to classify routing algorithms. One way is to divide them into centralized and distributed. In centralized algorithms, all route choices are made at a central node, while in distributed algorithms, the computation of routes is