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.

Lagrangian approaches for QoS scheduling in computer networks

A. Frangioni;L. Galli
;
E. Sorbera
2024-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/1231487
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact