Abstract

The paper deals with routing and link allocation in ATM networks, 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 appropriate bandwidth to the 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 and 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. We find that the choice of routing and link allocation algorithms have 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 the 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 requirement 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 the 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, i.e. 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.

Biography of first author

Gabor Fodor received his Msc. degree in electrical engineering from the Technical University of Budapest (TUB) in 1988. He worked five years at ABB Atom in Sweden at the company's Department of Automation and Control Systems. Since 1993 he is pursuing the Ph.D. degree at TUB. His interests include computer simulation of telecommunication networks, and specifically performance analysis of ATM networks.

Gabor Fodor                                Ph.D. Student
Technical University Of Budapest           :fodor@bme-tel.ttt.bme.
Dept. Of Telecommunications and Telematics tel(office): +36 1 4633884 
Sztoczek utca 2. H-1111 Budapest, HUNGARY  fax(office): +36 1 4633107