Delay-Constrained Shortest Paths: Approximation Algorithms and Second-Order Cone Models

  Real-time traffic with stringent Quality of Service requirements is becoming more and more prevalent in contemporary telecommunication networks. When maximum packet delay has to be considered, optimal delay-constrained routing requires not only choosing a path, but also reserving resources (transmission capacity) along its arcs, as the delay is a nonlinear function of both kinds of components. So far only simple versions of the problem have been considered in the literature where all arcs are reserved the same capacity (this is referred to as ERA, i.e., Equal Rate Allocations) and have the same capacity reservation cost, because in such a restricted case polynomial time exact algorithms can be devised, whereas the general problem is $\Mcnp$-hard. We first extend the polynomial-time approaches for the ERA version of the problem with unit arc costs by deriving a pseudo-polynomial time algorithm for the integer arc costs case and a FPTAS for the general arc costs case. We then show that, under the main latency models proposed in the literature, the general problem can be formulated as a mixed-integer Second-Order Cone (SOCP) program, and therefore solved with off-the-shelf technology. We compare two formulations: one based on standard big-M constraints, and an improved one where Perspective Reformulation techniques are used to tighten the continuous relaxation. Extensive computational experiments on both real-world networks and randomly-generated realistic ones show that the ERA approach is extremely fast and provides a surprisingly effective heuristic for the general problem whenever it manages to find a solution at all, but it fails for a significant fraction of the instances that the SOCP models can solve. We therefore propose a three-pronged approach that combines the fast running time of the ERA algorithm and the effectiveness of the SOCP models, and show that the combined approach is capable of solving realistic-sized instances at different levels of network load in a time compatible with real-time usage in an operating environment.