現今光纖網路由於分波多工技術（Wavelength Division Multiplexing, WDM）的成熟大幅了提升整體網路的頻寬，然而分波多工所特有的波長連續性限制(Wavelength Continuity Constraint)會使網路資源無法充分利用，而導致較高的連線阻斷機率（Blocking Probability），相對影響了整體網路的服務品質。為了有效改善連線阻斷問題，路由與波長配置(Routing and Wavelength Assignment, RWA）以及將路由與波長配置結合波長轉換器(Wavelength Converter)同時考量成為現階段常被討論的議題。其路由方法中的FPLC ( Fixed-Paths Least-Congestion)能有效降低連線阻斷率，但路由決策必須花費許多時間對網路上的資訊做收集，因而產生較高的連線建立延遲(Setup Delay)與控制負載(Control Overhead)；而另一種方法FPLC-k對路由決策只需少數k段鏈路(Link)的鄰近資訊(Neighborhood Information)就能決定，但因資訊不充足可能會造成較高的連線阻斷率。本研究提出一個新的動態路由演算法稱為以門檻值為基礎之最少壅塞路由(Threshold-based Least Congestion Routing, TLCR)來改善上述問題。實驗的結果顯示，TLCR在阻斷機率上與FPLC能有相同的效能，並且比FPLC-k的路由決策更具有彈性。另一方面，在網路中考量稀疏波長轉換器之情況，TLCR與FAR、LLR比較也有相當不錯的連接效能。

Nowadays optical networks have been enhanced the overall capacity because of the maturity of WDM technology. However, the wavelength continuity constraint in WDM networks prevents network resources from being fully utilized and hence results in high blocking probability. To improve the blocking probability, how to devise an effective routing and wavelength assignment(RWA) algorithm becomes an important issue. Some previous works show that FPLC can reduce the blocking probability effectively but make routing decision costly because it needs complete wavelength information and hence results in high setup delay and complex control overhead. FPLC-k, FPLC’s variant, only needs neighborhood information of few first k links of routes to make decision, but tradeoff higher blocking probability since less wavelength information is considered. In this dissertation, we propose a new dynamic routing algorithm, threshold-based least congestion routing (TLCR). This algorithm can reduce setup time and control overhead without sacrificing blocking probability. The experiment results show that TLCR has the same performance as FPLC in blocking probability and but is more flexible in routing decision than FPLC-k. Therefore, it can work under the requirement of low setup delay and control overhead. Some experiments with sparse wavelength converter placement also show that TLCR is comparable with FAR and LLR in terms of blocking probability.

摘要 i
Abstract ii
致謝 iv
目錄 v
圖目錄 vii
第一章 緒論 1
1.1 研究背景 1
1.2 動機 3
1.3 研究目的 4
1.4 研究貢獻 5
1.5 論文架構 5
第二章 文獻探討 6
2.1 分波多工網路之演進 6
2.2 分波多工技術及系統架構 6
2.3 分波多工系統之相關設備 8
2.3.1 摻鉺光纖放大器 (Erbium Doped Fiber Amplifier, EDFA) 8
2.3.2 光塞取多工器 (Optical Add/Drop Multiplexer, OADM) 9
2.3.3 光交換器 (Optical Cross-Connects, OXC) 10
2.4 分波多工網路架構 13
2.5 光路徑之概念及限制 15
2.6 路由與波長配置介紹 16
2.6.1 路由演算法 17
2.6.2 波長配置 21
2.7 路由演算法種類 23
2.7.1 最短路徑路由 (SP) 23
2.7.2 固定式交替路由 (FAR) 23
2.7.3 最少流量負載路由演算法 (LLR) 24
2.7.4 固定式最少壅塞路由演算法 (FPLC) 25
2.7.5 網路資訊之收集 26
2.8 SP、FAR、LLR及FPLC之效能比較 27
2.9 改善連線建立延遲及控制負載之議題 28
2.9.1 Fixed-Paths Least-Congestion-k (FPLC-k) 28
2.9.3 Hybrid Fixed-Paths Least Congested Routing (HFPLC-k) 29
2.10 波長轉換器介紹 30
第三章 以門檻值為基礎之最少壅塞路由 34
3.1 TLCR演算法 34
3.2 TLCR虛擬碼流程 38
第四章 模擬及效能評估 41
4.1 模擬環境 41
4.2 模擬結果與分析 44
4.2.1 TLCR阻斷效能分析 44
4.2.2 TLCR與FAR、LLR、FPLC之阻斷效能比較 47
4.2.3 TLCR與FPLC-k之阻斷效能比較 50
4.2.4 TLCR與FPLC在資訊收集之平均路徑長度的比較 52
4.2.5 在配有稀疏波長轉換器之情況下阻斷效能的比較 54
第五章 結論與未來研究 58
參考文獻 60

[1] A. Mokhtar, M. Azizoglu, “Adaptive Wavelength Routing in All-Optical Networks,” IEEE/ACM Transactions on Networking, vol. 6, issue 2, pp. 197–206, Apr. 1998.
[2] A. S. Arora and S. Subramaniam, “Converter Placement in Wavelength Routing Mesh Topologies,” IEEE International Conference on Communications, pp. 1282–1288, June 2000.
[3] Arun K. Somani, “Survivability and Traffic Grooming in WDM Optical Networks,” Cambridge, 2006.
[4] B. Zhou, H. T. Mouftah, “Adaptive Least Loaded Routing for Multi-fiber WDM Networks using Approximate Congestion Information,” IEEE International Conference on Communications, vol. 5, pp. 2745- 2749, Apr. 2002.
[5] C. Siva Ram Murthy, M. Gurusamy, “WDM Optical Networks: Concepts, Design, and Algorithms,” Englewood Cliffs, NJ: Prentice Hall, 2001.
[6] C. X. Xiao, Y. Guo, J. F. Dai, “A Synthetic Algorithm for Wavelength Routing in Optical Network,” Journal of Electronics (CHINA), vol. 24, issue 1, pp. 46-49, Jan. 2007.
[7] Cisco, Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, Available: http://www.cisco.com/en/US/hmpgs/index.html
[8] D. Mitra and J. B. Seery, “Comparative Evaluations of Randomized and Dynamic Routing Strategies for Circuit-Switched Networks,” IEEE Transactions on Communications, vol. 39, pp. 102–116, Jan. 1991.
[9] D. Zhemin and M. Hamdi, “A Simple Routing and Wavelength Assignment Algorithm using the Blocking Island Technique for All-Optical Networks,” IEEE International Conference on Communications, vol. 5, pp. 2907–2911, Apr. 2002
[10] E. E. Bedeer, H. M. H. Shalaby, El-Badawy, S. A. Khamis, “A Heuristic Method of Logical Topology Design in WDM Optical Networks,” 25th National Radio Science Conference, pp. 1-11, Mar. 2008.
[11] E. Karasan, and E. Ayanoglu, “Effects of Wavelength Routing and Selection Algorithms on Wavelength Conversion Gain in WDM Optical Networks,” IEEE/ACM Transactions on Networking, vol. 6, pp. 186-196, Apr. 1998.
[12] G. Markovic, V. Acimovic-Raspopovic, “A Procedure of Wavelength Rerouting in Optical WDM Networks,” 7th International Conference on Telecommunications in Modern Satellite Cable and Broadcasting Services, vol. 1, pp. 303- 306, Sept. 2005.
[13] H. C. Lin, S. W. Wang, M. L. Hung, “Finding Routing Paths for Alternate Routing in All-Optical WDM Networks,” Journal of Lightwave Technology, vol. 26, issue 11, pp. 1432-1444, June 2008.
[14] J. Ahmad, S. M. H. Zaidi, S. Nawaz, “Dynamic routing in Wavelength Convertible WDM Networks,” 8th International Multitopic Conference, pp. 278- 283, Dec. 2004.
[15] J. S. Kim, D. C. Lee, H. Sridhar, “Route-Metric-Based Dynamic Routing and Wavelength Assignment for Multifiber WDM Networks,” IEEE Journal on Selected Areas in Communications, vol. 24, issue 12, pp. 56 – 68, Dec. 2006.
[16] J. Zheng and H. T. Mouftah, “Optical WDM Networks: Concepts and Design Priciples,” New York: Wiley, 2004.
[17] J. Zhou, X. Yuan, “A Study of Dynamic Routing and Wavelength Assignment with Imprecise Network State Information,” International Conference on Parallel Processing Workshops, pp. 207- 213, Aug. 2002.
[18] K. Roy, “A Simple Approach for Optimal Allocation of Wavelength Converters in WDM Optical Networks,” International Conference on Wireless and Optical Communications Networks, pp. 1-5, July 2007.
[19] K. Xi, S. Arakawa, M. Murata, “An Efficient Algorithm for Converter Placement in Dynamic WDM Networks,” IEEE International Conference on Communications, vol. 3, pp. 1884-1890, May 2005.
[20] L. Li and A. K. Somani, “Dynamic Wavelength Routing Using Congestion and Neighborhood Information,” IEEE/ACM Transactions on Networking, vol.7, pp. 779-786, Oct. 1999.
[21] N. S. Kojic, I. S. Reljin, B. D. Reljin, “Different Wavelength Assignment Techniques in All-Optical Networks Controlled by Neural Network, ” 8th International Conference on Telecommunications in Modern Satellite, Cable and Broadcasting Services, pp. 401-404, Sept. 2007.
[22] P. Rajalakshmi, A. Jhunjhunwala, “Analytical Tool to Achieve Wavelength Conversion Performance in No Wavelength Conversion Optical WDM Networks,” IEEE International Conference on Communications, pp. 2436 – 2441, June 2007.
[23] R. Mewanou, S. Pierre, “Dynamic Routing Algorithms in All-Optical Networks,” IEEE Canadian Conference on Electrical and Computer Engineering, vol. 2, pp. 773 – 776, May 2003.
[24] T. Ohara, H. Takara, T. Yamamoto, H. Masuda, T. Morioka, M. Abe, H. Takahashi, “Over-1000-channel Ultra Dense WDM Transmission with Supercontinuum Multicarrier Source,” Journal of Lightwave Technology, vol. 24, pp. 2311-2317, June 2006.
[25] Wikipedia, Wavelength-division Multiplexing, Available:
http://en.wikipedia.org/wiki/wavelength_division_multiplexing.
[26] X. W. Chu, B. Li, “Dynamic Routing and Wavelength Assignment in the Presence of Wavelength Conversion for All-Optical Networks,” IEEE/ACM Transactions on Networking, vol. 13, issue 3, pp. 704 – 715, June 2005.
[27] X. W. Chu, B. Li, “Wavelength Converter Placement under Different RWA Algorithms in Wavelength-Routed All-Optical Networks,” IEEE Transactions on Communications, vol. 55, issue 4, pp. 607-617, Apr. 2003.
[28] X. W. Chu, B. Li, Z. Zhang, “A Dynamic RWA Algorithm in A Wavelength-Routed All-Optical Network with Wavelength Converters,” Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1795 – 1804, Apr. 2003.
[29] Y. Yoo, S. Ahn, C. S. Kim, “Adaptive Routing Considering the Number of Available Wavelengths in WDM Networks,” IEEE Journal on Selected Areas in Communications, vol. 21, issue 8, pp. 1263–1273, Oct. 2003.
[30] 王崗嶸, 陳鴻仁, “DWDM技術入門,” 全華科技圖書股份有限公司, 台北, 2002.
[31] 蔡仲鵬, 林華君, “全光式WDM網路上固定式替用繞徑演算法的路徑排序方式,” 國立清華大學資訊工程學系, 2004.
[32] 蘇皇文, “分波多工網際網路之跨層保護技術研究,” 國立中央大學通訊工程研究所, 2005.