資訊科技的進步，雲端運算、可攜式裝置的流行，網路流量大量增長，如何增加可用頻寬以利於乘載更加劇量的流量將是一巨大挑戰，因此，網路必須具備適應未來動態流量快速變化之能力。在傳統光纖網路－波長分波多工網路將單一波長視為一高速傳輸通道藉以傳輸乘載資料的光訊號，然而僵化的傳輸單位是其最大之限制，不論何種速率之連線都將其放入整數倍固定頻寬的完整波長中，而造成頻寬使用效率低落之問題。近年來，光正交頻分復用技術的發展開啟了彈性光網路之時代，此技術能聚合多個低速子載波乘載資料，載波彼此間部分重疊並維持正交性，再者其能彈性切割光通道不固定以單一波長為單位，大幅提升頻譜使用效率並降低訊號沿途所經歷之物理耗損，使彈性光網路成為未來發展趨勢之主流。
繞徑與頻譜配置是彈性光網路中的重要議題，由於此問題已被證實其最佳化的光路徑配置方式為NP-hard問題，因此，近年來眾多學者投入心力設計具有較佳良好網路表現的繞徑與頻譜配置演算法，雖然能有效地提升網路傳輸頻寬，但往往需要耗費大量的計算時間，就繞徑和頻譜配置兩階段來看，多數繞徑演算法的時間複雜度幾乎不跳脫O(n^2)的範圍，而在頻譜配置上須檢查是否有可利用之頻譜區段，隨著可用頻譜區段數量的增加，檢查的時間複雜度也隨之提升，有鑑於此，本篇論文提出在於彈性光網路中之動態繞徑與頻譜配置演算法，以群集作為一個新的配置單元之概念首次被使用在論文中，目的是為了降低在頻譜配置方面所需要的計算時間；然而在初始設計中雖然能達到大幅的降低執行時間的目的，但在連線阻斷比率上卻不盡人意，透過分析初始方法設計並考量可能引發的負面影響，進而延伸出子群集、超群集及虛擬群集之概念，並透過概念間的整合發展出各類不同的方法並於實驗數據中呈列各類方法的網路表現，其中表現最佳之方法SCB+NP相對於比較方法SPV而言，在頻寬阻斷率上約略有最大5%的差異幅度，但卻可於小拓樸中節省至少35%的計算時間，在大拓樸中甚至可以節省至少61%的計算時間，因此就實驗結果而言，此篇論文所提出之群集配置方法有利於維持整體網路的運作，不僅能維持可接受的網路表現並且大幅節省執行時間。

With the rapid growth of traffic in network, the traditional Wavelength-Division Multiplexing (WDM) optical networks encounters the difficulty of inefficient spectrum utilization because of its rigid granularity. With the O-OFDM technology arising, the subcarriers are partial overlapped with each other on the spectrum space, saving more spectrum resources than WDM. The bandwidth-variable transponders (BV-Ts) and bandwidth-variable cross-connect (BV-OXCs) enable the elastic optical networks (EONs). EON provides flexibility and approximate-sized spectrum resources for heterogeneous traffic. The routing and spectrum assignment (RSA) problem is a main part in EONs. The optimal assignment is proved as a NP-hard problem. Efficiently establishing optical paths for connections considering both Bandwidth Blocking Probability (BBP) and computation time becomes an important issue. In this thesis, we propose a novel spectrum assignment strategy with a new assignment unit, cluster. The design of the cluster aims at the rapid assignment for connections to be assigned into the spectrum space, which is substituted for searching frequency slots. However, the limitation of the cluster assignments causes some side effects, harmful to the network performance. We analyze all of the possible drawbacks and their occurrences. Sub-cluster extension, super-cluster extension and virtual cluster extension are developed to deal with these drawbacks. The sub-cluster extension is to collect the fragments in a cluster, which can be reused by connections, while super-cluster allows connections to assign into multiple clusters. The virtual cluster is a resources management mechanism, aggregating the free spectrum resources in the network. Simulation results show that our proposed scheme is still a competitive and serviceable dynamic RSA algorithm in EONs. The BBP improvement of SCB+NP is at most 5% as long as to the one of comparison, but SCB+NP can save at least 35 % execution time in small topology and even at least 61% execution time in larger topology. Our proposed method can save much computational time while the BBP performance is still acceptable.

[1] M. S. Borella, J. P. Jue, D. Banerjee, B. Ramamurthy and B. Mukherjee, "Optical components for WDM lightwave networks," in Proc. IEEE, vol. 85, no. 8, Aug. 1997, pp. 1274-1307.
[2] Y. C. Chang, “On layered-graph-model-based spectral resource management in elastic optical networks,” Technical Report, National Cheng Kung University, Taiwan, July 2014.
[3] C. Chen and S. Banerjee, “A new model for optimal routing in all–optical networks with scalable number of wavelength converters,” IEEE GLOBECOM, 1995, pp. 13-17.
[4] I. Chlamtac, A. Ganz and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WAN's," IEEE Trans. on Communications, vol. 40, no. 7, Jul 1992, pp. 1171-1182.
[5] X. Chen, et al., "A pattern-layered routing and spectrum allocation in OFDM-based flexible optical networks," in Asia Communications and Photonics Conf., Nov. 2012, pp. 1-3.
[6] B. Chatterjee, N. Sarma and E. Oki, "Routing and spectrum allocation in elastic optical networks: a tutorial," IEEE Communications Surveys & Tutorials, no. 99, 2015, pp. 1-1.
[7] K. Christodoulopoulos, I. Tomkos and E.A. Varvarigos, "Elastic bandwidth allocation in flexible OFDM-based optical networks," J. Lightwave Technol., vol. 29, no. 9, May 2011, pp. 1354-1366.
[8] P. A. Fishwick, “SimPack: getting started with simulation programming in C and C++,” in Proceedings of the 24th conference on Winter simulation, ACM, Dec. 1972, pp. 154-162.
[9] W. Fawaz, B. Daheb, O. Audouin and G. Pujolle, "Service level agreement and provisioning in optical networks," IEEE Commun. Mag., vol. 42, no. 1, Jan. 2004, pp. 36-43.
[10] O. Gerstel, M. Jinno, A. Lord and S.J.B. Yoo, "Elastic optical networking: a new dawn for the optical layer?," IEEE Commun. Mag., vol. 50, no. 2, b. 2012, pp. s12-s20.
[11] M. Garnot, M. Sotom and F. Masetti, "Routing strategies for optical paths in WDM networks," in IEEE International Conf. on Communications, 1997, pp. 422-426.
[12] L. Gong, X. Zhou, X. Liu, W. Zhao, W. Lu, Z. Zhu, "Efficient resource allocation for all-optical multicasting over spectrum-sliced elastic optical networks," IEEE/OSA J. Opt. Commun. Netw., vol. 5, no. 8, Aug. 2013, pp. 836-847.
[13] C. F. Hsu, Y. C. Chang and S. C. Sie, “On layered-graph-model-based routing and spectrum assignment in elastic optical networks,” in IEEE Conf. Proc. GLOBECOM 2015.
[14] J. Taha Haitham and M. F. M. Salleh., “Multi-carrier transmission techniques for wireless communication systems: a survey,” WSEAS Trans. Commun. (WTOC) , May 2009, pp. 457-472.
[15] E. Hyytia and J. Virtamo, "Wavelength assignment and routing in WDM networks," Nordic Teletraffic Seminar (NTS), Copenhagen, Denmark, Aug. 1998.
[16] T. Hwang, C. Yang, G. Wu, S. Li and G.Y. Li, "OFDM and its wireless applications: a survey," IEEE/OSA Trans. Veh. Technol., vol. 58, no. 4, May 2009, pp. 1673-1694.
[17] ITU-T Rec. G.694.1, “Spectral grids for WDM applications: DWDM frequency grid,” 2006.
[18] M. Jinno, et al., "Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies," IEEE Commun. Mag., vol. 47, no. 11, Nov. 2009, pp. 66-73.
[19] M. Jinno, et al., “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag., vol. 48, no. 8, Aug. 2010, pp. 138-145.
[20] K. Kuang, et al., "Dynamic routing and spectrum allocation in elastic optical networks with mixed line rates," in IEEE 15th International Conference on High Performance Switching and Routing (HPSR), Jul. 2014, pp. 1-6.
[21] D. W. Matula, G. Marble, and J. D. Issacson, “Graph coloring algorithms,” in Graph Theory and Computing (R. C. Read, ed.), ch. 10, New York and London: Academic Press, 1972, pp. 109-122.
[22] C. Siva Ram Murthy and M. Gurusamy, "WDM Optical Networks Concepts, Design, and Algorithms," Prentice Hall PTR, 2002.
[23] A. Rosa, C. Cavdar, S. Carvalho, J. Costa and L. Wosinska, "Spectrum allocation policy modeling for elastic optical networks," in 9th International Conference on High Capacity Optical Networks and Enabling Technol. (HONET), Dec. 2012, pp. 242-246.
[24] M. Recalcati, F. Musumeci, M. Tornatore, S. Bregni and A. Pattavina, "Benefits of elastic spectrum allocation in optical networks with dynamic traffic," IEEE Latin-America Conference on Communications (LATINCOM), Nov. 2014, pp. 1-6.
[25] G. Raybon, et al., "1-Tb/s dual-carrier 80-GBaud PDM-16QAM WDM transmission at 5.2 b/s/Hz over 3200 km" in Proc. 2012 IEEE Photonics Conference (IPC), Sept. 2012, pp. 1-2.
[26] S. Shirazipourazad, Z. Derakhshandeh and A. Sen, "Analysis of on-line routing and spectrum allocation in spectrum-sliced optical networks," 2013 IEEE International Conference on Communications (ICC), Jun. 2013, pp. 3899-3903.
[27] G. Shen and Q. Yang, "From coarse grid to mini-grid to gridless: how much can gridless help contentionless?," in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf., Mar. 2011, pp. 1-3.
[28] T.K. Tan and J.K. Pollard, "Determination of minimum number of wavelengths required for all-optical WDM networks using graph colouring," IEEE Electronics Lett., vol. 31, no. 22, Oct 1995, pp. 1895-1897.
[29] Y. Wang, X. Cao, Q. Hu and Y. Pan, "Towards elastic and fine-granular bandwidth allocation in spectrum-sliced optical networks," IEEE/OSA J. Opt. Commun. Netw., vol. 4, no. 11, Nov. 2012, pp. 906-917.
[30] Y. Wang, X. Cao and Y. Pan, "A study of the routing and spectrum allocation in spectrum-sliced Elastic Optical Path networks," in Proc. IEEE INFOCOM, Apr. 2011, pp. 1503-1511.
[31] X. Wan, N. Hua and X. Zheng, "Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks," IEEE/OSA J. Opt. Commun. Netw., vol. 4, no. 8, Aug. 2012, pp. 603-613.
[32] D. J. A. Welsh and M. B. Powell, “An upper bound for the chromatic number of a graph and its application to timetabling problems,” J. Comput, vol. 10, 1967, pp. 85-86.
[33] J. Y. Yen, “Finding the k shortest loopless paths in a network,” Manage. Sci., vol. 17, no. 11, 1971, pp. 712–716.
[34] L. Yang, H. Nan, Z. Xiaoping, Z. Hanyi and Z. Bingkun, "Polynomial-time adaptive routing algorithm based on spectrum scan in dynamic flexible optical networks," China Commun., vol. 10, no. 4, Apr. 2013, pp. 49-58.
[35] X. Yu, Y. Zhao, J. Zhang, B. Mukherjee, J. Zhang, and X. Wang, "Static routing and spectrum assignment in co-existing fixed/flex grid optical networks," in Optical Fiber Communication Conf., 2014, paper W2A.59.
[36] Z. Zhu, X. Chen, C. Chen, S. Ma, M. Zhang, L. Liu and S.J.B. Yoo, "OpenFlow-assisted online defragmentation in single-/multi-domain software-defined elastic optical networks [invited]," IEEE/OSA J. Opt. Commun. Netw., vol. 7, no. 1, Jan. 2015, pp. A7-A15.
[37] H. Zhang, J.P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Netw. Mag., vol. 1, no. 1, Jan. 2000, pp. 47-60.
[38] G. Zhang, M. De Leenheer, A. Morea and B. Mukherjee, "A survey on OFDM-based elastic core optical networking," IEEE Communications Surveys & Tutorials, vol. 15, no. 1, First Quarter 2013, pp. 65-87.
[39] Z. Zhu, W. Lu, L. Zhang and N. Ansari, "Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing," J. Lightwave Technol., vol. 31, no. 1, Jan. 2013, pp. 15-22.
[40] L. Zhang, W. Lu, X. Zhou and Z. Zhu, "Dynamic RMSA in spectrum-sliced elastic optical networks for high-throughput service provisioning," International Conference on Computing, Networking and Communications (ICNC), Jan. 2013, pp. 380-384.
[41] S. Zhang, C. Martel and B. Mukherjee, "Dynamic traffic grooming in elastic optical networks," IEEE/OSA J. Sel. Areas Commun., vol. 31, no. 1, Jan. 2013, pp. 4-12.