Grooming of non-uniform traffic on unidirectional and bidirectional rings

Traffic grooming in WDM networks is obtained by intelligently allocating the traffic onto a given set of wavelengths. This paper presents heuristics for grooming of non-uniform general traffic demands onto a given set of wavelengths available on a unidirectional or bidirectional ring. The objective is to minimize the number of higher layer equipment, like SONET Add/Drop Multiplexers (ADMs), or MPLS routers. We map the unidirectional ring onto a linear topology and develop a generalized two-step approach to solve the grooming problem on the mapped topology. In the first step, we allocate the traffic while minimizing the possible number of strings (each string being a collection of non-overlapping traffic streams) in a manner that yields the optimal number of strings in the linear topology case. We also prove the optimality of this step in the number of the strings (wavelengths). In the second step we employ a grouping technique to efficiently combine g strings onto a wavelength while minimizing the total number of the ADMs. We also address the problem of grooming the non-uniform traffic on a bidirectional ring by mapping it onto unidirectional rings, and applying the two-step approach. Moreover, in the case of bidirectional rings we propose an approach to route the traffic that reduces the total number of the required wavelengths and ADMs. The time complexity of our technique is at least an order of n less than other proposed approaches, where n is the total number of nodes in the network. The efficacy of the proposed technique has been demonstrated through a large number of experiments.