SIMULATIVE ANALYSIS OF ROUTING AND LINK ALLOCATION STRATEGIES IN ATM NETWORKS

Abstract

For Broadband Integrated Services Digital (B-ISDN) networks ATM is a promising technology, because it supports a wide range of services with different bandwidth demands, traffic characteristics and QoS requirements. This diversity of services makes traffic control in these networks much more complicated than in existing circuit or packet switched networks. Traffic control procedures include both actions necessary for setting up virtual connections (VC), such as bandwidth assignment, call admission, routing and resource allocation and congestion control measures necessary to maintain throughput in overload situations. This paper deals with routing and link allocation, and analyses the performance of such algorithms in terms of call blocking probability, link capacity utilization and QoS parameters. In our model the network carries out the following steps when a call is offered to the network: (1) Assign an appropriate bandwidth to an offered call (Bandwidth assignment) (2) Find a transmission path between the source and destination with enough available transmission capacity (Routing) (3) Allocate resource along that path (Link allocation) We consider an example 5-node network [7], conduct an extensive survey of routing, and link allocation algorithms. Regarding step (1) we employ the equivalent link capacity assignment presented by various interesting papers [1]-[5]. We find that the choice of routing and link allocation algorithms has a great impact on network performance, and that different routing algorithms perform best under different network load values. Shortest path routing (SPR) is a good candidate for low, alternate routing (AR) for medium and non-alternate routing (NAR) for high traffic load values. Concerning link allocation strategies, we find that partial overlap (POL) strategies that seem to be able to present near optimal performance are superior to complete sharing (CS) and complete partitioning (CP) strategies. As a further improvement of the POL scheme, we propose a 2-level link allocation algorithm, which yields highest link utilization. In this scheme, not only the accesses of different service classes to different virtual paths (VPs) are controlled, but also an individual VP's transmission capacity is optimally allocated to the service classes according to their bandwidth requirements in order to assure high link utilization. This method seems to be adjustable to the fine degree of granularity of bandwidth demands in B-ISDN networks. It is shown that in order to minimize cell loss the call level resource allocation plays a significant role: networks with the same buffer size switches display different cell loss probabilities in the nodes and impose different end-to-end delay on cells if the link allocation and routing differ. Again, we find that when traffic is tolerable by the network, SPR causes the least cell loss. This can be explained by the fact that SPR spreads the incoming calls in the network. It eagerly seeks new routes instead of utilizing the already used but still not congested routes. SPR obviously wastes more rapidly link and buffer capacity as traffic load becomes higher than the AR, which chooses a new route only when it has to, i.e. when the route of higher priority becomes congested. That is why we experience that as soon as the SPR starts loosing cells, it indicates that available resources have been consumed and it rapidly goes up to very high blocking probabilities after a small further increase of load.