For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Routing Method for Range Queries in Skip Graph
Ryohei BANNO Kazuyuki SHUDO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2020/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Skip Graph, overlay networks, peer-to-peer networks, routing algorithms, distributed algorithms,
Full Text: PDF(1.3MB)>>
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.