GarQ: An efficient scheduling data structure for advance reservations of grid resources

Abstract

In Grids, users may require assurance for completing their jobs on shared resources. Such guarantees can only be provided by reserving resources in advance. However, if many reservation requests arrive at a resource simultaneously, the overhead of providing such service due to adding, deleting and searching, will be significant. An efficient data structure for managing these reservations plays an important role in order to minimise the time required for searching available resources, adding and deleting reservations. In this paper, we present new approaches to advance reservation in order to deal with the limitations of the existing data structures, such as Segment Tree and Calendar Queue in..