請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36084
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林永松(Yeong-Sung Lin) | |
dc.contributor.author | Hsiao-Tse Chang | en |
dc.contributor.author | 張孝澤 | zh_TW |
dc.date.accessioned | 2021-06-13T07:51:02Z | - |
dc.date.available | 2007-07-27 | |
dc.date.copyright | 2005-07-27 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-07-25 | |
dc.identifier.citation | [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]顏宏旭著,電腦網路與後勤網路之規劃與容量管理,國立台灣大學資訊管理學研究所博士學位論文,民國九十年六月。 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36084 | - |
dc.description.abstract | 隨著光波長多工光網路的不斷發展,一條光纖所能攜帶的光波長數目不斷以倍數增加,光網路交換器(OXC)的複雜度與成本也隨之增加。GMPLS定義了三種光交換的方式:光纖交換、光波段交換與光波長交換。而在異質性網路下,允許每個節點有其中一種光交換的能力。光網路建置成本最大的來源即是光網路交換器,而光網路交換器的成本又與其所使用的埠數目直接相關,因此當一條光纖能攜帶數百條光波長時,光波長交換器的成本也將提高數百倍,且交換器埠的數目至今仍有設計上的數量瓶頸存在。
此篇論文的目的即是希望在異質性網路下,妥當的規劃各節點,以最低的成本而能滿足網路上所需的靜態流量要求。我們將這個問題建立成一個數學模型,透過目標函式與限制式來適當的描述此問題,是一個整數規劃的問題,問題的本身具有高度的複雜性和困難度。因為光網路路由與光波長配置的問題(RWA)已知為一個NP-hard的問題,而此問題隱含了RWA問題,因此此問題也是一個NP-hard問題,無法在有限的時間內以已知有效的演算法解決。因此我們採用最佳化領域中的拉格蘭日鬆弛法(Lagrangean Relaxation)來解決此問題。 另外,我們根據[8]中的RWA問題發展出一個簡易的交換器配置演算法,我們設計數項實驗在不同的網路拓撲下測試所提出演算法與簡易演算法相比,實驗結果顯示都有較佳的結果。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T07:51:02Z (GMT). No. of bitstreams: 1 ntu-94-R92725014-1.pdf: 1684334 bytes, checksum: 9a4ba412e21498d5154296eff938031a (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | 謝 誌 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 | |
dc.language.iso | en | |
dc.title | 異質性光波長多工光網路之交換器配置演算法 | zh_TW |
dc.title | Switch Placement Algorithms in Optical WDM Heterogeneous Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 顏宏旭(Hong-Hsu Yen) | |
dc.contributor.oralexamcommittee | 趙啟超(Chi-chao Chao),林盈達(Ying-Dar Lin),呂俊賢(Chun-Hsien Lu) | |
dc.subject.keyword | 光波長多工,光網路規劃,光纖交換,光波段交換,光波長交換,最佳化,拉格蘭日鬆弛法,數學規劃, | zh_TW |
dc.subject.keyword | Fiber Switch,Lagrangean Relaxation Method,Lambda Switch,Mathematical Programming,Network Planning,Optimization,Waveband Switch,WDM, | en |
dc.relation.page | 69 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-07-26 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 1.64 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。