Traffic grooming in WDM SONET UPSR rings with multiple line speeds

We consider the traffic grooming problem in WDM/SONET UPSR 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 a novel integer linear programming (ILP) formulation for the problem. We also propose two techniques to exploit the symmetric problem structure resulting from the equivalency in the line speed assignments and the color assignments for wavelengths. The techniques reduce computation time, thus, allow many problem instances to be solved exactly. For large size problems, we propose efficient heuristic algorithms that achieve 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 show that allowing nodes to switch traffic can help to reduce the cost further.