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

Walkowiak, Krzysztof

International Journal of Applied Mathematics and Computer Science, Tome 12 (2002), p. 257-267 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2002-01-01

Zbl 1038.90503

EUDML-ID : urn:eudml:doc:207585

Bibliographie

[000] Anderson J., Doshi B., Dravida S. and Harshavardhana P. (1994): Fast restoration of ATM networks. - IEEE JSAC, Vol. 12, No. 1, pp. 128-138.

[001] Ayanoglu E. and Gitlin R. (1996): Broadband network restoration. - IEEE Comm. Mag., Vol. 34, No. 7, pp. 110-119.

[002] 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.

[003] 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.

[004] Ford L. and Fulkerson D. (1969): Flows in Networks. - Warsaw: Polish Scientific Publishers (in Polish). | Zbl 0139.13701

[005] 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. | Zbl 1131.90321

[006] 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.

[007] 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. | Zbl 0924.68003

[008] Goldberg D. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. - Reading: Addison-Wesley. | Zbl 0721.68056

[009] 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.

[010] 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.

[011] 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.

[012] 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.

[013] Kajiyama Y., Tokura N. and Kikuchi K. (1994): An ATM VP-based self-healing ring. - IEEE JSAC, Vol. 12, No. 1, pp. 171-178.

[014] Kasprzak A. (1985): Optimal capacity and non-bifurcated flow assignment in a computer communication network. - Syst. Sci., Vol. 11, No. 1, pp. 47-58.

[015] 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.

[016] 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.

[017] 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.

[018] Kawamura R. and Tokizawa I. (1995): Self-healing virtual path architecture in ATM networks. - IEEE Comm. Mag., Vol. 33, No. 9, pp. 72-79.

[019] 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.

[020] Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEE/ACM Trans. Networking, Vol. 4, No. 2, pp. 22-39.

[021] 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.

[022] 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.

[023] Sysło M., Deo N. and Kowalik J. (1993): Discrete Optimization Algorithms. -Warsaw: Polish Scientific Publishers (in Polish). | Zbl 0574.90057

[024] 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.

[025] Veitch P. and Hawker I. (1996): Administration of restorable virtual path mesh networks. - IEEE Comm. Mag., Vol. 34, No. 12, pp. 96-101.

[026] Veitch P. and Johnson D. (1997): ATM network resilience. - IEEE Network, Vol. 11, No. 5, pp. 26-33.

[027] 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).

[028] 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.

[029] 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.