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

Authors

DOI:

https://doi.org/10.26636/jtit.2004.2.245

Keywords:

content delivery network, optimization, branch-andcut algorithm

Abstract

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.

Downloads

Download data is not yet available.

References

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[6] B. Davison, "The design and evaluation of Web prefetching and caching techniques", Ph.D. thesis, 2002.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[9] O. Gunluk, "Branch-and-cut algorithm for capacitated network design problems", Math. Programm., vol. 86, pp. 17-39, 1999.
View in Google Scholar

[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.
View in Google Scholar

[11] S. Jamin, Ch. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, "On the placement of Internet instrumentation", in Proc. IEEE INFOCOM 2000, Tel-Aviv, Israel, 2000, pp. 295-304.
View in Google Scholar

[12] S. Jamin, Ch. Jin, Y. Jin, A. Kurc, D. Raz, and Y. Shavitt, "Constrained mirror placement on the Internet", in Proc. IEEE INFOCOM 2001, Anchorage, Alaska, USA, 2001, pp. 31-40.
View in Google Scholar

[13] R. Karp, "On the computational complexity of combinatorical problems", Networks, vol. 5, pp. 45-68, 1975.
View in Google Scholar

[14] A. Kasprzak, Topological Design of Wide Area Networks. Wrocław: Wrocław University of Technology Press, 2001.
View in Google Scholar

[15] L. Kennington, "A survey of linear cost multicommodity networks flows", Oper. Res., vol. 26, pp. 209-236, 1978.
View in Google Scholar

[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.
View in Google Scholar

[17] P. Krishnan, D. Raz, and Y. Shavitt, "The cache location problem", IEEE/ACM Trans. Netw., vol. 8, pp. 568-582, 2000.
View in Google Scholar

[18] T. Li, "MPLS and the evolving Internet architecture", IEEE Commun. Mag., pp. 38-41, Dec. 1999.
View in Google Scholar

[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.
View in Google Scholar

[20] J. Mitchell and E. Lee, "Branch-and-bound methods for integer programming", in Handbook of Applied Optimization. Oxford: Oxford University Press, 2002.
View in Google Scholar

[21] J. Mitchell, "Branch-and-cut methods for combinatorial optimization problems", in Handbook of Applied Optimization. Oxford: Oxford University Press, 2002.
View in Google Scholar

[22] M. Padberg and G. Rinaldi, "Optimization of a 532-city traveling salesman problem by branch-and-cut", Oper. Res. Lett., vol. 6, 1987.
View in Google Scholar

[23] G. Peng, "CDN: content distribution networks", Tech. Rep., 2003.
View in Google Scholar

[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.
View in Google Scholar

[25] M. Rabinovich, "Issues in Web content replication", Data Eng. Bull., vol. 21, no. 4, 1998.
View in Google Scholar

[26] E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecture", RFC 3031, Jan. 2001.
View in Google Scholar

[27] A. Vakali, "An evolutionary scheme for Web replication and caching", in Proc. 4th Int. Web Cach. Worksh., San Diego, USA, 1999.
View in Google Scholar

[28] K. Walkowiak, "Designing of survivable Web caching", in Proc. 8th Polish Teletraffic Symp., Zakopane, Poland, 2001, pp. 171-181.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[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.
View in Google Scholar

[34] J. Wang, "A survey of Web caching schemes for the Internet", ACM Comput. Commun. Rev., pp. 36-46, Oct. 1999.
View in Google Scholar

[35] B. Williams, "Transparent Web caching solutions", in Proc. 3rd Int. WWW Cach. Worksh. - TF-Cache Meet., Manchester, England, 1998.
View in Google Scholar

[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.
View in Google Scholar

Downloads

Published

2004-06-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
K. Walkowiak, “An exact algorithm for design of content delivery networks in MPLS environment”, JTIT, vol. 16, no. 2, pp. 13–22, Jun. 2004, doi: 10.26636/jtit.2004.2.245.

Most read articles by the same author(s)