一定次数のオーバレイネットワークにおける最適経路長の経路決定方法の考察

URI http://harp.lib.hiroshima-u.ac.jp/hiroshima-cu/metadata/5523
ファイル
タイトル
一定次数のオーバレイネットワークにおける最適経路長の経路決定方法の考察
別タイトル
A Study of Optimal Path Routing in Constant Degree Overlay Network
著者
氏名 島 和之
ヨミ シマ カズユキ
別名 SHIMA Kazuyuki
氏名 松尾 浩平
ヨミ マツオ コウヘイ
別名 MATSUO Kohhei
氏名 大場 充
ヨミ オオバ ミツル
別名 OHBA Mitsuru
氏名 佐藤 康臣
ヨミ サトウ ヤスオミ
別名 SATO Yasuomi
氏名 清水 將吾
ヨミ シミズ ショウゴ
別名 SHIMIZU Shogo
抄録

分散ハッシュ表(DHT)のためのオーバレイネットワーク,および,その上で最適な経路を求める方法を提案する.DHTは,P2P型システムのような分散システムにおいて,リソースを効率的に検索するための仕組みである.提案するオーバレイネットワークについて確率論的な評価を行い,平均的な次数がノード数によらず一定であること,および,ノード数nに対して経路長がO(log n)となることを示した.次数が一定であることから,ノード数が多い場合でも,ノードの参加や離脱のとき,隣接ノードを更新するための負荷が高くならず,スケーラブルなシステムを構築できると考えられる.また,従来手法の経路長はO(log n)以上であることから,提案手法の経路長は最適であり,従来と同等以下の時間でリソースを検索できると考えられる. / We propose an overlay network for Distributed Hash Table (DHT) and an optimal path routing in the overlay network. DHTs are mechanisms to efficiently locate nodes that provide a particular resource in distributed systems such as peer-to-peer (P2P) systems. Probabilistic evaluation of the proposed overlay network shows the expected degree is constant not depending on the number of nodes, and the expected path length is O(log n) where the number of nodes is n. The proposed overlay network is scalable, that is, the load of updating neighbors does not become high when the number of nodes becomes large because the degree is constant. The proposed routing can locate nodes within time equals to or shorter than previous works, that is, the path length of the proposed routing is optimal because the path lengths of previous works are not less than O(log n).

査読の有無
掲載雑誌名
情報処理学会論文誌
48
2
開始ページ
422
終了ページ
433
出版年月日
2007-02-15
出版者
社団法人情報処理学会
ISSN
0387-5806
NCID
AN00116647
NAID
110006207767
本文言語
日本語
資料タイプ
学術雑誌論文
著者版フラグ
出版社版
権利情報
ここに掲載した著作物の利用に関する注意:本著作物の著作権は(社)情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 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. All Rights Reserved, Copyright (C) Information Processing Society of Japan.
本文データは学協会の許諾に基づきCiNiiから複製したものである
関連情報
isVersionOf:http://ci.nii.ac.jp/naid/110006207767
関連URL
旧URI
区分
hiroshima-cu