On the Probability of Buffer Overflow Under an Arbitrary Bounded Input-Output Distribution

In this paper we study the behavior of a certain queue which arises when a finite buffer is used to store data. Specifically, our problem is the following. Every time instant i( = 0,1, ⋯ )Xᵢ units of data arrive (say from a data source) for ultimate transmission over a channel or some other processor. At this same time instant, this channel will accept Yᵢ data units for transmission. We assume that \ Xᵢ ,Yᵢ \₀^∞ are random variables such that with positive probability Yᵢ < Xᵢ. Thus, at least some of the time, the channel will not be able to accept all the available data. We assume therefore that a buffer is interposed between the source and channel to store this excess. Let L be the size or capacity of the buffer. Occasionally the buffer will be full, and at these times the excess (Xᵢ - Yᵢ ) units of data must be discarded and considered as lost. In this paper our primary concern is with Q₁ (L), the average fraction of data which is lost due to the “buffer overflow”. An informal statement of our main result is the following. We assume that Zᵢ = ^Δ Xᵢ - Yᵢ, 0 i < ∞, are independent identically distributed bounded random variables with arbitrary probability distribution, and we show that Q₁ (L), the average fraction of data lost due to buffer overflow is, for large L, approximately (i) $A / L(A > 0)$ or (ii) Br₀- L (B > 0,r₀ > 1) according as (i) E(Zᵢ ) = 0 or (ii) E(Zᵢ ) < 0, respectively. For case (ii) we also determine the parameter r₀.