隨著網路資訊需求日益增加，光纖通訊技術的發展也日新月異，為多樣性的網路服務提供了足夠的頻寬，其中，多波長分波多工光纖網路已經被廣泛研究。在長途骨幹網路以及都會光纖網路中，提供備援容錯，有效率以及差別式服務的功能，已經是刻不容緩的議題。在環狀網路以及網狀網路架構下，許多研究提出了錯誤回復和保護的機制，其中，事先組態保護環(p-cycle)兼顧了環的回復速度以及網狀網路的成本效益，然而，此架構無法應付多重錯誤發生在彼此相依的連結上，在大網路環境中，p-cycle保留的備援頻寬被證實並不符合經濟效益。
作者提出一個有效的錯誤回復架構，使原本的回路回復機制更加完備，這個相似於p-cycle的架構不僅可以節省備援頻寬，同時也減少發生錯誤時的回復時間。在Star-Block演算法中，光纖網路拓樸先被簡化成2-connected的邏輯拓樸，並且根據所提出的演算法，將此邏輯拓樸劃分成數個不同的區塊，每個區塊包含一個中心節點以及包圍此中心節點的環狀節點。在成功分割區塊之後，此邏輯拓樸將被回復為原先的拓樸。取得劃分好的區塊，進一步根據Block Selection演算法來將拓樸中的edge分配給不同的區塊，當有鏈結錯誤發生時，此資料流可以迅速經由所屬區塊中的回復路徑來回復。
經由大量的實驗比較，相較於回路回復機制和p-cycle，我們證實所提出的架構不僅可以達到有效率的備援頻寬的使用，由於回復路徑長度的減少，回復時間也大大縮短，這對於高速傳輸的資料是重要的。
除了提供單一錯誤回復，此架構也提供了多重錯誤回復的功能，並且，在備援頻寬不足的情況下，可以動態達到雙重錯誤回復的目的。此架構也應用在差別式服務的錯誤回復，根據回復路徑的長短，為不同優先等級的服務來提供不同回復時間的服務。
延續Star-Block演算法，我們繼而提出支援差別式服務的復原機制。當WDM網路中發生雙重故障時，我們提出具有優先權適應能力的回復機制，藉由分配適當的備援頻寬容量給兩個不同優先權的工作資料流，來提供差別式復原能力，根據模擬結果，這個機制可以經由動態設定來針對不同優先權的資料流達到預期的復原比例。
另外，我們提出一個根據回復時間的長短來支援多層級差別式回復的演算法，此機制可以讓不同優先權的資料流有不同的回復時間，越高等級的資料可以在越短的時間內回復。模擬結果證明，經過Star-Block演算法分析之後的網路拓樸，可以提供三種優先級別的復原服務。

An efficient fault restoration framework is proposed for accomplishing loopback recovery in optical networks. The proposed framework is based on the p-cycles and island-based protection concepts and therefore achieves both a minimal spare capacity requirement and a rapid restoration time. In the proposed approach, an algorithm designated as Star-Block is used to simplify the original topology to a 2-connected graph and to partition the graph into multiple blocks, where each block contains a center node and the minimum number of neighboring nodes which collectively form a complete cycle. The simplified graph is then restored to the original topology using conventional graph rules. A Block Selection algorithm is then used to assign the edges belonging to multiple blocks to an appropriate block for fault recovery purposes. Within each block, the working flows are restored in real-time via local p-cycles on the on-cycle and chord fibers. The performance of the proposed protection framework is evaluated numerically in terms of the spare capacity to working capacity ratio and the length of the restoration path. It is shown that the framework has a better spare capacity efficiency than existing loopback recovery schemes or the conventional p-cycles approach. In addition, it is shown that the Star-Block decomposition algorithm shortens the average length of the restoration path and therefore reduces the restoration time. Finally, it is shown that the protection scheme not only provides a differentiated recovery service for traffic with different QoS requirements in the event of single-link failures within a single block, but also supports multiple-fault restoration for the case in which multiple single-link failures occur simultaneously. A scheme is proposed for supporting dual-failure priority-aware survivability in WDM networks with two-level classes of working traffic by means of a proportional spare capacity allocation strategy. The proposed scheme not only provides a differentiated recovery capability, but also maximizes the capacity utilization. The simulation results show that the scheme achieves the desired restoration ratio given appropriate settings of the reservation and allocation ratios. A QoS restoration scheme is proposed for supporting multi-priorities delay-aware survivability in WDM networks with three-level classes of working traffic by means of a routing strategy. The proposed scheme provides a time-based differentiated recovery capability under the consideration of maximizing the capacity utilization. Simulation results show that the scheme provides desired recovery functions for differentiated services.

[1] O. Gerstel and R. Ramaswami, “Optical layer survivability-an implementation perspective,” IEEE Journal on Selected Areas in Communications, vol. 18, pp. 1885–1899, Oct. 2000.
[2] J. B. Slevinsky, W. D. Grover, and M. H. MacGregor, “An algorithm for survivable network design employing multiple self-healing rings,” Globecom’93, pp. 1568–1573.
[3] M. Medard, S. G. Finn, and R. A. Barry, “WDM loop-back recovery in mesh networks,” Infocom’99, pp. 752-759.
[4] W. D. Grover and D. Stamatelakis, “Cycle-oriented distributed preconfiguration: Ring-like speed with mesh-like capacity for self-planning network restoration,” ICC’98, pp. 537–543.
[5] 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, pp. 1938–1949, Oct. 2000.
[6] G. Ellinas, A. G. Hailemarian, and T. E. Stern, “Protection Cycles in Mesh WDM Networks,” IEEE Journal on Selected Areas in Communications, vol. 18, pp. 1924–1937, Oct. 2000.
[7] A. Monitzer, A. Jukan, and H. R. van As, “Service-specific recovery of wavelength connections in WDM networks,” OFC´99, pp. 164-166.
[8] A. Jukan and H. R. van As, “Service-specific resource allocation in WDM networks with quality constraints,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, pp. 2051–2061, Oct. 2000.
[9] O. Komolafe and J. Sventek, “Impact of GMPLS Control Message Loss,” IEEE Journal of Lightwave Technology, vol. 26, pp. 2029-2036, Jul. 2008.
[10] T. Ozugur, M. Park, and J. Jue, "Label prioritization in GMPLS-centric all-optical networks," ICC’03, pp. 1283-1287.
[11] A. Tzanakaki, G. Markidis, and K. Katrinis, “Supporting Differentiated Survivability Services in WDM Optical Networks”. ICTON’08, pp. 71-74.
[12] Z. Ding and M. Hamdi, “Clustering techniques for traffic grooming in optical WDM mesh networks,” Globecom’02, pp. 2711–2715.
[13] G. Ellinas, S. Rong, A.Hailemariam, and T. E. Stern, “Protection cycle covers in optical networks with arbitrary mesh topologies,” OFC’00, pp. 213-315.
[14] L. M. Gardner, M. Heydari, J. Shah, I. H. Sudborough, I. G. Tollis, and C. Xia, “Techniques for finding ring covers in survivable networks,” Globecom’94, pp. 1862–1866.
[15] D. Stamatelakis and W. D. Grover, “Theoretical underpinning for the efficiency of restorable networks using preconfigured cycles (p-cycles),” IEEE/ACM Transaction on Communications, vol. 48, no.8, Aug. 2000, pp. 1262-65.
[16] D. A. Schupke, C. G. Gruber, and A. Autenrieth. “Optimal configuration of p-cycles in WDM networks,” ICC’02, pp. 2761- 2765.
[17] J. Doucette, D. He, W. D. Grover, and O. Yang, “Algorithmic approaches for efficient enumeration of candidate p-cycles and capacitated p-cycle network design,” DRCN’03. pp. 212- 220.
[18] H. Drid, B. Cousin, S. Lahoud, and M. Molnar, “Multi-criteria p-cycle network design,” LCN’08, pp. 361-366.
[19] S.G. Finn, M. Médard, and R.A. Barry, “A novel approach to automatic protection switching using trees,” ICC’97, pp. 272–276.
[20] M. Médard, S. G. Finn, R. A. Barry, and R. G. Gallager, “Redundant trees for pre-planned recovery in arbitrary vertex-redundant or edge-redundant graphs,” IEEE/ACM Transaction on Networking, pp. 641–652, 1999.
[21] M. Médard, R. A. Barry, S. G. Finn, W. He, and S. Lumetta, “Generalized loopback recovery in optical mesh networks,” IEEE/ACM Transaction on Networking, pp. 153–164, 2002.
[22] D. Zhemin and M. Hamdi, “On the application of the blocking island paradigm in all-optical networks,” IEEE Transactions on Communications, vol. 51, pp. 1690-1699, 2003.
[23] A. Hailemariam, G. Ellinas, and T. E. Stern, “Localized restoration in mesh optical networks,” OFC’04.
[24] A. Hailemariam, G. Ellinas, and T. E. Stern, “Island-Based Restoration in Mesh Optical Networks”, ECOC’ 03,
[25] K. Paton. “An algorithm for finding a fundamental set of cycles for a graph,” Communications of the ACM, pp. 514–518, 1969.
[26] R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, vol. 1, no. 2, pp. 146–160, 1972.
[27] P. Mateti and N. Deo, “On algorithms for enumerating all circuits of a graph,” SIAM Journal on Computing, vol. 5, no. 1, pp. 90-99, 1976.
[28] A. Fumagalli, M. Tacca, I. Cerutti, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” Infocom’99, vol. 2, pp. 726–733.
[29] O. J. Wasem, “An algorithm for designing rings for survivable fiber networks,” IEEE Transactions on Reliability, vol. 40, no. 4, pp. 428–432, 1991.
[30] J. Bar-Ilan, G. Kortsarz, and D. Peleg, “How to allocate network centers,” Journal of Algorithms, vol. 15, pp. 385–415, 1993.
[31] T. Gonzalez, “Clustering to minimize the maximum inter-cluster distance,” Theoretical Computer Science, vol. 38, pp. 293–306, 1985.
[32] D.B. West, “Introduction to Graph Theory”, Prentice Hall, 1996.
[33] H. Higaki, “Wavelength priority assignment for reconfigurable WDM networks”, WOCN’06.
[34] S. Ramamurthy, Laxman Sahasrabuddhe, and Biswanath Mukherjee, “Survivable WDM Mesh Networks”, IEEE Journal of Lightwave Technology, vol. 21, no. 4, pp. 870-883, 2003.
[35] T. Cicic, A. Kvalbein, A. F. Hansen and S. Gjessing, “Resilient Routing Layers and p-Cycles: Tradeoffs in Network Fault Tolerance,” HPSR’05, pp. 278-282.
[36] P. Cholda, A. Jajszczyk, “Reliability Assessment of Optical p-Cycles”, IEEE/ACM Transactions on Networking, vol. 15, no. 6, 2007, pp. 1579-1592.
[37] C. C. Sue, J. Y. Yeh, ”Utilize 100% redundancy to offer higher-level multiple fault restoration in WDM networks without wavelength conversion,” Computer Networks, vol. 53 ,2009, pp. 691–705.
[38] C. C. Sue, J. Y. Yeh, Y. C. Chen, and C. Y. Huang, “Tolerating Multiple Faults in WDM Networks without Wavelength Conversion,” Tencon’04, vol. 3, pp. 89-92.
[39] A. Banerjee, et al., "Generalized multiprotocol label switching: an overview of routing and management enhancements," IEEE Commun. Mag., vol. 39, no. 1, pp. 144-150, 2001.
[40] J. T. Park, “Resilience in GMPLS path management: model and mechanism,” IEEE Commun. Mag., vol. 42, no. 7, pp. 128-135, 2004.
[41] J. F. Labourdette, E. Bouillet, R. Ramamurthy, and A. A. Akyma, “Fast approximate dimensioning and performance analysis of mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 4, pp. 906-917, 2005.
[42] H.D. Rozenfeld, J.E. Kirk, E.M. Bollt and D. ben Avraham, “Statistics of cycles: how loopy is your network,” J. Phys. A: Math. Gen., vol. 38, pp. 4589–4595, 2005.
[43] C. Saradhi, M. Gurusamy and L. Zhou, “Differentiated QoS for survivable WDM optical networks,” IEEE Commun. Mag., vol. 42, no. 5, pp. 8-14, 2004.
[44] W. Wei, Q. Zeng, Y. Ouyang, and D. Lomone, “Differentiated integrated QoS control in the optical Internet,” IEEE Opt. Commun., vol. 42, no. 11, pp. 27–34, 2004.
[45] N. Golmie, T. Ndousse and D. Sue, “A differentiated optical services model for WDM networks,” IEEE Commun. Mag., vol. 38, pp. 68-73, 2000.
[46] A. Jukan and H. R. van As, “Service-specific resource allocation in WDM networks with quality constraints,” IEEE J. Select. Areas Commun., vol. 18, no. 10, pp. 2051-2061, 2000.
[47] Y. Boujelben, J. Belhoste and S. Pierre, “A Lightpath length-aware adaptive routing algorithm for WDM networks,” IEEE Commun. Letters, vol. 9, no. 8, pp. 750-752, 2005.
[48] P. L. Krapivsky and S. Redner, “Network growth by copying,” Phys. Rev. E, vol. 71, no. 3, 2005.
[49] P. Cholda, et al., “Service differentiation based on recovery methods,” in Proc. EuroNGI Workshop on Traffic Engineering, Protection and Restoration for NGI, 2005. [Online]. Available: http://www.kt.agh.edu.pl/~cholda/Papers/EuroNGI2005.pdf.
[50] T. H. Corman, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2001.
[51] N. Bouabdallah and B. Sericola, “A simple priority mechanism for shared-protection schemes,” IEEE Commun. Lett., vol. 11, no. 2, 2007.
[52] W. Fawaz and M. Khabbaz, “Incorporating mutation probability into priority-aware protection in optical networks,” IEEE Commun. Lett., vol. 13, no. 11, 2009.
[53] A. Kodian and W. D. Grover, “Multiple-quality of protection classes including dual-failure survivable services in p-cycle networks,” in Proc. IEEE BroadNets, 2005.
[54] W. Ni, et al., “On backup path activation to achieve differentiated dual-failure restorability in WDM mesh networks,” in Proc. COIN’08, 2008.
[55] N. Andriolli, A. Giorgetti, and L. Valcarenghi, “Idle protection capacity reuse in multiclass optical networks,” J. Lightw. Technol., vol. 25, no. 5, pp. 1152–1162, 2007.
[56] B. Chen, S. Bose, and W.-D. Zhong, “Priority Enabled Dynamic Traffic Grooming,” IEEE Commun. Lett., vol. 9, pp. 366-368, 2005.
[57] Optical Internetworking Forum, “User Network Interface (UNI) 2.0 Signaling Specification: Common Part,” OIF-UNI-02.0, Feb. 2008.
[58] H. Drid, B. Cousin, M. Molnar and S. Lahoud, “A survey of survivability in multi-domain optical networks,” Comput. Commun., vol. 33 no.8, pp.1005-1012, May, 2010.