Skip to content

Instantly share code, notes, and snippets.

@gogapp
Last active August 14, 2018 15:33
Show Gist options
  • Save gogapp/ccf6222acc9e154c095eee941cc6051a to your computer and use it in GitHub Desktop.
Save gogapp/ccf6222acc9e154c095eee941cc6051a to your computer and use it in GitHub Desktop.
GSoC 2018: Implementing blackholing in Gatekeeper

During GSoC 2018, I worked with my mentor Qiobin Fu on the project titled “Implementing Blackholing in Gatekeeper” with my mentor organisation: Boston University/Linux XIA group.
The main goal of the project was to implement the RHHH Algorithm in Gatekeeper so that Gatekeeper could effectively monitor heavy hitters and blackhole them for a maximum period described in its configuration file. After this expiration, the IP destinations/prefixes/flows are released, and Gatekeeper will black hole them again if the overwhelming attacks continue. The second part of the project was to enhance the performance of RHHH Algorithm by applying the Cold Filter. The third part of the project involved testing the performance of the implemented algorithms in terms of throughput, accuracy etc.

As the implementation of RHHH is based on a counter based algorithm, Space Saving Algorithm was implemented to perform as RHHH counters. Due to it's low memory consumption and good accuracy, Space Saving Algorithm has a performance edge over other counter algorithms. For testing of the algorithms, packet traces requested from Caida were used. The packets were processed using libpcap library. For measuring the false positives, the outputs of the algorithms were matched with that of the fully correct algorithm. For measuring the speed of the implementation, the time required per lcore to process a fixed number of packets has been noted. The implementation of RHHH was done for the following configurations : 1D IPv4 packets, 2D IPv4 packets, 1D IPv6 packets. I have added the various useful links below. Details of running the tests have been provided in the Testing Repository link. I have added a few snaps of the tests run here. The entire project has been implemented using the dpdk library. Till now, the implementation of RHHH Algorithm and Space Saving Algorithm as gatekeeper libraries has been done. Space saving algorithm has been tested for correctness and throughput from my side. RHHH Algorithm implementation has undergone basic correctness testing.
I have got my code reviewed by the mentors on both the main repository pull request and local fork pull request for styling and other errors.

Future Work
A more rigorous correctness testing of RHHH Implementation is still left. The implementation of Cold Filter is still left to be done. Also, further testing of the algorithms needs to be done to fully ensure the correctness of the algorithms. For merging the code in gatekeeper repository, further improvements like combining of heavy hitter results from various lcores and proper configuration of the algorithm in gatekeeper needs to be done.

Links

  1. Main repository Pull Request
  2. Local Fork Pull Request
  3. Testing Repository
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment