Delay Constrained Routing: the Multi-flow Single-Path Case

Delay Constrained Routing (DCR) is an optimization problem arising in computer networks with stringent Quality of Service (QoS) scheduling requirements. IP packets are subject to several types of delays when traversing the network; we consider the routing problem where the QoS requirement consists in guaranteeing a controlled flow-specific worst-case end-to-end delay of any packet of each given flow. Depending on the scheduling algorithm employed in the routers, worst-case delay formulæ can be devised of the bandwidth (a.k.a. reserved rate) allocated for the flow over each arc of its (unique) origin-destination path. The (single-path) multi-flow DCR problem can then be modelled as a multicommodity-type problem with nonlinear constraints depending on the reserved rate on the chosen arcs, and it is clearly a hard problem since it generalises the nonsplittable multicommodity flow one. Even the single-flow DCR problem is hard, since it generalises the constrained shortest path one, but it can be solved efficiently enough for realistic-sized instances thanks to previously developed modelling and algorithmic approaches. We show how to leverage the latter to construct a Lagrangian approach and explore the quality of the obtained information on a set of realistic DCR instances.