Self-similarity Traffic and AQM Mechanism Based on Non-integer Order $PI^{\alpha }D^{\beta }$ Controller

Abstract

In this paper the performance of fractional order PID controller as AQM mechanism and impact of traffic self-similarity on network utilization are investigated with the use of discrete event simulation models. The researches show the influence of selection of PID parameters and degree of traffic self-similarity on queue behavior. During the tests we analyzed the length of the queue, the number of rejected packets and waiting times in queues. In particular, the paper uses fractional Gaussian noise as a self-similar traffic source. The quantitative analysis is based on simulation.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Most AQM mechanism proposed by IETF to control the network congestions are based on preventive packed dropping. For the most known active mechanism the number of discarded packets grows with the increase in queue occupancy. The basic active queue management algorithm is Random Early Detection (RED) algorithm. It was primarily proposed in 1993 by Sally Floyd and Van Jacobson [1]. Since that time a number of studies how to improve the basic algorithm have been proposed. We have also proposed and evaluated a few variants, [2,3,4,5,6,7].

In 2001 the use of the PI controller as AQM mechanism was proposed by C.V. Hollot, V. Misra and D. Towsley [8]. Based on the first implementation, a number of PI controllers have been proposed later [9,10,11].

In recent years the fractional order calculus becomes very popular. The articles [12,13,14] show that non-integer order controllers may have better performance than classic integer order. 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]. The detailed influence of fractional order PI controller on queue behavior was presented in article [16].

Measurements and statistical analysis (performed already in the 90s) of packet network traffic show that this traffic displays a complex statistical nature. It is related to such statistic phenomena as self-similarity, long-range dependence and burstiness [17,18,19,20].

Self-similarity of a process means that the change of time scales does not influence the statistical characteristics of the process. It results in long-distance autocorrelation and makes possible the occurrence of very long periods of high (or low) traffic intensity. These features have a great impact on a network performance [21]. They enlarge the mean queue lengths at buffers and increase the probability of packet losses, reducing this way the quality of services provided by a network [22].

As a consequence of this fact, it is needed to propose new or to adapt known types of stochastic processes when modeling these negative phenomena in network traffic. Several models have been introduced for the purposes of modeling self-similar processes in the network traffic area. These models of traffic use fractional Brownian Motion [23], chaotic maps [24], fractional Autoregressive Integrated Moving Average (fARIMA) [25], wavelets and multifractals and processes based on Markov chains: SSMP (Special Semi-Markov Process) [26], MMPP (Markov-Modulated Poisson Process) [27, 28], HMM (Hidden Markov Model) [29].

The main purpose of the paper is to present simulation results for the AQM mechanism in which fractional discrete calculus is used. Section 2 presents theoretical bases for $PI^{\alpha }D^\beta$ controller next used in simulation. Section 3 briefly describes a self-similar traffic used in this article and presents the obtained results.

2 An AQM Mechanism Based on $PI^{\alpha }D^\beta$ Controller

A proportional-integral-derivative controller (PID controller) is a traditional mechanism used in feedback control systems. The article [12] indicates that the introduction non-integer controllers may improve closed loop control quality. Therefore here we propose to use the $PI^{\alpha }D^\beta$ (PID controller with non integer integral and derivative order) instead of the RED mechanism to determine the probability of packet drop. Equation (1) is based on our proposition discussed in [16] for $PI^\alpha$ controller and extended here to the case of $PI^\alpha D^\beta$.

This probability is calculated in the following way:

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

(1)

where $K_P, K_I, K_D$ are tuning parameters, $e_k$ is the error in current slot $e_k = q-q_d$, q - actual queue size, $q_d$ - desired queue size and $\varDelta ^ \alpha {e_k}$ is defined as follows:

$$\begin{aligned} \triangle ^\alpha e_k=\sum _{j=0}^k(-1)^j {{\alpha }\atopwithdelims (){j}}e_{k-1} \end{aligned}$$

(2)

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

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

(3)

This definition unifies the definition of derivative and integral to one differintegral definition. We have the fractional integral of the considered function $e_k$ for $\alpha <0$. If the parameter $\alpha$ is positive, we obtain in the same way a fractional derivative and, to distinguish, we denote this parameter as $\beta$. If $\alpha =0$ the operation (2) does not influence the function $e_k$.

Figure 1 presents a comparison of the increase of packet dropping probability in $PI^\alpha$ and $PD^\beta$ controllers as a function of the queue length increased due to arrivals of packets. Naturally, the response depends on the choice of parameters. As can be seen, the integral order affects the time of controller reaction (below a certain threshold there is no packet dropping). The derivative order influences on increases packet dropping probability.

Fig. 1.

Packet dropping probability in $PI^\alpha$ controller (the influence of the integral order $\alpha$, $K_P=0.00115$, $K_I=0.0011$) (left), and in $PD^\beta$ controller (the influence of the derivative order $\beta$, $K_P=0.00115$, $K_D=0.01$) (right)

3 $PI^{\alpha }D^{\beta }$ Controller Under Self-similar Traffic

In this article we use fractional Gaussian noise as an example of exactly self-similar traffic source. Fractional Gaussian noise (fGn) has been proposed as a model [30] for the long-range dependence postulated to occur in a variety of hydrological and geophysical time series. Nowadays, fGn is one of the most commonly used self-similar processes in network performance evaluation. The fGn process is the stationary Gaussian process that is exactly self-similar [31]. The Hurst parameter H characterizes a process in terms of the degree of self-similarity. The degree of self-similarity increases with the increase of H [32]. A Hurst value smaller or equal to 0.5 means the lack of long range dependence.

We use a fast algorithm for generating approximate sample paths for a fGn process, introduced in [33]. We have generated the sample traces with the Hurst parameter with the range of 0.5 to 0.90. After each trace generation, the Hurst parameter was estimated. The simulations were done using the Simpy Python simulation packet.

During the tests we analyzed the following parameters of the transmission with AQM: the length of the queue, queue waiting times and the number of rejected packets. The service time represented the time of a packet treatment and dispatching. Considered input traffic intensities were $\lambda = 0.5$, independently of Hurst parameter. The distribution of service time was also geometric. Its parameter changed during the test. The high traffic load was considered for parameter $\mu =0.25$. The average traffic load we obtained for $\mu =0.5$. A small network traffic was considered for parameter $\mu =0.75$.

Table 1. FIFO queue

Fig. 2.

The influence of degree of traffic selfsimilarity on queue distribution, FIFO queue, queue size = 300, $\lambda =0.5$, $\mu =0.25$ (left), $\mu =0.5$ (right), $\mu =0.75$ (bottom)

In order to better demonstrate the influence of degree of selfsimilarity on queue behavior first experiment focused on the FIFO queue. The Fig. 2 presents the distribution of the queue length. This figure clearly shows dependence of the queue occupancy on the degree of traffic selfsimilarity. The figure shows three situations: most overloaded network node ($\rho =\frac{\lambda }{\mu }=2$), medium overloaded situation ($\rho =1$) and almost empty buffer for ($\rho =\frac{2}{3}$). The detailed results obtained during the simulation present Table 1. For overloaded buffer ($\mu =0.25$ and $\mu =0.50$) the number of dropped packets increased with the traffic degree of selfsimilarity increasing. This effect becomes more evident with congestion decrease. In the case of an unloaded buffer ($\mu =0.75$) packet loss occur only in the case of traffic with a high degree of selfsimilarity (Hurst parameter $H=0.9$). The presented results show how models that do not consider self-similar traffic may underestimate the queues occupancy and packet lost in routers.

In a first phase of the research we consider the influence of the $PI^{\alpha }$ controller on queue behavior. During the simulation the controller parameters were set as follows: $K_P=0.00115$, $K_I=0.0011$. The integral orders $\alpha$ changed and I received the following values: $-0.8, -1.0$ and $-1.2$. For the integral orders $\alpha =-1$ the controller becomes standard PI control loop feedback mechanism. The Tables 2, 3 and 4 present the obtained results. The queues distribution are presented in Figs. 3 and 4 (the queue distribution for controller with parameter $\alpha =0.8$ is similar to distribution shown in Fig. 3). The controller desired point was set at 100 packet. It should be noted that regardless of the integral order the controller behaved properly.

These studies showed a very interesting controller behavior. In the case of overloaded FIFO queue for traffic of the high degree of self-similarity ($H=0.9$) compared to less self-similar traffic the mean queue length decreases rapidly (see Table 1). This phenomenon also occurs in the case of standard AQM mechanisms [34]. In the case of $PI^{\alpha }$ occurrence of this phenomenon depends on the integral term and becomes less noticeable with the decrease in $\alpha$. Comparing the mean queue length for $H=0.9$ and $H=0.8$ can be stated that for $\alpha =-1.2$ the mean queue length decreases by 19% for $\rho =2$ and decreases by 3% for $\rho =1$. For $\alpha =-1.0$ the mean queue length decreases by 8% for $\rho =2$ and decreases by 2% for $\rho =1$. Whereas for $\alpha =-0.8$ the mean queue length increases by 6% for $\rho =2$ and increases by 2% for $\rho =1$. On the other hand, the number of discarded packets analyze shows that for traffic with high degree of self-similarity ($H=0.9$ and $H=0.8$) with integral order growth decreases the number of dropped packets (for standard AQM queue, the situation is exactly opposite).

Interesting results were also obtained for the low traffic intensity. The mean queue length grows with integral order decreasing. The Fig. 1 explains these phenomena. The controller response to increasing queue in depends on the queue previous moments. The controller reaction is delayed with the integral order increasing.

Table 2. $PI^{\alpha }$ queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-0.8$

Table 3. $PI^{\alpha }$ queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$

Fig. 3.

The influence of degree of traffic selfsimilarity on queue distribution, $PI^{\alpha }$ queue, queue size = 300, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $\lambda =0.5$, $\mu =0.75$ (left), $\mu =0.5$ (right), $\mu =0.25$ (bottom)

Table 4. $PI^{\alpha }$ queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.2$

Fig. 4.

The influence of degree of traffic selfsimilarity on queue distribution, $PI^{\alpha }$ queue, queue size = 300, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.2$, $\lambda =0.5$, $\mu =0.75$ (left), $\mu =0.5$ (right), $\mu =0.25$ (bottom)

The second phase of the researches shows how derivative term changes the queue occupancy and packet waiting times. The Figs. 5, 6 and 7 present the queue distribution for $PID^{\beta }$ controller ($\alpha =-1$). The results for PI controller were present in Fig. 3 and Table 3. Comparing the figures does not show a significant visual amendments. Differences in the controllers responses show Tables 5, 6 and 7.

The most interesting results were obtained for controller with derivative terms $\beta =0.8$. For high traffic ($\mu =0.25$ and $\mu =0.5$) the controller reduces the mean queue length and at the same time reduces the number of packet losses. The further derivative order increasing (Tables 6 and 7) reduces the mean queue length and at the same time increases number of dropped packets. However, these differences are much smoother as in the case of integral order $\alpha$ decreasing (see Table 4).

Table 5. PID queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $K_D=0.01$, $\beta =0.8$

Fig. 5.

The influence of degree of traffic selfsimilarity on queue distribution, $PI^{\alpha }D^{\beta }$ queue, queue size = 300, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $K_D=0.01$, $\beta =0.8$, $\lambda =0.5$, $\mu =0.75$ (left), $\mu =0.5$ (right), $\mu =0.25$ (bottom)

Table 6. PID queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $K_D=0.01$, $\beta =1.0$

Fig. 6.

The influence of degree of traffic selfsimilarity on queue distribution, $PI^{\alpha }D^{\beta }$ queue, queue size = 300, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $K_D=0.01$, $\beta =1.0$, $\lambda =0.5$, $\mu =0.75$ (left), $\mu =0.5$ (right), $\mu =0.25$ (bottom)

Table 7. PID queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $K_D=0.01$, $\beta =1.2$

Fig. 7.

The influence of degree of traffic selfsimilarity on queue distribution, $PI^{\alpha }D^{\beta }$ queue, queue size = 300, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.0$, $K_D=0.01$, $\beta =1.2$, $\lambda =0.5$, $\mu =0.75$ (left), $\mu =0.5$ (right), $\mu =0.25$ (bottom)

The last phase of the simulation evaluates the impact of derivate term on $PI^{\alpha }$ controller. Controller with integral term $\alpha =-1.2$ is an example of strong mechanism. For this controller the lowest values of mean queue length and waiting times were obtained. At the same time increase the number of dropped packets is insignificant. The results of the controller with derivative term and derivative order $\beta =0.8$ are shown in Fig. 8. Table 8 presents the detailed results. In this case, the controller with derivative term response is softer.

Table 8. PID queue, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.2$, $K_D=0.01$, $\beta =0.8$

Fig. 8.

The influence of degree of traffic selfsimilarity on queue distribution, $PI^{\alpha }D^{\beta }$ queue, queue size = 300, $K_P=0.00115$, $K_I=0.0011$, $\alpha =-1.2$, $K_D=0.01$, $\beta =0.8$, $\lambda =0.5$, $\mu =0.75$ (left), $\mu =0.5$ (right), $\mu =0.25$ (bottom)

4 Conclusions

Our article presents the impact of the degree of self-similarity (ex- pressed in Hurst parameter) on the length of the queue, queue waiting times and the number of rejected packets. Obtained results are closely related to the degree of self-similarity. The experiments are carried out for the four types of traffic ($H=0.5, 0.7, 0.8, 0.9$). During the test we also changed the parameter of distribution of service time. This change allowed us to consider the different queues loading.

The article presents an evaluation of the fractional order $PI^{\alpha }D^{\beta }$ controller used as an active queue management mechanism. The effectiveness of the controller as an AQM mechanism depends on proper parameters of the PID selection. In the case of fractional order controller we need to consider two additional parameters: fractional derivative ($\beta$) and integral ($\alpha$) orders. The controllers behavior was also compared to FIFO queue.

The results showed the usefulness of the $PI^{\alpha }D^{\beta }$ controller as AQM mechanism. The proper selection of the controller parameters is important in adaptation to various types of traffic (degree of self-similarity or various intensity).