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.

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.

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

Joining node sends a join request with its coordinates to any existing node (which can be the gateway server).

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).

Joining node connects to each neighbor on the list ※.

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).

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

Moving node sends position updates to all connected neighbors.

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.

If a valid new AOI neighbor is discovered, the moving node connects to it ※.

Moving node disconnects any boundary neighbor 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.

LEAVE Procedure

Leaving node 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 boundary neighbor leaves, replacements are learned via still-connected boundary neighbors (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 ▓).

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

Root node updates its AOI with the enclosing and boundary neighbors.

Root nodesends the messages to its enclosing neighbors with a spanning tree diffusion (see Fig. 4).

Figure: 4 Root node begins spanning tree

Parent node procedure

Parent node selects peer nodes as possibles child nodes.

Parent node sends requests to its enclosing peer nodes to be child nodes (see Fig. 5).

Parent node forwards the messages to its child nodes.

Figure: 5 Selecting a parent node.

Peer node procedure

Peer node receives requests to accept a parent node.

Peer node evaluates parent node proximity to the root.

Peer node sets the closest parent node to root as its parent (see Fig. 6).

Fig: 6 A complite spanning tree among AOI neighbors

## 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

Voronoi-related definitionsSite: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 withnsites intonareas 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.## VON Procedures

Node definitionsJoining 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

sends a join request with its coordinates to any existing node (which can be theJoining node).gateway server(i.e. the node whose region contains the joining node’s coordinates) by greedy forward (see Fig. 1a).acceptorconnects to each neighbor on the list ※.Joining nodebuilds up a Voronoi diagram of itsJoining nodewhile the contacted nodes update their Voronoi diagrams to accommodate theAOI neighbors(see Fig. 1b).joining node## MOVE Procedure

sends position updates to all connected neighbors.Moving nodechecks if any of its ownBoundary neighborhas entered the moving node’s AOI (see Fig. 2a) or if theenclosing neighborshas any newmoving node. If so then it sends a notification.enclosing neighboris discovered, theAOI neighborconnects to it ※.moving nodedisconnects anyMoving nodethat has left its AOI (see Fig. 2b).boundary neighbor## LEAVE Procedure

simply disconnects (there is no distinction between proper and abnormal departures from the overlay network, see Fig. 3a).Leaving nodeleaves, replacements are learned via still-connectedboundary neighbor(see Fig. 3b).boundary neighbors## VSO Procedures

## VoroCast Procedures

Node definitionsRoot 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

updates its AOI with the enclosing and boundary neighbors.Root nodesends the messages to its enclosing neighbors with a spanning tree diffusion (see Fig. 4).Root nodeParent node procedureselects peer nodes as possibles child nodes.Parent nodesends requests to its enclosing peer nodes to be child nodes (see Fig. 5).Parent nodeforwards the messages to its child nodes.Parent nodePeer node procedurereceives requests to accept a parent node.Peer nodeevaluates parent node proximity to the root.Peer nodesets the closest parent node to root as its parent (see Fig. 6).Peer node