Threshold policies for single-resource reservation systems

Requests for a resource arrive at rate ¦E, eachrequest specifying a future time interval, called a reservationinterval, to be booked for its use of the resource. Theadvance notices (delays before reservation intervals are tobegin) are independent and drawn from a distributionA(z). The durations of reservation intervals aresampled from the distribution B(z) and areindependent of each other and the advance notices. We let A and Bdenote random variables with the distributions A(z)and B(z) (the functional notation will always allowone to distinguish between our two uses of the symbols A andB).The following greedy reservation policy was analyzed in [3]: Arequest is immediately accepted (booked) if and only if theresource will be available throughout its reservation interval,i.e., the resource has not already been reserved for a time periodoverlapping the requested reservation interval. In [3], the authorscompute an efficiency measure, called the reservationprobability, which is the fraction of time the resource is inuse.This paper studies the reservation probability for a moregeneral greedy policy of threshold type that is defined by twoparameters s and ¦O. If a request has anadvance notice less than s or a duration exceeding¦O, then the threshold policy makes an attempt tobook it under the greedy rule; otherwise, it is rejected even if itcould have been accommodated. Our main result is an expression forthe asymptotic reservation probability as s iuiÞ and the advance-notice distribution becomesprogressively more spread out.The above result relates asymptotics of reservation policies toasymptotics of interval packing policies, a connection firststudied in [3]. In the interval packing problem [1], intervalsarrive randomly in R+2 according to aPoisson process in the two dimensions representing arrival timest and the left endpoints of the arriving intervals. Intervallengths are i.i.d., and since we will map them to reservationintervals, we let their distribution also be denoted byB(z). The intensity is 1, i.e., an average of oneinterval arrives per unit time per unit distance. For a givenx > 0, an arriving interval is packed (or accepted) inthe 'containing' interval [0, x] under the greedy algorithmif and only if it is a subinterval of [0, x] and it does notoverlap an interval already accepted. The problem is to find, or atleast estimate, the function K(t, x), which is theexpected total length of the intervals accepted by the greedypolicy during [0, t], assuming that none has yet beenaccepted by time 0 ([0, x] is initially empty).Estimates of K(t, x) were obtained in [3] from itsLaplace transform K(t, u); these results are specialcases of the corresponding results for the threshold packingpolicy with parameters s, ¦O The thresholdpacking policy extends greedy interval packing much as we extendedthe greedy reservation policy: An interval is processed by thegreedy packing algorithm if its length is at least ¦Oor if it arrives no sooner than s; otherwise, it isrejected. The next section exhibits the Laplace transform ofH¦O(s, t, x), the expectedtotal length of the intervals accepted during [0,t],t iÝ s, by the threshold packing policywith parameters s, ¦O. Note that thresholdpacking reduces to simple greedy packing if ¦O = 0 orif s = 0. The formulas in the next section will verify thatK(t,x) = H0(t,t,x).As noted in [3], there are many potential applications coveredby models like ours. However, relatively new applications inexisting and proposed communication systems, e.g., teleconferencingand video-on-demand systems, have given a fresh impetus to researchon reservation systems. Previous work in the communications fieldis quite recent and focuses more on engineering problems thanmathematical foundations; past research has dealt with theimplementation issues of incorporating distributed advance-noticereservation protocols in current networks, and with the algorithmicissues concerned with well utilized resources in reservationsystems (see [3, 4, 5] for many references). For the analysis ofmathematical models different from our own, see the work of Virtamo[5] and Greenberg, Srikant, and Whitt [4].