# Tulip Overlay

This article relies too much on references to primary sources. (March 2018) (Learn how and when to remove this template message) |

**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 [math]\displaystyle{ n }[/math] nodes uses [math]\displaystyle{ O(\sqrt{n}log n) }[/math] 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 [math]\displaystyle{ \sqrt{n}log n }[/math] nodes that are closest to the current node in terms of physical proximity. Tulip's construction partitions the nodes into [math]\displaystyle{ \sqrt{n} }[/math] color-sets such that:

- Every color-set has at most [math]\displaystyle{ 2\sqrt{n} }[/math] 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 [math]\displaystyle{ \sqrt{n} }[/math] and is under [math]\displaystyle{ \sqrt{n}log n }[/math] with high probability.

Each node [math]\displaystyle{ u }[/math] 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 [math]\displaystyle{ log n }[/math] closest neighbors of [math]\displaystyle{ u }[/math] from each color.
- Color List: It is the list of information about all nodes belonging to the same color group as node [math]\displaystyle{ u }[/math].

In other words, node [math]\displaystyle{ u }[/math] knows all the nodes in its color group as well [math]\displaystyle{ log n }[/math] 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 [math]\displaystyle{ s }[/math] wants to access an object at another node [math]\displaystyle{ t }[/math] then, if both belong to the same color group node [math]\displaystyle{ s }[/math] directly communicates with node [math]\displaystyle{ t }[/math] in one hop or else if the nodes [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] are in different color groups, then, node [math]\displaystyle{ s }[/math] communicates with its closest neighbor [math]\displaystyle{ w }[/math] which is in the same color group as [math]\displaystyle{ t }[/math] and reaches [math]\displaystyle{ t }[/math] in 2-hops via the node [math]\displaystyle{ w }[/math].

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 [math]\displaystyle{ x }[/math] stores an object [math]\displaystyle{ o }[/math], then a pointer indicating the same is stored by all nodes having the node [math]\displaystyle{ x }[/math] in their vicinity list. Also, all the nodes in the same color group as an object [math]\displaystyle{ o }[/math] will store a pointer to the closest node having the object [math]\displaystyle{ o }[/math].

Consider a node [math]\displaystyle{ s }[/math] which is searching for the nearest node storing an object [math]\displaystyle{ o }[/math]. If both [math]\displaystyle{ s }[/math] and [math]\displaystyle{ o }[/math] belong to the same color group then node [math]\displaystyle{ s }[/math] has a pointer to the closest node storing [math]\displaystyle{ o }[/math]. Otherwise, it communicates with another node [math]\displaystyle{ w }[/math] which has the same color as [math]\displaystyle{ o }[/math] and finds a node [math]\displaystyle{ t }[/math] nearest to [math]\displaystyle{ w }[/math] storing [math]\displaystyle{ o }[/math]. 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