On optimal traffic grooming in elemental network topologies

Rudra Dutta; Shu Huang; George N. Rouskas

doi:10.1117/12.533162

1 October 2003 On optimal traffic grooming in elemental network topologies

Rudra Dutta, Shu Huang, George N. Rouskas

Proceedings Volume 5285, OptiComm 2003: Optical Networking and Communications; (2003) https://doi.org/10.1117/12.533162
Event: OptiComm 2003: Optical Networking and Communications, 2003, Dallas, TX, United States

Abstract

We consider the problem of traffic grooming in WDM path, star, and tree networks. Traffic grooming is a variant of the well-known logical topology design problem, and is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. Our contribution is two-fold. In the first part of the paper we settle the complexity of traffic grooming in path and star networks by proving that a number of variants of the problem are computationally hard. Since routing and wavelength assignment in these two topologies is trivial, these results demonstrate that traffic grooming is itself an inherently difficult problem. Our results have implications for ring and other more general topologies, which we explore. In the second part, we design practical grooming algorithms with provable properties. Specifically, for all three topologies, we obtain a series of lower and upper bounds which are increasingly tighter but have considerably higher computational requirements; the series of upper bounds form an algorithm for the traffic grooming problem with strong performance guarantees. We also present corresponding heuristics with good performance. Our work is a first step towards a formal and systematic approach to the grooming problem in general topologies that builds upon results and algorithms for more elementary networks.

Citation Download Citation

Rudra Dutta, Shu Huang, and George N. Rouskas "On optimal traffic grooming in elemental network topologies", Proc. SPIE 5285, OptiComm 2003: Optical Networking and Communications, (1 October 2003); https://doi.org/10.1117/12.533162

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available