彈性光網路在近幾年被提出來，它能夠建立彈性頻寬的通道，並且具有相當高的頻譜使用效率。在彈性光網路中，繞徑與頻譜配置的問題變成一個重要的議題。在這篇文章中，我們提出一個頻譜分層圖的方式來描敘紀錄頻譜的使用及查詢，我們提出的分層圖可以使用在彈性光網路或是傳統的光波分割多工網路中。

繞徑與頻譜配置問題在許多的研究中，以繞徑方面來看，可以分為三大類，固定繞徑，多個固定繞徑以及所有繞徑。所有繞徑的方式可以提供最高的機率找出答案，但是在以往的文章中，這類型的方式往往花費相當高的時間複雜度。而其中有一篇文章可以將複雜度從指數降低到多項式，但是卻沒有考慮頻譜方面的計算複雜度。我們提出的繞徑與頻譜配置演算法使用分層圖來降低頻譜方面的計算時間，並且在尋找繞徑上面的複雜度也是多項式複雜度。

彈性光網路在繞徑與頻譜配置問題中，有個嚴重問題叫做頻譜碎裂問題，這個問題會降低找出繞徑與頻譜配置答案的機率。在近幾年的文章中，有許多硬體上的技術，可以調整現有的連線，來整理這些碎裂問題。我們利用現有的頻譜調整技術來設計演算法，挪出可用的頻譜空間給連線要求。相較於以前的文章，我們可以調整必要的現有連線，以及比較少的移動距離總和。在模擬結果中，顯示了我們的繞徑與頻譜配置演算法跟所有繞徑相比，可以達到相同的找解機率以及使用較少的計算複雜度時間。在整理碎裂的問題上，我們的演算法在整理時要調整的連線數是所有連線數中的一小部分，跟其他文章相比，我們調整的連線數減少了95%的連線數，而調整的距離總和跟其他文章相比，減少了95% 的移動距離。

Elastic optical network (EON) has been proposed in recent years as a highly spectrum-efficient solution for implementing flexible bandwidth channels. In EON, Routing and spectrum assignment (RSA) has become key problem which incorporate routing and wavelength assignment (RWA) in traditional optical network. In this thesis, we proposed auxiliary graph which can be used in EON or traditional optical network.

The widely used dynamic RSA schemes include Fixed Routing, K-shortest Path (KSP) routing and Exhaust routing schemes (ERS). The ERS has the lowest blocking rate in these routing schemes, but it has the highest time complexity. The method reduce complexity of ERS from exponential to polynomial in network scalar has been proposed. However this polynomial method does not consider the spectrum slot scalar in EON. We purposed an RSA algorithm which use auxiliary graph to reduce the time complexity, from exponential to polynomial within network scale and consider the spectrum slots scalar, thus we use smaller computation compare with previous polynomial method.

There is an important factor that leading RSA into high blocking rate, called fragment problem in EON. There have several technologies can reconfigure existing optical connection to defragment. We propose an algorithm using the spectrum retuning technique to make room for request. Compare with previous study, we can retune the necessary connections and less shift distance. Simulation show the layer graph RSA can achieve same blocking with polynomial method and use less computation compare with polynomial method. In the defragment algorithm, we show the number of retuned connections only a small fraction of all connections.

[1] J. Armstrong, "OFDM for optical communications," IEEE/OSA Journal of Lightwave Technology, vol. 27, no. 3, Feb 1. 2009, pp. 189-204.
[2] L. Babai, W. Kantor and E. Luks, “Computational complexity and the classification of finite simple groups,” Proc. 24th Foundations of Computer Science (FOCS), Nov. 1983, pp. 162-171
[3] A. Castro et al. “Dynamic routing and spectrum (re)allocation in future flexgrid optical networks,” Journal of Computer Network, vol. 56, no. 12, Aug. 2012, pp. 2869–2883.
[4] X. Chen, A. Jukan, and A. Gumaste, "Multipath de-fragmentation: Achieving better spectral efficiency in elastic optical path networks," INFOCOM, April 2013, pp.390-394
[5] X. Chen, et al.,"A Pattern-layered routing and spectrum allocation in OFDM-based flexible optical networks," Communications and Photonics Conference (ACP), Nov. 2012, pp.1,3, 7-10
[6] C. Chen, and S. Banerjee, “A new model for optimal routing in all-optical networks with scalable number of wavelength converters,” GLOBECOM, Nov 1995, pp. 13-17.
[7] K. Christodoulopoulos, I. Tomkos, E.A. Varvarigos, "Elastic bandwidth allocation in flexible OFDM-Based optical networks," IEEE/OSA Journal of Lightwave Technology, vol.29, no.9, May 2011, pp.1354-1366
[8] K. Christodoulopoulos, I. Tomkos, E.A. Varvarigos, "Routing and spectrum allocation in OFDM-Based optical networks with elastic bandwidth allocation," GLOBECOM, 6-10 Dec. 2010, pp.1-6.
[9] F. Cugini, et al., “Push-pull defragmentation without traffic disruption in flexible grid optical networks,” IEEE/OSA Journal of Lightwave Technology, vol. 31, no. 1, Jan. 2013, pp. 125–133.
[10] R. Dischler; F. Buchali; A. Klekamp "Demonstration of bit rate variable ROADM functionality on an optical OFDM superchannel," Optical Fiber Communication (OFC), collocated National Fiber Optic Engineers Conference (OFC/NFOEC), 21-25 March 2010, pp.1-3.
[11] G. Donald, et al., “Fundamental of queuing theory,” 3th ed, Wiley-Interscience, 2008
[12] O. Gerstel, M. Jinno, A. Lord, and S. J. B. Yoo, “Elastic optical networking: A new dawn for the optical layer?,” IEEE Communication Mag., vol. 50, no. 2, , Feb. 2012, pp. 12–20.
[13] P. Fishwick, SimPack Toolkit, http://www.cise.ufl.edu/~fishwick/simpack.html
[14] L. Gong and Z. Zhu, "Virtual optical network embedding (VONE) over elastic optical networks," IEEE/OSA Journal of Lightwave Technology, vol.32, no.3, Feb.1, 2014, pp.450,460
[15] T. Hashimoto; K.-i. Baba; S. Simojo, "A study on routing, modulation level, and spectrum allocation algorithms for elastic optical path networks, " International Conference on Photonics (ICP), 1-3 Oct. 2012, pp.395,399.
[16] M. Jinno, et al., “Filtering characteristics of highly-spectrum efficient spectrum-sliced elastic optical path (SLICE) network,” OFC/NFOEC, 22-26 March 2009, pp.1,3,
[17] M. Jinno, et al., "Spectrum-efficient and scalable elastic optical path network: Architecture, benefits, and enabling technologies," IEEE Communications. Mag., vol. 18, Nov. 2009, pp. 66-73.
[18] M. Jinno, et al., A., "Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network," IEEE Communications Mag., vol.48, no.8, August 2010, pp.138,145.
[19] M. Klinkowski; K. Walkowiak, "Routing and spectrum assignment in spectrum sliced elastic optical path network," IEEE Communications Letters, vol.15, no.8, August 2011, pp.884,886
[20] Y. Liul, et al.,” A Spectrum-scan routing scheme in flexible optical networks,” Communications and Photonics Conference and Exhibition 13-16 Nov. 2011
[21] W. Lu; X. Zhou, L. Gong, M. Zhang and Z., Zhu, "Dynamic multi-path service provisioning under differential delay constraint in elastic optical networks," IEEE Communications Letters , vol.17, no.1, January 2013, pp.158,161
[22] A. Nag; M. Tornatore; B. Mukherjee, "Optical network design with mixed line rates and multiple modulation formats, "Optical Fiber Communication (OFC), 22-26 March 2009, pp.1,3
[23] A.N. Patel, et al., "Defragmentation of transparent Flexible optical WDM (FWDM) networks," Optical Fiber Communication Conference and Exposition collocated the National Fiber Optic Engineers Conference (OFC/NFOEC), 6-10 March 2011, pp.1,3
[24] G. Shen and Q. Yang, “From coarse grid to mini-grid to gridless: How much can gridless help contentionless,” in Proc. Conference on Optical Fiber Communication (OFC), 2011.
[25] Z. Shuqiang; C. Martel, B. Mukherjee, "Dynamic traffic grooming in elastic optical networks," IEEE journal of selected areas in communication, vol.31, no.1, January 2013, pp.4,12
[26] C. Siva Ram Murthy, M. Gurusamy, “WDM optical networks: concepts, design, and algorithms”, 26 November 2001
[27] T. Takagi, et al., "Disruption minimized spectrum defragmentation in elastic optical path networks that adopt distance adaptive modulation," European Conference and Exhibition on Optical Communication (ECOC), 18-22 Sept. 2011, pp.1,3.
[28] X. Wan, N. Hua and X. Zheng, “Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks,” Journal of Optical Communication Network, vol. 4, no. 8, Aug. 2012, pp. 603–613
[29] R. Wang and B. Mukherjee, “Spectrum management in heterogeneous bandwidth networks,” GLOBECOM, Dec. 2012, pp. 2914–2918.
[30] X. Wan, N. Hua, H. Zhang et al., “Study on dynamic routing and spectrum assignment in bitrate-flexible optical networks". Photonic Network Communications, Vol. 24, Issue 3 , DEC 2012, pp 219-227.
[31] R. Wang and B. Mukherjee, "Provisioning in elastic optical networks with non-disruptive defragmentation," IEEE/OSA Journal of Lightwave Technology, vol.31, no.15, Aug.1, 2013, pp.2491,2500.
[32] Y. Wang, X. Cao, Y. Pan "A study of the routing and spectrum allocation in spectrum-sliced Elastic Optical Path networks," INFOCOM, , 10-15 April 2011, pp.1503-1511.
[33] K. Wen, et al., “Adaptive spectrum control and management in elastic optical networks,” IEEE journal of selected areas in communication, vol. 30, no. 1, Jan. 2013, pp. 39–48
[34] L. Xiahe, L. Gong, Z. Zhu, "Design integrated RSA for multicast in elastic optical networks with a layered approach," GLOBECOM, 9-13 Dec. 2013, pp.2346-2351.
[35] L. Yang, et al., "Polynomial-time adaptive routing algorithm based on spectrum scan in dynamic flexible optical networks," Communications, China, vol.10, no.4, April 2013, pp.49-58.
[36] Y. Yin, K. Wen, D.J. Geisler, R., Liu and S. J. B., Yoo,"Dynamic on-demand defragmentation in flexible bandwidth elastic optical networks," journal of Optical Express vol., 20, January 12, 2012, pp.1798-1804.
[37] Y. Yin, M. Zhang, Z. Zhu and S. J. B. Yoo,“Fragmentation-aware routing, modulation and spectrum assignment algorithms in elastic optical networks,” IEEE/OSA OFC, Mar. 2013, pp.1-3..
[38] M. Zhang, et al., “Spectrum defragmentation algorithms for elastic optical networks using hitless spectrum retuning techniques,” IEEE/OSA OFC, Mar. 2013, pp.1-3.
[39] H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Optical Network. Mag., vol. 1, no. 1, Jan. 2000, pp. 47–60
[40] L. Zhang, et al., "Dynamic RMSA in spectrum-sliced elastic optical networks for high-throughput service provisioning", International Conference on Computing, Networking and Communications (ICNC), 28-31 Jan. 2013, pp.380-384.
[41] M. Zhang, et al., "Bandwidth defragmentation in dynamic elastic optical networks with minimum traffic disruptions," ICC, 9-13 June 2013, pp.3894-3898.
[42] G. Zhang, M. De Leenheer; A., Morea,; B., Mukherjee, "A survey on OFDM-based elastic core optical networking," Communications Surveys & Tutorials, vol.15, no.1, Feb 2013, pp.65,87