direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Publications of KBS

Analysis of Data Structures for Admission Control of Advance Reservation Requests
Citation key Bur04c
Author Lars-Olof Burchard
Year 2004
Number KBS 2004/1
Institution Communication and Operating Systems Group, TU Berlin
Abstract Advance reservations are a useful method to allocate resources of various kinds in many different environments. Among others, a major advantage of this kind of reservations is the improved admission probability for requests that are made sufficiently early. Applications can be found in many different environments, e.g., the field of grid computing which allows to co-allocate compute resources in different locations connected over the Internet. For that purpose, co-allocations in advance of resources, such as compute nodes or network bandwidth, are important to guarantee the correct functionality of the whole system, e.g., that a certain job is completed up to given deadline. In order to implement reliable admission control in those cases, it is important to store information about future allocations and to provide fast access to the available information. It will be shown that data structures for that purpose demand for the largest portion of the overall admission processing time and therefore are required to be fast to access and also memory efficient. In this paper, two data structures are examined. One of them is a tree specially designed to support advance reservations which is compared to arrays. Both structures are examined both analytically and by measurements in a realistic network management system. It turns out that arrays are far better suited to support the required operations, in particular when large time intervals need to be scanned.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe