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

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

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

2009 (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]

2008 (1)

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

1996 (1)

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

1994 (1)

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]

Feo, T. A.

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]

Jinno, M.

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]

Kozicki, B.

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]

Matsuoka, S.

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]

Rawagepfeh, W. A.

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

Resende, M. G. C.

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]

Sharieh, A.

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

Smith, S. H.

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]

Sone, Y.

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]

Takara, H.

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]

Tsukishima, Y.

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]

Yoo, S. J. B.

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

Eur. J. Sci. Res. (1)

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

IEEE Commun. Mag. (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]

J. Lightwave Technol. (1)

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

Oper. Res. (1)

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]

Other (5)

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.

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.

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

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (5)

Fig. 1
Fig. 1

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

Fig. 2
Fig. 2

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

Fig. 3
Fig. 3

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

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

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

Tables (1)

Tables Icon

Table 1 Min-cost defragmentation algorithm

Metrics