Tulip Overlay

From formulasearchengine
Jump to navigation Jump to search

Template:Orphan Tulip is a distributed, decentralized, P2P network intended for routing, searching and publish-lookup information sharing. It is a structured P2P network very much like Chord, Pastry, Tapestry and CAN.


In Tulip protocol, a network with nodes uses 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 nodes that are closest to the current node in terms of physical proximity. Tulip's construction partitions the nodes into color-sets such that:

  1. Every color-set has at most 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 and is under with high probability.

Each node 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 closest neighbors of from each color.
  2. Color List: It is the list of information about all nodes belonging to the same color group as node .

In other words, node knows all the nodes in its color group as well 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 wants to access an object at another node then, if both belong to the same color group node directly communicates with node in one hop or else if the nodes and are in different color groups, then, node communicates with its closest neighbor which is in the same color group as and reaches in 2-hops via the node .

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 stores an object , then a pointer indicating the same is stored by all nodes having the node in their vicinity list. Also, all the nodes in the same color group as an object will store a pointer to the closest node having the object .

Consider a node which is searching for the nearest node storing an object . If both and belong to the same color group then node has a pointer to the closest node storing . Otherwise, it communicates with another node which has the same color as and finds a node nearest to storing . 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.


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

External links