Locating nearby copies of replicated Internet servers

ABSTRACT

In this paper we consider the problem of choosing among a collection of replicated servers, focusing on the question of how to make choices that segregate client/server traffic according to network topology. We explore the cost and effectiveness of a variety of approaches, ranging from those requiring routing layer support (e.g., anycast) to those that build location databases using application-level probe tools like traceroute. We uncover a number of tradeoffs between effectiveness, network cost, ease of deployment, and portability across different types of networks. We performed our experiments using a simulation parameterized by a topology collected from 7 survey sites across the United States, exploring a global collection of Network Time Protocol servers.

REFERENCES

• 1: Michael Accetta. RFC 887: Resource location protocol, December 1983.
• 2: Guy T. Almes, Andrew P. Black, Edward D. Lazowska, and Jerre D. Noe. The Eden system: A technical review. IEEE Transactions on Software Engzneering, SE-11(1):43-59, January 1985.
• 3: David Reeves Boggs, Internet broadcasting, 1982
• 4: C. Mic Bowman, Peter B. Danzig, Darren R. Hardy, Udi Manber, and Michael F. Schwartz. Harvest: A scalable, customizable discovery and access system. Technical report, Department of Computer Science, University of Colorado, Boulder, Colorado, August 1994. CU-CS-732-94.
• 5: C. Mic Bowman, Peter B. Danzig, Darren R. Hardy, Udi Manber, and Michael F. Schwartz. The Harvest information discovery and access system. Proceedings of the Second International World Wide Web Uonference, pages 763-771, October 1994.
• 6: Hans-Werner Braun and Kimberly C. Claffy. An experimental means of providing geographically oriented responses relative to the source of domain name server queries. Technical report, San Diego Supercomputing Center, April 1994.
• 7: Steve Casner. Frequently Asked Questions (FAQ) on the multicast backbone (MBONE), December 1994. Available from ftp://ftp.isi.edu/mbone- /faq.txt.
• 8: Anawat Chankhunthod, Peter B. Danzig, Chuck Neerdaels, Michael F. Schwartz, and Kurt J. Worrell. A hierarchical internet object cache. Technical report, Computer Science Department, University of Southern California, Los Angeles, CA., and Department of Computer Science, University of Colorado, Boulder, CO, March 1995. USC TR 95-611 and CU-CS-766-95.
• 9: Xerox Corporation. Network Binding Protocol. Technical report, Xerox Corporation, Network Systems Institute, Palo Alto, California, June 1986.
• 10: Peter Danzig, Katia Obraczka, Dante DeLucia, and Naveed Alam. Massively replicating services in autonomously managed wide-area internetworks. Technical report, University of Southern California, January 1994. USC-CS-93-541.
• 11: Steven E. Deering. P~FC 1256: ICMP router discovery messages, September 1991.
• 12: James D. Guyton and Michael F. Schwartz. Experiences with a survey tool for discovering Network Time Protocol servers. Proceedings of the USENIX Summer Conference, pages 257-265, June 1994.
• 13: James Gwertzman and Margo Seltzer. The case for geographical push-caching. Technical report, Harvard University, 1994. Avaliable from ftp://dasftp.harvard.edu/techreports/tr-34-94.ps.gz.
• 14: Steven Michael Hotz. Routing information organization to support scalable interdomain routing with heterogeneous path requirements. Technical report, Computer Science Department, University of Southern California, Los Angeles, California, September 1994 (Draft). PhD Thesis.
• 15: Van Jacobsen. Traceroute software, December 1988. Available from ftp://ftp.ee.lbl.gov/pub- /traceroute.tar. Z.
• 16: B. Kantor and P. Lapsley. RFC 977: Network News Transfer Protocol- a proposed standard for the stream-based transmission of news, February 1986.
• 17: Michael Muuss. Ping software, December 1983. Avaliable from ftp://uunet.uu.net/bsd_sources- /src/ping.
• 18: Craig Partridge, Trevor Mendez, and Walter Milliken. RFC 1546: Host anycasting service, November 1993.
• 19: Jon Postel. RFC 792: Internet control message protocol, September 1981.
• 20: David C. M. Wood, Sean S. Coleman, and Michael F. Schwartz. Fremont: A system for discovering network characteristics and problems. Proceedings of the USENIX Winter Conference, pages 335-348, January 1993.

INDEX TERMS

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

          Nouns: Internet

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

General Terms:
Algorithms, Performance