AbsrracCChere is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metria such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal-content web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggests an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast p u p s , in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We a h presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area. It is increasingly the case that a given Intemet interaction could be satisfied by one of a number of Internet hosts. Examples range from short-lived interactions such as a single web page access to any one of multiple equal-content web servers to a long-term peering relationship between two news (NNTP) servers [I]. In any such interaction, all other things being equal, it is advantageous to access the "nearest" choice. By near we mean in terms of Internet performance metrics, such as low latency or high bandwidth. Even when all other things are not equal, such as the case where different web servers have different response times, it is still useful to include distance to each candidate host as one of several criteria for making a selection [2] . One approach to obtaining this distance information is for the initiating host to measure it itself, using either unicast (ping, traceroute [3]) or multicast (expanding ring search [4] ) tools. While these tools have a wide range of uses, their utility is generally limited by their overhead. For instance, the cost of running a single traceroute can exceed the cost of the web page access itself. More important still, a large number of hosts making independent and frequent measurements could have a severe impact on performance overall. Ideally, measurements made by one system (host or rquter) should be made available, at low cost, to other hosts. A useful general service for the Internet would be one whereby a host could quickly and efficiently leam the distance between any two hosts. To be widely useful, such a service should provide an answer with a delay and overhead less than those of the gains achieved by using the service. A simple protocol for such a service (SONAR) was discussed in the ETF as early as February 1996 [SI, and in April 1997 as a more general service called HOPS (Host Proximity Service) [6]. Both of these efforts proposed lightweight clientkerver queryheply protocols along the lines of a DNS querykply. Both also required that the server be able to produce an answer in a very short time-preferably, though not necessarily, by using information already stored locally. This paper is concerned with the problem of how servers in such a SONAIUHOPS service can obtain the distance information needed to answer queries. Specifically, we explore the following questions: 1. Which systems originally produce the distance information, and how is it produced? 2. How does the distance information get from these producing systems to the servers? This paper, then, takes a first stab at exploring a global, as opposed to endhost based, architecture for Internet host distance estimation and distribution. We discuss basic aspects of the questions outlined above, and based on this propose a general architecture for an underlying service that provides the basic information used by a SONAIUHOPS service. T h s underlying service is called IDMaps, for Internet Distance Map Service. Guided in part by what applications need, but more by basic limitations in technology, section I1 outlines the goals of this work. Section 111 s t m with a broad discussion of the fundamental characteristics of the problem and the nature of the solution. It presents and develops two variants of the solution, "Hop-by-Hop'' and "End-to-End"-the latter of which is more elegant but less well understood-and ends with a discussion of their pros and cons. Section IV describes the results of a preliminary analysis that tests some of the basic assumptions of the End-to-End solution. These results suggest that it has promise, and encourage us to move forward with a more detailed design and implementation. Finally, Section V discusses some of the many open issues remaining. It is difficult to state precise goals for even a SONAIUHOPS service. much less the IDMaps service. This is because SONAFUHOPS could be called upon to support a wide range of applications, from web clients that want a web server from which to retrieve a small amount of data once, to Network Tine Protocol (NTP) servers that want to establish a long term association with a peer system. We could go through the exercise of making a list of potential applications and extracting out the most demanding requirements (and to some extent, at least informally, we have done this), but in fact this exercise quickly reveals that we can't even come close to satisfying all conceivable requirements. For instance, we cannot hope for a general IDMaps service to provide near-instantaneous information about current delays and bandwidth seen between two Internet hosts. even though such information could be very useful to a host wishing to select a server supplying a live video feed, for example. Rather, we've taken somewhat the opposite tack-we determined roughly the best service we may be able to provide given technology constraints and the need for global scalability of the service, and then considered whether there are applications for which this level of service would be useful. Following is a discussion of the resulting goals. Our goal is to provide distance information in terms of latency (e.g., round-trip delay) and, where possible, bandwidth. Latency is the easiest sort of information to provide, and luckily the most generally useful. There are two reasons that it is easy to provide. First, i t is easy to measure. A small number of packets can produce a good rough estimate. Second. it is relatively independent of the exact path between the two hosts, though by no means fully independent.
Already in REF an architecture has been proposed for designing a global internet host distance estimation service.
An architecture for a global Internet host distance estimation service
IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320)
IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No.99CH36320)
Computer Science