Complexity of path traffic grooming

Feature Issue on Transmission in Optically Transparent Core NetworksThe problem of efficiently designing lightpaths and routing traffic on them in hybrid electro-optic data communication networks so that optical pass-through is maximized and the electronic switching cost is minimized is known as traffic grooming and has been studied extensively. Traffic grooming is known to be an inherently difficult problem. It has been shown to be NP-complete even for path networks, a simple topology in which lightpath wavelength assignment is tractable. In this paper, we explore the borderline between tractability and intractability by considering grooming in unidirectional path networks in which all traffic requests are destined for a single egress node. Whether the complete grooming problem is NP-hard with this restriction is an open question. We show that at least the problem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial on the egress model. We also show that in the egress model, if the capacity constraint is relaxed, the entire problem becomes polynomial. If, in addition, traffic requests are uniform, we provide an explicit combinatorial formula for the optimum solution as well as an algorithm that constructs a routing that achieves this optimum. For the case of finite capacity and unit traffic requests, we show how to polynomially find a feasible solution that is optimal under reasonable assumptions.