GSOC2014Bufferbloat

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 2014 Accepted Projects page.

Understanding bufferbloat through simulations in ns-3

• Student: Truc Anh Nguyen
• Mentors: Tom Henderson and Dave Täht
• Abstract: The goal of the project is to study and visualize the bufferbloat problem by developing models and examples in ns-3 and analyze the performance of different queue types that are developed as solutions to bufferbloat, including CoDel, FQ_CoDel, and SFQRED
• Code: http://code.nsnam.org/annguyen/ns-3-dev-aqm/summary
• About me: I am currently a PhD student in Computer Science at The University of Kansas. My focus area is networking with the emphasis on studying and understanding the different reliable transport layer mechanisms and protocols, including the various connection management, error control, and congestion control approaches. More information is available on my website

Readings

• Traditional AQM is not enough
• Controlling Queue Delay
• CeroWrt
• ICCRG presentation
• ns-2 code
• ns-3 code review
• Active Queue Management Algorithms for DOCSIS 3.0

Approach

I plan to accomplish the project's goal through the following 3 phases:

• Phase 1: Bufferbloat problem demonstration and simulation
• Phase 2: Codel, FQ Codel, SFQRED code fix and cross-validation
  • Codel: address the comments on ns-3 code review for Codel, add documentation, write test suite, validate against ns-2 and OpenWrt Linux implementations
  • FQ Codel: address the comments on ns-3 code review for FQ Codel, add documentation, write test suite, validate against ns-2 and OpenWrt Linux implementations
  • SFQRED: address the comments on ns-3 code review for SFQRED, add documentation, write test suite, validate against ns-2 and OpenWrt Linux implementations
• Phase 3: Simulations and performance analysis

Deliverables

• Delverable 1: Scripts to demonstrate and visualize bufferbloat problem
• Deliverable 2: Codel code with documentation, test suite, and scripts to validate against ns-2 and OpenWrt implementations
• Deliverable 3: FQ Codel code with documentation, test suite , and scripts to validate against ns-2 and OpenWrt implementations
• Deliverable 4: SFQRED code with documentation, test suite, and scripts to validate against ns-2 and OpenWrt implementations
• Deliverable 5: Scripts to perform simulation analysis under different scenarios

Plan

After our weekly meeting on Friday, we update this section noting down our plan for the upcoming week(s).

• Friday, May 16, 2014:
  • Review ns-3 AQM code reviewers' comments, make a list of all the issues to be attacked, test Dave's git repo, and run the programs in the scratch/ dir
  • Develop a 3-node test script with FIFO queue for initial visualization of bufferbloat. One router sits in between a sender and a receiver, and the link connects the router and the receiver is the bottleneck link with a 10 Mb/s bandwidth and a 5 ms delay. The sender node sends multiple small TCP flows and 1 large flow. We may want a diversity of receivers with different RTTs to avoid synchronization effects. Initial set of performance metrics we want to capture include:
    • queue sojourn time
    • cwnd evolution for "elephant" TCP connection
    • completion time or PLT (Page Load Time) for "mice" TCP connections
    • other TCP statistics
• Friday, June 6, 2014:
  • Script that compares CoDel and DropTail with queue length of 1000 packets under a long-duration TCP transfer. TCP performance is captured using pcap tracing. The trace is then run through tcptrace or other visualization tools. The goal is that CoDel performs in the same manner. It would be nice to have other visualizations or statistics (e.g. direct queue statistics). ** Postpone Fq/Sfq variants until after mid-term
  • Need to move test scripts to src/internet/examples and add to the src/internet wscript
    • 'hg rename a b' can be used (e.g 'hg rename scratch/aqm-test1.cc src/internet/examples/aqm-test

1.cc')

• • Need to move codel from src/network to src/internet
  • Need a test suite that just tests codel queue in isolation (unit test for CoDel)
  • Start a codel.rst file for src/internet/doc/
    • cd src/
    • python create-module.py codel
    • cd codel/doc/
    • cp codel.rst ../../internet/doc/
    • cd ../../
    • rm -rf codel
  • Track open issues on wiki
    • Transcribe Dave's codel-todo.org file
  • boost dependency:
    • port flow_dissector to ns-3, but need to hash packet headers
    • post ns-developers to ask about general way we should approach this
• Friday, June 13, 2014:
  • Get basic example program committed that does TCP for a large transfer, traces cwnd, produces pcap output, and allows alternating between codel and droptail queue. Suggested configuration of txqueuelen 1000 packets on the droptail queue, 2 Mb/s data rate and 5 ms delay on the P2P bottleneck link leaving the queue under test, 100 Mb/s data rate with negligible delay on the P2P access links.
  • Get test case 3 in CoDel unit test working correctly. Make sure to test operation while in the drop state
  • Start to work on queue trace sources:
    • trace every drop, combined with the drop interval parameter
    • trace the event of entering drop state, and the interval state at that time
    • trace the event of exiting the drop state, and the targeted drop interval at that time
    • trace each queue length change-- useful for cases where misbehaving flows get into the queue
    • trace the "time in queue" for every packet successfully dequeued
• Friday, June 20, 2014:
  • Prepare for mid-term review
• Friday, July 11, 2014:
  • Discuss the rough order of priority (details in Section 7: Issues and action items

Weekly progress

• Week 1 (May 19, 2014 -- May 23, 2014):
  • Reviewed CoDel code, addressed reviewers comments
  • Started writing unit tests for CoDel
• Week 2 (May 26, 2014 -- May 30, 2014):
• Week 3 (June 2, 2014 -- June 6, 2014):
  • Added documentations for CoDel
  • Started codel.rst
• Week 4 (June 9, 2014 -- June 13. 2014):
  • Ran the unit tests on CoDel
  • Found additional errors with CoDel and got them fixed with the help from Dave and Tom
• Week 5 (June 15, 2014 -- June 20, 2014):
  • Completed initial test script (codel vs drop tail)
  • Ran pcap file generated by the test script through tcptrace and wireshark to examine CoDel performance in comparison with DropTail
  • Updated codel.rst
  • Prepared mid-term review
• Week 6 (June 23, 2014 -- June 27,2014):
  • Cleaned the code and prepared the wiki for mid-term review
  • Addressed comments on the code review
  • Added trace sources queue length and 'time in queue' for CoDel
  • Started on extending the test script to have asymmetric links
  • Week 8 (July 7, 2014 -- July 11, 2014):
  • Completed codel vs droptail asymmetric test script, which supports multiple up/down streams, asymmetric links, and isochronous with multiple on/off flows
  • Modified CoDel to use Queue::QueueMode
• Week 9 (July 14, 2014 -- July 18, 2014):
  • Worked on extending CoDel queue tracing to trace drop events

Issues and action items

In rough order of priority.

CoDel

• adding on-off flow (voip parameters). 20 ms interarrival time, 110-280 bytes per packet (Anh)
• redo Codel queue mode to instead use Queue::QueueMode (Anh)
• additional trace sources (Anh)
  • trace every drop, combined with the drop interval parameter
  • trace the event of entering drop state, and the interval state at that time
  • trace the event of exiting the drop state, and the targeted drop interval at that time
• add more unit tests
  • test the codel algorithm that it correctly gets the sojourn time evaluation right
  • inverse square root function is working (large packet limit, flood it, and in 100 ms, you should have a drop, then 83 ms longer, another drop)
  • other phase of algorithm harder to look at. On/off saturation. (Dave to write up)
• System test similar to codel-vs-droptail-asymmetric, perhaps using CORE emulator (Tom)

FqCodel

• patch to ns-3 Queue and derived classes to enable peeking at and modifying the IP header (Tom)
  • Initial direction for this is provided here: http://code.nsnam.org/tomh/ns-3-dev-queue/rev/fda94633fe03
  • Some more support in class Packet is likely needed to complete this approach
• support for hashing IP 5-tuples for FQ/SFQ; avoid boost (Tom)
  • Skeleton for Jenkins hash can be found here: http://code.nsnam.org/tomh/ns-3-dev-queue/rev/9b76389f6705
• alternative to Linux list macro? std::list?

SfqCodel

Depends on FqCodel issues, plus additional issues to be determined.

CoDel ToDo (Dave's codel-todo.org)

We intend to migrate the below into the previous section

• Generic issues:
  • Correct solution for queues that might not return a packet (Not clear if this problem is generic to the net point-to-point device or global)
  • Correct solution for tcp initial sequence numbers
  • The IPv4Header and the IPv6Header objects do not have equivalent functions like getECN
• FQ_Codel
  • Fix incorrect hashing for IPv6 and other protocols
    • Linux abstracted all this out into net/core/flow-dissector.c
    • It also inspects deep enough to get src/dst ports from many popular protocols.
    • Switching to the same jhash will also get rid of a dependency on boost
    • ns-3 header parsing is weird. Declare the object see if it exists?

   q->PeekHeader (each kind of ip header? tcp udp sctp?)
   if header->hasports()? 

• • fq_codel does not use shared buffer backlog on the codel aqm
    • That was how we did things prior to running into the horizontal standing queue problem.

   if (m_ht[h] == NULL) 
     {
        NS_LOG_DEBUG ("fq_codel enqueue Create queue " << h);
        m_ht[h] = new Fq_CoDelSlot (); 
        slot = m_ht[h]; 
        slot->q->backlog = &backlog; 
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^?
        slot-> h = h; 
     }

• • • (and to this day I'm dissatisfied with the solution in Linux. He drops a lot more sparse packets now than I'd like)
  • Fq_CoDelQueue::DoEnqueue (Ptr<Packet> p) looks a lot like sfq in initializing queues
    • It seems saner to me to initialize once at startup. Don't need a map, either, just a good old fashioned array
  • fq_codel initializes the perturbation value at instantation time.
    • It is not swept every so often as in SFQ.
  • Add IPv6 support
  • Add ECN support
  • Add support for codel and fq_codel variants
• SFQ
  • Use a quantum of 4500 by default - switch back to 1500 default (DONE)
  • Fix spelling of perturbation (DONE)
  • Change to timed, rather than per-packet perturbation interval as per Linux
  • Add IPv6 support
  • Add ECN support
  • Add depth and flows options
• ARED
• SFQRED and SFQARED
• Code cleanups
• Documentation
• Tests
• DNS model
• Cablelabs stuff
• RRUL test emulation
  • isochronous voip streams
  • 4 up 4 down tcp

Midterm review

• Code to be reviewed: https://codereview.appspot.com/110110044/
• Accomplishments:
  • Reviewed and studied CoDel algorithm and its implementation in ns-3
  • Helped identify and fix some bugs in the CoDel implementation
    • CoDelQueue::ShouldDrop () should not drop any packets.
    • CoDelQueue::DoDequeue () should drop an initial packet if we have to enter the dropping state because ShouldDrop () returns TRUE.
    • DoEnqueue () should make sure that the numbers of packets a queue can hold are the same when using packet mode and byte mode. DropTail queue and RED queue implementations have the same error.
  • Added documentations to CoDel, including doxygens, code style, and codel.rst
  • Wrote unit tests to perform sanity check on CoDel implementation
    • Available at: http://code.nsnam.org/annguyen/ns-3-dev-aqm/file/9698e6ff1b26/src/network/test/codel-queue-test-suite.cc
  • Wrote a basic test script to test CoDel vs. DropTail with congestion window tracing
    • Available at: http://code.nsnam.org/annguyen/ns-3-dev-aqm/file/65dfb6cfe5d4/src/internet/examples/codel-vs-droptail-basic-test.cc
• CoDel vs. DropTail basic test:
  • Topology and simulation parameters:

• • Some results:

• Throughput graphs
• 

  DropTail

• 

  CoDel

• Round trip time graphs
• 

  DropTail

• 

  CoDel

• Time/Sequence graphs
• 

  DropTail

• 

  CoDel

• • Analysis: The plots show that while CoDel is able to achieve almost the same throughput as DropTail (an average of 4.7 Mb/s achieved by CoDel in comparison to 4.86 Mb/s achieved by DropTail), CoDel maintains a much lower queue latency than DropTail (an average RTT of 10.3 ms for CoDel vs. an average RTT of 105.2 ms for DropTail).

• • How to reproduce the previous results:

      $ hg clone http://code.nsnam.org/annguyen/ns-3-dev-aqm
      $ cd ns-3-dev-aqm
      $ hg checkout -r 65dfb6cfe5d4
      $ ./waf configure --enable-examples --enable-tests && ./waf build
      $ ./waf --run "codel-vs-droptail-basic-test --PrintHelp"
      $ ./waf --run "scratch/codel-vs-droptail-basic-test --queueType=CoDel --pcapFileName=codel.pcap --cwndTrFileName=cwndCodel.tr" 
      $ ./waf --run "scratch/codel-vs-droptail-basic-test --queueType=DropTail --pcapFileName=droptail.pcap --cwndTrFileName=cwndDroptail.tr"
      Open .pcap files in wireshare
      Go to Statistics > TCP Stream Graphs to obtain the graphs
      Run the following command if using tcptrace:
      $ tcptrace -l -r -n -W <name of the pcap file>

Final review

• CoDel algorithm:
  • CoDelQueue::DoEnqueue() routine is similar to other (DropTail and RED) DoEnqueue() routines except the addition of tagging the packet p with the current time. This time tag is used to calculate the packet's sojourn when it's dequeued.

• • CoDelQueue::ShouldDrop() routine is a helper routine determining whether a packet p should be dropped based on its calculated sojourn time. When sojourn time has gone above m_target for at least m_interval, ShouldDrop() returns TRUE indicating that packet p can be dropped. Otherwise, it returns FALSE.

• • CoDelQueue::DoDequeue() routine is the heart of the CoDel algorithm. It consists of 2 branches: if we are not in dropping state, we need to decide if we have to enter the dropping state and drop the first packet; if we are currently in dropping state, we need to check if we can leave the state or have to perform the next packet drop. Note that we need to check for an empty queue before dequeuing a packet to avoid dereferencing a NULL pointer. Furthermore, an empty queue always takes us out of the dropping state. This part is not shown in the flow chart.

• CoDel vs. DropTail test
  • Typical cable modem topology and delay