Vol 1 No 2 (2006)

Mathematical models of the delay constrained routing problem

Walid Ben-Ameur
GET/INT - CNRS/SAMOVAR, Institut National des Télécommunications
Adam Ouorou
France Télécom - Division R&D , CORE/MCN
Published June 30, 2006
  • routing problems in telecommunications,
  • convex programming,
  • delay
How to Cite
Ben-Ameur, W., & Ouorou, A. (2006). Mathematical models of the delay constrained routing problem. Algorithmic Operations Research, 1(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/669


Given a network with known link capacities and traffic demands, one can compute the paths to be used and the amount of traffic to be send through each path by solving a classical multi-flow problem. However, more quality of service constraints such as delay constraints, may be imposed and the routing problem becomes difficult to solve. We assume that the delay on each link depends on both its capacity and the total flow on it. We show that satisfying the delay constraints and the capacity constraints is an NP-complete problem. We give a convex relaxation of the delay constrained routing problem and present some ways to get upper and lower bounds on the problem.