狠狠撸

狠狠撸Share a Scribd company logo

kibayos-ID/Locator-081031

?
?
M
Mikio Yoshida
1 of 27
2008/10/31 2nd sensor & overlay workshop / / y p （2008/3/6 DPS-134-6 発表資料＋α） オーバレイネットワークにおける ID/Locator 分離機構 吉田 幹 BBR&阪大 大阪大学
Agenda IPネットワークにおける課題整理 滨顿/尝辞肠补迟辞谤分离の方式例 ID解決における問題 オーバレイネットワークにおける滨顿/尝辞肠补迟辞谤分离機 構の提案 IDベースのルーティング IDベ スのル ティング 経路表の対称性 PIAXを使ったプロトタイピング PIAXを使 たプ トタイピング まとめと今後の課題 2
IPネットワークにおける課題整理 IPネ トワ クにおける課題整理
滨顿/尝辞肠补迟辞谤分离 IPアドレスの二元性問題（duality problem of the IP address） IPアドレス（or FDQN）が、ノード自身の識別子（ID）と接 続位置（locator）の両方の意味を有している モビリティ、マルチホーム、IPsec に支障を生じる ビ ホ ム 支障を生じる ノードの個体（identity）と接続位置（location）の概 念を分離し、IDと locatorを別レイヤで扱う必要が 念を分離し IDと l t を別レイヤで扱う必要が ある Service Socket Service Socket End-point End-point Host Identity Location L ti IP address dd Location L ti IP address dd HIPにおける滨顿/尝辞肠补迟辞谤分离の例 4
IPにおける滨顿/尝辞肠补迟辞谤分离の概要 IRTF, IETFにて検討が進められている 直近の問題として、マルチホーミングに伴う経路表 直近の問題として マルチホーミングに伴う経路表 の増大がある 提案方式 LINA（Location Independent Network Architecture）, LIN6（Location Independent Networking for IPv6） HIP（Host Identity Protocol） LISP（Locator Id tifi Separation Protocol） LISP（L t Identifier S ti P t l） などなど いずれも、ID解決にネームサーバを用いる ずれも 解決にネ ムサ バを用 る ネームサーバは、（ID, locator）の組を管理する 5
LINA, LIN6 アプリケーションは、送信先ノードの指定に、IDとlocatorの 両方を利用可能 Network層を2つの sub layerに分離 Identification sub layer と Delivery sub layer Identification sub layer で IDから locatorに変換 で、IDから （ID解決） MA（Mapping Agent）がネームサーバとして機能 MAが、 Identification sub layerからの要求に応える形で、 ID解決を実現 LIN6 は、LINAのIPv6への適用 IDを40bitで表現し、24bitのprefixをつけて、下位64bitに埋め込む IDを40bitで表現し 24bitのprefixをつけて 下位64bitに埋め込む IPv6 address locator ID 6
尝滨狈础の処理フロー Application ID Layer Transport ID Layer Identification mapping Sub Layer ID Locator Network Delivery Layer Sub Layer Locator 相手ノードがIDにより指定された場合 Application Locator Layer Transport Locator Layer Identification Sub Layer Network Delivery Layer L Sub L S b Layer Locator 相手ノードがlocatorにより指定された場合 7
HIP Architecture TransportとNetwork層の間に Transport Layer ID解決のための層を設ける HIP LINAと同じ と同じ Internetworking Layer 主な特徴 IDのために独立の空間を定義する LIN6の場合は、IPv6アドレスに埋め込み IDに認証と匿名性のための機能を付与する key generator このため、2種類のID（HI, HIT）を持 のため 2種類のID（HI HIT）を持つ public key private key ID解決のためのネ ムサ バ ID解決のためのネームサーバ として、DHTが検討されている public HI anonymous HI (ID, locator) の組をDHTにより管理 hash 認証機能により、改竄を防ぐ HIT LSI secure-i3 128bit 32bit i3（Internet Indirection Infrastructure）を拡張 8
既存方式の問題 実現性 LIN6においては、IPv6の普及が前提 HIPでは、ホストにおけるプロトコルスタック、LISPでは、ルータの置 は ホ お るプ タ ク は タ 置 き換えが必要 実現には時間とコストを要する ID解決のオーバヘッド ネームサーバを用いるため、オーバヘッドを生じる ハンドオーバ時にID解決を要する場合、通信断が長くなる ンドオ バ時にID解決を要する場合 通信断が長くなる セキュリティ強化の必要性 不正なエントリ参照や改竄を防ぐため、ノ ド認証の仕組みが必要 不正なエントリ参照や改竄を防ぐため ノード認証の仕組みが必要 DHT自体の持つ技術課題 通信頻度の高いノードのID解決エントリを保持するDHTノードの参 照負荷が高くなる ? DHT内の負荷が均等でない 負荷が高くなる 負荷が均等 な churn状態（DHTノードの出入りが頻繁）と複製の持ち方について緻 密に管理する必要がある ?検索成功の保証が困難 9
オ バレイネ トワ クを前提とした提案 オーバレイネットワーク
オーバレイネットワークにおける問題 ノードには、独立にIDが割り当てられる ? IDとlocatorの概念分離はできている ところが現状、IPネットワークの持つ二元性問題の 影響を受けている ? 物理ネットワークから来る制約を隠蔽できていない 64 0 構造化オーバレイの場合 v1 v4 identifier circle IDに基づくルーティングは可能 IDに基づくル テ ングは可能 (N=64) 52 であるが、 ノードの移動（locatorの変更） v2 が起こると、移動ノードへの通 が起 る 移動 ド 通 Node ID 20 信が不能となる 21 22 24 v3 28 36 Chordの例 11
滨顿/尝辞肠补迟辞谤分离のためのアプローチ 目的： オ オーバレイネットワーク上のアプリケーションにおいて、ノー レイネットワ ク上のアプリケ ションにおいて、 ドのlocatorを意識させない アプローチ： A. 物理ネットワークで、滨顿/尝辞肠补迟辞谤分离を実現する B. オーバレイネットワーク内で、滨顿/尝辞肠补迟辞谤分离を実現する / A案 案 IPネットワークで検討が進んでいるが、対応に時間を要する 対応していない物理ネットワーク上にオーバレイネットワークを作れ ない B案 物理ネットワークの制約をより強く隠蔽できる 物理ネットワ クの制約をより強く隠蔽できる ? オーバレイネットワーク本来のあり方 12
提案機構 オーバレイネットワークの下位層を2層に分離 ID Transport層 IDベースのルーティング ? IDによるメッセージ到達性 経路表には、隣接ノードのIDとlocatorを保持 Locator Transport層 下位の物理ネットワークの抽象化が目的 実際の処理は委譲する Overlay Network ID Reachability routing ID Transport Layer table locator Locator Transport Layer IP Network non-IP Network ... Physical (MANET,..) Networks 13
対象とする物理ネットワーク オーバレイネットワークで、滨顿/尝辞肠补迟辞谤分离を行うことにより、 ヘテロジーニアスな物理ネットワークをカバーできる IP network non-IP network overlay network overlay network non-IP network IP network overlay network 14
滨顿ベースルーティングによる利点 外部のネームサーバは不要になる LocatorのTransport層では、ホップ単位のメッセージ到達性 の p 層では、ホッ 単位の ッ ジ到達性 があればよい（部分到達性） マルチキャスト（ALM）も変更なしに扱える name server message ID Trans Layer Locator Trans Layer オーバレイネットワーク A router B routing IPネットワーク message table ID Trans Layer Locator Trans Layer A X B 15
ノード移動時の処理 移動により、メッセージ到達性が失われる場合は、再びノー ドをオーバレイネットワークに参加（join）させる 経路表に対称性があり、メッセージ到達性が失われない場 合、高速なハンドオーバが実現できる 経路表に対称性のある構造化オーバレイの例 DHT: Kademlia non-DHT: Sk G h Skip Graph B L2’ A L1’ D C L1 L2 C 16
PIAXにおける実装 ID Transport層と Locator Transport層にAPIを設定 IdTransport, LocatorTransport 経路表の対称性は、Multi-key Skip Graphにより保証 多様な物理ネットワークを扱うため、通信部分をSPI化 MSkipGraph bind IdTransport API getLocator notifyChange IdResolver IdR l IdTransport Locator Transport LocatorTransport API IPTS Locator ZigBeeTS (emulator) Transport (NAT Traversal) Services 17
シームレスハンドオーバ 無線LANの場合、 以下の手順 (1) 次に接続する無線AP を探すためのチャネルスキャン (2) 新しい無線AP とのアソシエーション (3) DHCP による新しいIP アドレスの取得 所要時間 (1)+(2) : 50～400msec (3): 2～5秒 （Windows だと、5秒から数十秒） 結構、長い 何もしないと、通信断は避けられない 何もしないと 通信断は避けられない 無線I/Fを2つ持つ、またはドライバの改造（電波を2つ取る） (3) の短縮も必要 non-IPの世界だけで行うことは有効 さらに、ネ ムサ バを引く時間も入れないといけない さらに ネームサーバを引く時間も入れないといけない 18
Dual Locator 方式 locatorを2つ持つことで、通信断をなくす 以下の時間、旧 以下の時間、旧locator を保持する 新しいlocatorを取得するのに要する時間（handover time） ID解決に要する時間（ID resolve time） 高速ハンドオーバのための目安 100m届く無線APで、50mあたりからハンドオーバさせる場合、移動 ノードが50m動くまでの間に完了させなければならない ノ ドが50m動くまでの間に完了させなければならない 時速60kmなら、3秒しか余裕がない locator L time locator L’ t1 t3 t2 handover ID resolve time time 19
経路表対称性条件が満たされる場合 ID解決のためにlocatorを保持する時間は、 RTT（往復遅延時間）で十分 シミュレーションで再確認 隣接ノード間の経路表更新が必ず成功するためにも、この 条件が必要 time locator L locator L’ node A locator M locator M’ node B send delay 20
シミュレーション評価 条件 ノ ド数：100, 1000, ノード数：100 1000 10000 各ノードは、Random Waypoint Model に従い移動 無線APは、100m間隔に設置されているとする [60,600]秒休憩し、[5,100]間隔で、[1,10]回ハンドオーバ 平均でいえば、5分休憩、50秒間隔を5回 高速ノードは、時速70km。低速ノードは、5km 高速 ド 時速 速 ド ID resolve time を変化させる（0 から n x RTT） 簡単のため RTT/2 = 10msec 簡単のため、RTT/2 0 から 30msec に変化 ランダムに抽出したノ ド間の通信（ID指定）の成功率を ランダムに抽出したノード間の通信（ID指定）の成功率を 調べる 21
シミュレーション評価 20ms（RTT相当）を越えると、エラー率はゼロ locator保持をさぼったとしても、1%程度 保持をさぼ た しても、 程度 22
まとめ オーバレイネットワークにおける滨顿/尝辞肠补迟辞谤分离機 構の提案 IDによるメッセージ到達性と以下の透過性を実現 ノード移動に対し透過的 ド移動に対し透過的 ヘテロジーニアスな物理ネットワークに対し透過的 経路表に対称性がある場合、高速なハンドオーバが実 現できることを示した 外部のネームサーバを必要としないことによる効率向上 余計な管理負荷が発生しない 改竄防止の対策が不要 PIAXを使った実装（プロトタイプ）を提示 を使 た実装（プ トタイプ）を提示 23
参考：ZigBee通信の実験例 無線アドホックネットワーク（AODV）上にPIAXの オーバレイネットワークを構成 UNS2008 にてデモ展示 PIAX nano MOTE バッテリ 24
参考：メッセージ軽量化の评価结果 無線アドホックネットワーク特有の狭帯域性に対応するため、 メッセージ軽量化を実験 位置座標の基準点、メソッド名のエンコード表の共有化 位置座標 基準点 メ ド名 ド表 共有化 総受信 イト数 総受信バイト数 メソッド実行までの平均時間 ソッド実行までの平均時間 5 190 １８７ 185 4 受信バイト (Kbyte) 180 時間 (秒) 3 間（秒） ト数 2 提案手法では 時間 間 15 増加率が徐々に減少 １０．５ 10 1 5 ０．９３ 0 0 0 4 8 12 16 20 24 28 PIAX Message JSON 提案手法 discoveryCall （回） PIAX Message JSON 提案手法 25
今後の課題 滨顿/尝辞肠补迟辞谤分离機構をフレームワーク化し、オープンソース として提供 ヘテロジーニアスな物理ネットワークで使用できるルーティ ングアルゴリズムの検討 ノードおよび通信特性の差を吸収するルーティング方式の検討 通信品質とノード性能において大きく特性が異なるネットワークをまたぐ 前提 半構造化オーバレイの検討 構造化オーバレイの場合、均一なノードの性能を期待するため、非構造 化オーバレイのルーティング方式を効果的に融合させる必要がある 化オ バレイのル ティング方式を効果的に融合させる必要がある クロスレイヤ制御 物理ネットワ クの通信状況をオ バレイネットワ クのル ティン 物理ネットワークの通信状況をオーバレイネットワークのルーティン グに反映させる 高速ハンドオーバのためにも必要 26
Q&A

More Related Content

kibayos-ID/Locator-081031