Difference between revisions of "GSOC2017TBFAndHHF"

From Nsnam
Jump to: navigation, search
(GSoC Wrap Up and Final Report (IN PROGRESS))
(GSoC Wrap Up and Final Report (IN PROGRESS))
Line 230: Line 230:
 
=== Project Overview ===
 
=== Project Overview ===
  
This GSoC project was all about implementing the Token Bucket Filter and Heavy Hitter Filter algorithms in the traffic-control module of ns-3. These algorithm implementations were based on the Linux Source code for [[http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_tbf.c | TBF]] and [[http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_hhf.c | HHF]].
+
This GSoC project was all about implementing the Token Bucket Filter and Heavy Hitter Filter algorithms in the traffic-control module of ns-3. These algorithm implementations were based on the Linux Source code for [[http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_tbf.c TBF]] and [[http://elixir.free-electrons.com/linux/latest/source/net/sched/sch_hhf.c HHF]].
  
 
== Project Experience ==
 
== Project Experience ==

Revision as of 08:13, 26 August 2017

Main Page - Current Development - Developer FAQ - Tools - Related Projects - Project Ideas - Summer Projects

Installation - Troubleshooting - User FAQ - HOWTOs - 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.
  • 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.
  • 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.

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 (IN PROGRESS)

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 Accomplishments and Final Outcome

Project Overview

This GSoC project was all about implementing the Token Bucket Filter and Heavy Hitter Filter algorithms in the traffic-control module of ns-3. These algorithm implementations were based on the Linux Source code for [TBF] and [HHF].

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 :

  1. 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.
  2. Working with Linux Code - Both the algorithms that I worked on were based on the Linux Source Code

Project Statistics

Future Work