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

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

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

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

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

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

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