Abstract

A power law relationship is established between wavelength usage and algebraic connectivity of backbone wavelength division multiplexing networks. From this observation, a concise prediction formula linking wavelength consumption to network topologies is derived and evaluated for real-world wide area networks. It is shown that the algebraic-connectivity-based wavelength usage estimation is more precise than evaluations relying on node degree variance, number of spanning trees, and average internodal distance.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, 1992.
    [CrossRef]
  2. S. Baroni, P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol., vol 15, pp. 242–251, 1997.
    [CrossRef]
  3. C. Fenger, E. Limal, U. Gliese, C. J. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, vol. 1815of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2002, pp. 168–175.
    [CrossRef]
  4. D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.
  5. C. Rose, “Mean internodal distance in regular and random multihop networks,” IEEE Trans. Commun., vol. 40, pp. 1310–1318, 1992.
    [CrossRef]
  6. M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J., vol. 23, pp. 298–305, 1973.
  7. A. S. Rodionov, H. Choo, “On generating random network structures: connected graphs,” in Information Networking, vol. 3090of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2004, pp. 483–491
  8. M. Stoer, F. Wagner, “A simple min-cut algorithm,” J. ACM, vol. 44, pp. 585–591, 1997.
    [CrossRef]

1997 (2)

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol., vol 15, pp. 242–251, 1997.
[CrossRef]

M. Stoer, F. Wagner, “A simple min-cut algorithm,” J. ACM, vol. 44, pp. 585–591, 1997.
[CrossRef]

1992 (2)

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, 1992.
[CrossRef]

C. Rose, “Mean internodal distance in regular and random multihop networks,” IEEE Trans. Commun., vol. 40, pp. 1310–1318, 1992.
[CrossRef]

1973 (1)

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J., vol. 23, pp. 298–305, 1973.

Baroni, S.

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol., vol 15, pp. 242–251, 1997.
[CrossRef]

Bayvel, P.

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol., vol 15, pp. 242–251, 1997.
[CrossRef]

Bélanger, M. P.

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

Bernier, É.

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

Châtelain, B.

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

Chlamtac, I.

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, 1992.
[CrossRef]

Choo, H.

A. S. Rodionov, H. Choo, “On generating random network structures: connected graphs,” in Information Networking, vol. 3090of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2004, pp. 483–491

Fenger, C.

C. Fenger, E. Limal, U. Gliese, C. J. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, vol. 1815of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2002, pp. 168–175.
[CrossRef]

Fiedler, M.

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J., vol. 23, pp. 298–305, 1973.

Gagnon, F.

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

Ganz, A.

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, 1992.
[CrossRef]

Gliese, U.

C. Fenger, E. Limal, U. Gliese, C. J. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, vol. 1815of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2002, pp. 168–175.
[CrossRef]

Karmi, G.

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, 1992.
[CrossRef]

Limal, E.

C. Fenger, E. Limal, U. Gliese, C. J. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, vol. 1815of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2002, pp. 168–175.
[CrossRef]

Mahon, C. J.

C. Fenger, E. Limal, U. Gliese, C. J. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, vol. 1815of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2002, pp. 168–175.
[CrossRef]

O’Brien, D.

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

Rodionov, A. S.

A. S. Rodionov, H. Choo, “On generating random network structures: connected graphs,” in Information Networking, vol. 3090of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2004, pp. 483–491

Rose, C.

C. Rose, “Mean internodal distance in regular and random multihop networks,” IEEE Trans. Commun., vol. 40, pp. 1310–1318, 1992.
[CrossRef]

Stoer, M.

M. Stoer, F. Wagner, “A simple min-cut algorithm,” J. ACM, vol. 44, pp. 585–591, 1997.
[CrossRef]

Tremblay, C.

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

Wagner, F.

M. Stoer, F. Wagner, “A simple min-cut algorithm,” J. ACM, vol. 44, pp. 585–591, 1997.
[CrossRef]

Czech. Math. J. (1)

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J., vol. 23, pp. 298–305, 1973.

IEEE Trans. Commun. (2)

C. Rose, “Mean internodal distance in regular and random multihop networks,” IEEE Trans. Commun., vol. 40, pp. 1310–1318, 1992.
[CrossRef]

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WANs,” IEEE Trans. Commun., vol. 40, pp. 1171–1182, 1992.
[CrossRef]

J. ACM (1)

M. Stoer, F. Wagner, “A simple min-cut algorithm,” J. ACM, vol. 44, pp. 585–591, 1997.
[CrossRef]

J. Lightwave Technol. (1)

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrarily connected wavelength-routed optical networks,” J. Lightwave Technol., vol 15, pp. 242–251, 1997.
[CrossRef]

Other (3)

C. Fenger, E. Limal, U. Gliese, C. J. Mahon, “Statistical study of the correlation between topology and wavelength usage in optical networks with and without conversion,” in Networking 2000 Broadband Communications, High Performance Networking, and Performance of Communication Networks, vol. 1815of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2002, pp. 168–175.
[CrossRef]

D. O’Brien, B. Châtelain, F. Gagnon, C. Tremblay, M. P. Bélanger, É. Bernier, “A dual metaheuristic solution for the min-RWA problem,” in Optical Fiber Communication Conf. and Exposition and Nat. Fiber Optic Engineers Conf., OSA Technical Digest (CD), Washington, DC: Optical Society of America, 2008, paper JThA80.

A. S. Rodionov, H. Choo, “On generating random network structures: connected graphs,” in Information Networking, vol. 3090of Lecture Notes in Computer Science, Berlin, Germany: Springer, 2004, pp. 483–491

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 (3)

Fig. 1
Fig. 1

Average wavelength usage versus (a) node degree variance, (b) number of spanning trees, (c) mean internodal distance, and (d) algebraic connectivity.

Fig. 2
Fig. 2

Topological metrics behavior for 20 and 40 node networks with densities of 1.5, 2.0, and 2.5.

Fig. 3
Fig. 3

Average wavelength usage versus algebraic connectivity.

Tables (2)

Tables Icon

Table 1 WAN Network Connectivity, Density, Lower Bound, and Estimation of Wavelength Usage

Tables Icon

Table 2 Topological Metrics Estimation Error and Deviation

Equations (6)

Equations on this page are rendered with MathJax. Learn more.

N c = max i p ξ e i p , i = 1 , 2 , , m , p = 1 , 2 , , P .
N min = max All possible C k ( n k ) C ,
L i j = { deg ( v i ) if i = j 1 if v i is adjacent to v j , i j 0 otherwise } .
τ = det ( L ) .
β = 1 P i , j V i j W ( i , j ) ,
N estimated = μ 2 l × 10 a n 2 + b n + c ,