sched: CHOKe flow scheduler

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative
packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
  For every packet arrival:
  	Calculate Qave
	if (Qave < minth)
	     Queue the new packet
	else
	     Select randomly a packet from the queue
	     if (both packets from same flow)
	     then Drop both the packets
	     else if (Qave > maxth)
	          Drop packet
	     else
	       	  Admit packet with proability p (same as RED)

See also:
  Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
   queue management scheme for approximating fair bandwidth allocation",
  Proceeding of INFOCOM'2000, March 2000.

Help from:
     Eric Dumazet <eric.dumazet@gmail.com>
     Patrick McHardy <kaber@trash.net>

Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>

1 files changed, 29 insertions, 0 deletions

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 776cd93d5f7b..d4bb6f58c90c 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -247,6 +247,35 @@ struct tc_gred_sopt {
         __u16           pad1;
 };
 
+/* CHOKe section */
+
+enum {
+        TCA_CHOKE_UNSPEC,
+        TCA_CHOKE_PARMS,
+        TCA_CHOKE_STAB,
+        __TCA_CHOKE_MAX,
+};
+
+#define TCA_CHOKE_MAX (__TCA_CHOKE_MAX - 1)
+
+struct tc_choke_qopt {
+        __u32           limit;          /* Hard queue length (packets)  */
+        __u32           qth_min;        /* Min average threshold (packets) */
+        __u32           qth_max;        /* Max average threshold (packets) */
+        unsigned char   Wlog;           /* log(W)               */
+        unsigned char   Plog;           /* log(P_max/(qth_max-qth_min)) */
+        unsigned char   Scell_log;      /* cell size for idle damping */
+        unsigned char   flags;          /* see RED flags */
+};
+
+struct tc_choke_xstats {
+        __u32           early;          /* Early drops */
+        __u32           pdrop;          /* Drops due to queue limits */
+        __u32           other;          /* Drops due to drop() calls */
+        __u32           marked;         /* Marked packets */
+        __u32           matched;        /* Drops due to flow match */
+};
+
 /* HTB section */
 #define TC_HTB_NUMPRIO          8
 #define TC_HTB_MAXDEPTH         8