BATON Overlay

The BAlanced Tree Overlay Network (BATON) is a distributed tree structure designed for peer-to-peer (P2P) systems. Unlike other overlays that employ a distributed hash table, BATON organises peers in a distributed tree to facilitate range search. BATON aims to maintain a balanced tree height, similar to the AVL tree, resulting in a bounded to $O(\log N)$ for search exact and range queries as well as update operations (join/leave).

System model

Exemplary BATON tree structure

BATON is a binary tree. In each tree level, the node is named by its position in the tree.

Each node in BATON keeps four kinds of links:

a link to its parent node (unless it is root)
links up to two-children nodes
a link to left and right adjacent node
links to select neighbor nodes maintained in a left routing table (LRT) and right routing table (RRT). Combining these, the routing table is created $RT:={LRT}\cup {RRT}$

The level of any node is one greater than the level of its parent. Root is on level 0. For a node at position $p$ , it will fill its left routing table by nodes at position $p-2^{x}$ for any valid $x\geq 0$ and fill its right routing table by nodes at position $p+2^{y}$ for any valid $y\geq 0$ . The construction of the routing table has slight resemblance to the finger tables in Chord.

So according to the example structure, node 2:1 would keep links to

1:0 (parent)
3:2 (children)
0:0 and 3:2 (adjacent)
2:0, 2:2 and 2:3 (neighbors)

Height-Balanced

BATON is considered balanced if and only if the height of its two sub-trees at any node in the tree differs by at most one. If any node detects that the height-balanced constraint is violated, a restructuring process is initiated to ensure that the tree remains balanced.

Node joining and leaving

When a new node wants to join the network in BATON, its joining request is always forwarded to the leaf node. The leaf node then checks whether its routing table is full. If the table is full, it means that the level is full of nodes, and the leaf node can accept the new node as its child to create a new level node. If the table is not full, the leaf node must forward the new node to take over one of the empty positions.

On the other hand, when a node wants to leave the network, it must update the routing tables of its parent node, child nodes, adjacent nodes, and routing nodes. If the leaving node is a leaf node, it can safely leave the network. However, if it is not a leaf node, it must find a leaf node to replace its position.

Routing

In BATON, each node maintains a continuous key space. When a new node joins as its child, the node splits its space and assigns half of it to the child. This partitioning method allows the tree to be traversed in ascending order if we travel the tree in in-order. This is why BATON supports range queries.

To execute a range query q, BATON first locates its left bound, q.low. Then, the search process travels the tree in in-order (by adjacent link) until it reaches the upper bound, q.up. For locating a single key, BATON uses a similar routing strategy as Chord. The request is first routed to the farthest routing node that does not overshoot the key. If no such routing nodes exist, the parent link, child link, or adjacent link is used.

Restructure

When a node x accepts a joining node y as its child and detects that the tree balance is violated, it initiates the restructuring process. Without loss of generality, let's assume that this restructuring is towards the right. Suppose that y joins as x's left child. To rebalance the system, x notifies y to replace its position and notifies its right adjacent node z that x will replace z's position. Z then checks its right adjacent node t to see if its left child is empty. If it is, and adding a child to t does not affect the tree balance, z takes the position of t's left child as its new position, and the restructuring process stops. If t's left child is full or t cannot accept x as its left child without violating the balance property, z occupies t's position, while t needs to find a new position for itself by continuing to its right adjacent node.

Load balancing

BATON adopts two kinds of load balancing strategy. Once a node n detects that it is over loaded,

If its left or right adjacent node is light loaded, the node will transfer some data to the adjacent node to lower its load
If its adjacent nodes are not capable to share the load, the node will invoke a process to find a randomly light loaded node in the network. The light loaded node leaves its original position and joins as the child of the overloaded node to take over part of its data. The restructure process may be invoked.

BATON extensions

BATON* - BAlanced m-ary Tree Overlay Network: A height-balanced m-ary search tree extension of BATON with further links for efficiency, fault-tolerance, and load-balancing.
nBATON* - null-BAlanced m-ary Tree Overlay Network: A null-balancey m-ary search tree extension of BATON* with up to 50% better performance w.r.t. required routing hops.

References

H. V. Jagadish; Beng Chin Ooi & Quang Hieu Vu (2005). "BATON: a balanced tree structure for peer-to-peer networks" (PDF). Proceedings of the 31st international conference on Very large data bases, Trondheim, Norway. pp. 661–672. ISBN 1-59593-154-6.

External links

Website of BestPeer Project