## Dynamic on-demand defragmentation in flexible bandwidth elastic optical networks |

Optics Express, Vol. 20, Issue 2, pp. 1798-1804 (2012)

http://dx.doi.org/10.1364/OE.20.001798

Acrobat PDF (1436 KB)

### 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

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]

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.

## 2. The defragmentation problem in flexible bandwidth elastic optical networks

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

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

**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

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

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

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

*) ~O(3*

^{0.276n}

^{n}^{/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]

*n*is the number of nodes in the graph. Exact algorithms can achieve a better complexity of O(2

*) [7], while the parallel algorithms can achieve O((log n)*

^{0.0076n}*), but occupies O((n/log n)*

^{4}*) 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.*

^{3}## 3. Enabling technologies and node architectures

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

*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*× 2

*N*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**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

*λ*, 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.

## 6. Conclusion

## Acknowledgments

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

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 |

3. | A. N. Patel, P. N. Ji, J. P. Jue, and W. Ting, “Defragmentation of transparent Flexible optical WDM (FWDM) networks,” in |

4. | S. J. B. Yoo, “Wavelength conversion technologies for WDM network applications,” J. Lightwave Technol. |

5. | T. A. Feo, M. G. C. Resende, and S. H. Smith, “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set,” Oper. Res. |

6. | M. Halldórsson and J. Radhakrishnan, “Greed is good: approximating independent sets in sparse and bounded-degree graphs,” in |

7. | A. Sharieh and W. A. Rawagepfeh, “An algorithm for finding maximum independent set in a graph,” Eur. J. Sci. Res. |

8. | R. M. Karp and A. Wigderson, “A fast parallel algorithm for the maximum independent set problem,” in |

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: Year | Journal | Reset

### References

- 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]
- 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.
- 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.
- S. J. B. Yoo, “Wavelength conversion technologies for WDM network applications,” J. Lightwave Technol.14(6), 955–966 (1996). [CrossRef]
- 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]
- 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.
- A. Sharieh and W. A. Rawagepfeh, “An algorithm for finding maximum independent set in a graph,” Eur. J. Sci. Res.23, 586–596 (2008).
- 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).
- 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.

« Previous Article | Next Article »

OSA is a member of CrossRef.