Constrained coordinated en-route web caching in tree networks

Abstract

Caching popular objects close to users can improve web performance greatly. In this paper, we first propose a novel mathematical model for the coordinated enroute web caching problem of computing the locations for the copies of an object to be placed among the en-route caches in tree networks such that the overall cost gain is maximized under the constraint that the cost gain at each node is non-negative. We formulate this problem as a constrained optimization problem and show that it can be transformed to an unconstrained optimization problem. We present a dynamic programming-based algorithm to obtain an optimal solution to the problem. The time complexity of this algorithm is O(n2), where n is the number of nodes in the network. Second, we consider the coordinated en-route web caching problems under the constraints of placing exactly k copies and at most k copies of an object respectively. We show that these two problems can be solved by tuning the parameter of cost gain in the solution of the first problem.