Keywords

1 Introduction

The development of the Internet is partially based on new solutions for traffic control to improve the Quality of Service (QoS) provided at the network layer. Among others, the studies are related to real-time applications such as Voice over IP or Video on Demand. To ensure QoS, the Internet Engineering Task Force (IETF) has proposed Integrated Services (IntServ) and Differentiated Services (DiffServ) architectures. They include a number of mechanisms, in particular for queue management in routers and the efficiency of the TCP protocol depends largely on them. Queue management may be passive or active. In passive solutions, packets coming to a buffer are rejected only if there is no space in the buffer to store them, hence the senders have no earlier warning on the danger of the increasing congestion and all packets coming during saturation of the buffer are lost.

To enhance the throughput and fairness of a link sharing, also to eliminate the synchronization, the IETF recommends active algorithms of buffer management (Active Queue Management, AQM) [1]. They incorporate mechanisms of preventive packet dropping already when there is still place to store packets, this way advertising that the queue is increasing and the danger of congestion is ahead. The packets are dropped randomly, hence only certain users are notified and the global synchronization of connections is avoided. The probability of packet rejection is increasing with the level of congestion.

The basic active queue management algorithm is Random Early Detection (RED) algorithm. It was primarily proposed in 1993 by Sally Floyd and Van Jacobson [2]. Its performance is based on a drop function giving probability that a packet is rejected. The argument avg of this function is a weighted moving average queue length determined at arrival of a packet:

$$\begin{aligned} avg=(1-w_q)avg'+w_q q \end{aligned}$$

where q is the current queue length, \(avg'\) is the previous value of avg and \(w_q\) is a weight parameter, typically \(w_q<<1\), thus avg varies much more slowly than q. Therefore avg indicates long-term changes of q. If \(avg<Min_\mathrm {th}\), all packets are admitted. If \(Min_\mathrm {th}<avg<Max_\mathrm {th}\), then dropping probability p is increasing linearly:

$$\begin{aligned}` p=p_\mathrm {max}\frac{avg-Min_\mathrm {th}}{Max_\mathrm {th}-Min_\mathrm {th}}. \end{aligned}$$

The value \(p_\mathrm {max}\) corresponds to a probability of packet rejecting at \(avg=Max_\mathrm {th}\). If \(avg>Max_\mathrm {th}\) then all packets are dropped. Dropping probability p is thus dependent on network load.

Efficient operation of the RED mechanism depends on the proper selection of its parameters. There were several works on the impact of various parameters on the RED performance [3] and many variants of RED mechanism were developed to improve its performance [4–6]. They may be classified according to the dropping packet function and according to the parameters of the algorithm. Section 2 briefly reviews the modifications of the RED mechanism studied in this article.

Research related to the Internet traffic aims to provide a better understanding of the modern Internet, inter alia, by presenting the current characteristics of Internet traffic based on a large number of experimental data and introducing the internet traffic models. The understanding of the traffic nature of the modern Internet is important to the Internet community. It supports optimization and development of protocols and network devices, improves the network applications security and the protection of network users.

Measurements and statistical analysis (performed already in the 90s) of packet network traffic show that this traffic displays a complex statistical nature including self-similarity, long-range dependence and burstiness [7–10].

Self-similarity of a process means that the change of time scale does not influence the statistical characteristics of the process. It results in long-distance auto-correlation 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 [11]. They enlarge mean queue lengths at buffers and increase the probability of packet loss, deteriorating this way the quality of services provided by a network.

In consequence, it is needed to propose new or to adapt known types of stochastic processes able to model these negative phenomena in network traffic. Several models have been introduced to imitate self-similar processes in the network traffic. They use fractional Brownian Motion, chaotic maps, fractional Autoregressive Integrated Moving Average (fARIMA), wavelets and multifractals, and processes based on Markov chains: SSMP (Special Semi-Markov Process), MMPP (Markov-Modulated Poisson Process) [12], HMM (Hidden Markov Model) [13]. Section 3 briefly describes the self-similar traffic source used in this article.

2 Our Modifications of the RED Mechanism

Our previous works [14–16] presented a study of the influence of RED modifications on its performance in the presence of self-similar traffic.

In classic RED and its variations described in the literature a packet to be dropped is taken usually from the end of the queue. As Sally Floyd wrote: “when RED is working right, the average queue size should be small, and it shouldn’t make too much difference one way or another whether you drop a packet at the front of the queue or at the tail”. Our article [14] reconsiders the problem of choosing tail or front packets in presence of self-similar traffic.

It was shown that in the case of light non-self-similar traffic the obtained results confirmed the opinion of S. Floyd. If the mean queue length is relatively low, the influence of dropping scheme on queueing time is negligible: the introduction of drop-front strategy gives less then \(1\,\%\) shorter mean queueing time. In the case of heavy traffic, drop from front strategy gives two times shorter mean queueing times. However, when the Poisson traffic is replaced by self-similar one with the same intensity and the same parameters of RED are preserved, the length of the queue increases and the influence of the dropping scheme is more visible: drop from front strategy reduces mean queueing time by about \(16\,\%\) even in the case of light load. This fact confirms the advantage of drop from front strategy if the traffic exhibits the self-similarity.

In [15] we investigated the influence of the self-similarity on the non-linear packet dropping function in a special case of NLRED queues. In the NLRED mechanism the linear packet dropping function is usually replaced by a quadratic function. We introduced a linear combination of independent polynomials of \(3^\mathrm {rd}\) degree:

$$\begin{aligned} p(x,a_1,a_2,p_\mathrm {max}) = \left\{ \begin{array}{l l } 0 &{} \quad \mathrm {for}\quad x< Min_\mathrm {th}\\ \varphi _0(x)+a_1\varphi _1(x)+a_2\varphi _2(x) &{} \quad \mathrm {for} \quad Min_\mathrm {th}\le x\le Max_\mathrm {th}\\ 1 &{} \quad \mathrm {for} \quad x> Max_\mathrm {th} \end{array} \right. \end{aligned}$$

where the set of basis function is defined as follows:

$$\begin{aligned} \varphi _0(x)= & {} p_\mathrm {max}\frac{x-Min_\mathrm {th}}{Max_\mathrm {th}-Min_\mathrm {th}},\\ \varphi _1(x)= & {} (x-Min_\mathrm {th})(Max_\mathrm {th}-x),\\ \varphi _2(x)= & {} (x-Min_\mathrm {th})^2(Max_\mathrm {th}-x). \end{aligned}$$

The process of finding the best values of \(p_\mathrm {max}\), \(a_1\) and \(a_2\) for a given type of traffic may be considered as optimization problem in 3-dimensional space. The experimental results show the existence of one optimal set of values of parameters; self-similarity of network traffic and traffic load have no influence on the choice of the optimal dropping packet function. The results obtained for this optimal set of parameter values demonstrate that the mean waiting time is two and half times shorter compared to the RED mechanism in the case of non-self-similar traffic and it is four times shorter in the case of self-similar traffic.

Then in [16] we investigated the impact of the way how the weighted moving average is defined on the performance of the RED mechanism in the presence of self-similar traffic. The proposed approach, named REDwM, is an extension of RED where the average queue length A(n) at a moment n is given by the first order difference equation

$$\begin{aligned} A(n)&= a_1 A(n-1)+a_2 A(n-2)+ \ldots +a_k A(n-k)\\&\quad + b_0 Q(n)+b_1 Q(n-1)+\ldots +b_m Q(n-m) \end{aligned}$$

where \(a_j\) (\(j=1,\dots ,k\)) and \(b_i\) (\(i=0,\dots ,m\)) are constant, A(l) is the average queue length at the l-th moment of time, and Q(l) is the current length of the packet queue at the l-th moment; \(a_j\) and \(b_i\) are subject to constraints:

$$\begin{aligned} \sum _{j=1}^k a_j+\sum _{i=0}^m b_i = 1 \wedge a_j \ge 0 \wedge b_i \ge 0. \end{aligned}$$

The optimal values of equation coefficients were found during minimization of the score function. The improvements, following numerical experiments, are over \(5\,\%\) if we refer to results given by the classic RED approach (for the assumed score function based on the mean waiting time).

The improvements of the RED mechanism described above may be combined making NLREDwM mechanism. The primary goal of this article is to study its performance.

3 Self-Similar Traffic Source

Previously in [14–16] we used the SSMP markovian traffic source to represent the self-similar traffic. Such Markov based model can generate a self-similar traffic over a finite number of time scales. Here we use fractional Gaussian noise which is an exactly self-similar traffic source.

Fractional Gaussian noise (fGn) has been proposed in [17] as a model 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 [18] and the only stationary Gaussian process being exactly self-similar.

The autocorrelation function of fGn process [7]

$$\begin{aligned} \rho ^{(m)}(k)=\rho (k)=\frac{1}{2} \left[ (k+1)^{2H}-2k^{2H}+(k-1)^{2H}\right] \end{aligned}$$

assures second-order self-similarity.

The synthetic generation of sample paths (traces) of self-similar processes is an important problem [18]. In this paper we use a fast algorithm for generating approximate sample paths for a fGn process, first introduced in [19].

Fig. 1.
figure 1

Maximum and minimum difference between assumed and estimated Hurst parameter

Full size image
Table 1. Estimated Hurst parameters obtained for sample fGn traces generated for assumed Hurst parameter \(H=0.7\)
Full size table

The Hurst parameter H characterizes a process in terms of the degree of self-similarity, the degree increases with the increase of H. Thge value \(H\le 0.5\) denotes the lack of long-range dependence, but the process is still self-similar, [20]. We have generated the sample traces with the Hurst parameter with the range of 0.5 to 0.95. After each trace generation, the parameter was estimated with the use of aggregated variance method [21]. Table 1 presents results of this estimation for 10 generated traces with the Hurst parameter assumed to be equal to 0.7. These results show that the assumed and estimated Hurst parameters are not the same. This situation repeated for each value of Hurst parameter (see Fig. 1).

Table 2. FIFO queue
Full size table

fGn generator usually generates the traffic with a slightly greater Hurst parameter. The difference between assumed and estimated Hurst parameter decreases with the increase of the value of Hurst parameter. For our purpose we chose the samples with the smallest difference.

4 Obtained Results

The simulation model of an appropriate AQM mechanism was prepared with the use of SimPy. SimPy is a process-based discrete-event simulation framework based on the language Python. Its event dispatcher is based on Python’s generators [22]. SimPy is released under the MIT License (free software license originating at the Massachusetts Institute of Technology).

We investigated the influence of combination of modifications described in Sect. 2 on RED performance. We also studied the impact of the degree of self-similarity on the examined AQM mechanisms. 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. The input process, following fGn was based on descrete time slots (1 or 0 arrivals in a time slot), the average interarrival time was 2 time slots. The size of this time slot was our symbolic time unit presented in figures. The service time was geometrically distributed with the average of 4 time slots. That means a heavy charge, leading to the link saturation, as our goal was to study the mechanisms performance at high load intervals. The type of the distributions and their mean values were the same for all Hurst parameters.

Table 2 shows the results obtained for the FIFO queue without any AQM mechanism. The introduction of drop from front strategy gives shorter mean waiting time compared to drop tail strategy. Additionally, an increase in the degree of self-similarity causes an increase in number of rejected packets. The reason of it is bursty nature of self-similar traffic. Figure 2 shows fluctuations of queue length in the case of \(H=0.9\).

Fig. 2.
figure 2

FIFO queue – drop from front, waiting time distribution (top), fluctuations of queue length (bottom), Hurst parameter \(H=0.90\)

Full size image

The same results were obtained in case of the RED queue (see Table 3). The RED parameters were: buffer size 300 packets, threshold values \(Min_\mathrm {th}=100\) and \(Max_\mathrm {th}=200\), \(p_\mathrm {max}=0.1\), \(w=0.02\). We distinguish packets rejected when RED starts dropping packets and packets rejected when the walking average of the queue is at the maximum threshold. Table 3 shows that majority of packets were rejected when the average is at the maximum threshold. The number of packets rejected because of reaching the maximum threshold increased with the increase of Hurst parameter.

Table 3. RED queue
Full size table

Tables 4 and 5 show the results obtained for two sets of parameter values of our NLRED mechanism (described in Sect. 2). The first set of values of parameters (Table 4) refers to the case with the minimal value of average waiting time at the expense of the number of rejected packets (the best case). The second set (Table 5) refers to the case with the maximal value of average waiting time (the worst case). The results obtained for the worst case resemble those obtained for the classical RED mechanism. In the best case all packets are rejected when RED starts dropping packets. In this case the mean waiting time is 1.77 times shorter compared to the RED mechanism (in the case of \(H=0.9\)). The results presented in both tables show the impact of degree of self-similarity on mean queue length, mean waiting time and number of rejected packets. Figures 3 and 4 compare the waiting time distributions and queue length fluctuations (the best case of NLRED) for non-self-similar traffic to the case of self-similar traffic with \(H=0.9\).

Table 4. NLRED queue; \(a1=0.00042\), \(a2=-0.0000038\), \(p_\mathrm {max}=0.855\)
Full size table
Table 5. NLRED queue; \(a1=-0.00008\), \(a2=-0.0000008\), \(p_\mathrm {max}=0.6\)
Full size table
Table 6. NLREDwM mechanism; \(a1=0.00042\), \(a2=-0.0000038\), \(p_\mathrm {max}=0.855\)
Full size table
Table 7. NLREDwM mechanism; \(a1=-0.00008\), \(a2=-0.0000008\), \(p_\mathrm {max}=0.6\)
Full size table
Fig. 3.
figure 3

NLRED – tail drop, waiting time distribution (top), fluctuations of queue length (bottom), \(H=0.50\), \(a1=0.00042\), \(a2=-0.0000038\), \(p_\mathrm {max}=0.855\)

Full size image
Fig. 4.
figure 4

NLRED – tail drop, waiting time distribution (top), fluctuations of queue length (bottom), \(H=0.90\), \(a1=0.00042\), \(a2=-0.0000038\), \(p_\mathrm {max}=0.855\)

Full size image

Tables 6 and 7 show the results obtained for NLREDwM mechanism (best and worse case), which is a combination of our NLRED and REDwM mechanisms (described in Sect. 2). The introduction of modified weighted moving average function gives about \(0.1\,\%\) of changes compared to NLRED. This improvement increases with the increase of Hurst parameter.

5 Conclusions

The article confirms the important impact of the degree of self-similarity (expressed in terms of Hurst parameter) on the following parameters of the transmission with AQM: the length of the queue, queue waiting times and the number of rejected packets. We discuss the problem of choosing the optimal shape of dropping packet function for NLRED algorithm and at the same time investigate the influence of the weighted moving average on packet waiting time reduction for this NLRED mechanism.

Drop from front strategy, when applied in place of tail drop one, results in reduction of packet waiting time in examined AQM mechanism. Obtained results are closely related to the level of self-similarity. Hence the application of presented AQM mechanism may be recommended for bursty traffic connections with real-time requirements.