実際のネットワークを考慮した階層型分散ハッシュ法

概要

　近年、インスタントメッセンジャーなど多くのピアツーピア(P2P)アプリケー ションが使用されており、インターネット上でオーバレイネットワークが構築さ れています。しかし、P2P環境では中央サーバが存在しないという利点は存在す るものの通信したい相手(ノード)を発見することが困難であると言えます。その ため、ピュアP2Pネットワーク上で高速に検索することを可能にする分散ハッシュ 法(Distributed Hashing)や分散ハッシュテーブル(Distributed Hash Table : DHT) と呼ばれる手法が注目されています。分散ハッシュテーブルを使用し、その上で オーバレイネットワークを構築することで高速な検索が可能となります。
　しかし、分散ハッシュテーブルを使用したオーバレイネットワークは、実際の 物理ネットワークの近さと分散ハッシュ上での近さは無関係となっています。その ため、オーバレイネットワーク上では無駄の無い検索ホップであっても、実際の物 理ネットワークでは、一度遠くのネットワークに存在するノードまで検索が進んだ 後に、検査kを開始したノードの近くのノードに検索が戻ってきてしまうような無駄 が含まれる可能性があります。
　そこで、本研究では、物理ネットワークでのノード間で通信にかかる遅延時間を 物理ネットワークでの近さであると定義し、物理ネットワークの近さを分散ハッシュ 上でのIDに反映させます。そして、そのIDを使用して階層化を行うことで、先に挙 げたような問題点を改良します。

関連研究

　本研究で提案手法の基礎とした Chord では、各ノードは SHA-1 などのハッシュ 関数により自分の ID を生成します。自分の ID と他のノードの ID をもとに管理 すべき領域や保存すべきノードの情報を決定することができるため，完全に分散し て動作することが可能です。 Chord では、ID 空間上で自分のID から見て時計周り の方向に最初に存在するノードを successor として記憶します。また、同様に反 時計周りに最初に存在するノードを predecessor として記憶し、その predecessor と自分との間の ID 空間を責任領域として管理を行います。また、各ノードは、 ルーティングテーブルに用いる m 行のテーブル(フィンガーテーブル)を 保持し、そのテーブルの i 行目には ID+2^(i-1) の successor の 情報が入ります。つまり、各ノードは自分の 1,2,4,8,... 先のノード情報を 保持していることになります。 Chord はこれらの情報をのみを用い、検索にかかる ホップ数を O(log n) に抑えています。
　Chord を使用し、先に挙げたような分散ハッシュを使用したオーバレイネットワー クの問題点を改良した手法として HIERAS が提案されています。 HIERAS 上の各ノードは、ランドマークノード(ネットワーク中のどのノードからも 存在と IP アドレスなどが知られているノード)への遅延時間をもとにした、物理 ネットワークでの位置を表すリングID と呼ばれる特別な識別子を持ちます。 HIERAS では，同じリングID を持つノード同士で生成した Chord のネットワークを 通常の Chord でのネットワークとは別に保持することで階層化を行っています。 HIERAS ではこのように複数の Chord ネットワークを使用することで先に挙げた 問題を改良しています。しかし、 HIERAS では各階層で Chord と同じ情報を保持 しなければならないため、維持コストが増加します。また、階層化を行うことに より、物理層での遅延時間は減少する反面、アプリケーション層でのホップ数が 増加することが報告されています。

提案手法

本研究では、 Chord で使用される ID に物理ネットワークの近さを反映させ、そ の ID を利用し階層化を行う LCLV(Layered Chord with Landmark Vector）を提 案します。 HIERAS では、リング ID と呼ばれる分散ハッシュ上の ID とは別の 識別子を新たに生成し、それをもとに階層化を行っていました。しかし、 LCLV では分散ハッシュ上の ID そのものに物理ネットワークでの近さを反映させ ます。この点が HIERAS との違いとなります。

ランドマークベクトルによる ID の生成法

　LCLV は物理ネットワーク上での距離を通信に必要な遅延時間により近似可能であ るという前提のもとに、遅延時間の短いノード同士は、分散ハッシュ上のネットワー クにおいても近くなるようなID を生成します。

　LCLV における新しいノード N の ID の生成の流れを以下に示します。

1. 各ランドマークの2次元空間での位置(座標)を求める。
2. 各ランドマークの座標と、 N から各ランドマークへの通信遅延時間 から、 N の2次元空間での座標を求める。
3. 決定された座標から ID を生成。

図1：ランドマークを用いた2次元空間へのマッピング

図2：Space Filling Curve を用いた ID の割り当て

　まず，ランドマークノードを図1 のように2次元空間にマッピングします(1)。 その方法として、各ランドマーク間の物理ネットワーク上での通信遅延時 間を測定し、測定された遅延と2次元空間での距離との誤差の和が最小となる点に ランドマークを配置します。次に同様の方法を用いて、今 ID を決定したいノード N の2次元空間での座標を求めます(2)。以上の方法で、物理ネットワークで 近いノード同士は、2次元空間においても近似的に近い座標を得ることが可能となり ます。
　次に、2次元空間をいくつかの空間に分け、そこに図2 のように空間充填曲 線(Space Filling Curve : SFC)を引きます。ここでは、空間充填曲線として Hilbert 曲線を用いました。そして、空間充填曲線が通った順に数字を割り当て ます。このとき、ノード N が存在する座標上の空間充填曲線によって割り 当てられた数字をノードの ID として新たに割り当てます(3)。

　この方法を用いることにより、物理ネットワークで近いノード同士を、分散ハッ シュ上での ID においてもおおよそ近い ID に割り当てることが可能となります。

階層化

　LCLV における階層化は、 Chord で用いる ID を数ビット毎に区切ること で行います。例として、 ID の大きさが12ビット、階層数が2、 第一階層の ID が3ビット、第二階層の ID が9ビットとし、 あるノード N のID が8進数表示で ID = 7042 と与えられた場合を考えます。 この場合、第一階層の ID は 7 となり、 第二階層の ID は 042 となります。つまり、図3 のように階層を分 けることになり、ノード N は図中の位置に配置されます。 このような階層化において、それぞれの階層は ID が小さいため、 もとの Chord よりも小さい規模のネットワークとなります。 このように LCLV は，小さな規模のネットワークに分けること で階層化を行います。 HIERAS は各階層で Chord と同じ大きさのネットワークを生成するため、 LCLV の方が維持コスト、テーブル量において優位です。

　LCLV では上位の階層の ID のみを先ほど説明したランドマークベ クトルによる ID を使用し、最下層の ID は通常の Chord と同様にハッシュ関数 を使用して割り当てます。

このような ID の割り当て方式を用いることにより、図2 においては， 第一階層でのネットワークは物理的に遠いノード同士のネットワークとなるため、 この階層における通信遅延は大きくなります。 しかし、第二階層でのネットワークは物理的に近いノード同士で構成されるため、 通信遅延は小さくなります。

図3：LCLV における階層化されたネットワーク

評価実験

　LCLV の効果を評価するため、 Chord,HIERAS,LCLV のそれぞれをネット ワークシミュレータである NS-2上に実装し評価実験を行いました。 実験では、各ノードがランダムな key を検索し、 検索にかかった遅延時間の平均、アプリケーション層でのホップ数の平均、 物理層でのホップ数の平均を測定しました。
　また、 LCLV においては、ランドマークベクトルによる ID の割り当ての効果を 確認するため、階層化のみを行った場合、階層化とランドマークベクトルによる ID の割り当ての両方を行った場合の二種類の実験を行いました。
　ID の大きさを24ビットとし、ノード数を512台から2048台まで変化させて 実験を行いました。 LCLV における種々のパラメータは、 ランドマークの数を15台、階層数を3とし、第一階層のIDは4ビット、 第二階層のIDを4ビット、第三階層のIDを16ビットに設定しました。 また、実験に使用したネットワークは GT-ITM(TSモデル)を使用しました。 TSモデルの設定において、 HIERAS の論文ではTransit-Transit(TT)間の 遅延時間を100ms、Transit-Stub(TS)間を 20ms， Stub-Stub(SS)間を 5ms としてあったので、本研究でも同様の設定を行いました。

図4：アプリケーション層の平均ホップ数

図5：物理層の平均ホップ数

図6：平均遅延時間

　図4 にアプリケーション層でのホップ数、図5に物理層でのホップ数、 図6に遅延時間をそれぞれ比較したときのグラフを示します。
　図4 と図5 より、 HIERAS は Chord よりもアプリケーショ ン層でのホップは増加し、物理層でのホップはわずかに減少していることが 確認できます。 また、LCLV は Chord、HIERAS よりも検索にかかるホップ数が減少していることも 同様に確認できます。
　図6 より、 HIERAS は Chord より遅延時間が減少していることが確認できます。 しかし、LCLV でランドマークによる ID に加え階層化を行った場合は HIERAS よりも 遅延時間が減少しています。

図7：検索の各ホップ毎の平均遅延時間

　また、ノード数が2048台のときの検索ホップ中の各ホップ毎にかかった平均遅延時 間を図7 に示します。
　図7から、実験に使用したネットワークはHIERAS に適したネットワークで あるため、階層化が適切に行われており、検索の初期は遅延時間が小さく、 後期は大きくなっていることが確認できます。
　LCLV においても同様に階層化を適切に行えたため、検索の初期ホップは 遅延時間が大きく、後期ホップは小さくなりました。
　HIERAS は最悪のホップ数の場合、後期のホップほど遅延時間は大きくな り、最大値が大きくなります。しかし、 LCLV は最悪のホップ数の場合においても、 後期のホップは遅延時間が小さいため、遅延時間の最大値は大きくならない。以上に より図6 に示すとおり LCLV の遅延時間の平均は HIERAS よりも下がる 結果となりました。