BATON Overlay - Routing

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.