Optimal methods for coordinated enroute Web caching for tree networks

L. I. Keqiu, Hong Shen, Francis Y.L. Chin, S. Q. Zheng

Research output: Contribution to journalArticlepeer-review

52 Citations (Scopus)


Web caching is an important technology for improving the scalability of Web services. One of the key problems in coordinated enroute Web caching is to compute the locations for storing copies of an object among the enroute caches so that some specified objectives are achieved. In this article, we address this problem for tree networks, and formulate it as a maximization problem. We consider this problem for both unconstrained and constrained cases. The constrained case includes constraints on the cost gain per node and on the number of object copies to be placed. We present dynamic programming-based solutions to this problem for different cases and theoretically show that the solutions are either optimal or convergent to optimal solutions. We derive efficient algorithms that produce these solutions. Based on our mathematical model, we also present a solution to coordinated enroute Web caching for autonomous systems as a natural extension of the solution for tree networks. We implement our algorithms and evaluate our model on different performance metrics through extensive simulation experiments. The implementation results show that our methods outperform the existing algorithms of either coordinated enroute Web caching for linear topology or object placement (replacement) at individual nodes only.

Original languageEnglish
Pages (from-to)480-507
Number of pages28
JournalACM Transactions on Internet Technology
Issue number3
Publication statusPublished - Aug 2005
Externally publishedYes


  • Autonomous system (AS)
  • Dynamic programming
  • Object placement (replacement)
  • Performance evaluation
  • Tree network
  • Web caching


Dive into the research topics of 'Optimal methods for coordinated enroute Web caching for tree networks'. Together they form a unique fingerprint.

Cite this