提供: Research



呉承彦, 安倍広多, 石橋勇人, 松浦敏雄, P2Pネットワークにおける経路長あるいは経路表サイズの最大値を柔軟に設定可能な経路表構築方式の提案とその評価,電子情報通信学会論文誌 B, Vol. J97-B, No. 10, pp. 849-860, (2014-10).


構造化P2Pネットワークでは,各ノードが保持する経路表を用いてルーティングを行い宛先ノードに到達する.既存の多くの構造化P2Pネットワークでは,経路長はノード数nに対してO(logk n)であるが,対数の底kはP2Pネットワークの運用中に変更できるものは知られていない.本稿では,構造化P2Pネットワークの1つであるChord#の経路表(finger table)を拡張することでkの値を動的に変更可能な経路表構築手法を提案する.また,拡張したfinger tableを用いて,最大経路長が指定した任意の値を上回らないようにする方式(経路長優先方式)と,経路表サイズを指定した任意の値とする方式(経路表サイズ優先方式)を実現した.これらの方式により,定数ホップおよび対数ホップルーティングが可能である. 提案手法の有効性はシミュレーションにより確認した.

In a structured P2P network, each node has its own routing table and locates another node using the table. Considering most of the existing structured P2P networks, the number of routing hops is O(logk n) where n is the number of nodes in the network. To the best of our knowledge, there are no such algorithms that allow to change the value of k, the base of logarithm in the above expression, of working networks.

This paper describes a construction method of routing tables with adjustable k by extending the finger table of Chord#, one of the structured P2P networks. The following two methods are introduced: 1) keeping the number of routing hops under an arbitrary constant, 2) keeping the size of routing table an arbitrary constant.

As a result, the proposed algorithm is able to handle not only constant hop routing but also logarithmic hop routing. Effectiveness of the method is confirmed by simulation experiments.