Recovery using precalculated paths based routing in ATM networks

• Autorzy: Orincsay D. , Jósa B.G. , Kosa D. , Tamasi L.

Warianty tytułu

PL

Podnoszenie z upadków w sieciach ATM przy wykorzystaniu obliczonych wcześniej ścieżek

• Języki publikacji: EN

Abstrakty

EN

The ATM technology serves as basis for many communication networks. The generally applied PNNI protocol enables to use sophisticated traffic engineering techniques. A progressive approach is such a routing strategy that applies precalculated paths in order minimize the reaction time for a new call request. As an advanced technique, more precalculated paths can be stored for each destination in every swith, which increase the possibility of the successful cal setup. Generally , the well-known K shortest path algorithm is used for this purpose that calculates the K cheapest paths based on an appropriate cost function. Although this method performs well in normal operation, it does not ensure that there is a bypass path among the stored ones when a network element fails along the currently used path. In this study we proposed a new path calculation concept based on algorithm of Edmonds and Karp, aiming at reducing the restoration time in case of failure. We investigate the performance of the novel method through simulations.

PL

Technologia ATM służy jako podstawa wielu sieci komunikacyjnych. Stosowany w niej najczęściej protokół PNNI pozwala na wykorzystanie złożonych technik inżynierii ruchu. Coraz częściej stosuje się strategię wyboru drogi wykorzystującą wcześniejsze wyliczanie ścieżek, w celu zmniejszenia czasu odpowiedzi na żądanie nawiązania nowego połączenia. Rozwój techniki pozwala na zapamiętywanie w każdym węźle coraz większej liczby takich obliczonych uprzednio ścieżek, co zwiększa prawdopodobieństwo ich wykorzystania. Do ich obliczenia stosuje się dobrze znany algorytm K najkrótszych ścieżek, wykorzystujący założoną funkcję kosztów. Opisane podejście działa dobrze przy normalnej pracy sieci, nie pozwala jednak znaleźć nowych, uzupełniających ścieżek dla przełączenia ruchu, gdy zawodzi jeden z elementów aktualnie wykorzystywanej ścieżki. Niniejszy artykuł proponuje nową metodę obliczania ścieżek, opartą na algorytmie Edmondsa i Karpa, pozwalającą na zmniejszenie czasu nawiązywania nowego połączenia po upadku pracującej ścieżki. Przydatność metody jest badana za pomocą modeli symulacyjnych.

Słowa kluczowe

EN

ATM network; asynchronous transfer mode; Edmonds and Karp algorithm; PNNI protocol; k shortes path algorithms

PL

ATM; asynchronous transfer mode; algorytm Edmondsa i Karpa; protokół PNNI; algorytm k najkrótszych ścieżek

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2003
• Tom: Vol. 24, nr 2A
• Strony: 119--128
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Orincsay D.

• Ericsson Research Hungary, Traffic Analysis and Network Performance Laboratory, H-1300 Budapest, Hungary P.O. Box 107

autor

Jósa B.G.

• Ericsson Research Hungary, Traffic Analysis and Network Performance Laboratory, H-1300 Budapest, Hungary P.O. Box 107

autor

Kosa D.

• Ericsson Research Hungary, Traffic Analysis and Network Performance Laboratory, H-1300 Budapest, Hungary P.O. Box 107

autor

Tamasi L.

• Ericsson Research Hungary, Traffic Analysis and Network Performance Laboratory, H-1300 Budapest, Hungary P.O. Box 107

Bibliografia

• 1. ATM Forum Technical Committee: Private Network-Network Interface Specification Version 1.0. ATM Forum af-pnni-OO55.OOO, March 1996.
• 2. Józsa B. G., Orincsay D., Magi A., Szviatovszki B.: On the Use of Trunk Reservation in PNNI Routing. ICATM2000, Heidelberg, Germany, June 2000, pp. 135-139.
• 3. Magi A., Szentesi A., Szviatovszki B.: Analysis of Link Cost Functions for PNNI Routing, the 6th IFD? Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley 1998.
• 4. Topkis D. M.: A к Shortest Path Algorithm for Adaptive Routing in Communication Networks. IEEE Transactions on Communications, vol. 36, no. 7, July 1998.
• 5. Yen J. Y.: Finding the К Shortest Loopless Paths in a Network. Management Science 17, 1971, pp. 712-716.
• 6. lannaccone G., Chuah C.-N„ Mortier R., Bhattacharyya S., Diot C.: Analysis of link failures over an IP backbone. ACM SIGCOMM Internet Measurement Workshop. Marseilles, France, November 2002.
• 7. Nucci A., Schroeder B., Bhattacharyya S., Taft N.. Diot C.: IS-IS Link Weight Assignment for Transient Link Failures. Sprint ATL Technical Report Nr. TR02-ATL-071000, Sprint Labs., July 2002.
• 8. International Telecommunication Union - Telecommunication Standardization Sector: Call routing & connection routing methods, ITU-T E.360.2, May 2002.
• 9. Edmonds J., Karp R. M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of ACM 19,1972, pp. 248-264.
• 10. Ahuja R. K., Magnanti T. L., Orlin J. B.: Network Flows - Theory, Algorithms, and Applications. Prentice-Hall, New Jersey 1993.