MAUI Project 2009
インターネットにおける近接性
政策・メディア研究科修士課程1年 黒宮 佑介（kuro） 親: 斉藤（ks91）さん サブ親: 重近（nazo）さんインターネットにおける近接性
• インターネット
– 複数の自律分散システム（AS）が相互接続 – 物理的・論理的に複雑なトポロジを持っている• インターネットにおける近接性
– Point-to-Pointの論理的ネットワークにおいて近い – 近接性を考慮することによるメリット • ネットワーク資源の有効活用 – インターネットバックボーンへの負荷を低減 • 優れたエクスペリエンスインターネットにおける近接性
• 問題点（デメリット）
– “近い”とは… • 何を以て近いとするか（RTT・Hop-Count） – オーバーヘッド • 近さを考慮することは重要だが… – 検出指標 • 下位層トポロジ情報 – 大量の時間・コスト • End Pointから取得できる指標 – 妥当性 – End Point » ユーザ・コンテンツプロバイダ卒業制作・卒業論文
• “近い”
– DNSの管理ドメインの階層構造において近い• 評価指標
– 下位層トポロジ情報としてHop-Countと比較 • Hop-Countが小さいネットワーク的に近い • 優先的に接続することで – ネットワーク資源の有効活用 – 優れたエクスペリエンスroot .
A-a A-b B-a B-b C-a C-b
Distance ne ad jp 3rd Level Domain Sub Domain 2nd Level Domain
Top Level Domain
Distance Network Distance Network Distance A B C
• 管理ドメイン階層構造
– 管理ドメインにおける近さ – 下位層トポロジの近さDNSを利用したネットワーク距離
近似可能であると仮定 a b c dアプローチ
•
DNSの管理ドメインの表現方法
– Fully Qualified Domain Name（FQDN）に着目
– 仮定 • 「FQDN において、同一のドメイン名を持つノードは 単一の組織に属しているためネットワーク的に近い」
•
FQDNの例
– 例）p1234-ipbf5678marunouchi.tokyo.ocn.ne.jp – 組織名・地理情報・ネットワークIDなどが含まれるFQDNの解析
•
IntelliSense
1. ドメインレベルの判定 一致しなかったところで終了 2. レーベンシュタイン距離を計算 自分のFQDNとの差を求める ドメインレベル判定 レーベンシュタイン距離計算p1234-ipbf5678marunouchi.tokyo.ocn.ne.jp
p1234-ipbf2222marunouchi.tokyo.ocn.ne.jp
レーベンシュタイン距離
•
2つの文字列の類似度を示す数値
– 編集距離ともいわれる• 文字列操作
– 置換 – 挿入 – 削除 必要な手順の最小回数を求める• 類似度が低いほど
– 大きな数値が出る 例）レーベンシュタイン距離: 3 1. kitten 2. sitten （“k”を“s”に置換） 3. sittin （“e”を“i”に置換） 4. sitting （“g”を挿入して終了） 出典: WikipediaIntelliSense実装
•
LinkPoint計算
– ドメインレベル判定
• 範囲: Top Level Domain ～ Sub Domain(s)
– 一致した場合: LinkPoint +64 points – 一致しなかった場合: 評価終了 LinkPointを決定 – レーベンシュタイン距離計算 • ドメインレベルの判定がすべて一致した場合に計算 • 範囲: Host Name – LinkPoint+（64―LD） – 64: DNSの仕様 • FQDNにおける各レベルの最大長: 63文字
実測データを用いた検証
• 実
P2Pネットワーク上のノードに対して検証
– 対象: Winny・Share• 取得した実測データ
– FQDN – Hop Count• 観測期間とノード数
– OCN：12/11～12/17（168時間） 35,000ノード • 全ノード数: 110,000, 推定AS数: 300（500） – BBTEC：1/16～1/17（48時間） 13,750ノードp****-ipbf****hodogaya.kanagawa.ocn.ne.jp p****-adsao01yokonib1-acca.kanagawa.ocn.ne.jp ノード数 Levenshtein Distance Domain Level ノード数 . jp ne ocn
OCNから取得した実測データ
•
Hop CountとFQDNによる優先度の比較
p****-ipbf****hodogaya.kanagawa.ocn.ne.jp p****-adsao01yokonib1-acca.kanagawa.ocn.ne.jp
優先度が高くなるにつれてHop Countが小さくなる 10 20 30 12 10 8 5 0 64 128 192 256 320 384 アルゴリズムの境界 295 300 305 310 315 320
Levenshtein Distance Domain Level . net ノード数
BBTECから取得した実測データ
•
Hop CountとFQDNによる優先度の比較
ノード数 softbank************.bbtec.net 10 20 30 30 20 10 0 64 128 192 アルゴリズムの境界 178 180 182 184 186 188 190Hop CountとFQDN優先度の一致率
• 一致率
– 実測データから任意の2つのノードを抜き出す – 優先度の高いノードHop Countが小さい•
OCN
•
BBTEC
正解 81% 不正解 19% 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 正解 76% 不正解 24% 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%（考察）
FQDNについて
• 地域名・IDのみが入るもの
– p123a45.tokynt01.ap.so-net.ne.jp
– nttkyo123456.tkyo.nt.ngn.ppp.infoweb.ne.jp
– pl123.nas955.p-tokyo.nttpc.ne.jp
– OFSfb-123p123-123.ppp11.odn.ad.jp • IPアドレスのみが入るもの – 123-45-67-89.eonet.ne.jp – 89.67.45.123.dy.bbexcite.jp • IPアドレスの一部が入るもの – q6789.dynamic.ppp.asahi-net.or.jp • 地域名・ID とIPアドレスが入るもの – FL1-123-45-67-89.tky.mesh.ad.jp – i123-45-67-89.s05.a015.ap.plala.or.jp
修士研究テーマ
短期的目標
修士研究テーマ
• インターネットにおける近接性
– まだ考え中… • 誰にとって最適か – ユーザー・コンテンツプロバイダー・運ぶ人 • 「P2Pのトラフィックが問題だ」 – 工学的な証明・裏付けとなるデータは？ – 性能の最適化でトラフィックは減らせる（工学的に）？ • エンドノードの限界 – ブラックボックスホワイトボックス • 本質的なトラフィックの要素 – アルゴリズムはトラフィック・実勢ベースだが…短期的目標
• 修士研究テーマの決定
– Intra-AS VS Inter-AS – コンテンツ配置• 学会への論文投稿
– CoNext2009を目標に執筆中 • 12ページ、6/12（6/19）締め切り•
Interop 2009 Cloud Computing Competition
– 6/2までにIntelliSenseを実装する予定
