Laura Galli, University of Pisa
Quality-of-Service (Qos) routing of real-time traffic in contemporary telecommunication networks requires a guaranteed maximum packet delay. This, in turn, implies not only choosing a path but also reserving transmission capacity along its arcs, as the delay is a nonlinear function of both components. The general problem can be formulated as a mixed-integer Second-Order Cone program and thus solved with off-the-shelf technology. When the minimum reserved capacity is fixed, the Lagrangian problem, obtained by relaxing the maximum delay constraint, presents a special structure. We exploit this property to design an effective method to compute upper and lower bounds of very good quality in extremely short computing times.