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

• Autorzy: Walkowiak K.
• 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; ATM; branch and bound algorithm

PL

sieć komputerowa; ATM; algorytm podziału

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2002
• Tom: Vol. 12, no 2
• Strony: 257--267
• Opis fizyczny: Bibliogr. 30 poz., rys., wykr.

Twórcy

autor

Walkowiak K.

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