DOI : 10.17577/IJERTCONV3IS22016
- Open Access
- Total Downloads : 16
- Authors : Varadharajan D, Jeyasekar A
- Paper ID : IJERTCONV3IS22016
- Volume & Issue : NCEASE – 2015 (Volume 3 – Issue 22)
- Published (First Online): 24-04-2018
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
Reducing Mismatch Between Average and Current Queue Size using SSQRED in RED Gateways
Varadharajan D, Jeyasekar A
Dept. Of CSE, St.Anness College Of Engineering and Technology, Panruti, India.
Dept. Of CSE, SRM University, Chennai, India.
Abstract– This paper presents Single Server Queue in Random Early Detection (SSQRED) for reducing mismatch between the average queue size and current queue size. In Random Early Detection (RED), the value of average queue length increases slightly with a small weighted queue (wq) parameter. This increases the mismatch between average and current queue length. SSQRED is applied to find the average queue length. SSQRED simulated against RED by measuring throughput, link utilization, packet loss and average delay. The results suggest SSQRED overcome the mismatch problem with the improvement in network performance.
Keywords: AQM, RED, Actual queue length, Average queue length, Queuing Theory.
-
INTRODUCTION
AQM algorithm must have a more efficient congestion indicator and control function. The congestion indicator indicates whenever congestion occurs and the control function is used to avoid or control congestion [1]. The first developed AQM scheme to be deployed in TCP/IP networks was RED[2]. RED which is designed heuristically is a queue based AQM with non per-flow state [3]. The parameters of RED are EWMA weight (wq), the minimum threshold (minth), maximum threshold (maxth) and the maximum non-congestion probability of dropping (pmax) at the maximum threshold. Parameter-tuning is difficult in RED.
The average queue length is referred as the macroscopic behavior because it focuses on the overall and long-term behavior of a queue. The actual queue length is referred as the microscopic behavior as it focuses on the short-term behavior of the queue[QSRED algorithm ]. The Red gateway calculates the average queue length using the low pass filter with an exponential weighted moving average (EWMA) [2]. The actual queue length is the maximum number of packets that can be enqueued.
The actual queue length will increase rapidly, when many bursts of data arrive at a RED router and eventually overflow the buffer. Since small weight (wq) is assigned to the actual queue length, the average queue length will vary slightly. This leads to the large mismatch between the average and actual queue length. The mismatch is highly reduced, when single server queue of queuing theory is applied to find the actual queue size and average queue size for the
wired network. The paper is organized as follows. Section II deals with the related work.. Section III provides RED. Section IV examines the proposed queue management. In Section V required experimental setup is discussed Section VI examines the network performance measurement
parameters. Section VII concludes the paper and the future work is discussed in Section VIII.
-
RELATED WORK
An effective mechanism for avoidance of congestion is the Random Early Detection gateways. When the average queue size exceeds the maximum threshold, RED gateways drops packets. Then the calculated average queue size is controlled. This provides Upper bound on the average delay at the gateway. A particular connection chosen by the RED gateway is proportional to the connections share of bandwidth at the gateway. This avoids bursty traffic at the gateway[2].
Studies suggest variant dynamics between average and actual queue size [4-6]. The actual queue size increases rapidly, when the burst traffic arrives at the RED gateway. This results in the overflow of buffer. Despite congestion the average queue size increases slowly when the weight queue parameter is very small. The packet sending rate will be reduced after a congestion signal is received by the source due to the packet drop at the gateway. The actual queue size is reduced after congestion but the average queue size will remain high due to peaks in previous actual queue size. This makes Red to continue drop packets which unfairly penalizes the new packets[7].
RED has difficulties detecting the mismatch between average queue size and actual queue size. This can result in RED continuing to drop packets even after the congestion is reduced. QSRED divides the buffer into six equal sectors. These sectors represent new dropping levels added to the original Red implementation. It used the actual and average queue size parameters to help RED absorb short lived bursty traffic and control congestion in a effective manner[QSRED]
Queuing theory is basically a mathematical approach applied to the analysis of waiting lines. Queuing theory uses models to represent the various types of queuing systems. Formula for each model indicates how the related queue system should perform, under a variety of conditions. Single server queuing system is the simplest queuing system to analyze. The arrivals follow poisson distribution with the mean arrival rate of and the service time has exponential distribution with the average service rate of µ. Utilization factor, expected number of customers in the system, average queue length, actual queue length and expected waiting time of customers in the queue and the system formulas and the corresponding notations are specified[Application of Queueing Theory for the improvement of bank service,].
The parameters used to measure network performance in wired communication are throughput, link utilization,
packet loss and average delay. For a wired network to have high performance, it should have more throughput and link utilization whereas packet loss and average delay should be less.
-
RED
The average queue length is calculated using the Exponential Weighted Moving Average (EWMA) in RED. The average queue size for non empty queue is
1 + (1) Lq represents the average queue size.
wq denotes the weighted queue parameter, 0 wq 1. L represents the current queue size.
Since the value of wq is very less i.e. it ranges from 0 to 1, the average queue size variation will be very less. Thus the difference in values between current queue size and average queue size will be high. This is illustrated in the Fig. 1.
30000
20000
10000
1
9
17
25
33
41
49
57
65
73
81
89
97
1
9
17
25
33
41
49
57
65
73
81
89
97
0
= 2 /µ(µ ) (6)
,
= 2 /µ(µ ) /(µ )
= (µ )/µ(µ )
= = (7)
4 = 1 6
1 =
= 1 (8)
The average queue length is calculated in SSQRED. The average queue size for non empty queue is obtained using the formula
= 1
V. EXPERIMENTAL SETUP
The proposed queue management consists of two links. One link connects the node to the gateway and the other link connects the gateway to the sink. Drop Tail is applied between node and the gateway with a link bandwidth of 100 Mbps and a propagation delay of 100ms.
-10000
-20000
S G
100Mb,100ms 1Mb,100ms
Sink
Time in Seconds
Fig. 1: Difference in Estimated and Current Queue Mismatch in RED and SSQRED
-
PROPOSED QUEUE MANAGEMENT
The mismatch between the average queue length and the actual queue length is reduced in the proposed system. A formula is derived to find the average queue lengt (Lq) by applying the single server queue in queuing theory. The actual queue length, utilization factor, length of the queue in the system, arrival rate and service rate are denoted by L, , Ls, µ and .
= µ/µ (2)
= /1 (3)
= /µ 2. 2
= /µ (4)
3 1
= µ/(µ ) /(µ )
= µ /µ
= 1 (5)
SSQRED is employed to indicate whenever there arise a congestion in the link between gateway and sink in the network with a link bandwidth of 1 Mbps and propagation delay of 100 ms. S1 denotes the source node and G denotes the gateway node. The simulation is performed for 1000 sec in ns2, estimated queue length and current queue length are measured.
-
NETWORK PERFORMANCE
The performance of network is measured with the network performance metrics for wired networks. The four network performance measurement parameters are network throughput, packet loss, link utilization and average delay. Fig.3 to 6 depict throughput, packet loss, link utilization and average delay respectively.
In Fig.2 network throughput obtained in RED and SSQRED is plotted. In the initial stage of simulation the network throughput obtained using RED in the bottleneck link (between gateway and sink) is higher than SSQRED. In the first 46 seconds of the total simulation time i.e. 1000 sec the throughput of RED is higher than SSQRED. The throughput for RED is 139 kbps and for SSQRED is 138 kbps when the simulation time reaches 46 sec. After that as the simulation time increases the value of throughput obtained for SSQRED increases than RED. In
half way stage of simulation i.e. 500 sec the throughput for SSQRED increases over 28 kbps than RED. At the end of simulation network throughput of SSQRED increases by 15% than RED.
In Fig.3 packet loss occurred in Red and SSQRED is plotted. The packet loss for RED is higher throughout the simulation than SSQRED. The packet loss during few seconds after the beginning of simulation say at 4 sec in Red is 116 bps and for SSQRED is only 8 bps. As the simulation progresses the packet loss in RED increases than in SSQRED. The increase in packet loss in RED over SSQRED after 500 sec is 112 bps. The increase in packet loss in RED at the end of simulation over SSQRED is 67.5%.
In Fig.4 link utilization for RED and SSQRED is plotted. The link utilization is calculated for the bottleneck link (between gateway and sink) with a link capacity of 1 Mbps and the propagation delay of 10 ms. There is a slight difference in the link utilization between RED and SSQRED during the first quarter of the total simulation time. The difference improves during the second and third quarter of simulation. The difference in link utilization between RED and SSQRED at the end of the simulation is 12 kbps. The increase in link utilization of SSQRED over RED is 14%.
In Fig.5 shows the average delay in RED and SSQRED. The average delay in RED is more than in SSQRED. The difference in average delay between RED and SSQRED is high during the initial stage of the simulation. The difference reduces as the simulation proceeds with RED possessing higher delay than SSQRED till the end.
From the graphs obtained it is inferred that the SSQRED has more throughput and link utilization than RED. The packet loss and average delay is less in SSQRED than RED.
200
180
160
140
120
100
80
60
40
20
0
200
180
160
140
120
100
80
60
40
20
0
1
73
145
217
289
361
433
505
577
649
721
793
865
937
1
73
145
217
289
361
433
505
577
649
721
793
865
937
Time in Seconds
Fig. 2: Network throughput for RED and SSQRED
1
73
145
217
289
361
433
505
577
649
721
793
865
937
1
73
145
217
289
361
433
505
577
649
721
793
865
937
Time in Seconds
Fig. 3: Packet Loss for RED and SSQRED
100
90
80
70
60
50
40
30
20
10
1
73
145
217
289
361
433
505
577
649
721
793
865
937
1
73
145
217
289
361
433
505
577
649
721
793
865
937
0
Time in Seconds
Fig. 4: Link Utilization in RED and SSQRED
0.2
0.18
0.16
0.14
0.12
0.1
0.08
0.06
0.04
0.02
0
1
9
17
25
33
41
49
57
65
73
81
89
97
1
9
17
25
33
41
49
57
65
73
81
89
97
Time in Seconds
Fig. 5: Average Delay in RED and SSQRED
REFERENCES
-
Seungwan Ryu, Christopher Rump and Chunming Qiao. Advances in Active Queue Management (AQM) Based TCP Congestion Control. Telecommunication systems 25:3,4, 317- 351, 2004.
-
Sally Floyd and Van Jacobson. Random Early Detection gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking. Vol. 1. No. 4. August 1993.
-
Dong Lin and Robert Morris. Dynamics of Random Early Detection. Proc. SIGCOMM97 Conference.
-
christiansen, M et al.: tunning RED for Web Traffic, IEEE/ACM Trans. Net., vol. 9, no.3,pp.249 64, June(2001).
-
Firoiu, V. and Borden, M.: A study of Active Queue Management for Congestion Congestion Control, Proc. INFOCOM 2000, pp. 1435-44. (2000).
-
May, M. et al.: Influence of Active Queue Parameters on Aggregate Traffic Performance, Technical Report no. 3995, INRIA, Sophia antipolis, France, http://www.inria.fr/RRRT/RR-3995.html
-
Nabhan Hamadneh, David Nurray, Michael Dixon and Peter
Thus SSQRED has high network performance when compared to RED.
-
-
CONCLUSION
-
This paper reduces the mismatch between average queue size and current queue size of wired network using SSQRED. The mismatch increase between average and current queue size in RED is due to the low variation in the average queue size. This variation is caused by the small value of weighted queue parameter. The average queue length determined in SSQRED will not vary very much with that of the current queue length leads to the reduction in mismatch between them. The network performance is high in SSQRED than RED which is evident from the performance parameters such as throughput, packet loss, link utilization and average delay obtained.
Cole. Dynamic Weight Parameter for the Random Early Detection (RED) in TCP Networks. IJNCAA 2(2):342-352, The society of digital information and wireless commn. 2012.
-
Nabhan Hamadneh, David Nurray, Michael Dixon and Peter Cole. QSRED, An Algorithm to Solve the Mismatch Between the Microscopic and Macroscopic Behavior of Red Gateways.
IJCSNS, Vol.10 No.11, Nov.2010
-
Toshiba sheikh, Sanjay kumar singh and Anil kumar kashyap. Application of Queueing Theory for the improvement of bank service. International journal of advanced computational engineering and networking, vol.1 issue-4 june-2013, issn:2320-2106