スライド 1

第十二講

ネットワークアーキテクチャ

2006年度秋学期 授業日程 （後半）

z 11/14 Internet Protocol version 6

z 11/28 移動体通信技術 （代講 三屋光史朗）

z 12/05 次世代トランスポート層技術 （代講 西田佳史） z 12/12 コネクションレス型の通信技術とサービス

z 12/19 P2P通信技術

クライアントサーバモデル（例：WWW）

Client

Client

Request Request Data Data

Server

クライアントサーバモデルの特徴（例：WWW）

各計算機の役割に注目

Server

Client

Client

Request Request Data Data 役割が明確に分割されているモデル

クライアントサーバモデルの特徴（例：WWW）

計算機資源に注目

Server

Client

Client

Request Request Data Data クライアントからの要求に 応じて消費される資源 ・CPU ・メモリ ・ハードディスク など 処理負荷がサーバに集中するモデル

クライアントサーバモデルの特徴

ネットワーク資源に注目

Server

Client

Client

Request Request Data Data ネットワーク負荷が集中するモデル

クライアントサーバモデルの特徴

z

メリット

z 管理者にとってサービス管理が容易 z 課金サービスモデルの構築が容易 z クライアントの計算機資源への負荷減少 z

デメリット

z Single Point of Failure（詳細後述） z サーバの計算機資源への負荷集中

クライアントサーバモデルで

規模性を実現する手法

Single Point of Failure

z ボトルネック z サーバの計算機資源 z 途中経路のネットワーク資源 z ボトルネック解消のアプローチ z ロードバランシング z DNSを利用したもの z WEBキャッシュ z Accelia Durasite z Akamai z それぞれ目的に応じた効果が得 られる Clients Server アクセスの集中による 回線の飽和 サーバのダウン

例:IRCの負荷分散方法(1/5)

z IRC(Internet Relay Chat):チャット専用アプリケーション

z _{CHOCOA:http://www.labs.fujitsu.com/free/chocoa/} z LimeChat:http://www.dive-in.to/~mb-arts/ z RFC1459 z 一つサーバに 処理が集中しない Client 3 Server 4 グループに1,2,3が 加わってる場合 Server 4にはグループに加 わったクライアントがない ためメッセージはこない Client 1 Client 2 Client 4 Server 1 Server 2 Server 3

Hi!

Hi!

Hi!

例:ロードバランシング(2/5)

z 同じIPアドレスで複数のサーバが反応 z ラウンドロビン、URLで、重み付け、負荷、コネクショ ン数、反応速度などで割り振る z 利点 z CPU負荷を軽減できる z 問題点 z ログが分割される z メンテナンス負荷は高くなる

コネクション要求

負荷分散装置

例:ロードバランシング(3/5)

z 同じIPアドレス(Anycast)で複数 のサーバが反応 z ルーティングにより最短のサー バが選択される z 負荷分散装置と似ているが z 実際に複数のマシンで同一の anycastアドレスを使ってルー ティングしている z 地理的／ネットワーク分散が可 能となる

コネクション要求

例:DNSを利用した負荷分散(4/5)

z 同じ名前で複数のサーバが登録されている z 物理的に別の場所で処理 z www.asahi.comなど z 利点 z 回線資源を 分散利用できる z 問題点 z 均等に負荷が 分散されない z 落ちている サーバにも振る z Cacheがあるため タイムラグがある www.asahi.comどこ？ Client 1 Client 2 www.asahi.comどこ？ 209.249.129.20 Wwwld2.asahi.com 210.80.197.158 Uunet3.asahi.com 209.249.129.20だよ 210.80.197.158だよ

例:キャッシュを利用した負荷分散(5/5）

z _{Accelia Durasite} http://www.accelia.net/japanese/news/12.html z ファイルを広域に分散しネットワーク負荷を分散 z _Akamai http://www.akamai.com/ z クライアントに一番近い、最 適なキャッシュを探す z サーバのかわりにキャッシュ がクライアントに応答 z 利点 z CPU資源の分散 z 回線資源の分散 Clients Server キャッシュを拠点に置き アクセスを分散させる コンテンツの配置 Cache Servers

P2Pモデル登場の背景

z エンドノードの計算機資源の潤沢化 z 演算処理能力の向上 z ハードディスク容量の増加 z インターネットの普及 z ネットワークの広範囲化 z ネットワークの広帯域化 z インターネット接続ノード数の増加 z クライアントサーバモデルの問題点 z Single Point of Failure

CPUの処理能力の推移

HDD容量の推移

P2Pモデルの特徴

z Peer z 同格、同等の相手 または 関係 z P2Pネットワークに参加する計算機を指す z 各計算機は対等な関係を持つ z サーバ・クライアントという関係ではない z 各計算機は複数の役割を動的に使い分ける z サービスの受信 z サービスの中継 z サービスの送信 などなど

クライアントサーバモデルとP2Pモデル

Client Server Hybrid P2P Pure P2P

サーバ 検索・発見の インデックス サーバ サーバ サーバ クライアント（ピア） サーバ クライアント（ピア） クライアント（ピア） データ 情報の検索 データの所在 クライアント

WWW, DNS Napstar, Messenger Gnutella, Winny

ハイブリッドP2Pモデル（第１世代P2P）

z 特徴 z サーバは検索・発見のインデックスを管理 z サービスの送受信はピア間で行われる z チャットアプリケーションやファイル共有ソフト（Napster）が利用 z 利点 z サーバの計算機資源への負荷を軽減 z ネットワーク負荷を分散 ①サービスの検索 ②サービスの送受信 サーバ ピア ピア

MSN Messengerの仕組み

ファイル転送 メッセージ メッセージ ・セッションの開始 ・コンタクトリスト サインイン情報 メッセージの送受信 ファイルの送受信 サインイン時の通信 サーバ

ハイブリッドP2Pモデルとファイル共有

z Napster

z Napster社のファイル共有ソフト

ハイブリッドP2Pモデルとファイル共有

z

インデックスサーバの利用

z 所持ファイルの一覧をサーバに送信 z 検索条件をサーバに送り、結果をもらう z 公開されているファイルをサーバが制御できる ファイルの検索 ファイルを取得 自分の持つファイルを登録

ハイブリッドP2Pモデルの特徴

z Single Point of Failure

z インデックスサーバ無し では機能しない z 世界中からの検索要求 の処理負荷は膨大！！ z サーバがダウンすると サービス全体がダウン z サービスを管理可能 z サーバを管理することで サービスの管理も可能 Hybrid P2P

ピュアP2Pモデル（第2世代P2P）

z

Single Point of Failure

からの開放

z 耐故障性 z 故障ノードの役割を他ノードが引継ぎ可能 z 資源分散 z 計算機資源への負荷分散 z ネットワーク資源への負荷分散 z

サービス管理が困難

z 中央制御機構が存在しない z ピアが協調することで検索、中継、データ交換を実現

ピュアP2Pモデルとオーバーレイネットワーク

z オーバーレイネットワーク（P2Pネットワーク） z ピュアP2Pモデルを実現するためのネットワーク z 一般にアプリケーション・サービス毎に構築される z ピアが協調することにより自立的に管理・構築される サービスA サービスB

トポロジを考慮しないデメリット

z

IPネットワークのトポロジとの分離

z 自分が手をつないでいる相手は地球の裏側かも…… z 実際に転送できる帯域が細い！

ピュアP2Pモデルにおける検索手法

z

インデックスサーバが存在しない

z ノード情報を取得するための仕組みが必要 z IPアドレス、URI、ファイル情報 などなど z

情報の検索方式による分類

z Unstructured z Flooding 方式 z ピュアP2Pで利用されてきた手法（Gnutella, Winny） z Structured

z _{Distributed Hash Table 方式}

Unstructured P2P

z Gnutella, Winny z P2Pネットワーク上で検索要求を転送 z 検索者が積極的にファイルを探しに行く。 z ファイルの所持者は受動的 ①検索メッセージを送信 ②検索メッセージを送信 ②検索メッセージを送信 ③検索応答を返す

Unstructured P2P と Time To Live

z

データ転送回数の上限

z 中継する毎にTTLを1つ減らし、0になったら破棄 z Gnutellaでは検索要求を7回まで中継 TTL -1 Source Peer Peer Peer Peer TTL=0になった 報告 TTL -1 通信開始 IPにおけるTTLの扱い

Unstructured P2Pの問題点と解決手法

z

Unstructured P2Pの問題点

z ネットワーク負荷の増加 z Floodingを利用するために通信量が増加 z 検索範囲が狭い z 検索範囲はTTLによって限定されるため、 検索対象が発見できない可能性がある z

いくつかの解決手法

z Structured P2P を利用する z P2Pネットワークの階層化 z アプリケーションの動作を工夫（Winnyを例に後述）

Structured P2P

z

Unstructuredに比べ検索効率が高い

z

検索時のトラフィックの抑制を実現

z

Distributed Hash Table

（分散ハッシュ表）

を利用

z 検索対象の発見を効率化する仕組み

z 検索対象を複数のノードで分散管理する仕組み

z 提案されているDHTプロトコル

z Chord, CAN, Pastry, Tapestry, Kademlia, etc..

z DHTを実装しているソフトウェア

z BitTorrent, Warez P2P, eMule, etc..

ハッシュ値とハッシュ関数

ハッシュ関数ではA≠Bの場合、F(A)≠F(B）が成り立つ

ハッシュテーブルとは

z キーと値の組（エントリと呼ぶ）を複数個格納し、キーに

対応する値をすばやく参照するためのデータ構造

DHT関連の論文

z Ion Stoica, Robert morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan, Chord: A Scalable Peer-to-Peer Lookup

Protocol for Internet Aplications, IEEE/ACM Trans. Networking, Vol.11, No.1, p.

17-32, Feb. 2003.

z Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, A

Scalable Content-Addressable Network, In Proc. ACM SIGCOMM 2001, August

2001

z Antony Rowstron and Peter Druschel, Pastry: Scalable, decentraliszed object

location and routing for large-scale peer-to-peer systems, Lecture Note in

Computer Science, Vol.2218, pp. 329-350, 2001.

z Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph, Tapestry: An

Infrastructure for Fault-tolerant Wide-area Location and Routing, Technical

Report UCB/CSD-01-114, Computer Science Division, U. C. Berkeley April 2001, 55

z Petar Maymounkov and David Mazieres, Kademlia: A Peer-to-peer Information

System Based on the XOR Metric, In Proceedings of IPTPS02, Cambridge, USA,

P2Pネットワークの階層化（Kazaa, Skype）

z スーパーノードが連携してインデックスを管理する スーパーノードクラスター 情報の保持 情報の保持 情報の保持 1.ファイル検索要求 2.ファイル検索 3.ファイル転送 内部ではDHTを利用

Skypeの場合

z ノード z _{NATやファイアウォールによって内向きの接続ができないこともある} z スーパーノードへ接続することでP2Pネットワークへ接続する z スーパーノード(リレーノード) z スパーノード同士で通信し、ユーザー情報を同期する z P2Pネットワークトポロジーの形成 z Firewall/NATでノード同士の直接通信ができない場合の中継役中継

z NMS（Network Management Server）

z 唯一、Skype(Skypeを作ってる団体)が管理する z スーパーノードの紹介

Skype通話の仕組み

A

B

スーパーノードの条件 •グローバルIPアドレス •マシン性能が良い •回線速度が速い •Skype起動時間が長い、など 1、BのIPアドレス問い合わせ 2、BのスーパーノードがIPアドレスを返信 3、通話の開始

ピュアP２Pのアプリケーション詳説

Winny (P2Pファイル共有ソフト)

z Winnyの特徴 z Unstructured P2P z トラフィック量が多い z 検索効率の向上 ƒ 公開者による広告機能 ƒ ピアによる複製・中継機能 z ファイルの冗長性確保 z 中継時のキャッシュ機能 z 匿名性の実現 z ファイルの暗号化 z 第三者によるファイル転送 z 2002年度「ベスト・オブ・悪用厳禁ツール」 z 参考文献： 『Winnyの技術』 金子 勇 著、アスキー刊、2005年

Winny（P2Pネットワークへの参加）

z

WinnyはピュアP2Pモデル

z 初期ノードを手動で登録する必要がある z

手動でIPアドレスとポート番号の情報を入力

z 一般的には、掲示板等を通して教えてもらう z 情報はハッシュ化されている z 人間が見ても、分からないような文字列 http://winny.cool.ne.jp/lesson1/node.html より、モザイク追加

Winny ネットワークの階層化

z

Winny が起動すると、2つの上流ノードを検索

z 冗長性のために２つ以上の上流ノードが必要 z 上流ノードがいなくなったら、新しく検索する z

検索リンクの接続は5つまで受け入れる

z 下流ノードが多すぎると接続出来ないノードが現れる 上流ノード 自分 下流ノード

Winnyにおける上流・下流の定義

z

回線速度によって階層分け：

z 上流ノード： 高速回線を使用しているノード z 下流ノード： 低速回線を使用しているノード z

検索は自身より上流のノード

だけ

へ問い合わせ

z 帯域の太いノードに、一方通行 ⇒ クエリの効率化 高速 (FTTH等) 中速 (ADSL等) 低速 (ISDN等)

Winnyネットワークの最適化（クラスタリング）

z ユーザの嗜好性に合わせて接続をする z 検索キーワードの似ているノードを選択 z 効率的なファイル転送 z その内、嗜好性によるクラスタリングが成立 z その嗜好性に応じて、接続を再設定 高速 (FTTH等) 中速 (ADSL等) 低速 (ISDN等)

ファイルの多重ダウンロード

z ファイルはブロックに分割し、キャッシュ z 途中で失敗しても、失敗したブロックから再送 z 同じファイルを複数のノードが持っている場合、複数のノードか ら並行してダウンロード z 1つのノードの帯域が細くても、複数のホストから ダウンロードして高速化 高速 (FTTH等) 中速 (ADSL等) 低速 (ISDN等)

Winny と IPネットワーク

z

Winny ネットワーク： インフラ（IPネットワーク）の

上に、アプリケーションレベルで作るネットワーク

z 実際のインフラのトポロジとは関係が無い z 例えば実際のトポロジでは隣にいるノードでも、 持っているファイルの嗜好性が違えば（＝違う クラスタなら） Winny ネットワークでは遠い存在 IPネットワーク

Winnyネットワークにおける検索処理

z

Winnyでは公開者も積極的に広告を行う

z 公開者は、ファイルの情報を隣接するPeerに広告 z 広告情報と検索要求を各Peerが比較 あのファイルが欲しい… 皆に聞いてみよう！ 持ってないよ！ 持ってないよ！ 持ってないよ！ Bさんのファイ ルをAさんが 探してる！！ Bさんがあの ファイルを持ってる Bさんがあの ファイルを持ってる このファイルを持ってることを 皆に教えてあげよう！ Aさん _Bさん Cさん

広告

Winnyにおける中継転送

z

中継転送

z P2Pネットワークでの中間のPeerが転送を中継 z 転送のパフォーマンスを犠牲にすることで、キャッ シュ_{を持つPeerを増やし冗長性を確保} Bさんのファイルを 中継してあげよう！ Aさん _Bさん Cさんが持ってたんだね！ 私のファイル人気があって 配るのが大変…… Cさん

Winnyにおけるキャッシュ

z

キャッシュ

z ファイルを取得したPeerや、中継転送したPeerがそ のファイルの複製を第三者に自動的に再公開 z 耐故障性の実現(冗長性の確保) z 検索効率の向上 Aさん _Bさん Cさん このファイルを他の人に も配ってあげよう！ 中継したファイルを他の人 にも配って良いよね！ 他の人も配ってくれると 楽で良いね！

Winnyにおける匿名性の実現

BからAへのファイル転送

1. BがFileを持っているという情報 が流れる (①) 2. Aは近くのマシンからFileの検 索を行う (②₎ 3. Cによって, AはFileをBが持っ ているとわかる 4. CはBへ, Fileを要求する 5. AはCへ, Fileを要求する

C

①

②

②

B

File

①

* ファイル転送に他のマシン(C)を 経由するため, 当人同士(AとB)は 繋いでいる相手が特定できない

A

Winnyにおける通信の暗号化と完全性

B

A

C

File

z 通信の暗号化 z 転送されるファイル z 中継ノードに残るキャッ シュファイル z 通信の完全性 z MD5による破損, 改竄検 出 z 一定ブロックごとにチェック

BからAへのファイル転送

File

Cache * ファイル転送を中継したノード(C) は, 転送したファイルのタイトルや内 容を知ることはできない 暗号化

Winnyの技術

z 検索範囲の拡大 z 中継ノードが検索と広告を組合わせる z 検索効率の向上 z コンテンツの嗜好に応じたクラスタリング z 中継ノードがコンテンツの複製を持つ z ファイル取得効率の上昇 z 多重ダウンロードの採用 z 参加者の匿名性の保守 z ファイルの暗号化 z 中継ノードを介したデータ受信 Unstructured P2Pの 欠点は減少させるが トラフィック量は増加 著作件侵害に関連 する技術的トピック

Winnyとネットワークトラフィック

z 2003年11月27日に逮捕者が出た段階で日本中のトラフィッ

クは2割減少した

IPマルチキャスト技術の問題点

Source 10Mbps 10Mbps 10Mbps 10Mbps マルチキャスト対応ルータに求められる機能 ・マルチキャストグループ管理 ・マルチキャストルーティング IPマルチキャストを利用するにはルータのマルチキャストサポートが必要不可欠

オーバーレイマルチキャスト技術

Source オーバーレイリンク オーバーレイマルチキャストの特徴① ・マルチキャストルータ不要 ・アプリケーション間で勝手にツリー構築

オーバーレイマルチキャスト技術

Source オーバーレイリンク 20Mbps 10Mbps 10Mbps オーバーレイマルチキャストの特徴② ・物理トポロジ依存しない配信であるため、ツリーの 構築基準次第でネットワーク負荷が高くなることがある ※例えばコンテンツの嗜好でクラスタリングするなど。。 30Mbps 20Mbps

オーバーレイマルチキャストの難しさ

z

コンテンツのリアルタイム性の維持

z 伝送遅延を出来る限り抑えた効率的な配信が必要 z 配信ツリーの構築基準の選択が重要！！ z 不適当なメトリックに応じてツリーを構築すると… ƒ 不必要なネットワークトラフィックが増加してしまう ƒ 同じ内容のデータがネットワーク上を行ったり来たりする z 構築基準の例

ƒ RTT（Round Trip Time）

ƒ 計算機の処理能力 ƒ リンク帯域の大きさ

オーバーレイマルチキャスト実現の一手法

z Naradaの場合 z 1. コントロール・トポロジの作成 z 各ノードがお互いの生存確認 を行い、トポロジの分離を回避 z メッシュと呼ばれる事が多い z 2. データ・トポロジの作成 z コントロールトポロジを利用し て配信ツリーを構築する z DVMRPを利用

オーバーレイマルチキャストと符号化技術

z

アプリケーション層でマルチキャストを実現

z 中継ノードは様々な処理をアプリケーション層で実現

z データ量の削減 （Layered Coding）

z 再エンコーディング （Network Coding） などなど

P2P流通網への期待

z P2P流通網への期待 z 流通の中抜きによる価格引下げ z 著作者からユーザーへの直接的な流通の可能性 z コスト問題から無視されてきたマイナー著作物の流通整備 z 参入コストの低さによる様々な著作物の流通市場の整備 z P2P流通網の整備に必要とされる要素 z セキュリティ対策 z コピープロテクト対策 z プライバシー保護対策 z 課金/コンテンツ配信モデル z ネットワークトラフィックの低減

P2P時代のビジネスモデル

z ビジネスモデルがしっかりしていれば、みんな買う z iTunes Music Store

z 99セントで、欲しい曲がすぐ、簡単に、正規に手に入る

z Skype

z Skypeユーザ同士の会話はただ

z 公衆電話網と接続したり、ボイスメールに課金

P2P技術と分散処理

z ネットワークに繋がったコンピュータ群を一つのコン ピュータと見立てる z → Gridコンピューティングの発想 z 電力網を意味する「Power Grid」に由来 z 他人の余っている資源を拝借する z 自分の余っている資源を提供する z 資源 z CPU z HDD z 回線帯域 z CPUを束ねて高速な処理を行うだけでなく、データストレージを 束ねて大規模なデータベースを構築するといったことも 。

資源共有、分散データストア： OceanStore

z

世界中の計算機で共有される巨大ストレージ

z 地球規模を想定 z 100億台のコンピュータ z 1010テラバイト(1億PB)のデータ z ピュアP2Pモデル P2Pネットワーク全体が一つの巨大なファイル置き場

処理分散、巨大計算機：SETI@home

z SETI（Search for

Extra-Terrestrial Intelligence: 地球外知性探査） z 地球外からの電波を探査し、 知性の証拠を探る計画 z 膨大な資源が必要 z 電波望遠鏡での観測時間 z データ解析のCPU時間 z SETI@home z 世界中のマシンの空き時間 を用いてデータを解析 z _{39万のユーザ (2005年8月)} http://setiathome.ssl.berkeley.edu/

All IP Computing

z 各パーツ(CPU, Memory, DISK, Display, Keyboard,

Mouse等)がそれぞれ内部バスによって接続されている z ネットワークが高速となった今、バスもIP化できないものか？ z 利用例 z 家から大学のコンピュータに、手元のキーボード、マウス、 Displayを使って操作（IPネットワークで計算機をグルーピング） z スーパコンピュータでは計算機の数が膨大になるため、共有で きるリソースは共有した方がコスト／スペース的に有利（キー ボード、ディスプレイ他）

All IP Computing

z いくつかのデバイスは既にトライされてきている

z iSCSI(ネットワーク型ストレージ）

z _{USB/IP Project (http://usbip.naist.jp/)} z AnywhereUSB (http://www.ibsjapan.com/ION/AnywhereUSB.htm) z 現在、村井研究室では東京大学との共同研究で実証実験／研究 開発を行っている段階 z 超低遅延高速(光)ネットワーク技術 z IP/UDP/TCP/AnyL4のチューニング z _{IPの周辺技術（デバイスのバインド、デバイス探索他）} z 興味がある人は是非コンタクトください([email protected]) www.digi.comより

最終課題

z 下記の内容を7000字以内でまとめよ z これからのインターネットに求められる新しい機能要求を示し、その機 能を実現するための仕組みを示せ。その際、どの階層にどのような新 しいプロトコルが必要か、あるいはどの既存プロトコルの改良が必要 かを技術的に述べよ。 z これまでの機能要求（例） z 広帯域、低遅延、信頼性、認証・セキュリティ、リアルタイム通信、QoS、 P2P技術 など z

１月２３日11:59PMまで

z 注意点 z 提案の妥当性、オリジナル性を評価します z SOIのシステムを利用し、提出すること z 遅れた場合は採点しません z 他の文献/WEBサイトを参照した場合は必ず参考文献をつけ、 出元を明確に せよ。参考文献なしの引用は不正行為