OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 20, Iss. 2 — Jan. 16, 2012
  • pp: 1798–1804
« Show journal navigation

Dynamic on-demand defragmentation in flexible bandwidth elastic optical networks

Yawei Yin, Ke Wen, David J. Geisler, Ruiting Liu, and S. J. B. Yoo  »View Author Affiliations


Optics Express, Vol. 20, Issue 2, pp. 1798-1804 (2012)
http://dx.doi.org/10.1364/OE.20.001798


View Full Text Article

Acrobat PDF (1436 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

While flexible bandwidth elastic optical networking is a promising direction for future networks, the spectral fragmentation problem in such a network inevitably raises the blocking probability and significantly degrades network performance. This paper addresses the spectral defragmentation problem using an auxiliary graph based approach, which transforms the problem into a matter of finding the maximum independent set (MIS) in the constructed auxiliary graph. The enabling technologies and defragmentation-capable node architectures, together with heuristic defragmentation algorithms are proposed and evaluated. Simulation results show that the proposed min-cost defragmentation algorithms can significantly reduce the blocking probability of incoming requests in a spectrally fragmented flexible bandwidth optical network, while substantially minimizing the number of disrupted connections.

© 2012 OSA

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

1. 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]

]. 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

1. 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]

,2

2. D. J. Geisler, R. Proietti, Y. Yin, R. P. Scott, X. Cai, N. K. Fontaine, L. Paraschis, O. Gerstel, and S. J. B. Yoo, “The First Testbed Demonstration of a Flexible Bandwidth Network with a Real-Time Adaptive Control Plane,” in ECOC 2011, 37th European Conference and Exhibition on Optical Communication(Geneva, Switzerland, 2011), p. Th.13.K.12.

]. 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

3. A. N. Patel, P. N. Ji, J. P. Jue, and W. Ting, “Defragmentation of transparent Flexible optical WDM (FWDM) networks,” in Optical Fiber Communication Conference 2011 (Los Angeles, CA, 2011), pp. 1–3.

].

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

3. A. N. Patel, P. N. Ji, J. P. Jue, and W. Ting, “Defragmentation of transparent Flexible optical WDM (FWDM) networks,” in Optical Fiber Communication Conference 2011 (Los Angeles, CA, 2011), pp. 1–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.

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.

Figure 2
Fig. 2 (a) constructing the auxiliary graph (b) finding the maximum independent set in the auxiliary graph.
shows an auxiliary graph constructed to find the one-to-one, non-overlap matching between the disrupted connections and the unused spectral blocks:

  • Step 1: Take one of the solutions (one of the available alternate blocks) for every existing connection as a vertex.
  • Step 2: Connect two vertices if they belong to the set of solutions of the same connection.
  • Step 3: Connect two vertices if they spectrally overlap with each other.

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(20.276n) ~O(3n/3) [5

5. T. A. Feo, M. G. C. Resende, and S. H. Smith, “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set,” Oper. Res. 42(5), 860–878 (1994). [CrossRef]

,6

6. M. Halldórsson and J. Radhakrishnan, “Greed is good: approximating independent sets in sparse and bounded-degree graphs,” in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing(1994), pp. 439–448.

], where n is the number of nodes in the graph. Exact algorithms can achieve a better complexity of O(20.0076n) [7

7. A. Sharieh and W. A. Rawagepfeh, “An algorithm for finding maximum independent set in a graph,” Eur. J. Sci. Res. 23, 586–596 (2008).

], while the parallel algorithms can achieve O((log n)4), but occupies O((n/log n)3) of memory spaces [8

8. R. M. Karp and A. Wigderson, “A fast parallel algorithm for the maximum independent set problem,” in Proceedings of the sixteenth annual ACM symposium on Theory of computing(1984).

]. For the simplicity of implementation, in our simulation we choose the algorithms in [7

7. A. Sharieh and W. A. Rawagepfeh, “An algorithm for finding maximum independent set in a graph,” Eur. J. Sci. Res. 23, 586–596 (2008).

] to find the MIS in the constructed auxiliary graph.

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

4. S. J. B. Yoo, “Wavelength conversion technologies for WDM network applications,” J. Lightwave Technol. 14(6), 955–966 (1996). [CrossRef]

]. 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
Fig. 3 (a) pre-switch defragmentation-capable node architecture (b) post-switch defragmentation-capable node architecture.
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.

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

9. D. J. Geisler, Y. Yin, K. Wen, N. K. Fontaine, R. P. Scott, S. Chang, and S. J. B. Yoo, IEEE, “Demonstration of Spectral Defragmentation in Flexible Bandwidth Optical Networking by FWM,” accepted for publication in IEEE Photonics Technology Letters (2011).

]. 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)
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.
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−3 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.

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)
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
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.

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.

Acknowledgments

This work was supported in part by NSF ECCS grant 1028729, and under the CISCO University Research Program.

References and links

1.

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]

2.

D. J. Geisler, R. Proietti, Y. Yin, R. P. Scott, X. Cai, N. K. Fontaine, L. Paraschis, O. Gerstel, and S. J. B. Yoo, “The First Testbed Demonstration of a Flexible Bandwidth Network with a Real-Time Adaptive Control Plane,” in ECOC 2011, 37th European Conference and Exhibition on Optical Communication(Geneva, Switzerland, 2011), p. Th.13.K.12.

3.

A. N. Patel, P. N. Ji, J. P. Jue, and W. Ting, “Defragmentation of transparent Flexible optical WDM (FWDM) networks,” in Optical Fiber Communication Conference 2011 (Los Angeles, CA, 2011), pp. 1–3.

4.

S. J. B. Yoo, “Wavelength conversion technologies for WDM network applications,” J. Lightwave Technol. 14(6), 955–966 (1996). [CrossRef]

5.

T. A. Feo, M. G. C. Resende, and S. H. Smith, “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set,” Oper. Res. 42(5), 860–878 (1994). [CrossRef]

6.

M. Halldórsson and J. Radhakrishnan, “Greed is good: approximating independent sets in sparse and bounded-degree graphs,” in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing(1994), pp. 439–448.

7.

A. Sharieh and W. A. Rawagepfeh, “An algorithm for finding maximum independent set in a graph,” Eur. J. Sci. Res. 23, 586–596 (2008).

8.

R. M. Karp and A. Wigderson, “A fast parallel algorithm for the maximum independent set problem,” in Proceedings of the sixteenth annual ACM symposium on Theory of computing(1984).

9.

D. J. Geisler, Y. Yin, K. Wen, N. K. Fontaine, R. P. Scott, S. Chang, and S. J. B. Yoo, IEEE, “Demonstration of Spectral Defragmentation in Flexible Bandwidth Optical Networking by FWM,” accepted for publication in IEEE Photonics Technology Letters (2011).

OCIS Codes
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4256) Fiber optics and optical communications : Networks, network optimization

ToC Category:
Backbone and Core Networks

History
Original Manuscript: October 10, 2011
Manuscript Accepted: November 1, 2011
Published: January 12, 2012

Virtual Issues
European Conference on Optical Communication 2011 (2011) Optics Express

Citation
Yawei Yin, Ke Wen, David J. Geisler, Ruiting Liu, and S. J. B. Yoo, "Dynamic on-demand defragmentation in flexible bandwidth elastic optical networks," Opt. Express 20, 1798-1804 (2012)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-20-2-1798


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. 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]
  2. D. J. Geisler, R. Proietti, Y. Yin, R. P. Scott, X. Cai, N. K. Fontaine, L. Paraschis, O. Gerstel, and S. J. B. Yoo, “The First Testbed Demonstration of a Flexible Bandwidth Network with a Real-Time Adaptive Control Plane,” in ECOC 2011, 37th European Conference and Exhibition on Optical Communication(Geneva, Switzerland, 2011), p. Th.13.K.12.
  3. A. N. Patel, P. N. Ji, J. P. Jue, and W. Ting, “Defragmentation of transparent Flexible optical WDM (FWDM) networks,” in Optical Fiber Communication Conference 2011 (Los Angeles, CA, 2011), pp. 1–3.
  4. S. J. B. Yoo, “Wavelength conversion technologies for WDM network applications,” J. Lightwave Technol.14(6), 955–966 (1996). [CrossRef]
  5. T. A. Feo, M. G. C. Resende, and S. H. Smith, “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set,” Oper. Res.42(5), 860–878 (1994). [CrossRef]
  6. M. Halldórsson and J. Radhakrishnan, “Greed is good: approximating independent sets in sparse and bounded-degree graphs,” in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing(1994), pp. 439–448.
  7. A. Sharieh and W. A. Rawagepfeh, “An algorithm for finding maximum independent set in a graph,” Eur. J. Sci. Res.23, 586–596 (2008).
  8. R. M. Karp and A. Wigderson, “A fast parallel algorithm for the maximum independent set problem,” in Proceedings of the sixteenth annual ACM symposium on Theory of computing(1984).
  9. D. J. Geisler, Y. Yin, K. Wen, N. K. Fontaine, R. P. Scott, S. Chang, and S. J. B. Yoo, IEEE, “Demonstration of Spectral Defragmentation in Flexible Bandwidth Optical Networking by FWM,” accepted for publication in IEEE Photonics Technology Letters (2011).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1 Fig. 2 Fig. 3
 
Fig. 4 Fig. 5
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited