Chord#における経路表の維持管理コスト削減手法

書誌情報

呉承彦，安倍広多，石橋勇人，松浦敏雄，Chord#における経路表の維持管理コスト削減手法，情報処理学会第19回 マルチメディア通信と分散処理ワークショップ (DPSWS2011) 論文集，pp.250–256, (2011-10).

Abstract

Chord# は構造化P2P(Peer-to-Peer)ネットワークの一種である．Chordなどの分散ハッシュテーブルに基づくシステムとは異なり，キーの範囲検索が可能な点に特徴がある． Chord# ではショートカットリンク(finger table)を用いることでノード数nに対して，O(log n)ホップで検索が可能である． Chord# のfinger tableは，ノードの挿入や削除，障害に対応するために定期的に更新する必要があるが，本稿ではこの更新処理のコストを削減する方式を提案する． 提案手法では，finger tableを2次元配列に拡張した上で，隣接するノードのfinger tableが類似していることを利用して更新処理のコストを削減する． シミュレーションによりfinger tableの更新処理コストを削減できることを確認した．

Chord# is a kind of structured Peer-to-Peer (P2P) network. Unlike those systems based on distributed hash tables (DHT) such as Chord, Chord# is able to handle range queries. Chord# achieves O(log n) search hops, where n denotes the number of nodes, by using a finger table, a collection of short cut links. A finger table of Chord# must be periodically updated to catch up node insertion, deletion and failure. In this paper, we propose a method to reduce the cost of updating finger tables. In the proposed method, a finger table is extended to two-dimensional array and the cost of updating finger tables is reduced by using the similarity of finger tables of adjacent nodes. We have simulated the algorithm and confirmed that the cost of updating finger tables is actually reduced.

論文

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

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.

プレゼンテーション

賞

  • 賞1
  • 賞2