跳到主要內容

臺灣博碩士論文加值系統

(35.172.136.29) 您好!臺灣時間:2021/07/29 08:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳科位
研究生(外文):Ke-Wei Chen
論文名稱:WDM網路上以最小化ADMs數目為目標的邏輯環狀結構設計
論文名稱(外文):Design of Logical Survivable Rings to Minimize the Number of ADMs in Multi-hop WDM Networks
指導教授:林華君
指導教授(外文):Hwa-Chun Lin
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:67
中文關鍵詞:WDM環狀結構存活能力ADMs
外文關鍵詞:WDMSurvivableRingADMs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:88
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
在這篇文章中,我們研究了如何利用Survivable Rings來確保WDM網路上存活能力。若有數條光徑形成環狀結構,則當環狀結構上的某條光徑無法傳送資料時,可以藉由環狀結構上的其他光徑來繼續傳送資料,所以說環狀結構上的光徑都具有存活能力,而為了使得每條光徑都具有存活能力,所有的光徑都必須是某個環狀結構的一部分,若是無法形成完整的環狀結構,則增加額外的光徑來形成完整的環狀結構,而這方面研究的成本考量,是希望使用較少的額外光徑,同樣也代表著希望使用較少的電子終端設備,在一般的實體拓樸上(general topology),有[5,6]兩篇論文著手於研究這類的問題,而這類的問題的最佳化已經被證明是NP-Hard,所以他們各自提出近似演算法(approximation algorithm),用Maximum Matching來規劃環狀結構,使得光徑盡量共用電子終端設備,但是Maximum Matching會拆散完整的環狀結構,所以[6]提出先使用preprocessing的步驟找出較小的環狀結構,而後再利用Maximum Matching,以避免將完整的環狀結構拆散,[5,6]兩篇中的近似演算法可分別得到確保小於1.6倍最佳解與小於(1.5+ε)倍最佳解的結果。
我們觀察到目前提出的近似演算法PIM[6]仍然存在著兩個可以改善的地方,第一個是因為每個iteration利用Maximum Matching,以光徑共用最多的電子終端設備的觀點為考量,卻沒有考慮到光徑共用電子終端設備後,所形成的環狀結構是否會使用較少的額外光徑,且有可能將較佳的光徑組合拆散,雖然光徑在每個iteration共用最多的電子終端設備,但是卻不一定會使得最後共用的電子終端設備最多,也就不一定會使得所需的額外光徑數目較少,第二個是因為preprocessing的步驟中是找出較小的環狀結構,卻不是找出可以符合目標,也就是使得所需的額外光徑數目較少的環狀結構,所以我們的動機是要改善上面所提及的兩點,尋找解決問題的方法。這篇論文主要的貢獻有兩個,第一個貢獻是我們跳脫Maximum Matching的做法,提出新的想法與方法,來解決這一類的問題,並且在選擇環狀結構時,放棄選擇較小的環狀結構,改以兩個Greedy演算法選擇較適當的環狀結構讓所需的額外光徑數目較小,與PIM[6]相比,最少可以減少12.36%的額外光徑數目,最多可以減少16.01 %的額外光徑數目,的確可以節省所需額外光徑數目。第二個貢獻是我們發現光徑的路徑也會影響結果,若是利用有效的光徑(lightpath)繞徑方式,使得所有光徑的路徑盡量平均分散在網路上,若是路徑不重疊就可以共用電子終端設備,使得可以共用電子終端設備的機會增加,並且使用較少的額外光徑形成具有存活能力的環狀結構,以節省成本,可以發現有效的光徑繞徑方式對於PIM[6]與我們的方法都有幫助,而我們方法與PIM[6]相比,最少可以減少16.45%的額外光徑數目,最多可以減少27.43 %的額外光徑數目,也的確可以節省所需額外光徑數目。若是當實體拓樸上的平均每個節點的degree越大時,鏈結數目越多,也可以使得所有光徑盡量平均分散在網路上,也可以減少所需的額外光徑數目。
目 錄
1.概述....................................................1
1.1.光分波長多工網路上的存活能力(Survivability)與恢復機制........................................................5
1.2.WDM網路上相關的存活能力研究...........................7
1.3.要解決的問題與目前提出的方法.........................14
1.4.研究動機與貢獻.......................................20
2.將問題定義與問題難易度.................................25
3.提出的Greedy演算法.....................................29
3.1.判斷所需額外光徑程序(Additional_Lightpath_Procedure).29
3.2.尋找初始集合程序(Initial_Set_Finding_Procedure). ....31
3.3.簡單的Greedy演算法(Simple Greedy Algorithm)..........39
3.4.增進的Greedy演算法(Enhanced Greedy Algorithm)........43
4.演算法效能模擬與結果...................................52
5.結論...................................................64
參考文獻.................................................65
[1] B. Mukherjee, ”WDM-based local lightwave networks. I. Single-Hop Systems,” IEEE Network, vol. 6, no. 3, pp. 12-27, May 1992.
[2] B. Mukherjee, ”WDM-based local lightwave networks. II. Multihop Systems,” IEEE Network, vol. 6, no. 4, pp. 20-32, May 1992.
[3] S. Ramamuthy and B. Mukherjee, “Survivable WDM Mesh Networks: Part I—Protection,” Proc., IEEE INFOCOM’99, New York, Mar. 1999, pp.744-751.
[4] S. Ramamuthy and B. Mukherjee, “Survivable WDM Mesh Networks: Part II—Restoration,” Proc., ICC’99, Vancouver, CA, June 1999, pp.2023-2030.
[5] T. Eilam, S. Moran and S. Zaks, “Lightpath Arrangement in Survivable Rings to Minimize the Switching Cost,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 1, pp.172 – 182, Jan. 2002.
[6] G. Calinescu, O. Frieder, and P. J. Wan, “Minimizing Electronic Line Terminals for Automatic Ring Protection in General WDM Optical Networks,” IEEE Journal on Selected Areas in Communications, vol. 20 , no. 1, pp.183 – 189, Jan. 2002.
[7] O. Crochat and J.-Y. Le Boudec, “Design Protection for WDM Optical Networks,” IEEE Journal on Selected Areas in Communications, vol. 16, no. 7, pp. 1158-1165, Sep. 1998.
[8] Y. Wang, L. Li and S. Wang, “A New Algorithm of Design Protection for Wavelength-Routed Networks and Efficient Wavelength Converter Placement,” Proc., ICC’01, vol. 6, 11-14 June 2001, pp.1807-1811.
[9] A. Nucci, B. Sanso, T. G. Crainic, E. Leonardi, and M. A. Marsan, “Design of Fault-Tolerant Logical Topologies in Wavelength-Routed Optical IP Networks,” Proc., IEEE GLOBECOM '01, vol. 4, 25-29 Nov. 2001, pp.2098-2103.
[10] E. Modiano and A. Narula-Tam, “Survivable Lightpath Routing: A New Approach to the Design of WDM-Based Networks,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 4, pp.800-809, May 2002.
[11] A. Sen, B. Hao, B. H. Shen and G. Lin, ”Survivable Routing in WDM Networks-Logical Ring in Arbitrary Physical Topolopy,” Proc, ICC’01, vol. 5, 28 April-2 ,May 2002, pp. 2771 – 2775.
[12] A. Fumagalli, I. Cerutti and M. Tacca, “Optimal design of survivable mesh networks based on line switched WDM self-healing rings,” IEEE/ACM Transactions on Networking, vol. 11, no. 3, pp.501-512, June 2003
[13] M. Medard, R. A. Barry, S. G. Finn, He Wenbo and S. S. Lumetta, “Generalized Loop-Back Recovery in Optical Mesh Networks,” IEEE/ACM Transactions on Networking, vol. 10, no. 1 , pp. 153-164, Feb. 2002.
[14] G. Ellinas, A. G. Hailemariam, and T.E. Stern, “Protection Cycles in Mesh WDM Networks,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, pp. 1924-1937, Oct. 2000.
[15] D. Stamatelakis, and W. D. Grover, “IP Layer Restoration and Network Planning Based on Virtual Protection Cycles,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, pp. 1938-1949, Oct. 2000.
[16] D. A. Schupke, C. G. Grube and A. Autenrieth, “A Optimal Configuration of p-Cycles in WDM Networks,” Proc., ICC’2002, vol. 5, 28 April-2 May 2002, pp. 2761-2765.
[17] X. Guoliang, C. Li and K. Thulasiraman, “Quality-of-Service and Quality-of-Protection Issues in Preplanned Recovery Schemes Using Redundant Trees,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 8, pp. 1332-1345, Oct. 2003.
[18] M. Medard, S. G. Finn, R. A. Barry and R. G. Gallager, “Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant or Edge-Redundant Graphs,” IEEE/ACM Transactions on Networking, vol. 7, no. 5, pp.641-652, Oct. 1999.
[19] J. Shi and J. Fonseka, “Hierarchical self-healing rings,” IEEE/ACM Transactions on Networking, vol. 3, no. 6, pp. 690-697, Dec. 1995.
[20] J. Shi and J. Fonseka, “Interconnection of self-healing rings,” Proc., ICC’96,vol. 3, June 1996, pp. 1563-1567.
[21] L.Wuttisittikulkij and M. O’Mahony, “Design of WDM network using a multiple ring approach,” Proc.,IEEE GLOBECOM’97, vol. 1, Nov. 1997, pp. 551-555.
[22] C. Xin, Y. Ye, S. Dixit and C. Qiao, ”A Joint Working and Protection Path Selection Approach in WDM Optical Networks,” Proc.,IEEE GLOBECOM’01, vol. 4, 25-29 Nov. 2001, pp.2165-2168.
[23] A. Fumagalli, M. Tacca, F. Unghvary and A. Farago, “Shared Path Protection With Differentiated Reliability,” Proc., ICC’02, vol. 4, 28 April-2 May 2002, pp.2157-2161.
[24] Canhui Ou, Jing Zhang, Hui Zang, L. H. Sahasrabuddhe and B. Mukherjee, Near-Optimal Approaches for Shared-Path Protection in WDM Mesh Networks,” Proc., ICC '03, vol. 2, 11-15 May 2003, pp.1320-1324.
[25] C. Assi, Y. Ye, A. Shami, S. Dixit and M. Ali, “Efficient Path Selection and Fast Restoration Algorithms for Shared Restorable Optical Networks,” Proc., ICC’03, vol. 2, 11-15 May 2003, pp.1412-1416.
[26] L. Liu, X. Li, P.-J. Wan and O. Frieder, “Wavelength Assignment in WDM Rings to Minimize SONET ADMs,” Proc., IEEE INFOCOM’00, vol. 2, 26-30 March 2000, pp.1020-1025.
[27] X. Yuan and A. Fulay, “Wavelength Assignment to Minimize the Number of SONET ADMs in WDM Rings,” Proc., ICC’02, vol. 5, 28 April-2 May 2002, pp.2917-2921.
[28] R. Berry and E. Modiano, “Reducing Electronic Multiplexing Costs in SONET/WDM Rings with Dynamically Changing Traffic,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, pp.1961-1971, Oct. 2000.
[29] O. Gerstel, R. Ramaswami and G. H. Sasaki, “Cost-Effective Traffic Grooming in WDM Rings,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp.618-630, Oct. 2000
[30] O. Gerstek, P. Lin and G. Sasaki, “Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings,” Proc., IEEE INFOCOM’98, vol. 1, pp.94-101.
[31] C. A. Brackett, “Dense wavelength division multiplexing networks: Principles and applications,” IEEE Journal on Selected Areas in Communications, vol. 8, pp.948–946, Aug. 1990.
[32] P. R. Trischitta and W. C. Marra, “Applying WDM technology to undersea cable networks,” IEEE Commun. Mag., pp. 62–66, Feb. 1998.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top