Skip to main content
You are not a member of this wiki.
Pages and Files
Procedure & Terminology
This page describes how the following mechanisms work, as implemented in VAST:
Voronoi-based Overlay Network (VON)
: how peers connect each other in a P2P overlay and perform neighbor discovery
Voronoi Self-organizing Overlay (VSO)
: how peers in a VON adjust themselves automatically to balance loads
: how peers in a VON can multicast messages to a specified area based on forwarding
Below we first describe the terminology, then the procedures for each mechanism:
A Voronoi Diagram: Dots indicate sites, and lines define boundaries (edges) for regions.
a point (i.e. node) on 2D plane defined by a (x, y) coordinate pair.
: a geometrical method to partition a 2D plane with
areas such that each point in the area is closer to the area’s site than to any other site.
area that belongs to a particular site after partitioning.
: boundary lines that define Voronoi regions.
Large circle is the AOI boundary for the center node. Squares (▓) are enclosing neighbors; triangles (▲) are boundary neighbors; stars (★) are both enclosing and boundary neighbors; circle (●) represents a regular AOI-neighbor; crosses (╳) represent neighbors irrelevant (i.e. outside of AOI) to the center node.
: the node that is about to join VON.
: the node that is moving (i.e. sending position updates to its neighbors).
: the node that is leaving VON (whether normally or abnormally).
the node whose Voronoi region contains the joining node’s initial position.
: an well-known initial entry point for entering VON.
Neighbor definitions (for a given node n)
AOI neighbors (AN)
: nodes whose coordinates are inside the AOI of n.
Enclosing neighbors (EN)
: nodes that have shared edges with n’s Voronoi region.
Boundary neighbors (BN)
: AOI neighbors whose ENs may be outside the AOI of n.
Note for procedures below:
※ When any node A initiates a connection to node B, it also sends its knowledge of node B’s enclosing neighbors during handshakes. Node B would then verify and notify node A of any missing ones.
sends a join request with its coordinates to any existing node (which can be the
Join request is forwarded to the
(i.e. the node whose region contains the joining node’s coordinates) by greedy forward (see Fig. 1a).
connects to each neighbor on the list ※.
builds up a Voronoi diagram of its
while the contacted nodes update their Voronoi diagrams to accommodate the
(see Fig. 1b).
Figure 1: JOIN procedure (a) Gateway server and its ENs are the circles. Acceptor and its ENs are the squares. Star (☆) is the intended joining spot. Join request is forwarded to the acceptor (b) Star (★) is the joining node, shades are neighbors affected by join. Note that the effect is localized.
sends position updates to all connected neighbors.
checks if any of its own
has entered the moving node’s AOI (see Fig. 2a) or if the
has any new
. If so then it sends a notification.
If a valid new
is discovered, the
connects to it ※.
that has left its AOI (see Fig. 2b).
All nodes update their Voronoi diagrams to reflect the current topology at each step.
Figure 2: MOVE procedure (a) Triangle (▲) indicates the intended new position. Squares (▓) are new neighbors about to be discovered. Stars (★) are the boundary neighbors. (b) After the move, crosses (╳) are the neighbors no longer inside the AOI, therefore are disconnected.
simply disconnects (there is no distinction between proper and abnormal departures from the overlay network, see Fig. 3a).
Affected neighboring nodes update their Voronoi. If a
leaves, replacements are learned via still-connected
(see Fig. 3b).
Figure 3: LEAVE procedure (a) Cross (╳) is the leaving node. (b) After node leave, triangle (▲) is a new enclosing neighbor discovered by still-connected boundary/enclosing neighbors (Squares ▓).
: the node that is the initial position or center node of the AOI.
the node that is my enclosing and also it is the closest to root node.
the node that selects a parent node.
Root node procedure
updates its AOI with the enclosing and boundary neighbors.
sends the messages to its
with a spanning tree diffusion (see Fig. 4).
Figure: 4 Root node begins spanning tree
Parent node procedure
selects peer nodes as possibles child nodes.
sends requests to its enclosing peer nodes to be child nodes (see Fig. 5).
forwards the messages to its child nodes.
Figure: 5 Selecting a parent node.
Peer node procedure
receives requests to accept a parent node.
evaluates parent node proximity to the root.
sets the closest parent node to root as its parent (see Fig. 6).
Fig: 6 A complite spanning tree among AOI neighbors
help on how to format text
Turn off "Getting Started"