QoS-aware Object Replication in Overlay Networks

Many emerging applications for peer to peer overlays may require nodes to satisfy strict timing deadlines to access a replica of a given object. This includes multimedia and hard real-time applications such as distributed gaming. We formulate the QoS-aware replication problem, the goal of which is to locate the minimum number of replicas to satisfy access time deadlines for all nodes while minimizing storage usage in the overlay. Existing replication schemes cannot be used to solve this problem since they are best-effort only. We show that finding a solution to the QoS-aware object replication in an arbitrary overlay topology is intractable (NP-complete). We then present simple centralized as well as decentralized heuristics for QoS-aware replication, and compare their performance experimentally. In addition, we investigate how these decentralized heuristics effectively works in a real network. (1)