Robust random early detection: Difference between revisions

Revision as of 08:53, 18 June 2011

Latest revision as of 13:38, 7 January 2024

(22 intermediate revisions by 18 users not shown)

Line 1:

'''Robust random early detection''' ('''RRED''') is a queueing discipline for a [[network scheduler]]. The existing [[Randomrandom Earlyearly Detectiondetection]] (RED) algorithm and its variants are found vulnerable to emerging attacks, especially the [http://sites.google.com/site/cwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow[Denial-rateDenialof-service attack#Low-rate Denial-of-ServiceAttacks.pdf?attredirects=0Service attacks|Low-rate Denial-of-Service attack]]s (LDoS) attacks. Experiments have confirmed that the existing RED-like algorithms are notably vulnerable under LDoS attacks due to the oscillating TCP queue size caused by the attacks.<ref name=RRED>Changwang{{Cite journal | last1 = Zhang, Jianping| first1 = C. | last2 = Yin, Zhiping| first2 = J. | last3 = Cai, and| Weifengfirst3 = Z. | last4 = Chen, [http://sites| first4 = W.google.com/site/cwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow-rateDenial-of-ServiceAttacks.pdf?attredirects | title =0 RRED: Robust RED Algorithmalgorithm to Countercounter Lowlow-rate Denialdenial-of-Serviceservice Attacks],attacks | doi = 10.1109/LCOMM.2010.05.091407 | journal = [[IEEE Communications Letters,]] vol.| volume = 14, pp.| 489-491,issue = 5 | pages = 489–491 | date=May 2010. [http| s2cid = 1121461 | url = https://ieeexploresites.ieeegoogle.orgcom/xplsite/freeabs_allcwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow-rateDenial-of-ServiceAttacks.jsppdf?arnumberattredirects=5456075 Ref]0}}</ref>

AThe Robust RED (RRED) algorithm was proposed to improve the TCP throughput against LDoS attacks. The basic idea behind the RRED is to detect and filter out attack packets before a normal RED algorithm is applied to incoming flows. RRED algorithm can significantly improve the performance of TCP under Low-rate [[Denial denial-of Service]]-service attacks.<ref name="RRED"/>

==The Design of Robust RED (RRED)==

==The Designdesign of Robust RED (RRED)==

A detection and filter block is added in front of a regular RED block on a router. The basic idea behind the RRED is to detect and filter out LDoS attack packets from incoming flows before they feed to the RED algorithm. How to distinguish an attacking packet from normal TCP packets is critical in the RRED design.

Within a benign TCP flow, the sender will delay sending new packets if loss is detected (e.g., a packet is dropped). Consequently, a packet is suspected to be an attacking packet if it is sent within a short-range after a packet is dropped. This is the basic idea of the detection algorithm of Robust RED (RRED).<ref name="RRED"/>

==The Algorithm of the Robust RED (RRED)==

[http://sites.google.com/site/cwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow-rateDenial-of-ServiceAttacks.pdf?attredirects=0 More Details]

'''algorithm''' RRED-ENQUE(pkt)

01 f←RRED f ← RRED-FLOWHASH(pkt)

02 Tmax←MAX Tmax ← MAX(Flow[f].T1, T2)

03 '''if''' pkt.arrivaltime is within [Tmax, Tmax+T*] '''then'''

04 reduce local indicator by 1 for each bin corresponding to f

05 '''else'''

06 increase local indicator by 1 for each bin of f

07 Flow[f].I←maximumI ← maximum of local indicators from bins of f

08 '''if''' Flow[f].I >=≥ 0 '''then '''

09 RED-ENQUE(pkt) // pass pkt to the RED block

10 '''if''' RED drops pkt '''then'''

11 T2 ← pkt.arrivaltime

12 '''else'''

13 Flow[f].T1←pktT1 ← pkt.arrivaltime

14 drop(pkt)

15 '''return'''

*''f.T1'' is the arrival time of the last packet from flow ''f'' that is dropped by the detection and filter block.

==The Algorithm of the Robust RED (RRED)==

*''T2'' is the arrival time of the last packet from any flow that is dropped by the [[Randomrandom Earlyearly Detectiondetection]] (RED) block.

*''Tmax = max(f.T1, T2)''.

''f.T1'' is the arrival time of the last packet from flow ''f'' that is dropped by the detection and filter block.

*''T*'' is a short time period, which is empirically choosechosen to be 10ms10&nbsp;ms in a default [[RRED]] algorithm.<ref name="RRED"/>

''T2'' is the arrival time of the last packet from any flow that is dropped by the [[Random Early Detection]] block.

''Tmax = max(f.T1, T2)''.

''T*'' is a short time period, which is empirically choose to be 10ms in a default [[RRED]] algorithm.

<nowiki>

RRED-ENQUE(pkt)

01 f←RRED-FLOWHASH(pkt)

02 Tmax←MAX(Flow[f].T1, T2)

03 if pkt.arrivaltime is within [Tmax, Tmax+T*] then

04 reduce local indicator by 1 for each bin corresponding to f

05 else

06 increase local indicator by 1 for each bin of f

07 Flow[f].I←maximum of local indicators from bins of f

08 if Flow[f].I >=0 then

09 RED-ENQUE(pkt) //pass pkt to the RED block

10 if RED drops pkt then

11 T2←pkt.arrivaltime

12 else

13 Flow[f].T1←pkt.arrivaltime

14 drop(pkt)

15 return

</nowiki>

[http://sites.google.com/site/cwzhangres/home/files/RREDRobustREDAlgorithmtoCounterLow-rateDenial-of-ServiceAttacks.pdf?attredirects=0 More Details]

==The Simulation code of the Robust RED (RRED)==

The simulation code of the RRED algorithm is published as an [[Active Queue Management]] and [[Denial-of-Service]] (AQM&DoS) Simulation Platform. The [http://sites.google.com/site/cwzhangres/home/posts/aqmdossimulationplatform AQM&DoS Simulation Platform] is able to simulate a variety of DoS attacks (Distributed DoS, Spoofing DoS, Low-rate DoS, etc.) and Active Queue Management (AQM) algorithms (RED, [[RRED]], SFB, etc.). It automatically calculate and record the average throughput of normal TCP flows before and after DoS attacks to facilitate the analysis of the impact of DoS attacks on normal TCP flows and AQM algorithms.[http://sites.google.com/site/cwzhangres/home/posts/aqmdossimulationplatform More Details]

==Related Publications==

[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinlow-ratedosattacks Recent Publications in Low-rate Denial-of-Service (LDoS) attacks ]

[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinrandomearlydetectionredschemes Recent Publications in Random Early Detection (RED) schemes]

[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinactivequeuemanagementaqmschemes Recent Publications in Active Queue Management (AQM) schemes]

==The Simulationsimulation code of the Robust RED (RRED)==

The simulation code of the RRED algorithm is published as an [[Activeactive Queuequeue Managementmanagement]] and [[Denialdenial-of-Serviceservice attack]] (AQM&DoS) Simulationsimulation Platformplatform. The [http://sites.google.com/site/cwzhangres/home/posts/aqmdossimulationplatform AQM&DoS Simulation Platform] is able to simulate a variety of DoS attacks (Distributed DoS, Spoofing DoS, Low-rate DoS, etc.) and Activeactive Queuequeue Managementmanagement (AQM) algorithms (RED, [[RREDrandom early detection|RED]], RRED, SFB, etc.). It automatically calculatecalculates and recordrecords the average throughput of normal TCP flows before and after DoS attacks to facilitate the analysis of the impact of DoS attacks on normal TCP flows and AQM algorithms.[http://sites.google.com/site/cwzhangres/home/posts/aqmdossimulationplatform More Details]

==References==

{{reflist}}

==External links==

*[http://sites.google.com/site/cwzhangres/home/posts/aqmdossimulationplatform AQM&DoS Simulation Platform]

*[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinlow-ratedosattacks Recent Publications in Low-rate Denial-of-Service (LDoS) attacks ]

*[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinrandomearlydetectionredschemes Recent Publications in Random Early Detection (RED) schemes] {{Webarchive|url=https://web.archive.org/web/20160917055738/http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinrandomearlydetectionredschemes |date=2016-09-17 }}

*[http://sites.google.com/site/cwzhangres/home/posts/recentpublicationsinrandomearlydetectionredschemesrecentpublicationsinactivequeuemanagementaqmschemes Recent Publications in RandomActive EarlyQueue DetectionManagement (REDAQM) schemes]

{{DEFAULTSORT:Random Early Detection}}

[[Category:Network performance]]

[[Category:Packets (information technology)]]

[[Category:Denial-of-service attacks]]

[[Category:Computer network security]]