A comparative analysis of server selection in content replication networks

ABSTRACT

Server selection plays an essential role in content replication networks, such as peer-to-peer (P2P) and content delivery networks (CDNs). In this paper, we perform an analytical investigation of the strengths and weaknesses of existing server selection policies, based initially on an M/G/1 Processor Sharing (PS) queueing-theoretic 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. 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 paper is that in an N-server system, the worst case ratio between the average delay of 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 extended in asymptotic regimes to the G/G/1 First-Come First-Serve and multi-class M/G/1-PS models and supported by simulations run for various arrival and service processes, scheduling disciplines, and workload exhibiting temporal locality. These results indicate that our analysis is applicable to realistic scenarios.

REFERENCES

• 1: K. Obraczka, P. Danzig, and D. DeLucia, "Massively Replicating Services in Autonomously Managed, Wide-Area Internetworks," University of Southern California, Tech. Rep. 93-541, 1993.
• 2: Athena Vakali , George Pallis, Content Delivery Networks: Status and Trends, IEEE Internet Computing, v.7 n.6, p.68-74, November 2003 [doi>10.1109/MIC.2003.1250586]
• 3: B. Yang and H. G. Molina, "Designing a super-peer network," in Proc. Nineteenth Int. Conf. on Data Engineering, Bangalore, India, 2003.
• 4: Cisco, Cisco Global Site Selector Platforms: Chapter 1 [Online]. Available: http://www.cisco.com/en/US/products/hw/contnetw/ps4162/ products_configuration_guide_chapter09186a00800ca80e.html
• 5: Valeria Cardellini , Emiliano Casalicchio , Michele Colajanni , Philip S. Yu, The state of the art in locally distributed Web-server systems, ACM Computing Surveys (CSUR), v.34 n.2, p.263-311, June 2002 [doi>10.1145/508352.508355]
• 6: Ellen W. Zegura , Mostafa H. Ammar , Zongming Fei , Samrat Bhattacharjee, Application-layer anycasting: a server selection architecture and use in a replicated Web service, IEEE/ACM Transactions on Networking (TON), v.8 n.4, p.455-466, Aug. 2000 [doi>10.1109/90.865074]
• 7: Y. Korilis, A. Lazar, and A. Orda, "Architecting noncooperative networks," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1241-1251, 1995.
• 8: M. Stemm, R. Katz, and S. Seshan, "A network measurement architecture for adaptive applications," in Proc. IEEE INFOCOM, Tel-Aviv, Israel, Mar. 2000.
• 9: T. Ng, Y. Chu, S. Rao, K. Sripanidkulchai, and H. Zhang, "Measurement-based optimization techniques for bandwidth-demanding peer-to-peer systems," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003.
• 10: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 11: D. Villela, P. Pradhan, and D. Rubenstein, "Provisioning servers in the application tier for e-commerce systems," in Proc. Twelfth IEEE Int. Workshop on Quality of Service, Montreal, Canada, June 2004.
• 12: Mudashiru Busari , Carey Williamson, ProWGen: a synthetic workload generation tool for simulation evaluation of web proxy caches, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.6, p.779-794, 22 April 2002 [doi>10.1016/S1389-1286(01)00285-7]
• 13: J. Wardrop, "Some theoretical aspects of road traffic research," Proc. Institute of Civil Engineers, vol. 1, pt. II, pp. 325-378, 1952.
• 14: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 15: E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria," in Proc. Symp. on Theoretical Aspects in Computer Science, Trier, Germany, Mar. 1999.
• 16: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 17: J. Correa, A. Schulz, and N. Stier-Moses, "On the inefficiency of equilibria in congestion games," [Online]. Available: http://www.jcorrea. uai.cl/papers/CSS2005.pdf 2005
• 18: Tim Roughgarden, The price of anarchy is independent of the network topology, Journal of Computer and System Sciences, v.67 n.2, p.341-364, September 2003 [doi>10.1016/S0022-0000(03)00044-8]
• 19: L. Kleinrock, Queueing Systems. New York: Wiley, 1976, vol. 2.
• 20: S. Karlin and H. Taylor, A First Course in Stochastic Processes. New York: Academic, 1975.
• 21: Apache [Online]. Available: http://www.apache.org/
• 22: S. Ranjan, R. Karrer, and E. Knightly, "Wide area redirection of dynamic content by internet data centers," in Proc. IEEE INFOCOM, Hong Kong, China, Mar. 2004.
• 23: S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, "An approach to alleviate link overload as observed on an IP backbone," in Proc. IEEE INFOCOM, San Francisco, CA, 2003.
• 24: C. Fraleigh et al., "Packet-level traffic measurements from the sprint IP backbone," IEEE Network, vol. 17, no. 6, pp. 6-16, 2003.
• 25: Subhabrata Sen , Jia Wang, Analyzing peer-to-peer traffic across large networks, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.219-232, April 2004 [doi>10.1109/TNET.2004.826277]
• 26: Asser N. Tantawi , Don Towsley, Optimal static load balancing in distributed computer systems, Journal of the ACM (JACM), v.32 n.2, p.445-465, April 1985 [doi>10.1145/3149.3156]
• 27: Keith W. Ross , David D. Yao, Optimal load balancing and scheduling in a distributed computer system, Journal of the ACM (JACM), v.38 n.3, p.676-689, July 1991 [doi>10.1145/116825.116847]
• 28: Chonggun Kim , Hisao Kameda, An Algorithm for Optimal Static Load Balancing in Distributed Computer Systems, IEEE Transactions on Computers, v.41 n.3, p.381-384, March 1992 [doi>10.1109/12.127455]
• 29: M. Gerla and L. Kleinrock, "On the topological design of distributed computer networks," IEEE Trans. Commun., vol. 25, no. 1, pp. 48-60, Jan. 1977.
• 30: D. Bertsekas, Nonlinear Programming, 2nd ed. Nashua, NH: Athena Scientific, 1999.
• 31: Tao Wu , David Starobinski, An analytical study of server selection for scalable internet services, Boston University, Boston, MA, 2007
• 32: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 33: Hisao Kameda , Jie Li , Chonggun Kim , Yongbing Zhang, Optimal load balancing in distributed computer systems, Springer-Verlag, London, 1997
• 34: W. Marchal, "Some simpler bounds on the mean queueing time," Operations Research, vol. 26, pp. 1083-1088, 1978.
• 35: R. Wolff, Stochastic Modeling and the Theory of Queues. Englewood Cliffs, NJ: Prentice-Hall, 1989.
• 36: A. Zwart, "Sojourn times in a multiclass processor sharing queue," in Proc. Sixteenth Int. Teletraffic Congress, Edinburgh, U.K., Jun. 1999.
• 37: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 38: David Starobinski , Moshe Sidi, Modeling and analysis of power-tail distributions via classical teletraffic methods, Queueing Systems: Theory and Applications, v.36 n.1-3, p.243-267, 2000 [doi>10.1023/A:1019195522806]
• 39: S. Ranjan, R. Swaminathan, M. Uysal, and E. Knightly, "DDoS-resilient scheduling to counter application layer attacks under imperfect detection," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 40: B. Avi-Itzhak and H. Levy, "On measuring fairness in queues," Advances in Applied Probability, vol. 36, no. 3, pp. 919-936, 2004.
• 41: Anirban Mahanti , Derek Eager , Carey Williamson, Temporal locality and its impact on Web proxy cache performance, Performance Evaluation, v.42 n.2-3, p.187-203, Oct. 2000 [doi>10.1016/S0166-5316(00)00032-8]
• 42: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, "Web caching and Zipf-like distributions: Evidence and implications," in Proc. IEEE INFOCOM, New York, Mar. 1999, pp. 126-134.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
content delivery networks, distributed systems, game theory, load balancing, peer-to-peer networks, price of anarchy