Early work on latency prediction services focused on reducing the intractability of all-pairs measurements through clustering. Based on the assumption that nodes in the same cluster would have similar latencies to nodes in another cluster, researchers examined how to create accurate clusters and how to minimize inter- and intra-cluster measurement overhead. Francis et al.created clusters based on IP address prefixes, but found that prediction error was heavily dependent on the initial choice of representatives [12]. Chen et al. addressed this problem through the automatic formation of clusters and representatives; they found the cluster size and, more generally, the amenability of the network to clustering had a large effect on accuracy [6]. Ratnasamy et al. proposed a hybrid approach: nodes that are similar distances away from fixed landmarks place themselves into the same cluster; they also found error was highly dependent on the number of bins [26]. Because all of this clustering involves measurement and lower network layers are already performing much of this measurement, Nakao et al. proposed reducing overhead by tapping into this existing information; unfortunately, this requires a change in the interface of Internet routers [21].
While this research and the work on network coordinates that grew out of it focus on generalized latency prediction -- maintaining an infrastructure that works well for most queries -- a separate body of work has focused more directly on the problem of finding the nearest of many replicated services. In direct response to an application-level request, Meridian finds the nearest overlay node (i.e., one running Meridian) to an arbitrary point in the Internet through a set of pings that progress logarithmically closer to the target [32]. Freedman et al. developed OASIS, a distributed service explicitly designed to help clients find and choose a ``good'' server out of many [13]. Building on Meridian, OASIS primarily focuses on network locality, but also incorporates liveness and load. OASIS employs a reliable core of hosts to map clients to nearby servers, which are assumed to be long-lived. Note the distinct purposes of these anycast services from those of network coordinates: Meridian and OASIS are designed for the case where contact with the service will be frequent and long-lived enough to outweigh the high upfront cost of finding the best service. With their current levels of accuracy (good but not perfect) and maintenance (zero), network coordinates fall to the other side of the trade-off: short-lived, cheap decisions for which finding the exact answer is not worthwhile, but repeatedly finding a good answer leads to aggregate savings. While Meridian (and OASIS) are inherently reactive - acting in response to a query - they too could be more tightly integrated with an application, using its messages to dampen ring maintenance, for example.
Jonathan Ledlie 2007-02-23