The AQM Dropping Packet Probability Function Based on Non-integer Order $PI^{\alpha }D^\beta$ Controller

Abstract

In this paper we present the probability function based on PID controller with non-integer integral and derivative orders. We present how to change the probability of packet dropping during continuous increase in buffer occupancy. The shape of the probability function strictly depends on the parameters selection.

1 Introduction

First AQM mechanism was proposed in 1993 by Floyd and Jacobson. Its performance is based on a drop function giving probability that a packet is rejected. It was named Random Early Detection (sometimes Random Early Discard). This mechanism is based on previous preventive dropping packets even if there is still place in the queue. The packets are dropped randomly and the probability of packet rejection depends on the queue occupancy. The argument avg of this function is a weighted moving average queue length:

$$ avg=(1-w_q)avg'+w_qq $$

q is the current queue length, $avg'$ is the previous value of avg and $w_q$ is a weight parameter, typically $w<<1$, thus avg varies much more slowly than q. Therefore avg indicates permanent network congestion reflecting long-term changes of q. If $avg<Min_{th}$, all packets are admitted. There are two thresholds: $Min_{th}$ and $Max_{th}$. If $Min_{th}<avg<Max_{th}$, then dropping probability p increases linearly:

$$ p=p_{max}\frac{avg-Min_{th}}{Max_{th}-Min_{th}} $$

The value $p_{max}$ corresponds to the probability of packet rejection at $avg=Max_{th}$. If $avg>Max_{th}$ then all packets are dropped. Dropping probability p is thus dependent on a network load - has small value for smaller load, and increases with the increasing of congestion.

The choice of RED parameter is difficult. The proper parameter selection problem was discussed in many articles (e.g. [2, 18, 25, 26]). There are a lot of modifications of the RED mechanism (e.g. [12]). We have also proposed and evaluated a few variants, [1, 4,5,6,7,8,9, 11].

In this article we propose a different method of dropped packet probability calculation based on the fractional order $PI^{\alpha }D^{\beta }$ controller applied to active queue management. First PI AQM controller was proposed by Hollot et al. [13, 14]. Since then a number of PI controllers have been proposed [19,20,21, 27]. The paper [26] compared performance of several of them. The articles [3, 16, 24] show that controllers with non-integer integral and derivative orders have better performance than classic ones. The first application of the fractional order PI controller as a AQM policy in fluid flow model of a TCP connection was presented in [15]. In [10] we discuss the $PI^{\alpha }$ controller as an AQM mechanism. In particular we investigate the influence of parameters of the controller on packet loss probability, queue length (hence also transmission time) and its variability (jitter) which are usual determinants of the quality of service for network transmissions.

In our paper the extension of the fractional $PI^{\alpha }$ controller is presented. The rest of this article is constructed as follows: Sect. 2 gives features of the fractional order PID controller as AQM mechanism. In Sect. 3 we propose a dropping probability function based on $PI^{\alpha }D^\beta$ controller. Section 4 concludes this article and discusses future works.

2 Fractional Calculus

The Fractional Calculus is a natural extension of normal integrals and derivatives. The first mention of the possibility of integral order $\frac{1}{2}$ appeared in 1695. Dilemma recognized by Leibniz was resolved several years later. At the end of the nineteenth century the basis of fractional calculus were created by Liouville, Grunwald, Letnikow, Riemann.

The Fractional Order Derivatives and Integrals (FOD/FOI) definitions unify the definition of derivative and integral to one differintegral definition. The most popular formulas to calculate differintegral numerically are Grunwald-Letnikov (GrLET) formula and Riemann-Liouville formulas (RL) [17, 22, 23].

Differintegral is a combined differentiation/integration operator. The q-differintegral of f, denoted by

$$\begin{aligned} \varDelta ^{q}f \end{aligned}$$

(1)

is the fractional derivative (for $q > 0$) or fractional integral (if $q < 0$). If $q = 0$, then the q-th differintegral of a function is the function itself.

If order of differintegral is greater then 0 then we calculate the derivative. If the order is smaller then 0 then we calculate integral.

In the case of discrete systems (in the active queue management, packet drop probabilities are determined at discrete moments of packet arrivals) there is only one definition of differ-integrals of non-integer order. This definition is a generalization of the traditional definition of the difference of integer order to the non integer order and it is analogous to a generalization used in Grunwald-Letnikov (GrLET) formula.

$$\begin{aligned} \triangle ^{q} f_k=\sum _{j=0}^k(-1)^j {{q}\atopwithdelims (){j}}{f_{k-1}} \end{aligned}$$

(2)

where $q \in R$ is generally a non-integer fractional order, $f_k$ is a differentiated discrete function and ${{q}\atopwithdelims (){j}}$ is generalized Newton symbol defined as follows:

$$\begin{aligned} {{q}\atopwithdelims (){j}} = \left\{ \begin{array}{l l } 1 &{} \hbox {for } j=0\\ \displaystyle \frac{q(q-1)(q-2)..(q-j+1)}{j!}&{}\hbox {for } j=1, 2, \ldots \end{array} \right. \end{aligned}$$

(3)

The following formulas show the relationships between the traditional and the fractional approach.

For $\alpha =1$ we get the formula for the difference of the first order (only two coefficients are non-zero).

$$\begin{aligned} \triangle ^1 x_k = 1x_k-1x_{k-1}+0x_{k-2}+0x_{k-3}\ldots \end{aligned}$$

(4)

For $\alpha =-1$ we get the sum of all samples (the discrete integral of first order equivalent).

$$\begin{aligned} \triangle ^{-1} x_k = 1x_k+1x_{k-1}+1x_{k-2}+1x_{k-3}\ldots \end{aligned}$$

(5)

For $\alpha =0.5$ we get the weighted sum of all samples:

$$\begin{aligned} \triangle ^{0.5} x_k = 1x_k-0.5x_{k-1} - 0.125x_{k-2}-0.0625x_{k-3}\ldots \end{aligned}$$

(6)

For $\alpha =1.5$ we get:

$$\begin{aligned} \triangle ^{1.5} x_k = 1x_k-1.5x_{k-1} + 0.375x_{k-2}+0.0625x_{k-3}\ldots \end{aligned}$$

(7)

And adequately:

$$\begin{aligned} \triangle ^{-0.5} x_k = 1x_k+0.5x_{k-1} +0.375x_{k-2}+0.3125x_{k-3}\ldots \end{aligned}$$

(8)

$$\begin{aligned} \triangle ^{-1.5} x_k = 1x_k+1.5x_{k-1} + 1.875x_{k-2}+2.1875x_{k-3}\ldots \end{aligned}$$

(9)

3 The Packet Dropping Probability Function Based on $PI^{\alpha }D^\beta$ Controller

A proportional-integral-derivative controller (PID controller) is a traditional mechanism used in feedback control systems. Earlier works show that the non-integer order controllers have better behavior than classic controllers [24]. $PI^{\alpha }D^\beta$ may be used instead of the RED mechanism to determine the probability p of a packet drop in the following way:

$$\begin{aligned} p_i=max \{0,-(K_P e_k+K_I \varDelta ^\alpha {e_k}+K_D \varDelta ^ \beta {e_k})\} \end{aligned}$$

(10)

where $K_P, K_I, K_D$ are tuning parameters, $e_k$ is the error in current slot $e_k = q_d-q$, q - actual queue size, $q_d$ - desired queue size, $\alpha$ and $\beta$ are non integer integral and derivative order.

As stated in the previous section the method of calculation of the controller derivative and integral term (based on GrLET formula) is the same but the integral orders ($\alpha$) are always less than 0 and derivative orders ($\beta$) are greater than 0.

For standard PID controller (for $\alpha =-1$ and $\beta =1$) the packet dropping probability is defined as follows (see Eqs. 4 and 5):

$$\begin{aligned} p_i=max \{0,-(K_p e_i+K_i\sum _{j = i}^0 e_j+K_d(e_j-e_{j-1} )\} \end{aligned}$$

(11)

In this proposition the dropping probability depends on five parameters: the coefficients for the proportional, integral and derivative terms ($K_p, K_i, K_d$) and integrals ($\alpha$) and derivative ($\beta$) orders.

Figures presented in this section show the probability of packet dropping p given by Eq. 10 and are based on the $PI^{\alpha }D^{\beta }$ response. The figures present how change the probability of packet dropping during continuous increase in buffer occupancy as a result of the continuous packets incoming. Naturally, the response depends on the choice of parameters.

The Figs. 1, 2, 3 and 4 present the $PI^{\alpha }$ controller behavior. In Figs. 1 and 2 $\alpha = -1$, therefore it is in fact a PI controller. The integral term in the $PI^\alpha$ creates a strong correlation between the packet dropping probability and the history of the queue occupancy. This correlation is confirmed by the Fig. 4. This figure shows two situations. In the first case the controller starts error calculation at once. In the second case the controller begins work when the queue length exceeds desired queue size. When the controller starts error calculation for empty queue (start point = 0), its reaction is evidently delayed. This delay depends on the integral order (see: Fig. 3).

Fig. 1.

Packet dropping probability based on a $PI^\alpha$ controller response (the influence of the parameter $K_p$), $\alpha =-1$, $K_i=0.0008$

Fig. 2.

Packet dropping probability based on a $PI^\alpha$ controller response (the influence of the parameter $K_i$) $\alpha =-1$, $K_p=0.00115$

Fig. 3.

Packet dropping probability on a $PI^\alpha$ controller response (the influence of the integral order $\alpha$) $K_p=0.00115$, $K_i=0.0011$

Fig. 4.

Packet dropping probability on a $PI^\alpha$ controller response (the influence of the previous queue occupancy) $K_p=0.00115$, $K_i=0.0011$, $\alpha =-1$

Fig. 5.

Packet dropping probability on a $PD^\beta$ controller response (the influence of the parameter $K_p$) $K_d=0.01$, $\beta =1$

Fig. 6.

Packet dropping probability on a $PD^\beta$ controller response (the influence of the parameter $K_d$) $K_p=0.00115$, $\beta =1$

Fig. 7.

Packet dropping probability on a $PD^\beta$ controller response (the influence of the derivative order $\beta$) $K_p=0.00115$, $K_d=0.01$

Fig. 8.

Packet dropping probability on a $PD^\beta$ controller response (the influence of the previous queue occupancy and the derivative order $\beta$) $K_p=0.00115$, $K_d=0.01$, $\beta =2.5, 2.0, 1.0, 1.5, 0.8, 0.4$

Fig. 9.

Packet dropping probability on a $PI^{\alpha }D^\beta$ controller response (the influence of the parameter $K_p$) $K_d=0.01$, $K_i=0,0011$, $\alpha =-1$, $\beta =1$

Fig. 10.

Packet dropping probability on a $PI^\alpha {}D^\beta$ controller response (the influence of the derivative order $\beta$) $K_p=0.00115$, $K_d=0.01$, $K_i=0,0011$, $\alpha =-1$

Fig. 11.

Packet dropping probability on a $PI^\alpha {}D^\beta$ controller response (the influence of the derivative order $\beta$) $K_p=0.00115$, $K_d=0.01$, $K_i=0,0011$, $\alpha =-0.8$

Fig. 12.

Packet dropping probability on a $PI^\alpha {}D^\beta$ controller response (the influence of the integral order $\alpha$) $K_p=0.00115$, $K_d=0.01$, $K_i=0,0011$, $\beta =0.5$

The Figs. 5, 6, 7 and 8 present the $PD^{\beta }$ controller behavior. The Figs. 5 and 6 present standard PD controller ($\beta = 1$). The controller derivative term increases the dropping probability. The Fig. 8 presents the controller behavior in dependence on queue history and derivative order. The derivative order temporarily increases the controller response.

Figure 9 presents the packet dropping function based on standard PID controller ($\alpha =-1$, $\beta =1$). This figure shows the proportional term influence on controller response. The derivate order influence ($\beta$) on $PID^{\beta }$ controller ($\alpha =-1$) is shown in Fig. 10.

The last two figures present the $PI^{\alpha }D^{\beta }$ controller responses. The Fig. 12 presents the derivative order $\beta$ influence on packet dropping probability function ($\alpha =0.8$). The Fig. 11 shows the integral order impact (derivative order $\beta =0.5$).

4 Summary

The Internet Engineering Task Force (IETF) organization recommends to use in IP routers active queue management mechanism (AQM). This mechanisms drops packet in preventive way even if there is still place to store packets. In classical AQM mechanisms (i.e. RED) packets are dropped randomly and the probability of packet rejection increases together with queue occupancy. Many variations of RED mechanism were developed to improve its performance. They can be classified according to the modification of the method of control variable or dropping packet function calculation.

This article introduces the new active queue management based on fractional $PI^\alpha {}D^\beta$ controller. In the proposed mechanism, the dropping packet probability is calculated based on controller response. The AQM quality highly depends on the proper selection of controller parameters. In the proposed solution controller response depends on five parameters: proportional, integral and derivative terms and derivative and integral orders.

In the article we present how to change the probability of packet dropping during continuous increase in buffer occupancy. The shape of the probability function strictly depends on the parameters selection.

We present a selection of parameters to show the influence of the proportional term, integral term and derivative term on dropping function. The non-integer derivative and integral order cause significant differences in the behavior of the controller.

In future work the authors will show how the choice of fractional controller parameters affects the behavior of the router queue. An interesting issue may be to find a set of parameters that minimize queue length. Our article shows that integral order delays eventually accelerates the controller reaction while the derivative order strengthens or weakens controller response. Therefore, the adaptive fractional controller with variable orders depending on the situation in the queue may be more efficient in the router queues.