« [P2P]ブラウザだけで分散ハッシュテーブル(DHT)を体感しよう! | トップページ | ソーシャルブックマーク(SBM)勉強会の準備を開始します »

2007.04.08

[P2P]ノード数と最大ホップ数の関係~その1

DHTの研究をしていくと、平均ホップ数や最大ホップ数を気にするようになります。すると、平均ホップ数や最大ホップ数はどこまで改善できるようになるのか、一度は考えて見たかたもいると思います。実は私もその一人です。

そこで、今回はノード数と最大ホップ数の一般的な関係について考えてみましょう。

以下の問題について考えてみてください。答えは近日中に公表します。解答案を作った方は是非トラックバック等をしてくださいね。

□問題
Pure P2Pに参加しているノード群を考えてみる。各ノードは一定の数のリンクを持っている。1ノードあたりのリンク数をPとする。またノードの総数はNとする。ノードがホップできる先はリンクしているノードに限られるとする。このとき、最大ホップ数はN,Pをつかってどのような関係にあるのか示してください。なお、任意の2ノード間はリンクにより辿り着くことができることとする。

P2Pは複雑ネットワークやグラフ理論と深い結びつきがありますが、今回の問題はグラフ理論の応用です。グラフ理論でいうと、リンク数は「次数」、最大ホップ数は「直径」に相当します。任意の2ノード間がリンクを使って辿れる事は連結グラフに相当します。
実を言うと、考えやすいように今回の問題は次数が一定=Pの場合を書いていますが、次数が一定でなくてもノードにおける最大次数がPの場合も答えは同じになります。もちろん、Structured P2PでもUnstructured P2Pでも当てはまる関係式となります。

是非チャレンジしてみてくださいね。

|

« [P2P]ブラウザだけで分散ハッシュテーブル(DHT)を体感しよう! | トップページ | ソーシャルブックマーク(SBM)勉強会の準備を開始します »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/14596644

この記事へのトラックバック一覧です: [P2P]ノード数と最大ホップ数の関係~その1:

« [P2P]ブラウザだけで分散ハッシュテーブル(DHT)を体感しよう! | トップページ | ソーシャルブックマーク(SBM)勉強会の準備を開始します »