In an online server routing problem, a vehicle or server moves in a network in order to process incoming requests at the nodes. Online server routing problems have been thoroughly studied using competitive analysis. We propose a new model for online server routing, based on adversarial queueing theory. The model addresses questions such as whether a server routing algorithm is stable, that is, whether it is such that the number of unserved requests in the system remains bounded at all times, assuming a bound on the global rate of requests arrival. This captures a notion of throughput for which competitive analysis typically does not give any useful result. In this framework, we consider a number of natural algorithms and we analyze their stability and performance. © 2007 Elsevier Ltd. All rights reserved.

Bonifaci, V. (2007). An adversarial queueing model for online server routing. THEORETICAL COMPUTER SCIENCE, 381(1-3), 280-287 [10.1016/j.tcs.2007.05.034].

An adversarial queueing model for online server routing

Bonifaci V.
2007

Abstract

In an online server routing problem, a vehicle or server moves in a network in order to process incoming requests at the nodes. Online server routing problems have been thoroughly studied using competitive analysis. We propose a new model for online server routing, based on adversarial queueing theory. The model addresses questions such as whether a server routing algorithm is stable, that is, whether it is such that the number of unserved requests in the system remains bounded at all times, assuming a bound on the global rate of requests arrival. This captures a notion of throughput for which competitive analysis typically does not give any useful result. In this framework, we consider a number of natural algorithms and we analyze their stability and performance. © 2007 Elsevier Ltd. All rights reserved.
Bonifaci, V. (2007). An adversarial queueing model for online server routing. THEORETICAL COMPUTER SCIENCE, 381(1-3), 280-287 [10.1016/j.tcs.2007.05.034].
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: http://hdl.handle.net/11590/379870
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact