日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

二次元平面上の P2P オーバレイネットワークにおける経路表の順序関係に基づいたルーティング手法
北條 真史

長尾 洋也

宮尾 武裕

首藤 一幸

二次元平面上のノード群で，ドロネー図をトポロジとする P2P オーバレイネットワークを構成する方法が提案されてきた．我々は，この二次元平面上の P2P ネットワークでの柔軟な経路表 (FRT) の考えを用いた経路表構築手法を提案する．FRT を用いることで，経路表サイズの動的な調整が可能となり，ルーティング時に様々な指標を考慮するための拡張性が得られる．また，経路表サイズがネットワークに参加しているノード数よりも大きいとき，何の切り替えも必要とせずにシングルホップ動作を行うことができる．我々が提案する FRT に基づく二次元平面上のルーティング方式は，ノード間のユークリッド距離に注目し，経路長の削減を目的とした経路表構築を行う．我々は提案方式を Overlay Weaver 上に実装し，シミュレーションによる評価を行った．この提案方式が経路長削減に関して有効であることや，シングルホップ動作とマルチホップ動作の一貫した管理が可能であることを確認した．

ロネーネットワーク [4] を用いた際の FRT に基づく

1 はじめにルーティング方式を提案する．

オーバレイネットワークとは，実ネットワーク上の二次元平面上の P2P ネットワークは実空間での計算機群で形成するアプリケーション層のネットワー

位置情報を用いる際などに有用である．今回はまず，クである．オーバレイネットワークはアプリケーショノードが平面上に均一に配置されている仮定の上でンの要請に基づいて実ネットワークとは異なるトポFRT に基づくルーティング方式を提案する．今後，ロジをとるので，計算機群が直接的な通信を行うこ無線ネットワークなどで見られるような，ノードの配とができる．このため，非集中でスケーラビリティや置に偏りがあり，通信可能な相手ノードが限られる実対故障性に優れた Peer-to-Peer (P2P) システムを構地での方式を検討していく．

築する試みが広く行われている．今日，様々なトポロジを用いて P2P オーバレイネットワークを構築す

2 関連研究る手法が考案されており，これらのネットワーク上で

2. 1 P2P ドロネーネットワーク

メッセージをルーティングする手法も数多く存在してP2P ドロネーネットワーク [4] は，計算幾何分野でいる．

知られるドロネー図を利用した P2P オーバレイネッ

我々は，ルーティングアルゴリズムの設計方法論、トワークである．ドロネー図は，空間上に散布された柔軟な経路表（Flexible Routing Tables, FRT） [3]点 (母点と呼ぶ) を特定の条件によって辺で結ぶことを提案しており，これに基づいて，既存・新規のルーによって構成されるものであり，各母点をノード，各ティングアルゴリズムの記述を試みている．本研究

辺を通信経路と見なしたものが P2P ドロネーネット

では，FRT の新たな試みとして，二次元の P2P ドワークである．P2P ドロネーネットワークは以下のA Routing Algorithm on Two-Dimensional Surface
Based on an Order of Routing Tables
Masashi Hojo, Hiroya Nagao, Takehiro Miyao,Kazuyuki Shudo, 東京工業大学, Tokyo Institute ofTechnology.

ような特徴を持つ．

• ドロネー図は連結グラフである．
• P2P ドロネーネットワークでは，ノードの管理領域を割り当てる際にボロノイ分割を利用する

それぞれ 2i (i ≥ 1) ホップ先のノードと LRC を形成し，遠隔ノードへのルーティングの際に短縮経路として用いる．
ホップ数に注目した LRC は，ノードが二次元平面に一様に分布していない場合でも経路長の削減に効果的であり，実空間上の座標を用いた P2P オーバレ
イネットワークなどでの利用が可能である．

2. 2 柔軟な経路表 (FRT)
柔軟な経路表 (Flexible Routing Tables, FRT) [3]
図1

二次元のドロネー図とボロノイ図

は，P2P オーバレイネットワークにおけるルーティングアルゴリズムの構成手法である．FRT に基づくアことができる．ボロノイ分割はドロネー図の各母ルゴリズムは，経路表間の優劣を表す順序関係 ≤ID

点とのユークリッド距離に基づいた領域分割でを定義し，それに従って経路表の改良を繰り返す．こある．の経路表構築手法により，経路表に追加するノード候• P2P ドロネーネットワークでは，ユークリッド距離に基づく greedy routing によって任意のノー補を限定することなくルーティング効率を向上させることができる．

ドから任意の目的地点の管理ノードに到達する

FRT における経路表管理の操作は次の 2 つである．

ことができる．

• エントリ学習操作

このような特徴により，P2P ドロネーネットワー

エントリ学習操作は経路表エントリを 1 つ増やクは多次元の空間をノード群で管理するような基盤す操作であり，通信などで知り得たノード情報をネットワークに適している．図 1 は二次元平面上で選別せずに経路表に追加する．のドロネー図の例である．

• エントリ厳選操作

2. 1. 1 自律分散生成アルゴリズム

エントリ厳選操作は経路表エントリ数が予め設定二次元平面において，P2P ドロネーネットワーク

されたサイズ L を超えたときに，ある指標に基を自律分散的に生成するアルゴリズムが提案されていづいて経路表エントリを 1 つ減らす操作である．

る [7]．この手法を用いると，各ノードが自身の近傍

FRT では，エントリ厳選操作における削除するエのノードとの接続関係を自律的に計算することによっントリの決定のために，経路表エントリに含まれるて，全体で P2P ドロネーネットワークを構成するこノード ID の組合せに基づき，経路表間の順序関係とが可能となる．ノードの参加や離脱のネットワーク≤ID を定義する．この順序関係に従った学習と厳選に与える影響がそのノード近傍のみにとどまるため，が繰り返されることで，よりよい経路表が構築されてネットワークの再構築やノードの担当領域の再計算にいく．

関して高いスケーラビリティを期待できる．

2. 1. 2 遠隔接続経路各ノードが自身の近傍との接続のみを持つ P2P ドロネーネットワークでは，遠隔ノードへのルーティン

FRT の利点には例えば以下の利点がある．
• 経路表サイズ L の動的な調整が可能である．Lはノードの性能や離脱頻度などに応じて変更されるものである．

グ時に経路長が大きくなる．そこで，各ノードが遠• シングルホップ動作とマルチホップ動作を一貫隔接続経路 (Long Range Contacts, LRC) を構成しして扱うアルゴリズム設計が可能である．ネット

経路長を削減する手法が提案されている [8]．この手ワークに参加するノード数 N が N ≤ L を満た

法では，各ノードが平面上の水平と垂直の 4 方向です際には，エントリ学習操作が繰り返されること

で経路表に全ノードを加えることができるため，ことで，効果的に経路長を削減する方法を述べていシングルホップ動作を実現する．N > L となるる．その確率分布が c/d(s, ei )r であり，r の値を調節ときはマルチホップ動作となり，エントリ厳選操することでその効率が変わる．今回は，FRT に基づ作によって性能向上を図る．

くアルゴリズムの 1 つである FRT-Chord [3] と類似• FRT に基づくアルゴリズムは拡張しやすく，した計算を行うことを考えて r = 1 とした．

様々な 指 標 を 考 慮す る こ と が 可 能 で あ る ．例と し て ，ノ ー ド ID に 加 え て 通 信 遅 延 を 考 慮

3. 2 経路表間順序関係 ≤IDした Proximity-aware Flexible Routing Tables

前述の要件を満たす経路表構築を行うために，経路(PFRT) [2] や，グループ間通信の削減を考慮した Grouped Flexible Routing Tables (GFRT)

表 E に関して以下のような確率を考える．

PiE (x)[3] が提案されている．

3 FRT に基づく二次元平面上のルーティン=

P (d(s, ei−1 ) ≤ x ≤ d(s, ei ))=F (d(s, ei )) − F (d(s, ei−1 )∼log d(s, ei ) − log d(s, ei−1 ) (1)提案方式では， (1) の確率を総ての 2 ≤ i ≤ |E| でグ方式等しくなるようにすることで，前述の確率分布に従3. 1 概要う経路表構築を行う．このとき経路表間順序関係は，2. 1. 2 節の二次元 P2P ドロネーネットワーク上でE≤ID F のとき E よりも F の各エントリのほうが，の経路長短縮の手法は，経路表に追加するべきエントリをホップ数や方向から厳密に計算している．この方式はマルチホップ動作を前提とし，通信遅延など，経路長の削減以外のルーティング効率を考慮することが難しい．そこで我々は，二次元 P2P ドロネーネッ(1) の確率が均一であると定義することができる．
提案方式の厳選操作では，以下の基準に従ってエントリの削除を行う．

E≤ID F ⇔≤トワーク上のショートカットリンク生成に FRT の考えを導入する．

min(2≤i≤|E|−1min2≤i≤|F |−1)

EPi−1(x) + PiE (x)()

F
Pi−1(x) + PiF (x)この基準に従った厳選操作では，各エントリ ei につ

二次元平面上で経路表間順序関係 ≤ID を考案する

いて P (d(s, ei−1 ) ≤ x ≤ d(s, ei+1 )) を計算し，これに当たって，ここでは各ノードがハッシュ函数などが最小のものを削除する．この操作が繰り返されるこを用いて計算したランダムな ID を座標として用い，とで (1) の確率が均一化される．

ノード群が二次元平面上に一様に配置されていることを想定する．このような条件の下で，ショートカッ

4 評価

トリンク用の経路表 E = {ei | i ≥ 1} (ei は経路表エ

提案方式の狙いは，FRT の経路表構築による経路ントリ) を以下の要件を満たすように構築する．

1. 経路表は自ノード s と各 ei とのユークリッド距
離 d(s, ei ) に基づいて昇順に整列される．

長の削減と，シングルホップ動作とマルチホップ動作のシームレスな切替えの実現である．これらが達成されることを確認するため，オーバレイネットワーク構

2. エントリ ei は，c/d(s, ei ) という確率に従って築ツールキットである Overlay Weaver [5] [6] 上に提経路表に分布する．c は確率の和を 1 にするため案方式を実装し，シミュレーションにより評価実験をの定数である．

行った．実験環境は以下の通りである．

3. ショートカットリンクを構成するノードの方向はランダムに決定する．
これらの条件の内 2 は，Small-World 現象に関す• Overlay Weaver 0.10.4• OS Windows 7 64bit• CPU Intel Core i7-3612QM 2.10 GHz

る研究 [1] を参考にしている． [1] では，自身との距離• メモリ 8.00 GBに関する確率分布に従って経路表エントリを決定する• Java SE 7 Update 21

図2

エントリ学習・厳選の進行にともなう平均経路長

4. 1 経路表の改良に関する実験

4. 2 シングルホップ動作に関する実験

全ノードをネットワークに参加させて P2P ドロ

4. 1 節と同様の実験において N ≤ L を満たす際にネーネットワークを構築したのち，ランダムに選択は，ネットワーク上の総てのノードを経路表に載せらしたノードからランダムに選択した ID への探索を行れるため，経路長を 1 とするシングルホップ動作が実い，その際に通信をしたノードを学習する動作を繰り現できる．N = 102 , L = 160 として実験を行い，探返す実験を行った．ノード数を N = 102 , 103 , 104 と索時にシングルホップが達成される割合を計測した．

変化させ，経路表サイズの最大値は L = 20 とした．

実験結果が図 3 である．探索が繰り返されること実験は探索を行うノードが次のフォワーディング先ので経路表にノードが追加され，シングルホップ動作が問い合わせを繰り返す反復方式で行い，探索時の平均行われる割合が上昇していることがわかる．シング

経路長を計測した．また，提案方式による経路長の削ルホップ率に増減があるのは，毎回の測定の際にラン減を確認するための比較対象として，厳選時に無作為ダムな ID への探索を行っているからである．1 ノーにエントリを選択して削除するアルゴリズムも実装し，提案方式と同様の条件下で実験を行った．
実験により，1 ノード当たりの探索回数に対する平均経路長の関係を求めた結果が図 2 である．エント
リ厳選時にランダム削除を行う方式が一定回数の探索以降で平均経路長が短縮されないのに対して，提案方式ではエントリ厳選操作が繰り返し働くことによって平均経路長が短縮され続けていることがわかる．
特にノード数が大きい際に，経路長削減の効果が大きくなっている．
図3

エントリ学習・厳選の進行にともなうシングルホップ到達率

ド当たり約 360 回の探索で初めてシングルホップ率も適切にルーティング効率を向上できる手法を考察す

100% を計測し，その後も経路表の改良が進むことでることが，今後の課題である．

シングルホップ率 100% を計測する頻度は上昇している．

謝辞 有用なコメントを下さった大西真晶氏に深く感謝します．本研究は JSPS 科研費 24650025, 25700008の助成を受けたものです．

5 まとめと今後の課題
我々は，二次元平面上の P2P オーバレイネットワー
クで効率よくルーティングするために FRT を用いた経路表構築手法を提案した．この提案方式では各ノードがランダムな二次元 ID を持ち，平面上に一様に配置されていることを仮定している．経路表エントリの厳選操作は，自ノードとエントリに含まれるノードとのユークリッド距離に基づいて行われるため，少ない管理情報と計算量で動作する．
評価実験により，学習・厳選操作による経路表の改良が行われていることや，経路表サイズがノード数よりも大きいときにシングルホップ動作が行われることを確認した．今回は実装・実験こそ行っていないが，FRT に基づく方式であるため，拡張，例えばネットワーク近接性の考慮なども容易である．
提案方式では，二次元平面上のノード配置はランダムで偏りがないことを仮定している．しかしノード群が実空間の地理に基づいた情報管理を行う場合など
では，実空間のノード位置を利用することが有効となるだろう．このような場合ではノード位置が偏るので，提案方式に狙い通りの効果を期待することができない．FRT を用いてノード位置に偏りがある場合で参 考 文 献[1] Kleinberg, J.: The Small-World Phenomenon: AnAlgorithm Perspective, Proc. 32th ACM symposiumon Theory of computing, ACM, 2000, pp. 163–170.
[2] Miyao, T., Nagao, H., and Shudo, K.: A Method
for Designing Proximity-aware Routing Algorithms
for Structured Overlays, Proc. IEEE ISCC ’13,2013.
[3] Nagao, H. and Shudo, K.: Flexible Routing Tables: Designing Routing Algorithms for Overlays
Based on a Total Order on a Routing Table Set,
Proc. IEEE P2P ’11, IEEE, 2011, pp. 72–81.
[4] Ohnishi, M., Nishide, R., and Ueshima, S.: Incremental Construction of Delaunay Overlaid Network for Virtual Collaborative Space, Proc. C5 ’05,IEEE, 2005, pp. 75–82.
[5] Shudo, K., Tanaka, Y., and Sekiguchi, S.: Overlay Weaver: An Overlay Construction Toolkit,
Computer Communications, Vol. 31, No. 2(2008),
pp. 402–412.
[6] 首藤一幸: Overlay Weaver, http://overlayweaver.
sourceforge.net.
[7] 大西真晶, 源元佑太, 江口隆之, 加藤宏章, 西出亮, 上島紳一: ノード位置を用いた P2P モデルのためのドロネー
図の自律分散生成アルゴリズム, 情報処理学会論文誌デー
タベース (TOD), Vol. 47, No. SIG4 (TOD29)(2006),
pp. 51–64.
[8] 大西真晶, 坪井新治, 平山雅夫, 江口隆之, 上島紳一:
P2P ドロネーネットワークにおける遠隔接続経路の自律分散生成法, 情報処理学会論文誌データベース (TOD),
Vol. 48, No. SIG11 (TOD34)(2007), pp. 190–214.