距離が付加された要素集合をコンパクトに表現できるDistance Bloom Filterの提案とP2Pネットワークにおける最短経路探索への応用

提供: Research

目次

書誌情報

西川大器,安倍広多,石橋勇人,松浦敏雄,距離が付加された要素集合をコンパクトに表現できるDistance Bloom Filterの提案とP2Pネットワークにおける最短経路探索への応用,情報処理学会研究報告,Vol. 2012-IOT-16, No. 4, pp. 1--8 (2012-3)

Abstract

P2P ネットワークにおいて重要な機能の1つは,あるデータを検索し,そのデータを持つノードを特定することである.この際,目的のノードに到達するまでの遅延時間をできるだけ小さくできることが望ましいが,従来の多くの手法では,局所的な情報のみを利用して経路を決定するため,必ずしも最短経路が選ばれるわけではない.この問題を解決するため,本稿では,経路ごとの遅延時間を空間効率良く保持できるデータ構造である Distance Bloom Filter,ならびに,これを用いて高い確率で最短経路を選択可能な手法を提案する.また,提案手法を構造化 P2P ネットワークの1つである Skip graph に適用したシミュレーションを行い,その有効性を確認した.

One of the key functions of P2P networks is locating a node that stores target data. This is performed by routing a search message with the key corresponding to the data over the overlay network. Minimizing the latency of this process is not fully achieved by most P2P systems since they only use local information to determine the route. This paper proposes a novel routing method for P2P systems that finds the shortest path to the destination with high probability. Distance Bloom Filter as a space-efficient data structure to store distance information is introduced to support the method. Simulation results of the method applied to skip graphs, a structured P2P network, are also reported.

論文

ここに掲載した著作物の利用に関する注意 本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。

Notice for the use of this material The copyright of this material is retained by the Information Processing Society of Japan (IPSJ). This material is published on this web site with the agreement of the author (s) and the IPSJ. Please be complied with Copyright Law of Japan and the Code of Ethics of the IPSJ if any users wish to reproduce, make derivative work, distribute or make available to the public any part or whole thereof.

プレゼンテーション


個人用ツール