EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

93. A combined Lagrange-Benders approach to Delay Constrained Routing

Invited abstract in session TB-4: Topics in Mixed Integer Nonlinear Programming 1, stream MINLP.

Tuesday, 10:30-12:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Antonio Frangioni
Dipartimento di Informatica, Universita' di Pisa
2. Laura Galli
Mathematics, Alma Mater Studiorum Università di Bologna
3. Enrico Sorbera
Dipartimento di Matematica, Università di Pisa

Abstract

Modern computer networks are required, on one hand, to support high bandwidth applications, on the other hand, to have stringent Quality of Service (QoS) guarantees. This is a relevant practical issue, since many applications over IP networks require QoS in terms of real-time guarantees, that is, controlled end-to-end delay. This implies that Internet Service Providers are required to negotiate delay bound within their Service Level Agreements, which in turn requires appropriate traffic engineering support.
From a mathematical point of view, this problem, known as Delay Constrained Routing (DCR), can be formulated as a Mixed-Integer Nonlinear Program, where one needs to simultaneously compute paths and reserve resources along the paths of the network, since the maximum delay of a flow depends (in a non-linear way) on both.
Even in the single-flow case, DCR is significantly more difficult than classical shortest path routing problems. Yet, DCR presents an interesting mixture of combinatorial and continuous structures and naturally lends itself to decomposition methods. We propose a combined Lagrange-Benders approach that provides both upper and lower bounds of very good quality in extremely short computing times.

Keywords

Status: accepted

Back to the list of papers