在傳統光纖網路上，波長分波多工網路將一個波長視為傳送的單位，藉以傳輸乘載資料的光訊號，但是波長分波多工網路有個缺點，就是不管何種速率的連線都會將其放入整數倍的波長頻寬當中，造成頻寬的使用效率較低。而近年來，隨著光正交頻分復用技術的發展，可以將子載波做部分的重疊並維持正交性，此技術提高了頻譜的使用效率，而開啟了彈性光網路的時代，在彈性光網路裡面，可以將光通道彈性的去做切割，大幅提升頻譜的使用效率，使彈性光網路成為未來發展的主流，在彈性光網路上，繞徑與頻譜配置是一個很重要的議題，如何在建立連線的時候，有效的去分配頻譜的使用。
本篇論文提出在靜態的繞徑與頻譜配置中，以群集為一個配置單位，主要是為了增加配置的速度，我們總共提出三種分配群集的方式，分別為以深度優先搜尋的群集覆蓋、以廣度優先搜尋的群集覆蓋和切割的群集覆蓋，在實驗數據模擬的部分，我們去比較了CC_Refinement的效益、MS值、總共使用的slot數量、執行時間、lower bound的分析和upper bound的分析，在MS值方面，我們可以達到一樣的效果，另外在lower bound的分析和upper bound的分析上，我們可以提高lower bound和降低upper bound，所以我們的方法可以縮短lower bound和upper bound之間的差距。

The traditional Dense Wavelength Division Multiplexing (DWDM) network is an inefficiency of spectral utilization because of its fixed granularity. Based on Orthogonal Frequency-Division Multiplexing (OFDM) transmission technology, the subcarriers can be partially overlapping in the spectrum domain, which can provide high spectral efficiency. In EON, the Routing and Spectrum Assignment (RSA) is the main issue and we discuss the static version. In static RSA, all requests are known a priori. Its primary goal is usually to minimize maximum number of subcarriers and meanwhile accommodate all requests. In this thesis, we propose three schemes to determine cliques in the corresponding auxiliary graph of the static RSA problem. They are clustering-based clique covering search by depth-first (CBCC_DFC), clustering-based clique covering search by breadth-first (CBCC_BFC) and partitioning-based clique covering (PBCC). We construct a reuse graph in advance. CBCC_DFC search on reuse graph by depth-first. CBCC_BFC search on reuse graph by breadth-first and PBCC is partitioning vertices on reuse graph. A clique in reuse graph is corresponding to a cluster in elastic optical networks. The size of a cluster is determined by the biggest demand size of requests belonging to the corresponding clique. In simulation, we compare the effect of CC_Refinement, the MS value, total used slots, execution time, lower bound analysis and upper bound analysis. Our method can achieve the same MS value as SPSR. Moreover, we can reduce the gap between lower bound and upper bound.

[1] M. Aouchiche and P. Hansen, “A survey of Nordhaus-Gaddum type relations,” Journal of Discrete Applied Mathematics, vol. 161, no. 4-5, Mar. 2013, pp. 466-546.
[2] C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam.
[3] B. Chatterjee, N. Sarma and E. Oki, "Routing and spectrum allocation in elastic optical networks: a tutorial," IEEE Communications Surveys & Tutorials, vol. 17, no. 3, May 2015, pp. 1776-1800.
[4] C.-F. Hsu, Y.-C. Chang, and S.-C. Sie, “Graph-model-based dynamic routing and spectrum assignment in elastic optical networks,” IEEE/OSA Journal of Optical Communications and Networking, to appear. (SCI)
[5] ITU-T Rec. G.694.1, “Spectral grids for WDM applications: DWDM frequency grid,” 2006.
[6] M. Jinno, et al., "Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies," IEEE Communications Magazine, vol. 47, no. 11, Nov. 2009, pp. 66-73.
[7] M. Jinno, et al., “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Communications Magazine, vol. 48, no. 8, Aug. 2010, pp. 138-145.
[8] B. Mukherjee, Optical WDM Networks. Berlin, Germany: Springer- Verlag, 2006.
[9] D. Pritchard, “An optimal distributed bridge-finding algorithm,” in Proceedings of the 25th annual ACMSIGACT-SIGOPS symposium on Principles of Distributed Computing (PODC’06), Denver, Colorado, USA, Jul. 2006.
[10] R. E. Tarjan, “A note on finding the bridges of a graph,” Information Processing Letters, vol. 2, no. 6, 1974, pp. 160-161.
[11] C. V. Nuffelen and K. V. Rompay, “Upper bounds on the independence and clique covering number,” 4OR vol. 1, no. 1, Mar. 2003, pp. 43–50.
[12] D. J. A. Welsh and M. B. Powell, “An upper bound for the chromatic number of a graph and its application to timetabling problems,” Computer Journal, vol. 10, no. 1, 1967, pp. 85–86.
[13] N. Wang and J. P. Jue, “Holding-time-aware routing, modulation, and spectrum assignment for elastic optical networks,” IEEE Globecom 2014, Dec. 2014, pp. 2180-2185.
[14] Y. Wang, X. Cao, Q. Hu, and Y. Pan, “Towards elastic and fine-granular bandwidth allocation in spectrum-sliced optical networks,” IEEE/OSA Journal of Optical Communications and Networking, vol. 4, no. 11, Nov. 2012, pp. 906–917.
[15] X. Wan, N. Hua and X. Zheng, "Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks," IEEE/OSA Journal of Optical Communications and Networking, vol. 4, no. 8, Aug. 2012, pp. 603-613.
[16] 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 Communications, vol. 10, no. 4, Apr. 2013, pp. 49-58.
[17] H. Zhang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Optical Networks Magazine, vol. 1, no. 1, Jan. 2000, pp. 47-60.