Logo

研究背景

大規模ネットワーク障害に対応可能なオーバレイルーティング手法



ネットワークが正常に動作することが前提の社会– 既存の障害対策は単一障害を想定


大規模複数障害に対しては復旧に長い時間が必要– 災害，テロ，ルータの不具合などによって，大規模複数障害が起こりうる⇒ 複数障害発生時の対策が必要

中野研究室 4年
堀江 拓郎




ネットワークの冗長系を用意するにはコストが高い
従来のプロトコルの改訂には標準化作業が必要
大規模ネットワークでは全体を動的に監視できない

大規模ネットワークにおける複数障害に対して，ネットワークの信頼性を高めるには？
2008/2/22

研究目的

プロアクティブ型回復手法– あらかじめ障害を想定した準備をしておくことで，障害検知後に直ちに復旧が可能– 適用するネットワーク規模に対してスケーラブル

プロアクティブ型回復手法の1つ
Routing Layer (RL)

ノード5の障害発生⇒ ノード5を隔離したRLを用いたルーティング– 障害発生時に用いるネットワークトポロジ ⇒ ノード5以外のノード間の到達性が保障– 事前に用意し，全ノードで共有する代替経路を– 障害を想定したノードを隔離直ちに用いる

オーバレイルーティング

想定された障害ノードを隔離ノードと呼ぶ
隔離ノードの持つリンクをすべて削除する
リンク削除後のトポロジで経路表を作成

ネットワークの標準化作業が不要– ISP間のピアリングリンクがすべてのノード間で使用可能

通常ノード
隔離ノード
障害ノード
通常経路
代替経路
通常リンク
隔離リンク

元のトポロジ代替経路に用いることができるリンク数の増加
 平均経路長の減少


ノード5の障害発生を想定したRLを作成

プロアクティブ型オーバレイルーティング
2008/2/22

平成19年度特別研究発表会

2

RL群 (Routing Layer Set: RLS) を作成
すべてのノードをRLSのいずれかのRLで隔離

RLｎ

トレードオフが存在！

６２１



３
５

４８

通常ノード
隔離ノード

６７

８

[1] A. Hansen, A. Kvalbein, T. Cicic, and S. Gjessing, “Resilient routing layers for network disasterplanning,” Lecture notes in computer science, vol. 3421, pp. 1097-1105, Apr. 2005.
2008/2/22

平成19年度特別研究発表会

3

隣接する複数ノードの障害を想定
同じ属性（同じ地域，同じ種類のルータなど）を持つノード群の障害を想定– ノードを複数のRLで重複して隔離することを許可する場合のRLSも作成

５７８

RRLをオーバレイルーティングに適用
複数障害に対して効果的なRLSの作成

４

平成19年度特別研究発表会

RL1

３７– 属性法
RL２

２５４６

３

– 同時に障害が起こる可能性が高いノードを同じRLで隔離
– ハブ法

RLn-1

対応できる障害パターンが増加
 リンク数の減少によって平均経路長が増加

１

2008/2/22



元のトポロジ２１

提案手法の概要

RLS– 単一障害に対して，100%復旧が可能– 複数障害に対しても，すべての障害ノードを同じRLで隔離していれば復旧が可能⇒ 1つのRLで多くのノードを隔離

ノード5に障害が発生！

[1] A. Hansen, A. Kvalbein, T. Cicic, and S. Gjessing, “Resilient routing layers for network disasterplanning,” Lecture notes in computer science, vol. 3421, pp. 1097-1105, Apr. 2005.

Resilient Routing Layers (RRL) [1] (2/2)
リンクを削除– 隔離ノード以外のノード間における到達性が保障– RL 1つで複数のノードを隔離可能– アプリケーションレベルでの実装が可能

1

Resilient Routing Layers (RRL) [1] (1/2)


大規模ネットワークにおける複数障害に対応可能な経路制御手法を提案


平成19年度特別研究発表会

4

RL 1つ当たりの隔離ノード数が増加
到達性，平均経路長に与える影響を調査

比較用RLSの作成––––

2008/2/22

下位優先ランダム法
一様ランダム法次数降順法
次数昇順法
平成19年度特別研究発表会

51

評価環境・条件


JPNICに属するASのトポロジを用いる
属性法に用いる属性の与え方– カットサイズ（分割グラフ間をまたぐリンク数）が小さくなるようにグラフ分割を行い，分割結果に応じて各ノードに属性を与える– ランダム障害
ランダムに選択した複数のノードに障害を発生させる– 隣接ノード障害


属性法



重複の効果

– 最大で8%の改善

隣接する（リンクで接続された）複数のノードに障害を発生させる



評価指標

– RLがより多くの障害に対応⇒ 重複させない場合に比べて改善割合が大きい– 到達性
障害ノードを除くすべてのノード間の経路の存在確率– 平均経路長
到達可能なすべてのノード間の経路長の平均

2008/2/22

ハブ法を用いることで99%まで到達性が改善

平成19年度特別研究発表会

62008/2/22

隣接ノード障害発生時の平均経路長



障害ノード数1～10の隣接ノード障害発生時における平均経路長ハブ法属性法

huboverlapped hub
attribute
overlapped attributeprioritizing_lower_random
uniform_random
degree_decreasing
degree_increasing
optimalnormal2.9– 重複の有無に関わらず減少する

ピアリングリンクによる効果

重複の効果– RL内のリンク数が減少⇒ 平均経路長の増加
重複を許すことによって平均経路長が増加

2008/2/22

2.8

Length

0.8

0.6
hub
overlapped hub
attribute
overlapped attributeprioritizing_lower_random
uniform_random
degree_decreasing
degree_increasing
optimalnormal

0.4

0.2

0
1

2

3

4
56
7
Number of failed ASes

89

平成19年度特別研究発表会

107

まとめ
– 大規模ネットワーク障害に対応可能なプロアクティブ型オーバレイルーティ
ング手法を提案– ハブ法の評価結果

平均経路長– ほとんど増大しない

到達性
1

まとめと今後の課題


3

重複を許すことによって到達性が改善– 重複の有無に関わらず大きく改善– 最大で15%の改善（99%まで改善）発生させる障害

障害ノード数が1～10の隣接ノード障害における到達性
ハブ法

Reachability

隣接ノード障害発生時の到達性

ランダム障害– 到達性を改善，平均経路長を維持
隣接ノード障害– 到達性を大きく改善，平均経路長を維持– 属性法の評価結果
2.7


ランダム障害，隣接ノード障害– 到達性を改善，平均経路長を減少

今後の課題– リンク障害など，想定する障害の種類を増やした評価– 3ノード以上の障害に対する効果的なRLS作成手法の検討

2.6

2.5
012

平成19年度特別研究発表会

34567
Number of failed ASes

89810
2008/2/22

平成19年度特別研究発表会

92