| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Bounded-Latency Content Distribution: Feasibility and Evaluation
November 2005 (vol. 54 no. 11)
pp. 1422-1437
This paper investigates the performance of a content distribution network designed to provide bounded content access latency. Content can be divided into multiple classes with different configurable per-class delay bounds. The network uses a simple distributed algorithm to dynamically select subsets of its proxy servers for different classes such that a global per-class delay bound is achieved on content access. The content distribution algorithm is implemented and tested on PlanetLab [25], a world-wide distributed Internet testbed. Evaluation results demonstrate that, despite Internet delay variability, subsecond delay bounds (of 200-500ms) can be guaranteed with a very high probability at only a moderate content replication cost. The distribution algorithm achieves a four to five-fold reduction in the number of response-time violations compared to prior content distribution approaches that attempt to minimize average latency. To the authors' knowledge, this paper presents the first wide-area performance evaluation of an algorithm designed to bound maximum content access latency, as opposed to optimizing an average performance metric.
[1] 1422 Akamai, http:/www.akamai.com, 2005.[2] A. Barbir, B. Cain, R. Nair, and O. Spatscheck, “Known Content Network (CN) Request-Routing Mechanisms,” RFC 3568, July 2003.[3] V. Cardellini, M. Colajanni, and P.S. Yu, “Request Redirection Algorithms for Distributed Web Systems,” IEEE Trans. Parallel and Distributed Systems, Apr. 2003.[4] R.L. Carter and M.E. Crovella, “Server Selection Using Bandwidth Probing in Wide-Area Networks,” Proc. IEEE INFOCOM '97, 1997.[5] Y. Chen, R.H. Katz, and J.D. Kubiatowicz, “Scan: A Dynamic, Scalable, and Efficient Content Distribution Network,” Proc. Int'l Conf. Pervasive Computing (Pervasive '02), Aug. 2002.[6] V. Chvátal, “A Greedy Heuristic for the Set-Covering Problem,” Math. Operations Research, 1979.[7] M. Crovella and A. Bestavros, “Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes,” Proc. SIGMETRICS '96, May 1996.[8] M.R. Garey and D.S. Johnson, Computers and Intractability. W.H. Freeman, 1979.[9] N. Hu and P. Steenkiste, “Evaluation and Characterization of Available Bandwidth Probing Techniques,” IEEE J. Selected Areas in Comm., special issue on Internet and WWW measurement, mapping, and modeling, Aug. 2003.[10] M. Jain and C. Dovrolis, “End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP Throughput,” Proc. ACM SIGCOMM '02, Aug. 2002.[11] S. Jamin, C. Jin, A.R. Kurc, D. Raz, and Y. Shavitt, “Constrained Mirror Placement on the Internet,” Proc. IEEE INFOCOM '01, Apr. 2001.[12] L. Jia, R. Rajaraman, and T. Suel, “An Efficient Distributed Algorithm for Constructing Small Dominating Sets,” Proc. 20th ACM Symp. Principles of Distributed Computing (PODC '01), Aug. 2001.[13] D.S. Johnson, “Approximation Algorithms for Combinational Problems,” J. Computer and System Sciences, 1974.[14] K.L. Johnson, J.F. Carr, M.S. Day, and M.F. Kaashoek, “The Measured Performance of Content Distribution Networks,” Proc. Fifth Int'l Web Caching Workshop and Content Delivery Workshop (WCW '00), 2000.[15] J. Kangasharju, J. Roberts, and K.W. Ross, “Object Replication Strategies in Content Distribution Networks,” Proc. Sixth Int'l Web Caching Workshop and Content Delivery Workshop (WCW '01), 2001.[16] M. Karlsson, C. Karamanolis, and M. Mahalingam, “A Framework for Evaluating Replica Placement Algorithms,” Technical Report HPL-2002-219, HP Labs, 2002.[17] B.-J. Ko and D. Rubenstein, “Distributed, Self-Stabilizing Placement of Replicated Resources in Emerging Networks,” Proc. 11th Int'l Conf. Network Protocols (ICNP '03), Nov. 2003.[18] B. Krishnamurthy, C. Wills, and Y. Zhang, “On the Use and Performance of Content Distribution Networks,” Proc. ACM SIGCOMM Internet Measurement Workshop 2001, Nov. 2001.[19] F. Kuhn and R. Wattenhofer, “Constant-Time Distributed Dominating Set Approximation,” Proc. 22nd ACM Symp. Principles of Distributed Computing (PODC '03), July 2003.[20] B. Li, M. Golin, G. Italiano, and K. Sohraby, “On the Optimal Placement of Web Proxies in the Internet,” Proc. IEEE INFOCOM '99, Mar. 1999.[21] B. Liang and Z.J. Hass, “Virtual Backbone Generation and Maintenance in Ad Hoc Network Mobility Management,” Proc. IEEE INFOCOM '00, Mar. 2000.[22] Z. Mao, J. Rexford, J. Wang, and R. Katz, “Towards an Accurate AS-Level Traceroute Tool,” Proc. ACM SIGCOMM '03, 2003.[23] D. Mosberger and T. Jin, “httperf: A Tool for Measuring Web Server Performance,” Proc. First Workshop Internet Server Performance, June 1998.[24] A. Ninan, P. Kulkarni, P. Shenoy, K. Ramamritham, and R. Tewari, “Cooperative Leases: Scalable Consistency Maintenance in Content Distribution Networks,” Proc. Int'l World Wide Web Conf., 2002.[25] PlanetLab, http:/www.planet-lab.org, 2005.[26] L. Qiu, V.N. Padmanabhan, and G.M. Voelker, “On the Placement of Web Server Replicas,” Proc. IEEE INFOCOM '01, Apr. 2001.[27] M. Rabinovich, I. Rabinovich, R. Rajaraman, and A. Aggarwal, “A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service,” Proc. IEEE Int'l Conf. Distributed Computing Systems (ICDCS '99), 1999.[28] P. Radoslavov, R. Govindan, and D. Estrin, “Topology-Informed Internet Replica Placement,” Proc. Sixth Int'l Web Caching Workshop and Content Delivery Workshop (WCW '01), June 2001.[29] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content Addressable Network,” Proc. ACM SIGCOMM '01, 2001.[30] RIPE NCC Routing Information Service, riswhois.ripe.net, 2005.[31] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems,” Proc. IFIP/ACM Int'l Conf. Distributed Systems Platforms (Middleware), Nov. 2001.[32] S. Saroiu, K.P. Gummadi, R. Dunn, S.D. Gribble, and H.M. Levy, “An Analysis of Internet Content Delivery Systems,” Proc. Fifth Symp. Operating Systems Design and Implementation (OSDI '02), 2002.[33] Sprint IP Monitoring Project, http:/ipmon.sprint.com, 2005.[34] Sprint IPMon Delay Analysis, http://ipmon.sprint.comdelay stat, 2005.[35] Squid Web Cache, http:/www.squid-cache.org, 2005.[36] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,” Proc. ACM SIGCOMM '01, Aug. 2001.[37] J. Strauss, N. Katabi, and M.F. Kaashoek, “A Measurement Study of Available Bandwidth Estimation Tools,” Proc. Internet Measurement Conf. (IMC) 2003, Oct. 2003.[38] X. Tang and J. Xu, “On Replica Placement for QoS-Aware Content Distribution,” Proc. IEEE INFOCOM '04, Mar. 2004.[39] A. Venkataramani, P. Weidmann, and M. Dahlin, “Bandwidth Constrained Placement in a WAN,” Proc. ACM Principles of Distributed Computing (PODC '01), Aug. 2001.[40] L. Wang, V. Pai, and L. Peterson, “The Effectiveness of Request Redirection on CDN Robustness,” Proc. Fifth Symp. Operating Systems Design and Implementation (OSDI '02), Dec. 2002.[41] J. Yin, L. Alvisi, M. Dahlin, and A. Iyengar, “Engineering Server-Driven Consistency for Large Scale Dynamic Web Services,” Proc. Int'l World Wide Web Conf. (WWW '01), 2001.[42] B.Y. Zhao, J. Kubiatowicz, and A.D. Joseph, “Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing,” Technical Report UCB/CSD-01-1141, Univ. of California Berkeley, 2001.
Index Terms:
Index Terms- Content distribution networks, distributed systems, performance evaluation.
Citation:
Chengdu Huang, Tarek Abdelzaher, "Bounded-Latency Content Distribution: Feasibility and Evaluation," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1422-1437, Nov. 2005, doi:10.1109/TC.2005.175
