Suzaku: A Churn Resilient and Lookup-Efficient Key-Order Preserving Structured Overlay Network

Kota ABE  Yuuichi TERANISHI  

IEICE TRANSACTIONS on Communications   Vol.E102-B   No.9   pp.1885-1894
Publication Date: 2019/09/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2018EBT0001
Type of Manuscript: PAPER
Category: Network
peer-to-peer systems,  key-order preserving structured overlay network,  churn resilience,  

Full Text: PDF(2.7MB)>>
Buy this Article

A key-order preserving structured overlay network is a class of structured overlay network that preserves, in its structure, the order of keys to support efficient range queries. This paper presents a novel key-order preserving structured overlay network “<I>Suzaku</I>”. Similar to the conventional Chord#, Suzaku uses a periodically updated finger table as a routing table, but extends its uni-directional finger table to bi-directional, which achieves ⌈log2 n⌉-1 maximum lookup hops in the converged state. Suzaku introduces active and passive bi-directional finger table update algorithms for node insertion and deletion. This method maintains good lookup performance (lookup hops increase nearly logarithmically against n) even in churn situations. As well as its good performance, the algorithms of Suzaku are simple and easy to implement. This paper describes the principles of Suzaku, followed by simulation evaluations, in which it showed better performance than the conventional networks, Chord# and Skip Graph.