Topology-informed Internet replica placement

Abstract

Recently, several studies have looked into the problem of replicated server placement on the Internet. Some of those studies have demonstrated that there exists a replica placement algorithm that can perform within a factor of 1.1–1.5 of the optimal solution. However, this particular greedy algorithm requires detailed knowledge about network topology, and knowledge about expected client locations on the topology. One of these previous studies has also looked at topology-informed replica placement. They consider placing replicas at highly connected nodes in the Autonomous System level graph. In this paper, we extend their work by investigating the performance of topology-informed placement on Internet router-level topology. In our evaluation, we consider approximated policy-based paths, and examine the sensitivity of our results to different client placements. We find that topology-informed replica placement methods can achieve average client latencies which are within a factor of 1.1–1.2 of the greedy algorithm, but only if the placement method is designed carefully.