Tapestry
Infrastructure for Fault-resilient,
Decentralized Location and Routing
Overview
Tapestry is an overlay network infrastructure designed to provide fault-resilient
delivery of messages between overlay nodes and efficient location of objects
given their IDs. The
Tapestry project
at University of California at Berkeley Computer Science Division is headed
by Ben Y. Zhao
and Professors Anthony Joseph
and John Kubiatowicz
, with much help from collaborators including
Kris Hildrum
, Ling Huang, Shelley
Zhuang
and Sean Rhea
. Past collaborators include Tom Duan, Yan Chen, David Liu and Xiaofen
Ren, among others.
Since Tapestry's inception in March 2000, several similar research projects
have entered the same research space. Chief among these are
Pastry
from Microsoft Research and Rice University,
Chord
from MIT and UC Berkeley, and Content-addressable
Networks
(CAN) from AT&T Center for Internet Research. While all four
of these systems provide functionality to route a message to an object, the
key distinquishing property for Tapestry is performance in object
location with locality.
The basic Chord and CAN systems do not take network latencies into
account when building their initial overlay routing mesh. Tapestry and
Pastry, on the other hand, constraint the routing distance per overlay hop,
resulting in efficient point to point routing between overlay nodes.
The key difference between Pastry and Tapestry is in object location.
While Tapestry helps the user or application locate the nearest copy of an
object, Pastry actively replicates the object and places replicas at random
locations in the network. The result is that when a client searches for
a nearby object, Tapestry would route through a few hops to the object, while
Pastry might require the client to route to a distant replica of the
object.
Tapestry 2.0 released June 2003, is a java source release primarily
geared for Linux. It requires:
- Sun JDK 1.3 or a compatible Java Development and Runtime environment
(We recommend the IBM Linux JDK runtime environment, and the Jikes compiler).
- A version of the UNIX make program, used in compilation (you
can get a copy of make for Windows from Cygwin).
- The Cryptix JCE library (a version of which is included with
this release).
- The Java interface libraries for the BerkeleyDB database (included
with this release).
Tapestry is the networking substrate of OceanStore, a storage system aiming
to provide global-scale persistent and secure storage. More information
on OceanStore can be found here
. Currently, several initial applications have been and are being developed
on Tapestry. As their code becomes ready for release, they will be announced
on the Tapestry
website
. If you have comments through your use of Tapestry, good or bad,
I would appreciate hearing from you. Please email me at ravenben@cs.berkeley.edu
. The best overall introduction to the properties of Tapestry is probably in our recent journal paper in IEEE Journal on Selected Areas in Communications (JSAC), a pdf of which is here and also included in the Tapestry 2.0 distribution.
Copyright
Copyright (c) 2001 by Regents of the University of California. All
rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
- redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
- Neither the name of the University nor the names of its contributors
may be used to endorse or promote products derived from this software without
specific prior written permission
THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE OF THIS SOFTWARE,EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Ben Y. Zhao
ravenben@cs.berkeley.edu
July 2, 2003