|
Overview Demo Downloads
Documentation
Contributors
|
VON Procedures
(PDF version)
(a) (b) (a) Dots indicate sites, and lines define boundaries (edges) for regions. (b) 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. 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. 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 authority that assigns unique ID for each node in 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. Procedures JOIN procedure 1. Joining node contacts the gateway server for a unique ID. 2. Joining node sends a join request with its coordinates to any existing node (which can be the gateway server). 3. Join request is forwarded to the acceptor (i.e. the node whose region contains the joining node’s coordinates) by greedy forward (see Fig. 2a). 4. Acceptor responds by sending a list of joining node’s AOI and enclosing neighbors. 5. Joining node connects to each neighbor on the list*. 6. 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. 2b).
(a) (b) Figure 2: 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. 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. 3a) 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. 3b). 5. All nodes update their Voronoi diagrams to reflect the current topology at each step.
(a) (b) Figure 3: 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. 1. Leaving node simply disconnects (there is no distinction between proper and abnormal departures from the overlay network, see Fig. 4a). 2. Affected neighboring nodes update their Voronoi. If a boundary neighbor leaves, replacements are learned via still-connected boundary neighbors (see Fig. 4b).
(a) (b) Figure 4: 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 ▓).
* 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.
any questions/comments/inquiries? please contact us
Copyright © 2005-2025, VAST Development Team Last modified: March 03 2006.
|
