Optimal methods for object placement in en-route web caching for tree networks and autonomous systems

This paper addresses the problem of computing the locations of copies of an object to be placed among the en-route caches such that the overall cost gain is maximized for tree networks. This problem is formulated as an optimization problem and both unconstrained and constrained cases are considered. The constrained case includes constraints on the cost gain per node and on the number of copies to be placed. Low-cost dynamic programming-based algorithms that provide optimal solutions for these cases are derived. Furthermore, based on our mathematical model, a solution to coordinated en-route web caching (CERWC) for autonomous systems (ASes) is also presented. The implementation results show that our methods outperform existing algorithms for both CERWC for linear topology and object placement at individual nodes.