- Tulip Overlay
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.
Overview
In Tulip protocol, a network with n nodes uses O(sqrt{n}log 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 sqrt{n}log n nodes that are closest to the current node in terms of physical proximity. Tulip's construction partitions the nodes into sqrt{n} color-sets such that:
# Every color-set has at most 2sqrt{n} nodes.
# 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 asSHA-1 are used to ensure that the size of each group is about sqrt{n} and is under sqrt{n}log n with high probability.Each node u in the network maintains data in the form of two lists to capture routing information:
# Vicinity List: It is the list of information about all log n closest neighbors of u from each color.
# 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 log 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
External links
* [http://iptps05.cs.cornell.edu/PDFs/CameraReady_230.pdf Paper proposing Tulip: "Practical Locality-Awareness for Large Scale Information Sharing]
Wikimedia Foundation. 2010.