Computer Science – Data Structures and Algorithms
Scientific paper
2003-08-24
Computer Science
Data Structures and Algorithms
Scientific paper
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, $I_R$, and the amount of the resource that is reserved, $B_R$, formally $R=\{I_R,B_R\}$. 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)$.
Brodnik Andrej
Nilsson Andreas
No associations
LandOfFree
Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Static Data Structure for Discrete Advance Bandwidth Reservations on the Internet will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-17295