An analytical study of server selection for scalable Internet services.

摘要

Content replication has become one of the most important paradigms in modern Internet architectures because of its inherent scalability and availability. A key aspect of replication is that of server selection, which directly affects the performance, stability and fairness of content replication networks, such as content delivery networks (CDNs) and peer-to-peer (P2P) networks. While there exist numerous server selection policies, systematic and analytical study of these policies' characteristics remains limited.; In this work, we analytically investigate the strengths and weaknesses of existing server selection policies for single- and multi-class content replication networks. 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.; For single-class networks, we find that EQ_LOAD achieves an average delay always higher than or equal to that of EQ_DELAY. A key theoretical result of this work is that in an N-server single-class network, 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. These results are based on an M/G/ 1 Processor Sharing queueing-theoretic model and are extended to the G/G/1 First-Come First-Serve model at high load.; For multi-class networks, we first evaluate the performance of EQ_DELAY and EQ_LOAD in simple network topologies, and obtain their delay expressions in all configurations. We then extend these results to more general settings under low and high load regimes and derive similar bounds as in single-class networks.; 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. The simulation results indicate that our analysis is applicable to realistic scenarios and that the worst-case performance of EQ_DELAY and EQ_LOAD is likely to occur in single-class networks.