Tulip Overlay - Citizendia

Tulip is a distributed, decentralized, P2P network intended for routing, searching and publish-lookup information sharing. For other uses of the term see Peer-to-peer (disambiguation For peer-to-peer networks used for file sharing see File sharing It is a structured P2P network very much like Chord, Pastry, Tapestry and CAN. Chord is one of the original Distributed hash table protocols This article describes the Pastry Distributed Hash Table For the food see Pastry. Tapestry is a Distributed hash table which provides a decentralized object location Routing, and Multicasting infrastructure for distributed applications The Content Addressable Network ( CAN) is a distributed decentralized P2P infrastructure that provides Hash table functionality on an Internet

1 Overview
- 1.1 Tulip Construction
- 1.2 Key Lookup and Object Lookup
2 Developers
3 External links

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. In Mathematics, the triangle inequality states that for any Triangle, the length of a given side must be less than or equal to the sum of the other two sides but greater

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 $2\sqrt{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 as SHA-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. A hash function is any well-defined procedure or mathematical function for turning some kind of Data into a relatively small integer, that may

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 $l o g 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 $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. PlanetLab is a group of computers available as a Testbed for Computer networking and Distributed systems research 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

Paper proposing Tulip: "Practical Locality-Awareness for Large Scale Information Sharing

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Overview

Tulip Construction

Key Lookup and Object Lookup

Developers

External links