臺灣博碩士論文加值系統

中文摘要

分波多工（Wavelength Division Multiplexing , WDM）的技術讓光纖網路可以提供極大的頻寬以及資料

的穩定性，使用者因此能夠在極短的時間內傳送大量的資料，解決現在網路頻寬的不足。然而，隨著多媒

體發展以及視訊會議的普及，點對多點的傳輸方式變成很重要，因此，我們將探討在WDM光學網路上進行

群播（multicast）時，若僅有某些節點具有分光複製能力時 （sparse light splitting），光樹

（light-tree）如何建構的問題。A.Zsigri 【1】 等人提出了S3P演算法來建構光樹，雖然節省了許多的

波段（wavelength channel），但會產生極大的傳輸延遲，因此我們提出了一個新的演算法SPTR

（Shortest Path Based Forest with Tree-Reconnecting algorithm）來改進S3P，適當的減少過大的傳

輸延遲，使得整體效能更好。

關鍵字：分波多工（Wavelength Division Multiplexing；WDM），群播（multicast），稀疏分光複製能

力（sparse light splitting），波道（wavelength channel）

ABSTRACT

Optical Networks based on Wavelength Division Multiplexing （WDM）are the most promising

candidates for the next generation backbone networks. It offers a large bandwidth and

stability. Moreover, since multicast applications become increasingly popular, supporting

multicast at the WDM layer becomes an important topic. In this thesis, the construction of

light-trees for multicast communication in WDM networks with spare light splitting is

studied. A. Zsigri et al【1】proposed the S3P algorithm to solve this problem. Although some

wavelengths are saved in this algorithm, it often generates a large source-destination

delay. Therefore, we will propose a new algorithm SPTR to improve the S3P algorithm.

Key words：Wavelength Division Multiplexing, multicast, sparse light splitting, wavelength

channel.

目錄

封面內頁
簽名頁
授權書 iii
中文摘要 iv
英文摘要 v
誌謝 vi
目錄 vii
圖目錄 ix

第一章　序論
1.1 前言 1
1.2 WDM網路簡介 3
1.3 光樹建構的問題 10
第二章　相關文獻
2.1 Member-only等四種演算法 13
2.2 AOMH演算法 15
2.3 Virtual-Source和Tabu演算法 16
2.4 S3P演算法 17
第三章 研究方法以及演算法
3.1 S3P（SP+PP）演算法的討論 19
3.2 SPTR演算法 22
第四章 模擬與結果
4.1 模擬環境 26
4.2 模擬結果 26
第五章 結論 36
參考文獻 37

參考文獻

[1]A. Zsigri, A. Guitton, and M. Molnár, “Construction of light-trees for WDM

multicasting under splitting capability constraints,” The 10th International Conference on

Telecommunications, vol. 1, pp. 171.175, 2003.
[2]P. R. Trischitta and W. C. Marra “Applying WDM technology to undersea cable

networks,” IEEE Communication Magazine, PP. 62-66, 1998.
[3]Uyless Black, “Optical networks: Third generation transport systems,” 2002, ISBN:

0130607266.
[4]C. Diot, W. Dabbous, J. Corwroft, “Multipoint communication: A survey of protocols,

functions, and mechanisms, ” IEEE Journal of Selected Areas in Communications, vol. 15,

Issue: 3, April 1997.
[5]D. Waitzman, C. Partridge, and S. Deering（editors）, “Distance vector multicast

routing protocol,” RFC 1075, BBN STC and Stanford University, November 1998.
[6]J. Moy, “MOSPF: Analysis and experience,” RFC 1585, March 1994.
[7]D. Estrin, D. Farinacci, et al., “Protocol independent multicast- sparse mode（PIM

-SM）: protocol specification,” RFC 2362, June 1998.
[8]A. Ballardie, “Core based tree（CBT version 2）multicast routing,” RFC 2189,

September 1997.
[9]I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high

bandwidth optical WAN’s,” IEEE Transactions on Communication, Vol. 40, page（s）:

1171.1182, July 1992.
[10]Kuo-Chun Lee, Victor O. k. li, Fellow, “A Wavelength- Convertible Optical Network,

” IEEE Journal of lightwave technology, Vol. 11, page（s）: 962-970, May 1993.
[11]L. H. Sahasrabuddhe and B. Mukhejee, “Light-trees: Optical multicasting for

improved performance in wavelength routed networks,” IEEE Communication Magazine, page（s）

: 67-73 February 1999.
[12]X. Zhang, J. Y. Wei, and C. Qiao, “Constrained multicast routing in WDM networks

with sparse light splitting,” Journal of Lightwave Technology, vol. 18, No. 12, pp. 1917-

1927, 2000.
[13]N. Sreenath, N. K. M. Reddy, G. Mohan, and C. S. R. Murthy, “Virtual source based

multicast routing in WDM networks with sparse light splitting,” IEEE Workshop on High

Performance Switching and Routing, pp.141.145, 2001.
[14]C. -Y. Hsieh and W. Liao, “All optical multicasting routing in sparse-splitting

optical networks,” in Proceedings of the 28th Annual IEEE International Conference on Local

Computer Networks, pp. 162.167, 2003.
[15]F. K. Hwang, Dana, S. Richards, “Steiner tree problem,” Networks, Vol. 22, PP 55-

89, 1992.
[16]M. Garey and D. Jphnson, “A Guide to the theory of NP-completeness,” Computers and

Intractability. Freeman, New York, 1979.
[17]A. Maher, Jitender, S. Deogun, “Cost-Effective implementation of multicasting in

wavelength-routed network,” IEEE Journal of Lightwave Technology, Vol. 18, No. 12, December

2000.
[18]E. W. Dijkstra, “A note on two problems in connection with graph,” Numerical

Mathematics, October 1959.
[19]Wen-Yu Tseng, Sy-Yen Kuo, “All-Optical multicasting on wavelength-routed WDM

networks with partial replication,” 15TH International Networking, Jan. 31-Feb. 2, 2001.
[20]S. Yan, S. Deogun, M. Ali, “Routing in sparse splitting optical networks with

multicast traffic,” Computer Network, Elsevier Science, Vol. 40, No 1, page（s）89-114,

January 2003.
[21]S. Yan, M. Ali, J. Deogun, “Route optimization of multicast sessions in spare light

splitting optical networks,” IEEE Global Telecommunications Conference, Vol.4, pp. 25-29,

2001.
[22]Georgia Tech Internetwork Topology Model. GT-ITM. 【Online】.Available

:http://www.cc.gatech.edu/projects/gt-itm/
[23]M. Doar and I. Leslie, “How bad is naïve multicast routing,” INFOCOM, page 82-89,

1993.