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

Krzysztof Walkowiak

International Journal of Applied Mathematics and Computer Science (2002)

  • Volume: 12, Issue: 2, page 257-267
  • ISSN: 1641-876X

Abstract

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

How to cite

top

Walkowiak, Krzysztof. "The branch and bound algorithm for a backup virtual path assignment in survivable ATM networks." International Journal of Applied Mathematics and Computer Science 12.2 (2002): 257-267. <http://eudml.org/doc/207585>.

@article{Walkowiak2002,
abstract = {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.},
author = {Walkowiak, Krzysztof},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {survivable networks; branch and bound algorithm; ATM},
language = {eng},
number = {2},
pages = {257-267},
title = {The branch and bound algorithm for a backup virtual path assignment in survivable ATM networks},
url = {http://eudml.org/doc/207585},
volume = {12},
year = {2002},
}

TY - JOUR
AU - Walkowiak, Krzysztof
TI - The branch and bound algorithm for a backup virtual path assignment in survivable ATM networks
JO - International Journal of Applied Mathematics and Computer Science
PY - 2002
VL - 12
IS - 2
SP - 257
EP - 267
AB - 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.
LA - eng
KW - survivable networks; branch and bound algorithm; ATM
UR - http://eudml.org/doc/207585
ER -

References

top
  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). Zbl0139.13701
  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. Zbl1131.90321
  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. Zbl0924.68003
  9. Goldberg D. (1989): Genetic Algorithms in Search, Optimization, and Machine Learning. - Reading: Addison-Wesley. Zbl0721.68056
  10. 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. 
  11. 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. 
  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 VP-based 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 broad band 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). Zbl0574.90057
  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 200 (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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.