Tulip Overlay

Overview

In Tulip protocol, a network with n nodes uses O ( n l o g n ) space per node. Tulip guarantees a 2-hop optimal routing with a stretch of 2 over optimal routing, based on the assumption of the triangle inequality.

Tulip Construction

Tulip defines the vicinity of each node as the set of n l o g n nodes that are closest to the current node in terms of physical proximity. Tulip's construction partitions the nodes into n color-sets such that:

1. Every color-set has at most 2 n nodes.
2. Every node has in its vicinity at least one node from every other color-set.

Colors are assigned to Nodes based on the hash value of the node's id. Hash functions such as SHA-1 are used to ensure that the size of each group is about n and is under n l o g n with high probability.

Each node u in the network maintains data in the form of two lists to capture routing information:

1. Vicinity List: It is the list of information about all l o g n closest neighbors of u from each color.
2. Color List: It is the list of information about all nodes belonging to the same color group as node u .

In other words, node u knows all the nodes in its color group as well l o g n additional nodes for every other color.

Key Lookup and Object Lookup

Key lookup in Tulip has a guaranteed stretch of 2 over optimal lookup with up to 2 lookup hops. If a source node s wants to access an object at another node t then, if both belong to the same color group node s directly communicates with node t in one hop or else if the nodes s and t are in different color groups, then, node s communicates with its closest neighbor w which is in the same color group as t and reaches t in 2-hops via the node w .

Objects are also given a color based on the hash value of their id. There is no correlation between the color of a node and the color of the objects it stores. Moreover, a single object may also be stored in multiple nodes. Hence, in order to enable object lookup, i.e. to find the nearest node having a copy of the object, all the nodes in Tulip maintain object pointers. If a node x stores an object o , then a pointer indicating the same is stored by all nodes having the node x in their vicinity list. Also, all the nodes in the same color group as an object o will store a pointer to the closest node having the object o .

Consider a node s which is searching for the nearest node storing an object o . If both s and o belong to the same color group then node s has a pointer to the closest node storing o . Otherwise, it communicates with another node w which has the same color as o and finds a node t nearest to w storing o . The triangular inequality ensures a stretch of up to 4 over optimal object lookup.

Tulip provides separate protocols to maintain locality under churn. This includes protocols for node joining, node deletion, refresh mechanisms and multi-hop query routing. Tulip has been implemented in C++ and has already been deployed over the nodes in PlanetLab. Tulip has been shown to provide locality awareness and fault tolerance.

Developers

Ittai Abraham, Ankur Badola, Danny Bickson, Dahlia Malkhi, Sharad Maloo, Saar Ron