computer science

Robust random early detection

Robust random early detection is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Robust random early detection rather than just read about it. In short: Robust random early detection (RRED) is a queueing discipline for a network scheduler. The existing random early detection (RED) algorithm and its variants are found vulnerable to emerging attacks, especially the Low-rate Denial-of-Service attacks (LDoS).

Key takeaways

Robust random early detection belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Robust random early detection to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Robust random early detection from memory before moving on to harder problems.

Reference excerpt

Robust random early detection (RRED) is a queueing discipline for a network scheduler. The existing random early detection (RED) algorithm and its variants are found vulnerable to emerging attacks, especially the Low-rate Denial-of-Service attacks (LDoS). 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. The 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-of-service attacks.

The design 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).

Algorithm of the Robust RED (RRED) algorithm 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

f.T1 is the arrival time of the last packet from flow f that is dropped by the detection and filter block. T2 is the arrival time of the last packet from any flow that is dropped by the random early detection (RED) block. Tmax = max(f.T1, T2). T* is a short time period, which is empirically chosen to be 10 ms in a default RRED algorithm.

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 attack (AQM&DoS) simulation platform. The 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 calculates and records 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.

References

External links AQM&DoS Simulation Platform Recent Publications in Low-rate Denial-of-Service (LDoS) attacks Archived 2013-06-05 at the Wayback Machine Recent Publications in Random Early Detection (RED) schemes Archived 2016-09-17 at the Wayback Machine Recent Publications in Active Queue Management (AQM) schemes

Worked examples

Example 1 — a first encounter with Robust random early detection

Start with the simplest possible case. Write down what Robust random early detection claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Robust random early detection before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Robust random early detection ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Robust random early detection

In research: Robust random early detection appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Robust random early detection in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Robust random early detection is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computer network security, Denial-of-service attacks, Network performance, so understanding it makes those chapters shorter.
In everyday life: Look for Robust random early detection outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Robust random early detection in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Robust random early detection means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Robust random early detection out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Robust random early detection in simple terms?

Why does Robust random early detection matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Robust random early detection?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Robust random early detection.