1. Introduction

Flexible bandwidth elastic optical networks were recently proposed to achieve spectrally efficient and adaptive networking with agile granularities of spectrum allocation beyond the rigid ITU-T spectrum grid (G.649.1) [1]. The networks have the potential of provisioning both super-wavelength and sub-wavelength channels with arbitrary channel bandwidth and modulation formats. The flexible bandwidth optical networks offer higher spectral efficiency achieved by overlapping orthogonal spectrum subcarriers or coherent optical comb lines [1,2]. However, this new capability in the wavelength domain leads to an additional spectral contiguous constraint, which means that when assigning the spectral resources to single connections, whether super-wavelength connections or sub-wavelength connections, the resources assigned to them must be contiguous over the entire blocks in the spectrum domain. Careful routing and spectrum assignment (RSA) algorithms are necessary in such networks to avoid fragmentations of spectral resources into small noncontiguous spectral bands on fiber links. However, in dynamic traffic scenario, the channel setup and tear down processes lead to such fragmentation as well [3].

Spectral fragments, which are typically embodied by non-aligned stranded bandwidths, inevitably lead to spectral underutilization and potential high blocking probability in flexible bandwidth optical networks. This results from the fact that they are neither contiguous on the spectrum axis nor continuous in the fiber link direction, making themselves hard to be utilized by future connection requests, especially for those with multi-hop and/or large bandwidth demands. Network operators are under the demand to optimize or maximize the service capacity within the limited spectral resources, which in turn leads to the need to dynamically or periodically reconfigure the network to accommodate new incoming traffic. This network resource optimization also includes network defragmentation. In addition to reducing blocking probability by consolidating the available network resources, this operation will also enable better network maintenance and enhance quality of service for a given spectral capacity. However, when the network is reconfigured due to defragmentation, it is possible that existing connections may be disrupted. A major challenge for network defragmentation is to minimize these disruptions and to possibly achieve hitless optimization.

This paper addresses the spectral defragmentation problem using an auxiliary graph based approach. Further, this paper will introduce enabling technologies and node architectures for defragmentation, and will propose and evaluate the corresponding heuristic algorithms. The remainder of this paper has the following organization: Section 2 defines the spectral defragmentation problem and addresses it using an auxiliary graph based approach. Section 3 talks about the enabling technologies for defragmentation, and proposes two scalable node architectures with variable degrees of defragmentation capabilities. Section 4 presents a proof-of-principle experimental demonstration showing the feasibility of implementing a flexible bandwidth wavelength cross connect (FB-WXC) with spectral defragmentation capabilities. Section 5 discusses the simulation results showing the reduced blocking probabilities due to defragmentation and the minimized disruptions to the existing connections. Section 6 concludes this paper.

2. The defragmentation problem in flexible bandwidth elastic optical networks

In a flexible bandwidth elastic optical network, the first step to spectral defragmentation is to reconfigure the network so that the spectral fragments can be consolidated into contiguous blocks. The reconfigurations for defragmentation can be done either periodically or on-demand in a dynamic fashion. Periodical defragmentation usually operates with the goal of confining the spectral usage to one side of the spectrum, and requires the entire network to be considered for defragmentation simultaneously [3]. On the contrary, dynamic on-demand defragmentation can be adaptively tailored to the specific demand of the important and urgent incoming connections. With either approach, the existing connections need to be reconfigured either by changing routes, assigning different spectrum at the transceivers, or converting wavelength in the intermediate nodes. In any case, there is a chance that some existing live connections may be disrupted. One of the key operational requirements is to minimize the number of disruptions during the reconfiguration phase.

This paper considers primarily the wavelength conversion technique in the intermediate nodes for the dynamic on-demand defragmentation scenario. In this case, to make room for the incoming connections with large bandwidth demands, the existing connections that are in spectral conflict with the new connection requests will be wavelength converted to other available, but fragmented spectrum blocks on the same link.

Taking one example of 4 links in the 14-node NSF network, as shown in Fig. 1(a) , the current state of the spectrum usage are assumed as shown in Fig. 1(b). When a new connection going through link 1, 2, 3 and 4 requests three contiguous subcarriers, there is no contiguous spectrum blocks (while blocks) available on all the links. Assuming the algorithms in the network control plane firstly choose the spectrum interval of [fs, fs + W] (i.e. the block surrounded by the yellow rectangle) as a starting point to evaluate defragmentation. There are three existing connections in this spectral interval, namely C1, C2 and C3. To do defragmentation is to convert these three connections in the wavelength domain to make this spectral interval available to the new connection. Since these three connections are all relatively small connections (short distance and narrow spectrum), there is more chance that they can take advantage of the fragmented spectral resources on the links.

 

Fig. 1 (a) 14-node NSF network (b) example defragmentation scenario.

Download Full Size | PDF

Obviously, there are two alternative spectrum blocks to accommodate each individual connection in this example. As shown in Fig. 1(b), the two blue dash circles above the yellow frame represent C1 solution 1 and C1 solution 2. Similarly, C2 and C3 have two solutions as well. However, as Fig. 1(b) indicates, one connection cannot randomly choose a spectral block to accommodate itself since some of the blocks overlap with each other. Such conflicts should be considered in the control plane when reconfiguring the existing connections to avoid interferences between two channels. Therefore, to defragment the network means to find a one-to-one, non-overlap matching between the disrupted connections and the available but fragmented spectrum resources.

Note that the converted connections may traverse to other links out of the route in the network before they reaches their destination. For instance, assume C1 comes from Champaign, IL and goes to Atlanta, GA. The wavelengths of C1 need to be converted away on node A, and then converted back at node D. There are two reasons of doing this. Firstly, in such way the wavelength conversion based reconfiguration of the network is restricted only on the pre-computed route for the new connection, therefore the chain effect of reconfiguring the entire network will be avoided. Secondly, the wavelength conversion happens only on the intermediate nodes, so the transceivers will not be affected by this reconfiguration other than at the instant of reconfiguring wavelength conversion. So the network will not be hit other than experiencing disruption due to the wavelength conversion reconfiguration, which can be very fast (in nanoseconds) [4]. In this initial study, the physical layer impairments of wavelength conversion will not be considered.

Figure 2 shows an auxiliary graph constructed to find the one-to-one, non-overlap matching between the disrupted connections and the unused spectral blocks:

 

Fig. 2 (a) constructing the auxiliary graph (b) finding the maximum independent set in the auxiliary graph.

Download Full Size | PDF

As Fig. 2(a) indicates, the example auxiliary graph consists of six vertices and seven edges. Each vertex corresponds to one of the solutions for each connection. The horizontal lines between two vertices means they are dependent on each other because of the same solution set they belongs to. The vertical lines between two vertices means they are dependent on each other because they overlap spectrally.

Therefore, the relationship between two solutions of the connections is transformed into dependencies between two vertices in the auxiliary graph. Finding the one-to-one, non-overlap mapping between the connections and the solutions becomes finding the maximum independent set (MIS) in the auxiliary graph. After a MIS is found, if the cardinality of the MIS equals to the number of disrupted connections, then one solution to do defragmentation is found. As shown in Fig. 2(b), C1 solution 2, C2 solution 1 and C3 solution 1 consist of one MIS, and the cardinality of this set is three, which equals the number of disrupted connections in the spectral interval. There may be more than one MIS in the graph, which correspond to more than one solutions of the problem (e.g. the dashed circle named as MIS2 in Fig. 2(b)). However, if the cardinality of the MIS is smaller than the number of disrupted connections, then there will be no solution in this spectral interval.

Dynamic on-demand defragmentation requires the algorithms to be efficient in terms of time complexity. Finding the MIS in a graph is known as a NP-complete problem. There are a lot of algorithms proposed in literature for this problem. Heuristic algorithms can achieve the time complexity of O(2^0.276n) ~O(3^n/3) [5,6], where n is the number of nodes in the graph. Exact algorithms can achieve a better complexity of O(2^0.0076n) [7], while the parallel algorithms can achieve O((log n)⁴), but occupies O((n/log n)³) of memory spaces [8]. For the simplicity of implementation, in our simulation we choose the algorithms in [7] to find the MIS in the constructed auxiliary graph.

We propose two heuristic algorithms taking advantage of the auxiliary graph approach to address the dynamic defragmentation problem, namely the first-fit algorithm and the min-cost algorithm. Both of the algorithms start after the route of the incoming request is computed and there are only fragmented resources available to accommodate the traffic. The algorithms are described as follows (Table 1 ):

Table 1. Min-cost defragmentation algorithm

View Table

The first-fit algorithm is the same as the min-cost algorithm unless it stops after the first spectral interval with at least one solution is found.

3. Enabling technologies and node architectures

There are several wavelength conversion technologies that can be used to implement spectral defragmentation. The three main categories of wavelength conversion are: optoelectronic based conversion, optical gating based conversion and wave-mixing based conversion [4]. Wave-mixing based techniques, such as four wave mixing (FWM) and difference frequency generation (DFG), are capable of converting coherent (amplitude/phase) information for multi-channels simultaneously and operating over THz bandwidth. These are all important characteristics for the flexible bandwidth optical networks. Section 4 demonstrates FWM based wavelength conversion technology in particular as the means for performing the broadband wavelength conversion necessary for spectral defragmentation operations in flexible bandwidth optical networks.

A major challenge for spectral defragmentation is the implementation of wavelength conversions in a scalable fashion. As Fig. 3 indicates, network nodes equipped with FWM elements and wavelength selective switches (WSS) support spectral defragmentation functionality. With M parallel FWM convertors on a link, the node has the capability to convert M connections’ spectra simultaneously, namely the node has the defragmentation degree of M. Spectral defragmentation can be performed in either a pre-switch (Fig. 3(a)) or a post-switch (Fig. 3(b)) fashion. The pre-switch architecture requires spectrum non-overlapping on both the output link and the fiber between the M × 1 WSS and the N × N WSS. In the post-switch architecture, if a new request requires spectral defragmentation, it is routed to the lower port of the corresponding output link while the defragmentation is performed on the upper link. Since the non-overlapping constraints only need to be satisfied on the output link during the defragmentation process, the post-switch architecture provides more flexibility for spectrum rearrangements. However, this flexibility requires an N × 2N WSS as well as a sufficient number of FWM elements on a single link in order to perform multiple conversions simultaneously, while in the pre-switch architecture these operations are distributed to multiple input links.

 

Fig. 3 (a) pre-switch defragmentation-capable node architecture (b) post-switch defragmentation-capable node architecture.

Download Full Size | PDF

4. Proof-of-principle experimental demonstration

A recent experimental demonstration has shown the feasibility of implementing a flexible bandwidth wavelength cross connect (FB-WXC) with a spectral defragmentation degree of one [9]. The demonstration consists of performing spectral defragmentation over 500 GHz by spectrally shifting a 200 GHz channel by 200 GHz. Here, spectral defragmentation was implemented using four-wave mixing (FWM). Figure 4(a) shows the spectrum before spectral defragmentation, which consists of two 200 GHz, A and B. The spectrum after spectral defragmentation (Fig. 4(b)) shows that B has been shifted −200 GHz to form B′. Spectrally shifting B enabled the addition of channel C without causing any blocked channels. Figure 4(c) details the 2 pump FWM process to achieve non-inverting wavelength conversion, which also involves wavelength selective switches (WSS’s) to remove unwanted spectral artifacts. Figure 4(d) shows bit-error rate (BER) results for B, B′, and C, which indicate successful wavelength conversion. The slight power penalty for the Even vs. Odd channels results from slightly uneven power levels entering the FWM process. Nonetheless, all channels achieved a BER less than the forward error correct (FEC) limit of 10⁻³ for each measured subcarrier. Scaling this technique to larger spectral defragmentation degree will enable greater flexibility and further reduce blocking probability for new incoming connections.

 

Fig. 4 (a) Spectra showing A and B before spectral defragmentation. (b) Spectra of A and B′ after defragmentation with the addition of C. (c) Details of the FWM based wavelength conversion process. (d) BER performance of both even and odd channels for B, B′, and C.

Download Full Size | PDF

5. Numerical results

We evaluate the performance of spectral defragmentation and the two algorithms in terms of blocking probability in a dynamic traffic scenario. The 14-node NSFNET (Fig. 1(a)) was used as the simulation topology, with the assumption that each fiber has 5 THz total spectrum and the bandwidth of each subcarrier is 12.5 GHz. The required bandwidth for connections is uniformly distributed from the smallest granularity (12.5 GHz) to 500 GHz. New connection requests arrive according to a Poisson process at a rate of λ, and their holding time conforms to a negative exponential distribution with parameter µ. The average holding time h, which equals 1/µ, is 730 time units in the simulation. The load of the network is measured by “offered load”, which is the product of λ and h. From the results, the blocking probability is greatly reduced by spectral defragmentation. In particular, the pre-switch architecture results in a 50% reduction in the blocking probability with only one FWM element for one link. Increasing to four FWM elements, the blocking probability remains low (0.07) even with high network load (λ = 0.9). The difference of blocking probability reduction between pre-switch architectures and pos-switch architectures comes from the fact that the post-switch architecture requires a sufficient number of FWM elements on a single output link in the case of multiple conversions are required simultaneously, while in the pre-switch architecture these operation requirements are distributed to multiple input links.

Figure 5(c) show the comparison of number of disruptions between two algorithms. As expected, the min-cost search achieves smaller number of disruptions since it tries to find the optimal spectral intervals to insert the new connection, while the first-fit algorithm stops when the first solution was found. Note that both min-cost and first-fit algorithms achieves the same amount of blocking probability reduction, since only one solution is needed for doing one defragmentation operation, whether or not the solution is optimized in terms of disruption.

 

Fig. 5 (a) Blocking probability using pre-switch architecture (b) blocking probability using post-switch architecture (c) number of disruptions to the existing connections in the network

Download Full Size | PDF

6. Conclusion

This paper addressed the defragmentation problem in the flexible bandwidth optical networks using an auxiliary graph based approach, and successfully transformed the problem into a a matter of finding the maximum independent set (MIS) in the graph. By taking advantage of an exact algorithm solving the MIS problem, this paper proposes a min-cost and a fist-fit spectral defragmentation algorithm together with two scalable WXC architectures to enable on-demand defragmentation. Our simulation results demonstrate significant reductions in blocking probabilities enabled by spectral defragmentation with minimized number of disruptions to the current network.