red.h 7.5 KB

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