Output Stream from the AQM Queue with BMAP Arrivals

Abstract

We analyse the output stream from a packet buffer governed by the policy that incoming packets are dropped with a probability related to the buffer occupancy. The results include formulas for the number of packets departing the buffer in a specific time, for the time-dependent output rate and for the steady-state output rate. The latter is the key performance measure of the buffering mechanism, as it reflects its ability to process a specific number of packets in a time unit. To ensure broad applicability of the results in various networks and traffic types, a powerful and versatile model of the input stream is used, i.e., a BMAP. Numeric examples are provided, with several parameterisations of the BMAP, dropping probabilities and loads of the system.

1. Introduction

In the vast majority of packet networks, there are buffers for packets employed at network nodes. It is optimal when the occupancy of these buffers is low most of the time, but non-zero. If there are no packets in the buffer to transmit, then the link between the nodes is underutilised. Conversely, when the buffer occupancy is high, the packet sojourn time in the buffer is long, adding unnecessary delay to the whole packet delivery time.

In the literature, short queues, essential to sustain high utilisation of links, are called “good queues”, whereas the long unnecessary ones are called “bad queues” [1]. Unfortunately, bad queues appear quite often in all forms of packet networking, including wired, wireless and sensor networks. Specifically, bad queues occur when the following three factors are combined together: tail-drop buffers, the TCP protocol and oversized buffering space. All of them are pretty common. Namely, oversized buffers are common due to Moore’s Law and inexpensive memory chips. Tail-drop buffer organisation, i.e., the policy that a packet is deleted if and only if the buffer is full, is the simplest and the most popular one. Lastly, the TCP protocol is the one of the most useful and exploited protocols in networking.

It is generally understood that active queue management (AQM), implemented in packet buffers, may reduce or eliminate bad queues [2,3]. In AQM, a packet may be dropped while the buffer occupancy is far from maximum. Some advanced AQM mechanisms use many system states and complicated policies to decide whether a packet ought to be dropped or not [1,4,5,6,7,8,9,10].

A different approach to AQM is that a packet is dropped on arrival with probability $d\left(k\right)$, which is directly related the buffer occupancy on this packet arrival, k. In this case, only one variable (the buffer occupancy) and a simple decision policy is used. In different studies, different functions $d\left(k\right)$ have been suggested: linear [11], negative exponential [12], polynomial [13,14], beta [15] and other functions [16,17].

The simplicity of the policy based on the buffer occupancy, its ease of implementation and its low computational complexity (i.e., low energy requirement) are especially attractive in wireless sensor networking (WSN). Therefore, several authors advocate using it in WSN, e.g., [18,19,20,21].

In this paper, we want to analyse the output stream from a buffer governed by this policy. A typical scenario is depicted in Figure 1. Specifically, we have a wireless sensor network of some topology and a sink node that collects data packets from sensor nodes. It transmits them further to a user through the internet (or to a local server first, but this is irrelevant here). Most importantly, the sink node has implemented an AQM mechanism at the buffer of its output interface (the blue part in Figure 1). Our interest lies in the statistical properties of the output stream from this buffer.

The buffer with AQM under study, in blue in Figure 1, is enlarged further in Figure 2. Namely, on the left-hand side of Figure 2, the traffic from the wireless sensor network, aggregated inside the sink node, is depicted. The packets from this traffic are subject to the AQM mechanism based on function $d\left(k\right)$. Specifically, every packet on arrival is subject to a random decision; it is dropped with probability $d\left(k\right)$, or it is deposited in the buffer of size N with probability $1-d\left(k\right)$. Argument k of function $d\left(k\right)$ denotes the buffer occupancy at the time of each decision. The buffer in Figure 2 is meanwhile being drained by transmissions throughout the output link. Each packet transmission time is random and has an arbitrary distribution function $F\left(t\right)$. This distribution may account for variable packet sizes or a variable bitrate of the output link, or both. Lastly, the aggregated traffic, on the left-hand side of Figure 2, is modelled here by the BMAP process, whose powerful capabilities enable modelling of traffic of arbitrary type and complexity (this subject will be broadened later).

Note that the output stream on the right-hand side of Figure 2 must be essentially unlike the aggregated traffic on the left-hand side. First, this is because the AQM mechanism occasionally drops packets, which is its main goal for the reasons explained before. Therefore, even the output rate from the sink node is not equal to its input rate. Second, the transmission through the output link further changes the statistical properties of the output stream.

The purpose of this paper is to find the characteristics of the output stream in Figure 2 using instruments of queuing theory, and to study in numeric examples how the properties of the output stream vary with the properties of the model.

The paper proceeds with the following arrangements. In Section 2, the contribution of the paper is detailed. In Section 3, previous investigations in related fields are recalled. The model of the input stream, the packet buffer and its policy based on function $d\left(k\right)$ are presented in Section 4. Then, in Section 5, a mathematical analysis of the output stream is conducted. In Section 6, numeric examples are shown and commented, with diverse parameterisations of the input stream, mechanism loads and functions $d\left(k\right)$. Lastly, the insights of this research work are summarised in Section 7. In the same section, suggestions for future work are provided.

2. Contribution

The primary contribution of this paper includes three new formulas: one for the average number of packets over time t in the output stream, one for the momentary packet output rate at time t and one for the steady-state output rate.

The secondary contribution of the paper is a set of numeric examples, exposing dependencies of the output stream characteristics on the model parameters. Specifically, five parameterisations of a BMAP are used in these examples, with different features of the input stream, and combined with different system loads and different forms of function $d\left(k\right)$ to observe the impact of each on the output stream in both steady-state and time-dependent cases.

Why do the characteristics of the output stream matter?

From a networking standpoint, they matter because the considered output stream constitutes an input stream to another device. Specifically, the output stream in Figure 1 can be an input stream to a router, local or distant processing server, local or distant user, etc. Whatever the next device is, the performance of the whole system depends on the characteristics of the considered stream.

From a theoretical angle, the rate of the output stream is the key characteristic of the buffering mechanism, because it represents the overall performance of this mechanism, i.e., its ability to process a specific number of packets in a time unit.

Now, it is worth stressing that the results obtained here are broadly applicable in networks with completely different statistical properties of traffic and exploiting different functions $d\left(k\right)$. Such universality is a consequence of three assumptions on the analysed model.

Firstly, the batch Markovian arrival process (BMAP) is used to model the packet interarrival times in the aggregated traffic (see Figure 2). The BMAP has very powerful modelling capabilities—perhaps most powerful among all known point processes—which are analytically tractable. To name a few of these capabilities, the BMAP is able to model an arbitrary autocorrelation structure of the input stream, batch and single arrivals, and an arbitrary interarrival distribution [22,23]. It is known that all these features may influence the performance of the buffering policy. For instance, the effects of the interarrival distribution are known from elementary queueing theory [24]. The impact of the correlation structure was thoroughly investigated when positive autocorrelation was discovered in LANs [25]. The batch structure of traffic was shown to follow from the design of the TCP protocol [26], and is also known to deeply impact the queueing characteristics [24,27].

Secondly, the transmission times are assumed to have an arbitrary distribution. This means every needed packet length distribution can be used in numeric calculations.

Lastly, the function $d\left(k\right)$ is not specified in the analysis and may be of any mentioned type [11,12,13,14,15,16,17], or some other.

3. Related Work

Based on the author’s knowledge, the results of this article are new.

Specifically, there are no published papers devoted to the output stream of packets leaving a buffer governed by the $d\left(k\right)$-based policy. This is rather unexpected, bearing in mind the importance of the $d\left(k\right)$-based policy in networking and the significance of the characteristics of the output stream, discussed in Section 2.

The work related to this paper can be categorised into four groups.

First, there are published articles on the output stream from a buffer for various types of input stream and = service time, but without the $d\left(k\right)$-based packet dropping policy. For instance, in the classic work [28], the output stream for a Poisson input stream and exponential service is shown to be Poisson. In [29], the case with a general, single, uncorrelated input stream and general service times is studied. In [30], a system with a batch, uncorrelated input stream and general service times is investigated. Lastly, some papers are devoted to analysis of the output stream from a buffer with correlated batch arrivals, see, e.g., [31,32,33].

In none of the mentioned above work was the $d\left(k\right)$-based dropping policy considered, whereas it is a crucial component of the system studied here. Obviously, this policy deeply influences the system performance in general and the output stream behaviour in particular.

Second, there are studies on buffers that do incorporate the $d\left(k\right)$-based policy, but without an analysis of the output stream. In these papers, different queueing characteristics are studied either via simulations [11,12,13,14,15,16,17] or mathematically [34,35,36,37,38,39,40,41,42] under diverse assumptions of system parameters. As it was argued above, the characteristics of the output stream are very important for both theoretical and practical reasons. Therefore, we study them herein.

Third, as it was already mentioned, there are papers on AQM, in which the probability of deletion of a packet at the buffer depends on different variables [1,4,5,6,7,8,9,10].

Fourth, there are many studies on the BMAP and queueing models for telecommunication networks, which are very loosely related to the model studied herein, see, e.g., [43,44,45,46] and the references provided there.

Lastly, it is worth mentioning that usage of the BMAP process is not limited to networking. Other real-world applications of the BMAP include inventory models [47,48], supply chain management [49], maintenance and spare parts [50], disaster models [51] and vehicular traffic [52,53].

All the mentioned references are gathered in

Table 1. Research related to AQM, the BMAP and the output stream.

$d\left(k\right)$-based AQM,	this work
analysis of the output stream
no AQM at all,	[28,29,30,31,32,33]
analysis of the output stream
$d\left(k\right)$-based AQM,	[11,12,13,14,15,16,17,34,35,36,37,38,39,40,41,42]
no analysis of the output stream
different AQM to here,	[1,4,5,6,7,8,9,10]
various characteristics
BMAP traffic models and queueing,	a vast literature, see [43,44,45,46,47,48,49,50,51,52,53]
no AQM at all	and the references there

, in which the originality of this paper is highlighted when compared to them.

4. Model

We are going to analyse the model depicted schematically in Figure 2.

Firstly, the aggregated input stream on the left-hand side of Figure 2 is modelled by a BMAP [54].

To parametrise the BMAP, matrices $D_b$, $b=0,1,\dots$, are needed, each of size $M\times M$. They have to fulfill the following requirements:

• $D_0$ is negative on its diagonal but non-negative outside the diagonal;
• $D_b$ is non-negative for $b>0$;
• $D={\sum }_{k=0}^{\infty }{D}_b$ is a transition-rate matrix, i.e., each row of D sums to zero;
• $D_0\ne D$.

Matrix D constitutes the intensity matrix of the underlying Markov chain of the BMAP, $v\left(t\right)$, which has possible states $\{1,\dots ,M\}$. In what follows, when saying that the BMAP is in state i, we will mean that this underlying chain is in state i, i.e., $v\left(t\right)=i$.

The evolution of $v\left(t\right)$ governs arrivals of batches. In particular, diagonal entries of $D_b$ for $b>0$ correspond to arrivals of batches of length b, while off-diagonal entries correspond to arrivals of batches of length b together with changes in $v\left(t\right)$. Off-diagonal elements of $D_0$ correspond to changes in $v\left(t\right)$ without arrivals. In practice, we usually deal with a few $D_b$ matrices only, each corresponding to a possible batch length. All the remaining $D_b$ values are zero.

Two important characteristics of a BMAP are ${\nu }_i$ and $p_{i,j}\left(b\right)$. Specifically, ${\nu }_i$ is the parameter of the exponentially distributed sojourn time before the next change of state, given that the BMAP is now in state i, whereas $p_{i,j}\left(b\right)$ is the probability that after this sojourn time the state switches from i to j with arrival of a batch of b packets. It holds that

$${\nu }_i=-{\left[D_0\right]}_{i,i},$$

(1)

and

$$p_{i,j}\left(0\right)={\nu }_i^{-1}{\left[D_0\right]}_{i,j},i\ne j,$$

(2)

$$p_{i,j}\left(b\right)={\nu }_i^{-1}{\left[D_b\right]}_{i,j},b>0.$$

(3)

More on the mathematical properties of BMAPs can be found in the monograph [43].

Now, we presume that a buffer of capacity N packets is fed by a stream of packets modelled by a BMAP. The packets create an FIFO queue in this buffer, which is served from the head by a transmission process. The transmission time of each packet is random and distributed in accordance with some distribution function $F\left(t\right)$.

When N packets are present in the buffer, a newly incoming packet is deleted. However, even with fewer than N packets in the buffer, a new packet may be deleted. This may happen with every incoming packet with probability $d\left(k\right)$, where k denotes the buffer occupancy at the time of arrival of this new packet. Therefore, arguments of function $d\left(k\right)$ are non-negative integers, $k=0,1,2,\dots$

It is presumed that the packet being currently transmitted is the first one in the buffer; i.e., there is no separate room for the packet under service. Therefore, the phrase “buffer occupancy” includes the packet being transmitted, if any.

By $\lambda$ we denote the rate of the aggregate input stream, i.e., the BMAP rate. The load of the buffering mechanism is:

$$\rho =\lambda {\mu }^{-1},$$

(4)

where

$${\mu }^{-1}={\int }_0^{\infty }(1-F\left(t\right))\mathrm{d}t,$$

(5)

is the average packet transmission time.

When characterising the output process, we will be interested in the following three characteristics: $D_{n,i}\left(t\right)$, $V_{n,i}\left(t\right)$ and V.

Specifically, $D_{n,i}\left(t\right)$ is the average number of packets occurring in the output stream in $(0,t)$, assuming the buffer occupancy at $t=0$ was n and the state was i.

$V_{n,i}\left(t\right)$ is the momentary rate of the output stream at time t, defined by:

$$V_{n,i}\left(t\right)=\frac{\mathrm{d}{D}_{n,i}\left(t\right)}{\mathrm{d}t},$$

(6)

Finally, V is the steady-state rate of the output stream, defined by:

$$V=\underset{t\to \infty }{lim}{V}_{n,i}\left(t\right).$$

(7)

As the limit in (7) is independent of n and i, any $n=0,\dots ,N$ and $i=1,\dots ,M$ can be used.

All model parameters and characteristics of interest are gathered in

Table 2. Summary of model parameters and characteristics of interest.

$D_b$	BMAP matrices (parameters of the input stream)
$v\left(t\right)$	underlying Markov chain of the BMAP
N	buffer size in packets
$d\left(k\right)$	dropping probability for buffer occupancy k in AQM
$F\left(t\right)$	distribution function of the packet transmission time
M	number of states of $v\left(t\right)$
$\lambda$	packet input rate
$\rho$	load of the buffering mechanism
${\mu }^{-1}$	average packet transmission time
V	state-state rate of the output stream

.

Finally, note that herein we consider only the aggregated traffic without distinguishing between individual flows from users. The information about which packet comes from which individual user is not included in the BMAP. Naturally, the rates and distributions of particular users influence the aggregated traffic. Fortunately, several algorithms for fitting BMAP matrices to the aggregated traffic have already been proposed, see, for example, [22,23,55,56]. In these fitting algorithms, the rates and distributions of particular users are incorporated into the resulting BMAP matrices. We assume herein that we already have the BMAP matrices reflecting the statistical properties of the aggregated traffic and, indirectly, the particular users within it.

5. Output Stream Analysis

To make it easier to follow the derivations in this section, the workflow of the analysis of the output stream is shown in Figure 3.

Therefore, we begin derivations by constructing the first integral equation for $D_{n,i}\left(t\right)$.

Assume first that the buffer occupancy is 0 at $t=0$. For an arbitrary initial state i, we have:

$$D_{0,i}\left(t\right)=\sum _{b=0}^{\infty }\sum _{a=0}^N\sum _{j=1}^M{\int }_0^t{\nu }_i{e}^{-{\nu }_{i}x}{p}_{i,j}\left(b\right)q(0,b,a)D_{a,j}(t-x)\mathrm{d}x,$$

(8)

where ${\nu }_i$ and $p_{i,j}\left(b\right)$ are given in (1) and (3), respectively. Furthermore, $q(n,b,a)$ denotes the probability that on arrival of a batch of b packets, a packets are admitted to the buffer, while $b-a$ packets are dropped, presuming the buffer occupancy on the arrival of this batch is n. A formula for $q(n,b,a)$ will be shown at the end of this section.

Equation (8) is inferred by conditioning on the initial moment of any change in the input stream, x. At time x, a packets are admitted to the buffer, so the new buffer occupancy is a, and the new state is j. There could not be any departure by x, so the new average number of packets departed by t, counting from x, will be $D_{a,j}(t-x)$.

Calculating the Laplace transform for both sides of (8), we achieve:

$$D_{0,i}^{*}\left(s\right)=\frac{{\nu }_i}{{\nu }_i+s}\sum _{b=0}^{\infty }\sum _{a=0}^N\sum _{j=1}^M{p}_{i,j}\left(b\right)q(0,b,a)D_{a,j}^{*}\left(s\right),i=1,\dots ,M,$$

(9)

with

$$D_{n,i}^{*}\left(s\right)={\int }_0^{\infty }{e}^{-st}{D}_{n,i}\left(t\right)\mathrm{d}t.$$

(10)

Then, adopting vectors and matrices in (9), i.e.,

$$D_n^{*}\left(s\right)={[D_{n,1}^{*}\left(s\right),\dots ,D_{n,M}^{*}\left(s\right)]}^T,$$

(11)

$$P(b,s)={\left[\frac{p_{i,j}\left(b\right){\nu }_i}{{\nu }_i+s}\right]}_{i,j=1,\dots ,M},$$

(12)

yields:

$$D_0^{*}\left(s\right)=\sum _{b=0}^{\infty }\sum _{a=0}^{N}q(0,b,a)P(b,s)D_a^{*}\left(s\right).$$

(13)

Lastly, (13) can be ordered with regards to growing a as follows:

$$\left[R(0,0,s)-I\right]D_0^{*}\left(s\right)+\sum _{a=1}^{N}R(0,a,s)D_a^{*}\left(s\right)=\mathbf{0},$$

(14)

where

$$R(n,a,s)=\sum _{b=0}^{\infty }q(n,b,a)P(b,s),$$

(15)

$$\mathbf{0}={[0,\dots ,0]}^T,$$

(16)

and I is the identity matrix.

Now, we can deal with the eventuality where the buffer occupancy is non-zero at $t=0$. In such a situation, we can construct the following equation:

$$\begin{array}{cc}\hfill D_{n,i}\left(t\right)=& \sum _{a=0}^{N-n}\sum _{j=1}^M{\int }_0^t{H}_{i,j}(n,a,x)[1+D_{n+a-1,j}(t-x)]\mathrm{d}F\left(x\right),n=1,\dots ,N,\hfill \end{array}$$

(17)

where $H_{i,j}(n,a,x)$ denotes the probability that until the time x, the number of packets admitted to the buffer is a; the state at the time x is j, given that no departure took place by the time x; the initial occupancy was n; and the initial state was i.

Equation (17) is inferred by conditioning on a different moment to (8). Specifically, x in (17) is the first departure moment, distributed according to $F\left(x\right)$. Just after x, we have one packet already transmitted from the buffer, the new buffer occupancy of $n+a-1$ and the new state of j. Consequently, the new average number of packets departed by t, counting from x, will be $1+D_{n+a-1,j}(t-x)$.

Calculating the Laplace transform for both sides of (17) yields:

$$\begin{array}{cc}\hfill D_{n,i}^{*}\left(s\right)=& \sum _{a=0}^{N-n}\sum _{j=1}^M{a}_{i,j}(n,a,s)\left[\frac{1}{s}+D_{n+a-1,j}^{*}\left(s\right)\right],n=1,\dots ,N,\hfill \end{array}$$

(18)

with

$$a_{i,j}(n,a,s)={\int }_0^{\infty }{e}^{-sx}{H}_{i,j}(n,a,x)\mathrm{d}F\left(x\right).$$

(19)

Denoting:

$$A(n,a,s)={\left[a_{i,j}(n,a,s)\right]}_{i,j=1,\dots ,M},$$

(20)

$$\mathbf{e}={[1,\dots ,1]}^T,$$

(21)

we have from (18):

$$D_n^{*}\left(s\right)=\sum _{a=0}^{N-n}A(n,a,s)\left[\frac{1}{s}\mathbf{e}+D_{n+a-1}^{*}\left(s\right)\right],n=1,\dots ,N.$$

(22)

Lastly, (22) leads to:

$$\sum _{a=0}^{N-n}A(n,a,s)D_{n+a-1}^{*}\left(s\right)-D_n^{*}\left(s\right)=B(n,s),n=1,\dots ,N,$$

(23)

where:

$$B(n,s)=-\frac{1}{s}\sum _{a=0}^{N-n}A(n,a,s)\mathit{e}.$$

(24)

Equations (14) and (23) constitute a system of algebraic equations with unknowns: $D_0^{*}\left(s\right),\dots ,D_N^{*}\left(s\right)$. Combining these unknowns in a vertical vector $D^{*}\left(s\right)$, we can derive the solution of (14) and (23), which can be recapitulated as follows.

Theorem 1.

The average number of packets at time t in the output stream has the Laplace transform:

$$D^{*}\left(s\right)={(C\left(s\right)-I)}^{-1}E\left(s\right),$$

(25)

where

$$D^{*}\left(s\right)={\left[D_0^{*}{\left(s\right)}^T,\dots ,D_N{\left(s\right)}^T\right]}^T,$$

(26)

$$C\left(s\right)={\left[C_{n,m}\left(s\right)\right]}_{n,m=0,\dots ,N},$$

(27)

$$C_{n,m}\left(s\right)=\left\{\begin{array}{cc}R(0,m,s),\hfill & \mathrm{if}n=0,\hfill \\ A(n,m-n+1,s),\hfill & \mathrm{if}n\ge 1,n-1\le m\le N-1,\hfill \\ \mathrm{O},\hfill & \mathrm{otherwise},\hfill \end{array}\right.$$

(28)

$$E\left(s\right)={\left[{\mathbf{0}}^T,B{(1,s)}^T,\dots ,B{(N,s)}^T\right]}^T,$$

(29)

whereas $R(n,m,s)$, $A(n,m,s)$ and $B(n,s)$ are given in (12), (19) and (24), and $\mathrm{O}$ is the zero matrix.

Take note that to use this result in practice, one needs to be able to calculate the values of functions $q(n,b,a)$ and $H_{i,j}(n,a,x)$, which occur in (12) and (19), respectively. Both these functions are rather easy to compute recursively using the method shown in [40]. Specifically, for $q(n,b,a)$, we have:

$$q(n,0,0)=1,$$

(30)

$$q(n,0,a)=0,a\ge 1,$$

(31)

$$q(n,b,0)={\left(d\left(n\right)\right)}^b,b\ge 1,$$

(32)

$$q(n,b,a)=0,min\{N-n,b\}<a,$$

(33)

and

$$q(n,b,a)=q(n,b-1,a)d\left(n\right)+q(n+1,b-1,a-1)(1-d(n\left)\right),b\ge 1,a\ge 1,$$

(34)

which enables recursive calculation of $q(n,b,a)$ for arbitrary n, b and a.

For $H_{i,j}(n,a,x)$, we have the following formulas, recursive with respect to a:

$$H^{*}(n,0,s)={(I-R(n,0,s))}^{-1}Z\left(s\right),$$

(35)

$$H^{*}(n,a,s)={(I-R(n,0,s))}^{-1}\sum _{l=1}^{a}R(n,l,s)H^{*}(n+l,a-l,s),a\ge 1,$$

(36)

where

$$H^{*}(n,a,s)={\left[H_{i,j}^{*}(n,a,s)\right]}_{i,j=1,\dots ,M},$$

(37)

$$H_{i,j}^{*}(n,a,s)={\int }_0^{\infty }{e}^{-st}{H}_{i,j}(n,a,x)\mathrm{d}x,$$

(38)

$$Z\left(s\right)=\mathrm{diag}\left[\frac{1}{s+{\nu }_1},\dots ,\frac{1}{s+{\nu }_M}\right].$$

(39)

and $R(n,a,s)$ is given in (12).

Note also that $D_{n,i}\left(t\right)$ is, by definition, non-decreasing with respect to t. For a visualisation of the properties of the output stream, it is more convenient to use the time-dependent rate of the output stream, $V_{n,i}\left(t\right)$, which is defined in (6).

Applying the well-known derivative theorem on the Laplace transform, we have:

$$V_{n,i}^{*}\left(s\right)=s{D}_{n,i}^{*}\left(s\right),$$

(40)

where

$$V_{n,i}^{*}\left(s\right)={\int }_0^{\infty }{e}^{-st}{V}_{n,i}\left(x\right)\mathrm{d}x,$$

(41)

whereas $D_{n,i}^{*}\left(s\right)$ can be calculated using (25).

The steady-state rate of the output stream, V, can be computed using another well-known property of the transform. Specifically, using the Final-Value Theorem on (40), we have:

$$V=\underset{s\to 0}{lim}{s}^2{D}_{0,1}^{*}\left(s\right).$$

(42)

with $D_{0,1}^{*}\left(s\right)$ obtained from (25) again.

Lastly, note that (25) and (40) are expressed in the transform domain based on variable s. To return to the time domain, t, we have to employ an inversion method. A great variety of such methods is accessible (see monograph [57] on the subject). In the following numeric examples, the Zakian approach is exploited (Formula (7.12) in [57]).

6. Numeric Examples

In the numeric examples, we will use a few parameterisations of the BMAP which exemplify different features of the input stream. These include single arrivals, batch arrivals, positive autocorrelation, negative autocorrelation and no autocorrelation.

Specifically, the following five parameterisations will be employed:

• $BMA{P}_1$:

$$D_0=\left[\begin{array}{ccc}\hfill -0.827091& \hfill 0.787708& \hfill 0.005626\\ \hfill 0.022505& \hfill -0.545767& \hfill 0.011255\\ \hfill 0.001442& \hfill 0.001203& \hfill -1.950544\end{array}\right],D_1=\left[\begin{array}{ccc}0.005626& 0.016879& 0.011252\\ 0.501318& 0.005626& 0.005063\\ 0.019469& 0.000961& 1.927469\end{array}\right].$$

• $BMA{P}_2$:

$$D_0=\left[\begin{array}{ccc}\hfill -1.331696& \hfill 1.268285& \hfill 0.009057\\ \hfill 0.036235& \hfill -0.878738& \hfill 0.018121\\ \hfill 0.015328& \hfill 0.012775& \hfill -20.731246\end{array}\right],D_1=\left[\begin{array}{ccc}0.009059& 0.027177& 0.018118\\ 0.008153& 0.009059& 0.807170\\ 20.485996& 0.010218& 0.206929\end{array}\right].$$

• $BMA{P}_3$:

$$D_0=-0.2I,D_1=0.016667J,D_3=0.022221J,D_9=0.027778J,J={\left[1\right]}_{n,m=1,\dots ,3}.$$

• $BMA{P}_4$:

$$D_0=\left[\begin{array}{ccc}\hfill -0.165418& \hfill 0.157543& \hfill 0.001127\\ \hfill 0.004505& \hfill -0.109154& \hfill 0.002253\\ \hfill 0.000289& \hfill 0.000242& \hfill -0.390109\end{array}\right],D_1=\left[\begin{array}{ccc}0.000281& 0.000844& 0.000562\\ 0.025066& 0.000281& 0.000253\\ 0.000973& 0.000048& 0.096377\end{array}\right],$$

$$D_3=\left[\begin{array}{ccc}\hfill 0.000375& \hfill 0.001125& \hfill 0.000750\\ \hfill 0.033419& \hfill 0.000375& \hfill 0.000337\\ \hfill 0.001297& \hfill 0.000064& \hfill 0.128493\end{array}\right],D_9=\left[\begin{array}{ccc}0.000468& 0.001406& 0.000937\\ 0.041776& 0.000468& 0.000421\\ 0.001622& 0.000080& 0.160624\end{array}\right].$$

• $BMA{P}_5$:

$$D_0=\left[\begin{array}{ccc}\hfill -0.266339& \hfill 0.253653& \hfill 0.001823\\ \hfill 0.007250& \hfill -0.175748& \hfill 0.003627\\ \hfill 0.003067& \hfill 0.002557& \hfill -4.146250\end{array}\right],D_1=\left[\begin{array}{ccc}0.000452& 0.001358& 0.000905\\ 0.000407& 0.000452& 0.040360\\ 1.024340& 0.000510& 0.010346\end{array}\right],$$

$$D_3=\left[\begin{array}{ccc}\hfill 0.000603& \hfill 0.001811& \hfill 0.001207\\ \hfill 0.000543& \hfill 0.000603& \hfill 0.053809\\ \hfill 1.365680& \hfill 0.000681& \hfill 0.013794\end{array}\right],D_9=\left[\begin{array}{ccc}0.000754& 0.002264& 0.001509\\ 0.000679& 0.000754& 0.067264\\ 1.707180& 0.000851& 0.017244\end{array}\right].$$

The total input rate of each of these streams is 1. $BMA{P}_1$ and $BMA{P}_2$ have single arrivals only, whereas $BMA{P}_3$–$BMA{P}_5$ have batch arrivals. $BMA{P}_1$ and $BMA{P}_4$ are positively autocorrelated with a one-lag autocorrelation of 0.425, whereas $BMA{P}_2$ and $BMA{P}_5$ are negatively autocorrelated with a one-lag autocorrelation of −0.425. $BMA{P}_3$ is not autocorrelated. Lastly, $BMA{P}_3$–$BMA{P}_5$ have common average batch length of 5, and a common rate of arrivals of batches of 0.2.

Unless indicated otherwise, the following function $d\left(k\right)$ will be utilised in the examples:

$$\begin{array}{cc}\hfill d\left(k\right)& =\left\{\begin{array}{ccc}0,\hfill & \mathrm{for}\hfill & k=0,\dots ,15,\hfill \\ 1.8-1.8e^{-(k-16)/20},\hfill & \mathrm{for}\hfill & k=16,\dots ,31,\hfill \\ 1,\hfill & \mathrm{for}\hfill & k=32,33,\dots .\hfill \end{array}\right.\hfill \end{array}$$

(43)

This is a negative-exponential function of REM type (see, e.g., [12]). The buffer on which this function operates is of length 32.

Unless indicated otherwise, the transmission time distribution is hyper-exponential with parameters ${\lambda }_1=0.75$, ${\lambda }_2=1.75$, $p_1=0.3$, $p_2=0.7$, the average value of 0.8 and the std. deviation of 0.94. Therefore, unless indicated otherwise, the system load is $\rho =0.8$.

In

Table 3. Rate of the output stream at different times for different input streams. $n=0$, $i=1$.

	$\mathit{t}=20$	$\mathit{t}=50$	$\mathit{t}=100$	$\mathit{t}=200$	$\mathit{t}=500$	$\mathit{t}=\mathbf{\infty }$
$BMA{P}_1$	0.536	0.717	0.809	0.822	0.822	0.822
$BMA{P}_2$	0.941	0.980	0.994	0.994	0.994	0.994
$BMA{P}_3$	0.830	0.900	0.908	0.908	0.908	0.908
$BMA{P}_4$	0.351	0.434	0.526	0.627	0.710	0.715
$BMA{P}_5$	0.801	0.886	0.893	0.894	0.894	0.894

, the rate of the output stream is shown for all considered BMAPs at different times and in the steady state, $t=\infty$. In all instances, the buffer occupancy at $t=0$ was 0 and the initial state was 1.

Let us focus first on the steady-state output rate, shown in the last column of Table 3. As is evident, the rate may differ greatly depending on the internal nuances of the input stream. The worst result, 0.715, differs by almost 30% from the best result, 0.994, even though the input rate was the same in all cases. Note that 0.715 (or even 0.822) is a quite bad output rate, given that the system is significantly underloaded, $\rho =0.8$.

Clearly, positive autocorrelation produces worse results than negative autocorrelation. Specifically, positively correlated $BMA{P}_1$ produces a worse output rate than negatively correlated $BMA{P}_2$, while they both have no batch arrivals. Similarly, positively correlated $BMA{P}_4$ provides a worse rate than negatively correlated $BMA{P}_5$, while they both have the same average batch length. It is interesting, however, that uncorrelated $BMA{P}_3$ offers a slightly better rate than negatively correlated $BMA{P}_5$.

Moreover, batch arrivals produce worse results than single arrivals. This becomes evident if we compare $BMA{P}_1$ with $BMA{P}_4$, and $BMA{P}_2$ with $BMA{P}_5$. Within each of these pairs, the autocorrelation is common but the former input stream is single, whereas the latter is of batch type.

Summarising the steady-state results, the worst rate, 0.715, is obtained when both positive autocorrelation and the batch structure are involved, while the best rate, 0.994, is obtained when the autocorrelation is negative and there are no batch arrivals.

Now we can focus on the time-dependent output rates shown in Table 3. Apparently, the convergence time to the steady state may vary greatly depending on the internal nuances of the input stream. In the case of $BMA{P}_2$ and $BMA{P}_3$, the steady-state output rate is achieved at the relatively low $t=100$, whereas for $BMA{P}_4$, it is not achieved even at $t=500$. The convergence time seems to be prolonged by positive autocorrelation and the batch structure. This can be observed by performing comparisons in the same pairs, as previously, i.e., $BMA{P}_1$ vs. $BMA{P}_2$, $BMA{P}_4$ vs. $BMA{P}_5$, $BMA{P}_1$ vs. $BMA{P}_4$ and $BMA{P}_2$ vs. $BMA{P}_5$.

A detailed evolution in time of the output rate is depicted in Figure 4 and Figure 5 for all considered BMAPs. Figure 4 differs from Figure 5 in that the former is computed for an initially empty buffer, while the latter for an initially full buffer. In the full buffer scenario, the output rate is initially rather high for every considered BMAP. This is because efficient transmission ($\rho <1$) can temporarily provide an output rate greater than the input rate using packets stored in the buffer.

Interestingly, in both Figure 4 and Figure 5, the curves for $BMA{P}_3$ and $BMA{P}_5$ are close to each other, despite the fact that the former stream has no autocorrelation, whereas the latter has negative autocorrelation. Apparently, the negative autocorrelation provides very close (slightly worse) output rates to zero autocorrelation. Conversely, both these curves are in sharp contrast with the $BMA{P}_4$ curve, obtained for positively autocorrelated input streams.

Lastly, we can observe in detail the convergence to the steady state in Figure 4 and Figure 5. For $BMA{P}_2$, $BMA{P}_3$ and $BMA{P}_5$, each with negative or zero autocorrelation, the convergence is pretty quick. It is a little bit slower for $BMA{P}_1$, which has positive autocorrelation, but no batch arrivals, and much slower for $BMA{P}_4$, which has positive autocorrelation and batch arrivals.

A detailed evolution in time of the output rate, depending on the initial occupancy, is depicted in Figure 6 and Figure 7, for one selected input stream, $BMA{P}_4$. In both figures, the curves for initial occupancies of 0, 25%, 50%, 75% and 100% are shown. Figure 6 differs from Figure 7 in that the former is computed for the initial state 1, while the latter for the initial state of 3.

Firstly, we can notice that the initial state may severely influence the evolution of the output rate—the figures are not alike.

Secondly, the discussed above effect of the initially high output rate is not characteristic to the initially full buffer only. In fact, this effect occurs for every non-zero initial occupancy. Therefore, all the curves for $n>0$ differ greatly from the curve for $n=0$ in both Figure 6 and Figure 7.

In the next figure, we may examine the dependence of the steady-state output rate on the system load. To achieve that, parameters ${\lambda }_1$ and ${\lambda }_2$ of the transmission time distribution are scaled by a factor r, resulting in a variable system load from 0 to 2.

The results are depicted in Figure 8. For $BMA{P}_2$, which has neither a batch structure nor positive autocorrelation, a good output rate is maintained almost up to the load of 1. For $BMA{P}_1$, $BMA{P}_3$ and $BMA{P}_5$, which have either batch arrivals or positive autocorrelation, the output rate begins to deteriorate much earlier, for the load about 0.6. However, the impact of the positive autocorrelation in $BMA{P}_1$ prevails, and the output rate in this case drops faster than for $BMA{P}_3$ and $BMA{P}_5$. Lastly, for $BMA{P}_4$, which has both a batch structure and positive autocorrelation, the output rate begins to deteriorate at as low a $\rho$ as 0.3. The shape of the curve is in this case quite close to the shape for $BMA{P}_1$—both curves were obtained for the same autocorrelation.

In the final set of results, we examine the dependence of the steady-state output rate on the function $d\left(k\right)$. To achieve this, we can focus on the most demanding input stream, $BMA{P}_4$, with a class of functions $d\left(k\right)$ depending on two parameters, u and w:

$$d_{u,w}\left(k\right)=d^w\left(\frac{16k-32u+512}{32-u}\right),$$

(44)

where $d\left(k\right)$ is given in (43).

Parameter u establishes the interval of effective operation of function $d_{u,w}\left(k\right)$, which is $(u,32)$. Parameter w establishes how steep the function is, i.e., how quickly the dropping probability grows in the operation interval.

In Figure 9, we can see function $d_{u,w}\left(k\right)$ for a few combinations of parameters u and w.

The resulting steady-state output rate as a function of u and w for $BMA{P}_4$ is depicted in Figure 10. As one could foresee, the output rate grows with each of the two parameters. What is more interesting, however, is that both parameters seem to influence the output rate in a similar manner, i.e., the surface is almost symmetrical.

7. Conclusions

We analysed the output stream from a packet buffer governed by the policy that incoming packets are dropped with a probability related to the buffer occupancy.

In the mathematical part, formulas for the number of packets departing the buffer in a specific time, the time-dependent output rate and the steady-state output rate were derived. A powerful and versatile model of the input stream was used, the BMAP, and accompanied with a general transmission time distribution and a general function $d\left(k\right)$. These make the results broadly applicable in networks of completely different statistical properties of traffic and exploiting different $d\left(k\right)$ probabilities.

In the numeric examples, we used the obtained formulas to examine the influence of the properties of the input stream, system load and function $d\left(k\right)$ on the properties of the output stream.

7.1. Insights of this Research Work

In the steady-state examples, it was shown that the output rate may differ greatly depending on the internal nuances of the input stream, even if the input rate is unaltered. Furthermore, it was demonstrated that the output rate can be quite low, even if the load of the buffering mechanism is low.

An essential takeaway from this is the following. For a given input packet rate $\lambda$, a given load $\rho$ and a particular function $d\left(k\right)$, there is absolutely nothing we can say about the output rate without taking into consideration the internal statistical structure of the input stream.

As was demonstrated, the most important factors causing deterioration of the output rate are the batch structure and positive autocorrelation, especially when combined together. Interestingly, a negative correlation in the input stream produced a slightly worse output rate than a zero correlation.

In the time-dependent examples, its was shown that a batch structure and positive autocorrelation make the convergence time to the steady state much longer than in the case without these factors.

Lastly, it was established that a batch structure and positive autocorrelation can cause much quicker deterioration of the output rate with a growing load.

Namely, in uncorrelated examples with single arrivals, close to the maximum output rate was maintained up to the load approaching 1. If either batch arrivals or positive correlation was introduced, the output rate started to deteriorate at the load of about 0.6. If, however, both these factors were combined together, the output rate began to deteriorate at as low a load as 0.3.

7.2. Future Work

Future work can branch off in several ways.

First, the buffering mechanism from Figure 2 can be further studied with respect to other characteristics. For example, the average response time of this mechanism has not been derived so far. The response time of a system is the total time that a packet spends in this system. (Herein, it would be the time spent in the buffer plus the transmission time.) It is therefore a key characteristic of the mechanism, reflecting the latency that it adds to the entire packet delivery time.

Second, extensions of the mechanism in Figure 2 can be proposed and studied. For example, instead of one function $d\left(k\right)$, a separate function $d\left(k\right)$ for each flow of traffic can be used. For some reasons, we may prefer to filter one flow differently than another.

Third, completely different AQM mechanisms than those considered here can be analysed using queueing models, e.g., the mechanisms of [1,4,5,6,7,8,9,10]. To date, they have been tested mainly using network simulations.

Finally, computations for other transmission time distributions can be carried out, e.g, gamma, uniform, degenerate, etc., distributions.