GSOC2017TBFAndHHF

Main Page - Roadmap - Summer Projects - Project Ideas - Developer FAQ - Tools - Related Projects

HOWTOs - Installation - Troubleshooting - User FAQ - Samples - Models - Education - Contributed Code - Papers

Return to GSoC 2017 Accepted Projects page.

Project Overview

• Project Title: Implementation of Token Bucket Filter (TBF) and Heavy-Hitter Filter (HHF) in ns-3.

• Student: Surya Seetharaman

• Mentor: Stefano Avallone

• Abstract: In PSNs, sometimes it is not possible to distinguish and manipulate different kinds of network flows. For example, we may want to give priority to some flows while limiting bandwidth of other flows or even perform packet classification. To solve such problems, we have a traffic control layer in ns-3 which intercepts the packets flowing between the L2 Net devices and any IP protocol. It uses several qdiscs like pfifo, HBT, RED, CoDel etc., in order to process these packets and perform scheduling or shaping. Currently the ns-3 traffic layer only contains traffic scheduling qdisc models (AQMs) and lacks realistic traffic shaping algorithms. This project aims to introduce the TBF and HHF algorithms into the ns-3 traffic control layer. TBF is a classless traffic shaper, that is used to control the flow rate or bandwidth of the throughput. HHF is a size-based qdisc that attempts to differentiate small and heavy flows. The goal is to catch the heavy flows and move them to a separate queue with less priority so that bulk traffic does not affect the latency of critical traffic.

• Code: Coming Soon...

• About me: A FOSS enthusiast, pursuing the final year of my Master’s degree in Network Services and Systems, from KTH Royal Institute of Technology, Stockholm. My areas of interests include designing/analysing Networked Systems and problem solving using Algorithms and Data Structures.

Deliverables

By the end of this project, the following would be delivered to the ns-3 traffic-layer component :

1. A realistic classless traffic shaping algorithm - Token Bucket Filter (TBF).
2. Validation tests, User example and Documentation of TBF.
3. A size based classless qdisc - Heavy-Hitter Filter (HHF).
4. Validation tests, User example and Documentation of HHF.

Approach

A detailed description of the technical approach can be found in my original proposal [link].

Project Timeline

Community Bonding Phase [May 4th - May 29th]

• Continue studying about the traffic-control component but now more specific to the project at hand (TBF and HHF).
• Submit quality patches to traffic-control component (could be open issues or some other minor tasks) or do some required solid documentation work for this component.
• Communicate regularly with mentors and discuss about weekly plans. Also finalize on the project plan with respect to the submitted proposal. In case any changes need to be made, now is the time. Put the approved plan on the ns-3 Wiki page.
• Study the references provided by mentors in order to start with the project.

Coding Phase [May 30th - Aug 21st]

Phase 1

Week 1 [May 30th - Jun 6th] : TBF implementation phase 1.

• Plan

1. Go through TBF documentation and Linux kernel source code for TBF.
2. Make clarifications and discuss the TBF implementation approach with mentors and make sure of the method before jumping to code.
3. Declare the TbfQueueDisc class and other necessary functions in it.
4. Finish the tbf.h file completely and write proper comments in the file.

• Execution

Week 2 [Jun 6th - Jun 13th] : TBF implementation phase 2.

• Plan

1. Create the structure of the tokens, bucket and transmission queue (fifo).
2. Define the function DoEnqueue()and test it.
3. Define the other functions like BurstChange() and DoPeek().
4. Finally define DoDequeue() and test it.
5. Finish tbf.c file and comment it.

• Execution

Week 3 [Jun 13th - Jun 20th] : TBF user example.

• Plan

1. Do a stand alone testing and ensure it works properly.
2. Create the user example network topology.
3. Use the example simulation to test the overall integrated working of TBF.
4. Complete tbf-example.cc and write proper comments in the file.

• Execution

Week 4 [Jun 20th - 27th] : TBF testing.

• Plan

1. Create the simple test network topology.
2. Finish implementation of all the test cases in tbf-disc-test-suite.cc and validate each one of them individually before moving to next test case.
3. Get code written till date, ready for PHASE 1 evaluation.

• Execution

Deliverables at the end of Phase 1 : TBF algorithm, user example and test case suite will be ready.

Phase 2 :

Week 5 [Jun 27th - Jul 4th] : TBF patch submission for code review.

• Plan

1. Buffer time for any incomplete work from past weeks.
2. Do a full on integrated testing of TBF with ns-3.
3. Produce mergeable patch for TBF and submit it for review.

• Execution

Week 6 [Jul 4th - Jul 11th] : HHF implementation phase 1.

• Plan

1. Go through HHF documentation and Linux kernel source code for HHF.
2. Make clarifications and discuss the HHF implementation approach with mentors and make sure of the method before jumping to code.
3. Declare the HhfQueueDisc class and other necessary functions in it.
4. Finish the hhf.h file completely and write proper comments in the file.

• Execution

Week 7 [Jul 11th - Jul 18th] : HHF implementation phase 2.

• Plan

1. Create the flow (hash) table.
2. Define the function DoEnqueue()and test it.
3. Define the other functions like Classify().
4. Finally define DoDequeue() and test it.
5. Finish hhf.c file and do a stand alone testing ensuring it works properly.

• Execution

Week 8 [Jul 18th - Jul 25th] : HHF user example

• Plan

1. Improvise by taking comments from the mentors and others in the organization about the submitted code review for TBF. Complete TBF and keep it ready for merge.
2. Create the HHF user example network topology.
3. Use the example simulation to test the integrated working of HHF.
4. Complete hhf-example.cc and write proper comments in the file.
5. Get code written till date, ready for PHASE 2 evaluation.

• Execution

Deliverables at the end of Phase 2 : HHF algorithm, user example will be ready along with TBF patch for merge into ns-3.

Phase 3 :

Week 9 [Jul 25th - Aug 1st] : HHF testing.

• Plan

1. Create the simple test network topology (take if from TBF).
2. Finish implementation of all the test cases in hhf-disc-test-suite.cc and validate each one of them individually before moving to next test case.
3. Complete integrated testing of HHF.

• Execution

Week 10 [Aug 1st - Aug 8th] : HHF patch submission for code review.

• Plan

1. Buffer time for any incomplete work from past weeks.
2. Produce mergeable patch for HHF and submit it for review.

• Execution

Week 11 [Aug 8th - Aug 15th] : Documentation and Improvising

• Plan

1. Web page documentation for the added parts of the traffic-control model library.
2. Complete API documentation for TBF and HHF using Doxygen.
3. Improvise by taking comments from the mentors and others in the organization about the submitted code review for HHF. Complete HHF and keep it ready for merge.

• Execution

Week 12 [Aug 15th - Aug 21st] : Fix the Project

• Plan

1. All code should be ready after cleanup and comments write up.
2. Integrating, testing and fixing the complete project.

• Execution

Code Submission Week [Aug 21st - Aug 29th] : Submission

• Plan

1. Buffer time for final touches and incomplete documentation work.
2. Merge the code to ns-3.
3. Submit the code for the final GSoC evaluations.

• Execution