Meridian is a lightweight framework for performing network
positioning without embedding nodes into a global virtual coordinate space. The
framework consists of an overlay network structured around multi-resolution
rings, query routing with direct measurements, and gossip protocol for
dissemination.
The goal of the framework is to have each node know enough local information
to authoritatively answer geographic queries for its region of the network, and
hand off queries regarding distant nodes to a neighbor in that region. Essentially,
the idea is for each node-to-node query hand-off to “zoom in” to the solution
space, reducing the necessary state requirement on each node to only
logarithmic of the system size.
Each Meridian node must therefore keep information on a
subset of the neighbor nodes in the system. The neighbor nodes must be selected
to satisfy the requirement of giving the owner authoritative information on its
region. However, for the system to have very few hand-off hops, a node must
also keep a diverse set of neighbors outside its immediate region. A Meridian node
organizes its neighbors in multi-resolution rings to satisfy the authoritative
information requirement as well as to increase diversity in its neighbor set.
The multi-resolution rings are a set of concentric,
non-overlapping rings, with each ring containing the same maximum number of
members. The radius of each ring is measured in latency, and a neighbor is
placed in the appropriate ring of a node depending on the peer’s latency to it.
The ring radii increase exponentially i.e. the radius of a ring i is a
fixed factor larger than the radius of the ring i-1. The rationale for
exponentially increasing ring radii stems from the need for having local
authoritative information as well as having a representative set of pointers to
the rest of the network.
Organizing neighbors into multi-resolution rings is not
sufficient to ensure diversity, as the ring members of each ring may still be
tightly clustered. A ring membership management scheme is used to further
improve the diversity of nodes within each ring by selecting well spread nodes
that lie in the enclosed latency space as ring members as shown in Figure 1.
The scheme performs a local
non-exported network embedding of the nodes in each ring, and selects the set
of neighbors that form the largest hypervolume polytope. Intuitively, we can
see that the ring members are diverse within the enclosed space by looking at
the three dimensional case, which selects the three nodes from each ring that
form the largest triangle.
|
|
Figure 1. Each Meridian node keeps track of a fixed number of other nodes and organizes
these nodes into concentric, non-overlappng rings of exponentially increasing
radii. Within a given ring, a set of nodes that span a large amount of space (dark)
are more desirable than a more limited subset (light)
|