臺灣博碩士論文加值系統

分波多工(Wavelength Division Multiplexing，WDM)網路使用波長路由繞送的方式傳送資料之技術已確定成為下一代網路的主要架構。為能利用少量的波長(wavelength)及波長通道(wavelength channel)來達到群播(multicast)傳送的目的，因此，在光學交換器上提供具有光分割(light splitting)及波長轉換(wavelength conversion)功能，此交換器亦稱為VS(virtual source)節點。VS節點成本較高，故一般僅有部份節點具有VS功能，透過配置具有VS功能節點及決定群播的傳送路徑，建構出群播樹(multicast tree)，以使得群播所使用的波長及波長通道數最少是一個值得研究的問題。
本論文主要研究在WDM網路環境下，給定一些群播的需求，與一個正整數k，如何配置k個VS節點，使得群播所使用的波長通道數最少的最佳化問題。因如何配置VS節點，使得所使用的波長通道數最小為NP-hard的問題，目前的解決方法均以啟發式演算法(heuristic algorithm)來探討如何配置VS節點的問題，因此本論文中提出以基因演算法(genetic algorithm，GA)來解決此問題，讓所求得解近似最佳解，而避免落入局部最佳解的情況。為了使每一個群播群組(multicast session)在建立群播樹(multicast tree)時，能使用到最少的波長通道數，在本論文中更提出了三種不同的路由繞送(routing)方式: (1) 核心樹(core-based tree，CBT)，(2) 鏈結互斥核心樹(link disjoint core-based tree，LDCBT)，(3) 層狀圖(layered graph)。
經過實驗，透過基因演算法所配置出VS節點的位置，再使用核心樹(CBT)、鏈結互斥核心樹(LDCBT)及層狀圖(layered graph)作為路由繞送，與配置於網路中分支度最大的位置(Max-Degree)或隨機位置(Random)的方法作比較，都能明顯的減少了波長通道數的使用。其中以layered graph作路由繞送的方法，能將群播樹所使用的波長通道數減到最少，約可減少了20%波長通道的使用率。但當群播群組需求增加時，所需的波長數增加，造成建立群播樹的時間耗費較長，而時間上來說則以CBT所花費的時間最短，並且在波長通道數的使用上可減少了約17%，亦相當接近使用layered graph方法時所使用的波長通道數。

Using wavelength routing technique for Wavelength Division Multiplexing (WDM) network will definitely be the main framework for network of the next generation. To reduce the number of used wavelengths (or wavelength channels) of multicast transmission, several optical switches in WDM network are equipped with light splitting and wavelength conversion capabilities which are denoted as Virutal Source (VS) nodes. VS node incurs a comparatively higher cost than normal switch, so only some of the switches may provide VS capabilities. Therefore, it is an important isseu that constructs multicast trees by using VS function such that the number of used wavelengths (or wavelength channels) can be minimized.
In this thesis, given a positive integer k, and a set of multicast requests, the goal is to determine the location of VS nodes, and determine the routing paths and wavelength assignments for multicast requests, such that the number of used wavelength channels can be minimized. This problem is a NP-hard problem, current approaches used to solve it is to design heurisitic algorithms. In this thesis, a genetic algorithm (GA) is proposed to solve this problem, the goal is to achieve the gobal optimum instead of local optimum. In this thesis, three multicast methods are proposed for establishing multicast tree. These are: (1) Core-Based Tree (CBT), (2) Link Disjoint Cored-Based Tree (LDCBT) and (3) Layered Graph.
Experiment results reveal that the reduced ratio of the number of used channels by using GA with CBT, LDCBT and Layered Graph, compared to the results obtained by Max-Degree or Random, in which VS nodes are assigned in a position with the highest degree or in random, respectively. Among these methods, the Layered Graph method can find the best result, and can reduce wavelength channels about 20%. When the demand increases, the CBT method can offer the best performance and can reduce the radio of the number of used channels about 17%.

摘要 I
ABSTRACT III
誌 謝 V
圖目錄 VIII
表目錄 X
第一章 序論 1
1.1 前言 1
1.2 研究動機 2
1.3 研究目的與主要貢獻 3
1.4 後續章節介紹 4
第二章 文獻探討 5
2.1 WDM簡介 5
2.2 群播 6
2.3 波長轉換 6
2.4 群播功能 7
2.5 Virtual Source 10
2.6 配置問題 11
2.6.1 MC placement 11
2.6.2 WC placement 12
2.6.3 VS placement 12
2.7 核心樹 14
2.8 基因演算法 14
第三章 研究問題定義與方法 17
3.1 研究問題定義 18
3.2 基因演算法(Genetic Algorithm) 19
3.2.1 編碼(encoding) 19
3.2.2 基因初值設定(initialization) 20
3.2.3 選擇(selection) 20
3.2.4 交配(crossover) 20
3.2.5 基因調整(Gene adjustment) 22
3.2.6 突變(Mutation) 24
3.2.7 取代(Replacement) 26
3.2.8 適應值函數(Fitness function) 26
3.2.9 基因演算法的流程 27
3.3 群播路由繞送(Multicast Routing) 27
3.3.1 CBT(core-based tree)方法 29
3.3.2 Link disjoint core-based tree方法 40
3.4 波長指派(Wavelength assignment) 42
3.5 層狀圖(Layered graph)方法 45
3.5.1 當來源節點不具有VS功能時 47
3.5.2 當來源節點具有VS功能時: 48
第四章 實驗結果 51
4.1 參數決定 51
4.2 效能比較 59
4.2.1 節點分支度與群播群組數之比較 59
4.2.2 群播群組增加時的比較結果 62
4.3 效能評估 63
第五章 結論 65
參考文獻 67

[1] Maher Ali, “Optimization of Splitting Node Placement in Wavelength-Routed Optical Networks,” IEEE Journal of Selected Areas in Communications, vol. 20, No. 8, October, pp.1571-1579, 2002.
[2] Maher Ali and Jitender Deogun, “Allocation of Splitting Nodes in All-Optical Wavelength-Routed Networks,” Photonic Network Communications, Vol.2, No.3, August, pp.247-265, 2000.
[3] Maher Ali and Jitender S. Deogun, “Cost-Effective Implementation of Multicasting in Wavelength-Routed Networks,” IEEE Journal of lightwave technology, Vol. 18, No. 12, December, pp.1628-1638, 2000.
[4] A. Ballardie, “Core Based Trees (CBT version 2) Multicast Routing,” RFC, No. 2189, September, pp.1-23, 1997.
[5] Yuan Cao and Oliver Yu, “Optimal Placement of Light Splitters and Wavelength Converters for Multicast in WDM Networks,” IEEE International Conference on Telecommunications, Vol. 1, May, pp.585-589, 2005.
[6] Chien Chen and S. Banerjee, “A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks,” IEEE Conference on Computer Societies, Vol. 1, No. 24, March, pp.164-171, 1996.
[7] Aijun Ding, Gee-Swee Poo, and Sun-Teck Tan, “An expanded graph model for MCRWA problem in WDM networks,” IEEE Conference on Local Computer Networks, No. 6, November, pp.557-564, 2002.

[8] C. Diot, W. Dabbous, and J. Corwroft, “Multipoint Communication: A survey of Protocols, Functions, and Mechanisms,” IEEE Journal of Selected Areas in Communications, Vol. 15, No. 3, April, pp.277-290, 1997.
[9] D. Estrin and D. Farinacci, “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification,” RFC, No. 2362, June, pp.1-66, 1998.
[10] Mitsuo Gen and Runwei Cheng, “Genetic Algorithms and Engineering Design,” John wiley & Sons, Inc, December, 1996.
[11] Goldberg, D.E., “Genetic Algorithms in Search, Optimization and Machine Learning, ” Addison-Wesley, 1998.
[12] Holland, J.H., “Adaptation in Natural and Artificial System,” Ann Arbor: The University of Michigan Press, 1975.
[13] Jingyi He, Chan, S.-H.G.., and Tsang, D.H.K., “Routing and wavelength assignment for WDM multicast networks,” Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE, Vol. 3, November, pp.1536-1540, 2001.
[14] Kuo-Chun Lee and Victor O. K. li, “A Wavelength-Convertible Optical Network,” IEEE Journal of lightwave technology, Vol. 11, No. 5, May-June, pp.962-970, 1993.
[15] J. Moy, “MOSPF: Analysis and Experience,” RFC, No. 1585, March, pp.1-13, 1994.
[16] M. N. Ransom and D. R. Spears, “Applications of public gigabit networks,” IEEE Networks, Vol. 6, No. 2, March, pp. 30-40, 1992.
[17] S. Runggeratigul, P. Thongsri, and P. Sumsiripong, “Optimal number of wavelength converters for WDM network design,” TENCON 2004. 2004 IEEE Region 10 Conference, Vol. 3, November, pp.93-96, 2004.
[18] Laxman H. Sahasrabuddhe and Biswanath Mukherjee “Light-Trees : Optical Multicasting for Improved Performance in Wavelength-Routed Networks,” IEEE Communications Magazine, Vol. 37, No. 2, February, pp.67-73, 1999.
[19] Johannes Hamonangan SIREGAR, Yongbing ZHANG, and Hideaki TAKAGI, “Optimal Multicast Routing Using Genetic Algorithm for WDM Optical Networks,” IEICE TRANS. COMMUN., Vol. E88-B, No. 1, January, pp.219-226, 2005.
[20] N. Sreenath, C. Siva Ram Murthy, and G. Mohan, “Virtual Source Based Multicast Routing in WDM Optical Networks,” IEEE International Conference, September, pp.385-389, 2000.
[21] N. Sreenath, N.Krishna Mohan Reddy, G. Mohan, and C. Siva RamMurthy, “Virtual Source Based Multicast Routing in WDM Networks with Sparse Light Splitting,” Workshop on High Performance Switch and Routing, May, pp.141-145, 2001.
[22] N. Sreenath and C. Siva Ram Murthy, “Virtual source based multicast traffic routing in IP-over-WDM networks,” Journal of High Speed Networks, Vol.13, No. 4, pp.265-281, 2004.
[23] D. Waitzman, C. Partridge, and S. Deering(editors), “Distance Vector Multicast Routing Protocol,” RFC, No. 1075, November, pp.1-23, 1998.
[24] Jianping Wang, Xiangtong Qi., and Mei Yang, “Routing and wavelength assignment for core-based tree in WDM networks,”Computer Communications, Vol. 29, No. 11, July, pp.1896-1904, 2006.
[25] Shuguang Yan, Maher Ail, and Jitender Deogun, “Route Optimization of Multicast Sessions in Sparse Light-splitting Optical Networks,” Global Telecommunications Conference, 2001. GLOBECOM ’01. IEEE, Vol. 4, November, pp.25-29, 2001.
[26] Keen-Mun Yong, Gee-Swee Poo, and Tee-Hiang Cheng, “Optimal placement of multicast and wavelength converting nodes in multicast optical virtual private network,” Computer Communications, Vol. 29, No. 12, August, pp.2169-2180, 2006.
[27] Wen-Yu Yseng and Sy-Yen Kuo, “All-Optical Multicasting on Wavelength-Routed WDM Networks with Partial Replication,” 15Th Internation Conference on Information networking, January-February, pp.813-818, 2001.
[28] X. Zhang, R. Malli, and C. Qiao, “Benefit of Multicasting in All-Optical Networks,” in SPIE Proc. Of Conf. All-optical Networking, Vol. 2531, November, pp.209-220, 1998.
[29] Xijun Zhang, John Y. Wei, and Chunming Qiao, “Constrained Multicasting Routing in WDM Networks with Sparse Light Splitting,” Journal of Lightwave Technology, Vol. 18, No. 12, December, pp.1917-1927, 2000.
[30] Auik Zsigri, Alexandre Guitton, and Miklos Molnar, “Construction of Light-Trees for WDM Multicasting under Capability Constraints,” 10Th International Conference on Telecommunications, Vol. 1, February-March, 2003.