Lindley equation

An ideal "work conserving" communications link has an infinite buffer and traffic departs fromit at a rate $c$when the buffer is backlogged. The Lindley equation gives the length ofa buffer queue of a work conserving communicationslink given a cumulative traffic arrival process $A$ and capacity $c$.

Calculating the Queue Size of a Work Conserving Link

The departures at a "work conserving" communicationslink are constrained by its capacity $c$.If the number of arrivals $A$is a discrete-time process:

$A\; =\; \{A(t),\; t=0,1,2,ldots\}$

where $A$ is the total number of arrivalsup to and including time $t$.Let $a(t)$ be the number of arrivalsin the interval $t$, in which case:

$a(t)=A(t)-A(t-1)$

The length of the buffer queue of this workingconserving link $q(t)$at time $t$, is given by the Lindley equation:

$q(t+1)\; =\; (q(t)+a(t+1)-c)^\{+\}$

where $x^\{+\}\; =\; extrm\{max\}(0,x)$ and $a(t)\; =\; A(t)-A(t-1)$. In each periodthe departures $b$ from the queue is bounded by $c$:

$b(t)\; le\; c$.

If