Optimal placement of mirrored web servers in ring networks

The placement problem of mirrored web servers in ring networks is investigated in the case where each client accesses the closest mirrored server. Without budget constraint, it is shown that the mirrored servers in the optimal placement are in the shape of a string including the original server S, and an efficient algorithm is proposed that computes the optimal placement with time complexity O(|C|²×|V|). With budget constraint, if all candidate servers charge the same fee, an algorithm is proposed to compute the optimal placement in time O(k²|C|³|V|) by using dynamic programming. If candidates charge different fees, the problem is shown to be NP-hard, and two heuristic algorithms are proposed. 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.