Procedure & Terminology


This page describes how the following mechanisms work, as implemented in VAST:

1. Voronoi-based Overlay Network (VON): how peers connect each other in a P2P overlay and perform neighbor discovery
2. Voronoi Self-organizing Overlay (VSO): how peers in a VON adjust themselves automatically to balance loads
3. VoroCast: 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:





VAST Terminology



A Voronoi Diagram: Dots indicate sites, and lines define boundaries (edges) for regions.
A Voronoi Diagram: Dots indicate sites, and lines define boundaries (edges) for regions.




Voronoi-related definitions
Site: a point (i.e. node) on 2D plane defined by a (x, y) coordinate pair.
Voronoi diagram: a geometrical method to partition a 2D plane with n sites into n areas such that each point in the area is closer to the area’s site than to any other site.
Region: area that belongs to a particular site after partitioning.
Edge: 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.
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.





VON Procedures


Node definitions
Joining node: the node that is about to join VON.
Moving node: the node that is moving (i.e. sending position updates to its neighbors).
Leaving node: the node that is leaving VON (whether normally or abnormally).
Acceptor: the node whose Voronoi region contains the joining node’s initial position.
Gateway server: 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.

JOIN procedure

  1. Joining node sends a join request with its coordinates to any existing node (which can be the gateway server).
  2. Join request is forwarded to the acceptor (i.e. the node whose region contains the joining node’s coordinates) by greedy forward (see Fig. 1a).
  3. Joining node connects to each neighbor on the list ※.
  4. Joining node builds up a Voronoi diagram of its AOI neighbors while the contacted nodes update their Voronoi diagrams to accommodate the joining node (see Fig. 1b).
VON-join.jpg
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.


MOVE Procedure

  1. Moving node sends position updates to all connected neighbors.
  2. Boundary neighbor checks if any of its own enclosing neighbors has entered the moving node’s AOI (see Fig. 2a) or if the moving node has any new enclosing neighbor. If so then it sends a notification.
  3. If a valid new AOI neighbor is discovered, the moving node connects to it ※.
  4. Moving node disconnects any boundary neighbor that has left its AOI (see Fig. 2b).
  5. All nodes update their Voronoi diagrams to reflect the current topology at each step.
VON-move.jpg
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.

LEAVE Procedure

  1. Leaving node simply disconnects (there is no distinction between proper and abnormal departures from the overlay network, see Fig. 3a).
  2. Affected neighboring nodes update their Voronoi. If a boundary neighbor leaves, replacements are learned via still-connected boundary neighbors (see Fig. 3b).

VON-leave.jpg
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 ▓).




VSO Procedures









VoroCast Procedures


Node definitions
Root node: the node that is the initial position or center node of the AOI.
Parent node: the node that is my enclosing and also it is the closest to root node.
Peer node: the node that selects a parent node.

Root node procedure

  1. Root node updates its AOI with the enclosing and boundary neighbors.
  2. Root node sends the messages to its enclosing neighbors with a spanning tree diffusion (see Fig. 4).

imgVoroCast-A.png
Figure: 4 Root node begins spanning tree


Parent node procedure

  1. Parent node selects peer nodes as possibles child nodes.
  2. Parent node sends requests to its enclosing peer nodes to be child nodes (see Fig. 5).
  3. Parent node forwards the messages to its child nodes.

imgVoroCast-D.png
Figure: 5 Selecting a parent node.

Peer node procedure

  1. Peer node receives requests to accept a parent node.
  2. Peer node evaluates parent node proximity to the root.
  3. Peer node sets the closest parent node to root as its parent (see Fig. 6).
imgVoroCast-E.png
Fig: 6 A complite spanning tree among AOI neighbors