2003/08/24 by Andrej Brodnik, Andreas Nilsson, Brodnik, Andrej +1
Business, Management and Accounting · Computer Science · Engineering · #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #C.2.3 #Data Structures and Algorithms (cs.DS) #E.1 #FOS: Computer and information sciences #Network Traffic and Congestion Control #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0308041
arxiv created 2003/08/24 · openalex publication_date 2003/08/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we present a discrete data structure for reservations of limited resources. A reservation is defined as a tuple consisting of the time interval of when the resource should be reserved, IR, and the amount of the resource that is reserved, BR, formally R=\IR,BR\. The data structure is similar to a segment tree. The maximum spanning interval of the data structure is fixed and defined in advance. The granularity and thereby the size of the intervals of the leaves is also defined in advance. The data structure is built only once. Neither nodes nor leaves are ever inserted, deleted or moved. Hence, the running time of the operations does not depend on the number of reservations previously made. The running time does not depend on the size of the interval of the reservation either. Let n be the number of leaves in the data structure. In the worst case, the number of touched (i.e. traversed) nodes is in any operation O(log n), hence the running time of any operation is also O(log n).