Server Selection in Content Replication Networks - 02/09/2007

Tao Wu

Server selection plays an essential role in content replication networks, such as peer-to-peer (P2P) and content delivery networks (CDNs). In this work, we analytically investigate the strengths and weaknesses of existing server selection policies, based on an M/G/1 Processor Sharing queuing theoretic model, extendable, at high load, to the G/G/1 First-Come First-Serve model.

We develop a theoretical benchmark to evaluate the performance of two general server selection policies, referred to as EQ_DELAY and EQ_LOAD, which characterize a wide range of existing server selection algorithms. A key theoretical result of this work is that in an N-server system, the worst-case delay ratio between EQ_DELAY or EQ_LOAD and the minimal average delay (obtained from the benchmark) is precisely N. We constructively show how this worst-case scenario can arise in highly heterogeneous systems. This result, when interpreted in the context of selfish routing, means that the price of anarchy in unbounded delay networks depends on the topology, and can potentially be very large. Our analytical findings are supported by simulations run for various arrival and service processes, different scheduling disciplines, and workload exhibiting temporal locality and non-negligible network delays.