The Branch and Bound Algorithm for joint optimization of primary and Backup routes in Survivable Networks

• Autorzy: Walkowiak K.

Warianty tytułu

PL

Algorytm podziału i oszacowań dla wyznaczania tras podstawowych i zaposowych w przeżywalnych sieciach komputerowych

• Języki publikacji: EN

Abstrakty

EN

Survivability of computer networks is an important subject. Organizational and individual users of computer network expect reliable services with guarantees of data delivery. In high-speed network technologies like Asynchronous Transfer Mode (ATM) and Multiprotocol Label Switching (MPLS) a large amount of data can be lost due to a network failure and cause significant economics loses. In this work we focus on problems of network survivability. Several network restoration methods are presented and discussed. A new optimization problem of Joint Primary and Backup Routes Assignment is formulated. As the rerouting strategy the local-destination rerouting is applied. The function of lost flow due to a failure of any single link is used as an objective function. The problem of finding the optimal assignment of connections in NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover two heuristic algorithms are proposed. Numerical results are included.

PL

Przeżywalność sieci komputerowych jest ważnym zagadnieniem. Użytkownicy indywidualni i instytucjonalni oczekują niezawodnych usług gwarantujących dostarczenie przesyłanych danych. W szybkich sieciach komputerowych takich jak ATM ( Asynchronous Transfer Mode) oraz MPLS (Multiprotocol Label Switching) wiele ważnych i cennych informacji może być utraconych wskutek awarii. W tej pracy koncentrujemy się na zagadnieniach przeżywalności sieci komputerowych. Przedstawiono i porównano kilka metod zapewniania przeżywalności w sieciach. Nowy problem optymalizacyjny równoczesnego wyznaczania tras podstawowych i zapasowych został sformułowany. Jako metodę restoracji sieci po awarii wybrano restorację lokalno-globalną. Funkcja utraconego przepływu po awarii pojedynczego łącza została użyta jako funkcja kryterialna. Rozważany problem jest NP.-zupełny. Dlatego zaproponowano algorytm dokładny oparty na metodzie podziału i oszacowań. Dodatkowo przedstawiono dwa algorytmy przybliżone. Dołączono wyniki eksperymentów obliczeniowych.

Słowa kluczowe

EN

survivable networks; connection-oriented networks; branch and bound algorithm

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2003
• Tom: T. 15, z. 4
• Strony: 273--296
• Opis fizyczny: Bibliogr. poz. 36, rys., wykr.

Twórcy

autor

Walkowiak K.

• Chair of Systems and Computer Networks, faculty of Electronics, Wroclaw University of Technology, Wybrzeze Wyspianskiego 27, 50-370 Wroclaw, Poland,

Bibliografia

• [1] Anderson J., Doshi B., Dravida S. and Harshavardhana P. (1994): Fast Restoration of ATM Networks. - IEEE JSAC, Vol. 12, No. 1, pp. 128-138.
• [2] Ayanoglu E. and Gitlin R. (1996): Broadband Network Restoration. - IEEE Comm. Mag., Vol. 34, No. 7, pp. 110-119.
• [3] Burgina J. and Dorman D. (1991): Broadband ISDN Resource Management: The Role of Virtual Paths. - IEEE Comm. Mag., Vol. 29, No. 9, pp. 44-48.
• [4] Chen T. and Oh T. (1999): Reliable Services in MPLS - IEEE Communications Magazine, December 1999, pp. 58-62.
• [5] Chlamatac I., Fargo A., and Zhang T. (1994): Optimizing the System of Virtual Paths. - IEEE/ACM Trans, on Networking, Vol. 2, No. 12, pp. 581-587.
• [6] Ford L. and Fulkerson D. (1969): Flows in Networks - PWN: Warszawa. 1969 (in Polish).
• [7] Fratta L., Gerla M. and Kleinrock L. (1973): The Flow Deviation Method: An Approach to Store- and-Forward Communication Network Design - Networks, Vol. 3, No. 2, pp. 97-133.
• [8] Friesen V., Harms J. and Wong J. (1996): Resource Management with Virtual Paths in ATM Networks. - IEEE Network. Vol. 10. No. 5, pp. 10-20.
• [9] Gerstel O., Cidon I., and Zaks S. (1996): The Layout of Virtual Paths in ATM Networks. - IEEE/ACM Transactions on Networking, Vol. 4, No. 12, pp. 873-884.
• [10] Goldberg D. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. - Reading MA: Addison-Wesley, 1989.
• [11] Guerin R.. Ahmadi H. and Nagshineh M. (1991): Equivalent Capacity and Us Application to Band¬width Allocation in High-Speed Networks - IEEE JSAC, Vol. 9, No. 9, pp. 968-981.
• [12] Herzberg M., Bye S. and Utano A. (1995): The Hop-Limit Approach for Spare-Capacity Assignment in Survivabie Networks - IEEE/ACM Trans, on Networking, Vol. 3, No. 12, pp. 775-784.
• [13] Hui J., Gursoy M., Moayeri N. and Yates R. (1991): A Layered Broadband Switching Architecture with Physical and Virtual Path Configurations - IEEE JSAC, Vol. 9, No. 12, pp. 1416-1426.
• [14] Iraschko R.. MacGregor M. and Grover W. (1998): Optimal Capacity Placement for Path Restoration in STM or ATM Mesh-Survivable Networks. - IEEE/ACM Trans, on Networking, Vol. 6, No. 6, pp. 325-335.
• [15] Kajiyama Y., Tokura N. and Kikuchi K. (1994): An ATM VP-Based Self-Healing Ring. - IEEE JSAC, Vol. 12, No. 1, pp. 171-178.
• [16] Kasprzak A. (1985): Optimal Capacity and Non-bifurcated Flow Assignment in a Computer Communication Network. - Syst. Sei., Vol. 11, No. 1, pp. 47-58.
• [17] Kasprzak A. (1989): Optimization algorithms of flows, channel capacity and topology in computer communication networks. - Publishing House of the Wroclaw Univ. Technolog., Wroclaw, 1989.
• [18] Kasprzak A. and Walkowiak K. (2000): Designing of virtual private networks in the public ATM network environment. - Proc. Conf. 34th Modelling and simulation of system, MOSIS, Ostrava, pp. 111-116.
• [19] Kawamura R., Sato K. and Tokizawa I. (1994): Self-healing ATM Networks Based on Virtual Path Concept. - IEEE JSAC, Vol. 12, No. 1, pp. 120-127.
• [20] Kawamura R. and Tokizawa 1. (1995): Self-healing Virtual Path Architecture in ATM Networks. - IEEE Comm. Mag., Vol. 33, No. 9. pp. 72-79.
• [21] Li T. (1999): MPLS and the Evolving Internet Architecture. - IEEE Comm. Mag., Vol. 37, No. 12, pp. 38-41.
• [22] May K.. Semal P., Du Y. and Hermann C. (1995): A Fast Restoration System for ATM-Ring-Based LANs. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 90-98.
• [23] Murakami K. and Kim H. (1996): Virtual Path Routing for Survivabie ATM Networks. - IEEE/ACM Trans, on Networking, Vol. 4. No. 2, pp.22-39.
• [24] Nederlof L., Struyve K., O’Shea C., Misser H. and Tamayo B. (1995): End-to-End Survivabie Broadband Networks. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 63-70.
• [25] Rosen E., Viswanathan A. and Callon R. (2001). Multiprotocol Label Switching Architecture - RFC 3031, January 2001.
• [26] Sato K.. Ohta S. and Tokizawa I. (1990): Broad-band ATM Network Architecture Based on Virtual Paths. - IEEE Trans, on Comm.. Vol. 38, No. l.pp. 1212-1222.
• [27] Sharma V. and Hellstrand F. (editors) (2002): Framework for MPLS-based Recovery - Work in Progress, October 2002
• [28] Syslo M.. Deo N. and Kowalik J. (1993): Discrete Optimization Algorithms. - PWN: Warszawa 1993 (in Polish).
• [29] Van Landegem T., Vankwikelberge P. and Vanderstraeten H. (1994): A Self-Healing ATM Network Based on Multilink Principles. - IEEE JSAC, Vol. 12. No. l.pp. 139-148.
• [30] Veitch P. and Hawker I. (1996): Administration of Restorable Virtual Path Mesh Networks. - IEEE Comm. Mag., Vol. 34, No. 12, pp. 96-101.
• [31] Veitch P. and Johnson D. (1997): ATM Network Resilience. - IEEE Network, Vol. 11, No. 5, pp. 26-33.
• [32] Walkowiak K. (2000a): Algorithms for assignment of virtual paths in survivable ATM networks. - Ph.D. Thesis, Sci. Papers Division of Systems and Computer Networks of Wroclaw Univ. Technolog., Series: Report Preprinty 2/00 (in Polish).
• [33] Walkowiak K. (2000b): An exact algorithm for designing backup virtual paths in survivable ATM networks. - Proc. Conf. 22nd International Scientific School, ISAT. Szklarska Poręba, pp. 263-271.
• [34] Walkowiak K. (2001), Assignment of virtual paths in survivable ATM networks for local-destination rerouting - Third International Workshop on Design of Reliable Communication Networks DRCN 2001, Proceedings, [Budapest. Hungary. October 7-10 2001], pp. 273-280.
• [35] Walkowiak K. (2002): The Branch and Bound Algorithm for Backup Virtual Path Assignment in Survivable ATM Networks - International Journal of Applied Mathematics and Computer Science, Nr. 2, Vol. 12. 2002. pp. 257-268.
• [36] Wang W., Tipper D.. Jager B., Mehdi D. (1997): Fault Recover Routing in Wide Area Networks. Proceedings of 15th International Teletraffic Congress, Washington DC, June 1997, pp. 1077-1086.