Approximation Algorithms for Many-to-Many Traffic Grooming in Optical WDM Networks

A large number of network applications today allow several users to interact together using the many-to-many service mode. In many-to-many communication, also referred to as group communication, a session consists of a group of users (we refer to them as members), where each member transmits its traffic to all other members in the same group. In this paper, we address the problem of grooming subwavelength many-to-many traffic (e.g., OC-3) into high-bandwidth wavelength channels (e.g., OC-192) in optical wavelength division multiplexing (WDM) mesh networks. The cost of an optical WDM network is dominated by the cost of higher-layer electronic ports (i.e., transceivers). A transceiver is needed for each initiation and termination of a lightpath. Therefore, our objective is to minimize the total number of lightpaths established. Unfortunately, the grooming problem even with unicast traffic has been shown to be NP-hard. In this paper, we introduce two novel approximation algorithms for the many-to-many traffic grooming problem. We also consider the routing and wavelength assignment problem with the objective of minimizing the number of wavelengths used. Through extensive experiments, we show that the proposed algorithms use a number of lightpaths that is very close to that of a derived lower bound. Also, we compare the two algorithms on other important objectives such as the number of logical hops traversed by a traffic stream, total amount of electronic switching at a node, and Min-Max objectives.