| Abstract |
For a given k ≥ 1, subintervals of a given interval[0, X] arrive at random and are accepted (allocated) so longas they overlap fewer than k subintervals already accepted.Subintervals not accepted are cleared, while accepted subintervalsremain allocated for random retention times before they arereleased and made available to subsequent arrivals. Thus, thesystem operates as a generalized many-server queue under a lossprotocol. We study a discretized version of this model that appearsin reference theories for a number of applications; the one of mostinterest here is linear communication networks, a model originatedby Kelly [2]. Other applications include surfaceadsorption/desorption processes and reservation systems [3, 1].The interval [0, X], X an integer, is subdividedby the integers into slots of length 1. An interval isalways composed of consecutive slots, and a configuration C ofintervals is simply a finite set of intervals in [0, X]. Aconfiguration C is admissible if every non-integer point in[0, X] is covered by at most k intervals in C. Denotethe set of admissible configurations on the interval [0, X]by $C_{X}.$ Assume that, for any integer pointi, intervals of length l with left endpoint i arriveat rate $λ_{l};$ the arrivals of intervals atdifferent points and of different lengths are independent. A newlyarrived interval is included in the configuration if the resultingconfiguration is admissible; otherwise the interval is rejected. Itis convenient to assume that the arrival rates $λ_{l}vanish$ for all but a finite number of lengths l, $sayλ_{l}$ > 0, 1 ≤ l ≤ L, $andλ_{l}$ = 0 otherwise.The departure of intervals from configurations has a similardescription: the flow of "killing" signals for intervals of lengthl arrive at each integer i at rate $µ_{l}.$ Ifat the time such a signal arrives, there is at least one intervalof length l with its left endpoint at i in theconfiguration, then one of them leaves.Our primary interest is in steady-state estimates of the vacantspace, i.e., the total length of available subintervals kX $-∑l_{i},$ where the $l_{i}$ are thelengths of the subintervals currently allocated. We obtain explicitresults for k = 1 and for general k with allsubinterval lengths equal to 2, the classical dimer case ofchemical applications. Our analysis focuses on the asymptoticregime of large retention times, and brings out an apparently new,broadly useful technique for extracting asymptotic behavior fromgenerating functions in two dimensions.Our model, as proposed by Kelly [2], arises in a study ofone-dimensional communication networks (LAN's). In thisapplication, intervals correspond to the circuits connectingcommunicating parties and [0, X] represents the bus. Kelly'smain results apply to the case k = 1 and to the case ofgeneral k with interval lengths governed by a geometriclaw.The focus here is on space utilization, so the results here addto the earlier theory in three principal ways. First, we giveexpected vacant space for k = 1, with special emphasis onsmall-µ asymptotics. Behavior in this regime is quitedifferent from that seen in the "jamming" limit (absorbing state)of the pure filling model (all µ's are identically 0).Second, the important dimer case of chemical applications, whereall intervals have length 2, is covered. Finally, the approach ofthe analysis itself appears to be new and to hold promise for theanalysis of similar Markov chains. In very broad terms, expectedvacant space is expressed in terms of the geometric properties of acertain plane curve defined by a bivariate generating function. |
