Competitive Analysis of Online Traffic Grooming in WDM Rings

Authors

Karyn Benson, Johns Hopkins University
Benjamin Birnbaum, University of Washington - Seattle Campus
Esteban Molina-Estolano '06, Harvey Mudd College
Ran Libeskind-Hadas, Harvey Mudd CollegeFollow

Student Co-author

HMC Undergraduate

Document Type

Article

Department

Computer Science (HMC)

Publication Date

2008

Abstract

This paper addresses the problem of traffic grooming in wavelength-division multiplexing (WDM) rings where connection requests arrive online. Each request specifies a pair of nodes that wish to communicate and also the desired bandwidth of this connection. If the request is to be satisfied, it must be allocated to one or more wavelengths with sufficient remaining capacity. We consider three distinct profit models specifying the profit associated with satisfying a connection request. We give results on offline and online algorithms for each of the three profit models. We use the paradigm of competitive analysis to theoretically analyze the quality of our online algorithms. Finally, experimental results are given to provide insight into the performance of these algorithms in practice.

Rights Information

© 2008 Institute of Electrical and Electronics Engineers

DOI

10.1109/TNET.2007.901065

Recommended Citation

K. Benson, B. Birnbaum, E. Estolano-Molina, and R. Libeskind-Hadas, “Competitive Analysis of Online Traffic Grooming in WDM Rings,” IEEE/ACM Transactions on Networking, Vol. 16, No. 4, August 2008, pp. 984-997. DOI: 10.1109/TNET.2007.901065