Traffic grooming in WDM SONET rings with multiple line speeds

We consider the traffic grooming problem in WDM/SONET rings with multiple line speeds. This is motivated by the fact that when traffic demands are non-uniform and are spread over a relatively wide range, a ring using multiple line speeds would lead to a lower cost, owing to the economy of scale seen in devices, in particular, electronic ADMs, running at higher speeds. We give novel integer linear programming (ILP) formulations for the problem. We also propose techniques that exploit the problem structure and, thereby, reduce the computation time. As a result, many problem instances can be solved exactly. For large size problems, we propose an efficient heuristic algorithm that achieves a similar cost using a fraction of the computation time. We show that, by allowing WDM/SONET rings to run at different line speeds, we can greatly reduce the ADM cost. We also study the cost benefits of traffic switching, compare UPSR and BLSR, and study the trade-offs of shortest path routing in BLSR