Voronoi Self-organizing Overlay (VSO)

VSO is an extension to VON that allows the dynamic load balancing of Voronoi regions so that a single VON node will not be overloaded due to handling too much traffic or processing.

The basic idea is that assuming the size of a Voronoi region handled by a VON node roughly equals its workload, then by adjusting the region size and shape (which can be done easily by moving the Voronoi sites), region load can be balanced. Voronoi partitioning is used as it may produces smaller number of partitions given a clustered distribution of loading. See below for a comparison between quad-tree-based partitioning and Voronoi partitioning (i.e., for the same 50 entities, quad-tree produces 10 regions while Voronoi produces only 6, assuming each node handles 10 entities maximally). This means that fewer resources need to be provisioned (e.g., cloud-based servers or super-peers in P2P networks).

Comparison between quad-tree and Voronoi partitioning methods, given 50 entities.

Given that some objective load indicator exists for a VON node, the adjustment rules are:
  1. Shrink region size when overloaded by asking neighbors to move their sites closer.
  2. Request a new node insertion from a gateway, if 1) does not work after a while.
  3. A node may leave the system if it is underloaded for some period.

Below is a video demonstration of VSO (to load balance 100 entities in motion). Note that the lines are the Voronoi partitioning of regions, and each region is handled by a VON node.

Video Demo

For more information, please refer to VSO's research publications