Author:: [[Junzhi Gong]] et al Source:: [USENIX 2018, atc18-gong](https://www.usenix.org/system/files/conference/atc18/atc18-gong.pdf) Source:: [Updated Version](https://github.com/papergitkeeper/heavy-keeper-project/raw/master/technical_report.pdf) rel:: [[Papers]] [[monitoring]] [[Networking]] [[probabilistic]] [[algorithms]] [[datastructures]] [[Top-K]] # HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows ## References - [annotated paper pdf link](https://www.dropbox.com/s/hm8javdfvgqgeow/heavykeeper-an%20accurate%20algorithm%20for%20finding%20top-k%20elephant%20flows%20%28annotated%29.pdf) [[2020-05-12]] - [paper's example implementation in C++](https://github.com/papergitkeeper/heavy-keeper-project/blob/c07aab7a13b08f565d4090f7be17d805d5b6ba85/heavykeeper.h#L37) of [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] - redis-bloom - [blog anouncement](https://redislabs.com/blog/meet-Top-K-awesome-probabilistic-addition-redisbloom/) - [C implementation](https://github.com/RedisBloom/RedisBloom/blob/174e9de22c1ea7ad9593f71ae670a6d6ce4de96b/src/topk.c#L108) for [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] - [[golang]] [implementation](https://github.com/migotom/heavykeeper) ## Overview Finding [[Top-K]] [[elephant flows]] is a critical task in network traffic measurement > ==In this paper, we adopt a [[probabilistic]] strategy, called [[count with exponential-weakening decay]]==, to achieve space-accuracy balance by actively removing small flows through decaying, while minimizing the impact on large flows, so as to achieve high precision in finding [[Top-K]] elephant flows." > Experimental results show that [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] algorithm achieves ==99.99% precision with a small memory size, and reduces the error by around 3 orders of magnitude on average compared to the state-of-the-art.== > small, constant processing overhead per packet and thus supports high line  rates ### Applications - [[congestion control]], dynamically scheduling [[elephant flows]] - network [[capacity planning]] - [[anomaly detection]] - [[Databases MOC]] ### Contrast With Traditional Solutions >The results show that [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] has little impact on the throughput, while other algorithms decrease the throughput significantly ![[wz9tiUOkod.png]] #### count-all - a large [[Count-min sketch]] is needed to count all flows, not memory efficient - tends to over-estimate #### admit-all-count-some It assumes every new incoming flow is an elephant, and expels the smallest one in the summary to make room for the new one. But most flows are mouse flows. Such an assumption causes significant error, especially under tight memory" ==massive mouse flows will cause significant overestimation errors== ## Data Structure ![[UeN8yUe1Pm.png]] > Uses a small hash table to store all elephant flows. As there are a great number of flows, each bucket of the hash table will be mapped by many flows, and we aim to store only the largest flow with its size, which cannot be achieved with no error when using small memory. > To address this problem, we propose a [[probabilistic]] method called [[count with exponential-weakening decay]]. > When the incoming flow is different from the flow in the hashed bucket, we decay the flow size with a decay [[Probability]] which is exponentially smaller as the flow size grows larger. > If the flow size is decayed to 0, it replaces the original flow with the new flow. In this way, mouse flows can easily be decayed to 0, while elephant flows can easily keep stable in the bucket. ### Two shortcomings > With a small [[Probability]] we elect the wrong flow as the largest flow" > The stored flow size is a little smaller than the true frequency because of the decay operations > To address those issues, use multiple hash tables with different hash functions. Choose the recorded largest size, minimizing error" ### Insertion #### Insertion Cases - ![[xqs21SlfsW.png]] #### Decay [[Probability]] ![[d17MB-XrN_.png]] `C` is the value in the current counter field `b` is a predefined exponential base number for `b=1.08` ![[Xd1qM-sAJu.png]] the larger size a flow has, the harder it is to decay For elephant flows, it is held at several buckets, and the corresponding  counter fields are incremented regularly, while decayed with a very small [[Probability]]. Therefore, the [[error rate]] for estimated sizes of [[elephant flows]] is very small. ### Query 1. computes the `d` hash functions to get `d` buckets `Aj[Hj(Fi)]` (`1 <= j <=d`) 1. chooses the buckets whose fingerprint fields are equal to `Fi` 1. then reports the maximum counter field of those buckets ### Basic [[Top-K]] Algorithm - uses a [[min-heap]] to store the IDs and sizes of [[Top-K]] flows - for each incoming packet `Pi` belonging to flow `Fi` - insert into HeavyKeeper, get size estimate `Ni` - if `Fi` is already in the [[min-heap]], update its estimated flow size with: `max(Ni, min_heap[Fi])` - else `Ni` is larger than the smallest flow (root of [min-heap]) - expel root node and replace with `[Fi, Ni]` ### Example ![[UeN8yUe1Pm.png]] 1. An incoming packet P5 belonging to flow __f3__ 1. we compute the __d__ hash functions to obtain one bucket in each array 1. In the mapped bucket of the first array, the fingerprint field is not equal to **F3** and the counter field is 21, thus we decay the counter field from 21 to 20 with a probability of `1.08^-21` (assume __b __= 1.08). 1. In the second mapped bucket, the fingerprint field is not **F3** yet, and with a probability of `1.08^-1`, we decay the counter field from 1 to 0. 1. If the counter field is decayed to 0, we set the fingerprint field to **F3**, and set the counter field to 1. 1. In the last mapped bucket, the fingerprint field is **F3**, we increment the counter field from 7 to 8. ### Optimizations - Fingerprint Collision Detection - Selective Increment - Speed Acceleration ## Algorithm ![[V_Zht9vv4E.png]] ## Source Notes ### Overview A flow’s ID is usually defined as a combination of certain packet header fields, such as source IP address, destination IP address, source port, destination  port, and protocol type Many management applications can benefit from a function that can find them efficiently, such as ==congestion control by dynamically scheduling elephant flows, network capacity planning, anomaly detection==, and caching of forwarding table entries. Such a function also has applications beyond networking in areas such as data mining, information retrieval, databases, and security. It is well known that the distribution of flow sizes (the number of packets in a flow), is highly skewed, __i.e.__, the majority are mouse flows, while the minority are elephant flows #### Traditional solutions ##### count-all - relies on a [[Count-min sketch]] - As a large [[Count-min sketch]] is needed to count all flows, not memory efficient - **problem**: all flows are pseudo-randomly mapped to the same pool of counters through hashing. Each counter may be shared by multiple flows, and thus record the sum of sizes of all these flows. Consequently, [[Count-min sketch]] has an over-estimation problem, which will become severe in a tight memory space where the number of counters is far smaller than the number of flows, resulting in aggressive sharing. In such a case, a small flow may be treated as an elephant flow if all its __d__ counters are shared with real elephant flows. ##### admit-all-count-some - examples - Frequent - Lossy Counting - Space-Saving, related to [[Misra-Gries Summaries]] - CSS - It assumes every new incoming flow is an elephant, and expels the smallest one in the summary to make room for the new one. But most flows are mouse flows. Such an assumption causes significant error, especially under tight memory - admits all new flows while expelling the smallest existing ones from the summary. - To give new flows a chance to stay in the summary, their initial flow sizes are set as `Nmin + 1`. Such a strategy drastically over-estimates sizes of flows - ==massive mouse flows will cause significant overestimation errors== ### [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] approach [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]], based on a different strategy, called [[count with exponential-weakening decay]], which keeps all elephant flows while drastically reducing space wasted on mouse flows. - Unlike __count-all__, our strategy only keeps track of a small number of flows. - Unlike __admit-all-count-some__, we do not automatically admit new flows into our data structure and the vast majority of mouse flows will be by-passed - For a small number of mouse flows that do enter our data structure, they will decay away to make room for true elephants. - The design of exponential decay is biased against small flows, and it has a smaller impact on larger flows. ![[wz9tiUOkod.png]] - The results show that [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] has little impact on the throughput, while other algorithms decrease the throughput significantly ### Design of [[HeavyKeeper - An Accurate Algorithm for Finding Top-K Elephant Flows|HeavyKeeper]] - use a small hash table to store all elephant flows. As there are a great number of flows, each bucket of the hash table will be mapped by many flows, and we aim to store only the largest flow with its size, which cannot be achieved with no error when using small memory. - To address this problem, we propose a [[probabilistic]] method called [[count with exponential-weakening decay]]. - When the incoming flow is different from the flow in the hashed bucket, we decay the flow size with a decay [[Probability]] which is exponentially smaller as the flow size grows larger. - If the flow size is decayed to 0, it replaces the original flow with the new flow. In this way, mouse flows can easily be decayed to 0, while elephant flows can easily keep stable in the bucket. - Two shortcomings 1. With a small [[Probability]] we elect the wrong flow as the largest flow 2. The stored flow size is a little smaller than the true frequency because of the decay operations - To address those issues, use multiple hash tables with different hash functions. Choose the recorded largest size, minimizing error