Live E! シンポジウム 2008,
東京大学, 2008年9月19日(金)オーバレイ・センサネットワーク～ オーバレイネットワークへの期待

首藤 一幸

情報通信研究機構 (NICT) 客員研究員

内容• オーバレイネットワーク– 非構造化 / 構造化オーバレイ• 非構造化オーバレイの基本と実例– Peer-to-peer ライブ配信• 構造化オーバレイの基本と実例– Overlay Weaver とその PlanetLab 上の運用

• オーバレイへの期待– ストレージ, データ処理, …

オーバレイネットワーク
非構造化オーバレイと構造化オーバレイ

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

Overlay

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

– 狙い: 多ノード / 耐故障 / 低管理コスト→ 自律的にオーバレイを構成

RouterPhysical Network

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

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

非構造化オーバレイの基本と実例- 基礎: Gnutella プロトコル- peer-to-peer ライブ配信

Unstructuredオーバレイの例:

Gnutella プロトコル (0.4)• 各ノードは、一定数の隣接ノード (neighbor) を持つ。
– どのノードを隣接ノードとするか、および、隣接ノードの数はアプリ依存。例えば 4。

• 検索時、各ノードは問い合わせを全隣接ノードに転送する → flooding– TTL（time-to-live, 最大ホップ数）は 7。
– 返答は、転送経路に沿って返される。
問い合わせ

①

①
①⑤

②
④

返答

③ 持ってる！

• Gnutella プロトコル 0.6 は、super-peers の概念を採り入れた。

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

cf. YouTube, ○○動画

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

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

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

IPA未踏ソフトウェア 2006年度上期 並木PM

配信元
①リクエスト②データ

各ノードで、周辺状況を可視化

全ノードの接続状況を可視化

UG Live: トラフィック削減効果• 視聴側トラフィックに対する配信側トラフィックが、わずか数%→ 90% 以上の削減効果
2007年 11月 26日

accessのtalk about生中継

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

91～93 % の削減効果

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

server-side事例: UG Live

鹿島アントラーズ戦
音声 ライブ配信
協力： J ストリーム様•２回 / 月 程度
•2007年 4～12月•2008年 4～12月

事例: UG Live

早稲田祭 2007 のステージ中継 (2007/11/3～4)
協力： 早稲田大学 後藤研究室 様非常に高いビットレート 2 Mbps

事例: UG Live

24インチLCDでの視聴に耐える品質

人工衛星「きずな (WINDS)/ H-IIAロケット14号機 打ち上げ (2008/2/23)
配信： Jストリーム様, ウタゴエ

事例: UG Live

スペースシャトル打ち上げ,「きぼう」日本実験棟 組み立て (2008/6/1-15)
配信： Jストリーム様, ウタゴエ

アプリケーション層マルチキャスト (ALM) の手法:

ツリー型 vs. メッシュ型
配信元

配信元
データ

②データ

①リクエスト配信木• ツリー型– 明示的に作ったトポロジがデータ流路。
– 根から葉に向かってpush。
– △ ノード故障時は、要 迅速な復旧。
– ○ 末端まで確実に届く。配信遅延 小。
–
広い上り帯域幅を使い尽くし得る。

• メッシュ型– 隣接ノードと緩やかな関係を保つ。
– 隣接ノードからpull。

– ○ 生来、ノード故障に強い。
– △ 末端まで届く保証なし。要 補償策。
–
狭い上り帯域幅を使い尽くし得る。

技術の詳細• メッシュ型の最初の提案は、香港の大学 & カナダの大学から。

– X. Zhang et al.: CoolStreaming/DONet: A Data-Driven Overlay
Network for Efficient Live Media Streaming, Proc. INFOCOM 2005.

• ウタゴエでの研究・開発:
現実のインターネットでうまく動かす– 隣接ノード数の調整アルゴリズム– 上り/下り帯域幅の差への配慮 (秘密の技術アリ)– 配信元ノードからデータがスムースに出て行く工夫– バックアップの仕掛け– NAT越え, ウェブとの連携, …

研究 (例): 隣接ノード数の調整• 帯域幅等に応じて、動的に調整。
隣接ノード数の評価
1000ノード 映像帯域340kbps
10090806050

系列140302010

隣接ノード数

N=20

N=19

N=18

N=17

N=16

N=15

N=14

N=13

N=12

N=11

N=10

N=9

N=8

N=7

N=6

N=5

N=4

N=30

提案手法

Delivery Rate70

構造化オーバレイの基本と実例
Overlay Weaver とその PlanetLab 上の運用構造化オーバレイの基本• ノード（計算機）とオブジェクトの両方にIDが振られる。

– IDはたいてい整数値。160ビットだったり 128ビットだったり。
– オブジェクト：任意の文字列だったり、ファイルだったり、プロセスだったり。

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

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

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

ノード

ID空間

2…
ノード

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

構造化オーバレイの基本• 肝は routing / forwarding• 資源にかかる負担が、ノード数 n として O(log n)。
– forwarding 時のメッセージ数など。
– cf. 非構造化オーバレイ上の 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 DOLR

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台で 15万ノード動作。

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

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

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

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

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

• 研究プラットフォームとして– ブラジル, ロシア, 英国, ハンガリー, …
– 第三者が、ルーティング方式を追加実装:
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 に参加させた。
– 最大で、34ヶ国 490台で動作。

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

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

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

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

• Chord の経路表。

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

PlanetLab の資源利用状況• CoVisualizeオーバレイネットワークへの期待センサネットワークの基盤に• できないか？
• したい！
• …という人達が盛んに研究を推進中。
• オーバレイの活かし方– ストレージ• 分散ハッシュ表 (DHT) にセンサデータを格納– 範囲検索もしたい → 奈良先端, NEC, …の研究, SkipGraph, …

• ノードが担当地域を動的に調整するオーバレイ by 松浦先生 (奈良先端)– データ処理, 計算• データ融合 (fusion) - 今後のPIAX (阪大)• 分散処理の途中データを DHT に格納して、再利用 (東大)• オーバレイをプログラミング– E.g. Overlay GHC by 斉藤先生 (慶應)コミュニティ, 情報交換
• 広域センサネットワークとオーバレイネットワークに関するワークショップ– http://live-e.naist.jp/sensor_overlay2008/

第二回を近日開催予定