An Efficient Routing Method for Range Queries in Skip Graph

Ryohei BANNO  Kazuyuki SHUDO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.3   pp.516-525
Publication Date: 2020/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019FCP0008
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Category: 
Keyword: 
Skip Graph,  overlay networks,  peer-to-peer networks,  routing algorithms,  distributed algorithms,  

Full Text: PDF>>
Buy this Article




Summary: 
Skip Graph is a promising distributed data structure for large scale systems and known for its capability of range queries. Although several methods of routing range queries in Skip Graph have been proposed, they have inefficiencies such as a long path length or a large number of messages. In this paper, we propose a novel routing method for range queries named Split-Forward Broadcasting (SFB). SFB introduces a divide-and-conquer approach, enabling nodes to make full use of their routing tables to forward a range query. It brings about a shorter average path length than existing methods, as well as a smaller number of messages by avoiding duplicate transmission. We clarify the characteristics and effectiveness of SFB through both analytical and experimental comparisons. The results show that SFB can reduce the average path length roughly 30% or more compared with a state-of-the-art method.