Optimal methods for proxy placement in coordinated en-route web caching

Copyright © 2005 The Institute of Electronics, Information and Communication EngineersThe performance of en-route web caching mainly depends on where the caches are located and how the cache contents are managed. In this paper, we address the problem of proxy placement in en-route web caching for tree networks, i.e., computing the optimal locations for placing k web proxies in a network such that some specified objectives are achieved. Based on our proposed model, we formulate this problem as an optimization problem and compute the optimal locations using a computationally e.cient dynamic programming-based algorithm. We also extend our solution for tree networks to solve the same problem for autonomous systems. Finally, we implement our algorithms and evaluate our model on several performance metrics through extensive simulation experiments. We also compare the performance of our model with the best available heuristic KMPC model, as well as the random proxy placement model. The implementation results show that our model outperforms all the other models with respect to all performance metrics considered. The average improvements of our model over the KMPC model and the random proxy placement model are about 31.9 percent and 58.6 percent in terms of all the performance metrics considered.Keqiu Li and Hong She