23rd International Conference on Distributed Computing Systems Workshops (ICDCSW'03)
Placement of Mirrored Web Servers in Ring Networks with Budget Constraint
Providence, Rhode Island, USA
May 19-May 22
ISBN: 0-7695-1921-0
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 0(|C|2 ×|V|). With budget constraint, if all candidate servers charge the same fee, we propose an algorithm to compute the optimal placement in time 0(k2|C|3|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.
Index Terms:
web server; web proxy; mirrored servers; ring networks
Citation:
Hai Liu, Xiaohua Jia, Deying Li, C. H. Lee, "Placement of Mirrored Web Servers in Ring Networks with Budget Constraint," icdcsw, pp.905, 23rd International Conference on Distributed Computing Systems Workshops (ICDCSW'03), 2003