Patrick Wendell
Michael J. Freedman
Jennifer Rexford
Abstract
Geo-replicated services need an effective way to direct client requests to a particular location, based on performance, load, and cost. This paper presents DONAR, a distributed system that can offload the burden of replica selection, while providing these services with a sufficiently expressive interface for specifying mapping policies. Most existing approaches for replica selection rely on either central coordination (which has reliability, security, and scalability limitations) or distributed heuristics (which lead to suboptimal request distributions, or even instability). In contrast, the distributed mapping nodes in DONAR run a simple, efficient algorithm to coordinate their replica-selection decisions for clients. The protocol solves an optimization problem that jointly considers both client performance and server load, allowing us to show that the distributed algorithm is stable and effective. Experiments with our DONAR prototype--providing replica selection for CoralCDN and the Measurement Lab--demonstrate that our algorithm performs well "in the wild." Our prototype supports DNS- and HTTP-based redirection, IP anycast, and a secure update protocol, and can handle many customer services with diverse policy objectives.
- Amazon Web Services, "http://aws.amazon.com/," 2010.Google Scholar
- Akamai Technologies. http://www.akamai.com/, 2010.Google Scholar
- AmazonAWS, Elastic load balancing. http://aws.amazon.com/ elasticloadbalancing/, 2010.Google Scholar
- DynDNS. http://www.dyndns.com/, 2010.Google Scholar
- UltraDNS. http://www.ultradns.com/, 2010.Google Scholar
- B. Maggs, "Personal communication," 2009.Google Scholar
- M. Colajanni, P. S. Yu, and D. M. Dias, "Scheduling algorithms for distributed web servers," in ICDCS, May 1997. Google ScholarDigital Library
- M. Conti, C. Nazionale, E. Gregori, and F. Panzieri, "Load distribution among replicated Web servers: A QoS-based approach," in Workshop Internet Server Perf., May 1999.Google Scholar
- V. Cardellini, M. Colajanni, and P. S. Yu, "Geographic load balancing for scalable distributed web systems," in MASCOTS, Aug. 2000. Google ScholarDigital Library
- M. J. Freedman, K. Lakshminarayanan, and D. Mazières, OASIS: Anycast for any service," in NSDI, May 2006. Google ScholarDigital Library
- M. Pathan, C. Vecchiola, and R. Buyya, "Load and proximity aware request-redirection for dynamic load distribution in peering CDNs," in OTM, Nov. 2008. Google ScholarDigital Library
- Quova. http://www.quova.com/, 2010.Google Scholar
- MeasurementLab. http://www.measurementlab.net/, 2010.Google Scholar
- M. J. Freedman, E. Freudenthal, and D. Mazières, "Democratizing content publication with Coral," in NSDI, Mar. 2004. Google ScholarDigital Library
- B. Wong, A. Slivkins, and E. G. Sirer, "Meridian: A lightweight network location service without virtual coordinates," in SIGCOMM, Aug. 2005. Google ScholarDigital Library
- R. Krishnan, H. V. Madhyastha, S. Srinivasan, S. Jain, ishnamurthy, T. Anderson, and J. Gao, "Moving beyond end- to-end path information to optimize CDN performance," in SIGCOMM, Aug. 2009. Google ScholarDigital Library
- E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," in INFOCOM, June 2002.Google Scholar
- F. Dabek, R. Cox, F. Kaashoek, and R. Morris, "Vivaldi: A decentralized network coordinate system," in SIGCOMM, Aug. 2004. Google ScholarDigital Library
- P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, "IDMaps: A global Internet host distance estimation service," Trans. Networking, Oct. 2001. Google ScholarDigital Library
- H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services," in OSDI, Nov. 2006. Google ScholarDigital Library
- D. K. Goldenberg, L. Qiu, H. Xie, Y. R. Yang, and Y. Zhang, Optimizing cost and performance for multihoming," in SIGCOMM, Aug. 2004. Google ScholarDigital Library
- PlanetLab." http://www.planet-lab.org/, 2008.Google Scholar
- A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rex- ford, "In VINI veritas: Realistic and controlled network experimentation," in SIGCOMM, Aug. 2006. Google ScholarDigital Library
- S. Thomson, Y. Rekhter, and J. Bound, "Dynamic updates in the domain name system (DNS UPDATE)," 1997. RFC 2136.Google Scholar
- J. Terrace and M. J. Freedman, "Object storage on CRAQ: High-throughput chain replication for read-mostly workloads," in USENIX Annual, June 2009. Google ScholarDigital Library
- Zookeeper. http://hadoop.apache.org/zookeeper/, 2010.Google Scholar
- D. Dean, E. W. Felten, and D. S. Wallach, "Java security: From HotJava to Netscape and beyond," in Symp. Security and Privacy, May 1996. Google ScholarDigital Library
- V. Valancius, N. Feamster, J. Rexford, and A. Nakao, "Wide area route control for distributed services," in USENIX An- nual, June 2010. Google ScholarDigital Library
- Internet2, "Network diagnostic tool (ndt). http://www.internet2.edu/performance/ndt/, 2010.Google Scholar
- M. Mathis, J. Heffner, and R. Reddy, "Network path and application diagnosis (npad). http://www.psc.edu/networking/projects/pathdiag/, 2010.Google Scholar
- M. Krohn, E. Kohler, and F. M. Kaashoek, "Events can make sense," in USENIX Annual, Aug. 2007. Google ScholarDigital Library
- MOSEK, "http://www.mosek.com/," 2010.Google Scholar
- J. Guyton and M. Schwartz, "Locating nearby copies of repli- cated Internet servers," in SIGCOMM, Aug. 1995. Google ScholarDigital Library
- W. Theilmann and K. Rothermel, "Dynamic distance maps of the Internet," in IEEE INFOCOM, Mar. 2001.Google Scholar
- Y. Chen, K. H. Lim, R. H. Katz, and C. Overton, "On the stability of network distance estimation," SIGMETRICS Perform. Eval. Rev., vol. 30, no. 2, pp. 21--30, 2002. Google ScholarDigital Library
- 2005. http://cello.cs.uiuc.edu/cgi-bin/slamm/ip2ll/.Google Scholar
- D. Moore, R. Periakaruppan, and J. Donohoe, "Where in the world is netgeo.caida.org?," in INET, June 2000.Google Scholar
- V. N. Padmanabhan and L. Subramanian, "An investigation of geographic mapping techniques for Internet hosts," in SIG- COMM, Aug. 2001. Google ScholarDigital Library
- M. J. Freedman, M. Vutukuru, N. Feamster, and H. Balakrishnan, "Geographic locality of IP prefixes," in IMC, Oct. 2005. Google ScholarDigital Library
- B. Wong and E. G. Sirer, "ClosestNode.com: An open access, scalable, shared geocast service for distributed systems, SIGOPS OSR, vol. 40, no. 1, 2006. Google ScholarDigital Library
- H. A. Alzoubi, M. Rabinovich, and O. Spatscheck, MyXDNS: A resquest routing DNS server with decoupled server selection," in WWW, May 2007. Google ScholarDigital Library
- Z. M. Mao, C. D. Cranor, F. Douglis, M. Rabinovich, O. Spatscheck, and J. Wang, "A precise and efficient evaluation of the proximity between Web clients and their local DNS servers," in USENIX Annual, June 2002. Google ScholarDigital Library
- J. Pang, A. Akella, A. Shaikh, B. Krishnamurthy, and S. Seshan, "On the responsiveness of DNS-based network control, in IMC, Oct. 2004. Google ScholarDigital Library
- A. Schran, J. Rexford, and M. J. Freedman, "Namecast: A reliable, flexible, scalable DNS hosting system," Tech. Rep. TR-850-09, Princeton University, Apr. 2009.Google Scholar
- D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Prentice Hall, 1989. Google ScholarDigital Library
- D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.Google Scholar
Index Terms
- DONAR: decentralized server selection for cloud services
Recommendations
DONAR: decentralized server selection for cloud services
SIGCOMM '10: Proceedings of the ACM SIGCOMM 2010 conferenceGeo-replicated services need an effective way to direct client requests to a particular location, based on performance, load, and cost. This paper presents DONAR, a distributed system that can offload the burden of replica selection, while providing ...
MyXDNS: a resquest routing dns server with decoupled server selection
WWW '07: Proceedings of the 16th international conference on World Wide WebThis paper presents the architecture and the preliminary evaluation ofa request routing DNS server that decouples server selectionfrom the rest of DNS functionality. Our DNS server, which we refer toas MyXDNS, exposes well-defined APIs for uploading an ...
End-User Mapping: Next Generation Request Routing for Content Delivery
SIGCOMM'15Content Delivery Networks (CDNs) deliver much of the world's web, video, and application content on the Internet today. A key component of a CDN is the mapping system that uses the DNS protocol to route each client's request to a ``proximal'' server ...
Comments