Placement of mirrored web servers in ring networks with budget constraint

This paper investigates the placement problem of mirrored web servers in ring networks, where each client accesses the closest mirrored server. Without budget constraint, we propose an efficient algorithm that computes the optimal placement with time complexity O(|C|² × |V|). With budget constraint, if all candidate servers charge the same fee, we propose an algorithm to compute the optimal placement in time O(k²|C|³|V|) by using dynamic programming; if candidates charge different fees, we prove the problem is NP-hard, and further propose two heuristic algorithms. The performance of the proposed placement schemes is evaluated with the traffic-reduction ratio and the budget-usage ratio over a wide range of system parameters.