Mathematical models of the delay constrained routing problem

Mathematical models of the delay constrained routing problem

0.00 Avg rating0 Votes
Article ID: iaor20071271
Country: Canada
Volume: 1
Issue: 2
Publication Date: Jul 2006
Journal: Algorithmic Operations Research
Authors: ,
Keywords: networks: flow
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 sent 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.

Reviews

Required fields are marked *. Your email address will not be published.