| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436824 | Theoretical Computer Science | 2007 | 8 Pages |
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.
