Weighted cache location problem with identical servers. (English) Zbl 1442.68011

Summary: This paper extends the well-known \(p\)-CLP with one server to \(p\)-CLP with \(m \geq 2\) identical servers, denoted by \((p, m)\)-CLP. We propose the closest server orienting protocol (CSOP), under which every client connects to the closest server to itself via a shortest route on given network. We abbreviate \((p, m)\)-CLP under CSOP to \((p, m)\)-CSOP CLP and investigate that \((p, m)\)-CSOP CLP on a general network is equivalent to that on a forest and further to multiple CLPs on trees. The case of \(m = 2\) is the focus of this paper. We first devise an improved \(O(p h^2 + n)\)-time parallel exact algorithm for \(p\)-CLP on a tree and then present a parallel exact algorithm with at most \(O((4 / 9) p^2 n^2)\) time in the worst case for \((p, 2)\)-CSOP CLP on a general network. Furthermore, we extend the idea of parallel algorithm to the cases of \(m > 2\) to obtain a worst-case \(O((4 / 9)(n - m)^2((m + p)^p /(p-1)!))\)-time exact algorithm. At the end of the paper, we first give an example to illustrate our algorithms and then make a series of numerical experiments to compare the running times of our algorithms.


68M10 Network design and communication in computer systems
68M12 Network protocols
68R10 Graph theory (including graph drawing) in computer science
68W10 Parallel algorithms in computer science
68W40 Analysis of algorithms
90C35 Programming involving graphs or networks
Full Text: DOI


[1] Baentsch, M.; Baum, L.; Molter, G.; Rothkugel, S.; Sturm, P., World wide web caching: the application-level view of the internet, IEEE Communications Magazine, 35, 6, 170-178 (1997)
[2] Danzig, P.; Hall, R.; Schwartz, M., A case for caching file objects inside internetworks, ACM SIGCOMM Computer Communication Review, 23, 4, 239-248 (1993)
[3] Glassman, S., A caching relay for the World Wide Web, Computer Networks and ISDN Systems, 27, 2, 165-173 (1994)
[4] Yeager, N.; McGrath, R., Web Server Technology: The Advanced Guide for World Wide Web Information Providers (1996), San Francisco, Calif, USA: Morgan Kaufmann Publishers, San Francisco, Calif, USA
[5] Chankhunthod, A.; Danzig, P.; Neerdaels, C.; Schwartz, M.; Worrell, K., A hierarchical internet object cache, Proceedings of the Annual Conference on USENIX Annual Technical Conference (ATEC ’96), USENIX Association
[6] Cohen, E.; Krishnamurthy, B.; Rexford, J., Improving end-to-end performance of the Web using server volumes and proxy filters, Computer Communication Review, 28, 4, 241-253 (1998)
[7] Abrams, M.; Stanridge, C.; Abdulla, G.; Fox, E.; Williams, S., Removal policies in network caches for World-Wide Web documents, ACM SIGCOMM Computer Communication Review, 26, 4, 293-305 (1996)
[8] Krishnan, P., Utility of co-operating Web proxy caches, Computer Networks and ISDN Systems, 30, 1-7, 195-203 (1998)
[9] Malpani, R.; Lorch, J.; Berger, D., Making world wide web caching servers cooperate, Proceedings of the 4th International World-Wide Web Conference
[10] Heddaya, A.; Mirdad, S., WebWave: globally load balanced fully distributed caching of hot published documents, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS ’97)
[11] Krishnan, P.; Raz, D.; Shavitt, Y., The cache location problem, IEEE/ACM Transactions on Networking, 8, 5, 568-582 (2000)
[12] Li, B.; Deng, X.; Golin, M.; Soharby, K., On the optimal placement of Web proxies in the Internet: linear topology, Proceedings of the IFIP TC-6 8th International Conference on High Performance Networking (HPN ’98)
[13] Li, B.; Golin, M. J.; Italiano, G. F.; Deng, X.; Sohraby, K., On the optimal placement of web proxies in the Internet, Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societie (INFOCOM ’99)
[14] Kariv, O.; Hakimi, S. L., An Algorithmic Approach to Network Location Problems. II: the p-Medians, SIAM Journal on Applied Mathematics, 37, 3, 539-560 (1979) · Zbl 0432.90075
[15] Tamir, A., An O(pn^2) algorithm for the p-median and related problems on tree graphs, Operations Research Letters, 19, 2, 59-64 (1996) · Zbl 0865.90089
[16] Woeginger, G. J., Monge strikes again: optimal placement of web proxies in the internet, Operations Research Letters, 27, 3, 93-96 (2000) · Zbl 0970.90108
[17] Chen, G.; Zhang, G.; Ding, W., Web proxy location problem in the tree networks, Applied Mathematics A: Journal of Chinese Universities, 19, 510-514 (2004)
[18] Chen, G.; Zhang, G.; Burkard, R. E., The web proxy location problem in general tree of rings networks, Journal of Combinatorial Optimization, 12, 4, 327-336 (2006) · Zbl 1126.90036
[19] Du, D., Placement of read-write Web proxies in the Internet, Proceedings of the The 21st International Conference on Distributed Computing Systems (ICDCS ’01)
[20] Jia, X.; Li, D.; Hu, X.; Wu, W.; Du, D., Placement of Web-server proxies with consideration of read and update operations on the Internet, Computer Journal, 46, 4, 378-390 (2003) · Zbl 1031.68014
[21] Liu, J.; Yang, J., Delay-constrained Web proxy problem in Internet, Computer Engineering and Applications, 45, 31, 109-110 (2009)
[22] Bondy, J. A.; Murty, U. S. R., Graph Theory with Application (1976), London, UK: Macmillan, London, UK
[23] Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269-271 (1959) · Zbl 0092.16002
[24] Ding, W.; Zhou, Y.; Chen, G.; Wang, H.; Wang, G., On the 2-MRS problem in a tree with unreliable edges, Journal of Applied Mathematics, 2013 (2013) · Zbl 1397.68140
[25] Ding, W.; Xue, G., A fast parallel algorithm for finding a most reliable source on a general ring-tree graph with unreliable edges, Combinatorial Optimization and Applications. Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 6831, 98-112 (2011), Heidelberg, Germany: Springer, Heidelberg, Germany · Zbl 1342.68253
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.