R に管理するデータの移管を行なう ノード P が管理しています。そのため情 ・ Finger Tab を更新する 報 X を検索、登録する際には、ノード ・ p 「 edecesso 「の存在を確認する ID=Hash(X) となるノード p と通信する という作業をする必要があります。 必要があります。ノード P が存在しない successor と predecessor の更新手順は 場合は successor (Hash (X) ) となるノー ドが情報 X を管理します。例えば図 4 以下のとおりです。 ノード A は、現在ノード A が おいて Hash ( X ) = 3 となる情報 X はノー 手順 1 ド 3 が保有していますが、ノード 3 が存 successor と考えているノ 在せずかっノード 4 が存在する場合は、 ド B に対して、ノ ド B の predecessor ( ノード X と呼ぶこ ノード 4 が情報 X を管理します。 とにする ) について質問します。 ノードの参加 ノード B はノード A にノード X の情報を返答します。この時 ノード 1 、 3 が存在して、かっノード 2 ノード B が返答するノード X は が Chord に参加する場合の手順を説明し 以下のようになります。 ます。 ケース 1 : ノード A とノード B の ノード 2 は自分の successor とな 手順 1 りうるノードにこではノード 間にノード S が新たに 参加している場合→ 3 ) 情報について、 DHT に参加 しているあるノード N に検索依 ノード S ケース 2 : ノード A とノード B の 頼を行なう。 間に新たにノードが ノード 2 はノード N からノード 3 参加していない場合 のノード情報を入手する。ノー ド 2 はノード 3 を successor とし →ノード A この手順によってノード A はノード て登録する。 A ~ B 間の新たなノードの確認が 以上がノードの参加手順です。 できます Chord ネットワークの安定化作業 ノード A はノード X の情報を元 に successor を更新します 参加手順 2 が終わった段階では、ノード 1 ケース 1 の場合ノード S 、ケー ~ ノード 3 における successor と predecessor ス 2 の場合ノード B を successor の状態に不整合が生じています。例えば とします。 ノード 1 の successor はノード 3 のままで 手順 4 す。また各ノードの Finger TabIe 、管 ノード A は successor にノード A の存在を告げます。すなわち 理する情報にも不整合が生じています。 このようなノード参加、離脱による状 ノード A はケース 1 の場合ノー ド S 、ケース 2 の場合ノード B 態の不整合を解決するため、各ノードは にノード A の存在を通知しま 定期的に、 す。この作業によりノード A の ・ successor と predecessor を更新する successor はノード A の存在を ・新しいノード R が参加した場合、ノード SPECIRL B * 17 代表例として OceanStore http://oceanstore.cs.be 「 keley. edu/ PAST http://research.mic 「 os oft.com/-antr/PAST/defauIt. htm が挙げられる。 * 18 Miguel Castro, Pete 「 Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, and Atul Singh 「 SpIitStream : High- bandwidth multicast in a cooperative envi 「 onment 」 ln Proceedings of (IPTPS ℃ 3) February 2003 * 19 阿部洋丈、加藤和彦「 Ae 「 ie : W WW のための完全分散型プロキシ」 情報処理学会論文誌 : コンピューティ ングシステム、 VOI. 46 、 NO. SIG 3 (ACS 8 ) 、 pp. 51-61 、 2005 年 1 月 * 2 。西谷智広「 P2P と認証、 P2P で の SNS 」 ( 「 P2P とは何か ? 基礎か ら研究紹介まで」から ) http://homepage3.nifty.com/ toremoro/p2p/dhtaaa. html * 21 Taku 」 i limura, Hiroaki Hazeyama, and Youki Kadobayashi 「 Dist 「 ibuted ScalabIe MuIti-pIayer OnIine Game Servers on Peer-to-Peer Netwo 「 ks 」情報処理学会論文誌、 Vol. 46 、 No. 2 、 pp. 376-391 、 Feb 「 uary 2005. * 22 「 P2P - S 旧解説」 http://muziyoshiz.jp/sc2005/ SC2005_yoshiz_P2P_SlP.pdf Skype conference 2005 資料 手順 2 手順 2 手順 3 32 UNIX magazine 2006 Autumn

・ predecessor(X) : ハッシュ値 X におい てハッシュ値が小さい方向で 1 番近い 図 3 においてノード 2 の場合はノード ID=2 ですので、 successor はノード 3 、 predecessor はノード 1 を指します。 まず、簡単な Finger TabIe の例を説 宛先ノード心 明します。各ノードは隣り合うノード情 X=5 報を保有しているとします。この時に 65XW7 ノード 0 がノード 7 にたどりつくまでに 85X ミ 1 1 1 2 5 X S 15 どのような通信が必要か説明します。 OSXS3 答の 1 つは、図 4 のようハッシュ値の 表 6 ノード 4 の Finger Table 大きい方向で隣り合うノードに順次ホッ りつく場合を考えてみましよう。 プしてノード 7 に到達することです。 ノー ド 6 のノード ID は 6 ですから、ノード 0 は の方法では一般的にノード参加数を N Finger TabIe ( 表 4 ) よりノード 4 にホッ とすると、情報を検索する上で 0 ( N, ) の プします。ノード 4 は Finger TabIe ( 表 ホップが必要となります。そのためノー 6 ) よりノード 6 にホップします。最後 ド参加数が大きい場合に到達ホップ数が 大きくなりシステムが破綻します。 にノード 6 から、ノード 6 の successor で あるノード 7 にホップします ( ノード 6 の それに対し、 Chord はとてもスマート Finger Table は表 7) * 16 。結局ノード 1 は な方法で各ノードへの到達ホップ数を減 3 ホップでノード 6 にたどり着くことが 少させています。 分かります ( 図 6 ) 図 5 を見てください。ノード 0 はハッ シュ値が大きい方向で 2N ( 0 坙 N 坙 3 ) 離れ Finger Table は、自ノードのハッシュ 値から近い部分については詳細な情報を たノード情報を保持しています。 保有し、ハッシュ値から遠くなるほど粗 ノード 0 の Finger TabIe はそれぞれ表 4 い情報しか持ちません。これが Finger のように表わされます。一般にノード A TabIe のサイズが小さくても、少ない の Finger Table は表 5 のように表わされ ホップ数で目的とするノードに到達でき ます。 る秘訣です。ノード参加数 N に対して、 なお、項番 N はハッシュ空間を m ビッ あるノードに到達する時に必要なホップ ト確保した場合、 1 坙 N 坙 m であること 数は 0 ( ん g ( N, ) ) 程度です。 に注意してください。 Finger Table において次ホップノー 情報の検索、登録 ドとなるノード ID ( これを ID_R としま 情報 X を検索、登録、削除するには、 す ) にノードが存在しない場合は、次ホッ Hash (x) を計算する必要があります。情 プノードは successor (ID_R) となります。 報 x は原則ノード ID が Hash(X) となる もう 1 度、ノード 0 からノード 7 にたど X=A + 1 mod A + 2 mod 2m A + 25 XSA + 3 2m 2 A + 45X5A + 7 2 ” A + 4 mod 3 N A + 2N75X5A + 2N - 1 n10d2n1 A + 2N 表 5 一般的なノード A の Finger Table 項番 次ホップノードのノード旧 宛先ノー D 項番 次ホップノードのノー D 宛先ノード旧 X=I 項番 2 4 8 2 ミ XS3 4 5 X 5 7 8 5 XS 1 5 2 表 4 ノード O の Finger TabIe 宛先ノード心 8 ミ X$9 1 0 ミ X S 13 14 ミ X515 14 OSX ミ 5 表 7 ノード 6 の Finger Table 次ホップノードのノー D 次ホップノードのノー椡 D 項番 5 7 8 6 8 2 2 2 3 4 0 * 16 Cho 「 d では最後の 1 ホップは各 ノードの successo 「情報からたど ります。 UNIX magazine 2006 Autumn

ノドー 5 SPECIRLB ・ノード 14 ノデ下 13 イデド 13 ノデト 1 2 ノト 1 2 イデト 1 1 ノ—ト 10 みド 10 図 3 ノード 0 ~ 15 が存在する Chord イメージ図 ことが可能です。 さて、ハッシュ値が取りうる空間を ハッシュ空間とします。ハッシュ空間と して m ビット確保すると、ハッシュ値空 間 H は 0 坙 H 坙 2 。ー 1 となりますが、 Chord のハッシュ空間は 2 。の剰余系 (mod 幻 であることに注意してください ノード ID という概念を導入します。ノー ド ID はノードと一意に紐付けられた ハッシュ空間の値です。ノード ID はイ ンターネットの世界における IP アドレ スと類似しています。 DHT の世界では ノード ID を使ってノードを指定します。 また、ノード ID はハッシュ空間 H 内の値 を取ります ChordT0 はノード ID として IP アドレ スのハッシュ値を使います * 15 Chord の Finger Table ノード間の通信を行なうため、ルー タにおけるルーティングテープル相当の 情報を各ノードで保持します。これを Finger Table と呼びます。 図 3 は例としてノード 0 ~ ノード 15 が ここで例として 4 ビットのハッシュエ すべて存在する状況を図示しています。 間による Chord アルゴリズムの動作を説 FingerTabIe を説明する目リに successor 明します。つまりハッシュ空間 H は 0 坙 と predecessor について定義しましよう。 H 坙 15 です。このとき 0 坙ノード ID 坙 15 ・ successor(X): ハッシュ値 X において となります。ノード ID=Z のノードをノー ハッシュ値が大きい方向で 1 番近い ド Z と呼ぶことにします。 図 4 隣り合うノード情報を保有している場合 2 。 = 1 0 / ト 14 2 ー = 2 みド 13 / デド 12 23 = 8 図 5 ノード O が保有しているノード情報 、ノト 1 5 ノド 14 みド 13 み = ド 1 2 ノ・ト 1 0 図 6 ノード O からノード 7 へ辿り着くルート * 15 この手法によって、あるノード R がノード ID を偽装しているかどう か、ノード R の旧アドレスを知るこ とにより検証できる。また旧アドレ スとポート番号を組み合わせた情 報の八ッシュ値をノー制 D として利 用することも提案されている。 30 UNIX magazine 2006 Autumn

【手順 2 ~ 4 】 他ノード情報を 仲介サーバから入手 【手順 1 】 各ノードはノード情報を 仲介サーバに登録 介 Gnutella 、 Winny は Unstructured タイプ に分類されます。両者の違いについては 後ほど解説します。 ピュア P2P の大きな課題の 1 つは、ほ かのノード情報、特にファイル情報や IP アドレスをどのように入手するかという ことにあります。まずは GnuteIIa を代表 とする Unstructured タイプで上記課題 を解決する方法を解説します。 Unstructured タイプは、フラッティ ング ( fl 。 od = 溢れる ) により各種メッセー ジをほかのノードに伝播させる方式で す。フラッディングとは、各種メッセー 【手順 3 】 ファイルを保有して ジを隣接するノードにバケツリレー式に 【手順 4 、 5 】 いることを回答 直接通信してファイル共有 次から次へと転送させていく方式です。 各種メッセージがネットワーク上に溢れ 図 2 ピュア P2P (Unstructured タイプ ) の構成図 るような様であることから、 をする。 このように 命名されています。 手順 5 1 ノード A はノード G からファイ さて図 2 のようにノード A ~ G が接続し ル P をダウンロードする。 ているとしますこのときノード A がノード Unstructured タイプはフラッティン B—G に、ファイル P の有無について検索 グでメッセージ通信を行なうので、ファ イルの存在確認などをするたびにネッ 依頼する手順を説明しましよう。ここでノー ドが直接リンクしているノードを、隣接ノー トワーク帯域を消耗します。そこで GnuteIIa は次のような対策を行なってい ドと呼ぶことにします ノード A は隣接ノード B 、 C に ます。 手順 1 ・ TTL (Time to Live) を利用して、ファ ファイル P の有無について検索 依頼を出す。 イル存在確認が行なえるノードの範 囲を限定する。 TTL とはホップ数の ノード B は隣接ノード D 、 E にファ 手順 2 上限を決める値で、各種メッセージの イル P の有無について検索依頼 中に含まれています。メッセージが各 を出す同様にノード C は隣接ノー ノードにホップするごとに TTL の数 ド F 、 G にファイル P の有無につ いて検索依頼を出す を 1 減らし、 TTL が 0 になった時にノー ドはメッセージの転送を停止します ファイル P が存在した場合、各 手順 3 ・メッセージに固有番号を含めること ノードは自分の IP アドレスな で、各種メッセージのループが検出で どの情報を検索依頼したノード きるようにする。各ノードは受信時 に回答する。 にこの固有番号を記録し、その後同一 手順 4 ファイル P を有すると回答した のメッセージを受信した場合は、その ノード G とノード A が直接通信 ロ ロ ロ ード D 【手順 5 、 6 】 仲介サーバの情報を元に ー他ノードと直接通信 図 1 八イブリッド P2P の構成図 【手順 1 】 メッセージを送信 、ノド D ・ド ノ 【手順 2 】 メッセージを送イ 【手順 2 】 メッセージを送信 一三ロ ード 0 * 4Gnute 日 a プロトコルは「ネット ワーク管理者のための Gnute 日 a 入 門」が詳しい。 http://www.atmarkit.co.jp/fwin 2k/experiments/gnutelIa_for admin/gnutella for_admin_l. html * 5 Winny 全般は金子勇著「 Winny の技術」 ( アスキー ) が参考になる。 Winny プロトコルは、オープンソー スの Winny クローン「 Poeny 」を調べ るとよいだろう。 UNIX magazine 2006 Autumn

信木に参加することになります。各ノー ら 10 ノードに対して転送でき、受信可 が行なわれます。このルーティングは、 ドはどれかただ 1 つの配信木で子を持ち 能なノードの数をそれだけ増やすことが 該当するキーと値の組を保持している ます。複数配信木を構築する ALM には、 できます。 ノードに到達するというわけです。 ほかに Chunkyspread などがあります。 ここで同一の ID を宛先として、複数 ここで、配信木を構成する各ノードの 上り帯域幅について考えます。子を持つ の異なるノードからルーティングを行 メッシュべースのデータ転送 ノードは、データを子に転送するために なった場合を考えます。各ルーティング 上り帯域幅を活用しています。持ち得る 木構造には、親が 1 つである、ノード の経路は、最終的には同一の担当ノード 間に親・子という方向がある、といった 子の数が、上り帯域幅によって制限され に収束します。これら複数の経路の和集 いくつかの制約があり、この制約に従っ 合は、木構造を構成します ( 図 5 ) 。 る点にも注意してください。このことは 配信木を構成する際に、各ノードの帯域 てデータが流れます。これに対し、より の木構造を配信木として使おうという 緩やかなノード間の関係に基づいてデー 幅、特に上り帯域幅を考慮する必要があ のが、構造化オーバーレイを使ったマ タを転送していくメッシュべースの方式 ることを意味します。続いて子を持たな ルチキャストの基本的なアイデアです。 も提案されています。ここでは、ノード いノード、つまり配信木の葉の場合はど Scribe は、構造化オーバーレイのアルゴ うでしよう。ほかのノードに対してデー 間に親子関係がなかったり、ノード間の リズムである Pastry を使って配信木を タを転送していないということは、上 関係が枝の有無といったゼロ / イチでは 構築します。それは配信木の根をランデ 定まらなかったりする、比較的ノード間 プーポイント (Rendezvous point) と り帯域幅を活用していないことになりま の関係が緩やかな構造を大雑把にメッ す。木構造において、葉となるノードの して、そこから葉に向けてデータを転送 シュと呼びます 数は案外多いものです。各ノードが 2 つ していくという ALM です。 メシ上全ノードに対してデー の子を持っバイナリツリーですら、半分 上り帯域幅を活用しつくすための 複数ツリー タを配布する方式として、 flooding とい 強のノードが葉となります。各ノード う単純な方式がよく知られています ( 図 が 16 の子を持っとしたら、 9 割を超える 昨今のインターネットは Web 向きに 6 ) 。 flooding は日本語で「洪水」「氾濫」 数のノードが葉となります。 ALM にお 設計されており、 P2P ソフトウェアの であり、文字どおり、メッシュ上にデー いて、系全体にとっての貴重な資源であ 動作に適さない構造が各所にあります。 タを氾濫させます。 P2P 関係では、ファ る上り帯域幅を活用しないというのは、 アクセス系ネットワークについていえ イル共有プロトコル Gnutella で検索クエ もったいないことです。 ば、 NAT の普及による双方向通信の阻 リの拡散に fl 。 oding が使われていること そこで、複数の配信木を構築して、 害や、非対称 DSL (ADSL) での上り方 が有名です。 それぞれの配信木ではデータの一部分 向帯域幅の狭さがその例です。特に上り flooding では、各ノードは隣接ノード を流すという手法が考えられました。 帯域幅の狭さは、 ALM で非常に大きな SplitStream は、複数の配信 問題となります。 ALM では、各ノード 木を構築する ALM です。 が受信したデータをほかのノードに提供 で構築される複数の配信木は するので、受信のための下り帯域幅だけ forest と呼ばれます。それぞれ でなく、送信のための上り帯域幅が重要 の配信木は Scribe の手法で構 となります。上り帯域幅が広いほど、ト 築し、データストリームを時間 ラフィックをより大きく増幅できると 方向に分割したものを、複数 いうことです。例えば、 500kbps のトラ の配信木に分散して流します。 フィックを受信している場合、上り帯域 つまり、ノードは必要なデー 幅が 500kbps なら 1 ノードに対してしか タを揃えるために、複数の配 転送できません。しかし 5Mbps だとした ー②未送信 & 転送 3 未送信 & 転送 2 ②受信済 & 転送せす 3 3 図 6 flooding 37 UNIX magazine 2006 Autumn

す。各隣接ノードとのスルーブットに応 ものにシーケンス番号を振り、その番号 じて、隣接ノードの選別も行ないます。 やビットマップで保持データを表現し、 一方、 Chainsaw は、論文で述べられて 隣接ノードに通知しておきます。これに いる範囲では、ランダムに選んだ一定数 よって各ノードは、隣接ノードがどの のノードを隣接ノードとします。両者と データ片を保持しているかを知ることが も、保持データ情報を隣接ノードとの間 でき、データ片を要求できるのです。 で交換し、それに基づいてデータを要求 この方法はデータ駆動 (data-driven 、 するという点は共通しています。 data-centric) と呼ばれます ( 図 7 ) 。ツ データ駆動方式は提案から比較的日が リーベースでは欠かせないノード故障・離 脱時の木構造の再構成が不要であること 浅く、間題があまり明らかになっていま が長所です。またメッシュべースのブッ せん。我々の経験と考察によると、デー タが各ノードに到達するまでの時間、つ シュ型プロトコルで起こりがちな無駄な まり遅延が問題となり得ます。それは データ転送をなくすこともできます。前 単なるプル型ゆえの問題だけではあり 者を理由として、ノードの頻繁な出入り ません。つまりプッシュ型では必要の (churn) に強い (resilient) という生来 ないデータ要求が必要となり遅延が増 の性質を持ちます。ただしこれは、隣接 すだけではなく、遅延と隣接ノード間 ノードの選択・管理アルゴリズム、つまり での保持データ情報の通知頻度の間に どのノードをどのような基準に基づいて トレードオフがあります。通知の頻度が 隣接ノードとするかによります。状況変 化への耐性 (resilience) は、ツリーベー 低い場合、自分の隣接ノードがデータ 片を入手してからそれを自分が知るまで ス、データ駆動にかかわらず、特定のア に、時間が空いてしまいます。その時 ルゴリズムを想定しての比較が必要です。 間間隔が、転送の回数だけかさんでしま データ駆動方式の ALM には、 Cool うのです。逆に、通知の頻度を高くする Streaming/DONet や Chainsaw がありま と、それだけ通信処理の負担が増えます す。前者はノードの情報、例えば IP ア CoolStreaming/DONet は隣接ノー ドレスなどを gossip で流通させ、隣接 間で継続的に保持データ情報を交換し、 ノード数が一定値を切った場合には、ラ Chainsaw はデータ片を受信するや否や、 ンダムに選んだノードと接続を持ちま 隣接ノードにそのことを通知します。前 者は、比較的低頻度、後者は高頻度であ 保持テータ情報を交換しておく るといえます。 ハイプリッド P2P とピュア P2P データ転送の方式とは独立して、 ALM にもほかの P2P システムと同様に、ハ イプリッド P2P かピュア P2P かという 分類の観点があります。ピュア P2P で は、純粋に役割が対等なピア ( ノード ) ①テ ータ片を要求 ②テ ータ片を送信 ァータ駆動 (data-driven 、 data-centric) 方式 図 7 39 UNIX magazine 2006 Autumn

群だけで機能 ( 例 :ALM) が果たされま ノードに対してどのノードの子になる す。それに対してハイプリッド P2P で べきか ( およびどのノードの親になるべ は、ピアに対して何らかのサービスを提 きか ) を指示するものです。このような 供するサーバがあって初めて、機能が果 ALM には、 CoopNet 、 ALMI などがあ たされます ( 図 8 ) ります。この方式の利点は、オーバーレ ALM の場合は、大元のデータ配信元 イ全体を把握しているコンピュータがト は唯一データを供給する特殊なノードで ポロジを決めるため、より良いトボロジ あり、ほかのノードと役割が対等ではあ を設計し得るという点です。ピュア P2P りません。これを理由として、 ALM は では一般に、各ノードは全ノードの状況 すべてハイプリッド P2P であると分類 を把握できないため、良いトボロジの構 することもできます。しかし通常はそう 築は難しいものとなります。またトボロ は考えません。データ配信元ノードが直 ジを管理するコンピュータに、全ノード 接サービス ( データ ) を提供する対象は の状況とトボロジの情報が集まるため、 ごく一部のノードに ALM システムを運用する人がオーバー 全ノードではなく、 限られるためです。 レイ全体を把握できるという利点もあり ALM では、何かしらのサーバがノー ます。ピュア P2P の ALM では、オーバー ドの大多数にサービスし、完全に自律的 レイの全体像を把握するには、そのため に動作するノードが存在しないかごく少 の工夫が別途必要となります。 数であるようなものを、ハイプリッド ハイプリッド P2P の間題は、 ALM に P2P と分類します。この基準で分類す 限らず、負荷の集中と耐故障性にありま ると、研究成果として発表されている多 す。サーノヾには、最低でもオーバーレ くの ALM はピュア P2P です。 イに参加しているノードの数に比例す ハイプリッド P2P である ALM の例に る処理負荷とネットワーク負荷がかかり ツリーベースの方式で、配信木の構造、 ます。データ自体はノード間で転送され つまりトボロジを集中的に決めるものが ますが、ツリーベース ALM ではトボロ あります。これは少数 ( 一般的には 1 台 ) ジ管理のための負荷がサーバに集中しま のサーバが集中的にトボロジを決め、各 す。そのため、いかにそこを軽量に作る かが重要となります。また耐故障性とし ては、サーバの故障などでサービスを提 ゝーイ 供できなくなると、オーバーレイ全体が 機能不全に陥るという問題があります。 トボロジ・ノード情報等 の問い合わせ ( ) ハイプリッド P2P では、バックアップ サーバを用意するなどの可用性向上策が 欠かせません。 データの符号化 ALM そのものの手法ではありません が、データ、特に映像・音声ストリーム SPECIRL C 何らかの アクション 特殊なビア ( ノード群 ) だけで 機能が果たされる ピュア P2P ハイプリッド P2P 図 8 八イプリッド P2P とピュア P2P 40 UNIX magazine 2006 Autumn

販売価格 ノードの情報 管理範囲 情報 X ハッシュ値 Y=Hash(X) 管理ノード リンゴ バナナ スイカ 1 OO 円 150 円 1 OOO 円 130 円 300 円 200 円 250 円 400 円 30 円 1 2 5 「 / 0 ミ Y ミ 6 ノード A * 1 。 Sylvia Ratnasamy, Paul Francis, Ma 「 k Handley, Richa 「 d Karp, and Scott Shenke 「「 A Scalable Content-Add 「 essable Network 」旧 P 「 oc. ACM SIGCOMM 2001, August 2001 * 11 Antony Rowstron and Peter DruscheIFastry: Scalable, decentralized object location and routing forlarge-scale peer-to-peer systems 」 Lecture NOtes in Computer Science, VOL2218 pp. 329-350 , 2001. 先に ove 「 view 資料をみた方が理解 しやすい。 http://freepastry.org/PAST/ov erview. pdf * 12 Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph 「 Tapestry :An lnfrastructure fO 「 Fault- tolerant Wide-area Location and Routing 」 TechnicaI Report UCB/CSD-OI-1141 , Computer Science Division, U. C. BerkeIey, ApriI 2001. 55 Tapest 「 y については日本語関連資 料あり。「オーバレイネットワークに よる統分散環境」 http://www.wide.ad.jp/ project/document/ 「 eports/pd f2002/part17. pdf * 13 Petar Maymounkov and David Maziéres 「 Kademlia. A Peer-to-peerlnformation System Based on the XOR Metric 」旧 Proceedings Of lPTPS02, Cambridge, USA, Ma 「 ch 2002 日本語関連資料あり。 首藤ー幸「 Kademlia 」。 http://www.shudo.net/a 「 ticle/ KademIia-20040727/shud0-Ka demlia. pdf * 14 http: 〃 overlayweaver. sour ceforge. net/index-j. html なし バイナップル もも マンゴー 0 5 3 2 3 っ 0 7 SY ミ 17 ノード B ぶどう みかん 18 ミ Y 坙 40 ノード C 表 3 八ッシュテープルの分散管理のイメージ図 機能 1 らに分割したテープルはノード A—C で ノードの DHT ネットワークへ の参加 分散管理しています。 また各ノードが管理すべき情報 X ( 具 機能 2 ノードの DHT ネットワークか 体的には X のハッシュ値 Y ) の範囲も管 らの離脱 理ノード間で自律的に決定します。 機能 3 ノードへの情報の登録 このようにハッシュテープルを分割 機能 4 ノードに登録された情報の取得 し、そのハッシュテープルを各ノードが 機能 5 他ノードの要求に応じたルーテ 分散管理することが、 DHT の基本概念 イング機能 となります * 8 機能 6 任意のノードとの直接通信 それでは DHT の特徴を挙げてみま DHT ネットワークを安定的に 機能 7 維持するための機能 しよう。 DHT の代表例として Chord * 9 、 CAN*IO ・情報はシステムに参加しているノー Pastry*ll 、 Tapestry*12 、 Kademlia*13 など ド群で分散管理されている が挙げられますが、これらの基本機能はほ ・各ノードは一意のと第田寸けされる ば同じです ・各ノードは容易に DHT ネットワーク それでは、 DHT の代表例である Chord へ参加、離脱か可能である について解説します。 ・ネットワークに属する任意の 2 つの ノード間で通信可能 DHT の実例 ・任意のノードに対して、比較的少ない Chord のしくみ ホップ数でたどり着くことができる ・リンク先となれるノードにトボロジ Chord は DHT の中でもしくみがシ 的制約がある ンプルなため、盛んに研究されている DHT の 1 つです。 DHT ミドルウェアで 次に DHT におけるノードの機能を分 ある OverIay Weaver*14 でも動作させる 類します。 0 29 UNIX magazine 2006 Autumn

に対し強制的にデータを送りつけます。 構造を前提としながらもメッシュべース つまりプッシュ型の方式です。データを の手法をとっています。最初は配信木に 受信したノードは、そのデータの受信が 従ってデータを流しますが、各ノードは 初めてであれば、データが来た方向を除 すべての子に全データを流すわけではあ いて、自分の隣接ノードに対してデータ りません。各ノードは木構造に関係なく、 を転送します。受信済であれば転送しま 足りないデータをほかのノードから入手 せん。 します。この点がメッシュべースである 単純な flooding には、データ転送の総 所以です。どのノードがどのデータを保 量、それも無駄なデータ転送が多いとい 持しているかという情報は、木構造を活 う問題があります。例えば図 6 中のある 用して流通させます。この手法によりッ ノードは、同一のデータを 4 回以上受信 リーベースよりも高帯域幅のデータを流 しています。各ノードの上り帯域幅が貴 すことができる、というのが提案者の主 重な ALM において、これは大きな問題 張です。 です。そこで、 ALM に flooding を適用す データ駆動のデータ転送 る場合には、無駄なデータ転送を低減す る工夫がとり入れられています。 これまで紹介してきたツリーベース、 flooding の良い点、つまり高いデータ浸 メッシュべースの方法は、基本的にブッ 透率を維持しつつ、なおかっデータ転送 シュ (push) 型のプロトコルでした。木 の総量を抑える手法として、 1980 年代に 構造では、データは単一の親からしか gossip と呼ばれる手法が考え出されまし やってこないため、プル (pull) 型のプロ た。 gossip は rumor mongering 、 epidemic トコル、つまり親に対するデータの要求 dissemination とも呼ばれます。文字どお は無駄なものでしかありません。しかし り、噂が人づてに伝わっていくような動 メッシュべースでは状況が異なります。 作をします。 gossip プロトコルには、多く ブッシュ型プロトコルである flooding や のノヾリエーションがあります。基本的には gossip では、同一のデータが複数の隣接 転送処理として、隣接ノードの中から転 ノードからやってきます。この無駄を省 送先をランダムに選び転送する、という くためには、プル型のプロトコルが有効 動作を繰り返します。そして、例えば受 です。つまり、強制的にデータを送りつ 信済ノードへの転送を一定回数繰り返し けること (push) はやめ、明示的な要求 てしまった時点で、転送を止めます。 (pull) があって初めて転送するのです。 この種のプロトコルの ALM への応用 かといって、隣接ノードに対してや としては、構造化オーバーレイ CAN の みくもにデータを要求しても、その隣 上で % oding を行なうものがあります。 接ノードが当該データを持っていなけれ flooding は ALM 自体よりも、イベント ば、要求自体が無駄なものとしかなりま 通知 ( 例 :lpbcast) やオーノヾーレイのメ せん。そこで、自らが保持しているデー ンノヾ管理 ( 例 : CoolStreaming/DONet) タの一覧を、隣接ノードに知らせておく という方法がとられます。具体的には、 によく用いられています。 Bullet という ALM は、ノード間の木 データストリームを時間方向に分割した SPECIRL C 38 UNIX magazine 2006 Autumn

に CDN ( コンテンツ配信ネットワーク ) を前提とすると、 CDN は ISP 間のトラ フィックを減らす効果があるので、 P2P システムを使った方が ISP 間トラフィッ クは多くなることが予想されます。 ISP の境界をまたぐトラフィックが増える と、ある業者は収入が増え、別の業者は 支出が増えます。収入が増える業者は何 も言わないでしようが、支出が増える業 者は対応を迫られます。 ただし、 P2P システムが ISP 間トラ フィックを増やすとは限りません。特 に CDN を経由しないデータについては、 受信者の数だけ ISP 間をまたいでいた分 が、 P2P システムにより ISP 内で再配布 され、 ISP 間トラフィックが減る効果も 期待できます。さらには、 P2P システム が ISP の境界を認識できたなら、 CDN と同等以上の ISP 間トラフィック減効果 を得られるかもしれません。 いずれにせよ P2P システムの開発者 には、インターネット運用側のこのよう な力学を意識し、システムを設計するこ とが求められます。 大規模試験の方法 P2P システムには、下は数十から上 は数百万ノードまで、破綻せずに動作す ることが求められます。では、ノードが 増えていった場合にもきちんと動作す ることを、どのように確認したらよいで しようか。 クライアント / サーバ型のシステム であれば、ポトルネックとなるのはサー バ側の処理能力やネットワーク帯域幅で す。その負荷は大抵サーバへの問い合 わせ数や通信量に比例するので、試験は シンカレです。サーバに対する問い合わ せ頻度や通信量を可能な範囲で上げてい き、それ以上については負荷の量を外挿 します。サーバ側を増強することで性能 向上を図れますし、運用の努力で安定性 を高めることもできます。 P2P システムでは、利用者側のコン ピュータがサーバの役割も果たします。 利用者側ノードの安定性や性能は P2P システム提供側の手の及ぶところでは なく、運用の努力で向上できるものでも ありません。また、ソフトウェアが普 及すればするほど、後々での更新も難し くなっていきます。そのため、あらかじ め頻繁な離脱と参加、低性能・狭帯域幅 ノードの参加、ノード数の増加を想定し、 綿密に設計する必要があります。同時に、 どのような状況でも破綻せずに動作する ことを、事前に確認しておくことが望ま れます。 確認の手段は、システムのシミュレー ションおよび大規模環境のエミュレーショ ンです。シミュレーションでは、 P2P シス テムの挙動を模したソフトウェアを作り、 1 ~ 数台程度のコンピュータで多数のノード を模します。工ミュレーションでは、 P2P システム側ではなくネットワーク環境を模 します。一般に、シミュレーションの方が 模すことのできるノード数を多くできます。 一方のエミュレーションでは、実際のソフ トウェアを動作させることができ、より現 実に近い動作を期待できます。どちらの方 法でも、最大で数千程度のノードを模擬で きているというのが世の中の状況です。 試験は、ノード数を多くすればよいと いうものではありません。例えばノード の頻繁な離脱・参加があった場合にも破 綻しないことを確認しておきたいところ です。そのためには、シミュレータや工 ミュレータに、各ノードにそういった動 作をさせるためのしかけが必要となりま す。それには、パラメータに従い離脱や 参加を繰り返す特殊なノードを作る、も しくはシナリオとして記述 ( 生成 ) した 動作を各ノードに行なわせるという手が あります。 しかしながら、試験とはあらかじめ想 定し得た項目しか行なうことができない ため、実際と同じ状況でできるだけ多く の人に試してもらうことは欠かせません。 まとめ ンジニアの一助となれば幸いです。 稿が、分散システムを設計・開発する工 に埋もれているというのが現状です。本 論文や書籍、発言の中に散らばり、とき た。いまだこの種の知識は、さまざまな めには配慮が欠かせない点を整理しまし れがちな、しかし現実環境での動作のた ここでは、理論・方式研究では無視さ UNIX magazine 2006 Autumn 47