本論文探討在疏光分離 (Sparse-Splitting)的光波長路由網路(Wavelength-Routed Network) 上進行全光群播的技術。在疏光分離的網路中，只有部分的光交換機具有全光群播的能力，其餘的只能夠進行一對一的信號交換，因此傳統的群播路由演算法並不適用。一種常見的解決方案是，首先在不考慮疏光分離的條件下套用最小成本樹的演算法得到初步的解，接著再將這個結果修改以符合底層網路的限制。雖然計算最小成本樹有許多有效的演算法，但由於第二個步驟會需要額外的成本，這種做法會導致所計算出來的全光群播樹需要極高的網路資源(波長頻道的數目)。有別於此，我們提出一種新的機制，使得所長出來的全光群波樹的成本，能夠直接由最小成本樹演算法來決定；並且以此為基礎，設計出兩個有效的全光群播路由演算法來減少所需要的網路資源；同時，我們也將所設計的演算法延伸到群體中的成員會動態改變的情形。為了評估這些方法的效能，我們推導出這些方法所計算出的解所需要的最高成本。結果發現，藉由我們的方法所長出來的全光群波樹，其所需要的成本，最多不會超過最低成本的3倍；同時，我們也進行了詳盡的模擬，並和現存的文獻相互比較。結果顯示，我們的方法無論是在所需要的波長頻道數目，或者是所需要的波長數目上，都是最佳的解決方案。

This thesis studies all-optical multicast routing in wavelength-routed optical networks with sparse light splitting. In a sparse splitting network, only a small percentage of nodes are capable of light splitting, i.e., multicast capable, and the rest are multicast incapable. The typical solutions of existing multicast routing algorithms for sparse splitting networks combine an existing Steiner Tree heuristics with some rerouting procedures to refine the trees. The resulting tree cost in terms of the total number of wavelengths used on all tree links (i.e., wavelength channel cost) is then very expensive. In this thesis, we propose a new mechanism that constructs all-optical light-trees for sparse splitting networks without an additional rerouting procedure in the tree construction. We suggest two efficient approaches to grow a light-tree for a given multicast session in which the tree cost is minimized, and extend our mechanism to support dynamic group membership in the network. Their performances are evaluated by estimating their worst-case bound. The result shows that the suboptimal solution generated by our approach is within triple of the optimal one. Also, an extensive simulation is conducted to compare the performance of our mechanism with existing work. The results show that our mechanism builds light-trees with the least wavelength channel cost and with the smallest number of wavelengths used per link.

Content
CHAPTER 1 INTRODUCTION 1
1.1. WAVELENGTH ROUTED NETWORK 1
1.2. ALL-OPTICAL MULTICASTING 2
1.3. RELATED WORK 5
1.4. MOTIVATION 8
1.5. ORGANIZATION 10
CHAPTER 2 LIGHT-TREE CONSTRUCTION METHOD 11
2.1. NETWORK MODEL AND PROBLEM STATEMENTS 11
2.1.1. Assumptions 11
2.1.2. Network Model and Notations 11
2.1.3. Problem Statements 12
2.2. MINIMUM-COST MC-TREE 14
2.3. THE SELECTION POLICY OF MC NODES 16
2.4. REDUCED COMPLEXITY OF MC-TREE 19
2.5. WORST-CASE TREE COST ANALYSIS 21
2.5.1. Analysis for NMCF 22
2.5.2. Analysis for OTMCF 26
2.6. FROM STATIC TO DYNAMIC GROUP MEMBERSHIP 28
CHAPTER 3 PERFORMANCE EVALUATION 30
3.1. SIMULATION ENVIRONMENT 30
3.2. WAVELENGTH CHANNEL COST 31
3.3. MAXIMUM NUMBER OF WAVELENGTHS USED PER LINK 37
CHAPTER 4 CONCLUDING REMARKS 42
FUTURE WORK 43
REFERENCE 44
APPENDIX 46

Reference
[1] L. H. Sahasrabuddhe and B. Mukherjee, “Light-trees: Optical Multicasting for Improved Performance in Wavelength-Routed Networks,” IEEE Communications Magazine, vol. 37, pp. 67-73, Feb. 1999.
[2] W.S.Hu and Q.J.Zeng, “Multicasting optical cross connects employing splitter-and-delivery switch, “ IEEE Photon. Technol. Lett., vol. 10, pp. 970-972, July 1998
[3] X. Zhang, et al., ”Constrained Multicast Routing in WDM Network with Sparse Light Splitting,” IEEE Journal of Lightwave Technology, vol. 18, no. 12, Dec. 2000.
[4] B. Chen and J. Wang, “Efficient Routing and Wavelength Assignment for Multicast in WDM Networks,“ IEEE JSAC, vol. 20, no. 1, Jan. 2002.
[5] G. Sahin and M. Azizoğlu, “Multicast Routing and Wavelength Assignment in Wide Area Networks,” in SPIE, vol. 2531, Nov 1998.
[6] S. Yan, et al., “Route Optimization of Multicast Sessions in Sparse Light-Splitting Optical Networks,” IEEE GLOBECOM, 2001
[7] W.- Y. Tseng et al. “All-Optical Multicasting on Wavelength-Routed WDM Networks with Partial Replication,” IEEE ICC ‘01, Helsinki, Finland, June 2001.
[8] N. Sreenath, “Virtual Source based Multicast Routing in WDM Networks with Sparse-Light Splitting,” IEEE High Performance Switching and Routing, 2001
[9] M. Ali and J. Deogun, “Allocation of Multicast Nodes in Wavelength-Routed Networks,” IEEE ICC ‘01, Helsinki, Finland, June 2001.
[10] A. Mokhtar and M. Azizoglu, “Adaptive Wavelength Routing in All-Optical Networks,” IEEE/ACM Trans. Net., vol. 6, Apr. 1998, pp. 197-206.
[11] H. Zang, J. P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed Optical WDM Networks,” Optical Networks Magazine, vol. 1, Jan. 2000, pp. 47-60
[12] H. Takahashi and A. Matsuyama, “ An approximate solution for the Steiner problem in graphs,” Math, Japonica, vol.24, no.6, pp. 573-577
[13] B. Waxman, “Routing of multipoint connections, “ IEEE J. Selected Areas Comm., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.
[14] M. Smith and P. Winter, “Path-distance heuristics for the Steiner problem in undirected networks,” Algorithmica, vol. 7, no. 2-3, pp. 309-327, 1992.
[15] L. Kou, G. Markowsky, and L. Berman, “A Fast Algorithm for Steiner Trees, “ Acta Informatica, 1981, pp. 141-45.
[16] Wang and J. Hou, “Multicast routing and its QoS extension problems, algorithms, and protocols,” IEEE Network, pages 22-36, January 2000.
[17] K. Calvert and E. Zegura, “GT Internetwork Topology Models (GT-ITM),” available at: http://www.cc.gatech.edu/fac/Ellen.Zegura/gt-itm
[18] A. Shaikh and K. Shin, “Destination-Driven Routing for Low-Cost Multicast, ” IEEE J. Selected Areas Comm., vol.15 issue 3, Page(s): 373 -381, April 1997.
[19] F. Hwang and D. Richards, “Steiner tree problems,” Networks, vol. 22, pp. 55-89, 1992