This paper deals with the performance of two algorithms for a continuous-time network routing problem. The authors consider a related continuous-time network model where calls have Poisson arrivals and exponential durations. Load-balancing and alternative routing strategies are deployed to assign bandwidth to arriving calls, under constraints imposed by network topology. Specifically they study two versions of the general dynamic alternative routing (GDAR) algorithm. The first-fit dynamic alternative routing (FDAR) algorithm is the version when the algorithm always chooses the first possible alternative route, if there is one. The balanced dynamic alternative routing (BDAR) is the version when the algorithm chooses an alternative route which minimizes the larger of the current loads on its two indirect links, if possible. Calls that do not find an available route are lost. In this context, the authors prove that with the BDAR algorithm the capacity required to ensure that most calls are routed successfully is much smaller than with the FDAR algorithm.

Recensione dell'articolo: (Luczak, Malwina J.; McDiarmid, Colin - "Balanced routing of random calls." - Ann. Appl. Probab. 25 (2015), no. 3, 1279–1324)

Leonardo Pasini
2015-01-01

Abstract

This paper deals with the performance of two algorithms for a continuous-time network routing problem. The authors consider a related continuous-time network model where calls have Poisson arrivals and exponential durations. Load-balancing and alternative routing strategies are deployed to assign bandwidth to arriving calls, under constraints imposed by network topology. Specifically they study two versions of the general dynamic alternative routing (GDAR) algorithm. The first-fit dynamic alternative routing (FDAR) algorithm is the version when the algorithm always chooses the first possible alternative route, if there is one. The balanced dynamic alternative routing (BDAR) is the version when the algorithm chooses an alternative route which minimizes the larger of the current loads on its two indirect links, if possible. Calls that do not find an available route are lost. In this context, the authors prove that with the BDAR algorithm the capacity required to ensure that most calls are routed successfully is much smaller than with the FDAR algorithm.
File in questo prodotto:
File Dimensione Formato  
PASINI MR3325274.pdf

solo gestori di archivio

Descrizione: Testo della recensione presente in MathSciNet
Tipologia: Altro materiale allegato
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 149.38 kB
Formato Adobe PDF
149.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11581/406137
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact