# An Improved ARED Algorithm for Congestion Control of Network Transmission

Authors: Jianyong Chen; Cunying Hu; Zhen Ji
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

In order to achieve high throughput and low average delay in computer network, it is necessary to stabilize the queue length and avoid oscillation or chaos phenomenon. In this paper, based on Adaptive Random Early Detection (ARED), an improved algorithm is proposed, which dynamically changes the range of maximum drop probabilitypmax according to different network scenarios and adjusts pmax to limit average queue size qave in a steady range. Moreover, exponential averaging weight w is adjusted based on linear stability condition to stabilize qave. A number of simulations show that the improved ARED algorithm can effectively stabilize the queue length and perform better than other algorithms in terms of stability and chaos control.


---

## Body

## 1. Introduction

In the current internet, congestion control has been a serious problem. Lack of effective management of congestion significantly affects the performance of internet, such as degradation of link utilization, more round-trip time, and even makes the network inaccessible. At the same time, various approaches have been proposed to solve the issue. These schemes can be divided into two categories. One category strengthens congestion management at the end while making few changes to internet [1, 2]. The other one aims to adapt Active Queue Management (AQM) at each router, and eventually control congestion level, such as Random Early Detection (RED) [3], Random Early Marking (REM) [4] and Virtual Queue (VQ) [5, 6]. Among them, RED is the most prominent and well-studied AQM scheme. Though RED can prevent global synchronization, reduce packet loss, and achieve high throughput, it induces oscillation or chaos to degrade the performance of the system in some network scenarios. The stability of RED gains more and more researchers’ attentions.The main goal of AQM is to keep queue length stable in order to make a good tradeoff between high throughput and low delay. As a queue management policy, RED gateway manages queue by monitoring the average queue sizeqave. When qave exceeds the preset lower threshold qmin, arriving packets are randomly dropped or marked with a certain probability, so that some connections can sense the early congestion, and then adjust their window sizes to avoid serious congestion and packet lost. Once the average queue size is larger than the upper threshold qmax, the RED gateway drops/marks every arriving packet to keep qave below qmax. Although the RED algorithm is an effective mechanism to achieve high throughput and low delay, some researches note that RED is quite sensitive to traffic load and RED parameters [7–9], and that the average queue length exhibits nonlinear instability and chaos [10–13]. In particular, when the average queue becomes larger than the upper threshold qmax, qave fluctuates seriously, leading to low throughput and large packet loss rate. Many modified RED algorithms are proposed to eliminate oscillations or chaos to improve its robustness by revising the drop probability function or by adjusting control parameters.Among these algorithms, one set of approaches are to modify the packet drop probability function to improve the stability of RED and its performances [14–18]. Particularly, Hollot et al. proposed a PI-controller (Proportional-Integral controller) to improve reaction of TCP-RED dynamics [15]. Besides that, the authors proposed LRED (Loss Ratio-based RED) in [18], which takes into account the dropping probability based on loss rate and queue length rather than average queue size. These modified algorithms outperform original RED in terms of better stability and higher throughput. However, these methods always induce additional parameters that are needed to be optimized to stabilize the queue length in different network scenarios. The setting of parameters is still an unsolved problem. Another set of algorithms does not change the basic idea of RED, but tunes the control parameters to improve the stability of the queue length [8, 9, 12, 13, 19–23]. Feng et al. have argued that there is no single set of RED parameters that can work well under different congestion scenarios. In [8], they proposed original ARED, which tunes the parameter pmax based on network traffic to keep the average queue size qave between the upper threshold qmax and lower threshold qmin. Floyd et al. present a revised version, also called Adaptive RED [9], which adopts AIMD mechanism to change pmax slowly. Although ARED can stabilize the queue length at a given target and achieve high throughput in some networks, ARED does not provide any systematic methods to set parameters and the target. Furthermore, the control parameter selection is based only on empirical observation and simulation analysis. As a result, it performs well in one simulation, but fails in another. Besides that, some researches propose other variants of RED, such as SARED (Stabilized ARED) [19], PD-RED [20], while others discuss the bound of pmax [21–23]. These algorithms keep the queue length stable in some network scenarios by dynamically tuning parameters, but they fail to control the fluctuation and chaos in others.In the paper, we analyze the steady range ofqave and its linear stability condition, and propose a novel improved ARED algorithm. The improved ARED constrains pmax in a more reasonable range according to both the steady range and the target range of ARED. What is more, the improved ARED also decreases w to stabilize qave based on linear stability condition. By stabilizing qave within target range, the improved ARED algorithm could get high link utilization, more stable delay with less delay jitter. The rest of the paper is organized as follows. In Section 2, RED algorithm and a discrete-time TCP-RED model are introduced. Then we analyze linear stability condition of the average queue size. In Section 3, an improved ARED algorithm is proposed based on ARED algorithm, and the settings of the control parameters pmax and w are discussed in detailed. Section 4 presents simulations results and discusses the performance of various AQM schemes. Finally, we present the conclusions in Section 5.


## 2. Discrete-Time TCP-RED Model

In this paper, the network topology used is a dumbbell with a single bottleneck as shown in Figure1. There are N connections sharing a single link with the capacity C. It is assumed that these connections are identical, long-lived, and have the same round-trip propagation delay d.Figure 1
Structure of the network.


### 2.1. Random Early Detection (RED)

RED is a recommended scheme of AQM by the Internet Engineering Task Force (IETF) [3]. The main goal of RED is to achieve low average delay and high throughput. In order to achieve the goal, the RED gateway always measures qave, and drops/marks the arriving packets with the probability p to notify the TCP end of the incipient congestion when qave>qmin. Once qave>qmax, RED gateway drops every arriving packet so that it can control the average queue size even in the absence of cooperating sources. The drop probability p with RED can be described by the following piecewise function [3]:
(2.1)p={0qave<qmin,1qave>qmax,qave-qminqmax-qminpmaxqmin<qave<qmax.
Here pmax is the drop probability when qave is equal to qmax, and also called the maximum drop probability. qmax and qmin are the expected upper and lower thresholds, respectively. qave can be got with the following equation [3]:
(2.2)qave=(1-w)qave′+wq.
Here, qave′ is average queue size at the previous time. q is instantaneous queue length. w is exponential averaging weight which is limited at [0,1]. qave is updated at the time of packet arrival [3].


### 2.2. Discrete-Time Feedback Model for TCP-RED

To better understand the nonlinear instability in TCP-RED, Ranjan et al. have developed a discrete-time dynamical feedback TCP-RED model [11]. It is assumed that RED queue management mechanism with Explicit Congestion Notification (ECN) capability is implemented at each node to provide congestion signal. According to the model, the instantaneous queue size q can be determined by some network parameters, such as the buffer size B, mean packet size M, the number of connections N, and a constant K in [1, (8/3)0.5]. qave can be expressed mathematically as [11]
(2.3)qave=f(qave′)={(1-w)qave′qave≥q1,(1-w)qave′+wBqave≤q2,(1-w)qave′+w(NKp-CdM)otherwise.
Here q1=p1(qmax-qmin)pmax+qmin, where p1=(NMK/(dC))2 is the minimum drop rate that leads to an empty queue at next time. q2=p2(qmax-qmin)/pmax+qmin, where p2=(NMK/(dC+BM))2 is the maximum drop probability with full queue at next time. Cis the capacity of the shared link, and d is round-trip propagation delay. The parameterp can be calculated by (2.1):In the discrete-time model, it is noted that the average queue size is updated over time scale of approximately one RTT (round-trip time) [10, 11]. It is much longer than typical interarrival times of packets in practice. Therefore, win the model is much larger.


### 2.3. Instability in TCP-RED

The interaction between TCP and RED is proved to be rather complex and nonlinear [11, 24]. In recent years, some novel approaches are proposed to better understand the complex and nonlinear phenomena in practice [25–27], which may be used to explain the nonlinear phenomena in TCP-RED. In this section, the complex behavior with RED parameters variation is analyzed based on the associated eigenvalue that is presented as follows.If the average queue size stabilizes at a valueqave, that is, qave=f(qave), the fixed point qave must lie in the range [q2, q1]. That can be obtained from (2.3). Considering the associated eigenvalue λ corresponding to qave, the linear stability condition is |λ|<1 [11]. 								(2.4)|λ|=|∂f(qave)∂qave|qave|=|1-w-wNK2v(qave-qmin)3/2|<1.
Here, v=pmax/(qmax-qmin) means the increase factor of p. Figures 2 and 3 plot the average queue size and the associated eigenvalue for a fixed point qave*=345.1, as w varies from 0.12 to 0.2. In simulation, the parameters are the same as in [11]: C=75 Mb/s, K=(3/2)0.5,M=4, 000b,d=0.1 s, N=250,qmax=750 packets,qmin=250 packets, B=3750 packets, pmax=0.1.Figure 2
Bifurcation diagram of average queue size.Figure 3
Absolute value of the associated eigenvalue.From Figures2 and 3, it is evident that for w<0.1578, qave converges to the fixed point qave*=345.1. At the same time, |λ| also stays below 1. As w increases, PDB (period doubling bifurcation) emerges from the fixed point, and then chaos appears with |λ|>1. It implies that if |λ|>1 for qave, the average queue size is instable at the point. In other words, the point is not a fixed one. The system oscillates and even exhibits chaos phenomenon.Because all the parameters in (2.4) are positive, λ must be smaller than 1. The linear stability can be rewritten as λ>-1, that is,
(2.5)λ=1-w-wNK2v(qave-qmin)3/2>-1.


## 2.1. Random Early Detection (RED)

RED is a recommended scheme of AQM by the Internet Engineering Task Force (IETF) [3]. The main goal of RED is to achieve low average delay and high throughput. In order to achieve the goal, the RED gateway always measures qave, and drops/marks the arriving packets with the probability p to notify the TCP end of the incipient congestion when qave>qmin. Once qave>qmax, RED gateway drops every arriving packet so that it can control the average queue size even in the absence of cooperating sources. The drop probability p with RED can be described by the following piecewise function [3]:
(2.1)p={0qave<qmin,1qave>qmax,qave-qminqmax-qminpmaxqmin<qave<qmax.
Here pmax is the drop probability when qave is equal to qmax, and also called the maximum drop probability. qmax and qmin are the expected upper and lower thresholds, respectively. qave can be got with the following equation [3]:
(2.2)qave=(1-w)qave′+wq.
Here, qave′ is average queue size at the previous time. q is instantaneous queue length. w is exponential averaging weight which is limited at [0,1]. qave is updated at the time of packet arrival [3].


## 2.2. Discrete-Time Feedback Model for TCP-RED

To better understand the nonlinear instability in TCP-RED, Ranjan et al. have developed a discrete-time dynamical feedback TCP-RED model [11]. It is assumed that RED queue management mechanism with Explicit Congestion Notification (ECN) capability is implemented at each node to provide congestion signal. According to the model, the instantaneous queue size q can be determined by some network parameters, such as the buffer size B, mean packet size M, the number of connections N, and a constant K in [1, (8/3)0.5]. qave can be expressed mathematically as [11]
(2.3)qave=f(qave′)={(1-w)qave′qave≥q1,(1-w)qave′+wBqave≤q2,(1-w)qave′+w(NKp-CdM)otherwise.
Here q1=p1(qmax-qmin)pmax+qmin, where p1=(NMK/(dC))2 is the minimum drop rate that leads to an empty queue at next time. q2=p2(qmax-qmin)/pmax+qmin, where p2=(NMK/(dC+BM))2 is the maximum drop probability with full queue at next time. Cis the capacity of the shared link, and d is round-trip propagation delay. The parameterp can be calculated by (2.1):In the discrete-time model, it is noted that the average queue size is updated over time scale of approximately one RTT (round-trip time) [10, 11]. It is much longer than typical interarrival times of packets in practice. Therefore, win the model is much larger.


## 2.3. Instability in TCP-RED

The interaction between TCP and RED is proved to be rather complex and nonlinear [11, 24]. In recent years, some novel approaches are proposed to better understand the complex and nonlinear phenomena in practice [25–27], which may be used to explain the nonlinear phenomena in TCP-RED. In this section, the complex behavior with RED parameters variation is analyzed based on the associated eigenvalue that is presented as follows.If the average queue size stabilizes at a valueqave, that is, qave=f(qave), the fixed point qave must lie in the range [q2, q1]. That can be obtained from (2.3). Considering the associated eigenvalue λ corresponding to qave, the linear stability condition is |λ|<1 [11]. 								(2.4)|λ|=|∂f(qave)∂qave|qave|=|1-w-wNK2v(qave-qmin)3/2|<1.
Here, v=pmax/(qmax-qmin) means the increase factor of p. Figures 2 and 3 plot the average queue size and the associated eigenvalue for a fixed point qave*=345.1, as w varies from 0.12 to 0.2. In simulation, the parameters are the same as in [11]: C=75 Mb/s, K=(3/2)0.5,M=4, 000b,d=0.1 s, N=250,qmax=750 packets,qmin=250 packets, B=3750 packets, pmax=0.1.Figure 2
Bifurcation diagram of average queue size.Figure 3
Absolute value of the associated eigenvalue.From Figures2 and 3, it is evident that for w<0.1578, qave converges to the fixed point qave*=345.1. At the same time, |λ| also stays below 1. As w increases, PDB (period doubling bifurcation) emerges from the fixed point, and then chaos appears with |λ|>1. It implies that if |λ|>1 for qave, the average queue size is instable at the point. In other words, the point is not a fixed one. The system oscillates and even exhibits chaos phenomenon.Because all the parameters in (2.4) are positive, λ must be smaller than 1. The linear stability can be rewritten as λ>-1, that is,
(2.5)λ=1-w-wNK2v(qave-qmin)3/2>-1.


## 3. The Improved ARED Algorithm

In this section, we first briefly introduce ARED algorithm, and then propose a novel improved ARED algorithm. At last, we give a theoretic analysis for the proposed algorithm.


### 3.1. Adaptive RED

In 2001, Floyd et al. proposed a modified version of the original ARED (Adaptive RED), also called ARED [9]. To ensure high throughput and low delay, they set a target range with [qmin+0.4(qmax-qmin), qmin+0.6(qmax-qmin)]. When the current average queue size is not in the range, the control parameter pmax is revised by AIMD (additive-increase multiplicative-decrease) policy, which can be expressed mathematically as:
(3.1)pmax={pmax+α,qave>qtarget,pmax<0.5,pmaxβ,qave<qtarget,pmax≥0.01.
Here, qtarget is the target range. ARED changes pmax slowly, and the time scale is larger than interarrival time in original ARED. In general, the parameter interval = 0.5 seconds. Based on the principle that the change of qave should not be larger than the range of target in single interval [9], Floyd et al. advised to set α=min(0.01, pmax/4) and β=0.9. Besides that, pmax is constrained within the range [0.01, 0.5], so that the overall performance of RED could be still acceptable in the transition period, even though the average queue size is out of the target range. A lot of experiments demonstrate that ARED has a good performance in terms of stability and robustness [9]. However, the parameter w and the bound of pmax are configured according to some experiment results. Therefore, ARED works well in some network scenarios but fails in others.


### 3.2. The Improved ARED Algorithm

Since ARED adjustspmax by monitoring whether qave is within the target range, it is sensitive to the change of qave. Besides that, it causes oscillation when w is improper. In the section, we propose a novel ARED, named improved ARED, to reduce the parametric sensitivity and traffic sensitivity. The algorithm is described in Algorithm 1.Algorithm 1:Improved ARED algorithm
Everyinterval seconds:if(qave>qtarget&&pmax<pmax_u)pmax=pmax+α;elseif(qave<qtarget&&pmax>pmax_l)pmax=pmax×β;if(qave∈qtarget)Calculateλ by(2.4)if (λ<-1&&w>wmin)w=w×γ;Parameters:pmax_u: the upper threshold of  pmax; p1/0.6pmax_l: the lower threshold of  pmax; p2/0.4γ: decrease factor of wwmin: the lower threshold of w; 1-exp(-1/(10Cd/M))Other parameters are the same as those with Adaptive REDThere are two main differences between ARED and the improved ARED: (1) pmax is constrained in the range [p2/0.4,p1/0.6] in the improved ARED, instead of the range [0.01, 0.5] in ARED, (2) w is also adjusted in the improved ARED, when the linear stability condition is not satisfied and qave stays in the steady range.


### 3.3. Maximum Drop Probabilitypmax

Base on the discussion in Section2.3, one can see that qave is stable only when it is in the range [q2, q1] and λ at the point is below −1. In order to stabilize qave, it is necessary to ensure qave∈[q2,q1]. If the target range in ARED is constrained in the steady range [q2, q1], pmax could be adjusted effectively to keep qave in the range. In the case, the two following inequalities are obtained:
(3.2)q2<qmin+0.4(qmax-qmin),q1>qmin+0.6(qmax-qmin).Substitutingq1=p1(qmax-qmin)/pmax+qmin and q2=p2(qmax-qmin)/pmax+qmin into (3.2), we obtain the range of pmax:
(3.3)p20.4<pmax<p10.6.By the way, the drop mechanism with ARED can keepqave within the steady range [q2, q1], so the stability of qave depends on the value of λ from (2.5). Figure 4 shows the drop probability with the improved ARED algorithm.Figure 4
Drop probability of the improved ARED algorithm.


### 3.4. Exponential Averaging Weightw

The inequality (2.5) shows that λ depends on control parameters (qmax, qmin, w, pmax), system parameter N, the constant K and qave. Since the number of connections N is out of control, a network manager usually changes control parameters to stabilize qave. The thresholds qmin and qmax refer to the tradeoffs between throughput and delay, and they are constants in general. Thus, they are set in advance. The control parameters pmax is adjusted by ARED scheme. Therefore, wbecomes the only parameter to be chosen to achieve the stability of qave. Since λ is a monotony decrease function of w from (2.5), λ>-1 can be ensured by decreasing w when λ is below −1. In other words, the linear stability of qave can be obtained by decreasing w.On the other hand, ifw is too small, the average queue size cannot reflect the change of instantaneous queue size, so that RED gateway cannot detect the early congestion. In order to avoid too mall of w, a lower threshold wmin=1-exp(-1/(10Cd/M)) is used [9]. Besides that, multiplicative-decrease policy is used to reduce w quickly.


## 3.1. Adaptive RED

In 2001, Floyd et al. proposed a modified version of the original ARED (Adaptive RED), also called ARED [9]. To ensure high throughput and low delay, they set a target range with [qmin+0.4(qmax-qmin), qmin+0.6(qmax-qmin)]. When the current average queue size is not in the range, the control parameter pmax is revised by AIMD (additive-increase multiplicative-decrease) policy, which can be expressed mathematically as:
(3.1)pmax={pmax+α,qave>qtarget,pmax<0.5,pmaxβ,qave<qtarget,pmax≥0.01.
Here, qtarget is the target range. ARED changes pmax slowly, and the time scale is larger than interarrival time in original ARED. In general, the parameter interval = 0.5 seconds. Based on the principle that the change of qave should not be larger than the range of target in single interval [9], Floyd et al. advised to set α=min(0.01, pmax/4) and β=0.9. Besides that, pmax is constrained within the range [0.01, 0.5], so that the overall performance of RED could be still acceptable in the transition period, even though the average queue size is out of the target range. A lot of experiments demonstrate that ARED has a good performance in terms of stability and robustness [9]. However, the parameter w and the bound of pmax are configured according to some experiment results. Therefore, ARED works well in some network scenarios but fails in others.


## 3.2. The Improved ARED Algorithm

Since ARED adjustspmax by monitoring whether qave is within the target range, it is sensitive to the change of qave. Besides that, it causes oscillation when w is improper. In the section, we propose a novel ARED, named improved ARED, to reduce the parametric sensitivity and traffic sensitivity. The algorithm is described in Algorithm 1.Algorithm 1:Improved ARED algorithm
Everyinterval seconds:if(qave>qtarget&&pmax<pmax_u)pmax=pmax+α;elseif(qave<qtarget&&pmax>pmax_l)pmax=pmax×β;if(qave∈qtarget)Calculateλ by(2.4)if (λ<-1&&w>wmin)w=w×γ;Parameters:pmax_u: the upper threshold of  pmax; p1/0.6pmax_l: the lower threshold of  pmax; p2/0.4γ: decrease factor of wwmin: the lower threshold of w; 1-exp(-1/(10Cd/M))Other parameters are the same as those with Adaptive REDThere are two main differences between ARED and the improved ARED: (1) pmax is constrained in the range [p2/0.4,p1/0.6] in the improved ARED, instead of the range [0.01, 0.5] in ARED, (2) w is also adjusted in the improved ARED, when the linear stability condition is not satisfied and qave stays in the steady range.


## 3.3. Maximum Drop Probabilitypmax

Base on the discussion in Section2.3, one can see that qave is stable only when it is in the range [q2, q1] and λ at the point is below −1. In order to stabilize qave, it is necessary to ensure qave∈[q2,q1]. If the target range in ARED is constrained in the steady range [q2, q1], pmax could be adjusted effectively to keep qave in the range. In the case, the two following inequalities are obtained:
(3.2)q2<qmin+0.4(qmax-qmin),q1>qmin+0.6(qmax-qmin).Substitutingq1=p1(qmax-qmin)/pmax+qmin and q2=p2(qmax-qmin)/pmax+qmin into (3.2), we obtain the range of pmax:
(3.3)p20.4<pmax<p10.6.By the way, the drop mechanism with ARED can keepqave within the steady range [q2, q1], so the stability of qave depends on the value of λ from (2.5). Figure 4 shows the drop probability with the improved ARED algorithm.Figure 4
Drop probability of the improved ARED algorithm.


## 3.4. Exponential Averaging Weightw

The inequality (2.5) shows that λ depends on control parameters (qmax, qmin, w, pmax), system parameter N, the constant K and qave. Since the number of connections N is out of control, a network manager usually changes control parameters to stabilize qave. The thresholds qmin and qmax refer to the tradeoffs between throughput and delay, and they are constants in general. Thus, they are set in advance. The control parameters pmax is adjusted by ARED scheme. Therefore, wbecomes the only parameter to be chosen to achieve the stability of qave. Since λ is a monotony decrease function of w from (2.5), λ>-1 can be ensured by decreasing w when λ is below −1. In other words, the linear stability of qave can be obtained by decreasing w.On the other hand, ifw is too small, the average queue size cannot reflect the change of instantaneous queue size, so that RED gateway cannot detect the early congestion. In order to avoid too mall of w, a lower threshold wmin=1-exp(-1/(10Cd/M)) is used [9]. Besides that, multiplicative-decrease policy is used to reduce w quickly.


## 4. Simulations

The instability of RED schemes comes from its parametric sensitivity and traffic sensitivity. In other words, RED scheme is very sensitive to control parameters (w, qmin) and system parameters (N, d). In this section, we test the performance of the improved ARED, the gentle RED, and ARED when these parameters vary in a large range. The three algorithms use the discrete-time TCP-RED model for simulation, and are evaluated by the stability of qave. The parameters in simulation are the same as in [11]: C=75 Mb/s, K=(3/2)0.5,M=4,000b,d=0.1s,N=250,qmax=750 packets,qmin=250 packets,B=3750 packets, w=0.15, pmax=0.1, γ=08 except special descriptions. Besides that, because the instant of observation is about one RRT [10, 11], pmax is updated after every 5 iterations. It is roughly 0.5 seconds for both the improved ARED and ARED.


### 4.1. Control Parameters(w,qmin)

In the subsection, we test the parametric sensitivity of various algorithms. The plots in Figure5 present the average queue size when wvaries from 0.12 to 0.34 for the gentle RED, ARED and the improved ARED, respectively. Figure 5(a) shows that for gentle RED, qave can be stabilized at 345.1 with a small w. As w increases, qave becomes instable, and then PDB appears. When w is larger than 0.164, qave exhibits chaos phenomenon. ARED cannot stabilize qave within the target range until w>0.334 as shown in Figure 5(b). It implies that ARED is more stable than gentle RED when w varies. However, it also leads to PDB and chaos. From Figure 5(c), it is found that the improved ARED keeps qave stable at a point within target range when w is set at different values. The experiments show that the robustness of the improved ARED is better than Adaptive RED and gentle RED in terms of w.Average queue sizeqave versus w.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithmIn simulations, ARED can stabilizeqave with a larger wcompared with gentle RED because pmax with ARED is adjusted dynamically. However, when w is larger than some critical values, qave is more sensitive to the change of queue length, and thus changes fast. As a result, ARED gateway frequently adjusts pmax that leads to oscillation. In the same case, the improved ARED decreases w according to the linear stability condition besides adjusting pmax. Therefore, the performance of the improved ARED outperforms ARED.Figure6 demonstrates the change of the average queue size for various algorithms with the variation of qmin. From these figures, it is evident that gentle RED does a poor job in terms of stability due to the constant pmax. However, both ARED and the improved ARED perform better in eliminating oscillations and chaos when the lower threshold changes from 250 to 550. When qmin is near 500 packets, ARED exhibits oscillations as shown in Figure 6(b). That is because the target range [qmin+0.4(qmax-qmin), qmin+0.6(qmax-qmin)] shrinks as qmin increases, which means that qave stays within the range with a smaller probability. Under this condition, pmax fluctuates frequently, so qave fluctuates too. However, the improved ARED changes the value of wbased on linear stability condition to reduce the effect of the queue length on qave, and then reduce the fluctuation of pmax. By doing so, the improved RED degrades the sensitivity of qmin to some extent, and improves the stability of qave compared with ARED and gentle RED, as shown in Figure 6(c).Average queue sizeqave versus qmin.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithm


### 4.2. System Parameters(N,d)

In this subsection, we test the stability and robustness of different algorithms under different network loadN and different round-trip propagation delay d.Figure7 shows the average queue size when N increases from 100 to 1500. From Figure 7(a), it is evident that the system is difficult to stabilize qave with small N. As N increases, the system is more stable and qave stabilizes at a larger value. These results are consistent with that in [28]. However, if N continues to increase without constrain, there exists a value of N with qave near 2qmax, which corresponds to the drop probability of 1 for gentle RED. Once N exceeds the value, qave oscillates [8]. Therefore, the system can stabilize qave only if N varies in some range when other parameters are determined. Figure 7(b) shows that qave of ARED is stable when N∈[520,1080]. However it increases when N>1080 and oscillates when N<520. In the simulations, the improved ARED can keep qave stable in the target range with N∈[100,1500], as shown in Figure 7(c).Average queue sizeqave versus N.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithmFor smallN, ARED and the improved ARED decrease pmax to reduce the effect of single source on traffic so they can achieve good stability. For large N, a lot of packets need to be dropped to trigger enough congestion signals with a large drop probability. For the improved ARED, both p1 and p2 will increase accordingly, and the bounds of pmax will be enlarged as shown in (3.3). Therefore, the improved ARED can provide enough congestion signal by adapting a larger pmax. However, the upper threshold of pmax is set to 0.5 for ARED, so it is ineffective to provide a large enough drop probability with N>1080. Therefore, the improved algorithm can get better performance in the simulations.The plots in Figure8 show the average queue size with respect to the round-trip propagation delay. For gentle RED, larger d results in instability as shown in Figure 8(a), because it takes more time to transmit an early congestion signal. After the ends receive the congestion signals, a lot of packets have been sent out, caused more serious congestion with a long queue length. On the other hand, when the system recovers from congestion, the ends may still decrease sending rate, due to the delay arrival of congestion signals sent at the previous time. In this case, the average queue size will be very small and the network resource cannot be fully utilized. In the experiments, both ARED and the improved ARED can reduce aggressiveness of drop mechanism through decreasing pmax that makes qave enter into stability slowly. Figures 8(b) and 8(c) also verify that both algorithms are effective in control of oscillation and chaos.Average queue sizeqave versus d.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithm


## 4.1. Control Parameters(w,qmin)

In the subsection, we test the parametric sensitivity of various algorithms. The plots in Figure5 present the average queue size when wvaries from 0.12 to 0.34 for the gentle RED, ARED and the improved ARED, respectively. Figure 5(a) shows that for gentle RED, qave can be stabilized at 345.1 with a small w. As w increases, qave becomes instable, and then PDB appears. When w is larger than 0.164, qave exhibits chaos phenomenon. ARED cannot stabilize qave within the target range until w>0.334 as shown in Figure 5(b). It implies that ARED is more stable than gentle RED when w varies. However, it also leads to PDB and chaos. From Figure 5(c), it is found that the improved ARED keeps qave stable at a point within target range when w is set at different values. The experiments show that the robustness of the improved ARED is better than Adaptive RED and gentle RED in terms of w.Average queue sizeqave versus w.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithmIn simulations, ARED can stabilizeqave with a larger wcompared with gentle RED because pmax with ARED is adjusted dynamically. However, when w is larger than some critical values, qave is more sensitive to the change of queue length, and thus changes fast. As a result, ARED gateway frequently adjusts pmax that leads to oscillation. In the same case, the improved ARED decreases w according to the linear stability condition besides adjusting pmax. Therefore, the performance of the improved ARED outperforms ARED.Figure6 demonstrates the change of the average queue size for various algorithms with the variation of qmin. From these figures, it is evident that gentle RED does a poor job in terms of stability due to the constant pmax. However, both ARED and the improved ARED perform better in eliminating oscillations and chaos when the lower threshold changes from 250 to 550. When qmin is near 500 packets, ARED exhibits oscillations as shown in Figure 6(b). That is because the target range [qmin+0.4(qmax-qmin), qmin+0.6(qmax-qmin)] shrinks as qmin increases, which means that qave stays within the range with a smaller probability. Under this condition, pmax fluctuates frequently, so qave fluctuates too. However, the improved ARED changes the value of wbased on linear stability condition to reduce the effect of the queue length on qave, and then reduce the fluctuation of pmax. By doing so, the improved RED degrades the sensitivity of qmin to some extent, and improves the stability of qave compared with ARED and gentle RED, as shown in Figure 6(c).Average queue sizeqave versus qmin.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithm


## 4.2. System Parameters(N,d)

In this subsection, we test the stability and robustness of different algorithms under different network loadN and different round-trip propagation delay d.Figure7 shows the average queue size when N increases from 100 to 1500. From Figure 7(a), it is evident that the system is difficult to stabilize qave with small N. As N increases, the system is more stable and qave stabilizes at a larger value. These results are consistent with that in [28]. However, if N continues to increase without constrain, there exists a value of N with qave near 2qmax, which corresponds to the drop probability of 1 for gentle RED. Once N exceeds the value, qave oscillates [8]. Therefore, the system can stabilize qave only if N varies in some range when other parameters are determined. Figure 7(b) shows that qave of ARED is stable when N∈[520,1080]. However it increases when N>1080 and oscillates when N<520. In the simulations, the improved ARED can keep qave stable in the target range with N∈[100,1500], as shown in Figure 7(c).Average queue sizeqave versus N.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithmFor smallN, ARED and the improved ARED decrease pmax to reduce the effect of single source on traffic so they can achieve good stability. For large N, a lot of packets need to be dropped to trigger enough congestion signals with a large drop probability. For the improved ARED, both p1 and p2 will increase accordingly, and the bounds of pmax will be enlarged as shown in (3.3). Therefore, the improved ARED can provide enough congestion signal by adapting a larger pmax. However, the upper threshold of pmax is set to 0.5 for ARED, so it is ineffective to provide a large enough drop probability with N>1080. Therefore, the improved algorithm can get better performance in the simulations.The plots in Figure8 show the average queue size with respect to the round-trip propagation delay. For gentle RED, larger d results in instability as shown in Figure 8(a), because it takes more time to transmit an early congestion signal. After the ends receive the congestion signals, a lot of packets have been sent out, caused more serious congestion with a long queue length. On the other hand, when the system recovers from congestion, the ends may still decrease sending rate, due to the delay arrival of congestion signals sent at the previous time. In this case, the average queue size will be very small and the network resource cannot be fully utilized. In the experiments, both ARED and the improved ARED can reduce aggressiveness of drop mechanism through decreasing pmax that makes qave enter into stability slowly. Figures 8(b) and 8(c) also verify that both algorithms are effective in control of oscillation and chaos.Average queue sizeqave versus d.
(a)
Gentle RED algorithm(b)
ARED algorithm(c)
Improved ARED algorithm


## 5. Conclusions

In this paper, we study the instability of TCP-RED based on a discrete-time feedback system model and propose an improved ARED algorithm in which bounds of the maximum drop probabilitypmax are optimized and the lower threshold of the exponential averaging weight w is adjusted based on linear stability condition. Simulations based on the discrete-time model show that the improved ARED algorithm can stabilize qave effectively in the target range with various values of control parameters (w, qmin) and system parameters (N, d). Compared with the gentle RED and ARED, the improved ARED algorithm is less sensitive to parameters, and performs better than the two schemes in terms of stability. The simulation results imply that the improved ARED can achieve high throughput and less delay.



---

*Source: 329035-2010-04-21.xml*