Lagrangian approaches for QoS scheduling in computer networks

We study a routing problem arising in computer networks where stringent Quality of Service (QoS) scheduling requirements ask for a routing of the packets with controlled worst-case ``end-to-end'' delay. With widely used delay formulæ, this is a shortest-path-type problem with a nonlinear constraint depending in a complex way on the reserved rates on the chosen arcs. However, when the minimum reserved rate in the path is fixed, the Lagrangian problem obtained by relaxing the delay constraint presents a special structure and can be solved efficiently. We exploit this property and present an effective method that provides both upper and lower bounds of very good quality in extremely short computing times.