當寬頻網路使用者急速擴增暨網路多媒体廣泛被使用，我們急需要一個超寬頻、大容量的高速網路呈現。多波長分工光纖網路(Wavelength-Division- Multiplexing) 擁有巨大傳輸容量，目前已漸成為寬頻網路的最佳平台。在多媒體時代的來臨，其相關應用程式如視訊會議、分散資料處理、視訊選播及網際網路等等應用，均需搭配寬頻群播路由傳輸 (Multicast Routing) 的使用；然而多波長分工光纖網路即是實現群播路由傳輸的最有效利器。群播路由傳輸包含一個來源 (Source) 及多組目的地 (Destination)，如何有效率將來源訊號資料傳送至目的地，在網路傳輸領域是個熱門研究主題。群播傳輸協定 (Protocol) 技術的演變伴隨傳輸介質改善而提升，由傳統一對一 (Unicast) 單點傳輸演變群播樹狀 (Tree) 傳輸；另外傳輸訊號也由電子訊號轉變成光訊號。
本論文旨在探討如何有效率運用多波長分工光纖網路在全光路徑下(Lightpath) 使用群播路由傳輸服務之研究。首先，我們提出一個在多波長分工光纖網路最佳化波長選擇 (Wavelength Assignment) 方法，即針對群播路由傳輸時有效率地選擇適當波長作傳輸使用。此方法使用完全連接節點(Full-Connected-Component) 原理，有效將傳輸網路切割成若干同波長小區域網路，即群播傳輸群體 (Multicast Group)，藉以達成簡化波長使用目的。
接著，我們提出群播路由傳輸最佳路徑選擇演算法 (Routing Path Selection Strategy)，針對群播路由傳輸時選擇最佳路徑傳輸。此演算法將原建立群播傳輸樹重新建立連接，從新建立群播傳輸樹裡找尋費用最節省路徑。最後，我們以實際網路作為模擬實驗，其模擬研究結果顯示，我們使用之最佳化波長選擇方法暨最佳路徑選擇演算法能有效提升多波長分工光纖網路群播路由傳輸約百分三十至四十之效益。

When numbers of network users have increased rapidly and the multimedia service of network extensively has applied, we need a high-capacity bandwidth, large-volume high-speed network to provide the service. Wavelength-division -multiplexing (WDM) optical networks with terabits per second bandwidth are the best choice as a backbone for the next generation optical networks. Accompanied with the advent of multimedia services such as video-conference, distributed data processing, video-on-demand application, and world-wide-web browsing, supporting multicast routing in WDM optical networks becomes an import challenge. In a multicast communication, a single data source transmits user data to one or more than one destination. It is a hot topic in multicast communication how the source data transmits efficiently to destinations? Multicast routing protocols have evolved to improve the transmission technology that one-to-one (Unicast) is changed to one-to-many (Multicast) and electrical signal is changed to optical signal.
In this dissertation studies the problems related to the implementation of all-optical multicast routing in WDM optical networks. First, we propose an optimal lightpath routing algorithm in WDM multicast routing network that can efficient multicast in WDM optical networks. For solving the wavelength assignment problem, an auxiliary graph is created where by the nodes and the links in the original network are transformed to the edges and the vertices, respectively, and the same availability wavelength of each edge is taken into a multicast group (Full-Connected-Component).
Next, for solving the routing path selection problem, we propose the shortest-path routing strategy to choose the best transmission path between two multicast groups. A distinguish feature of our algorithm can obtain the minimum cost, including the cost of each edge on the path and the wavelength conversion. From the simulation results shown that our algorithm improves the performance over 30%-40% of the call-connection probability than previous algorithms.

[1] M. S. Borella, J. P. Jue, D. Banerjee, B. Ramamurthy and B. Mukherjee, “Optical Components for WDM Lightwave Networks,” in Proc. of THE IEEE, Vol.85, No.8, pp.1274-305(1997).
[2] I. P. Kaminow, C.R. Doerr, C. Dragone, T. Koch, and U. Koren, “A Wideband All-Optical WDM Network,” IEEE J. Select. Areas in Commun., Vol.14, No.5, pp.780-796(1996).
[3] B. Mukherjee, “WDM Optical Communication Networks: Progress and Challenges,” IEEE J. Select. Areas in Commun., Vol.18, No.10, pp.1810-1822(2000).
[4] P. Bonenfant, and A. Rodriguez-Moral, “Optical Data Networking,” IEEE Commun. Mag., pp.63-69(2000).
[5] I. Chlamtac, A. Farago and T. Zhang, “Lightpath Routing in Large WDM Networks,” IEEE J. Select. Areas in Commun., Vol.14, No.5, pp.909-913(1996).
[6] B. Mukherjee, Optical Communication Networks, McGraw-Hill Book Company, New York, pp.23-89(1997).
[7] I. Chlamtac, A. Ganz and G. Karmi, “Lightpath Communication: An Approach to High-Bandwidth Optical WANs,” IEEE Trans. on Commun., Vol.40, No.7, pp.171-1182(1992).
[8] T. E. Sten and K. Bala, Multiwavelength Optical Networks, Addison-Wesley Longman Inc., Massachusetts, pp.2-8(1999).
[9] L. H. Sahasrabuddhe and B. Mukherjee, “Light-Trees: Optical Multicasting for Improved Performance in Wavelength-Routed Networks,” IEEE Commun. Mag., pp.67-73(1999).
[10] R. A. Barry and P. A. Humblet, “Models of Blocking Probability in All-Optical Network With and Without Wavelength Changers,” IEEE J. Select. Areas in Commun., Vol.14, No.5, pp.858-866(1996).
[11] C. K. Miller, Multicast Networking and Applications, Addison-Wesley Longman Inc., Massachusetts, pp.76-90(1998).
[12] A. Girard, Routing and Dimensioning in Circuit-Switched Networks, Addison-Wesley Longman Inc., Massachusetts, (1990).
[13] J. Kuri, N. Puech and M. Gagnaire, “Routing and Wavelength Assignment of Scheduled Lightpath Demands,” IEEE J. Select. Areas in Commun., Vol.21, No.8, pp.1231-1240(2003).
[14] R. Malli, X.Zhang and C. Qiao, “Benefits of Multicasting in All-Optical Networks,” in Proc. SPIE Conf. All-Optical Networking, (1998).
[15] M. Ali and J. S. Deogun, “Cost-effective Implementation of Multicast in Wavelength-Routed Networks,” IEEE/OSA J. of Lightwave Technol., Vo.18, No.12, pp.1628-1638(2000).
[16] R. Ramamurthy and B. Mukherjee, “Fixed-Alternate Routing and Wavelength Conversion in Wavelength-Routed Optical Networks,” IEEE/ACM Trans. on Networking, Vol.10, No.3, pp.351-367(2002).
[17] G. Sahin and M. Azizoglu, “Multicast Routing and Wavelength Assignment in Wide Area Networks,” in Proc. SPIE Conf. All-Optical Networking, (1998).
[18] B. Chen and J. Wang, “Efficient Routing and Wavelength Assignment for Multicast in WDM Networks,” IEEE J. Select. Areas in Commun., Vol.20, No.1, pp.97-108(2002).
[19] G. Mohan and C. S. R. Murthy, “Efficient Wavelength Rerouting in WDM Single-Fiber and Multi-Fiber Networks with and without Wavelength Conversion,” J. of High Speed Networks, Vo.8, pp.149-171(1999).
[20] R. Wittmann and M. Zitterbart, Multicast Communication, Morgan Kaufmann Publisher, San Francisco, pp.34-46(2001).
[21] D. Bertsekas and R. Gallager, Data Networks, Prentice Hall, New Jersey, (1992).
[22] C. Diot, W. Dabbous and J. Crowcroft, “Multipoint Communication: A Survey of Protocols, Functions, and Mechanisms” IEEE J. Select. Areas in Commun., Vol.15, No.3, pp.277-290(1997).
[23] H. F. Salama, D. S. Reeves and Y. Viniotis, “Evaluation of Multicast Routing Algorithm for Real-time Communication on High-speed Networks,” IEEE J. Select. Areas in Commun., Vol.15, No.3, pp.332-345(1997).
[24] S. Y. Shi and J. S. Turner, “Multicast Routing and Bandwidth Dimensioning in Overlay Networks,” IEEE J. Select. Areas in Commun., Vol.20, No.8, pp.1444-1555(2002).
[25] R. C. Chalmers and K. C. Almeroth, “On the Topology of Multicast Trees,” IEEE/ACM Trans. on Networking, Vol.11, No.1, pp.153-165(2003).
[26] P. Winter, “Multicast Communication: Present and Future,” IEICE Trans. On Commun., Vol.E86-B, No. 6, pp.1754-1767(2003).
[27] C. A. Noronha and F. A. Tobagi, “Optimum Routing of Multicast Streams,” in Proc. IEEE INFOCOM’94, (1994).
[28] E. Aharoni and R. Cohen, “Restricted Dynamic Steiner Trees for Scalable Multicast in Datagram Network,” IEEE/ACM Trans. on Networking, Vol.3, pp.286-297(1998).
[29] P. Winter, “Steiner Problem in Networks: A Survey,” IEEE Networks, Vol.17, No.2, pp.129-167(1987).
[30] T. Billhartz, J. B. Cain, E. Farrey-Goudreau, D. Feig and S. G. Batsell, “Performance and Resource Cost Comparisons for the CBT and PIM Multicast Routing Protocols,” IEEE J. Select. Areas in Commun., Vol.15, No.3, pp.304-314(1997).
[31] S. Deering, C. Partridge and D. Waitzman, “Distance Vector Multicast Routing Protocol,” RFC 1075, 1988.
[32] T. H. Cormen, C. E. Leiserson, and R. Rivest, Introduction to Algorithms, McGraw-Hill Book Company, New York, pp.498-504(1996).
[33] A. Thyagarajan and S. Deering, “Hierarchical Distance Vector Multicast Routing for The Mbone,” ACM SIGCOMM’95, Cambridge, (1995).
[34] J. Moy, “OSPF Version 2,” Internet RFC 1247, pp.189-195,(1991).
[35] L. H. Sahasrabuddhe and B. Mukherjee, “Multicast Routing Algorithms and Protocols: A Tutorial,” IEEE Network, pp.90-102,(2000).
[36] D. Clark and D. Tennenhouse, “Architectural Considerations for A New Generation of Protocols,” ACM SIGCOMM’90, (1990).
[37] T. Turletti and J. C. Bolot, “Issues with Multicast Video Distribution in Heterogeneous Packet Networks,” in Proc. 6th Int. Workshop on Packet Video, Portland, (1994).
[38] J. C. Bolot and A. V. Garcia, “Control Mechanisms for Packet Audio in the Internet,” in Proc. IEEE INFOCOM’96, San Francisco, CA, (1996).
[39] R. Clark and M. H. Ammar, “Providing Scalable Web Services Using Multicast,” in Proc. 2th Workshop on Service in Distributed and Networked Environments, Canada, (1995).
[40] R. M. Krishnaswamy and K. N. Sivarajan, “Design of Logical Topologies: A Linear Formulation for Wavelength-Routed Optical Networks with No Wavelength Changers,” IEEE/ACM Trans. on Networking, Vol.9, No.2, pp.186-198(2001).
[41] D. Banerjee and B. Mukherjee, “Wavelength-Routed Optical Networks: Liner Formulation, Resource Budgeting Tradeoffs, and a Reconfiguration Study,” IEEE/ACM Trans. on Networking, Vol.8, No.5, pp.598-607(2000).
[42] S. Subramaniam, M. Azizoglu and A. K. Somani, “All-optical Network with Sparse Wavelength Conversion,” IEEE/ACM Trans. on Networking, Vol.4, pp.544-557 (1996).
[43] X. Chu, B. Li and I. Chlamtac, “Wavelength Converter Placement Under Different RWA Algorithms in Wavelength-routed All-optical Networks,” IEEE Trans. on Commun., Vol.51, No.4, pp.607-617(2003).
[44] K. C. Lee and V. O. K. Li, “A Wavelength Convertible Optical Networks,” IEEE/OSA J. of Lightwave Technol., Vol.11, pp.962-970(1993).
[45] G. Jeong and E. Ayanoglu, “Comparsion of Wavelength-interchanging and Wavelength-selective Cross-connects in Wavelength All-optical Networks” in Proc. IEEE INFOCOM’96, San Francisco, CA,(1996).
[46] F. Forghieri, R. W. Tkach, A. R. Chraplyvy and D. Marcuse, “Reduction of Four-wave Mixing Crosstalk in WDM system Using Unequally Spaced Channels,” IEEE Photo. Technol. Letters, Vol.6, No.6, pp.754-756(1994).
[47] Birman and A. Kershenbaum, “Routing and Wavelength Assignment Methods in Single-hop All-optical Networks with Blocking,” in Proc. INFOCOM’95, Boston, MA, (1995).
[48] H. Harai, M. Murata and H. Miyahara, “Performance of Alternate Routing Methods in All-optical Switching Networks,” in Proc. INFOCOM’95, Tokyo, Japan, (1997).
[49] L. Li and A. K. Somani, “A New Analytical Model for Multifiber WDM Networks” IEEE Trans. on Commun., Vol.18, No.10, pp.2138-2145(2000).
[50] I. Chlamtac, A. Ganz and G. Karmi, “Purely Optical Network for Terabit Communication,” in Proc. IEEE INFOCOM’89, Ottawa, Canada, (1989).
[51] T. E. Stern, K. Bala, S. Jiang and J. Sharony, “Liner Lightwave Networks: Performance Issues,” IEEE/OSA J. of Lightwave Technol., Vol.11, pp.937-950(1993).
[52] C. A. Noronha and F. A. Tobagi, “Routing of Multimedia Streams in Reconfigurable WDM Optical Networks,” J. of High Speed Networks, Vo.4, pp.133-153(1995).
[53] R. Ramaswami and K. N. Sivarajan, “Optimal Routing and Wavelength Assignment in All-optical Networks,” IEEE/ACM Trans. on Networking, Vol.3, No.5, pp.489-500(1995).
[54] K. M. Chan and T. S. Yum, “Analysis of Least Congested Path Routing in WDM Lightwave Networks,” in Proc. IEEE INFOCOM’94, Toronto, Canada, (1994).
[55] C. Chen and S. Banerjee, “Optical Switch Configuration and Lightpath Assignment in Wavelength Routing Multihop Lightwave Networks,” in Proc. IEEE INFOCOM’95, Boston, (1995).
[56] X. Zhang, J. Wei and C. Qiao, “Constrained Multicast Routing in WDM Networks with Sparse Light Splittung,” in Proc. IEEE INFOCOM’00, pp.1781-1790,(2000).
[57] M. Frey, and T. Ndousse, "Wavelength Conversion and Call Connection Probability in WDM Networks," IEEE Trans. on Commun., Vol.49, No.10, pp.1780-1787(2001).
[58] R. Ramaswami and K. Sivarajan, “Design of Logical Topologies for Wavelength-routed Optical Networks,” in Proc. IEEE INFOCOM’95, Boston, MA, (1995).
[59] M. Kovacevic and A. S. Acampora, “Benefits of Wavelength Translation in All-optical Clear-channel Networks,” IEEE J. Select. Areas in Commun., Vol.14, No.5, pp.868-880(1996).
[60] A. Binman, “Computing Approximate Blocking Probabilities for A Class of All-optical Networks,” IEEE J. Select. Areas in Commun., Vol.14, No.5, pp.852-857(1996).
[61] G. Jeong and E. Ayanoglu, “Comparison of Wavelength-interchanging and Wavelength-selective Cross-connects in Multiwavelength All-optical Networks,” in Proc. IEEE INFOCOM’96, San Francisco, CA, (1996).
[62] J. Yates, J. Lacey, D. Everitt and M. Summerfield, “Limited-range Wavelength Translation in All-optical Networks,” in Proc. IEEE INFOCOM’96, San Francisco, CA, (1996).
[63] F. K. Hwang and A. Jajszczyk, “On Nonblocking Multiconnection Networks," IEEE Trans. on Commun., Vol. 34, pp.1038-1041(1986).
[64] Y. Yang, "A Class of Interconnection Networks for Multicasting" IEEE Trans. on Commun., Vol. 47, No. 8, pp.899-906(1998).
[65] Y. Yang and J. Wang, "On blocking Probability of Multicast Networks," IEEE Trans. on Commun., Vol. 46, No. 7, pp.957-968(1998).
[66] M. Ali "Optimization of Splitting Node Placement in Wavelength-routed Optical Networks" IEEE J. Select. Areas in Commun., Vol. 20, No.8, pp.1571-1579 (2002).
[67] X. Qin and Y. Yang, "Multicast Connection Capacity of WDM Switching Network with Limited Wavelength Conversion," IEEE/ACM Trans. on Networking, Vol.12, No.3, pp.526-538(2004).
[68] Y. Yang, J. Wang and Chunming Qiao, "Nonblocking WDM Multicast Switching Network," IEEE Trans. on Parallel and Distributed System, Vol. 11, No. 12, pp.1274-1287(2000).
[69] 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 (1998).
[70] J. Kuri, N. Puech and M. Gagnaire, “Routing and Wavelength Assignment of Scheduled Lightpath Demands” IEEE J. Select. Areas in Commun., Vol.48, No.8 pp.1571-1579(2000).
[71] W. Liang, and X. Xhen, "Improve Lightpath routing in Large WDM Networks," IEEE Trans. on Commun., Vol.49, No.10, pp.1780-1787(2001).
[72] K. C. Lee and V. O. K. Li, “A Wavelength Rerouting Algorithm in Wide-Area All-Optical Networks” J. of Lightwave Technol., Vo.14, No.6, pp.1218-1229 (1996).