Kademlia

Kademliaは Petar Maymounkov、Ben Jonston、Perry StillerおよびDavid Mazieresにより設計せっけいされた分散ぶんさん ピアツーピアコンピュータネットワークのための分散ぶんさんハッシュテーブルである。Kademliaはネットワーク構造こうぞうおよびノード検索けんさくによる情報じょうほうの送受信そうじゅしんを規定きていしている。KademliaのノードはUDPにより相互そうごに通信つうしんを行おこなう。 参加さんかノードにより仮想かそう的てきなオーバーレイ・ネットワークが形成けいせいされる。各かくノードはノードIDと呼よばれる番号ばんごうで管理かんりされている。ノードIDはノードの識別しきべつに用もちいるだけでなく、KademliaアルゴリズムではノードIDにより値ねを抽出ちゅうしゅつするために使つかわれる。この値ねは通常つうじょうファイルのハッシュ値ちやキーワードである。実際じっさいには、ノードIDはファイルハッシュへの直接的ちょくせつてきなマッピングを与あたえ、そのノードはファイルやリソースを取得しゅとくする対象たいしょう

ある値ねを検索けんさくする際さい、このアルゴリズムではそれに割わり当あてられたキーの情報じょうほうが必要ひつようとなり、ネットワークを数すうステップかけて探索たんさくする。各かくステップにおいて、よりキーに近ちかいノードが発見はっけんされ、最終さいしゅう的てきに該当がいとうするノードが値ねを返かえすか、それ以上いじょう近ちかいノードがない状態じょうたいとなる。これは非常ひじょうに効率こうりつが良よく、他たの多おおくの分散ぶんさんハッシュテーブルのようにKademliaは$n$ノードのシステムにおいて検索けんさくの間あいだに合計ごうけい$O(\log(n))$ノードへの通信つうしんを行おこなう。(ランダウの記号きごう参照さんしょう)

分散ぶんさん化かされた構造こうぞうにはDoS攻撃こうげきに対たいする耐たい性せいが明確めいかくに向上こうじょうするという利点りてんがある。たとえあるノード集合しゅうごうへのアクセスが飽和ほうわしても、ネットワーク全体ぜんたいの可用性かようせいに及およぼす影響えいきょうは限定げんてい的てきであり、これらの「穴あな」を避さけてネットワークが回復かいふくされる。

関連かんれん項目こうもく

• Content addressable network
• Chord
• Tapestry (DHT)
• Pastry (DHT)
• Koorde
• InterPlanetary File System

外部がいぶリンク

• Petar Maymounkov's Academic Home Page
• Kademlia Specification : http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html
• Yi Qiao and Fabian E. Bustamante USENIX 2006 paper that characterizes Overnet and Gnutella

• Template:Cite web
• Russian site about Kad Network
• Brunet