MARIF: Multiple Queries Look-Up Architecture Using Range Information Feedback in a DHT Network

Kimihiro MIZUTANI  Toru MANO  Osamu AKASHI  Kensuke FUKUDA  

Publication
IEICE TRANSACTIONS on Communications   Vol.E96-B   No.7   pp.1680-1690
Publication Date: 2013/07/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.1680
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Internet Architectures, Protocols, and Management Methods that Enable Sustainable Development)
Category: 
Keyword: 
structured overlay network,  P2P,  DHT,  query reduction,  

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




Summary: 
In DHT network, a node can get/put a requested data by only log N look-up steps. However, conventional DHT network only supports single query look-up to search data. From the reason, each node in a DHT network must execute look-up process for each query even if a large number of put and get operations are executed. Therefore, this results in high network load in massive data management such as MapReduce, sensor network, and web information. To address the problem, we propose multiple queries look-up architecture using range information feedback (MARIF). MARIF extends the conventional KBR protocol to supports range information that is a scope of ID space a node keeps. When a source node receives range information from a destination node, the source node checks all queries in the range information and forwards queries matching the range information to the destination node directly. This effectively reduces the number of look-up queries and the network load for the IP network. In addition, MARIF can be implemented into conventional DHT networks and can easily be combined to effective DHT routing algorithms such as Chord, Kademlia, Pastry, and one-hop DHT. In evaluation, we implement MARIF into three DHT networks and compare its performance with that of conventional query bundling mechanisms based on the KBR protocol. The results show that MARIF reduces by up to 40% the total number of forwarding queries to put data compared with other mechanisms. In addition, MARIF saves the number of forwarding queries per look-up process by up to 85% compared to other mechanisms with low bundling overhead.