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