net/sched/sch_hhf.c

2 /* net/sched/sch_hhf.c		Heavy-Hitter Filter (HHF)
16 /*	Heavy-Hitter Filter (HHF)
19  * Flows are classified into two buckets: non-heavy-hitter and heavy-hitter
20  * buckets. Initially, a new flow starts as non-heavy-hitter. Once classified
21  * as heavy-hitter, it is immediately switched to the heavy-hitter bucket.
23  * in which the heavy-hitter bucket is served with less weight.
24  * In other words, non-heavy-hitters (e.g., short bursts of critical traffic)
25  * are isolated from heavy-hitters (e.g., persistent bulk traffic) and also have
28  * To capture heavy-hitters, we use the "multi-stage filter" algorithm in the
37  *    - For a heavy-hitter flow: *all* of its k array counters must be large.
38  *    - For a non-heavy-hitter flow: some of its k array counters can be large
43  * (heavy-hitters getting away uncaptured) is zero. However, the algorithm is
44  * susceptible to false positives (non-heavy-hitters mistakenly classified as
45  * heavy-hitters).
48  *    - Optimization O1: once a heavy-hitter is identified, its bytes are not
59  * Once a flow is classified as heavy-hitter, we also save its per-flow state
61  * dispatched to the heavy-hitter bucket accordingly.
67  *     heavy-hitter flow table, denoted table T, then send p to the heavy-hitter
70  *        + If F decides that p belongs to a non-heavy-hitter flow, then send p
71  *          to the non-heavy-hitter bucket.
72  *        + Otherwise, if F decides that p belongs to a new heavy-hitter flow,
74  *          send p to the heavy-hitter bucket.
105 	WDRR_BUCKET_FOR_HH	= 0, /* bucket id for heavy-hitters */
106 	WDRR_BUCKET_FOR_NON_HH	= 1  /* bucket id for non-heavy-hitters */
112 /* Heavy-hitter per-flow state */
115 	u32		 hit_timestamp;	/* last time heavy-hitter was seen */
179 /* Looks up a heavy-hitter flow in a chaining list of table T. */
194 			/* Delete expired heavy-hitters, but preserve one entry  in seek_list()
209 /* Returns a flow state entry for a new heavy-hitter.  Either reuses an expired
219 		/* Find an expired heavy-hitter flow entry. */  in alloc_new_hh()
245  * classify heavy-hitters.
306 		/* Just captured a new heavy-hitter. */  in hhf_classify()
354 	/* Always try to drop from heavy-hitters first. */  in hhf_drop()
393 			/* Always move heavy-hitters to old bucket. */  in hhf_enqueue()
600 		/* Initialize heavy-hitter flow table. */  in hhf_init()
614 		/* Initialize heavy-hitter filter arrays. */  in hhf_init()
628 		/* Initialize valid bits of heavy-hitter filter arrays. */  in hhf_init()
721 MODULE_DESCRIPTION("Heavy-Hitter Filter (HHF)");