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: https://github.com/tssurya/ns-3-dev-git

• Documentation: https://github.com/tssurya/ns-3-dev-git/wiki

• 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.

Work Done :

• Regular discussions with mentor; approval of project plan which was put up on wiki.
• Repository was created/forked and synced in github.
• Went through the Linux implementation of TBF with mentor's guidance.

Coding Phase [May 30th - Aug 21st]

Phase 1

Code : https://github.com/tssurya/ns-3-dev-git/tree/TBF

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

• Plan

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

• Execution Status (Updated on June 4th)

1. Currently working on the Dequeue functionality.
2. After finishing that, will try out a simple testing to check if it all works.
3. Also need to define default values for user-provided parameters of the queue disc.

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

• Plan

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

• Execution Status (Updated on June 13th)

1. Ran the simple ns-3-dev-git/examples/traffic-control/traffic-control.cc example.
2. Currently working on watchdog scheduler in DoDequeue() function.
3. Current Issues :
   1. Choice between Bytes and NanoSeconds or Bits and Seconds.
   2. The "if condition regarding the peakrate"
4. Need to start with User Examples and Test Suite asap.

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

• Plan

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

• Execution Status (Updated on June 20th)

1. Completed the DoDequeue() functionality which took longer than expected. With that finished the TBF implementation.
2. Also completed the TBF user example. Now awaiting mentor review and approval on TBF implementation and user example.
3. Currently checking the functionality of TBF by varying the parameter values from the TBF user example and checking for any bugs or logic errors.
4. Need to test the TBF by starting with the test case suite asap.

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

• Plan

1. Create the simple test network topology. - DONE
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. - DONE
3. Get code written till date, ready for PHASE 1 evaluation. - DONE

• Execution Status (Updated on June 27th)

1. Changed the manner of DoDequeue() implementation in TBF: Initially we were doing the exact same implementation as done in Linux, but this made the code unreadable in ns-3. So now we implemented the same Linux logic in a simpler manner.
2. Prepared and submitted code for phase 1 review.
3. Wrote a skeleton implementation of the TBF test suite.
4. Currently refining TBF code : Setting the m_mtu parameter in a better way, adding more check conditions in CheckConfig (), added functions to access m_btokens and m_ptokens.

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

Delivered : TBF algorithm, user example and half the test suite. - the other half was completed in Week 5 during the buffer time kept aside.

Code: https://github.com/tssurya/ns-3-dev-git/commit/81ab3093322a21c2bf8be50e6bccd561da2da346

Documentation: https://github.com/tssurya/ns-3-dev-git/wiki/GSoC-Project-Part-1-:-TBF-Implementation-in-ns-3

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. - USED
2. Do a full on integrated testing of TBF with ns-3. - DONE
3. Web page documentation for the added parts of the traffic-control model library. - DONE
4. Complete API documentation for TBF using Doxygen. - DONE
5. Produce mergeable patch for TBF and submit it for review. - UNDER REVIEW in GitHub

• Execution Status (Updated on July 4th)

1. Completed the TBF test suite
2. Completed TBF Documentation
3. Currently cleaning up TBF Code, and looking into the HHF Documentation.

Code : https://github.com/tssurya/ns-3-dev-git/tree/HHF

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

• Plan

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

• Execution Status (Updated on July 11th)

1. Produced a clean mergeable patch of a running TBF model which is under review.
2. Going through HHF Linux code and discussing with mentor on how to implement it.
3. Having starting troubles and a little bit of confusion regarding the multistage filter and data structures required (list/queue).

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

• Plan

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

• Execution Status (Updated on July 17th)

1. Finished a skeleton implementation of HHF (setting up the .h and .cc files)
2. Divided the implementation into two parts and started with the first part:
   1. Enqueue/Dequeue
   2. Multistage Filter
3. Currently really stuck at some points in the DoEnqueue and DoDequeue functions. Figuring out the Linux version of the HHF code for the same.

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. - UNDER REVIEW IN RIETVELD
2. Create the HHF user example network topology. - DONE
3. Use the example simulation to test the integrated working of HHF. - DOING
4. Complete hhf-example.cc and write proper comments in the file. - DOING
5. Get code written till date, ready for PHASE 2 evaluation. - DONE

• Execution Status (Updated on July 26th)

1. Figured out the exact workings of the Enqueue and Dequeue according to Linux Code
2. Prepared a step wise documentation of how it works in Linux : [link]
3. Currently working on creating an issue on rietveld from the GitHub patch for TBF.
4. Deliverables for Phase 2 will be ready during first part of Week 9.

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

Delivered : TBF patch for merge into ns3, HHF algorithm (in progress)

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 Status (Updated on August 2nd)

1. Finished the Enqueue/Dequeue operations implementation of HHF.
2. Refining the existing design of HHF.
3. Starting with the Multistage Filter in HHF.
4. Created TBF review issue on Rietveld (based on GitHub TBF commit).

Code : https://codereview.appspot.com/326150043/

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

• Plan

1. Buffer time for any incomplete work from past weeks.
2. Web page documentation for the added parts of the traffic-control model library.
3. Complete API documentation for HHF using Doxygen.
4. Produce mergeable patch for HHF and submit it for review.

• Execution Status (Updated on August 8th)

1. Refined Enqueue/Dequeue functions in HHF.
2. Implemented the Multistage Filter in HHF for packet classification.
3. Currently figuring out some macro definitions in HHF Linux code to port them into ns3. With that will be done with HHF implementation.

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

• Plan

1. Buffer time for improvising code.
2. Complete any left over documentation.
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 Status (Updated on August 16th)

1. Finished a Skeleton of the HHF user example and figured out what all parameters are to be traced.
2. Seriously stuck at the following lines of the Linux HHF Code; specially with regards to the pointer multicasting :
   1. http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_hhf.c#L189
   2. http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_hhf.c#L219
   3. http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_hhf.c#L293
   4. http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_hhf.c#L295

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 Status (Updated on August 25th)

1. Decided to use a list of FlowState* (m_tmpArray) to store all the flows related to every hhFlows[1024]; thus solving the first two issues stated in the previous week's status.
   1. So now we have two loops; one of them iterating over the list heads in each hhFlows[I] and second one iterating over the Flows stored inside m_tmpArray and then getting the corresponding FlowState of the ListHead/FlowChain.
2. Discussed bitwise operations with mentor and solved the 3rd and 4th issues stated in the previous week's status.
3. Currently testing the HHF with the user example :
   1. The very first packet's Enqueue/Dequeue seems to work although afterwards its giving a SIGSEV. Figuring this out now.

    Program received signal SIGSEGV, Segmentation fault.
    0x00000000f7628440 in ?? ()
    

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

• Plan

1. Do the final touches.
2. Merge the code to ns-3.
3. Submit the code for the final GSoC evaluations.

• Execution Status (Updated on August 26th)

1. Working on the final URL that has to be submitted to Google.
2. Debugging the HHF memory errors.

GSoC Wrap Up and Final Report

The Google Summer of Code 2017 is coming to an end on 29th August 2017 (deadline for the students). The section's URL is what will be submitted to Google for the final evaluations.

Project Summary and Final Outcome

This GSoC project was all about implementing the Token Bucket Filter (TBF) and Heavy Hitter Filter (HHF) algorithms in the traffic-control module of ns-3. Such traffic shaping algorithms may be needed for research studies related to bandwidth management (reserve bandwidth for a particular application, allow equal distribution of unreserved bandwidth etc.), latency sensitive traffic, optimizing AD delivery on websites (by displaying content that is tailored to the user’s interests so as to maximize clickthrough rates), QoS, and so on.

The TBF algorithm which is a simple classless traffic shaping algorithm, is used to control the flow rate or bandwidth of the throughput - basically it only passes packets arriving at a rate which is not exceeding some administratively set rate. Example use cases : To limit the download traffic at an interface of your PC; or to control the upload speed so that other actions can be done simultaneously while sending data.

The HHF algorithm attempts to prioritise the critical light weight traffic over the heavy hitters. It ensures that the bulk traffic does not impact the latency of the light weight essential traffic load. Example use cases : Allowing a user to chat (light flow) while a large file (heavy-hitter) is being downloaded slowly.

These algorithm implementations were based on the Linux Source code for TBF and HHF. So the aim of this project was to deliver the following to the ns-3 traffic-layer component:

1. A realistic classless traffic shaping algorithm - Token Bucket Filter (TBF) along with user example, validation tests and documentation.
2. A classless qdisc to differentiate heavy flows from critical traffic - Heavy-Hitter Filter (HHF) along with user example, validation tests and documentation.

This is what was achieved at the end of the GSoC Timeline:

1. A realistic classless traffic shaping algorithm - Token Bucket Filter (TBF) along with user example, validation tests and documentation.
   1. Code : The TBF code, its user example, test suite and documentation can be found in this link.
   2. Status : This algorithm was completed and is currently placed under review on Rietveld for merge : https://codereview.appspot.com/326150043/
   3. Instructions to run this extension in ns3 :
      1. Download this from the above rietveld issue into the ns-3-dev repo or checkout a version of the ns-3-dev-git from the above GitHub link.
      2. Use "patch -p1 -i issue326150043_1.diff" to add the patch to the repo.
      3. Build ns3 using "./waf build".
      4. Then in order to run the user example or validation tests of TBF use the instructions provided here.
2. A classless qdisc to differentiate heavy flows from critical traffic - Heavy-Hitter Filter (HHF) along with user example
   1. Code : The HHF code and its user example can be found in this link.
   2. Report : Since the HHF working in Linux Code is harder to understand than TBF, a report with pictorial description of its working can be found here.
   3. Status : This algorithm is not completely finished as the HHF test suite and documentation (.rst file) are yet to be done.

All the details of the project along with its documentation and the weekly tracking of the project's progress can be found here.

Project Experience

It has been an incredible and tremendous learning experience; working for the ns-3 organisation as a part of GSoC 2017. This was my first summer work that was done remotely and working with my mentor on implementing the TBF and HHF algorithms in the traffic-control module of the ns3 has helped me learn a lot. Some of the things I learnt and skills I developed include :

• Coding to Perfection of the algorithms - It is not just enough to implement the logic and get a working code, it was really nice to learn to do perfect code as is a rule of thumb in the Open Source Community.
• Working with Linux Code - Both the algorithms that I worked on were based on the Linux Source Code and this was the most challenging part in this project - to try and decipher the Linux working. The TBF code was fairly easy to understand and there was no problem in converting it to an easier user readable version for ns3. However HHF was fairly more complex in terms of the data structures and pointer structs used. It took a while to get a grip or understand the in depth flow and operations in the Linux HHF code and to come up with a plausible way of implementing this in ns3. This is what consumed up most of the time during the middle phase of the project that slowed the project pace down, due to which I was not able to completely finish the project (the HHF test suite and documentation have to be done).
• The most exciting part of the project was to get each of the algorithm working using the debugger and logging component that enabled me to get a clear view of the step by step working of the implementations.
• Overall, it helped me learn more about traffic control and shaping which is what I wanted in the first place during the GSoC Application Phase.

The ns-3 community was very supportive and I am very glad at having chosen this organisation for my GSoC project. A huge portion of this gladness and credit goes to my mentor who has been really patient with me and guided me so well.

Future Work / Unfinished Tasks

Currently the HHF algorithm is being verified for its functionality and correct implementation using the HHF example. At present there are some memory SIGSEGV errors in the multistage filter which is what is being debugged now. Hence it is advised not to yet run this extension until further updates.

Even after the GSoC phase, I will continue to work on this project as HHF still needs to completed. The following are left to be done :

1. Finish the verification of the working of HHF with the user example.
2. Do the test suite and documentation for HHF.