Reservation Probabilities

Requests for a given resource arrive in a rate- Poisson stream, each specifying a future time interval to be reserved for its use of the resource. The advance notices and the requested intervals are represented by two independent i.i.d. sequences. A request is immediately accepted if it is for an interval that overlaps no currently reserved interval; otherwise, it is lost. We compute the reservation probability, which is the fraction of time the resource is booked. From the huge variety of potential applications covered by our model, relatively new applications in existing and proposed communication systems motivate the research here. We begin by deriving explicit formulas for the reservation probability in several special, but interesting cases. For spread-out advance-notice distributions, our main result then establishes an intriguing connection between the reservation problem and the online interval packing problem. For example, if the advance-notice distribution is uniform on [0; a..