1 - ItrC

オーバーレイネットワークを用い
た
トラヒック制御と分散測定
2008.05.16
ITRC meet23＠名古屋ベンチャービジネスラボラトリー
NTT サービスインテグレーション基盤研究所
亀井聡川原亮一
はじめに～オーバーレイネットワークのふたつの側面

実験的機能を追加するための上位レイヤネットワーク
 Mbone, 6bone, …
 Planetlab (の実験インフラとしての側面)
 インターネットは専用線のオーバーレイ(かつては)
→ 比較的きっちりしたノードによるネットワーク

(主に)エンドユーザノード(等)を用いた多ノード分散環境
 P2P, DHT, Structured Overlay…
→ 比較的ゆるやかで柔軟なネットワーク
2
オーバーレイネットワークを用いたトラヒック制御
インフラストラクチャ技術
(OSPF, BGP, MPLS, etc…)
安定的物理網の上にインフラを構成
アプリケーションレイヤ技術
(P2P, DHT, etc…)
不安定な端末上にミドルウェアを構成
オーバーレイネットワークを用いたトラヒック制御技術
センサー，ユビキタス等超大規模化への対応
浮動(低信頼)ノード上でのインフラ構築

不安定なインターネット環境下において，多数の浮動
ノードを用いることにより安定的で高信頼，高品質な
オーバーレイインフラを構築することが目的．

既存のネットワーキング技術を多ノード，広域分散環境
に適用することは困難であるのが実情(OSPFでも数百で
アウト)．
3
既存のトラヒック制御の限界

ISP間では…
 DiffServ / MPLS の適用はルータ更改とISP間ポリシ調整が必要．
 BGPの枠内でもある程度は対応可能だが，実現は困難．また，Transit
と Peering の比率は国内では 1:5 程度であり，有効範囲も限定的．
 そもそもAS内で品質が一定ではない．
AS:2
Transit ：複数 hop に影響するが，
制御可能なのは 1 hop．
AS:1
Peering : 影響範囲は 1 hop
4
クラスタ化したノード群によるトラヒック制御
クラスタヘッドにより張られたオーバーレイ面
クラスタ集合
制御がかかる場合
A
制御がかからない場合
B
5
クラスタ単位でのトラヒック制御

基本的なアイディア
測定元と測定先になるノード(以下測定ノード)をクラスタ化す
ることにより，測定対地の組数を削減する．
 s1→s2 の測定を同一クラスタの代表ノードであるr1→r2の測定結
果により代替する．

クラスタ
s2
s1
非代表ノード
r1
r2
代表ノード
6
インターネットの品質空間
非ユークリッド，高次元空間(安定品質で見ても)
 距離だけに頼ったクラスタリングでは駄目


提案手法：単にノード間距離が近いノードを固め
るのではなく，いくつかのノードの「見え方」が
似ているノードを固める．
近いとは限らない
他ノードへの
経路は全く違
う可能性も
近い
既存手法
見え方が似ている
提案手法
7
既存手法(最近傍へ所属)
1.
2.
各クラスタの代表ノード (r1,…,rm)を検索．
自身(p)から全代表ノードへの品質を測定し最も遅延が短か
いクラスタへ所属．
遅延分布がユークリッド則に従わない場合に経路情報を反映できない
r2
r1
代表ノード
非代表ノード
新規参加ノード
p
クラスタ
r3
delay(p, r1)
delay(p, r2)
delay(p, r3)
8
提案手法
1.
2.
3.
各クラスタの代表ノード (r1,…,rm)を検索．
自身(p)から全代表ノードへの品質を測定し，vpへ収納．
代表ノードの測定結果vriとvpを比較し，近いクラスタへ所属．
ネットワーク上での遅延による相対位置を反映できる可能性
クラスタ
r1
r2
代表ノード
非代表ノード
新規参加ノード
p
vr =
3
delay(r3, r1)
delay(r3, r2)
0
r3
v =
p
delay(p, r1)
delay(p, r2)
delay(p, r3)
9
提案アルゴリズムの評価～

評価尺度
評価尺度
 真の値である，delay(s1, s2) を delay(r1, r2) で近似して
いるため，誤差の評価には以下の式を用いる．
e(s1, s2) =
| delay(s1, s2) - delay(r1, r2) |
max {delay(s1, s2), delay(r1, r2)}
クラスタ
s2
s1
非代表ノード
r1
r2
代表ノード
10
提案アルゴリズムの評価～

比較対象と評価モデル
評価モデル

代表ノードの選択

k-means法を利用


トポロジ


一様乱数を用いて2次元空間上にノードを配置
トポロジシミュレータ BRITE を用いてリンク構造を生成




ランダムグラフ (Waxman モデル)
リンク次数がべき乗則に従うグラフ (Barabasi-Allbert モデル以下BA)
全リンクを接続したフルメッシュグラフ
パラメータ





重心決定時に最近傍方式(単純距離)と提案手法(ベクトル間距離)を用いる
全ノード数 (n)
トポロジ (Waxman, BA, Fullmesh)
トポロジ生成時のノードあたりの平均リンク次数 (l)
全ノード数に対するクラスタ数の比率 (m)
遅延

2点間の経路を最短路探索にて決定した後，経由リンクの幾何的距離
を加算，光速で割ることにより決定．
11
アルゴリズム間の比較
Waxman
BA
e(si, sj)
Nearest
Vector
l=2, n=300
% of clusters
Fullmesh
それぞれトポロジを固定して，最近傍
アルゴリズムと提案アルゴリズムを比
較したもの．ノード数とリンク次数は
固定．提案方式は15stepで切っている．
Waxman, BA ともに提案方式が良い性
能を示している．差はBAのほうが顕著．
Copyright 2007 NTT Corporation, All Rights Reserved
時系列で見た K-MEANS (N=300,10クラスタ)
1. ランダムに代表ノード決定 (本図では300ノード，10クラスタ)
2. 最近傍，ベクトル方式でそれぞれ所属決定
3. クラスタ毎に重心を計算
• 距離(単純距離，ベクトル間距離)の合計値が最小になる代表ノードをクラスタ毎に決定
4. 2->3 繰り返し
重心再計算所属再計算
BA
Waxman
Fullmesh
vector
nearest
• vector の優位性確認なので，結果は良好だが nearest 方式はかなり悪い．
• vector では一見したところトポロジ毎の差は見えない．
13
• nearest のほうはかなり早期に収束している．vector は収束せず．
考察

ランダムトポロジやスケールフリートポロジにお
いては提案アルゴリズムが全ての領域において優
位性を示す．

特に，実インターネットに近いといわれるスケー
ルフリートポロジにおいてその差は顕著．
14
まとめと今後の課題

大規模ネットワークにおけるスケーラブルな品質
測定のためのクラスタ方式について，トポロジシ
ミュレータを用いた詳細評価を実施
提案手法の優位性が高いクラスタ数やトポロジ構造の
条件を明確化．
 大規模条件下でも提案アルゴリズムが有効であること
が示せた．


今後の課題として，
ネットワーク変動への追従．
 AS構造を反映したモデルの利用と，ネットワーク構造
を考慮したクラスタ化アルゴリズムとの比較．

15

Download Report