Optimal Methods for Proxy Placement in Coordinated En-Route Web Caching

Keqiu LI  Hong SHEN  

Publication
IEICE TRANSACTIONS on Communications   Vol.E88-B   No.4   pp.1458-1466
Publication Date: 2005/04/01
Online ISSN: 
DOI: 10.1093/ietcom/e88-b.4.1458
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Internet Technology V)
Category: 
Keyword: 
en-route web caching,  dynamic programming,  proxy placement,  optimization problem,  Internet,  

Full Text: PDF>>
Buy this Article




Summary: 
The 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 efficient 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.