ITRC meet23
2008年 5月 15-16日, 名古屋大学

Overlay Weaver とその PlanetLab 上での運用
首藤一幸
ウタゴエ / NICT

内容
• Peer-to-Peer コンテンツ配信技術 (ウタゴエ社)– ライブストリーミング– IPTV

• オーバレイ構築ツールキット– Overlay Weaver• 産総研グリッド研究センター由来。
2006年度からは個人で継続。

Peer-to-Peer ライブ配信
実ネットワークに適応するオーバレイマルチキャスト 放送基盤

• 映像・音声のライブ配信が可能。
ここが技術的に面白い。メッシュ型 (⇔ツリー型)

cf. YouTube, ○○動画

• 配信元のネットワーク帯域幅をほとんど食わない。
⇒ 極めて低い配信コスト⇒ 誰でも発信配信元②データ①リクエストcf. サーバ-クライアント, CDN• 1万ノードでの動作実績。
(PC クラスタ上)

実地 & PlanetLab上でも大規模動作。

• 様々なネットワーク環境に適応。
xDSL〜光ファイバ, ファイアウォール/NAT

池⻑慶彦 (早稲田大学 村岡研究室)
IPA未踏ソフトウェア 2006年度上期 並木PM 首藤一幸 (ウタゴエ (株))

トラフィック削減効果• トラフィック削減効果 90〜95 %– ウタゴエ社 UG Live 使用

2007年 11月 26日

accessのtalk about生中継

配信: Jストリーム,Castella (www.castella.jp),
ウタゴエ

91〜93 % の削減効果

user-side
90%以上の削減が持続

server-sideオーバレイネットワーク (overlay network)• 下位ネットワークとは独立したトポロジを持つ上位ネットワーク

Overlay– UUCP, NetNewsサーバのトポロジ– 電話網上のインターネット– インターネット上のVPN, CDN– MBone, 6bone,– GENI• 米国 NSF のテストベッド構築プロジェクト• 研究者は、自身の “net” を構築• PlanetLab からの強い影響– ここでは特に、大規模な自律分散系• それって (pure) P2P ?

– 多ノード/低管理コスト→ 自律的にオーバレイを構成Router

Physical Network

Unstructured と Structured• 非構造化 (unstructured) オーバレイ– 例： Gnutella ネットワーク, Winnyネットワーク– 誰を隣接ノードとするか、トポロジに制約がない。
– 存在するオブジェクトは、発見できる可能性がある。
– 一般に、効率は良くないが、柔軟な検索が可能。

• 構造化 (structured) オーバレイ– 例： DHT（分散ハッシュ表）のネットワーク– 誰を隣接ノードとするか、トポロジに制約がある。
– 存在するオブジェクトは、（たいてい）発見できる。
– 一般に、効率は良いが、柔軟な検索が苦手。

構造化オーバレイの基本• ノード（計算機）とオブジェクトの両方にIDが振られる。
– IDはたいてい整数値。160ビットだったり 128ビットだったり。
– オブジェクト：任意の文字列だったり、ファイルだったり、プロセスだったり。

• ノードは、ID空間中のある範囲を受け持つ。

– だいたい、ノードのIDと数値的に近い範囲を受け持つ。

• IDを宛先としてルーティングが行われ、その行き着く先は、そのIDを受け持つ担当ノードとなる。
2 -1 0 1
160

ノード

ID空間

2…
ノード

ルーティング
要求①（応用によっては）返答

構造化オーバレイの基本• 肝は routing / forwarding• 資源にかかる負担が、ノード数 n として O(log n)。
– forwarding 時のメッセージ数など。
– cf. unstructured オーバレイ上の flooding• 様々なアルゴリズムが提案されてきた。

– CAN, Chord, Tapestry, Pastry, Kademlia, Koorde, Broose, Accordion,ORDI, DKS, D2B, Symphony, Viceroy,• 構造化オーバレイ上に、いろいろなサービスが載る。

– 分散ハッシュ表 (DHT), マルチキャスト, メッセージ配送,

Tier 2Tier 1
Tier 0CFSPASTDHT

I3 Scribe SplitStream Bayeux OceanStoreCAST DOLRKBR API

Key-based Routing Layer (KBR)
Cited from [Dabek03]

構造化オーバレイの応用例• BitTorrent クライアント– eDonkey2k (hybrid P2Pプロトコル) から派生した Kad
Network。eMule 等が実装。
– BitTorrent、Azureus のトラッカーなし動作• Azureus: 100万以上のノード• DNS– “A Comparative Study of the DNS Design with DHTBased Alternatives”, Proc. INFOCOM 2006.

• その他、もろもろの名前解決や位置解決– ホスト名 → IPアドレス, 名前 → 電話番号, 曲名 → 楽
曲ファイルやそのURL などなど。

オーバレイ織り器• (構造化) オーバレイ関係の名前には、糸を織るというアナロジが見られる。
– Chord -- 弦
– Tapestry -- 壁掛けの織物– Pastry -- 練り粉, パイの皮 ??

• Overlay Weaver-- (structured) オーバレイの織り器– Weave -- 織る, 編む– Weaver -- 織り手, 織工, 編む人

WeaverTapestryのロゴ

Overlay Weaver• 構造化オーバレイ• 特徴– 分散ハッシュ表 (DHT) だけじゃない。
アプリケーション層マルチキャストも。
ライブラリ– 記述言語は Java。
– 約 ３万ステップ。
• ４万８千行。

– Apache License 2.0。

• いろいろな目的に使いやすい。

– ルーティングアルゴリズムを差し替え可能：

Chord, Kademlia, Koorde, Pastry, Tapestry– コーディングなしで運用や実験が可能。

• サンプルツール (DHTシェル等) を使った運用。
• エミュレータを使った実験: メッセージ数やホップ数の計測。PC 1台で 70,000ノード動作。

– 動作状態を可視化して楽しめる。デモできる。
– XML-RPC 経由で DHT を使える。

• Bamboo, OpenDHT と同じプロトコル → 同じクライアントを使える。

可視化ツール– 地球規模テストベッド PlanetLab 上で運用している。
• 35ヶ国 418台

オープンソースソフトウェア,研究プラットフォームとして• http://overlayweaver.sf.net/ (SourceForge)– 2006年 1月 17日、リリース。
– Apache License 2.0• 状況 (2008/5/17 23時)

– ダウンロード 9,500件。
– メーリングリスト登録数• 英語 71名, 日本語 90名– Mixi コミュニティのメンバ数 152名

• 研究プラットフォームとして– ブラジル, ロシア, 英国, ハンガリー,– 第三者が、ルーティング方式を追加実装:
Symphony, EpiChord,– 第三者による利用 / 応用多数:

RDFのDB(産総研), XMLデータ検索(筑波大), 複製数の影響(U Federal do Rio Grande do Sul), 複数サーバの横断検索(お茶大), ウェブアクセス動向集計(東工大), 複製配置手法(早大), コミュニケーション向けユーザ管理サーバ(日立),多次元範囲検索システム(NEC),

ウェブサイト研究プラットフォームとして• churn 耐性の評価と向上手法– 首藤, “下位アルゴリズム中立なDHT実装への耐churn手法の実装”, 情処ACS論文誌, 2008年3月.

• collective routing– 首藤, 中尾, “構造化オーバレイでの一括ルーティング”, OS研究会 (SWoPP), 2008年 8月.

PlanetLab 上での運用• 実機上、できればインターネット上で、実際に大規模な試験・運用を。

• PlanetLab: 地球規模テストベッド– PC 2台を供出すれば、使える。

• プロジェクトごとにVM (Linux-VServer) を用意できる。

– ただし、企業の fee は $25,000 / 年〜！
– 客員研究員として、大学を PlanetLab に参加させた。
– 最大で、35ヶ国 418台で動作。

PlanetLab上で運用しているノードのウェブインタフェース

デモ• 可視化ツール: Overlay Visualizer• PlanetLab 上の DHT に対する操作

Overlay Visualizer• ノード, メッセージ, マルチキャストの配送木を、実行中に可視化。
• 実ネットワーク / エミュレータどちらでも動作。

ノードのウェブインタフェース• ノードについての諸元。

• Chord の経路表。

ウェブインタフェース• 分散ハッシュ表 (DHT) への put, get, removeウェブインタフェース• DHT からの get の結果。

PlanetLab の資源利用状況• CoVisualize