No | 117046 | |
著者(漢字) | 徐,蘇鋼 | |
著者(英字) | ||
著者(カナ) | ジョ,ソコウ | |
標題(和) | WDM光ネットワークにおけるネットワーク制御と論理トポロジーの設計に関する研究 | |
標題(洋) | Studies on the Network Control and Logical Topology Design in WDM Optical Networks | |
報告番号 | 117046 | |
報告番号 | 甲17046 | |
学位授与日 | 2002.03.29 | |
学位種別 | 課程博士 | |
学位種類 | 博士(工学) | |
学位記番号 | 博工第5187号 | |
研究科 | 工学系研究科 | |
専攻 | 電子情報工学専攻 | |
論文審査委員 | ||
内容要旨 | 異なる複数の情報を1本の伝送路で効率良く伝送する目的で、古くから分割多重伝送が用いられてきた。光ファイバ伝送では、時間領域における多重伝送に加えて、波長多重伝送(WDM:Wavelength Division Multiplexing)という多重伝送が可能である。波長多重伝送は、波長の異なる複数の光信号を1本の光ファイバを用いて伝送するものであり、広い波長域にわたる光ファイバの低損失性を有効に利用できる利点がある。光ファイバを用いた大容量通信を実現するために、波長分割多重(WDM)システムは不可欠になってきている。 広域ネットワークでは大部分の接続関係がマルチホップ、すなわち伝送する間に多くのルータが介在するが、現在のWDMシステムでは各IPルータ間のポイントーポイント間通信にWDM技術を利用することで通信回線の大容量化を図っている。しかし、ノードで波長を電子的に処理することは非効率的かつコストが高く、電子デバイスにかかる費用によって制限を受けることになる。この場合、ルータがボトルネックになる可能性は大きい。これに対しては光ADM(add/drop multiplexer)と光クロスコネクトを用いてルータ内の所望の波長信号を分岐・挿入する方法がある。WDMネットワーク上において、ソースと目標ノードの間に複数の物理リンクにまたがって同一波長を割当てたライトパスを設定すれば、ルータが扱うべきトラヒック量を減らすことが可能になる。そのため、ライトパス上の途中ノードではトラヒックは電気的な処理が行われることなく通過することになる。このようなWDM光ネットワークはWavelength Routed Networksとも呼ばれているが、本研究はこのWavelength Routed Networksに関する研究である。 ネットワーク中で発生したコネクション要求の類型には主として2つがある。1つは動的に発生した短期的な要求であり、もう1つはより長期的なコネクション要求である。そこで、研究の目標は、ネットワーク中の波長資源を有効に利用し、発生したコネクションに対してライトパスを設定すること、さらに、より長期的なトラヒックのパタンによってネットワークの最適化を行うことである。ここで、本研究は構成上、大きく2つに分けている。まず、発生したコネクションに対してライトパスを設定するためのネットワークの制御を研究し、次に、より長期的なトラヒックのパタンによるネットワークの最適化に対する論理トポロジーの設計に関する研究を行った。 I. WDM光ネットワークにおけるネットワーク制御に関する研究 WDM光ネットワークにおけるネットワーク制御の一つ目的はコネクション要求によるライトパスを設定することである。即ち、WDM光ネットワークにおける光ルーティングと波長割当(Routing and Wavelength Assignment-RWA)である。光ネットワークでは交換ノード内で光信号の波長変換を行なうことができれば、より柔軟なルーチングが可能になる。しかし、光・電子変換を行なわず波長変換を行なうことは、現在の技術では困難である。交換ノードで波長変換を行なわない場合、コネクションを設定するパスの各リンク上では同一の波長を用いなければならない。本研究は波長変換を行わないSingle-fiberまたMulti-fiberを持つWDMネットワークに注目し、光ルーティングと波長割当問題を研究している。研究の内容はまず静態トラヒックにおけるRWA問題を研究し、次に動態トラヒックにおけるRWA問題を研究している。 1.静態トラヒックにおけるRWA問題の研究 理想的な光ネットワークは全てのソースと目標ノード間にライトパスが用意されている。このような静態トラヒックはN個ノードのネットワークに対してN(N-1)個のソースと目標ノードのペアがある。このN(N-1)個のコネクションに対して波長資源を有効に利用しライトパスを設定することが目標である。そこで、本研究はGridとShufflenet 2つ規則的なネットワークに注目し、2つのネットワークとも持つ特性−対称性を利用し、対称的なルーティング手法を提案した。またGridネットワークに対して特別な波長割当手法を提案した。この提案手法によって、N(N-1)本のライトパスを設定する際、必要となる波長の数量は従来の手法より大幅に減らすことが出来る。 2.動態トラヒックにおけるRWA問題の研究 動態トラヒックのパタン情報を用いてRWAを行う際、ライトパス設定の呼損性能を改善することが考えられる。そこで、まず動態トラヒックのパタン情報を利用し、最適な静態ルーティングを行う。そして、各リンク上でのコネクション量がわかる。コネクションの数量指定されたスレッシュホールドより多いリンクがhot spot linkと呼ばれる。これらのhot spot linkはよく利用されているが、輻輳しやすいリンクである。そのため、hot spot linkの使用は注意を要する。リンク上のチャンネル保留手法を用いて、呼損性能を改善することによって、本研究は動態トラヒック下のhot spot linkと見るリンクのみ波長チャンネルを保留する手法を提案した。これにより、Single-fiberまたMulti-fiberを持つネットワークに対して、呼損性能を改善することが可能になる。また、従来の手法のように全てのリンクではなく、hot spot linkと見る部分的なリンク上のみ波長チャンネルを保留することによって、ネットワークの制御が簡化された。 II. WDM光ネットワークおける論理トポロジーの設計に関する研究 ネットワークには長期的なコネクション要求が存在している。これらの長期的なコネクションのためにライトパスを設定する際、ネットワークリソース(トランスミッタ・レシーバや波長など)を有効に利用しなければならない。この問題は論理トポロジーの設計と見られている。ネットワークの物理トポロジーはノードとファイバーによって構成されており、IP over WDMの場合、論理トポロジーは各波長によるIPルータ間の仮想リンク=ライトパスによって構成される上位レイヤ(IP)のトポロジーを指す。論理トポロジーは各ノードにおける光ADMやトランスミッタ・レシーバの配置によって決まることから、これらの構成要素を用いてネットワークの論理トポロジーの再配置が可能になる。これにより、各波長のチャンネルにおけるトラヒックパターンや負荷に従ってルータにおけるトラヒック負荷を減らすことが出来る。さらに、ライトパスを中継するルータでの電気処理により生じる遅延を減らすことが出来、上位レイヤ(IPレイヤなど)ネットワークの通信品質を改良することが可能となる。従来の論理トポロジー構築の手法としては、主にネットワークのスループットを増大させるように設計されてきた。しかし、これらの手法ではライトパスを中継するルータでの電気処理により生じる遅延についてはほとんど考慮されていない。そこで本研究では、ホップ数を低く抑えることで、ルータにおける電気処理による遅延をできるだけ小さくするための論理トポロジーの設計を目指している。 1.新たな混合整数線形計画法モデル 論理トポロジーの設計方法によって、P2Pでの遅延を軽減し、ネットワークのスループットを向上させることが出来る。理想的な論理トポロジーの公式は、多くの場合、混合整数線形計画法から得ることが出来る。本研究はまずP2Pでの遅延を軽減し、ネットワークのスループットを向上させる混合整数線形計画法で新たなモデルを提案した。ここで、新たなモデルを提出する目的は論理トポロジー設計問題に対して従来の方法より新しい定義の構築を目指しているためである。混合整数線形計画法はネットワークサイズが大きくなるにつれて急速に計算量が増大して解答不能に陥ってしまう。事実、これを含めた系列問題の中にはNP困難として知られているものもあるため、サイズの大きなネットワークではこの問題を厳密に解こうとするのは現実的ではない。ここに、適切な近似を得るための発見的な方法が必要になってくる。 2.発見的な論理トポロジー設計アルゴリズム 本研究は上位レイヤネットワークの平均ホップ数を低く抑えること、また、論理リンクでの輻輳を軽減することに注目し、最短の平均ホップ数手法を提案した。従来の手法との比較により、提案手法−最短の平均ホップ数法を従来の手法とも適用領域があることが判明した。そこで、提案手法と従来の方法の相互の利点を用いて新たな方法を提案した。提案手法によって従来の設計手法よりもホップ数の少ない、かつ輻輳の小さい論理トポロジーの設計が可能となった。またソースと目標間での電気処理により生じる遅延を抑えることができる。 3.リンクの輻輳と中継ルータでの処理遅延に注目したIPトラヒックルーティング 従来の公式的な論理トポロジー設計方法の中では、リンクの輻輳しか考えられていないが、提案した新たなモデルでは、リンクの輻輳と中継ルータでの処理負荷に注目したIPトラヒックルーティングを利用した。これにより、設計した論理トポロジー上では輻輳の小さく、かつソースと目標間での電気処理により生じる遅延の小さい静的なIPルーティングが可能となった。 今後の課題 より上位のレイヤ、具体的にはIPレイヤでの品質制御と、波長レベルでのネットワーク制御との連携について研究を展開して行きたい。類似研究としてGMPLS等が実用化されつつある現在、GMPSを超克した新たな波長制御とIPレイヤの品質制御の連携手法の枠組みを創出することは緊急の研究課題である。波長制御は、ネットワークトポロジーの再構築や、物理的リンク増設などのネットワークプラニング、また障害時のネットワークの回復手法と継続的なリンク接続の保持方法などとも密接に関連するものであり、これらとの関連を視野に入れた幅広い視点での波長制御とIP品質制御との統合的な取り扱いについての枠組みを創出することを考えている。 | |
審査要旨 | 本論文はStudies on the Nctwork Control and Logical Topology Design in WDM Optical Networks(WDM光ネットワークにおけるネットワーク制御と論理トポロジーの設計に関する研究)と題し、全7章よりなる。 第1章はIntroductionであり本論文の課題と研究背景、即ち光ファイバを用いた高速広帯域通信網の必要性、ノード構成に必要となる光部品、WDM技術の現状と将来について述べている。 第2章はSurvey on the Routing and Wavelength Assignment methodと題し、バックボーンネットワークに対する既存のルーティング手法及び波長割当ての手法を、静的/動的割当て、波長変換の有無、ファイバの本数などの観点から分類・概観すると共にこれらの問題点を明確化すし、本研究の位置付けについて整理している。 第3章はStatic Routing and Wavelength Assignmentと題し、静的なルーティングの元での固定的な波長割当て問題を取り扱っている。特に規則的なトポロジーをもつネットワークにおける波長割当て問題に対して検討を行い、グリッド型トポロジーやシャッフルネット型トポロジーに対して、その対象性を利用した高速な波長割当て手法を提案すると共に、ネットワーク規模が大きい場合にもスケーラビリティが確保出来ることを明らかにすることにより、提案手法の有効性を示している。 第4章はDynamic Routing and Wavelength Assignmentと題し、動的なルーティングの元での動的な波長割当て問題を取り扱っている。ここでは全波長のうちある割合を留保しておく手法と、最も利用率の高いリンクを出来る限り迂回する手法を組み合わせたルーティング手法を提案している。また、提案手法のトラヒックシミュレーションによる評価を行い、最短経路を常に優先する従来手法に比べて、スループットを向上させる余地があることを示すことにより、提案制御手法の有効性を明らかにしている。更に、波長留保の割合と迂回制御を行う割合を規定するパラメータの推奨値について具体的な例を示すと共に、定性的な検討を行っている。 第5章はNew Model of Logical Topdogy Design Problemと題し、論理的ネットワークトポロジーの最適化問題の厳密解法の検討を行っている。従来、この問題はMixed Interger Linear Programming(MILP)の形で定式化することで最適化が行われてきたがリンク輻輳しか取り扱えない欠点があった。ここではトラヒックの増加に伴うノードでの処理時間の増加をも考慮した形式でのMILPへの定式化を行い、より現実的な制約の元での論理トポロジーの最適化が理論的に可能であることを示した。 第6章はThe heuristic method of Logical Topology design in WDM Optical Networksと題し、論理的ネットワークトポロジーの最適化問題の近似解法の検討を行っている。第5章で検討したMILPはNP完全問題であるため大規模のネットワークに対して適用することは困難である。ここでは既存の近似解法を概観すると共に、これを改良したMinimum average logical hop method (MALH)等のいくつかの手法を提案し、これら近似解法の比較検討を行うと共にその適用領域について論じている。 第7章は「結論」であり、本研究で得られた成果をまとめると共に、今後の展望に言及している。 以上これを要するに、本論文は光ファイバを用いた高速広帯域通信網における静的な光パスの設定方法、ルーティング手法、最適論理的トポロジーの導出方法を提案すると共に、その有効性を示したものであって、電子情報工学、特に通信工学に貢献するところが少なくない。よって本論文は博士(工学)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク |