CS 244 ’18: Flows Passing in the Night: A Reproduction of “Heavy-Hitter Detection Entirely in the Data Plane”

Sierra Kaplan-Nelson, Colin Kincaid

Original Paper: Sivaraman, Vibhaalakshmi, et al. “Heavy-hitter detection entirely in the data plane.” Proceedings of the Symposium on SDN Research. ACM, 2017.

Sivaraman et al.’s paper “Heavy-Hitter Detection Entirely in the Data Plane” proposes HashPipe, a heavy-hitter detection algorithm intended for implementation in programmable switches. HashPipe tracks heavy-hitting TCP flows in a multistage hash table, evicting candidates when heavier flows are observed. The paper finds that it is possible to decrease HashPipe’s false negative rate by increasing both the hash table’s memory size and the number of stages in the table, with only minor increases to the amount of duplicate flows stored in the table as a side effect. We attempt to reproduce the paper’s key figures, using our own implementations with the original network traces. Our findings corroborate some, but not all, of the original paper’s results. We explain why our results might make more sense than the original paper’s well-behaved trends, and we offer a proposal for obtaining better results when the network being studied has a relatively low ratio of distinct hosts to total flows.

Full Report.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s