Kelly's LAN model revisited
Authors: Baryshnikov Yuliy , Coffman E. G. , Jelenković Predrag 
Published: January 2007

For a given
k
≥ 1, subintervals of a given interval
[0,
X
] arrive at random and are accepted (allocated) so long
as they overlap fewer than
k
subintervals already accepted.
Subintervals not accepted are cleared, while accepted subintervals
remain allocated for random retention times before they are
released and made available to subsequent arrivals. Thus, the
system operates as a generalized many-server queue under a loss
protocol. We study a discretized version of this model that appears
in reference theories for a number of applications; the one of most
interest here is linear communication networks, a model originated
by Kelly [2]. Other applications include surface
adsorption/desorption processes and reservation systems [3, 1].

The interval [0,
X
],
X
an integer, is subdivided
by the integers into slots of length 1. An
interval
is
always composed of consecutive slots, and a configuration C of
intervals is simply a finite set of intervals in [0,
X
]. A
configuration C is
admissible
if every non-integer point in
[0,
X
] is covered by at most
k
intervals in C. Denote
the set of admissible configurations on the interval [0,
X
]
by

C
X
.

Assume that, for any integer point
i,
intervals of length l with left endpoint
i
arrive
at rate λ
l
; the arrivals of intervals at
different points and of different lengths are independent. A newly
arrived interval is included in the configuration if the resulting
configuration is admissible; otherwise the interval is rejected. It
is 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 similar
description: the flow of "killing" signals for intervals of length
l arrive at each integer
i
at rate µ
l
. If
at the time such a signal arrives, there is at least one interval
of length l with its left endpoint at
i
in the
configuration, then one of them leaves.

Our primary interest is in steady-state estimates of the vacant
space, i.e., the total length of available subintervals
kX
-
∑l

i

, where the l

i

are the
lengths of the subintervals currently allocated. We obtain explicit
results for
k
= 1 and for general
k
with all
subinterval lengths equal to 2, the classical
dimer
case of
chemical applications. Our analysis focuses on the asymptotic
regime of large retention times, and brings out an apparently new,
broadly useful technique for extracting asymptotic behavior from
generating functions in two dimensions.

Our model, as proposed by Kelly [2], arises in a study of
one-dimensional communication networks (LAN's). In this
application, intervals correspond to the circuits connecting
communicating parties and [0,
X
] represents the bus. Kelly's
main results apply to the case
k
= 1 and to the case of
general
k
with interval lengths governed by a geometric
law.

The focus here is on space utilization, so the results here add
to the earlier theory in three principal ways. First, we give
expected vacant space for
k
= 1, with special emphasis on
small-µ asymptotics. Behavior in this regime is quite
different 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, where
all intervals have length 2, is covered. Finally, the approach of
the analysis itself appears to be new and to hold promise for the
analysis of similar Markov chains. In very broad terms, expected
vacant space is expressed in terms of the geometric properties of a
certain plane curve defined by a bivariate generating function.