臺灣博碩士論文加值系統

隨著光波長多工光網路的不斷發展，一條光纖所能攜帶的光波長數目不斷以倍數增加，光網路交換器（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.

謝 誌 I
論文摘要 III
THESIS ABSTRACT V
Contents VII
List of Tables IX
List of Figures X
Chapter 1 Introduction 1
1.1 Background 1
1.1.1 DWDM Technology 1
1.1.2 OADM and OXC 4
1.1.3 GMPLS 8
1.2 Motivation 9
1.3 Literature Survey 11
1.3.1 RWA Related Issues 11
1.3.2 Homogeneous Network 12
1.3.3 Heterogeneous Network 15
1.3.4 Lagrangean Relaxation 15
1.4 Thesis Organization 17
Chapter 2 Problem Formulation 19
2.1 Problem Description 19
2.2 Graph Transformation 21
2.3 Notation 23
2.4 Problem Formulation 25
Chapter 3 Solution Approach 28
3.1 Lagrangean Relaxation 28
3.2 Subproblem 28
3.2.1 Subproblem 1 29
3.2.2 Subproblem 2 34
3.3 The Dual Problem and the Subgradient Method 36
3.4 Lagrangean Relaxation with Heuristics 37
Chapter 4 Getting Primal Feasible Solutions 39
4.1 Getting Primal Algorithms 39
4.2 Simple Heuristic Algorithms 42
Chapter 5 Computational Experiments 45
5.1 Experiment Environment 45
5.2 Seven-node Small Network 46
5.2.1 Network Topology 46
5.2.2 Solution Quality 47
5.2.3 Computation Time 50
5.3 GTE Network 52
5.3.1 Network Topology 52
5.3.2 Solution Quality 53
5.4 USA Network 55
5.4.1 Network Topology 55
5.4.2 Solution Quality 56
5.4.3 Computation Time 58
5.5 Discussion 59
5.5.1 Number of Wavelengths 59
5.5.2 Number of Wavebands 60
5.5.3 Scalability 61
Chapter 6 Conclusion and Future Work 63
6.1 Conclusion 63
6.2 Future Work 65
Reference 67

[1] L. Berger,” Generalized Multi-Protocol Label Switching (GMPLS) Signaling Functional Description”, IETF RFC 3471, January 2003.
[2] R. Douville, D. Papadimitriou, and E. Dotaro,“ Extensions to Generalized Multi-Protocol Label Switching in support of Waveband Switching“, IETF Internet Draft, July 2004.
[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.
[8] S. S.W. Lee, M. C. Yuang, P. Tien, and S. Lin, “A Lagrangean Relaxation-Based Approach for Routing and Wavelength Assignment in Multigranularity Optical WDM Networks”, IEEE Journal on Selected Areas in Communications, Vol.22, No.9, November 2004.
[9] J. W. Suurballe, R.E. Tarjan, “A Quick Method for Finding Shortest Pairs of Disjoint Paths”, Networks, Vol.14, 1984.
[10]J. W. Suurballe, “Disjoint Paths in a Network”, Networks, Vol.4, 1974.
[11]C. H. Papadimitriou, K. Steiglitz, “Combinatorial optimization : algorithms and complexity”, Prentice Hall, 1982.
[12]R. K. Ahuja, T. L. Magnanti, J. B. Orlin, ”Network flows : theory, algorithms, and applications”, Prentice-Hall International, 1993.
[13]S. S.W. Lee, “Introduction to IP over Wavelength Division Multiplexing (WDM) Network Technology” Presentation, March 2004.
[14]J. Bowers, “Fiber Optics” lecture notes in UCSB, 2004.
[15]R. Helkey, et al, ”Design of Large, MEMS-Based Photonic Switches”, Optics & Photonics News, May 2002
[16]P. H. Ho, H. T. Mouftah,and J. Wu, ”A Scalable Design of Multigranularity Optical Cross-Connects for the Next-Generation Optical Internet”, IEEE Journal on Selected Areas in Communications, Vol.21, No.7, Sep. 2003.
[17]M. L. Fisher, “The Larganian Relaxation Method For Solving Integer Programming Problems”, Management Science, Vol.27, No.1, January 1981.
[18]R. Parthiban, R. S. Tucker, “Waveband Grooming and IP Aggregation in Optical Networks”, IEEE Journal of Lightwave Technology, Vol.21, No.11, November 2003.
[19]郭至鈞， 以波長路由為基礎之多波長分工網路上群播樹合併演算法 ，國立台灣大學資訊管理學研究所碩士學位論文，民國九十二年七月。
[20]顏宏旭著，電腦網路與後勤網路之規劃與容量管理，國立台灣大學資訊管理學研究所博士學位論文，民國九十年六月。