## Abstract

Optical networks with flexible bandwidth provisioning have become a very promising networking architecture. It enables efficient resource utilization and supports heterogeneous bandwidth demands. In this paper, two novel spectrum defragmentation approaches, i.e. Maximum Path Connectivity (MPC) algorithm and Path Connectivity Triggering (PCT) algorithm, are proposed based on the notion of Path Connectivity, which is defined to represent the maximum variation of node switching ability along the path in flexible bandwidth networks. A cost-performance-ratio based profitability model is given to denote the prons and cons of spectrum defragmentation. We compare these two proposed algorithms with non-defragmentation algorithm in terms of blocking probability. Then we analyze the differences of defragmentation profitability between MPC and PCT algorithms.

©2013 Optical Society of America

## 1. Introduction

Considering the forecasted doubling in the amount of Internet-protocol (IP) traffic every two years, the looming physical limit of optical fibers will lead to a capacity crunch in optical transport systems in the not-so-distant future [1]. Under these circumstances, by introducing elasticity and adaptation into the optical domain, flexible bandwidth networks [2–4] are proposed and demonstrated as a promising networking approach. In such a flexible architecture, the current DWDM rigid grid is further divided into a number of narrow spectrum segments, which are named as frequency slots (FSs). A connection is made by allocating required minimum spectral resources (i.e., a required numbers of consecutive FSs) on all links along the path based on traffic demand and network conditions. However, in a dynamic traffic scenario, dynamic path setup and teardown operation will inevitably lead to spectral fragmentation, thus increasing the blocking probability. Additionally, the original routing and spectrum allocation will deviate from the optimal one over time. So from the network operator’s point of view, it is necessary to periodically optimize the network back to an optimal state so as to operate in a more efficient way. This operation is defined as network defragmentation and it is an important issue in flexible bandwidth networks.

The studies focusing on the defragmentation concern several important issues, which mainly include defragmentation trigger scheme, spectrum reconfiguration approach and defragmentation evaluation model [5–10]. There are mainly two kinds of trigger mechanism. The first one is traffic triggering method, which operates the spectral defragmentation for each being blocked connection demand [5, 6]. Another one is parameter-triggering mechanism which triggers defragmentation according to a pre-defined threshold which reflects the network current status [10]. With an explicit aim, the traffic-triggering algorithm locally reconfigures the network by less disturbing the online-traffic. On the contrary, the parameter-triggering mechanism aims to return the network back to its optimal status by globally reconfiguring online traffic. During the process of spectral defragmentation, different approaches are proposed based on its defragmentation target. For example in work [7], with the aim to minimize the number of interrupted connections, Greedy-Defragmentation algorithm and Shortest-Path-Defragmentation algorithm are proposed. Another important issue is the how to evaluate the spectrum defragmentation. Several metrics have been proposed to evaluate its profitability, including the blocking probability reduction [5–10], interruption connections [6] and traffic accommodation capacity [5].

In this paper, we study the dynamic spectrum defragmentation problem in flexible bandwidth optical networks [11]. Firstly, a notion of Node Spectral-X eigenvectors is introduced and a metric of Path Connectivity is formulated. Accordingly, two novel dynamic spectral defragmentation schemes (MPC and PCT) are proposed aiming to accommodate the being blocked demand or optimize the network status. In order to quantitatively describe the benefit of defragmentation, we define a cost-performance-ratio based profitability model to denote the pros and cons of spectrum defragmentation. We then compare these two proposed algorithms with non-defragmentation conditions in terms of blocking probability and defragmentation profitability. Simulation results show that compared to the non-defragmentation condition, both MPC and PCT defragmentation algorithms can better improve the performance of blocking probability. In case of light traffic load condition, MPC gains higher defragmentation profitability while in the heavy load condition, PCT is better in respect of defragmentation profitability.

The rest of this paper is organized as follows. In Section 2, we introduce a notion of Path Connectivity in the flexible bandwidth optical network. In Section 3, we propose two dynamic spectrum defragmentation algorithms based on this notion. The simulation results follow in Section 4, where we present numerical analysis of these proposed algorithms. Finally, Section 5 concludes the paper.

## 2. Path connectivity in flexible bandwidth optical networks

Connectivity, a terminology in graph theory, includes Point-Connectivity and Edge-Connectivity, which denotes the minimum number of node and edge without which a connected graph will turn into an unconnected graph. Here, we adopt this terminology to define the Path Connectivity in flexible bandwidth optical networks, which reflect the similarity degree of node’s switching ability along the path.

#### 2.1 Node Spectral-X Eigenvector of Spectrum Usage Matrix

Define a network as *G*{*V*,*E*,*S*} where *V* denotes the set of bandwidth-variable switching nodes, *E* represents the set of bi-directional fiber links between nodes in *V*. Let |*V*| = *N* and |*E*| = *L* denote the numbers of network nodes and links respectively. *S* denotes the set of FSs on each link, |*S*| = *F*. The link spectrum occupation is expressed using an *F* bit array, in which each binary bit indicates the usage of the corresponding FS. The bit value 1 means a free slot while the bit value 0 corresponds to an occupied slot. The Spectrum Usage Matrix of node *k*, which degree is ${n}_{k}$, is represented as follows:

Here, each row ${D}_{i}(k)$in the matrix ${U}_{k}$denotes the spectrum occupation on the corresponding connecting link. From another perspective, each column vector $F{S}_{i}$ in the Matrix indicates the *i-*th FS usage among the node connecting links. In detail, there are ${a}_{i}={\displaystyle {\sum}_{m=1}^{{n}_{k}}{O}_{m,i}}$ connecting links whose *i-*th FS are free. Among these links, there exist ${r}_{i}^{\left(k\right)}$ types of link pairs (i.e. route) via node k, on which at least the *i-*th FS can be allocated.

Particularly, with the consideration of the spectrum consecutive constraint, on these ${r}_{i}^{\left(k\right)}$ routes, the number of possible accommodation state [12] using the *i-*th FS for all possible path bandwidth is defined as ${n}_{i}^{\left(k\right)}$. So, the average bandwidth of each possible accommodation state ${b}_{i}^{\left(k\right)}$ is calculated as follows:

Where ${b}_{j}$ is the bandwidth of accommodation state *j*. The value of ${b}_{i}^{\left(k\right)}$represents the consecutiveness degree of the *i-*th FS to the adjacent available FSs and ${b}_{i}{}^{\left(k\right)}\cdot {r}_{i}^{\left(k\right)}$ denotes node’s switching ability on the *i-*th FS. So for Node *k*, a notion of Spectral-X Eigenvector is introduced to denote its switching ability for all FSs. In detail, the *Node Spectral-X Eigenvector* of node *k* is defined as follows:

Figure 1
depicts an example of how to calculate the Node spectral-X Eigenvector. As shown in Figs. 1(a)-1(b), the degree of Node *k* is 3, the connecting links to the Node is L1, L2, L3 and their spectrum occupation status is shown in the figure. The eigenvector *r _{k}* can be got according to Eq. (2). Figure 1(c) shows the possible accommodation states for all FSs when every adjacent links are on a candidate route. The blue dotted ellipse in Fig. 1(d) is the possible accommodation states set including the 7-th FS. The average bandwidth of these accommodation states including the 7-th FS is calculated according to Eq. (3): ${b}_{7}^{\left(k\right)}=\left(1+2+1+2+1+2+2+3\right)/7=2$. In the same way, the average bandwidth of each possible accommodation state for all FSs can be got:

According to Eq. (4), the *Node Spectral-X Eigenvector* of node *k* is calculated as:

#### 2.2 Path Connectivity in flexible bandwidth optical networks

Then regarding a path *p* with *m* nodes ($L=\left\{{k}_{1},{k}_{2},\mathrm{...},{k}_{m}\right\}$), there exists an *m*-elements-size vector space ($Spac{e}_{p}=\left\{{e}_{{k}_{1}},{e}_{{k}_{2}},\mathrm{...},{e}_{{k}_{m}}\right\}$) called *Path Spectral-X Eigenvector Space*. The mean vector of Path Spectral-X Eigenvectors in the Space expresses the center of them, which is calculated as follow:

Define $d\left({k}_{i}\right)$as the distance between the Path Spectral-X Eigenvector of node ${k}_{i}$ and the mean vector ${\mu}_{p}$, which can be illustrated by Eq. (8).

Among these Path Spectral-X Eigenvectors, node *a* and node *b* are the nodes whose Node Spectral-X eigenvectors are the farthest and nearest to the mean vector${\mu}_{p}$. They are chosen by Eq. (9) and Eq. (10) respectively.

Based on these, the similarity between node *a* and node *b*’s Node Spectral-X eigenvectors is defined as *Path Connectivity*${C}_{p}$. The value of ${C}_{p}$ represents the maximum variation of node switching ability along the path. It is calculated as follows:

In the definition of Path Connectivity, it can be seen that *a* and *b* are the nodes whose eigenvectors are the farthest and nearest to the mean vector respectively. That is to say, the switching uniformity of these two nodes is of the greatest difference among all nodes along the path. In this way, Path Connectivity shows the largest barrier for traffic to go through this path. Figure 2
is a conceptualized illustration of the notions in the proposed model. As shown, the blue thick line represents path *p*, consisting of node *V1, V2, V5* and *V*6. Take *V5* for example, based on the spectrum occupation situation of connected links, the Spectrum Usage Matrix of node *V5* can be expressed, which is shown in the bottom left of Fig. 2. According to Eq. (2) and Eq. (3), ${r}_{i}^{\left(5\right)}$and ${b}_{i}^{\left(5\right)}$ is calculated respectively, which calculation process are illustrated by the red and blue dashed circle. Then the Spectral-X Eigenvector of node *V5* can be got by Eq. (4), which is represented as${e}_{5}$. In a similar way, the Spectral-X Eigenvector the other nodes along the path is calculated and the Path Spectral-X Eigenvector Space of path *p* (say$spac{e}_{p}=\{{e}_{1},{e}_{2},{e}_{5},{e}_{6}\}$) can be established. The Path Spectral-X Eigenvector Space can be illustrated by a multi-dimensional cube, which is shown in the right top of Fig. 2. From Eq. (7), the mean vector in the Space is got, as shown by red arrow line in the space cube. According to Eq. (8), Eq. (9) and Eq. (10), the farthest and nearest Spectral-X Eigenvector to the mean are chosen respectively. Finally, the similarity between these two eigenvectors is defined as the Path Connectivity of path *p*, which is represented as the intersection angle between these two eigenvectors in the cube.

## 3. Path connectivity based dynamic spectral defragmentation

In flexible bandwidth networks, dynamic request will be blocked when there are no enough consecutive spectrum resources on links that a new path tries to traverse. Reconfiguring the existing connections by re-routing and re-allocating the spectrum to create enough free continuous slots on those links for the new traffic demands can reduce the blocking probability. Defragmentation attained by this reconfiguration is effective for it optimize the fragmented spectrum resources. In this paper, based on the notion of Path Connectivity, we propose two novel spectral defragmentation strategies, which are Maximum Path Connectivity (MPC) algorithm and Path Connectivity Triggering (PCT) algorithm.

#### 3.1 Maximum Path Connectivity algorithm (MPC)

In the proposed MPC algorithm the defragmentation is conducted in a make-before-break manner [3], with the aim to accommodate every being blocked connection. Additionally, the notion of Path Connectivity is introduced as an evaluation value in the rerouting and reallocating resources phase. In detail, when reconfiguring the conflicting paths, the metric is decided by the variation in the evaluation value before and after the alternative is accommodated. An outline of MPC defragmentation algorithm is given hereafter:

**Step 1:** For each blocked connection request, find a candidate pair of route and consecutive slots set whose disruptions to the existing paths are minimized. If there are multiple candidates, choose the one having the smallest slot index on the selected route.

**Step 2:** Find all existing paths that conflict with the pair of route and slots set selected in Step 1. For each conflicting path, generate all available alternatives, which can be expressed by pairs of candidate routes and candidate slots set. Define these alternatives as ${r}_{i},\left\{{f}_{j}\right\}$.

**Step 3:** Before accommodating the conflicting traffic, calculate the Path Connectivity of all candidate routes ${r}_{i}$ . Record these results as initial value ${C}_{{r}_{i}}$.Then, Assuming that the candidate slots ${f}_{j}$ is allocated to the candidate route ${r}_{i}$, calculate the Path Connectivity of all candidate routes ${r}_{i}$. Record these results as ${C}_{{r}_{i}}^{{f}_{j}}$. The decrease in value, ${C}_{{r}_{i}}-{C}_{{r}_{i}}^{{f}_{j}}$, is calculated as the metric for every alternative pairs. The pair that yields the smallest metric is selected as alternative path to the original conflicting path.

**Step 4:** For each blocked connection request, if all conflicting paths have alternative paths, relocate the conflicting paths and then accommodate the new traffic. Otherwise block the connection request.

The flowchart of MPC algorithm is shown in Fig. 3 .

#### 3.2 Path Connectivity Triggering algorithm (PCT)

The proposed PCT algorithm adopts the Average Path Connectivity as the performance threshold parameter and triggers the spectral defragmentation when it degrades below the predefined value. The spectral defragmentation carries out by optimizing online connections in a certain order, until the network performance promotes back to the range of the threshold. An outline of PCT defragmentation algorithm is given hereafter:

**Step 1:** After connections release or new connections establish, update the Path Connectivity of all *M* online connections and calculate the Average Path Connectivity ${C}_{m}$: ${C}_{m}=\frac{1}{M}{\displaystyle \sum _{i=1}^{M}{C}_{i}}$ as the performance threshold parameter. Compare ${C}_{m}$ with the pre-defined value ${C}_{0}$; If ${C}_{m}\le {C}_{0}$, trigger the spectral defragmentation.

**Step 2:** Rank the *M* online connections in an ascending order based on its Path Connectivity. Define the connection sequence as $\left\{{T}_{1},{T}_{2},\mathrm{...},{T}_{j},\mathrm{...},{T}_{M}\right\}$; According to the definition of Path Connectivity, the paths of front connections in the sequence have a worse spectrum switching uniformity, thus leading to more spectrum fragments.

**Step 3:** According to the connection sequence$\left\{{T}_{1},{T}_{2},\mathrm{...},{T}_{j},\mathrm{...},{T}_{M}\right\}$, re-allocate the spectrum on the original route for each connection ${T}_{j}$. In detail, assuming that the candidate slots set ${f}_{i}$ is allocated to ${T}_{j}$ on the original route ${r}_{j}$, calculate the Path Connectivity of this candidate spectrum slot as ${C}_{{f}_{i}}$.Then, the candidate slots set who yields the biggest value of ${C}_{{f}_{i}}$ is chosen.

**Step 4:** After re-allocating the spectrum for all online connections, update the Path Connectivity of them and calculate the Average Path Connectivity ${C}_{m}$ again. Compare ${C}_{m}$ with the pre-defined value ${C}_{0}$; If ${C}_{m}>{C}_{0}$, the spectral defragmentation ends, else goes to step 2. In order to avoid endless defragmentation, when the defragmentation time *K* reaches the pre-defined maximum value ${K}_{max}$, the fragmentation terminates whatever the network performance is.

The flowchart of PCT algorithm is shown in Fig. 4 .

## 4. Simulation results and discussions

A simulation study is performed to evaluate the proposed MPC and PCT algorithms and compared them in terms of blocking probability and defragmentation profitability. The widely-used NSFNet (14 nodes, 21 links) and ARPA-2 (21 nodes, 24 links) networks are used as the simulation topology (as shown in Fig. 5 ), with the assumption that each fiber has 128 total spectrum slots and the bandwidth of each slot is 12.5 GHz. The traffic connection requests for each node pairs are distributed randomly over the network spatially and for temporal distribution, they follow as a Poisson process with an arrival rate $\lambda $ (call/s). The holding time of each call is exponentially distributed with mean value$\mu $. In the simulation, five types of connection line rates, which are 10Gbit/s, 40Gbit/s, 100Gbit/s, 400Gbit/s and 1Tbit/s, are generated with equal probability. Note the actual transmitting spectrum is dependent on various factors such as modulation type, network and hardware conditions. Here for simulation purpose, we neglect these influence and suppose that the required spectrums for each line rate are 25GHz, 50GHz, 50GHz, 75GHz [13], 150GHz [14] and the required FS numbers are 2, 4, 4, 6, 12 respectively.

In the simulation study, besides the proposed defragmentation algorithms, we consider spectrum compactness based defragmentation algorithm [10] for comparison purpose. Figure 6 compares the performance of two proposed algorithms to the compactness based algorithm in terms of blocking probability. As shown, all defragmentation algorithms (including MPC, PCT and compactness based algorithms) reduce the blocking probability significantly comparing to the algorithm without defragmentation. In addition, as the traffic load increases, the network performance improves more significantly. The reason for this is in case of high traffic scenario, blocking probability is more sensitive to the distributing spectrum fragments in the network. Aiming to glue spectral fragments together, both MPC and PCT algorithms influence the network performance more evidently. Another phenomenon can be seen that the proposed MPC and PCT algorithms outperform the compactness based algorithm. This is because compactness based algorithm optimizes the spectrum fragments only on the view of links, while MPC and PCT algorithms consider the correlations among the links by introducing the notion of Node Spectral-X Eigenvector.

Another phenomenon can be seen that when comparing the PCT algorithms with different thresholds, higher threshold leads to better performance. This is because with higher threshold, the spectrum defragmentation is more apt to be triggered and more difficult to be terminated. That is to say, PCT algorithms with higher thresholds result in more times of defragmentation, thus optimize spectrum resource better and yields lower blocking probability. Finally, it can be seen that PCT algorithm outperforms MPC algorithm in heavy traffic load scenario. The reason is that MPC algorithm reroutes online connections with a limited view to accommodate the being blocked connections while PCT algorithm defragments the global spectrum resource. In case of light traffic load, for the sufficient spectrum resource, the difference on blocking probability reduction between two algorithms is not obvious. However under heavy traffic load scenario, the difference gets bigger.

Figure 7 compares the performance of two proposed algorithms to the compactness based algorithm in terms of resource occupation rate, which reflects the percentage of occupied FS to the total spectrum resource. From Fig. 7 it can be observed that the resource occupation rate increases with the traffic load. Another result can be seen is in condition of the same traffic load, the proposed algorithms gain high value of resource occupation rate than the other algorithms. The reason for this is that with lower blocking probability, the proposed algorithms accommodate more connection requests, thus leads to higher resource occupation rate.

Then we compare the disruption numbers between these two proposed algorithms. The result in NSFNet is shown in Table 1 . Here parameter Time means the defragmentation times and parameter Sum means the disruption numbers to the on-line connections. It can be seen that MPC algorithm disrupts less of the existing connections than the PCT algorithm. The reason is that MPC algorithm searches for the candidate path for each blocked request with a disruption-minimized aim. On the other hand, PCT algorithm reallocates spectrum of all existed connections as much as possible when defragmentation is triggered.

Finally, in order to quantitatively describe the benefit of defragmentation, we define defragmentation profitability as the ratio of blocking probability reduction to the interruption percent. Figure 8 depicts the defragmentation profitability difference of these two algorithms. It can be observed that in light traffic load scenario, although the blocking probability reductions of both algorithms are almost the same, MPC gains higher defragmentation profitability with less disruptions. Meanwhile, in the heavy load condition, PCT is better with respect to defragmentation profitability for it reduce blocking probability better.

## 5. Conclusions

Flexible bandwidth optical network is receiving recent attentions as a spectrum-efficient architecture that can offer flexible and elastic bandwidth allocation. In this paper, aiming to dynamic spectrum defragmentation problem, two novel dynamic defragmentation algorithms are proposed based on the notion of Path Connectivity. Accordingly, we define a cost-performance-ratio based profitability model to denote the prons and cons of spectrum defragmentation. Simulation results show that compared to the non-defragmentation condition, both MPC and PCT defragmentation algorithms can better improve the performance of blocking probability. In case of light traffic load condition, MPC gains higher defragmentation profitability while in the heavy load condition, PCT is better in respect of defragmentation profitability.

## Acknowledgments

This work was supported in part by 863 program (2012AA011301), 973 program (2010CB328204), NSFC project (61271189, 61201154, 60932004), RFDP Project (2009 0005110013), 111 Project (B07005) and the Fundamental Research Funds for the Central Universities (2011RC0406).

## References and links

**1. **R.-J. Essiambre, G. Kramer, P. J. Winzer, G. J. Foschini, and B. Goebel, “Capacity limits of optical fiber networks,” J. Lightwave Technol. **28**(4), 662–701 (2010). [CrossRef]

**2. **M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka, “Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies,” IEEE Commun. Mag. **47**(11), 66–73 (2009). [CrossRef]

**3. **O. Rival and A. Morea, “Cost-efficiency of mixed 10-40-100Gb/s networks and elastic optical networks,” in *Proceedings of Optical Fiber Communication Conference and Exposition and National Fiber Optic Engineers Conference* (OFC/NFOEC 2011), paper OTuI4.

**4. **A. N. Patel, P. N. Ji, J. P. Jue, and Ting Wang, “Routing, wavelength assignment, and spectrum allocation in transparent flexible optical WDM (FWDM) networks,” in *Proceedings of Photonics in Switching* (PS 2010), paper PDPWG1.

**5. **T. Takagi, H. Hasegawa, K. Sato, Y. Sone, A. Hirano, and M. Jinno, “Disruption minimized spectrum defragmentation in elastic optical path networks that adopt distance adaptive modulation,” in *Proceedings of European Conference on Optical Communication* (ECOC 2011), paper Mo.2.K.3.

**6. **K. Wen, Y. Yin, D. J. Geisler, S. Chang, and S. J. B. Yoo, “Dynamic on-demand lightpath provisioning using spectral defragmentation in flexible bandwidth networks,” in Proceedings of European Conference on Optical Communication (ECOC 2011), paper Mo.2.K.4.

**7. **A. N. Patel, P. N. Ji, J. P. Jue, and Ting Wang, “Defragmentation of transparent flexible optical WDM (FWDM) networks,” in *Proceedings of Optical Fiber Communication Conference and Exposition and National Fiber Optic Engineers Conference* (OFC/NFOEC 2011), paper OTuI8.

**8. **N. Amaya, M. Irfan, G. Zervas, K. Banias, M. Garrich, I. Henning, D. Simeonidou, Y. R. Zhou, A. Lord, K. Smith, V. J. F. Rancano, S. Liu, P. Petropoulos, and D. J. Richardson, “Gridless optical networking field trial: flexible spectrum switching, defragmentation and transport of 10G/40G/100G/555G over 620-km field fiber,” in *Proceedings of European Conference on Optical Communication* (ECOC 2011), PDP paper Th.13.K.1.

**9. **F. Cugini, M. Secondini, N. Sambo, G. Bottari, G. Bruno, P. Iovanna, and P. Castoldi, “Push-pull technique for defragmentation in flexible optical networks,” in *Proceedings of Optical Fiber Communication Conference and Exposition and National Fiber Optic Engineers Conference* (OFC/NFOEC2012), paper JTh2A.40.

**10. **Yu. Xiaosong, J. Zhang, Y. Zhao, T. Peng, Y. Bai, D. Wang, and X. Lin, “Spectrum compactness based defragmentation in flexible bandwidth optical networks,” in

**11. **Y. wang, J. Zhang, Y. Zhao, J. Zhang, J. Zhao, X. Wang, and W. Gu, “Dynamic spectral defragmentation based on path connectivity in flexible bandwidth networks,” in *Proceedings of European Conference on Optical Communication* (ECOC 2012), paper P5.10.

**12. **Y. Sone, A. Hirano, A. Kadohata, M. Jinno, and O. Ishida, “Routing and spectrum assignment algorithm maximizes spectrum utilization in optical networks,” in *Proceedings of European Conference on Optical Communication* (ECOC 2011), paper Mo.1.K.3.

**13. **Y.-K. Huang, E. Ip, M. Huang, B. Zhu, P. N. Ji, Y. Shao, D. W. Peckham, R. Lingle, Y. Aono, T. Tajima, and T. Wang, “10X456-Gb/s DP-16QAM transmission over 8X100 km of ULAF using coherent detection with a 30-GHz analog-to-digital converter,” in *Proceedings of OptoElectronics Communication Conference* (OECC 2010), paper PD3.

**14. **S. Gringeri, B. Basch, V. Shukla, R. Egorov, and T. J. Xia, “Flexible architectures for optical transport nodes and networks,” IEEE Commun. Mag. **48**(7), 40–50 (2010). [CrossRef]