Date Added: Dec 2010
In response to the high throughput needs of grid and cloud computing applications, several production networks have recently started to support advance reservation of dedicated circuits. An important open problem within this context is to devise advance reservation algorithms that can provide provable throughput performance guarantees, independently of the specific network topology and arrival pattern of reservation requests. In this paper, the authors first show that the throughput performance of greedy approaches, which return the earliest possible completion time for each incoming request, can be arbitrarily worse than optimal. Next, they introduce two new on-line, polynomial-time algorithms for advance reservation, called BatchAll and BatchLim.