Tabu Search Algorithm for Survivable Network Design Problem with Simultaneous Unicast and Anycast Flows

• Autorzy: Gładysz J. , Walkowiak K.
• Języki publikacji: EN

Abstrakty

EN

In this work we focus on the problem of survivable network design for simultaneous unicast and anycast flows. This problem follows from the growing popularity of network services applying the anycast paradigm. The anycasting is defined as one-to-one-of-many transmission and is applied in Domain Name Service (DNS), peer-to-peer (P2P) systems, Content Delivery Networks (CDN). In this work we formulate two models that enables joint optimization of network capacity, working and backup connections for both unicast and anycast flows. The goal is to minimize the network cost required to protect the network against failures using the single backup path approach. In the first model we consider modular link cost, in the second we are given a set of link proposal and we must select only one of them. Because these problems are NP-hard, therefore optimal solutions of branch-and-bounds or branch-and-cut methods can be generated for relatively small networks. Consequently, we propose a new heuristic algorithm based on Tabu Search method. We present results showing the effectiveness the proposed heuristic compared against optimal results. Moreover, we report results showing that the use of anycast paradigm can reduce the network cost.

Słowa kluczowe

EN

anycast; network design; tabu search; survivability

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2010
• Tom: Vol. 56, No. 1
• Strony: 41--47
• Opis fizyczny: Bibliogr. 20 poz., wykr.

Twórcy

autor

Gładysz J.

autor

Walkowiak K.

• Wrocław University of Technology and Regional Specialist Hospital in Wrocław, Research and Development Center,

Bibliografia

• [1] Awerbuch B., Brinkmann A., Scheideler C.: Anycasting in adversarial systems: routing and admission control, Lecture Notes in Computer Science, Vol. 2719, 2003, Springer-Verlag, Berlin, pp. 1153-1168.
• [2] Ballani H., Francis P.: Towards a Global IP Anycast Service, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, 2005 pp. 301-312.
• [3] Din D.: Anycast Routing and Wavelength Assignment Problem on WDM Network: IEICE Transactions on Communications, Vol. E88-B, No. 4, 2005, pp. 3941-3951.
• [4] Doi S., Ata S., Kitamura K., Murata M.: IPv6 anycast for simple and effective service-oriented communications, IEEE Communication Magazine, Vol. 42, No. 5, 2004, pp.163-171.
• [5] Gladysz J., Walkowiak K.: Modeling of Survivable Network Design Problems with Simultaneous Unicast and Anycast Flows, Proceedings of 2nd International Symposium on Logistics and Industrial Informatics, 2009, pp. 75-80.
• [6] Gladysz J., Walkowiak K.: Optimization of Survivable Networks with Simultaneous Unicast and Anycast Flows, Proceedings of the International Workshop on Reliable Networks Design and Modeling RNDM, 2009
• [7] Gladysz J., Walkowiak K.: Capacity and Flow Optimization for Survivable Networks with Concurrent Unicast and Anycast Flows, Proceedings of the 4th International Conference on Broadband Communication, Information Technology & Biomedical Applications BroadBandCom, 2009.
• [8] Glover F., Laguna M.: Tabu Search, Kluwer Academic Publishers, Norwell, MA. 1997.
• [9] Grover W.: Mesh-based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking, Prentice Hall PTR, Upper Saddle River, New Jersey, 2004.
• [10] Hofmann M., Beaumont L.: Content networking :architecture, protocols, and practice, Morgan Kaufmann, San Francisco, 2005.
• [11] Kasprzak A.: Algorithms of flow, capacity and topology structure in computer networks, Monography, Wroclaw, 1989, in Polish.
• [12] Orlowski S., Pióro M., Tomaszewski A., Wessaly R.: Survivable Network Design Library, Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium SNDlib 1.0 - April 2007, http://sndlib.zib.de
• [13] Peng G.: CDN: Content Distribution Network, Technical Report, http://sunysb.edu/tr/rpe13.ps.gz 2003.
• [14] Perros H.: Connection-oriented Networks, SONET/SDH, ATM, MPLS and Optical Networks, John Wiley & Sons, Ltd, Chichester, England, 2005.
• [15] Pioro M., Medhi D.: Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann Publishers, 2004.
• [16] Sharma V., Hellstrand F.: Framework for MPLS-based recovery, RFC 3469, 2003.
• [17] Steinmetz R., Wehrle K. (eds.): Peer-to-Peer Systems and Applications, Lecture Notes in Computer Science, vol. 3485, Springer Verlag, 2005.
• [18] Vasseur J., Pickavet M., Demeester P.: Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP and MPLS, Morgan Kaufmann, San Francisco, 2004.
• [19] Walkowiak K.: Anycast Communication - A New Approach to Survivability of Connection-Oriented Networks, Communications in Computer and Information Science, Springer Verlag, Berlin, pp. 378–389.
• [20] Wu J. (ed.): Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Auerbach Publications 2006.