GSOC2014Bufferbloat

From Nsnam
Jump to navigation Jump to search

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

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

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

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

  • 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

  • Accomplishments:
  • CoDel flow charts:
  • CoDel vs. DropTail basic test:
    • Topology and simulation parameters:

Topology and Parameters

    • Some results:

<gallery> File:droptail-throughput.png|DropTail File:codel-throughput.png|CoDel <gallery>