臺灣博碩士論文加值系統

隨著多媒體及網際網路應用之快速發展，網路頻寬之需求日益加大。分波多工能提供Gb/s甚至Tb/s之大量頻寬，使之成為未來骨幹網路之最佳選擇。也由於其所攜帶之大量頻寬，單一之光纜斷裂便可能造成大量的資料流失。這使得具存活力之網路設計成為一項很重要的設計議題。在最近的研究中，Su提出「桶狀鏈路表示法」及相對之保護路由演算法。其具有簡單及適用於分散式系統之優點。但在這個演算法中，工作路徑為固定式，使之成為最少備用資源問題之區域最佳解。
在本論文中，我們藉由動態之工作路徑選擇於單一鏈路錯誤之條件下提兩個動態保護路由演算法：DWPRA及CDWPRA演算法。模擬結果顯示動態工作路由演算法能有效降低所需之備用資源。另一方面，我們也發現備用資源之分享能力與通量數及網路搶樸之平均節點分枝度有關。通量數越大、平均之節點分枝度越高，其備用資源之分享能力越好。

With emerging multimedia and Internet applications, it is continuously thirsty for more network capacity. Wavelength-division multiplexing(WDM) networks, which provide the communication bandwidth at order of gigabits or terabits per seconds, had been the candidate of future backbone networks. With the large bandwidth, single fiber cut will induce huge data loss. It makes survivability became a critical issues. In recent research, Su had proposed a bucket-based link metrics and corresponding algorithm. It is simple and suited for distributed system. But in this approach, the working path is fixed. It is implemented as a local optimal solution of minimum spare capacity problem.

In this thesis, we propose two dynamic protection routing algorithm DWPRA and CDWPRA by choosing the working path dynamically where only single link failure is considered. And the simulation results show that the dynamic working path approach can reduce backup resources more efficiently. We also find the sharing capability is associated with the number of demands and the node degree of the network topology. More demands or higher node degree, the more sharing capability will be.

中文摘要……………………………………………………………………i
英文摘要……………………………………………………………………ii
誌謝…………………………………………………………………………iii
目錄…………………………………………………………………………iv
圖目錄………………………………………………………………………vi
表目錄………………………………………………………………………viii
壹、緒論……………………………………………………………………1
一、前言………………………………………………………………1
二、分波多工網路……………………………………………………2
三、具存活力之網路架構……………………………………………7
四、錯誤回復機制……………………………………………………10
(一) 點對點系統之錯誤回復機制………………………………10
(二) 環狀網路之錯誤回復機制…………………………………15
(三) 網狀網路之錯誤回復機制…………………………………17
五、研究現況與研究動機……………………………………………22
(一) 研究現況……………………………………………………22
(二) 研究動機……………………………………………………23
貳、動態之鏈結基礎保護路由演算法……………………………………24
一、問題描述…………………………………………………………24
(一) 靜態保護路由規劃…………………………………………24
(二) 動態保護路由規劃…………………………………………27
二、桶狀保護鏈結表示法……………………………………………30
三、動態保護路由演算法……………………………………………33
參、模擬及效能評估………………………………………………………41
一、模擬環境…………………………………………………………41
二、效能分析…………………………………………………………43
(一) 波長資源數…………………………………………………43
(二) 備用比與保護負擔…………………………………………44
(三) 錯誤回復速度………………………………………………45
(四) 演算法複雜度………………………………………………45
肆、結論……………………………………………………………………58
參考文獻……………………………………………………………………60
附錄…………………………………………………………………………64

[1] E. Karasan and E. Ayanoglu, “Performance of WDM Transport Networks”, IEEE JSAC, Vol. 16, No. 7, pp. 1081-1096, Sep. 1998.[2] A. Jourdan et al., “Key Building Blocks for High-Capacity WDM Photonic Transport Networks”, IEEE JSAC, Vol. 16, No. 7, pp. 1286-1297, Sep. 1998.[3] T. D. Wu, "Emerginh Technologies for Fiber Network Survivability", IEEE Commun. Mag., pp. 58-74, Feb 1995.[5] Y. Miyao and H. Saito, “Optimal Design and Evaluation of Survivable WDM Transport Networks”, IEEE JSAC, Vol. 16, No. 7, pp. 1190-1198, SEP. 1998.[5] O. Gerstel, and R. Ramaswami, “Oprical Layer Survivability ─ An Implementation Perspective”, IEEE JSAC, Vol. 18, No. 10, pp. 1885-1899, Oct 2000. [6] G. Mohan and C. Murthy, “Lightpath Restoration in WDM Optical networks”, IEEE Network, pp. 24-32, Nov/Dec 2000.[7] O. Gerstel and R. Ramaswami, "Optical Layer Survivability: A Services perspective", IEEE Commun. Mag., pp. 104-113, Mar. 2000.[8] D. Zhou and S. Subramaniam, “Survivability in Optical networks”, IEEE Network, pp. 16-23, Nov/Dec 2000.[9] R. Ramaswami, and K. Sivarajan, “Optical Network A Practical Perspective”, Morgan Kaufmann Publishers 1998.[10] Thomas E. Stern and Kirshna Bala, “Multiwavelength Optical Networks A Layered Approach”, Addison Wesley Publishers 1999.[11] M. Medard, S. Finn, R. Barry, and R. Gallager, “Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant Graphs”, IEEE/ACM Trans. Networking, Vol. 7, No. 5, pp. 641-652, Oct 1999.[12] C. Sue, S. Kuo and Y. Huang, “Fault Tolerant Crossconnect and Wavelength Routing in All-Optical Networks”, ICICE Trans. on Communication, Vol. E83-B, No. 10, pp. 2278-2293, Oct 2000.[13] Bell Communication Research, “SONET Dual-Fed Unidirectional Path-Switched Ring (UPSR) Equipment Generic Criteria”, Technical Report No. GR-1400-CORE, Mar. 1994. (1:1 SONET)[14] P. Bonenfant and C. Davenport, “SONET optical layer protection switching”, Bell Communications Research, Technical Report No. TM-24609, Dec. 1994. (1:1 optical)[15] S. Ramamurthy and B. Mukherjee, “Survivable WDM Mesh Networks, Part I — Protection” in Proc., IEEE INFOCOM’99, pp. 744-751, March 1999. [16] B. Caenegem, W. Parys, F. Turck and P. Demeester “Dimensioning of Survivable WDM Networks”, IEEE JSAC, Vol. 16, No. 7, SEP 1998.[17] B. T. Doshi, S. Dravida, P. Harshavardhana, O. Hauser, and Y. Wang,“Optical network design and restoration”, Bell Labs Technical Journal, pp. 58-84, January-March 1999.[18] Y. Ye, S. Dixit and M. Ali, "On Joint Protection/Restoration in IP-Centric DWDM-Based Optical Transport Networks", IEEE Commun. Mag., pp. 174-183, Jun. 2000.[19] O. Gerstel, R. Ramaswami, and G. Sasaki, “Fault Tolerant Multiwavelength Optical Rings with Limited Wavelength Conversion”, IEEE JSAC, Vol. 16, No. 7, pp. 1166-1178, SEP. 1998.[20] O. Crochat, J. Boudec, and O. Gerstel, “Protection Interoperability for WDM Optical Networks”, IEEE/ACM Trans. On Networking, Vol. 8, No. 8, June 2000.[21] L. Wuttisittikulkij, C. Baworntummarat and T. Iamvasant, “A Comparative Study of Mesh and Multi-Ring Designs for Survivable WDM Networks”, ICICE Trans. Commun., Vol. E83-B, No. 10,pp. 2270-2277, Oct. 2000.[22] O.Crochat, and J. Boudec, “Design Protection for WDM Optical Networks”, IEEE JSAC, Vol. 16, No. 7, pp. 1158-1165, SEP. 1998.[23] K. Struyve and P. Demeester, "Dynamic Routing of Protected Optical Paths in Wavelength Routed and Wavelength Translated Networks", IEE ECOC 97, 1997.[24] G. Mohan and C. Murthy, "Routing and Wavelength Assignment for Establishing Dependable Connections in WDM Networks", IEEE Symp.On Fault-Tolerant Computing, 1999.[25] M. Kodialam and T. Lakshman, “Dynamic Routing of Bandwidth Guaranteed Tunnels with Restoration” in proc. IEEE INFOCOM2000, pp. 902-911, 2000.[26] G. Mohan and A. K. Somani, "Routing Dependable Connections With Specified Failure Restoration Guarantees in WDM Networks" in Proc. IEEE INFOCOM 2000, Mar 2000.[27] V. Anand and C. Qiao, "Dynamic Establishment of Protection Paths in WDM Networks, Part I" in Proc. IEEE INFOCOM, 2001.[28] X. Su and C. Su, “An Online Distributed Protection Algorithm in WDM Networks” in proc. IEEE ICC 2001, pp. 1571-1575, 2001.[29] R. Ramamruthy and etc., “Capacity Performance of Dynamic Provisioning in Optical Networks”, IEEE JLT, Vol. 19, No. 1, pp.40-48, January 2001.[30] S. Ramamurthy and B. Mukherjee, “Survivable WDM Mesh Networks, Part II — Restoration” in Proc. IEEE ICC 99, pp. 2023-2030, June 1999.[31] W. Grover, D. Stamatelakis, “Cycle-Oriented Distributed Preconfiguration: Ring-link Speed with Mesh-like Capacity for Self-planning Network Restoration” in Proc. IEEE ICC’98, pp. 537-543, 1998.[32] L. Sahasrabuddhe, and B. Mukherjee, “Light-Trees: Optical Multicasting for Improved Performance in Wavelength-Routed Networks,” IEEE Communication Magazine, pp. 67-73, February 1999.