Tapestry (DHT)
Encyclopedia
Tapestry is a distributed hash table
which provides a decentralized object location, routing
, and multicast
ing infrastructure for distributed applications. It is composed of a peer-to-peer
overlay network
offering efficient, scalable, self-repairing, location-aware routing to nearby resources.
, Gnutella
, had restricting limitations such as a central directory for Napster and scoped broadcast queries for Gnutella limiting scalability. To address these problems a second generation of P2P applications were developed including Tapestry, Chord
, Pastry
, and CAN
. These overlays implement a basic key-based routing mechanism. This allows for deterministic routing of messages and adaptation to node failures in the overlay network.
Tapestry is an extensible infrastructure that provides decentralized object location and routing focusing on efficiency and minimizing message latency. This is achieved since Tapestry constructs locally optimal routing tables from initialization and maintains them in order to reduce routing stretch. Furthermore, Tapestry allows object distribution determination according to the needs of a given application. Similarly Tapestry allows applications to implement multicasting in the overlay network.
Application specific endpoints GUIDs are similarly assigned unique identifiers. NodeIDs and GUIDs are roughly evenly distributed in the overlay network with each node storing several different IDs. From experiments it is shown that Tapestry efficiency increases with network size, so multiple applications sharing the same overlay network increases efficiency. To differentiate between applications a unique application identifier is used.
Tapestry uses best-effort to publish and route objects.
Each neighbor map has multiple levels where each level contains links to nodes matching up to a certain digit position in the ID. The primary ith entry in the jth level is the ID and location of the closest node that begins with prefix (N, j-1)+i. This means that level 1 has links to nodes that have nothing in common, level 2 has the first digit in common, etc. Because of this, routing takes approximately
hops in a network of size N and IDs of base B (hex: B=16).
If an exact ID can not be found, the routing table will route to the closest matching node. For fault tolerance, nodes keep c secondary links such that the routing table has size
.
Objects are located by routing a message towards the root of the object. Each node along the path checks the mapping and redirects the request appropriately. The effect of routing is convergence of nearby paths heading to the same destination.
Distributed hash table
A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...
which provides a decentralized object location, routing
Routing
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
, and multicast
Multicast
In computer networking, multicast is the delivery of a message or information to a group of destination computers simultaneously in a single transmission from the source creating copies automatically in other network elements, such as routers, only when the topology of the network requires...
ing infrastructure for distributed applications. It is composed of a peer-to-peer
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
overlay network
Overlay network
An overlay network is a computer network which is built on the top of another network. Nodes in the overlay can be thought of as being connected by virtual or logical links, each of which corresponds to a path, perhaps through many physical links, in the underlying network...
offering efficient, scalable, self-repairing, location-aware routing to nearby resources.
Introduction
The first generation of peer-to-peer applications, including NapsterNapster
Napster is an online music store and a Best Buy company. It was originally founded as a pioneering peer-to-peer file sharing Internet service that emphasized sharing audio files that were typically digitally encoded music as MP3 format files...
, Gnutella
Gnutella
Gnutella is a large peer-to-peer network which, at the time of its creation, was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model...
, had restricting limitations such as a central directory for Napster and scoped broadcast queries for Gnutella limiting scalability. To address these problems a second generation of P2P applications were developed including Tapestry, Chord
Chord project
In computing, Chord is a protocol and algorithm for a peer-to-peer distributed hash table. A distributed hash table stores key-value pairs by assigning keys to different computers ; a node will store the values for all the keys for which it is responsible...
, Pastry
Pastry (DHT)
Pastry is an overlay and routing network for the implementation of a distributed hash table similar to Chord. The key-value pairs are stored in a redundant peer-to-peer network of connected Internet hosts. The protocol is bootstrapped by supplying it with the IP address of a peer already in the...
, and CAN
Content addressable network
The Content Addressable Network is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale...
. These overlays implement a basic key-based routing mechanism. This allows for deterministic routing of messages and adaptation to node failures in the overlay network.
Tapestry is an extensible infrastructure that provides decentralized object location and routing focusing on efficiency and minimizing message latency. This is achieved since Tapestry constructs locally optimal routing tables from initialization and maintains them in order to reduce routing stretch. Furthermore, Tapestry allows object distribution determination according to the needs of a given application. Similarly Tapestry allows applications to implement multicasting in the overlay network.
API
Each node is assigned a unique nodeID uniformly distributed in a large identifier space. Tapestry uses SHA-1 to produce a 160-bit identifier space represented by a 40 digit hex key.Application specific endpoints GUIDs are similarly assigned unique identifiers. NodeIDs and GUIDs are roughly evenly distributed in the overlay network with each node storing several different IDs. From experiments it is shown that Tapestry efficiency increases with network size, so multiple applications sharing the same overlay network increases efficiency. To differentiate between applications a unique application identifier is used.
Tapestry uses best-effort to publish and route objects.
- PublishObject
- UnPublishObject
- RouteToObject
- RouteToNode (to exact match instead of closest match)
Routing mesh
Each identifier is mapped to a live node called the root. If a node's nodeID is G then it is the root else use the routing table's nodeIDs and IP addresses to find the nodes neighbors. At each hop a message is progressively routed closer to G by incremental suffix routing.Each neighbor map has multiple levels where each level contains links to nodes matching up to a certain digit position in the ID. The primary ith entry in the jth level is the ID and location of the closest node that begins with prefix (N, j-1)+i. This means that level 1 has links to nodes that have nothing in common, level 2 has the first digit in common, etc. Because of this, routing takes approximately
hops in a network of size N and IDs of base B (hex: B=16).If an exact ID can not be found, the routing table will route to the closest matching node. For fault tolerance, nodes keep c secondary links such that the routing table has size
.Object publication and location
Participants in the network can publish objects by periodically routing a publish message toward the root node. Each node along the path stores a pointer mapping the object. Multiple servers can publish pointers to the same object. The redundant links are prioritized by latency and/or locality.Objects are located by routing a message towards the root of the object. Each node along the path checks the mapping and redirects the request appropriately. The effect of routing is convergence of nearby paths heading to the same destination.
Node insertion
The new node becomes then root for its nodeID. The root finds the length of the longest prefix of the ID it shares. Then it sends a multicast message that reaches all existing nodes sharing the same prefix. These nodes then add the new node to their routing tables. The new node may take over being the root for some of the roots objects. The nodes will contact the new node to provide a temporary neighborhood list. The new node then performs an iterative nearest neighbor search to fill all levels in its routing table.Node departure
To leave the network, a node broadcasts its intention of leaving and transmits the replacement node for each level in the routing tables of the other nodes. Objects at the leaving node are redistributed or replenished from redundant copies.Node failure
Unexpected node failure is handled through redundancy in the network and backup pointers to reestablish damaged links.Applications
Tapestry provides an overlay routing network that is stable under a variety of network conditions. This provides an ideal infrastructure for distributed applications and services. Applications based on tapestry are:- OceanStore − Distributed storage utility on PlanetLab
- Mnemosyne − Steganographic file system
- Bayeux − Self-organizing multicasting application
- Spamwatch − Decentralized spam filter
Developers
Tapestry was developed by Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph and John D. Kubiatowicz.See also
- Content addressable networkContent addressable networkThe Content Addressable Network is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale...
(CAN) - Chord (DHT)
- KademliaKademliaKademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A...
- Pastry (DHT)Pastry (DHT)Pastry is an overlay and routing network for the implementation of a distributed hash table similar to Chord. The key-value pairs are stored in a redundant peer-to-peer network of connected Internet hosts. The protocol is bootstrapped by supplying it with the IP address of a peer already in the...
External links
- Tapestry project and new implementation called Chimera
- Tapestry: A Resilient Global-Scale Overlay for Service Deployment