Towards Robust Routing in HD Tree

The Hierarchically Distributed Tree (HD Tree) [1, 2] is a new data structure within distributed environment. It is designed to better preserve data locality when the number of nodes in a tree grows exponentially. By adding extra links to a corresponding complete tree, multiple routing paths are available between each pair of tree nodes. Therefore the routing strategy for HD Tree could be designed to be highly flexible and error resilient. The routing traffic can be controlled dynamically, making the traffic load balanced among all the nodes. However, within an HD Tree, there are some nodes, which we name SPeers, that are different from the others. They have less connected neighbours. Furthermore, every SPeer has only one parent and in the case of parent node failure, a leaf SPeer node could be isolated from the system. Therefore, a new method by which to connect all the SPeers is needed. In this paper, we propose to enhance further the performance of our HD-Tree. We present a new routing strategy, in order to make the routing among the SPeer nodes more error-resilient when compared to our previous work. This strategy could be used as an alternative approach to previously developed algorithms. In addition, it is proven that when combined with other strategies, it will achieve better routing performance.