Keywords

1 Introduction

The most important factor of the TCP/IP network traffic control is the rejection of packets arriving to an IP router to be queued and send then forward. At first, packets are queued following FIFO algorithm and rejected only when the whole buffer space used to queue the packets was already occupied. Since many years, the recommended by IETF active queue management (AQM) where packets are rejected following a certain algorithm, enhances the efficiency of transfers [20] and cooperates better with TCP congestion window mechanism in adapting the flows intensity to the congestion of the network [2].

In the classic RED algorithms (the basic AQM mechanism) the incoming packet is dropped according to the given by a predefined function. Usually, this function is linear and depends on the queue length [8, 11, 15].

Our previous works proposed to base the probability function on the answer of the \(PI^{\alpha }\) controller [5,6,7, 10, 13]. The considered models were based on the controller with the non-integer integrate/derivative orders.

In this article we reconsider this problem by extending the controller to include variable parameters. Similarly to algorithm DSRED [22] (the well-known variant of the RED algorithm) we divided the queue length into the three separate segments. For each segment we choose a different set of parameters (controller \(PI^{\alpha }\) coefficients and integrate/derivative orders). The first two controllers are weak i.e. for high traffic load the bulk of packets are dropped due to maximal queue size exceeding. The third controller is strong: its main task is to counteract the buffer overloading. Such choice of controllers enables the incremental increase of controller response as a result of growth of the traffic load.

The remainder of the paper is organized as follows: Sect. 2 gives basic notions on active queue management and presents the DSRED algorithm, Sect. 3 presents briefly theoretical basis for \(PI^{\alpha }\) controller. Section 4 discusses numerical results. Some conclusions are given in Sect. 5.

2 The RED and DSRED Algorithms

The RED algorithm was the solution which fundamentally changed the principles of discarding packets in a router queue. In the case of passive queue management newly incoming packets are dropped only when the buffer is totally full. In the case of RED queue packets are rejected earlier - when the queue length exceeds a planned level. The authors of the RED algorithm: Sally Floyd and Van Jacobson [15] suggested that the destiny of this type of mechanism is to cooperate with transport protocols and congestion control mechanisms based on the positive acknowledgment.

Its performance is based on a drop function giving the probability that a packet is rejected. In RED drop function there are two thresholds: \(Min_{th}\) and \(Max_{th}\). The argument avg of this function is a weighted moving average queue length. If \(avg<Min_{th}\), all packets are admitted. 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 a probability of packet rejection in the case of \(avg=Max_{th}\). If \(avg>Max_{th}\) then all packets are dropped. Efficient operation of the RED mechanism is dependent on the proper selection of its parameters. There were several works studying the impact of various parameters on the RED performance.

Many variations of the 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 and according to how to configure and set the parameters of the algorithm.

One of the possibilities is to increase the thresholds number in the queue. In the algorithm DSRED (Double-Slope RED) [22], the bufor is divided into four sections. Three thresholds \(K_l\), \(K_m\) and \(K_h\) (usually \(K_m = (K_l + K_h)/2 \)) and parameter \(\gamma \) determine two slopes of this drop function:

where

$$ \alpha =\frac{2(1-\gamma )}{K_h-K_l}, \qquad \beta =\frac{2\gamma }{K_h-K_l}. $$

The double slope function makes the algorithm more elastic (more parameters to fix); gentle at the beginning (for low congestion) drop function enhances throughput and reduces queue waiting times. The advantages of this algorithm authors presented in [4] (Fig. 1).

Fig. 1.
figure 1figure 1

The probability function of rejection the packet for the DSRED mechanism [4]

Full size image

3 AQM Mechanism Based on Non-integer Order \(PI^{\alpha }\) Controller.

Our papers [5,6,7, 10] describe how to use the response from \(PI^{\alpha }\)(non-integer integral order) to calculate the probability of packet loss. It is described by a formula:

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

where \(K_P, K_I\) are tuning parameters, \(e_k\) is the error in current slot \(e_k = Q_k-Q\), i.e. the difference between current queue \(Q_k\) and desired queue Q.

For standard PI controller (for \(\alpha =-1\) and \(\beta =1\)) the packet dropping probability is defined as follows:

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

In this approach, the dropping probability depends on three parameters: the coefficients for the proportional and integral terms (\(K_p, K_i\)) and integrals (\(\alpha \)) orders.

The Fractional Order Derivatives and Integrals (FOD/FOI) definitions unify the notions 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) [3, 16, 18].

Differintegral is a combined differentiation/integration operator. The q-differintegral of function f, denoted by \(\varDelta ^{q}f\) 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.

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.

For a given sequence \(f_{0}, f_{1}, ..., f_{j}, ..., f_{k}\)

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

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 &{} \text {for }j=0\\ \displaystyle \frac{q(q-1)(q-2)..(q-j+1)}{j!}&{}\text {for}\,\,j=1, 2, \ldots \end{array} \right. \end{aligned}$$
(4)

Articles [5, 7, 10] show that using the non-integer order \(PI^{\alpha }\) controller as AQM mechanism is more efficient in network congestion control than standard RED mechanism and improves the router performance. The approach proposed in the article divides the queue length into several segments and for each of them use a different set of controller coefficients. This solution should result in more flexible behavior of AQM mechanism independently of the network load or long-range dependence of the network traffic.

4 Packet Dropping Scheme Based on the Answer of the Three \(PI^{\alpha }\) Controllers

The AQM algorithms drop packets following a dropping packet function. The choice of the proper coefficients of this function is not easy. These parameters may differ and depend on the network traffic profile.

This problem also exists in the case of the dropping packets functions based on the answers of the \(PI^{\alpha }\) controllers. Our previous works show significant influence of the traffic parameters (intensity and self-similarity) on the choice of the optimal controller parameters. The AQM mechanism should change its parameters during operation as a result of traffic load. One of the possibilities is to change the parameters of the controller as a function of the queue occupancy.

This article presents the DSRED-like solution. We divide the queue length iwith the use of thresholds. Each segment of the queue is controlled by a different \(PI^{\alpha }\) mechanism.

For queue length between 0 and 180 (packets) we use only one controller. For queue length from 180 to 220 the probability of packet dropping is a sum of answers of the first and second controller. When the queue occupancy exceeds 220 the probability is the sum of responses of all three controllers.

The packet dropping probability may be defined as follows:

where

  • \(p_{1}\) - answer of the first controller,

  • \(p_{2}\) - answer of the second controller,

  • \(p_{2}\) - answer of the third controller.

All presented in this article results were obtained using the simulation model. The simulations were done using the Simpy Python packet. To accelerate the calculations the \(PI^{\alpha }\) module was written in C language. During the tests, we analyzed the following parameters of the AQM transmission: the length of the queue and the number of rejected packets. The input traffic intensity \(\lambda = 0.5\) was considered independently of the Hurst parameter. During the tests we changed the Hurst parameter of the input traffic within the range from 0.5 to 0.90. We use a fast algorithm for generating approximate sample paths for a fGn process, first introduced in [17]. After each trace generation the Hurst parameter was estimated with the use of popular self-similarity parameter estimators [9, 12, 14]: the R/S statistic, aggregated variance, periodogram as well known methods with a significant history of use in estimating LRD and wavelet based method, local Whittle’s estimator as newer techniques. Traditional Hurst parameter estimators can be really biased [1, 21]. Additionally, the different implementations of the same method may give varying results [19]. Only Hurst parameter estimator based on wavelets can be treated as unbiased and robust [21].

The Table 1 presents the estimations for sample generated trace with the assumed Hurst parameter. These results show that the assumed and estimated Hurst parameters are not the same. The obtained results changed for subsequent generated samples and differed depending on the method of estimating the Hurst parameter. For all differences in results, the dependence of the increase in the estimated Hurst parameter with the increase in the assumed parameter is clearly visible.

Table 1. Hurst parameter estimates for IITiS data traces
Full size table

The service time represents the time of a packet treatment and dispatching. In packet-switched networks it is the time required to transmit information. We have used discrete-time model, hence we have assumed that service-time distribution is geometric (which corresponds to Poisson traffic in case of continuous time models). The distribution of service time \(\mu \) 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\). Small network traffic was considered for parameter \(\mu =0.75\)

The \(PI^{\alpha }\) controllers coefficients and setpoints presents Table 2. The impact of controller parameters on the behavior of the AQM mechanism and packet dropping probability were described in [5, 13]. In presented solution first and second controllers drop the some packets but mostly the queue size crosses the third threshold. When the queue size exceeded third threshold, the third controller begin to work. The third (strong) controller protects the queue against exceeding the maximum size.

Table 2. \(PI^{\alpha }\) controllers coefficients
Full size table

The distributions of the queue length present Figs. 2 and 3. The Tables 3, 4 and 5 present the detailed results. The results consider the high traffic load (\(\mu \) = 0.25). The Table 3 presents the results for the first controller. In our solution this controller works for the queue occupancy between 0 and 180. The controller parameters were chosen to maximize the queue length. However, the majority of packets are dropped by \(PI^{\alpha }\) mechanism, several packets are dropped due to maximum queue length exceeding. The number of packets dropped by the queue increases with the Hurst parameter. The Table 4 presents the controller that starts when queue length exceeds 180. This controller is weak. The most packets are dropped by the queue. The third controller (Table 5) is very strong. All packets are discarded from the queue by controller mechanism. Obtained results confirmed the assumptions of the controllers behavior.

Table 3. \(PI^{\alpha }\) controller, \(\mu \) = 0.25, \(K_{p}\) = 0.0001, \(K_{i}\) = 0.0004, \(\alpha = -0.4\), setpoint = 100
Full size table
Table 4. \(PI^{\alpha }\) controller, \(\mu \) = 0.25, \(K_{p}\) = 0.0001, \(K_{i}\) = 0.00015, \(\alpha = -0.5\), setpoint = 100
Full size table
Fig. 2.
figure 2figure 2

Distribution of queue length for high traffic load (\(\mu \) = 0.25) and H = 0.5, left: \(K_{p}\) = 0.0001, \(K_{i}\) = 0.00015, \(\alpha = -0.5\), right: \(K_{p}\) = 0.0001, \(K_{i}\) = 0.0004, \(\alpha = -0.4\), center: \(K_{p}\) = 0.0001, \(K_{i}\) = 0.00035, \(\alpha = -0.6\)

Full size image
Fig. 3.
figure 3figure 3

Distribution of queue length for high traffic load (\(\mu \) = 0.25) and H = 0.9, left: \(K_{p}\) = 0.0001, \(K_{i}\) = 0.00015, \(\alpha = -0.5\), right: \(K_{p}\) = 0.0001, \(K_{i}\) = 0.0004, \(\alpha = -0.4\), center: \(K_{p}\) = 0.0001, \(K_{i}\) = 0.00035, \(\alpha = -0.6\)

Full size image
Table 5. \(PI^{\alpha }\) controller, \(\mu \) = 0.25, \(K_{p}\) = 0.0001, \(K_{i}\) = 0.00035, \(\alpha = -0.6\), setpoint = 100
Full size table

The proposed solution sums the behavior of all three presented above controllers. The packet dropping probability increases with assumed thresholds.

Tables 6, 7 and 8 present obtained results for different traffic intensity. The Table 6 presents the overloaded network. Although two first controllers drop most packets, the queue length exceeds the third threshold. The advantage of this solution is a small reaction of the first and second \(PI^{\alpha }\) in the case of highly variable traffic. For \(H=0.90\) the most packets are dropped by third \(PI^{\alpha }\). Independently of the degree of self-similarity, no packets are dropped by the queue.

The Table 7 presents the results in the case of the average traffic load. The average queue length does not exceed 80 packets (independently of the traffic self-similarity). However, the detailed results suggest that temporarily the queue length exceeds the third thresholds. The number of dropped packet by second and third controller grows with the degree od self-similarity. This phenomenon is caused by high variability of queue occupancy. This variability grows with Hurst parameter.

The average queue length for small network traffic (Table 8) is the largest in the case of \(H=90\). The queue length never exceeds the third threshold. All packets are dropped by two earlier controllers. The queue length exceeds the firt threshold only in case of degree of self-similarity (expressed in Hurst parameter) exceeds 0.8.

Fig. 4.
figure 4figure 4

The influence of degree of traffic self-similarity on queue distribution, three \(PI^{\alpha }\) controllers, \(\mu =0.75\) (left), \(\mu =0.5\) (right), \(\mu =0.25\) (bottom)

Full size image
Table 6. Three \(PI^{\alpha }\) controllers, \(\mu \) = 0.25
Full size table
Table 7. Three \(PI^{\alpha }\) controllers, \(\mu \) = 0.50
Full size table
Table 8. Obtained results for the input traffic intensity \(\mu \) = 0.75
Full size table

Figure 4 presents distributions of the queue lengths depended on the traffic intensity and the degree of self-similarity.

5 Conclusions

The Internet Engineering Task Force (IETF) organization recommends that IP routers should use the active queue management mechanisms (AQMs). The basic algorithm for AQM is the RED algorithm. There are many modifications and improvements to the RED mechanism. One of these improvements is the calculation of the probability of packet loss using a \(PI^{\alpha }\) controller. Our previous work has shown the advantage of this solution [5, 10].

This paper introduces a new way of packet rejecting probability calculation based on the answer of three the non-integer order \(PI^{\alpha }\) controllers. The additional controllers start to work when the queue occupancy exceeds the assumed threshold. The behavior of the proposed solution was also compared to the behavior of the queue controlled by a single \(PI^{\alpha }\) controller. Obtained results show the advantage of such a solution. Individually, the \(PI^{\alpha }\) controllers presented in the article are poorly adjusted to the network traffic. The first and the second controller did not work properly in the case of high traffic intensity. Most packets were dropped due to exceeding the maximum queue size. The reaction of the third controller was too strong. In the case of low traffic intensity the number of discarded packets was redundant. Only the combination of described above controllers allowed to design more flexible AQM mechanism.

Our article presents also the impact of the degree of self-similarity (expressed in the Hurst parameter) on the length of the queue 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\)). Additionally, we evaluate the number of dropped packets in assumed queue segments. This results allowed to select the desired parameters of the controller.

The results described in this article confirm that our approach increases the efficiency of the AQM mechanism based on the \(PI^{\alpha }\) controller. In presented solution we refere mainly to the queue occupancy. In our future work we will focus on mechanisms based on the evaluation of the network traffic parameters and the selection of controller parameters according to the intensity or the self-similarity of the network traffic.