Information Technology Reference
In-Depth Information
3
Related Work
Data structures in advance reservations are divided into two categories: slotted data
structures and non-slotted data structures. Their inherent characters will be introduced
in detail later.
3.1
Slotted Data Structures
Generally, a slot is the smallest time unit for the allocation of resources and each
timeslot represents a fixed length of time such as one second, one minute, one hour,
or even one day. There are two typical slotted data structures—the timeslot array [4]
and the segment tree [5]. The comparison results show that the timeslot array is better
than the segment tree in the consumption of time and storage space. An example of a
timeslot array is showed in figure 2.
Fig. 2.
A timeslot array
In figure 2, each array element represents a timeslot and its value represents the
amount of allocated resources. The timeslot array must have an appropriate length
(LEN) which should not be exceeded by the time bound of reservation requests and
save storage space at the same time. A balance between these two points must be
built.
The admission control of the timeslot array is very simple. For any arriving reserva-
tion request—
req
(
bw
,
ts
,
te
), it only needs to modify the value of each array element
between the start time(
ts
) and the end time(
te
) (A[i] = A[i] +
bw
). There are still many
drawbacks in the timeslot array: (1) if a reservation request covers a long period of
time, a large number of array elements must be used to store the reserved information
with the result of wasting a lot of memory; (2) each array element represents a fixed
time period rather than an arbitrary time value, so the precision does not depend on
actual demand but on the size of a timeslot. (3) All the elements in the array will still
be overlapped over time because of the fixed size of the array. We can partially solve
this problem through using a ring buffer and marking the current timeslot, which en-
sures that the time bound of a reservation requestwill not exceed LEN.
Mugurel et al. analyze the timeslot array and put forward the concept of time slot
groups, but their application scope is limited [6]. And they improve the segment tree
so that it can adapt to the flexible resource reservation better [7].
3.2
Non-slotted Data Structures
Among the non-slotted data structures, a bandwidth tree was proposed based on re-
source reservation [8]. However, simulation results [9] show that the bandwidth tree is
