Lindley equation

From Wikipedia, the free encyclopedia

 The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

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

[edit] Calculating the Queue Size of a Work Conserving Link

The departures at a work conserving communications link 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 arrivals up to and including time t. Let a(t) be the number of arrivals in the interval t, in which case:

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

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

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

where x + = max(0,x) and a(t) = A(t) − A(t − 1). In each period the departures b from the queue is bounded by c:

b(t) \le c .

If c < q(t) + a(t + 1), then b(t) = c, otherwise b(t) = q(t) + a(t + 1) and q(t + 1) = 0, that is the backlog has been cleared.

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.