Loss Process at an AQM Buffer

Abstract

We perform a comprehensive analysis of packet losses occurring at an AQM buffer in which the packet deletion probability is relative to the size of the queue. Several characteristics of the loss process are derived: the number of deletions in an interval of length t, the temporary intensity of deletions at arbitrary time, the steady-state loss ratio, and the number of losses if there is no service. All of them are obtained for a general deletion probability function and an advanced model of the arrival process, which incorporates, among other things, the autocorrelation of traffic. Analytical results are accompanied by examples in which numerical values are obtained for several configurations of the system. Using these examples, the dependence of the loss process on the initial system state, deletion probability function, and traffic autocorrelation are discussed.

1. Introduction

Packet buffers play an important role in all types of packet networks, including wireless sensor networks (WSNs). The buffers in networking devices are meant to store temporary bursts of packets occurring due to random fluctuations in traffic. There is a long and far from being settled debate regarding what size the buffers should be (see, e.g., [1,2] for WSNs and [3,4] for classic IP networks).

Many researchers postulate that instead of searching for a proper buffer size, active queue management should be applied (see, e.g., Ref. [5] and the references given there). It means basically that packets should be deleted before the buffer becomes full. Moreover, these deletions should be more frequent the more probable an occurrence of congestion (and a buffer overflow) is in the near future.

The easiest way to detect congestion is to observe the size of the queue of packets in the buffer. The simplicity of this method plays an especially important role in WSNs, where computationally and energetically lightweight solutions are to be preferred. No wonder that among 35 congestion detection methods in WSNs protocols, listed in Table 6 of [2], 21 methods are based solely on the size of the queue/buffer occupancy. Therefore, many active queue management solutions are based on the size of the queue as well—see, e.g., Refs. [6,7,8,9,10] for general-purpose methods and [11,12,13] for their WSN-specialized versions. In these solutions, the probability of removing a packet, instead of placing it in the buffer, is a function of the buffer occupancy.

Therefore, we analyze herein a buffer with active queue management such that the probability of removing a packet upon its arrival is a function of the buffer occupancy. Naturally, packet losses arising from this mechanism have a deep impact on the performance of the network in which such a mechanism is used.

The goal of this paper is to present a comprehensive characterization of this packet loss process. To achieve that, the following characteristics are derived:

• The mean number of packets deleted in an interval of length t;
• The temporary intensity of deletions at arbitrary time;
• The steady-state loss ratio;
• The distribution of losses in interval of length t if there is no service.

The contributions of the paper are four new theorems for the four characteristics of the loss process listed above. In addition, several numerical examples are given to demonstrate the applicability of these theorems. In the examples, we can see the progression in time of the number of deleted packets and the temporary intensity of deletions for different initial conditions, deletion probabilities, and traffic autocorrelation.

An advanced model of arrival process is used, i.e., the Markov-modulated Poisson process [14]. First of all, MMPP enables mimicking not only the packet arrival rate and the interarrival time standard deviation but also the whole shape of the interarrival time distribution [15]. What is equally important, it allows for modeling the autocorrelation of packet interarrival times. As exposed in several well-known papers, e.g., [16], we can expect to have positively autocorrelated traffic in packet networks. Moreover, neglecting this autocorrelation in the model of the system may cause far too optimistic evaluation of its performance, sometimes wrong by several scales of magnitude.

To find the characteristics of the loss process, we use herein analytical tools of the queuing theory. First, the distribution of deletions in interval $(0,t)$ if there is no service is found using the fact that it has a recurrent structure in two dimensions. Then, the regeneration property of the queue size process is exploited to build integral equations for the time-dependent mean number of deletions and their intensity. These equations are practically insolvable in the time domain due to their integral forms. For this reason, they are transferred to the Laplace transform domain, where the integrals are removed and the solutions are possible to obtain. Finally, in numerical calculations, the transforms are inverted to the time domain using the inversion formula. This, however, is necessary only when the full, time-dependent solution is needed. To obtain the steady-state solution only (e.g., the steady-state loss ratio), the terminal value theorem can be used to obtain the characteristic directly from the transform domain, without the inversion formula.

All loss characteristics are derived herein for a general buffer model in which the probability of removing a packet is an arbitrary function of the buffer occupancy. In every aforementioned work [6,7,8,9,10,11,12,13], a specific deletion function was used, e.g., linear, cubic, etc. Herein, this function has a general form. Moreover, the service time distribution, associated with the packet size distribution, has a general form as well.

In the rest of the paper, we first characterize the related work (Section 2). In Section 3, the models of the buffer and packet arrival process are presented. Section 4 contains the main contribution of the paper, i.e., four theorems on the loss process characteristics with proofs. Then, in Section 5, examples are given. In particular, the mean number of packet losses and the loss intensity are shown for different initial system states, different forms of deletion probabilities, as well as for correlated and uncorrelated traffic. In addition to theoretical numbers, simulation results are presented. In Section 6, the concluding remarks are gathered.

2. Related Work

As far as the author knows, the results of this article are new.

The loss process in packet networks has been investigated for a long time using an experimental approach (see [17,18,19,20,21,22]) and theoretical models (see [23,24,25,26,27,28,29]), but none of the works [17,18,19,20,21,22,23,24,25,26,27,28,29] incorporate active queue management at the packet buffer. Such a mechanism has, obviously, a deep impact on packet loss characteristics.

Some analytical papers, which deal with the number of deleted packets, do include active queue management based on the size of the queue (see [30,31,32,33,34,35,36]). Unfortunately, in all of them a rather simple model of traffic is assumed. In particular, in [30,31,32,33,34,35], a simple Poisson process is used. A slightly more advanced model is exploited in [36], with general interarrival time distribution. None of the works [30,31,32,33,34,35,36], however, take into account the autocorrelation between interarrival times, which may degrade drastically performance of the system. For instance, in Section 5 here we will encounter an example in which neglecting the autocorrelation, even a mild one, makes the loss ratio optimistically wrong by three orders of magnitude.

In addition to the main loss characteristics, which are studied here, the burst ratio of losses can be studied [37]. The burst ratio, rather than characterizing the number of losses or the intensity of losses, as here, describes the stationary tendency of losses to occur in series, one after the other.

It is worth mentioning that active queue management has also been developed using different approaches, e.g., based on neural networks (see [38,39,40] and the references there). The approach analyzed herein may not give such good results as those based on neural networks but has other important advantages—it is easy to implement and of low computational complexity. Yet, it still gives a substantial improvement when compared with no AQM at all. (For a deeper discussion of that see [41], where a real implementation of the AQM considered herein is presented and accompanied with results of extensive tests in a real network).

This paper presents a comprehensive analysis of the number of deleted packets, for the first time, both in the transient and steady-state case, taking into account an AQM mechanism with packet deletions based on the size of the queue and a complex traffic model with autocorrelation and other advanced modeling capabilities.

3. Buffer Model

We deal with a packet buffer of capacity K. The arriving packets are placed in this buffer in the arrival order, forming a queue. At the same time, the buffer is drained from the head by an egress link. The service (transmission) time of a packet is random and has distribution function $F(·)$. In the simplest case, when the output link has a constant bitrate, distribution F is proportional to the distribution of the packet size. However, F may also account for some other uncertainties of the transmission time, e.g., induced by a wireless link layer.

When the buffer is overflowed, an incoming packet is deleted due to the lack of space for storage. This, however, is not the only case when a packet is deleted. There is also an AQM mechanism operating at the buffer. Namely, every packet can be deleted upon arrival with probability $d\left(n\right)$, where n stands for the number of packets present in the buffer upon the new packet arrival. Function $d\left(n\right)$ can have an arbitrary form as well as distribution F.

By $X\left(t\right)$, we denote the number of packets in the buffer at time t. We assume that both $X\left(t\right)$ and K include the service position. Similarly, n in function $d\left(n\right)$ incorporates the service position.

As usual, it is assumed that the service times are independent of each other, and independent of interarrival times.

Packet interarrival times are modeled by the MMPP process (Markov-modulated Poisson process) [14]. The construction of the MMPP is based on the underlying process, $J\left(t\right)$, which is of CTMC type. This CMTC has m states and intensity matrix Q. To define the MMPP process, we also need m arrival intensities, ${\lambda }_1,\dots ,{\lambda }_m$. The arrivals in the MMPP are of Poisson type but with variable intensity depending on the state of the underlying CMTC. In particular, the arrival intensity at arbitrary time t equals to ${\lambda }_{J\left(t\right)}$. Intensities ${\lambda }_i$ are often used in the diagonal matrix:

$$\mathrm{\Lambda }=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_m\end{array}\right].$$

The formula for the autocorrelation, which is a very important aspect of MMPP, can be found in [14], p. 153.

Finally, there are several known methods for fitting MMPP parameters to observed traffic, including its autocorrelation. In addition to the already mentioned work [15], the methods of [42] or [43] can be used.

4. Results on the Loss Process

We start with derivation of the distribution of the number of deleted and accepted packets in an interval of length t if there is no service. This is a characteristic of the loss and acceptance processes induced by the deletion mechanism only, with excluded influence of the service process. This characteristic may be of interest on its own, but it is also needed in the derivation of other characteristics.

Let $Y_{ij}(n,a,l,v)$ be the probability that in interval $(0,v)$, the number of packets accepted to the buffer is a, and the number of deleted packets is l, assuming that no service is finished by the time t and $J\left(0\right)=i$, $X\left(0\right)=n$, $J\left(t\right)=j$. We will be using its Laplace transform:

$$y_{ij}(n,a,l,s)={\int }_0^{\infty }{e}^{-sv}{Y}_{i,j}(n,a,l,v)\mathrm{d}v,$$

(1)

also in the matrix notation:

$$y(n,a,l,s)={\left[y_{ij}(n,a,l,ts\right]}_{i=1,\dots ,m;j=1,\dots ,m}.$$

(2)

To find $Y_{i,j}(n,a,l,t)$, we start with the case where no packets are deleted or accepted by the time t. This can happen either if there are no events by the time t, which has the probability $e^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})}t$, or if there is a change of the CMTC state from i to k only, which happens with intensity $p_{i,k}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}$, where

$$p_{ij}=\left\{\begin{array}{c}{Q}_{ij}/({\mathrm{\Lambda }}_{ii}-Q_{ii}),\mathrm{i}\mathrm{f} i\ne j,\hfill \\ \\ 0,\mathrm{i}\mathrm{f} i=j.\hfill \end{array}\right.$$

(3)

Therefore, we have

$$\begin{array}{cc}\hfill Y_{ij}(n,0,0,t)={\delta }_{ij}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})t}+\sum _{k=1}^m{\int }_0^t{p}_{ik}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}& Y_{kj}(n,0,0,t-v)\mathrm{d}v,\hfill \\ \hfill & 0\le i,j\le m,\hfill \end{array}$$

(4)

where ${\delta }_{ij}$ is the Kronecker delta function, namely

$${\delta }_{ij}=\left\{\begin{array}{c}0, \mathrm{i}\mathrm{f} i\ne j,\hfill \\ \\ 1, \mathrm{i}\mathrm{f} i=j.\hfill \end{array}\right.$$

No deletions and one or more packet acceptances by the time t can happen if the first packet appears by t and it is accepted, which happens with intensity $(1-d\left(n\right)){\mathrm{\Lambda }}_{ik}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}$. Alternatively, the CMTC can switch its state from i to k before that. In the former case, the size of the queue changes to $n+1$, while the required number of acceptances to $a-1$. In the latter situation, the size of the queue and the required number of acceptances do not change. We have:

$$\begin{array}{cc}\hfill Y_{ij}(n,a,0,t)& =(1-d\left(n\right))\sum _{k=1}^m{\int }_0^t{\mathrm{\Lambda }}_{ik}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n+1,a-1,0,t-v)\mathrm{d}v\hfill \\ \hfill & +\sum _{k=1}^m{\int }_0^t{p}_{ik}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n,a,0,t-v)\mathrm{d}v,a>0,0\le i,j\le m.\hfill \end{array}$$

(5)

On the other hand, no packet acceptances and one or more deletions by the time t can happen if the first packet appears by t and it is deleted or if the CMTC switches its state from i to k before that. In the former case, the queue does not change, but the required number of deletions decreases by 1. In the latter situation, the queue and the required number of losses do not change. Therefore, we have:

$$\begin{array}{cc}\hfill Y_{ij}(n,0,l,t)& =d\left(n\right)\sum _{k=1}^m{\int }_0^t{\mathrm{\Lambda }}_{ik}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n,0,l-1,t-v)\mathrm{d}v,\hfill \\ \hfill & +\sum _{k=1}^m{\int }_0^t{p}_{ik}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n,0,l,t-v)\mathrm{d}v,l>0,0\le i,j\le m.\hfill \end{array}$$

(6)

Lastly, to have one or more acceptances and one or more deletions by the time t, there has to be an arrival by t, no matter whether accepted or deleted. There also could be a CMTC state change before that. We have

$$\begin{array}{cc}\hfill Y_{ij}(n,a,l,t)& =(1-d\left(n\right))\sum _{k=1}^m{\int }_0^t{\mathrm{\Lambda }}_{ik}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n+1,a-1,l,t-v)\mathrm{d}v,\hfill \\ \hfill & +d\left(n\right)\sum _{k=1}^m{\int }_0^t{\mathrm{\Lambda }}_{ik}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n,a,l-1,t-v)\mathrm{d}v,\hfill \\ \hfill & +\sum _{k=1}^m{\int }_0^t{p}_{ik}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{Y}_{kj}(n,a,l,t-v)\mathrm{d}v,a,l>0,0\le i,j\le m.\hfill \end{array}$$

(7)

In the next step, we employ the Laplace transform to (4)–(7). Pay attention that all Equations (4)–(7) contain convolution integrals in which an exponential function is convoluted with function $Y(n,a,l,v)$ with respect to its last variable. Therefore, using the convolution theorem (see, e.g., [44], p. 92) yields

$$y_{ij}(n,0,0,s)=\frac{{\delta }_{ij}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}+\sum _{k=1}^m\frac{({\mathrm{\Lambda }}_{ii}-Q_{ii})p_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n,0,0,s),0\le i,j\le m,$$

(8)

$$\begin{array}{cc}\hfill y_{ij}(n,a,0,s)=& (1-d\left(n\right))\sum _{k=1}^m\frac{{\mathrm{\Lambda }}_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n+1,a-1,0,s)\hfill \\ \hfill & +\sum _{k=1}^m\frac{({\mathrm{\Lambda }}_{ii}-Q_{ii})p_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n,a,0,s),a>0,0\le i,j\le m,\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill y_{ij}(n,0,l,s)=& d\left(n\right)\sum _{k=1}^m\frac{{\mathrm{\Lambda }}_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n,0,l-1,s),\hfill \\ \hfill & +\sum _{k=1}^m\frac{({\mathrm{\Lambda }}_{ii}-Q_{ii})p_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n,0,l,s),l>0,0\le i,j\le m,\hfill \end{array}$$

(10)

$$\begin{array}{cc}\hfill y_{ij}(n,a,l,s)=& (1-d\left(n\right))\sum _{k=1}^m\frac{{\mathrm{\Lambda }}_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n+1,a-1,l,s)\hfill \\ \hfill & +d\left(n\right)\sum _{k=1}^m\frac{{\mathrm{\Lambda }}_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n,a,l-1,s)\hfill \\ \hfill & +\sum _{k=1}^m\frac{({\mathrm{\Lambda }}_{ii}-Q_{ii})p_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{y}_{kj}(n,a,l,s),a,l>0,0\le i,j\le m,\hfill \end{array}$$

(11)

respectively. Then, (8)–(11) can be rewritten using matrices. For $n\ge 0$, we have

$$y(n,0,0,s)=M\left(s\right)+N\left(s\right)y(n,0,0,s),$$

(12)

$$\begin{array}{c}\hfill y(n,a,0,s)=(1-d(n\left)\right)\mathrm{\Lambda }M\left(s\right)y(n+1,a-1,0,s)+N\left(s\right)y(n,a,0,s),a>0,\end{array}$$

(13)

$$\begin{array}{c}\hfill y(n,0,l,s)=d\left(n\right)\mathrm{\Lambda }M\left(s\right)y(n,0,l-1,s)+N\left(s\right)y(n,0,l,s),l>0,\end{array}$$

(14)

$$\begin{array}{cc}\hfill y(n,a,l,s)=(1-d(n\left)\right)\mathrm{\Lambda }M\left(s\right)y(n+1,a-1,l,s)& +d\left(n\right)\mathrm{\Lambda }M\left(s\right)y(n,a,l-1,s)\hfill \\ \hfill & +N\left(s\right)y(n,a,l,s),a,l>0,\hfill \end{array}$$

(15)

where

$$M\left(s\right)={\left[\frac{{\delta }_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}\right]}_{i=1,\dots ,m;k=1,\dots ,m},$$

(16)

$$N\left(s\right)={\left[\frac{({\mathrm{\Lambda }}_{ii}-Q_{ii})p_{ik}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}\right]}_{i=1,\dots ,m;k=1,\dots ,m}.$$

(17)

Finally, denoting the identity matrix by I, we can solve Equations (12)–(15) with respect to $y\left(\right)$. After that, we obtain the theorem as follows.

Theorem 1.

The transform of the joint distribution of lost and accepted packets in interval $(0,v)$ if there is no service is given by the following recursion:

$$y(n,0,0,s)={(I-N\left(s\right))}^{-1}M\left(s\right),$$

(18)

$$\begin{array}{c}\hfill y(n,a,0,s)=(1-d\left(n\right)){(I-N\left(s\right))}^{-1}\mathrm{\Lambda }M\left(s\right)y(n+1,a-1,0,s),a>0,\end{array}$$

(19)

$$\begin{array}{c}\hfill y(n,0,l,s)=d\left(n\right){(I-N\left(s\right))}^{-1}\mathrm{\Lambda }M\left(s\right)y(n,0,l-1,s),l>0,\end{array}$$

(20)

$$\begin{array}{cc}\hfill y(n,a,l,s)={(I-N\left(s\right))}^{-1}\mathrm{\Lambda }M\left(s\right)[(1-d\left(n\right))y(n+1,a-1,l,s)& +d\left(n\right)y(n,a,l-1,s)],\hfill \\ & a,l>0.\hfill \end{array}$$

(21)

It is easy to see that Theorem 1 can be used effectively to calculate $y(n,a,l,s)$ for arbitrary $n,a,l,s$.

Note also that, using Theorem 1, we can calculate the sole distribution of the number of accepted packets or the sole distribution of the number of deleted packets if there is no service. The former is obtained by summing $y(n,a,l,s)$ by all $l^{\prime }$s, the latter is obtained by summing $y(n,a,l,s)$ by all $a^{\prime }$s.

Now, let $L_{ni}\left(t\right)$ be the mean number of packets deleted by the time t under conditions that at $t=0$ the size of the queue is n and the CMTC state is i and let

$$l_{ni}\left(s\right)={\int }_0^{\infty }{e}^{-st}{L}_{ni}\left(t\right)\mathrm{d}t,$$

(22)

$$l_n\left(s\right)={[l_{n1}\left(s\right),l_{n2}\left(s\right),\dots ,l_{nm}\left(s\right)]}^T.$$

(23)

Assume that one or more packets are present in the queue at $t=0$. In this case, the service begins at $t=0$ as well. Conditioning on the departure time of the first served packet, v, yields

$$\begin{array}{cc}\hfill L_{ni}\left(t\right)=& \sum _{j=1}^m\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }{\int }_0^t{Y}_{ij}(n,a,l,v)[l+L_{n+a-1,j}(t-v)]\mathrm{d}F\left(v\right)\hfill \\ \hfill & +\sum _{j=1}^m\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }l{Y}_{ij}(n,a,l,t)[1-F\left(t\right)],1\le n\le K,1\le i\le m.\hfill \end{array}$$

(24)

The first summand of Formula (24) can be explained as follows. With probability $Y_{ij}(n,a,l,v)$, by the end of the first service, there will be a newly accepted packets in the buffer, and thus the new size of the queue at time v will be $n+a-1$ and the new CMTC state will be j. During the same interval $(0,v)$, there will be l deletions, and thus the new mean number of packet losses, counting from time v, will be $l+L_{n+a-1,j}(t-v)$. The second summand of Formula (24) can be explained by noticing that with probability $1-F\left(t\right)$, the first service will end after t. In such cases, the mean number of packet losses by t is just a sum of $l{Y}_{ij}(n,a,l,t)$ with respect to every possible l, a, and j.

Pay attention that (24) does not have a nice, recursive form, which can often be met when analyzing the classic queuing model with MMPP traffic (see, e.g., recursion (36) in [14]). This follows from the fact that, in contrary to the classic model, the considered model is not spatially homogeneous. Namely, in the classic model, the probability that the queue decreases by 1 in a given interval is the same for every positive queue size. Herein, this probability varies depending on the queue size and associated deletion probabilities.

Employing the Laplace transform to (24) and using the convolution theorem, we have

$$\begin{array}{cc}\hfill l_{ni}\left(s\right)=& \sum _{j=1}^m\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }\frac{l{g}_{ij}(n,a,l,s)}{s}+\sum _{j=1}^m\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }{g}_{ij}(n,a,l,s)l_{n+a-1,j}\left(s\right)\hfill \\ \hfill & +\sum _{j=1}^m\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }l{h}_{ij}(n,a,l,s),1\le n\le K,1\le i\le m,\hfill \end{array}$$

(25)

with

$$g_{ij}(n,a,l,s)={\int }_0^{\infty }{e}^{-sv}{Y}_{ij}(n,a,l,v)\mathrm{d}F\left(v\right),$$

(26)

$$h_{ij}(n,a,l,s)={\int }_0^{\infty }{e}^{-sv}{Y}_{ij}(n,a,l,v)(1-F\left(v\right))\mathrm{d}v.$$

(27)

Exploiting vector notation, we then have

$$\begin{array}{cc}\hfill l_n\left(s\right)=& \sum _{a=0}^{K-n}\sum _{l=0}^{\infty }\frac{l}{s}G(n,a,l,s)\mathbf{1}+\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }G(n,a,l,s)l_{n+a-1}\left(s\right)\hfill \\ \hfill & +\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }lH(n,a,l,s)\mathbf{1},1\le n\le K,\hfill \end{array}$$

(28)

with

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

(29)

$$G(n,a,l,s)={\left[g_{ij}(n,a,l,s)\right]}_{i=1,\dots ,m;j=1,\dots ,m},$$

(30)

$$H(n,a,l,s)={\left[h_{ij}(n,a,l,s)\right]}_{i=1,\dots ,m;j=1,\dots ,m}.$$

(31)

Assume now the system is empty at $t=0$. If so, we have

$$\begin{array}{cc}\hfill L_{0i}\left(t\right)=& \sum _{j=1}^m{\int }_0^t{p}_{ij}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-\left(({\mathrm{\Lambda }}_{ii}-Q_{ii})\right)v}{L}_{0j}(t-v)\mathrm{d}v\hfill \\ \hfill & +\left(1-d\left(0\right)\right)\sum _{j=1}^m{\int }_0^t{\mathrm{\Lambda }}_{ij}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}{L}_{1j}(t-v)\mathrm{d}v\hfill \\ \hfill & +d\left(0\right)\sum _{j=1}^m{\int }_0^t{\mathrm{\Lambda }}_{ij}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}(1+L_{0j}(t-v))\mathrm{d}v,1\le i\le m.\hfill \end{array}$$

(32)

Indeed, the first event by the time t can be either the change of the CMTC from i to j, which happens with intensity $p_{ij}({\mathrm{\Lambda }}_{ii}-Q_{ii})e^{-\left(({\mathrm{\Lambda }}_{ii}-Q_{ii})\right)v}$, or an accepted arrival, which happens with intensity $(1-d\left(0\right)){\mathrm{\Lambda }}_{ij}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}$, or a deleted arrival, which happens with intensity $d\left(0\right){\mathrm{\Lambda }}_{ij}{e}^{-({\mathrm{\Lambda }}_{ii}-Q_{ii})v}$. In the first case, the size of the queue upon the first event remains 0, and thus the new number of losses is $L_{0j}(t-v)$. In the second case, the size of the queue upon the first event becomes 1, and thus the new number of losses is $L_{1j}(t-v)$. In the third case, the size of the queue upon the first event remains 0, but the first event increases the number of losses by 1, and thus the new number of losses is $1+L_{0j}(t-v)$.

From (32) we then obtain

$$\begin{array}{cc}\hfill l_{0i}\left(s\right)=& \sum _{j=1}^m\frac{({\mathrm{\Lambda }}_{ii}-Q_{ii})p_{ij}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{l}_{0j}\left(s\right)+\left(1-d\left(0\right)\right)\sum _{j=1}^m\frac{{\mathrm{\Lambda }}_{ij}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{l}_{1j}\left(s\right)\hfill \\ \hfill & +\frac{d\left(0\right)}{s}\sum _{j=1}^m\frac{{\mathrm{\Lambda }}_{ij}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}+d\left(0\right)\sum _{j=1}^m\frac{{\mathrm{\Lambda }}_{ij}}{s+{\mathrm{\Lambda }}_{ii}-Q_{ii}}{l}_{0j}\left(s\right),1\le i\le m,\hfill \end{array}$$

(33)

and, finally,

$$\begin{array}{c}\hfill l_0\left(s\right)=N\left(s\right)l_0\left(s\right)+\left(1-d\left(0\right)\right)\mathrm{\Lambda }M\left(s\right)l_1\left(s\right)+\frac{d\left(0\right)}{s}\mathrm{\Lambda }M\left(s\right)\mathbf{1}+d\left(0\right)\mathrm{\Lambda }M\left(s\right)l_0\left(s\right).\end{array}$$

(34)

As we can notice, (28) and (34) establish a system of linear equations. We can easily rearrange these equations to obtain the solution in an explicite form. It is summarized in the theorem as follows.

Theorem 2.

The transform of the mean number of packets lost in $(0,t)$ is equal to:

$$l\left(s\right)=Z^{-1}\left(s\right)x\left(s\right),$$

(35)

where

$$l\left(s\right)={[l_0{\left(s\right)}^T,\dots ,l_K{\left(s\right)}^T]}^T,$$

(36)

$$Z\left(s\right)={\left[Z_{i,j}\left(s\right)\right]}_{i,j=0,\dots ,K},$$

(37)

$$Z_{ij}\left(s\right)=\left\{\begin{array}{cc}N\left(s\right)+d\left(0\right)\mathrm{\Lambda }M\left(s\right)-I,\hfill & ifi=j=0,\hfill \\ \left(1-d\left(0\right)\right)\mathrm{\Lambda }M\left(s\right),\hfill & ifi=0,j=1,\hfill \\ \sum _{l=0}^{\infty }G(i,1,l,s)-I,\hfill & ifi=j,i>0,\hfill \\ \sum _{l=0}^{\infty }G(i,j+1-i,l,s),\hfill & if1\le i\le K,i-1\le j\le K-1,i\ne j,\hfill \\ \mathbf{0},\hfill & otherwise,\hfill \end{array}\right.$$

(38)

$$\begin{array}{c}\hfill x\left(s\right)={[x_0{\left(s\right)}^T,\dots ,x_K{\left(s\right)}^T]}^T,\end{array}$$

(39)

$$x_0\left(s\right)=-\frac{d\left(0\right)}{s}\mathrm{\Lambda }M\left(s\right)\mathbf{1},$$

(40)

$$x_n\left(s\right)=-\left[\sum _{a=0}^{K-n}\sum _{l=0}^{\infty }\frac{l}{s}G(n,a,l,s)+lH(n,a,l,s)\right]\mathbf{1},1\le n\le K,$$

(41)

and $\mathbf{0}$ is a square matrix of 0s.

In practice, it is perhaps more intuitive to use the temporary intensity of deletions at time t, rather than the number of packets deleted in $(0,t)$. We define the temporary intensity of deletions at t as:

$$I_{ni}\left(t\right)=\frac{\mathrm{d}{L}_{ni}\left(t\right)}{\mathrm{d}t}.$$

(42)

Denote

$$i_{ni}\left(s\right)={\int }_0^{\infty }{e}^{-st}{I}_{ni}\left(t\right)\mathrm{d}t,$$

(43)

$$i_n\left(s\right)={\left[i_{n1}\left(s\right),\dots ,i_{nm}\left(s\right)\right]}^T,$$

(44)

$$i\left(s\right)={[i_0{\left(s\right)}^T,\dots ,i_K{\left(s\right)}^T]}^T.$$

(45)

It is a simple matter to obtain $i\left(s\right)$ from Theorem 2. Namely, using the formula for the transform of the derivative of the original function (see, e.g., [44], p. 54), we obtain the theorem as follows.

Theorem 3.

The transform of the intensity of deletions at t is equal to:

$$i\left(s\right)=s{Z}^{-1}\left(s\right)x\left(s\right),$$

(46)

where $Z\left(s\right)$ and $x\left(s\right)$ are given in (38) and (39)–(41), respectively.

Now we can derive the steady-state loss ratio, L, which is the global fraction of packets lost is a very long (infinite) interval. To achieve that, we can use the terminal value theorem (see, e.g., [44], p. 89), which bonds the behavior of the original function at $t=\infty$ with the behavior of its Laplace transform at $s=0+$. Namely, applying this theorem, we have

$$L=\underset{t\to \infty }{lim}{I}_{0,1}\left(t\right)/\lambda =\underset{s\to 0+}{lim}s{\left[i\left(s\right)\right]}_1/\lambda ,$$

(47)

where $\lambda$ is the global arrival rate, while ${\left[\right]}_1$ stands for the first entry of a vector. Finally, (47) and Theorem 3 yield the theorem as follows.

Theorem 4.

$$L=\underset{s\to 0+}{lim}{s}^2{\left[Z^{-1}\left(s\right)x\left(s\right)\right]}_1/\lambda ,$$

(48)

where $Z\left(s\right)$ and $x\left(s\right)$ are given in (38) and (39)–(41), respectively.

Obviously, $\lambda$ can be obtained by computing the steady-state distribution, $\pi$, of the CMTC, using equations

$$\left\{\begin{array}{c}\pi Q=[0,\dots ,0],\hfill \\ \\ \pi ·\mathbf{1}=1.\hfill \end{array}\right.$$

(49)

After that, we have

$$\lambda =\pi \mathrm{\Lambda }\mathbf{1}.$$

(50)

Finally, note that Theorems 1–3 are formulated in the transform domain. Therefore, the transform inversion formula is needed in numerical calculations (see, e.g., [44]). Theorem 4 can be used directly, without inversion.

5. Examples and Discussion

In the numerical examples of this section, the following parameterization of the arrival process to the packet buffer is used:

$$Q=\left[\begin{array}{ccc}\hfill -0.2772& \hfill 0.1310& \hfill 0.1462\\ \hfill 0.0734& \hfill -0.1458& \hfill 0.0724\\ \hfill 0.0664& \hfill 0.0973& \hfill -0.1637\end{array}\right],$$

(51)

$$\mathrm{\Lambda }=\left[\begin{array}{ccc}4.17575& 0& 0\\ 0& 0.32020& 0\\ 0& 0& 0.05271\end{array}\right].$$

(52)

It has a normalized total rate of $\lambda =1$ and mildly correlated interarrival times. The correlation coefficient of interarrival times for lags of 1–10 are shown in

Table 1. Correlation coefficient of interarrival times versus lag.

lag, k	1	2	3	4	5	6	7	8	9	10
correlation, $R\left(k\right)$	0.2156	0.1360	0.0946	0.0682	0.0498	0.0365	0.0267	0.0196	0.0144	0.0106

. As we can notice, the 1-lag correlation is 21%, but for lags over 10 it gets below 1%. As we will see, even such a mild correlation plays a crucial role in the loss process.

If not declared otherwise, the following deletion probabilities are used in the AQM mechanism, with $K=40$:

$$\begin{array}{cc}\hfill d\left(n\right)& =\left\{\begin{array}{ccc}0,\hfill & \mathrm{i}\mathrm{f}\hfill & n<20,\hfill \\ 0.0025n^2-0.1n+1,\hfill & \mathrm{i}\mathrm{f}\hfill & 20\le n<40,\hfill \\ 1,\hfill & \mathrm{i}\mathrm{f}\hfill & n\ge 40.\hfill \end{array}\right.\hfill \end{array}$$

(53)

(Other forms of $d\left(n\right)$ will be investigated at the end of the section.) Finally, the packet service time is hyperexponentially distributed, with parameters $(0.2,0.8)$ and $(0.6,3)$. Using the hyperexponential distribution allows us to set an arbitrary mean service time and its standard deviation. Herein, the mean service time is $T=0.6$, so the system is underloaded: $\rho =\lambda T=60\%$. The service time standard deviation is $S=0.963$, which gives a moderate coefficient of variation of the service time equal to 1.6.

For this parameterization of the system, the mean number of deletions in $(0,t)$ and the temporary intensity of deletions at t are depicted in Figure 1 and Figure 2, respectively. These figures are meant to illustrate the progression of the loss process in time, depending on the initial size of the queue. Therefore, the same initial CMTC state is used in every case, but n varies from 0 to 40.

As we can notice in Figure 1 and Figure 2, the progression of the loss process depends greatly on n in the initial, transient phase. For some values of the initial queue size, the intensity of deletions is not monotone in time. For instance, for $n=20$, $n=30$, and $n=40$, the intensity of deletions grows at first, then reaches a maximum, then decreases to some stable level.

In general, the particular behavior of the loss process can be attributed to complex interactions between the traffic, the size of the queue, and the deletion probability. Roughly speaking, the autocorrelated traffic tends to build up the queue in the buffer. However, the longer the queue is, the higher the deletion probability becomes and the more arriving packets are not allowed into the system. This gives the time to the service process to drain the buffer and decrease the queue, which in consequence decreases the deletion probability.

If, for instance, the initial queue is long, then a high deletion probability is used instantly according to (53), and we can see a steep peak of losses (the red curve in Figure 2). Such intensive losses last only for a relatively short time, until the service process can drain a significant portion of packets present in the buffer initially. This decreases the deletion probability and the loss process slowly converges to the steady state. If, on the other hand, the initial queue is short or empty, then no packets are deleted at the beginning, according to (53). In such cases, positively correlated arrivals build up the queue gradually, increasing packet deletions gradually until the steady state is achieved (see the black curve in Figure 2).

As can be seen in Figure 1 and Figure 2, the transient phase ends at about $t=70$. After that, the mean number of packet losses grows linearly and the temporary intensity of deletions stabilizes.

What is remarkable, the steady-state loss intensity is very high given the low load of the system. We have $L=I_{n,i}(\infty )=0.0599$, which means that on average about 6% of packets are lost, even though the system load is only 60%. This effect originates from the complex, autocorrelated structure of the traffic. (This will be discussed further at the end of the section).

In Figure 3 and Figure 4, the mean number of deletions in $(0,t)$ and the temporary intensity of deletions at t are depicted again. This time, the same $n=0$ is used in every case, but i varies from 1 to 3. Therefore, we can observe the progression of the loss process depending on the initial state of the CMTC for an initially empty queue. As we can notice, the loss process evolves quite differently for $i=1$ than for the two remaining states.

Notably, there is no significant difference between $i=2$ and $i=3$ cases, even though ${\lambda }_2$ is about six times greater than ${\lambda }_3$.

A similar situation can be seen in Figure 5, where the temporary intensity of deletions at t is depicted but for a different initial size of the queue, $n=20$.

Now we will proceed to the examination of the influence of function $d\left(n\right)$ on the progression of the loss process. To realize that, we will use a family of functions $d\left(n\right)$, dependent on two positive parameters, p and q, namely

$$d_{p,q}\left(n\right)={\left(d(n+p)\right)}^q,$$

(54)

where the original $d\left(n\right)$ is given in (53). In Figure 6, the shapes of function $d_{p,q}\left(n\right)$ for selected combinations of parameters p and q are shown. As can be seen, parameter p determines the deletion threshold, while parameter q determines the convexity of the deletion function. Obviously, the two parameters have the opposite impact on the number of losses. When p is kept unaltered and q grows, the number of losses decreases. When q is kept unaltered and p grows, the number of losses increases. Therefore, it is interesting to observe their combined impact on the loss process.

In Figure 7 and Figure 8, the temporary intensity of deletions at t for selected functions $d_{p,q}\left(n\right)$ is depicted. Figure 7 was obtained for the initial size of the queue of 20, while Figure 8 was obtained for the initial size of the queue of 30. Clearly, the influence of p (deletion threshold) prevails—the loss intensity decreases with this parameter in both figures. The reverse effect of growing q (convexity) is not strong enough to decrease the loss intensity.

In the next example, we check the influence of the autocorrelated structure of traffic on the loss process. Namely, the temporary intensity of deletions is computed for the MMPP parameterized in (51) and (52), as well as for the simple Poisson process of the same rate, $\lambda =1$. The results for the MMPP are obtained using Theorem 3, while the results for the Poisson process are obtained using the results of [35].

In both cases, the same function $d\left(n\right)$ from (53), the same service time distribution (defined at the beginning of this section), and the same initial size of the queue (zero) are used. In the case of MMPP, $i=1$ is assumed.

The resulting deletion intensities are depicted in Figure 9. Note the great difference between the two curves—the figure is in the logarithmic scale. In particular, the steady-state loss ratio is 6% in the case of MMPP and only 0.0095% in the case of Poisson arrivals, which is a difference of almost three orders of magnitude. Clearly, the autocorrelated structure of traffic influences the loss process heavily.

Finally, the theoretical results on the loss process were verified using computer simulation. For this purpose, a public-source simulator OMNeT++ was used. Namely, the model defined in Section 2 was implemented scrupulously in OMNeT++ and parameterized using parameters given at the beginning of this Section, i.e., (51)–(53), and hyperexponential service with parameters $(0.2,0.8)$ and $(0.6,3)$.

Three different initial sizes of the queue were used in simulations, $n=0$, $n=20$, and $n=40$. Each simulation run lasted until simulated stopping time t was reached. Four different values of this stopping time were used in different simulation runs: $t=5$, $t=50$, $t=500$, and $t=5000$. In every run, the number of deleted packets was noted. The simulation of every scenario, e.g., $n=20$ and $t=500$, was repeated 100,000 times with new RNG seeds so that a reliable mean value could be extracted from all the runs. In every run, $i=1$ was used.

The results of these simulations are presented in

Table 2. Theoretical and simulated mean number of deletions in interval $(0,t)$ depending on t and the initial size of the queue, n.

	Theoretical ${\mathit{L}}_{\mathit{n},\mathbf{1}}\left(\mathit{t}\right)$	Simulated ${\mathit{L}}_{\mathit{n},\mathbf{1}}\left(\mathit{t}\right)$
$n=0$, $t=5$	2.37 $\times {10}^{-3}$	2.33$\times {10}^{-3}$
$n=20$, $t=5$	9.85$\times {10}^{-1}$	9.83$\times {10}^{-1}$
$n=40$, $t=5$	9.68$\times {10}^0$	9.67$\times {10}^0$
$n=0$, $t=50$	2.62$\times {10}^0$	2.62$\times {10}^0$
$n=20$, $t=50$	7.13$\times {10}^0$	7.11$\times {10}^0$
$n=40$, $t=50$	1.98$\times {10}^1$	1.98$\times {10}^1$
$n=0$, $t=500$	3.03$\times {10}^1$	3.03$\times {10}^1$
$n=20$, $t=500$	3.49$\times {10}^1$	3.48$\times {10}^1$
$n=40$, $t=500$	4.78$\times {10}^1$	4.78$\times {10}^1$
$n=0$, $t=5000$	3.07$\times {10}^2$	3.07$\times {10}^2$
$n=20$, $t=5000$	3.11$\times {10}^2$	3.11$\times {10}^2$
$n=40$, $t=5000$	3.24$\times {10}^2$	3.24$\times {10}^2$

. They are compared with the theoretical results obtained via Theorem 2. As can be observed, there is a high compliance between the simulated and the theoretical numbers in all the scenarios.

6. Conclusions

In this paper, a comprehensive analysis of the packet loss process caused by an AQM buffer in which the loss probability is relative to the size of the queue was carried out. Several characteristics of the loss process were derived: the number of packets deleted in an interval of length t, the temporary intensity of deletions at arbitrary time, the steady-state loss rate, and the number of losses if there is no service. They were obtained for a general deletion probability function and an advanced model of the arrival process, which includes autocorrelation.

In numerical examples, the progression of the loss process in time, depending on the initial state of the system, was presented first. As we could see, both the the initial CMTC state and the initial size of the queue had a deep impact of the loss process, resulting in different, sometimes even non-monotone, behavior.

Then, the impact of the deletion probability function on the loss process was demonstrated using a family of deletion functions dependent on two parameters which determined the deletion threshold and the convexity of the deletion function, respectively. Apparently, the deletion threshold prevailed, i.e., for the loss intensity, it was more important in which size of the queue the deletions began than what convexity the deletion function had.

Finally, the impact of the autocorrelation of traffic was shown in an example comparing the loss process for correlated and uncorrelated traffic. Even for a mildly correlated traffic, a quite high steady-state loss ratio of 6% was obtained. It was in great contrast with the steady-state loss ratio obtained for traffic of the same rate but with zero correlation. In the latter case, only 0.0095% of the packets were lost—almost three orders of magnitude fewer.

There are a few possible directions of future work.

Firstly, for the same active queue management model defined in Section 3, other performance parameters may be investigated.

Secondly, performance parameters of other active queue management models in which the packet deletion probability is not directly relative to the size of the queue can be studied analytically. For instance, the CoDel algorithm [45], uses packet sojourn times through the buffer rather than sizes of the queue. Moreover, the deletion probability is related to sojourn times in a complicated way. Roughly speaking, when the observed sojourn times exceed some predefined threshold T for some predefined period of time P, a packet is deleted and the next deletion event is set in the future. It is not clear whether an analytical model of such an AQM can be solved using the currently available tools of the queueing theory. Nevertheless, such an analysis is worth giving a try due to the fact that the CoDel algorithm is becoming more and more popular.

Finally, an application of the model in vehicular networks (see e.g., Refs. [46,47]) can be investigated. As it is assumed that such networks operate often in a high-load regime (see [46]), active queue management may potentially constitute a useful tool for congestion reduction. This, however, requires some further studies.