The branch and bound algorithm for a backup virtual path assignment in survivable ATM networks

• Autorzy: Krzysztof Walkowiak
• Języki publikacji: EN

Abstrakty

EN

Issues of network survivability are important, since users of computer networks should be provided with some guarantees of data delivery. A large amount of data may be lost in high-speed Asynchronous Transfer Mode (ATM) due to a network failure and cause significant economic loses. This paper addresses problems of network survivability. The characteristics of virtual paths and their influence on network restoration are examined. A new problem of Backup Virtual Path Routing is presented for the local-destination rerouting strategy. The function of the flow lost due to a failure of a single link is chosen as the performance index. The problem of finding the optimal virtual path assignment is NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover, two heuristic algorithms are proposed. Numerical results are presented.

Słowa kluczowe

EN

survivable networks; branch and bound algorithm; ATM

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2002
• Tom: 12
• Numer: 2
• Strony: 257-267

Daty

wydano

2002

otrzymano

2001-01-19

poprawiono

2002-01-14

(nieznana)

2002-03-10

Twórcy

autor

Krzysztof Walkowiak

• Division of Systems and Computer Networks, Faculty of Electronics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• Anderson J., Doshi B., Dravida S. and Harshavardhana P. (1994): Fast restoration of ATM networks. - IEEE JSAC, Vol. 12, No. 1, pp. 128-138.
• Ayanoglu E. and Gitlin R. (1996): Broadband network restoration. - IEEE Comm. Mag., Vol. 34, No. 7, pp. 110-119.
• 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.
• Chlamatac I., Fargo A. and Zhang T. (1994): Optimizing the system of virtual paths. - IEEE ACM Trans. Networking, Vol. 2, No. 12, pp. 581-587.
• Ford L. and Fulkerson D. (1969): Flows in Networks. - Warsaw: Polish Scientific Publishers (in Polish).
• 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.
• 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.
• Gerstel O., Cidon I. and Zaks S. (1996): The layout of virtual paths in ATM networks. - IEEE/ACM Trans. Networking, Vol. 4, No. 12, pp. 873-884.
• Goldberg D. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. - Reading: Addison-Wesley.
• Guerin R., Ahmadi H. and Nagshineh M. (1991): Equivalent capacity and its application to band width allocation in high-speed networks. - IEEE JSAC, Vol. 9, No. 9, pp. 968-981.
• Herzberg M., Bye S. and Utano A. (1995): The hop-limit approach for spare-capacity assignment in survivable networks. - IEEEACM Trans. Networking, Vol. 3, No. 12, pp. 775-784.
• 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.
• Iraschko R., MacGregor M. and Grover W. (1998): Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks. - IEEE/ACM Trans. Networking, Vol. 6, No. 6, pp. 325-335.
• Kajiyama Y., Tokura N. and Kikuchi K. (1994): An ATM VP-based self-healing ring. - IEEE JSAC, Vol. 12, No. 1, pp. 171-178.
• Kasprzak A. (1985): Optimal capacity and non-bifurcated flow assignment in a computer communication network. - Syst. Sci., Vol. 11, No. 1, pp. 47-58.
• Kasprzak A. (1989): Optimization Algorithms of Flows, Channel Capacity and Topology in Computer Communication Networks. - Wrocław: Publishing House of the Wrocław Univ. Techn.
• Kasprzak A. and Walkowiak K. (2000): Designing of virtual private networks in the public ATM network environment. - Proc. Conf. 34th Modelling and Simulation of Systems, MOSIS, Ostrava, Czech Republic, pp. 111-116.
• 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.
• Kawamura R. and Tokizawa I. (1995): Self-healing virtual path architecture in ATM networks. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 72-79.
• 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.
• Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEE/ACM Trans. Networking, Vol. 4, No. 2, pp. 22-39.
• Nederlof L., Struyve K., O'Shea C., Misser H. and Tamayo B. (1995): End-to-end survivable broad band networks. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 63-70.
• Sato K., Ohta S. and Tokizawa I. (1990): Broad-band ATM network architecture based on virtual paths. - IEEE Trans. Comm., Vol. 38, No. 1, pp. 1212-1222.
• Sysło M., Deo N. and Kowalik J. (1993): Discrete Optimization Algorithms. -Warsaw: Polish Scientific Publishers (in Polish).
• Van Landegem T., Vankwikelberge P. and Vanderstraeten H. (1994): A self-healing ATM network based on multilink principles. - IEEE JSAC, Vol. 12, No. 1, pp. 139-148.
• Veitch P. and Hawker I. (1996): Administration of restorable virtual path mesh networks. - IEEE Comm. Mag., Vol. 34, No. 12, pp. 96-101.
• Veitch P. and Johnson D. (1997): ATM network resilience. - IEEE Network, Vol. 11, No. 5, pp. 26-33.
• 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 Wrocław Univ. Technol., Series: Preprints 200 (in Polish).
• 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.
• Wang W., Tipper D., Jager B. and Mehdi D. (1997): Fault recover routing in wide area networks. - Proc. 15th Int. Teletraffic Congress, Washington, USA, pp. 1077-1086.