PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
257--267
Opis fizyczny
Bibliogr. 30 poz., rys., wykr.
Twórcy
autor
  • 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
  • [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] 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.
  • [5] Ford L. and Fulkerson D. (1969): Flows in Networks. - Warsaw: Polish Scientific Publishers (in Polish).
  • [6] 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.
  • [7] 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.
  • [8] 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.
  • [9] Goldberg D. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. - Reading: Addison-Wesley.
  • [10] Guerin R., Ahmadi H. and Nagshineh M. (1991): Equivalent capacity and its application to bandwidth allocation in high-speed networks. - IEEE JSAC, Vol. 9, No. 9, pp. 968-981.
  • [11] Herzberg M., Bye S. and Utano A. (1995): The hop-limit approach for spare-capacity assignment in survivable networks. - IEEE/ACM Trans. Networking, Vol. 3, No. 12, pp. 775-784.
  • [12] 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.
  • [13] 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.
  • [14] Kajiyama Y., Tokura N. and Kikuchi K. (1994): An ATM VPbased self-healing ring. - IEEE JSAC, Vol. 12, No. 1, pp. 171-178.
  • [15] Kasprzak A. (1985): Optimal capacity and non-bifurcated flow assignment in a computer communication network. - Syst. Sci., Vol. 11, No. 1, pp. 47-58.
  • [16] 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.
  • [17] 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.
  • [18] 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.
  • [19] Kawamura R. and Tokizawa I. (1995): Self-healing virtual path architecture in ATM networks. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 72-79.
  • [20] 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.
  • [21] Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEE/ACM Trans. Networking, Vol. 4, No. 2, pp. 22-39.
  • [22] Nederlof L., Struyve K., O’Shea C., Misser H. and Tamayo B. (1995): End-to-end survivable broadband networks. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 63-70.
  • [23] 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.
  • [24] Sysło M., Deo N. and Kowalik J. (1993): Discrete Optimization Algorithms. - Warsaw: Polish Scientific Publishers (in Polish).
  • [25] 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.
  • [26] Veitch P. and Hawker I. (1996): Administration of restorable virtual path mesh networks. - IEEE Comm. Mag., Vol. 34, No. 12, pp. 96-101.
  • [27] Veitch P. and Johnson D. (1997): ATM network resilience. - IEEE Network, Vol. 11, No. 5, pp. 26-33.
  • [28] 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 2/00 (in Polish).
  • [29] 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.
  • [30] 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
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPZ1-0001-0024
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ć.