林永松臺灣大學：資訊管理學研究所張孝澤Chang, Hsiao-TseHsiao-TseChang2007-11-262018-06-292007-11-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/54375隨著光波長多工光網路的不斷發展，一條光纖所能攜帶的光波長數目不斷以倍數增加，光網路交換器（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 671684334 bytesapplication/pdfen-US光波長多工光網路規劃光纖交換光波段交換光波長交換最佳化拉格蘭日鬆弛法數學規劃Fiber SwitchLagrangean Relaxation MethodLambda SwitchMathematical ProgrammingNetwork PlanningOptimizationWaveband SwitchWDMotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54375/1/ntu-94-R92725014-1.pdf