that used flooding to locate content in
a file sharing system.
Structured overlays. In structured
overlays, distributed state is maintained using a distributed hash table
(DHT) abstraction. The DHT has the
same put/get interface as a conventional hash table. Inserted key/value pairs
are distributed among the participating nodes in the structured overlay using a simple placement function. For
instance, that function can position
replicas of the key/value pair on the set
of r nodes whose identifiers succeed
the key in the circular key space. Note
that in our terminology, the values
correspond to the state objects main-
figure 3. inserting a value into a Dht.
put (key, value)
figure 4. an example KBR tree.
c
b
groupId
A
tained by the system.
Given this replica placement policy,
the DHT’s put and get operations can
be implemented using the KBR primitive in a straightforward manner. To
insert (put) a key/value pair, we use
the KBR primitive to determine the responsible node for the key k and store
the pair on that node, which then propagates it to the set of replicas for k. To
look up (get) a value, we use the KBR
primitive to fetch the value associated
with a given key. The responsible node
can respond to the fetch request or forward it to one of the nodes in the replica set. Figure 3 shows an example put
operation, where the value is initially
The key/value pair is
replicated on the node
responsible for the key
(reached via Kbr) and
its three successors.
G
The Kbr routes from group
member nodes A, b, and c
to G (the node responsible
for the group key) form a
spanning tree rooted at G.
pushed to the node responsible for key
k, which is discovered using KBR, and
this node pushes the value to its three
immediate successors.
When a DHT experiences churn,
pairs have to be moved between nodes
as the mapping of keys to nodes changes. To minimize the required network
communication, large data values are
typically not inserted directly into a
DHT; instead, an indirection pointer is
inserted under the value’s key, which
points to the node that actually stores
the value.
DHTs are used, for instance, in file
sharing networks such as eDonkey,
and also in some versions of BitTorrent.
Summary. Unstructured overlays
tend to be very efficient at locating
widely replicated objects, while KBR-based techniques can reliably and efficiently locate any object that exists
in the system, no matter how rare it
may be. Put another way, unstructured
overlays are good at finding “hay” while
structured overlays are good at finding “needles.” On the other hand, unstructured networks support arbitrary
keyword-based queries, while KBR-based systems directly support only
key-based queries.
Distributed coordination. Frequently, a group of nodes in a P2P application
must coordinate their actions without
centralized control. For instance, the
set of nodes that replicate a particular object must inform each other of
updates to the object. In another example, a node that is interested in receiving a particular streaming content
channel may wish to find, among the
nodes that currently receive that channel, one that is nearby and has available
upstream network bandwidth. We will
look at two distinct approaches to this
problem: epidemic techniques where
information spreads virally through
the system, and tree-based techniques
where distribution trees are formed to
spread the information.
We focus only on decentralized
overlays, since coordination can be accomplished by the controller node in
partly centralized systems.
Unstructured overlays. In unstructured overlays, coordination typically
relies on epidemic techniques. In
these protocols, information is spread
through the overlay in a manner simi-
