aboutsummaryrefslogtreecommitdiffstats
path: root/include/net/red.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/net/red.h')
-rw-r--r--include/net/red.h325
1 files changed, 325 insertions, 0 deletions
diff --git a/include/net/red.h b/include/net/red.h
new file mode 100644
index 000000000000..2ed4358e3295
--- /dev/null
+++ b/include/net/red.h
@@ -0,0 +1,325 @@
1#ifndef __NET_SCHED_RED_H
2#define __NET_SCHED_RED_H
3
4#include <linux/config.h>
5#include <linux/types.h>
6#include <net/pkt_sched.h>
7#include <net/inet_ecn.h>
8#include <net/dsfield.h>
9
10/* Random Early Detection (RED) algorithm.
11 =======================================
12
13 Source: Sally Floyd and Van Jacobson, "Random Early Detection Gateways
14 for Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking.
15
16 This file codes a "divisionless" version of RED algorithm
17 as written down in Fig.17 of the paper.
18
19 Short description.
20 ------------------
21
22 When a new packet arrives we calculate the average queue length:
23
24 avg = (1-W)*avg + W*current_queue_len,
25
26 W is the filter time constant (chosen as 2^(-Wlog)), it controls
27 the inertia of the algorithm. To allow larger bursts, W should be
28 decreased.
29
30 if (avg > th_max) -> packet marked (dropped).
31 if (avg < th_min) -> packet passes.
32 if (th_min < avg < th_max) we calculate probability:
33
34 Pb = max_P * (avg - th_min)/(th_max-th_min)
35
36 and mark (drop) packet with this probability.
37 Pb changes from 0 (at avg==th_min) to max_P (avg==th_max).
38 max_P should be small (not 1), usually 0.01..0.02 is good value.
39
40 max_P is chosen as a number, so that max_P/(th_max-th_min)
41 is a negative power of two in order arithmetics to contain
42 only shifts.
43
44
45 Parameters, settable by user:
46 -----------------------------
47
48 qth_min - bytes (should be < qth_max/2)
49 qth_max - bytes (should be at least 2*qth_min and less limit)
50 Wlog - bits (<32) log(1/W).
51 Plog - bits (<32)
52
53 Plog is related to max_P by formula:
54
55 max_P = (qth_max-qth_min)/2^Plog;
56
57 F.e. if qth_max=128K and qth_min=32K, then Plog=22
58 corresponds to max_P=0.02
59
60 Scell_log
61 Stab
62
63 Lookup table for log((1-W)^(t/t_ave).
64
65
66 NOTES:
67
68 Upper bound on W.
69 -----------------
70
71 If you want to allow bursts of L packets of size S,
72 you should choose W:
73
74 L + 1 - th_min/S < (1-(1-W)^L)/W
75
76 th_min/S = 32 th_min/S = 4
77
78 log(W) L
79 -1 33
80 -2 35
81 -3 39
82 -4 46
83 -5 57
84 -6 75
85 -7 101
86 -8 135
87 -9 190
88 etc.
89 */
90
91#define RED_STAB_SIZE 256
92#define RED_STAB_MASK (RED_STAB_SIZE - 1)
93
94struct red_stats
95{
96 u32 prob_drop; /* Early probability drops */
97 u32 prob_mark; /* Early probability marks */
98 u32 forced_drop; /* Forced drops, qavg > max_thresh */
99 u32 forced_mark; /* Forced marks, qavg > max_thresh */
100 u32 pdrop; /* Drops due to queue limits */
101 u32 other; /* Drops due to drop() calls */
102 u32 backlog;
103};
104
105struct red_parms
106{
107 /* Parameters */
108 u32 qth_min; /* Min avg length threshold: A scaled */
109 u32 qth_max; /* Max avg length threshold: A scaled */
110 u32 Scell_max;
111 u32 Rmask; /* Cached random mask, see red_rmask */
112 u8 Scell_log;
113 u8 Wlog; /* log(W) */
114 u8 Plog; /* random number bits */
115 u8 Stab[RED_STAB_SIZE];
116
117 /* Variables */
118 int qcount; /* Number of packets since last random
119 number generation */
120 u32 qR; /* Cached random number */
121
122 unsigned long qavg; /* Average queue length: A scaled */
123 psched_time_t qidlestart; /* Start of current idle period */
124};
125
126static inline u32 red_rmask(u8 Plog)
127{
128 return Plog < 32 ? ((1 << Plog) - 1) : ~0UL;
129}
130
131static inline void red_set_parms(struct red_parms *p,
132 u32 qth_min, u32 qth_max, u8 Wlog, u8 Plog,
133 u8 Scell_log, u8 *stab)
134{
135 /* Reset average queue length, the value is strictly bound
136 * to the parameters below, reseting hurts a bit but leaving
137 * it might result in an unreasonable qavg for a while. --TGR
138 */
139 p->qavg = 0;
140
141 p->qcount = -1;
142 p->qth_min = qth_min << Wlog;
143 p->qth_max = qth_max << Wlog;
144 p->Wlog = Wlog;
145 p->Plog = Plog;
146 p->Rmask = red_rmask(Plog);
147 p->Scell_log = Scell_log;
148 p->Scell_max = (255 << Scell_log);
149
150 memcpy(p->Stab, stab, sizeof(p->Stab));
151}
152
153static inline int red_is_idling(struct red_parms *p)
154{
155 return !PSCHED_IS_PASTPERFECT(p->qidlestart);
156}
157
158static inline void red_start_of_idle_period(struct red_parms *p)
159{
160 PSCHED_GET_TIME(p->qidlestart);
161}
162
163static inline void red_end_of_idle_period(struct red_parms *p)
164{
165 PSCHED_SET_PASTPERFECT(p->qidlestart);
166}
167
168static inline void red_restart(struct red_parms *p)
169{
170 red_end_of_idle_period(p);
171 p->qavg = 0;
172 p->qcount = -1;
173}
174
175static inline unsigned long red_calc_qavg_from_idle_time(struct red_parms *p)
176{
177 psched_time_t now;
178 long us_idle;
179 int shift;
180
181 PSCHED_GET_TIME(now);
182 us_idle = PSCHED_TDIFF_SAFE(now, p->qidlestart, p->Scell_max);
183
184 /*
185 * The problem: ideally, average length queue recalcultion should
186 * be done over constant clock intervals. This is too expensive, so
187 * that the calculation is driven by outgoing packets.
188 * When the queue is idle we have to model this clock by hand.
189 *
190 * SF+VJ proposed to "generate":
191 *
192 * m = idletime / (average_pkt_size / bandwidth)
193 *
194 * dummy packets as a burst after idle time, i.e.
195 *
196 * p->qavg *= (1-W)^m
197 *
198 * This is an apparently overcomplicated solution (f.e. we have to
199 * precompute a table to make this calculation in reasonable time)
200 * I believe that a simpler model may be used here,
201 * but it is field for experiments.
202 */
203
204 shift = p->Stab[(us_idle >> p->Scell_log) & RED_STAB_MASK];
205
206 if (shift)
207 return p->qavg >> shift;
208 else {
209 /* Approximate initial part of exponent with linear function:
210 *
211 * (1-W)^m ~= 1-mW + ...
212 *
213 * Seems, it is the best solution to
214 * problem of too coarse exponent tabulation.
215 */
216 us_idle = (p->qavg * us_idle) >> p->Scell_log;
217
218 if (us_idle < (p->qavg >> 1))
219 return p->qavg - us_idle;
220 else
221 return p->qavg >> 1;
222 }
223}
224
225static inline unsigned long red_calc_qavg_no_idle_time(struct red_parms *p,
226 unsigned int backlog)
227{
228 /*
229 * NOTE: p->qavg is fixed point number with point at Wlog.
230 * The formula below is equvalent to floating point
231 * version:
232 *
233 * qavg = qavg*(1-W) + backlog*W;
234 *
235 * --ANK (980924)
236 */
237 return p->qavg + (backlog - (p->qavg >> p->Wlog));
238}
239
240static inline unsigned long red_calc_qavg(struct red_parms *p,
241 unsigned int backlog)
242{
243 if (!red_is_idling(p))
244 return red_calc_qavg_no_idle_time(p, backlog);
245 else
246 return red_calc_qavg_from_idle_time(p);
247}
248
249static inline u32 red_random(struct red_parms *p)
250{
251 return net_random() & p->Rmask;
252}
253
254static inline int red_mark_probability(struct red_parms *p, unsigned long qavg)
255{
256 /* The formula used below causes questions.
257
258 OK. qR is random number in the interval 0..Rmask
259 i.e. 0..(2^Plog). If we used floating point
260 arithmetics, it would be: (2^Plog)*rnd_num,
261 where rnd_num is less 1.
262
263 Taking into account, that qavg have fixed
264 point at Wlog, and Plog is related to max_P by
265 max_P = (qth_max-qth_min)/2^Plog; two lines
266 below have the following floating point equivalent:
267
268 max_P*(qavg - qth_min)/(qth_max-qth_min) < rnd/qcount
269
270 Any questions? --ANK (980924)
271 */
272 return !(((qavg - p->qth_min) >> p->Wlog) * p->qcount < p->qR);
273}
274
275enum {
276 RED_BELOW_MIN_THRESH,
277 RED_BETWEEN_TRESH,
278 RED_ABOVE_MAX_TRESH,
279};
280
281static inline int red_cmp_thresh(struct red_parms *p, unsigned long qavg)
282{
283 if (qavg < p->qth_min)
284 return RED_BELOW_MIN_THRESH;
285 else if (qavg >= p->qth_max)
286 return RED_ABOVE_MAX_TRESH;
287 else
288 return RED_BETWEEN_TRESH;
289}
290
291enum {
292 RED_DONT_MARK,
293 RED_PROB_MARK,
294 RED_HARD_MARK,
295};
296
297static inline int red_action(struct red_parms *p, unsigned long qavg)
298{
299 switch (red_cmp_thresh(p, qavg)) {
300 case RED_BELOW_MIN_THRESH:
301 p->qcount = -1;
302 return RED_DONT_MARK;
303
304 case RED_BETWEEN_TRESH:
305 if (++p->qcount) {
306 if (red_mark_probability(p, qavg)) {
307 p->qcount = 0;
308 p->qR = red_random(p);
309 return RED_PROB_MARK;
310 }
311 } else
312 p->qR = red_random(p);
313
314 return RED_DONT_MARK;
315
316 case RED_ABOVE_MAX_TRESH:
317 p->qcount = -1;
318 return RED_HARD_MARK;
319 }
320
321 BUG();
322 return RED_DONT_MARK;
323}
324
325#endif