異質性光波長多工光網路之交換器配置演算法

Switch Placement Algorithms in Optical WDM Heterogeneous Networks

張孝澤(Hsiao-Tse Chang)

指導教授 ： 林永松

共同指導教授 ： 顏宏旭(Hong-Hsu Yen)

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.01914

摘要

隨著光波長多工光網路的不斷發展，一條光纖所能攜帶的光波長數目不斷以倍數增加，光網路交換器（OXC）的複雜度與成本也隨之增加。GMPLS定義了三種光交換的方式：光纖交換、光波段交換與光波長交換。而在異質性網路下，允許每個節點有其中一種光交換的能力。光網路建置成本最大的來源即是光網路交換器，而光網路交換器的成本又與其所使用的埠數目直接相關，因此當一條光纖能攜帶數百條光波長時，光波長交換器的成本也將提高數百倍，且交換器埠的數目至今仍有設計上的數量瓶頸存在。

此篇論文的目的即是希望在異質性網路下，妥當的規劃各節點，以最低的成本而能滿足網路上所需的靜態流量要求。我們將這個問題建立成一個數學模型，透過目標函式與限制式來適當的描述此問題，是一個整數規劃的問題，問題的本身具有高度的複雜性和困難度。因為光網路路由與光波長配置的問題（RWA）已知為一個NP-hard的問題，而此問題隱含了RWA問題，因此此問題也是一個NP-hard問題，無法在有限的時間內以已知有效的演算法解決。因此我們採用最佳化領域中的拉格蘭日鬆弛法（Lagrangean Relaxation）來解決此問題。

另外，我們根據[8]中的RWA問題發展出一個簡易的交換器配置演算法，我們設計數項實驗在不同的網路拓撲下測試所提出演算法與簡易演算法相比，實驗結果顯示都有較佳的結果。

關鍵字

光波長多工 ； 光網路規劃 ； 光纖交換 ； 光波段交換 ； 光波長交換 ； 最佳化 ； 拉格蘭日鬆弛法 ； 數學規劃

並列摘要

With the rapid development of Wavelength Division Multiplexing (WDM), a fiber can carry more and more wavelengths, but the complexity and the cost of Optical Cross-connects (OXCs) also increase. To deal with the problem, General Multi-Protocol Labeling Switching (GMPLS) defines three kind of switching methods: fiber switch capable, waveband switch capable, and lambda switch capable. In a heterogeneous optical network, we allow each node to have one of the switching capabilities. OXCs contribute most to the planning cost of optical networks, and the cost of OXCs is in proportion to the number of ports. Therefore, while a fiber can carry hundreds of wavelengths, the cost of OXCs increases proportionally. Furthermore, there is still a shortage of ports in the OXC design.

In this thesis, we allocate the switch nodes properly based on the lowest cost, and satisfy all the static traffic demand in a heterogeneous network. We model this problem as an integer programming problem with an objective function and several constraints, which is very complicated. Since the routing and wavelength assignment problem (RWA) is a well known NP-hard problem, and our problem contains the RWA problem, our problem is also NP-hard. As we cannot solve it in polynomial time by well known algorithms, we adopt Lagrangean relaxation as the solution approach.
In addition, we propose a simple heuristic algorithm modified from an RWA problem, and conduct several experiments on different network topologies. We find that the experiment results of Lagrangean Relaxation are better then those of the simple heuristic algorithm.

並列關鍵字

Fiber Switch ； Lagrangean Relaxation Method ； Lambda Switch ； Mathematical Programming ； Network Planning ； Optimization ； Waveband Switch ； WDM

參考文獻

[3] Y. Suemura, et al, “Hierarchical Routing in Layered Ring and Mesh Optical Networks”, IEEE ICC 2002, May 2002.

[4] X. Cao, V. Anand, Y. Xiong, and C. Qiao, “A Study of Waveband Switching With Multilayer Multigranular Optical Cross-Connects, IEEE Journal on Selected Areas in Communications, Vol.21, No.7, September 2003.

[5] X. Cao, V. Anand, and C. Qiao, “A Waveband Switching Architecture and Algorithm for Dynamic Traffic”, IEEE Communications Letters, Vol.7 No.8, August 2003.

[6] P. H. Ho,and H. T. Mouftah, “Routing and Wavelength Assignment With Multigranularity Traffic in Optical Networks”, Journal of Lightwave Technology, Vol.20, No.8, August 2002.

[7] K. Zhu, H. Zhu, and B. Mukherjee, “Traffic Engineering in Multigranularity Heterogeneous Optical WDM Mesh Networks through Dynamic Traffic Grooming”, IEEE Network, vol. 17, no. 2, March 2003.