Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 12 | 2 | 257-267

Tytuł artykułu

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

Treść / Zawartość

Warianty tytułu

Języki publikacji



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








Opis fizyczny




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


  • 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.

Typ dokumentu



Identyfikator YADDA

JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.