Threshold policies for single-resource reservation systems
Authors: Coffman E. G. , Jelenković Predrag 
Published: January 2007

Requests for a resource arrive at rate ¦Ë, each
request specifying a future time interval, called a
reservation
interval,
to be booked for its use of the resource. The
advance notices
(delays before reservation intervals are to
begin) are independent and drawn from a distribution
A
(
z
). The durations of reservation intervals are
sampled from the distribution
B
(
z
) and are
independent of each other and the advance notices. We let A and B
denote random variables with the distributions
A
(
z
)
and
B
(
z
) (the functional notation will always allow
one to distinguish between our two uses of the symbols
A
and
B
).

The following greedy reservation policy was analyzed in [3]: A
request is immediately accepted (booked) if and only if the
resource will be available throughout its reservation interval,
i.e., the resource has not already been reserved for a time period
overlapping the requested reservation interval. In [3], the authors
compute an efficiency measure, called the
reservation
probability,
which is the fraction of time the resource is in
use.

This paper studies the reservation probability for a more
general greedy policy of threshold type that is defined by two
parameters
s
and ¦Ó. If a request has an
advance notice less than
s
or a duration exceeding
¦Ó, then the threshold policy makes an attempt to
book it under the greedy rule; otherwise, it is rejected even if it
could have been accommodated. Our main result is an expression for
the asymptotic reservation probability as
s
¡ú
¡Þ and the advance-notice distribution becomes
progressively more spread out.

The above result relates asymptotics of reservation policies to
asymptotics of interval packing policies, a connection first
studied in [3]. In the interval packing problem [1], intervals
arrive randomly in
R
+
2
according to a
Poisson process in the two dimensions representing arrival times
t
and the left endpoints of the arriving intervals. Interval
lengths are i.i.d., and since we will map them to reservation
intervals, we let their distribution also be denoted by
B
(
z
). The intensity is 1, i.e., an average of one
interval arrives per unit time per unit distance. For a given
x
> 0, an arriving interval is packed (or accepted) in
the 'containing' interval [0,
x
] under the greedy algorithm
if and only if it is a subinterval of [0,
x
] and it does not
overlap an interval already accepted. The problem is to find, or at
least estimate, the function
K
(
t, x
), which is the
expected total length of the intervals accepted by the greedy
policy during [0,
t
], assuming that none has yet been
accepted by time 0 ([0,
x
] is initially empty).

Estimates of
K
(
t, x
) were obtained in [3] from its
Laplace transform
K
(
t, u
); these results are special
cases of the corresponding results for the
threshold
packing
policy with parameters
s,
¦Ó The threshold
packing policy extends greedy interval packing much as we extended
the greedy reservation policy: An interval is processed by the
greedy packing algorithm if its length is at least ¦Ó
or if it arrives no sooner than
s
; otherwise, it is
rejected. The next section exhibits the Laplace transform of
H
¦Ó
(
s, t, x
), the expected
total length of the intervals accepted during [0,
t
],
t
¡Ý
s,
by the threshold packing policy
with parameters
s,
¦Ó. Note that threshold
packing reduces to simple greedy packing if ¦Ó = 0 or
if
s
= 0. The formulas in the next section will verify that
K
(
t,x
) =
H
0
(
t,t,x
).

As noted in [3], there are many potential applications covered
by models like ours. However, relatively new applications in
existing and proposed communication systems, e.g., teleconferencing
and video-on-demand systems, have given a fresh impetus to research
on reservation systems. Previous work in the communications field
is quite recent and focuses more on engineering problems than
mathematical foundations; past research has dealt with the
implementation issues of incorporating distributed advance-notice
reservation protocols in current networks, and with the algorithmic
issues concerned with well utilized resources in reservation
systems (see [3, 4, 5] for many references). For the analysis of
mathematical models different from our own, see the work of Virtamo
[5] and Greenberg, Srikant, and Whitt [4].