自律分散協調システム論 第8回「インターネットにおける自律分散協調」 中村 修 osamu@sfc.wide.ad.jp
担当 今週から 教員 アシスタント 主にインターネットにおける自律分散協調システムの実際について取り扱います 中村修 (osamu@sfc.wide.ad.jp) アシスタント 三島 和宏 (D2) (three@sfc.wide.ad.jp)
自律分散協調 ヤッターワンとヤッターメカ たちこま
システムの自律分散協調 自律 分散 協調 各要素が 主体的に動作 自律している例 PC 自律してない例 X端末 銀行ATM 各要素が複数、 空間的に離れて いる 分散している例 各支社ごとの 電話窓口 分散してない例 本社だけの 電話窓口 協調 相互に作用し、 全体の機能を 形作る 協調している例 一般的な会社 の部署 協調してない例 役所の縦割り 行政
インターネットにおける自律分散協調 インターネット自身 インターネット上の様々なシステム ネットワーク同士の相互接続 LAN(キャンパスLANや家庭内LANなど）が相互に接続して、地球を包むインターネットと呼ばれる１つのシステムとして稼働している。 インターネット上の様々なシステム 負荷分散などのための様々なシステム Winnyに代表されるP２Pシステム
Internet：まさに自律分散協調システム Internetの起源は、ARPAnet DARPA(Dept. of Advanced Research Project Agency)が、次世代の通信の研究開発に資金提供 目的：耐故障性にすぐれた通信システム - 高機能中継システム v.s エンドノード制御システム - 回線交換 v.s パケット通信 - 集中経路制御 v.s 分散経路制御 成果の証明： 湾岸戦争
ベストエフォート型通信システム Guaranteed Network v.s Best Effort 知性はネットワーク エンドノードは、従属的機械 知性は、エンドノード ネットワークはベストを尽くす
集中制御システムと分散システム 集中モデル 分散モデル 偉い人がいて、権利を 一手ににぎっている そいつが狂うと大変 偉い人がいない 権利は委譲されている どれかが狂っても全体に影響は少ない
堅牢性 一つの要素が故障や攻撃などで使用不能になった場合でも、全体に影響は少ない 例：どのノード・リンクが異常をおこしても接続性がある
電車・地下鉄における自律分散協調 乗り入れ 振り替え輸送 ダイヤの調整 例：東西線から東葉高速線に 運賃の振り分けが二社間で決められている ある線が運行不能になったときに、他社の路線へ振り替え 切符・運賃の扱いが二社間で決められている 耐故障性を提供 ダイヤの調整 乗り換え・終電など
経路制御の基本 隣同士で経路情報 （道案内の情報）をやりとり 隣より先は基本的に知らない つながっている全ての要素が情報をやり取りして、全体の接続性を提供する AS 1 AS 2 AS3 ASを通じた経路制御 （詳細は後述）
Internet Architecture
経路 ある宛先へ到達するために、IPパケットを送信・転送する先 宛先が同一リンク上なら直接配送 宛先が同一リンク上にない場合は中継ノード (ルータ)を経由 ルータ ルータ
経路表とIP Forwarding 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 prefix Next-hop 10.0.0.0/24 ルータA 172.16.0.0/24 ルータC ルータA ルータB ルータC 10.0.0.0/24 172.16.0.0/24 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
経路表の更新 ネットワークの構成変更がおこったら？ 全てのノードの経路表を更新を行う必要がある 新しいネットワークが追加されたら？ 停電などによって通信先のルータが落ちたら？ 全てのノードの経路表を更新を行う必要がある prefix Next-hop 192.168.0.0/24 ルータB 172.16.0.0/24 prefix Next-hop 10.0.0.0/24 ルータA 172.16.0.0/24 ルータC prefix Next-hop 10.0.0.0/24 ルータB 192.168.0.0/24 172.16.1.0/24 ルータB 172.16.1.0/24 ルータC ルータA ルータB ルータC 新しいネットワーク 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 172.16.1.0/24
静的経路制御(Static Routing) 動的に経路が変化しない 障害発生時 代替経路があっても、静的に 設定された経路のみを利用 管理者による設定変更が必要 Internet 障害発生 10.0.0.3 10.0.0.2 Next-hop 10.0.0.3 10.0.0.1の経路表(抜粋) Prefix Next-hop 0.0.0.0/0 10.0.0.2 10.0.0.1 Next-hop 10.0.0.1 到達性のない 経路のみが存在
動的経路制御(Dynamic Routing) 経路制御プロトコル(Routing Protocol)を利用 自動的に各ルータの経路表が設定される 障害発生時 障害を検知し、自動的に 代替経路を選択 障害箇所を迂回するよう 経路表を更新 Internet 障害発生 10.0.0.2 10.0.0.3 Next-hop 10.0.0.3 Next-hop 10.0.0.2 10.0.0.1の経路表(抜粋) 代替経路が 利用される Prefix Next-hop 0.0.0.0/0 10.0.0.2 10.0.0.3 10.0.0.1 Next-hop 10.0.0.1 到達性のない 経路は消去される
経路制御の分割 「AS内の経路制御」 と 「AS間の経路制御」 各ASは異なるポリシ・管理体系 規模性の実現 障害範囲の限定 経路数の軽減 (RIP, OSPF) AS間の経路制御 (BGP) AS内の経路制御 (RIP, OSPF) AS AS AS
ベクタ型経路制御 隣同士で経路交換 A Aはこちら AS 1 Aはこちら AS3 Aはこちら AS 2 最終的にAS3からAへ到達できる 全体を統括しているノードは無い
全体の概観 ネットワークの 相互接続図 多くのリンク 実際にはこのような全体図がなくても動作する（自律分散） 障害への保証 図：AS間の相互接続図
地球規模でのデータベース:DNS ホスト名とIPアドレスの電話帳をどうやってつくる？ 地球規模のデータベースが必要 最初は、/etc/hostsファイルをftp キャンパスレベルならYP、NIS 誰が管理（データのアップデート）するの？どうやって、この情報を配布するの？ DNS 最近は、Chordなど分散ハッシュテーブルの可能性？
名前解決 アドホックに管理 例:Windowsネットワークによるコンピュータ名 グローバルに管理 例:DNSによるホスト名 利便性を重視 一意性を重視 中央集権的なモデル 自律分散的な運用 アドホックに管理 例:Windowsネットワークによるコンピュータ名 利便性を重視 管理コストを軽減 / 全体で一意になる モデル ネットワーク内で すぐに使える 協調しなくともよい 委譲された空間 を管理 NetBEUIプロトコルのWindowsネットワーク AppleTalkのMacintoshネットワーク IPXプロトコルのNetWareネットワーク 両者を協調させるAvtiveDirectoryという仕組みもある。ダイナミックDNSをベースに、DNS構造のもとでホスト名を管理
ドメインツリー ・ jp uk …… com org ad ac co or cnn … keio … sfc cc 階層的な名前空間 Root Domain 階層的な名前空間 例：www.sfc.keio.ac.jp 規模性を実現 ドメインの種類 TLD: Top Level Domain gTLD: generic TLD ccTLD: Country Code TLD SLD: Second Level Domain ・ ccTLD gTLD jp uk …… com org SLD ad ac co or cnn … wide keio … u-tokyo sfc cc www.sfc.keio.ac.jp
名前解決の流れ root ネームサーバ ローカル ネームサーバ jp ネームサーバ ac.jp ネームサーバ keio.ac.jp ローカル ネームサーバ www.sfc.keio.ac.jpを問い合わせ root ネームサーバ jpのネームサーバを返答 www.sfc.keio.ac.jpを 問い合わせ www.sfc.keio.ac.jpを問い合わせ jp ネームサーバ ac.jpのネームサーバを返答 クライアント www.sfc.keio.ac.jpを問い合わせ ac.jp ネームサーバ keio.ac.jpのネームサーバを返答 www.sfc.keio.ac.jpを問い合わせ keio.ac.jp ネームサーバ sfc.keio.ac.jpのネームサーバを返答 www.sfc.keio.ac.jpを問い合わせ www.sfc.keio.ac.jpの アドレスを返答 sfc.keio.ac.jp ネームサーバ www.sfc.keio.ac.jpのアドレスを返答
ドメインとゾーン 階層構造の中の管理単位: ゾーン それぞれのゾーンはいくつかネームサーバにより運営 される ・ jp uk …… com Root zone 階層構造の中の管理単位: ゾーン それぞれのゾーンはいくつかネームサーバにより運営 される ・ jp zone jp uk …… com org jp.ad zone ad ac co or cnn … wide keio … u-tokyo sfc cc www.sfc.keio.ac.jp
ゾーンとネームサーバ 名前と値の対応情報はそれぞれのゾーンで管理される “ドメイン”は名前の管理上の境界 “ゾーン”は対応データベースの管理上の境界 １つのゾーンにつき、いくつかの（全世界に向けて）返答できるネームサーバが動作 複数のゾーンに関して１つのサーバで管理 することもできる
ゾーンの管理と委任 jpドメイン ac.jpドメイン 委任 管理 keio.ac.jpドメイン 委任 委任 jpゾーン 管理 sfc.keio.ac.jp ドメイン 管理 管理 keio.ac.jpゾーン ac.jpゾーン sfc.keio.ac.jpゾーン
様々なアプリケーションシステム システムの規模の拡大に伴って、より自律分散協調型に変異している。 クライアント・サーバ型システム サーバの冗長化、ネットワーク化 クライアント・サーバ型システムからP２P Peer to Peer System Clustering Server 利用者の拡大、分散・信頼性への要求 Simple Client Server Networked Server
クライアントサーバモデル インターネット上の通信の基本モデル 2種類のコンピュータ サーバ : サービスを提供するコンピュータ クライアント : サービスを受けるコンピュータ クライアント サーバ あるポート番号でクライアントからの要求を常に 待ち受けているプログラム 必要なときにサーバプログラムと通信して要求を送るプログラム データだよ クライアント サーバプログラム データちょうだい クライアントプログラム
クライアントサーバはSingle Point of Failure ボトルネック サーバの計算能力 ネットワーク帯域 ボトルネック解消のアプローチ ロードバランサの利用 キャッシュ/CDNの利用 P2Pモデルの導入 アクセスの集中による 回線の飽和 Server サーバのダウン Clients
負荷分散 分散させることによって負荷を軽減する 多くの有名サイトは分散している www.yahoo.co.jp などの名前を引くと？
例(1/4) : IRCの負荷分散方法 IRC(Internet Relay Chat) Hi! Hi! Hi! 一つサーバに処理が集中しない botnet RFC1459 Client 1 Server 1 Server 2 Hi! グループに1,2,3が 加わってる場合 Server 4 Hi! Client 2 Server 3 Hi! Server 4にはグループに加 わったクライアントがない ためメッセージはこない Client 4 Client 3
例(2/4) : ロードバランシング 同じIPアドレスで複数のサーバが反応 ラウンドロビン、URLで、重み付け、負荷、コネクション数、反応速度などで割り振る 利点 CPU負荷を軽減できる 問題点 ログが分割される メンテナンス負荷は高くなる コネクション要求 負荷分散装置
例(3/4) : DNSを利用した負荷分散 同じ名前で複数のサーバが登録されている 物理的に別の場所で処理 www.asahi.comなど 利点 回線資源を 分散利用できる 問題点 均等に負荷が 分散されない 落ちている サーバにも振る Cacheがあるため タイムラグがある www.asahi.comどこ？ Client 1 Client 2 209.249.129.20 Wwwld2.asahi.com 210.80.197.158 Uunet3.asahi.com 209.249.129.20だよ 210.80.197.158だよ
例(4/4） : キャッシュを利用した負荷分散 Accelia Durasite http://www.accelia.net/japanese/news/12.html ファイルを広域に分散しネットワーク負荷を分散 Akamai http://www.akamai.com/ クライアントに一番近い、最 適なキャッシュを探す サーバのかわりにキャッシュ がクライアントに応答 利点 CPU資源の分散 回線資源の分散 Clients Server キャッシュを拠点に置き アクセスを分散させる コンテンツの配置 Cache Servers
P2Pとは？ Peer-To-Peer 特徴 Peerとは端末ノードのこと(中継ノードではない) 耐故障性の実現 資源分散が可能 代表的なアプリケーション ファイル共有・交換・配信型 Napster コラボレーション型 Groove 分散コンピューティング型 SETI@home 特徴 耐故障性の実現 資源分散が可能 自由なランデブー
コミュニケーションとは？ 相手の発見と識別 コミュニケーションの開始 コミュニケーションの終了 コミュニケーションには主体がある。 P2Pではこれらは対等のものとしてpeerと呼ぶ。 誰かとコミュニケーションをとるためには、まずその主体同士が、 相手を発見・識別する コミュニケーションを開始する コミュニケーションを終了する ……という手順が必要になる 相手の発見と識別 コミュニケーションの開始 コミュニケーションの終了
クライアントサーバ、P2Pモデルの比較 クライアントサーバ ハイブリッドP2P ピュアP2P ランデブーも通信も中心で行う : Server 中心 : Server ピア ピア ピア ランデブーも通信も中心で行う ランデブーを中心で行い、通信をピア同士で行う ランデブーも通信もピア同士で行う WWWなどのインターネット上の大部分のアプリケーション Napster MSN Messengerなどの主要IM Gnutella ,Freenet, Winny
身近なＰ２Ｐアプリケーション ファイル共有 ストリーミング Napster Gnutella Morpheus WinMX Winny Share GNUnet ストリーミング PeerCast Joost (Skype) インスタントメッセンジャー MSNメッセンジャー ICQ、Jabber 3degrees、Skype Groove、Ariel AirOne 資源分散 OceanStore SETI@home HyperBee ネットワークゲーム Diablo Age of Empire
自律分散とコスト 自律分散でスーパーコンピュータ Apple ビッグマック PowerMAC G5 1100台 世界で３番目に早いスーパーコンピュータ 構築費用 520 万ドル 9.5 TFROPS 地球シミュレータ スーパーコンピュータ８台 NECが開発、世界最速 構築費用３億５千万ドル(!) 36.5 TFROPS 4位以下10位までほとんど4000万ドル以上かかっている
自律分散とコスト(2) FlashMob I もちよったPCでスーパーコンピュータを作る試み サンフランシスコ大学 300台程度 トップ500に入らなかった（500位の1/3程度) 構築費用・タダ！
自律分散とコスト(3) Seti@home 望遠鏡の観測データから、「地球外知的生命体」のメッセージを探す試み 配布しているソフトウェアを世界中の協力者のマシンで動かし、結果をインターネット経由でやりとり 52.56 TFROPS (!!) ただし変動し、 使い方も特殊なので ランキング外 そしてタダ