meridian title
A Lightweight Approach to Network Positioning

Meridian Framework


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.


Multi-resolution rings

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)


Applications


Meridian can be used to solve many commonly-encountered real world network positioning problems. We have evaluated how well Meridian solves the following applications: closest node discovery, central leader election, and multi-constraint resolution.

Closest node discovery is a significant problem in many real world applications. It can used to substantially benefit many distributed applications, such as filesharing networks, content distribution networks, backup systems, anonymous communication networks, pub-sub systems, service discovery, and multi-player online-games.

Meridian locates the closest node by performing a multi-hop search where each hop exponentially reduces the distance to the target. This is similar to searching in structured peer-to-peer networks such as Chord, Pastry, and Tapestry, where each hop brings the query exponentially closer to the destination, though in Meridian the routing is performed using physical latencies instead of numerical distances in a virtual identifier space. Another important distinction that Meridian holds over the structured peer-to-peer networks is that the target nodes need not be part of the Meridian overlay. The only requirement is that the latency between a node on the overlay and the target node can be measured.

When a Meridian node receives a client request to find the closest node to a target, it determines the latency d between itself and the target. Once the latency is determined, it locates its corresponding ring j and simultaneously queries all nodes in that ring, as well as all nodes in the adjacent rings j-1 and j+1 whose distances from the originating node is within d/2 to 3d/2. These nodes measure their distance to the target and report back to the source. If one of the queried peers is closer than B times the distance to the target, the client request is forwarded to the queried peer closest to the target. A larger B may reduce error at the expense of increased hop count. Figure 2 illustrates the process.

Central leader election is another frequently encountered problem in distributed systems, where the node that is “centrally situated” with respect to a set of other nodes is desired, as illustrated in Figure 3. Typically, such a node plays a specialized role in the network that requires frequent communication with the other members of the set; selecting a centrally located node minimizes both latency and network load. An example application is leader election, which itself is a building block for higher level applications such as clustering and low latency multicast trees. The central leader election application can be implemented by extending the closest node discovery protocol by replacing d in the single target closest node selection protocol with dsum in the multi-target protocol. The dsum is the sum of the latencies from the node to the set of targets.

Multi-constraint system is used in distributed systems to find a set of nodes satisfying constraints on the network geography. For instance, an ISP or a web hosting service is typically bound by a service level agreement (SLA) to satisfy latency requirements to well-known peering locations when hosting services for clients. A geographically distributed ISP may have thousands of nodes at its disposal, and finding the right set of nodes that satisfy the given constraints is necessary for satisfying the SLA. Latency constraints are also important for grid based distributed computation applications, where the latency between nodes working together on a problem is often the main efficiency bottleneck. A customer may want to specify that latency between every pair of nodes operating on a particular computation must be less than some value.

Finding a node that satisfies multiple constraints can be viewed as a node selection problem, where the constraints define the boundaries of a region in space (the solution space), as illustrated in Figure 4. A constraint is specified as a target and latency bound around that target. The closest node discovery protocol can be extended to “zoom in” to the solution space instead of a particular node.


Closest node discovery

Figure 2. A client sends a “closest node discovery to target T” request to a Meridian node A, which determines its latency d to T and probes its ring members between d/2 and 3d/2 to determine their distances to the target. The request is forwarded to the closest node thus discovered, and the process continues until no closer node is detected.





Central leader election

Figure 3. Central leader election selects the node with the minimum dsum, where dsum is the sum of the latencies from the node to the set of targets. For this example, node A is the best leader out of nodes A to H, where nodes A to H are also the targets.





Multi-constraint system

Figure 4. A multi-constraint query consisting of targets A, B, C with respective latency constraints αa, αb, αc. The shaded area represents the solution space, and contains two nodes.


Meridian Project

Computer Science Department
Cornell University