The SONET ring is the most widely used optical network infrastructure today. While deploying the WDM/SONET ring, traffic grooming is an important network-design problem. SONET allows each wavelength to carry several lower-rate independent traffic channels in TDM fashion. For each logical connection that is established on one TDM time slot of a wavelength, traffic needs to be added and dropped only at the two end nodes of the connection. It is possible to have some nodes on some wavelength where no add/drop is needed on any time slot, thus resulting in savings of electronic equipment cost. By carefully arranging the connections on the network, the savings can be maximized. In the WDM/SONET ring, the equipment cost is predominantly high, so efficient traffic grooming can greatly reduce the network cost. In this paper, we first present a comprehensive mathematical definition of the problem, which turns out to be an integer linear program (ILP). Then, we propose a simulated-annealing-based heuristic algorithm for traffic grooming. A simple heuristic is also provided for the case where a hub node is used to bridge traffic from different wavelengths (called the multihop approach). We find the following main results. The simulated-annealing approach provides very good results in most cases. In general, multihop approaches can achieve better equipment savings when the grooming ratio is large but it consumes more bandwidth. Single-hop approaches will do better in all aspects when the grooming ratio is small. This paper focuses on nonuniform traffic and both unidirectional and bidirectional rings.
展开▼