信頼性に関するQoSを考慮したWDMネットワークにおける 論理トポロジー設計手法の提案 加藤 潤一 大阪大学 大学院基礎工学研究科 情報数理系 博士前期課程 E-mail : [email protected] September 14, 2001 CQ研究会@CRL 1 研究の背景 インターネットの普及によるトラヒックの急激な増加 大容量伝送を可能とするWDMネットワークの台頭 IPを上位層とするIP over WDMネットワークへの期待 高いスケーラビリティ 大容量の伝送帯域 IPの経路制御による障害回復機能 しかし IPの経路制御による障害回復機能では・・・ 遅い 経路不安定性の誘引によるネットワークの性能低下の可能性 そこで WDM層での高速な障害回復が必要 September 14, 2001 CQ研究会@CRL 2 WDMネットワークアーキテクチャ 物理トポロジー A 光パス D 30Gbps 30Gbps 30Gbps C 30Gbps B E B C 10Gbps D 10Gbps 20Gbps 10Gbps 10Gbps 10Gbps 10Gbps E September 14, 2001 論理トポロジー CQ研究会@CRL 3 WDMネットワークにおける障害回復方法(1) Protection : プロテクション 通常時トラヒックを流すプライマリ光パスと同時に、 バックアップ用のパスを予約 障害発生時、あらかじめ決められた経路にトラヒックを 流して障害から回復 100%の確率で障害回復 Backup Path Primary Lightpath September 14, 2001 CQ研究会@CRL 4 WDMネットワークにおける障害回復方法(2) プロテクションパスの波長の共有 １つの障害で同時に断線しない光パスのプロテク ションパスは波長を共有できる D A E C B λ1 X Y λ2 F September 14, 2001 G CQ研究会@CRL 5 障害回復に関する従来の議論と問題点 プロテクション機能を有する様々な論理トポロジー設計 手法が提案 目的関数例：使用波長数最小化、ブロック率最小化 障害回復の品質に関する議論は少数 文献１：O.Gerstel著 キーワード QoP (Quality of Protection) 内容 SLSP (Short Leap Shared Protection) プロテクションにより帯域が トラヒックはプロテクションパスの 何％の確率で回復するかをト 長さを指定可能。それを満たすプ ラヒックごとに定義可能 ロテクション経路設計手法を提案 問題点 そこで 文献２：Pin-Han. Ho著 QoPは適切か？ プロテクションパスの長さが指定 できてもユーザは嬉しくない 各トラヒックが最大障害回復時間を指定できるQoPを提案 September 14, 2001 CQ研究会@CRL 6 発表内容 障害回復時間をに関したQoP機構の提案 提案QoPを実現するプロテクションパス設定 手法の紹介 上記のプロテクションパス設計手法を組み 入れた２つの論理トポロジー設計手法の提案 提案設計手法の比較評価 September 14, 2001 CQ研究会@CRL 7 障害回復時間を考慮したQoSの提案 QoP 最大障害回復時間：障害発生から回復までの最大待ち時間 QoP1 QoP2 Dmin Dmin+ 1×Dscale … … QoPn Dmin+ n×Dscale … … QoP∞ プロテクション経路なし Dmin：保障可能な障害回復時間の最小値 Dscale : 各QoPの刻み幅 これらの値はネットワークによって適宜決定 September 14, 2001 CQ研究会@CRL 8 障害回復時間モデル プロテクションパスPx : ｈホップ m-1 m m+1 n-1 n n+1 主経路の保護する領域の伝播遅延時間 Dp 領域(m, n)の障害回復時間 = Dp 最大障害検知時間 + Dnode×h パス設定時間 + Dconf September 14, 2001 CQ研究会@CRL パス切り替え時間 9 プロテクション手法１：SLSP 隣り合うプロテクションパスが交差し、始点と終点が隣接ノー ドになる。 波長変換を許可しない場合、プライマリパス、プロテクション パスともに同一波長 文献2:Pin-Han. Ho QoP：プロテクションパスの長さを指定 本研究 QoP：各区間内での障害回復時間の最大を指定 September 14, 2001 CQ研究会@CRL 10 プロテクション手法２：Path Protection SLSPで、QoPが十分に大きく、始点、終点間のプロ テクションパスのみでQoPが満たされる場合 始点ノードで電気的に出力波長を変換するため波長 変換を許可しない場合でも、プライマリパスとプロテク ションパスは異なる波長可 September 14, 2001 CQ研究会@CRL 11 論理トポロジー設計アルゴリズム 与条件 ：トラヒック量は既知 目的関数：使用波長数の最小化 トラヒックの割当順序 経路設定手法 波長割当方法 September 14, 2001 QoP、トラヒック量の順で降順 プライマリパス：最短経路 プロテクションパス：プライマリ パスと始点、終点以外にノードを 共有しない最小ホップ経路 ２つの方法を提案 CQ研究会@CRL 12 提案アルゴリズム１ 割当可能波長 割当不能波長 割当不能 λ0 割当不能 λ1 割当 割当可能 波長割当手法：First Fit 方式 波長に0から番号をつけ、 パスに対して番号の小さい 波長から順に割当可能かど うか調べ、可能な波長のうち 最も番号の小さい波長を割 り当てる Path Protectionの場合、プ ライマリ光パス、バックアップ パスそれぞれ別々にFF方式 を用いて割り当てる λ2 September 14, 2001 CQ研究会@CRL 13 提案アルゴリズム２ 新規使用波長 共有使用波長 コスト ２ λ0 ０ λ1 １ λ2 September 14, 2001 割当 プロテクションパスに新たに 使用するチャンネル数を各波 長のコストとする チャンネル：１リンクの１ 波長 最小コストとなる波長を割り 当てる Path Protection方式の場合、 プライマリ光パスはFF方式で 割り当てる CQ研究会@CRL 14 評価モデル 対象ネットワーク ： NSFNET トラヒックマトリクス ： 実測値（単位：Gbps） 波長帯域 ： 1波長10Gbps QoP ： ノード間に与えられる各トラヒックはQoPとして１か ら∞までの値をとる 評価指標 ： 使用波長数 2.8ms 1.4ms Dmin 10ms Dscale Dnode Dconf 2ms 4.7ms 1.4ms 3.5ms 1ms 2.8ms 2.8ms 3.5ms 5.6ms 0ms CQ研究会@CRL 0.7ms 3.5ms 8.4ms 7.0ms 8.4ms September 14, 2001 9.1ms 11.2ms 3.5ms 1.4ms 3.5ms 3.5ms 4.9ms 15 評価結果：QoPと波長数の関係(1/2) 各トラヒックが一葉に同一のQoPを要求した場合 提案アルゴリズム１を適用 60 波長数小 あるQoPからは 使用波長数一定 高QoPでは使用 波長数が単純減 少を示していない 50 # of Wavelength 低QoPほど使用 40 30 20 10 0 2 4 高いQoP September 14, 2001 CQ研究会@CRL 6 8 10 12 14 16 18 QoP: Quality of Protection 20 低いQoP 16 評価結果：QoPと波長数の関係(2/2) 各トラヒックが一葉に同一のQoPを要求した場合 提案アルゴリズム１を適用 45 ブロッキング ： 要求するQoPを満たす プロテクション経路の確 保が不可能な場合を意 味つす。この場合主経 路のみ設定 40 # of blocking 35 30 25 20 15 10 一部のノード間では高い QoPを要求してもそれを満 たす経路の確保が不可能 September 14, 2001 5 0 2 4 CQ研究会@CRL 6 8 10 12 14 16 QoP: Quality of Protection 18 17 20 評価結果：提案アルゴリズムの比較評価 各トラヒックのQoPをランダムに与えた場合 与トラヒック ： トラヒックマトリクスのα倍 1000 900 のほうが波長数小 提案アルゴリズム２ ではより多くのプロテ クションパスで波長を 共有しようとしたため # of Wavelength 提案アルゴリズム２ 800 600 500 400 300 Algorithm2 200 100 0 September 14, 2001 Algorithm1 700 10 CQ研究会@CRL 20 30 40 50 Traffic scale α 60 70 18 80 まとめと今後の課題 まとめ 障害回復時間に関するQoPの提案 QoPを考慮した２つの論理トポロジー設計手法の提案 QoPと使用波長数の関係を明らかにした アルゴリズム１と比較しアルゴリズム２の使用波長数が小さく なることを明らかにした 今後の課題 ブロッキングを排した評価 論理トポロジー設計アルゴリズムの提案 • より波長数を小さく抑えるアルゴリズム • 上位層をIPとしIPの経路制御機能も考慮したアルゴリズム September 14, 2001 CQ研究会@CRL 19 研究の背景 IP over WDMネットワークの台頭 WDMによるネットワークの伝送容量の増大 WDM層による障害回復の重要性 IP層での経路制御による障害回復では、経路の不安定 性を誘引する可能性があり、結果として経路制御のため のトラヒックを増大させ、ネットワーク全体の性能を低下さ せる要因になる。 September 14, 2001 CQ研究会@CRL 20 WDMネットワークにおける障害回復方法(1) Restoration : リストレーション 障害発生時に経路を再計算して障害から回復 局所的に障害回復をすることで高速な障害回復が可能 資源不足の場合WDM層での障害回復が不可能、こ の場合IPの経路制御による障害回復に依存 Primary Lightpath September 14, 2001 CQ研究会@CRL 21 提案アルゴリズム２ 対象となるパスに対して、割当可能な波長を全て求め、各 波長に対して新たに使用する波長数をコストとし、そのコ ストの最も小さい波長に割り当てる プロテクションパスは、プライマリパスがDisjointな 他のプロテクションパスと波長を共有可能 プライマリパスの場合、どの波長でもコストは同じな ので、Path Protectionの場合はFirst Fit方式を使用 September 14, 2001 CQ研究会@CRL 22
© Copyright 2024 ExpyDoc
