Mathematical models of the delay constrained routing problem

Authors

  • Walid Ben-Ameur GET/INT - CNRS/SAMOVAR, Institut National des Télécommunications
  • Adam Ouorou France Télécom - Division R&D , CORE/MCN

Keywords:

routing problems in telecommunications, convex programming, delay

Abstract

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.

Downloads

Published

2006-06-30

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

Issue

Vol. 1 No. 2 (2006)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.