Constant Time Updates in Hierarchical Heavy Hitters
Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, Erez Waisbard · 2017
Monitoring tasks, such as anomaly and DDoS detection, require identifying frequent flow aggregates based on common IP prefixes. These are known as hierarchical heavy hitters (HHH), where the hierarchy is determined based on the type of prefixes of interest in a given application. The per packet complexity of existing HHH algorithms is proportional to the size of the hierarchy, imposing significant overheads.