BATON Overlay

This article has multiple issues. Please help or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (November 2018) (Learn how and when to remove this template message) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help by introducing citations to additional sources. Find sources:  –  ·  ·  · scholar · JSTOR (November 2018) This article contains content that is written like an advertisement. Please help by removing promotional content and inappropriate external links, and by adding encyclopedic content written from a neutral point of view. (November 2018) (Learn how and when to remove this template message) The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources:  –  ·  ·  · scholar · JSTOR (November 2018) (Learn how and when to remove this template message) (Learn how and when to remove this template message)

The BAlanced Tree Over-lay Network (BATON) is a distributed tree structure for peer-to-peer (P2P) systems. Different from other overlays that use a distributed hash table (DHT), such as in the Chord system, BATON organizes peers in a distributed tree to support range search. In addition, BATON tries to keep the tree height-balanced, similar to the AVL tree. And hence, the search exact and range queries cost is bounded to ${\displaystyle O(\log N)}$, such as the cost for an update operation (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:

1. a link to its parent node (unless it is root)
2. links up to two-children nodes
3. a link to left and right adjacent node
4. links to select neighbor nodes maintained in a left routing table (LRT) and right routing table (RRT). Combining these, the routing table is created ${\displaystyle 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 ${\displaystyle p}$, it will fill its left routing table by nodes at position ${\displaystyle p-2^{x}}$ for any valid ${\displaystyle x\geq 0}$ and fill its right routing table by nodes at position ${\displaystyle p+2^{y}}$ for any valid ${\displaystyle 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 balanced if and only if at any node in the tree, the height of its two sub-trees differ by at most one. If any node detects that the tree validates the height-balanced constraint, a restructuring is initiated.

Node Joining and Leaving[]

The new node's joining request will always be forwarded to the leaf node. The leaf node will check to see whether the routing table is full. If the routing table is full, this level is full of nodes and the leaf node can accept the new node as its child to create a new level node. Otherwise, it must forward the new node to take over one of the empty positions.

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 this node is a leaf node, it can leave the network safely. Otherwise, it must find a leaf node to replace its position.

Routing[]

In BATON, each node maintains a continuous key space. Once a new node joins as its child, it splits its space and assigns half of it to the child. In this partition way, if we travel the tree in in-order, we can search the whole space in ascendant order. That's why BATON supports range queries.

For a range query q, BATON first locats its left bound, q.low. And then the search process will travel the tree in in-order (by adjacent link), until reach the upper bound, q.up. For locating a single key, BATON performs the similar routing strategy as Chord. First, the request is routed to the farthest routing nodes which does not over hit 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, suppose that this restructuring is towards the right. Assume 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,

1. If its left or right adjacent node is light loaded, the node will transfer some data to the adjacent node to lower its load
2. 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.

See also[]

• Chord
• CAN
• Pastry

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.

Further reading[]

• H. V. Jagadish; Beng Chin Ooi; Quang Hieu Vu; Rong Zhang & Aoying Zhou (2006). "VBI-Tree: A Peer-to-Peer Framework for Supporting Multi-Dimensional Indexing Schemes" (PDF). Proceedings of the 22nd International Conference on Data Engineering. p. 34. ISBN 0-7695-2570-9.
• H. V. Jagadish; Beng Chin Ooi; Kian-Lee Tan; Quang Hieu Vu & Rong Zhang (2006). "Speeding up search in peer-to-peer networks with a multi-way tree structure" (PDF). Proceedings of the 2006 ACM SIGMOD international conference on Management of data. pp. 1–12. ISBN 1-59593-434-0.
• Shiyuan Wang; Beng Chin Ooi; Tung, A.K.H. & Lizhen Xu (2007). "Efficient Skyline Query Processing on Peer-to-Peer Networks" (PDF). Proceedings of the 22nd International Conference on Data Engineering. pp. 1126–1135. ISBN 1-4244-0803-2.
• A. Gonzalez-Beltran; P. Milligan & P. Sage (2008). "Range queries over skip tree graphs" (PDF). Computer Communications. pp. 358–374. ISSN 0140-3664.
• Peter Detzner; Jana Gödeke & Steffen Bondorf (2021). "Low-Cost Search in Tree-Structured P2P Overlays: The Null-Balance Benefit" (link). 46th Conference on Local Computer Networks (LCN). pp. 358–374.

External links[]

• Website of BestPeer Project