Routing real-time traffic with maximum packet delay in contemporary telecommunication networks requires not only choosing a path, but also reserving transmission capacity along its arcs, as the delay is a nonlinear function of both components. The problem is known to be solvable in polynomial time under quite restrictive assumptions, i.e., Equal Rate Allocations (all arcs are reserved the same capacity) and identical reservation costs, whereas the general problem is NP-hard. We first extend the approaches to the ERA version to a pseudo-polynomial Dynamic Programming one for integer arc costs, and a FPTAS for the case of general arc costs. We then show that 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 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 fast and provides an 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 it is capable of solving realistic-sized instances with high accuracy at different levels of network load in a time compatible with real-time usage in an operating environment.

Delay-constrained shortest paths: approximation algorithms and second-order cone models

FRANGIONI, ANTONIO;GALLI, LAURA;SCUTELLA', MARIA GRAZIA
2015-01-01

Abstract

Routing real-time traffic with maximum packet delay in contemporary telecommunication networks requires not only choosing a path, but also reserving transmission capacity along its arcs, as the delay is a nonlinear function of both components. The problem is known to be solvable in polynomial time under quite restrictive assumptions, i.e., Equal Rate Allocations (all arcs are reserved the same capacity) and identical reservation costs, whereas the general problem is NP-hard. We first extend the approaches to the ERA version to a pseudo-polynomial Dynamic Programming one for integer arc costs, and a FPTAS for the case of general arc costs. We then show that 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 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 fast and provides an 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 it is capable of solving realistic-sized instances with high accuracy at different levels of network load in a time compatible with real-time usage in an operating environment.
2015
Frangioni, Antonio; Galli, Laura; Scutella', MARIA GRAZIA
File in questo prodotto:
File Dimensione Formato  
SOCP4SFSP.pdf

accesso aperto

Descrizione: Articolo Principale
Tipologia: Documento in Pre-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 264.37 kB
Formato Adobe PDF
264.37 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/486067
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 8
social impact