Traffic engineering seeks to route traffic demands in data networks to guarantee certain quality of service (QoS) parameters while efficiently utilizing network resources. MPLS, for example, provides the essential capabilities to achieve this with explicit routing. Finding paths for all the demands which meet QoS requirements is a nontrivial task. Indeed, guaranteeing just bandwidth is known to be NP-hard. In this paper, we propose a new complete (exact) algorithm for solving this problem, which is a hybrid that tightly integrates Lagrangian optimization and Constraint Programming search. We evaluate its performance on a set of benchmark tests, based on a large well-provisioned commercial backbone. The tests involve demand sets of varying size, mostly between 100 and 600 demands. We compare the results with those achieved by several other well-known algorithms, some complete and some heuristic. This reveals that the hybrid algorithm typically yields the most informative results in the most effective way. It resolves most of the test cases either by finding a solution or by proving infeasibility, each taking only a few seconds. Moreover, the solutions found for solvable problems are provably near-optimal. The results show, perhaps surprisingly, that the routing task can be difficult even in a very well-provisioned network. (C) 2004 Wiley Periodicals, Inc.
