a newly joining node forms its initial
links by repeatedly performing a random walk through the overlay starting
at the bootstrap node and requesting a
link to the node where the walk terminates. Nodes acquire additional links
(for example, by performing more random walks) whenever their degree falls
below the desired minimum; they refuse link requests when their current
degree is at its maximum.
The minimum node degree is typically chosen to maintain connectivity in the overlay despite node failures
and membership churn. A maximum
degree is maintained to bound the
overhead associated with maintaining
overlay links.
Structured overlays. In a structured
overlay, each node has a unique identifier in a large numeric key space, for example, the set of 160-bit integers. Identifiers are chosen in a way that makes
them uniformly distributed in that
space. The overlay graph has a specific
structure; a node’s identifier determines its position within that structure
and constrains its set of overlay links.
Keys are also used when assigning responsibilities to nodes. The
key space is divided among the participating nodes, such that each key is
mapped to exactly one of the current
overlay nodes via a simple function.
For instance, a key may be mapped to
the node whose identifier is the key’s
closest counterclockwise successor in
the key space. In this technique the key
space is considered to be circular (that
is, the id zero succeeds the highest id
value) to account for the fact that there
may exist keys greater than all node
identifiers.
The overlay graph structure is chosen to enable efficient key-based routing. Key-based routing implements
the primitive KBR(n0, k). Given a starting node n0 and a key k, KBR produces
a path, that is, a sequence of overlay
nodes that ends in the node responsible for k. As will become clear in subsequent sections, KBR is a powerful
primitive.
Many implementations of key-
based routing exist. 18, 27, 32 In general,
they strike a balance between the
amount of routing state required at
each node and the number of forward-
ing hops required to deliver a message.
Typical implementations require an
amount of per-node state and a num-
ber of forwarding hops that are both
logarithmic in the size of the network.