11.24.06
Review of “OASIS: Anycast for Any Service”
This paper explores network anycast as an overlay system. When I typically think of anycast, I imagine IP level anycast. Traffic sent to a specific IP address is routed to the “best” of many possible hosts associated with that address. Best could mean closest or least loaded depending on the network. However, the OASIS system presented in this paper does not enable this sort of IP layer multicast. Instead, OASIS provides anycast at higher layers, in particular through the use of DNS and HTTP redirects. In this way, I was disappointed once start into the paper. OASIS, as it turns out, is more of a server selection service than IP anycast.
Although OASIS is not the first server selection system, it does put a couple creative twists on the process in hopes of better performance. First, OASIS does not perform on-demand probing unlike other systems such as Vivaldi [1] and Meridian [2]. Instead, OASIS stores proximity information on each IP prefix in the Internet and continuously updates this information in the background. Second, OASIS uses geographic coordinates for locating and determining closest replicas. Systems such as Vivaldi [1] use virtual coordinates to determine closest replicas. Virtual coordinates may have the edge over geographic coordinates because physical distance is not the best estimator for RTT between two end points on the Internet; however, the authors made a reasonable case that geographic coordinates for the most part are good estimators.
The authors do a good job identifying and meeting their design goals. The obvious goals of minimizing probing while maximizing accuracy and speed are not easily obtainable. They gave up some fine granularity by adopting bucketing but were able to boost scalability and cut down the amount of probing. In my mind, this was good trade-off that appears to have paid-off.
Given this new approach and understanding that OASIS is nothing more than another server selection system, it was interesting to see the performance of the system. In fact, the authors found the results quite surprising. Apparently they did not expect the system to perform much better than existing systems, particularly Meridian, since it utilized Meridian for probing. As it turns out, OASIS performed better than Meridian on 60% of measurements. Although this shows improvement, I would argue that it is not substantial improvement over the existing.
End-to-end latency is another measurement that OASIS performed quite well on. This measurement included the time to perform DNS lookup of a replica as well as the time to transfer eight files in a simulated web session. According to the experiment performed OASIS is 290% faster than Meridian and 500% faster than a simple round-robin load balancing technique. This is an important measurement because it resembles an actual user experience and is important to the adoption of OASIS.
Despite the measurements that show that OASIS performs quite well, it is not clear that OASIS will show improvement in all cases. The experiments run used 250 PlanetLab nodes as service replicas. I would have like to have seen how well OASIS worked with substantially fewer replicas. Presumably, service provides may have many less replicas, say one per continent, yet would still like to take advantage of the performance gained from server selection. However, since all measurement cost is passed to the service replicas, such a system only works when there is a large number of service replicas. This means there must be many services with a few number of replicas or a few service with many replicas each. Put another way, there is probably some critical mass of replicas that must participate before the measurement responsibilities of any one replica is not too large.
Overall, OASIS is good at what it does and improves upon previous systems. It performs closest server selection with geographic coordinates without the use of on-demand probing making it faster than other serve selection system. OASIS has an easy to use DNS interface which allows any service to utilize the system without modifying the client making it attractive for use by application developers. However, it still does not get us closer to realizing true IP level anycast.
[1] F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A decentralized network coordinate system. In SIGCOMM, Aug. 2004.
[2] B. Wong, A. Slivkins, and E. G. Sirer. Meridian: A lightweight network location service without virtual coordinates. In SIGCOMM, Aug. 2005.
traviskeshav said,
December 1, 2006 at 4:52 pm
That’s a good point about the number of replicas; I suppose maybe it should be assumed that for sufficiently low numbers of replicas, highly detailed geographic routing isn’t quite necessary. Perhaps if there’s only one per continent, some basic tests can be done by IP prefix to determine which continent the user is from, and consequently which replica is the best match.
I’m not sure I agree that OASIS’s improvement on 60% of transactions isn’t significant. However, I suppose even the authors noted that performance wasn’t really the main metric they cared about; the end-to-end latency did decrease significantly, and that satisfied their goals.