lar to the way an infection spreads in
a population: the node that produced
the information sends it to (some of)
its overlay neighbors, who send it to
(some of) their neighbors, and so on.
This method of dissemination is very
simple and robust. As in all epidemic
techniques, there is a trade-off between the speed of information dissemination and overhead. Moreover, if
a given piece of information is of interest only to a subset of nodes and these
nodes are widely dispersed within the
overlay, then the information ends up
being needlessly delivered to all nodes.
A more efficient way to coordinate
the actions among a group of nodes
is to form a spanning tree among the
nodes. The spanning tree is embedded
in the overlay graph, using a decentralized algorithm for spanning tree formation. This tree can then be used to
multicast messages to all members, or
to compute summaries (for example,
sums, averages, minima, or maxima) of
state variables within the group. However, this added coordination efficiency must be balanced against the overhead of maintaining the spanning tree
in the unstructured overlay network.
Structured overlays. In structured
overlays, spanning trees among any
group of overlay nodes can be formed
and maintained very efficiently using the KBR primitive, making trees
the preferred method of coordination
in these overlays. To join a spanning
tree, a node uses KBR to route to a
unique key associated with the group.
The resulting union of the paths from
all group members form a spanning
tree rooted at the node responsible for
the group’s key. This KBR tree is then
used to aggregate and disseminate
state associated with the group, and to
implement multicast and anycast. Figure 4 illustrates an example KBR tree
formed by the union of the KBR routes
from nodes A, B, and C to the key corresponding to the group id. This tree is
rooted at node G, which is the responsible node for that key.
Because a join message terminates
as soon as it intercepts the tree, group
membership maintenance is decentralized, that is, the arrival or departure
of a node is noted only by the node’s
parent and children in the tree. As a
result, the technique scales to large
numbers of groups, as well as large and
unstructured
overlays are good at
finding “hay,” while
structured overlays
are good at finding
“needles.”
highly dynamic groups.
Summary. The epidemic techniques
typically used for coordination in unstructured overlays are simple and robust to overlay churn, but they may not
scale to large overlays or large numbers
of groups, and information tends to
propagate slowly. Spanning trees can
increase the efficiency of coordination,
but maintaining a spanning tree in an
unstructured overlay adds costs.
The additional overhead for maintaining a structured overlay is proportional to the churn in the total overlay
membership. Once that overhead is
paid, KBR trees enable efficient and
fast coordination among potentially
numerous, large and dynamic subgroups within the overlay.
content Distribution
Another common task in P2P systems is the distribution of bulk data
or streaming content to a set of interested nodes. P2P techniques for content distribution can be categorized
as tree-based (where fixed distribution
trees are formed either with the aid of
a structured overlay or embedded in
an unstructured overlay), or swarming
protocols (which have no notion of a
fixed tree for routing content and usually form an unstructured overlay). Due
to space constraints, we focus on the
swarming protocols popularized by the
Bit Torrent protocol. 10
In swarming protocols, the content
is divided into a sequence of blocks,
and each block is individually multicast to all overlay nodes such that different blocks are disseminated along
different paths.
The basic operation of a swarming
protocol is simple: once every swarming interval (say, one second), overlay
neighbors exchange information indicating which content blocks they have
available. (In streaming content distribution, only the most recently published blocks are normally of interest.)
Each node intersects the availability information received from its neighbors,
and then requests a block it does not
already have from one of the neighbors
who has it.
It is important that blocks are well
distributed among the peers, to ensure
neighboring peers tend to have blocks
they can swap and that blocks remain
available when some peers leave the
