An exact algorithm for design of content delivery networks in MPLS environment

• Autorzy: Walkowiak K.
• Języki publikacji: EN

Abstrakty

EN

Content delivery network (CDN) is an efficient and inexpensive method to improve Internet service quality. In this paper we formulate an optimisation problem of replica location in a CDN using MPLS techniques. A novelty, comparing to previous work on this subject, is modelling the network flow as connection-oriented and introduction of capacity constraint on network links to the problem. Since the considered optimisation problem is NP-complete, we propose and discuss exact algorithm based on the branch-and-cut and branch-and-bound methods. We present results of numerical experiments showing comparison of branch-and-cut and branch-and-bound methods.

Słowa kluczowe

EN

content delivery network; optimization; branch-and-cut algorithm

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2004
• Tom: nr 2
• Strony: 13--22
• Opis fizyczny: Bibliogr. 36 poz., rys.

Twórcy

autor

Walkowiak K.

• Chair of Systems and Computer Networks, Faculty of Electronics, Wrocław University of Technology, Wybrzeże Wyspiańskiego st 27, 50-370 Wrocław,

Bibliografia

• [1] K. I. Aardal and C. P. M. van Hoesel, „Polyhedral techniques in combinatorial optimization II: computations and applications", Stat. Nederl., vol. 53, pp. 129-178, 1999.
• [2] V. Arya, N. Garg, R. Khandekar, A. Meyerson, and V. Pandit, „Local search heuristics for k-median and facility location problems", in Proc. ACM Symp. Theory Comput., Hersonissos, Crete, Greece, 2001, pp. 21-29.
• [3] M. Baentsch, L. Baum, G. Molter, S. Rothkugel, and P. Sturm, „World wide Web caching: the application-level view of the Internet", IEEE Commun. Mag., pp. 170-178, June 1997.
• [4] J. Burns, T. Ott, A. Krzesi«ski, and K. Muller, „Path selection and bandwidth allocation in MPLS networks", Perform. Eval., vol. 52, pp. 133-152, 2003.
• [5] M. Charikar and S. Guha, „Improved combinatorial algorithms for the facility location and k-median problems", in Proc. IEEE Symp. Found. Comput. Sci., New York, USA, 1999, pp. 378-388.
• [6] B. Davison, „The design and evaluation of Web prefetching and caching techniques", Ph.D. thesis, 2002, http://www.cse.lehigh.edu/_brian/pubs/2002/thesis/
• [7] L. Fratta, M. Gerla, and L. Kleinrock, „The flow deviation method: an approach to store-and-forward communication network design", Networks, vol. 3, pp. 97-133, 1973.
• [8] S. Guha, A. Meyerson, and K. Munagala, „Improved approximation algorithms for fault-tolerant facility location", in Proc. ACM-SIAM Symp. Discr. Algor., Washington, USA, 2001, pp. 636-641.
• [9] O. Gunluk, „Branch-and-cut algorithm for capacitated network design problems", Math. Programm., vol. 86, pp. 17-39, 1999.
• [10] K. Jain, M. Mahdin, and A. Saberi, „A new greedy approach for facility location problems", in Proc. ACM Symp. Theory Comput., Montreal, Canada, 2002.
• [11] S. Jamin, Ch. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, „On the placement of Internet instrumentation", in Proc. IEEE INFO-COM 2000, Tel-Aviv, Israel, 2000, pp. 295-304.
• [12] S. Jamin, Ch. Jin, Y. Jin, A. Kurc, D. Raz, and Y. Shavitt, „Constrained mirror placement on the Internet", in Proc. IEEE INFO-COM 2001, Anchorage, Alaska, USA, 2001, pp. 31-40.
• [13] R. Karp, „On the computational complexity of combinatorical problems", Networks, vol. 5, pp. 45-68, 1975.
• [14] A. Kasprzak, Topological Design of Wide Area Networks. Wrocław: Wrocław University of Technology Press, 2001.
• [15] L. Kennington, „A survey of linear cost multicommodity networks flows", Oper. Res., vol. 26, pp. 209-236, 1978.
• [16] B. Krishnamurthy, C. Wills, and Y. Zhang, „On the use and performance of content delivery networks", in Proc. ACM SIGCOMM Internet Measur. Worksh., San Francisco, USA, 2001.
• [17] P. Krishnan, D. Raz, and Y. Shavitt, „The cache location problem", IEEE/ACM Trans. Netw., vol. 8, pp. 568-582, 2000.
• [18] T. Li, „MPLS and the evolving Internet architecture", IEEE Commun. Mag., pp. 38-41, Dec. 1999.
• [19] B. Li, M. Golin, G. Italiano, X. Deng, and K. Sohraby, „On the optimal placement of Web proxies in the Internet", in Proc. IEEE INFOCOM'99, New York, USA, 1999, pp. 1282-1290.
• [20] J. Mitchell and E. Lee, „Branch-and-bound methods for integer programming", in Handbook of Applied Optimization. Oxford: Oxford University Press, 2002.
• [21] J. Mitchell, „Branch-and-cut methods for combinatorial optimization problems", in Handbook of Applied Optimization. Oxford: Oxford University Press, 2002.
• [22] M. Padberg and G. Rinaldi, „Optimization of a 532-city travelling salesman problem by branch-and-cut", Oper. Res. Lett., vol. 6, 1987.
• [23] G. Peng, „CDN: content distribution networks", Tech. Rep., 2003, http://www.sunysb.edu/tr/rpe13.ps.gz
• [24] L. Qiu, V. Padmanabhan, and G. Voelker, „On the placement of Web server replicas", in Proc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, pp. 1587-1596.
• [25] M. Rabinovich, „Issues in Web content replication", Data Eng. Bull., vol. 21, no. 4, 1998.
• [26] E. Rosen, A. Viswanathan, and R. Callon, „Multiprotocol label switching architecture", RFC 3031, Jan. 2001.
• [27] A. Vakali, „An evolutionary scheme for Web replication and caching", in Proc. 4th Int. Web Cach. Worksh., San Diego, USA, 1999.
• [28] K. Walkowiak, „Designing of survivable Web caching", in Proc. 8th Polish Teletra_c Symp., Zakopane, Poland, 2001, pp. 171-181.
• [29] K. Walkowiak, „Modelling of Web server replication system in MPLS networks", in Proc. Inform. Syst. Model. ISM 2002, Roznov pod Radhostem, Czech Republic, 2002, pp. 213-220.
• [30] K. Walkowiak, „A new exact algorithm for Web replica location problem in MPLS networks", in Proc. Polish-Germany Teletraffic Symp. PGTS 2002, Gda«sk, Poland, 2002, pp. 307-314.
• [31] K. Walkowiak, „Some approaches to solve a Web replica location problem in MPLS networks", in Internet Technologies, Applications and Societal Impact, W. Cellary and A. Iyengar, Eds. Boston [etc.]: Kluwer, 2002, pp. 61-72.
• [32] K. Walkowiak, „On application of genetic algorithms to replica location problem", in Proc. Comput. Recogn. Syst. KOSYR 2003, Milków, Poland, 2003, pp. 445-450.
• [33] K. Walkowiak, „A new approach to survivability of connection oriented networks", in Lectures Notes in Computer Science. Berlin, Heidelberg: Springer-Verlag, 2003, vol. 2657, pp. 501-510.
• [34] J. Wang, „A survey of Web caching schemes for the Internet", ACM Comput. Commun. Rev., pp. 36-46, Oct. 1999.
• [35] B. Williams, „Transparent Web caching solutions", in Proc. 3rd Int. WWW Cach. Worksh.|TF-Cache Meet., Manchester, England, 1998.
• [36] A. Wierzbicki, „Internet cache location and design of content delivery networks", in Lectures Notes in Computer Science. Berlin, Heidelberg: Springer-Verlag, 2002, vol. 2376, pp. 69-82.