Difference between revisions of "GSOC2020Prague"

From Nsnam
Jump to: navigation, search
m (Milestones and Deliverables)
m (Weekly Reports)
Line 51: Line 51:
 
=== Community Bonding Period (May 4 - May 31) ===
 
=== Community Bonding Period (May 4 - May 31) ===
 
* Established the Wiki page for this project.
 
* Established the Wiki page for this project.
* Rebased the GSoC 2018 [https://www.nsnam.org/wiki/GSOC2018AccECN_ECN%2B%2B implementation] of ECN++ and AccECN (without TCP options) to the latest ns-3-dev. The rebased branches can be found in my [https://gitlab.com/deepakkavoor/ns-3-dev repository]
+
* Rebased the GSoC 2018 [https://www.nsnam.org/wiki/GSOC2018AccECN_ECN%2B%2B implementation] of ECN++ and AccECN (without TCP options) to the latest ns-3-dev.
* Went through the TCP models and architecture in ns-3 and studied about [https://github.com/JoakimMisund/PacedChirping Paced Chirping].
+
* Went through the documentation for TCP model in ns-3 and read about [https://github.com/JoakimMisund/PacedChirping paced chirping].
After a discussion with mentors and the L4S Team, it was decided that the first phase of this project should focus on pacing in TCP Prague.
+
After a discussion with mentors and the L4S Team, it was decided that the first phase of this project should focus on dynamic pacing in TCP Prague.
  
 
=== Week 1 (June 1 - June 7) (Start of Phase 1)===
 
=== Week 1 (June 1 - June 7) (Start of Phase 1)===
 
* Agreed upon the pacing structure for TCP Prague in ns-3. The document can be found [https://docs.google.com/document/d/1PPSLOHv_t2GCkvd9b7YFWQGyQuFtsExJX2oAwQx5tEs/edit?usp=sharing here].
 
* Agreed upon the pacing structure for TCP Prague in ns-3. The document can be found [https://docs.google.com/document/d/1PPSLOHv_t2GCkvd9b7YFWQGyQuFtsExJX2oAwQx5tEs/edit?usp=sharing here].
* Integrated basic pacing model for New Reno, DCTCP and TCP Prague in ns-3 by adding methods <code> PacingEnabled</code> and <code> UpdatePacingRate</code>. This allows any congestion control to dynamically update its pacing rate depending on whether it is in Slow Start or Congestion Avoidance.
+
* Integrated basic pacing model for New Reno, DCTCP and TCP Prague in ns-3 by adding methods <code> PacingEnabled ()</code> and <code> UpdatePacingRate ()</code>. This allows any congestion control to dynamically update its pacing rate depending on whether it is in Slow Start or Congestion Avoidance.
  
 
=== Week 2 (June 8 - June 14) ===
 
=== Week 2 (June 8 - June 14) ===
* Aligned ns-3 Prague with Linux by enabling <code> TcpPrague::CongControl</code>.
+
* Designed a test suite <code>TcpPacingTest</code> to test TCP packet pacing rate during Slow Start and Congestion Avoidance.
* Designed a test suite <code> TcpPacingTest</code> to test TCP packet pacing rate during Slow Start and Congestion Avoidance.
+
 
* Rebased Joakim Misund's [https://gitlab.com/JoakimMisund/l4s-evaluation/-/tree/tcp-prague/ work] on ns-3 Prague to latest ns-3-dev.
 
* Rebased Joakim Misund's [https://gitlab.com/JoakimMisund/l4s-evaluation/-/tree/tcp-prague/ work] on ns-3 Prague to latest ns-3-dev.
* Generated an [https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/331 MR] to add support for TCP Prague and pacing, along with the above test suite.
+
* Generated an [https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/331 MR] to add support for dynamic pacing, along with the above test suite.
  
 
=== Week 3 (June 15 - June 21) ===
 
=== Week 3 (June 15 - June 21) ===
 
* Worked on fixing a few issues with the MR generated in Week 2.
 
* Worked on fixing a few issues with the MR generated in Week 2.
* Went through the code for RTT Independence in Linux Prague, and gathered a few notes in this [https://docs.google.com/document/d/1uSFm7tdjHJcvLan7vKVtjtj0ZlrwSmoaw_O2-n-qd20/edit?usp=sharing document] (work in progress).
+
* Went through the code for RTT Independence in Linux Prague, and gathered a few notes in this [https://docs.google.com/document/d/1uSFm7tdjHJcvLan7vKVtjtj0ZlrwSmoaw_O2-n-qd20/edit?usp=sharing document].
 
* Added code to enable different scaling heuristics (similar to Linux).
 
* Added code to enable different scaling heuristics (similar to Linux).
<pre>
+
<pre>
 
   typedef enum
 
   typedef enum
 
   {
 
   {
Line 78: Line 77:
 
   } RttScalingMode_t;
 
   } RttScalingMode_t;
 
</pre>
 
</pre>
* The initial commit can be found [https://gitlab.com/deepakkavoor/ns-3-dev/-/commit/d10dcdcd8c7697d0e6f223167b673a79bcc70542 here].
 
  
 
=== Week 4 (June 22 - June 28) ===
 
=== Week 4 (June 22 - June 28) ===
* Divided the MR (from Week 2) to now separately add support for dynamic pacing ([https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/339 !339]) and TCP Prague ([https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/331 !331]).
+
* Divided the MR (from Week 2) to now separately add support for dynamic pacing ([https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/339 !339]) and TCP Prague ([https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/373 !373]).
 
* Ran experiments using Linux namespaces to check the behaviour of TCP flows when dynamic pacing is enabled.
 
* Ran experiments using Linux namespaces to check the behaviour of TCP flows when dynamic pacing is enabled.
* Compared the plots from Linux and ns-3 for congestion window and pacing rate, and observed significant differences; we are currently trying to identify why linux has more frequent cwnd oscillations compared to ns-3.
+
* Compared the plots from Linux and ns-3 for congestion window and pacing rate, and observed several differences; I am trying to identify why Linux has more frequent cwnd oscillations compared to ns-3.
  
 
=== Week 5 (June 29 - July 5)===
 
=== Week 5 (June 29 - July 5)===
Line 95: Line 93:
  
 
=== Week 7 (July 13 - July 19)===
 
=== Week 7 (July 13 - July 19)===
* Explored different topologies and configurations that would show the benefits of TCP pacing.
+
* Explored different topologies and configurations that would show the benefits of dynamic pacing.
 
* Modified the pacing example to follow the topology as given in Figure 2 [https://homes.cs.washington.edu/~tom/pubs/pacing.pdf here].
 
* Modified the pacing example to follow the topology as given in Figure 2 [https://homes.cs.washington.edu/~tom/pubs/pacing.pdf here].
* Continued the work on RTT Independence and added/modified the following methods:
+
* Continued to work on RTT Independence and added/modified the following methods:
 
** <code>TcpPrague::AiAckIncrease ()</code>: Update the per-ACK cWnd AI increase factor depending on the current RTT scaling heuristic.
 
** <code>TcpPrague::AiAckIncrease ()</code>: Update the per-ACK cWnd AI increase factor depending on the current RTT scaling heuristic.
 
** <code>TcpPrague::IncreaseWindow ()</code>: Consider the RTT scaling factor when updating cWnd during AI.
 
** <code>TcpPrague::IncreaseWindow ()</code>: Consider the RTT scaling factor when updating cWnd during AI.
Line 103: Line 101:
  
 
=== Week 8 (July 20 - July 26)===
 
=== Week 8 (July 20 - July 26)===
* Improved and refactored the code for Prague RTT independence.
+
* Improved and refactored the code for Prague RTT independence to align with Linux.
 
* Added unit tests to check correct increment of Congestion window for different RTT scaling heuristics.
 
* Added unit tests to check correct increment of Congestion window for different RTT scaling heuristics.
* Fixed bugs in ECN++ and AccECN code that were causing DCTCP tests to fail.
+
* Fixed [https://gitlab.com/deepakkavoor/ns-3-dev/-/commits/hackathon-prague bugs] in ECN++ and AccECN code that were causing DCTCP tests to fail.
* Participated in the IETF 108 Hackathon and helped with integration of Prague alongside other L4S components.  
+
* Participated in the [https://registration.ietf.org/108/participants/hackathon/ IETF 108 Hackathon] and helped with https://gitlab.com/tomhenderson/ns-3-dev/-/commits/hackathon/master integration] of ns-3 Prague model alongside other L4S components (such as Dual Queue).  
  
 
=== Week 9 (July 27 - August 02)===
 
=== Week 9 (July 27 - August 02)===
* Setup and built a kernel supporting Prague, DualQueue and AccurateEcn by referring to the Linux development branch [https://github.com/l4steam/linux here].
+
* Setup a Linux kernel supporting TCP Prague, Dual Queue model and Accurate Ecn by referring to the contemporary Linux development [https://github.com/l4steam/linux branch] maintained by the L4S team.
* Worked on setting up a [https://gitlab.com/tomhend/modules/l4s-evaluation/-/blob/hackathon/master/examples/tsvwg-scenarios.cc topology] in this kernel using Linux namespaces.
+
* Worked on setting up a [https://gitlab.com/deepakkavoor/nest/-/blob/prague-expt/examples/prague.py topology] in this kernel corresponding to the one-flow scenario using Linux namespaces.
  
 
=== Week 10 (August 03 - August 09)===
 
=== Week 10 (August 03 - August 09)===
* Tried to run experiments with the [https://gitlab.com/tomhend/modules/l4s-evaluation/-/tree/hackathon/master l4s-evaluation] module to show that Prague experiences higher throughput in presence of other Classic flows.
+
* Worked on experiments using the [https://gitlab.com/tomhend/modules/l4s-evaluation/-/tree/hackathon/master l4s-evaluation] module to show that Prague experiences higher throughput in presence of other Classic flows.
  
 
=== Week 11 (August 10 - August 16)===
 
=== Week 11 (August 10 - August 16)===
* Major refactoring of ns-3 Prague code to match the Linux implementation.
+
* Major refactoring of ns-3 Prague code to match the Linux implementation. The following methods were added:
* Validated this implementation against Linux namespaces and obtained alignment in the one-flow scenario.
+
** <code>TcpPrague::UpdateCwnd ()</code>: Update the congestion window on receipt of each ACK, and use a "PRR-like" reduction on ECE marks.
 +
** <code>TcpPrague::UpdateAlpha ()</code>: Update the value of alpha (which corresponds to an EWMA of the fraction of bytes that were CE marked) based on <code>TcpPrague::ShouldUpdateEwma ()</code>.
 +
** <code>TcpPrague::SlowStart ()</code>: When <code>cWnd < ssThresh / 2</code> use a slow start algorithm similar to <code>ns3::TcpLinuxReno</code>.
 +
** <code>TcpPrague::CwndChanged ()</code>: Call <code>TcpPrague::AiAckIncrease</code> whenever congestion window is updated.
 +
** <code>TcpPrague::EnterLoss ()</code>: On encountering a packet loss, gradually reduce congestion window to half its original value.
 +
* Validated this refactored implementation against Linux namespaces and obtained [https://drive.google.com/drive/folders/1qUhWiFwFO9eM8JQZWinMoD2TZVkC4Ca- alignment] in the one-flow scenario.
  
 
=== Week 12 (August 17 - August 23)===
 
=== Week 12 (August 17 - August 23)===
* Worked on obtaining results in the two-flow scenario to test working of RTT independence.
+
* Implemented a [https://gitlab.com/deepakkavoor/nest/-/blob/prague-expt/examples/rtt-indep-prague.py topology] in Linux namespaces corresponding to the two-flow scenario, with Prague and Reno running over a common bottleneck supporting Dual Queue.
* Worked on documentation of ns-3 Prague.
+
* Obtained aligning [https://drive.google.com/drive/folders/1hBZ2SUlfSWEO1gRhXeUmGfAzXmd8DRGJ results] in the two-flow scenario that validates RTT independence in ns-3 Prague with that of Linux.
* Worked on project site.
+
* Worked on adding final documentation of TCP Prague to ns-3.
 +
* Worked on the [https://deepakkavoor.github.io/gsoc-2020-prague/ project site].
  
 
=== Week 13 (August 24 - August 30)===
 
=== Week 13 (August 24 - August 30)===
* Added doxygen comments and slight cleanup of TCP Prague code.
+
* Added doxygen comments to the ns-3 Prague model.
* Setup an [https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/373 MR] for the TCP Prague model.
+
* Updated the [https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/373 MR] for ns-3 Prague model.
* Fixed issues related to delayed acknowledgements in the TCP pacing test suite.
+
* Fixed [https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/339 issues] related to delayed acknowledgements in the TCP pacing test suite.
 
* Worked on understanding how TCP system tests are written in ns-3.
 
* Worked on understanding how TCP system tests are written in ns-3.

Revision as of 16:41, 29 August 2020

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

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

Back to GSoC 2020 projects

Project Overview

  • Project Name: TCP Prague model for ns-3
  • Student: Deepak K
  • Mentors: Ankit Deepak, Mohit Tahiliani, Vivek Jain, Viyom Mittal
  • Project Goals and Outcomes: The original plan at the start of this project was to add TCP Prague to ns-3 mirroring ns-3 DCTCP, implement Classic ECN detection, RTT independence and Dynamic pacing. After several discussions with my mentors, these goals and priorities were altered. The following features have been implemented in ns-3 at the end of this project:
    • Dynamic pacing model in TCP, along with unit tests (link to code)
    • TCP Prague that aligns with contemporary Linux implementation, along with unit tests (link to code)
    • RTT independence in TCP Prague, along with unit tests (link to code)
    • Experiments to generate plots and validate the ns-3 implementation of TCP Prague with Linux (links to results)
  • Future Work: Adding system-wide tests for TCP Prague is something that was in the scope of GSoC work, but could not be fully completed. (I am currently working on these tests). A few features that we chose not to address during GSoC, but would definitely help the ns-3 Prague model include: merging Dual Queue model to ns-3, adding Classic ECN detection to TCP Prague, and merging Accurate ECN to ns-3.
  • Project Page: A project page was also added to give an elaborate explanation of the different features implemented as part of this work.
  • Repository: https://gitlab.com/deepakkavoor/ns-3-dev
  • About Me: I am a third-year undergraduate student pursuing Computer Science and Engineering at the National Institute of Technology Karnataka (NITK), India. My interests include computer networks and cryptography. Previously I have worked on implementing the Set-Associative Hashing feature for Fq-CoDel AQM in ns-3 (link to my commit).

Milestones and Deliverables

Phase 1

This phase implemented the dynamic pacing feature in ns-3 TCP.

  • The outcome was achieving alignment of ns-3 pacing with Linux implementation, which sets the current pacing rate based on the congestion window and prior RTT measurements.
  • On receipt of each ACK, a sender would update the pacing rate as follows: pacingRate = factor * cWnd * MSS / rtt
  • The value of factor depends on whether TCP is currently in Slow Start or Congestion Avoidance. The default values used by Linux are 2 and 1.2 respectively, and we use the same. A higher factor in Slow Start allows TCP to probe for higher speeds early on.
  • A test suite was also added to check that packets are correctly paced out as per the above update equation.
  • The work done in this phase was documented in ns-3.
  • I also tried to designed experiments in ns-3 to show improvements when using dynamic pacing.

Phase 2

This phase implemented the RTT independence feature in ns-3 TCP Prague.

  • The outcome was addition of ns-3 TCP Prague as a mirror of ns-3 DCTCP and implementation of the RTT independence feature following Linux Prague.
  • The cWnd increment during Congestion Avoidance is modified, so that Prague behaves as if it is operating at a (usually higher) target RTT. This reduces unfairness when Prague and other classic congestion controls (such as Reno) coexist within a common bottleneck.
  • There are currently three RTT scaling heuristics in Linux: Rate, Scalable and Additive, and all were implemented in ns-3.
  • As an example, the update equation for congestion window increment on receipt of each ACK using the "Rate" heuristic would be: increment = (curRTT / targetRTT) * (curRTT / targetRTT) * 1 / cWnd, where curRTT denotes the current RTT measurement and targetRTT denotes the target RTT at which Prague is expected to operate.
  • Unit tests were added to check that RTT independence in ns-3 Prague works as expected.
  • The work done in this phase was documented in ns-3.

Phase 3

This phase refactored the ns-3 Prague code to align with Linux.

  • The structure of ns-3 Prague was moved away from ns-3 DCTCP. A "PRR-like" cWnd reduction approach (that Linux follows) was added on receipt of an ACK with ECE mark.
  • Along with this, experiments were conducted to obtain aligning plots between ns-3 and Linux implementations of Prague.
  • We used the one-flow scenario (and two-flow scenario in case of RTT independence) from the l4s-evaluation module to validate ns-3 Prague with Linux. The topology was evaluated in Linux using network namespaces (specifically using the NeST framework).

A more elaborate description of the features added in these phases can be found in the project site. Along with the above features, I also worked on the following aspects that were indirectly related to TCP Prague:

  • ECN++ and Accurate ECN, which were implemented in ns-3 as part of a 2018 GSoC project was rebased onto ns-3-dev, along with a few revisions to test suites. The rebased branch can be found here.

Weekly Reports

Community Bonding Period (May 4 - May 31)

  • Established the Wiki page for this project.
  • Rebased the GSoC 2018 implementation of ECN++ and AccECN (without TCP options) to the latest ns-3-dev.
  • Went through the documentation for TCP model in ns-3 and read about paced chirping.

After a discussion with mentors and the L4S Team, it was decided that the first phase of this project should focus on dynamic pacing in TCP Prague.

Week 1 (June 1 - June 7) (Start of Phase 1)

  • Agreed upon the pacing structure for TCP Prague in ns-3. The document can be found here.
  • Integrated basic pacing model for New Reno, DCTCP and TCP Prague in ns-3 by adding methods PacingEnabled () and UpdatePacingRate (). This allows any congestion control to dynamically update its pacing rate depending on whether it is in Slow Start or Congestion Avoidance.

Week 2 (June 8 - June 14)

  • Designed a test suite TcpPacingTest to test TCP packet pacing rate during Slow Start and Congestion Avoidance.
  • Rebased Joakim Misund's work on ns-3 Prague to latest ns-3-dev.
  • Generated an MR to add support for dynamic pacing, along with the above test suite.

Week 3 (June 15 - June 21)

  • Worked on fixing a few issues with the MR generated in Week 2.
  • Went through the code for RTT Independence in Linux Prague, and gathered a few notes in this document.
  • Added code to enable different scaling heuristics (similar to Linux).
  typedef enum
  {
    RTT_CONTROL_NONE,      //!< No RTT Independence
    RTT_CONTROL_RATE,      //!< Flows with e2e RTT < target try to achieve same throughput
    RTT_CONTROL_SCALABLE,  //!< At low RTT, trade throughput balance for same marks/RTT
    RTT_CONTROL_ADDITIVE   //!< Behave as a flow operating with extra target RTT
  } RttScalingMode_t;

Week 4 (June 22 - June 28)

  • Divided the MR (from Week 2) to now separately add support for dynamic pacing (!339) and TCP Prague (!373).
  • Ran experiments using Linux namespaces to check the behaviour of TCP flows when dynamic pacing is enabled.
  • Compared the plots from Linux and ns-3 for congestion window and pacing rate, and observed several differences; I am trying to identify why Linux has more frequent cwnd oscillations compared to ns-3.

Week 5 (June 29 - July 5)

  • Generated merge requests for ECN++ and AccECN (rebased from Wenying Dai's GSoC 2018 work).
  • Added dynamic pacing to other congestion controls in ns-3.
  • Analyzed packet traces (using Wireshark) for topologies designed in Linux namespaces, and inferred the following: if a Linux TCP sender has more than two eligible packets to be sent, the first two are sent back-to-back, and the rest are paced out.

Week 6 (July 6 - July 12)

  • Extended examples/tcp/tcp-pacing.cc to highlight dynamic pacing and produce time-series plots of Congestion Window, Slow Start threshold and current Pacing Rate.
  • Added documentation regarding dynamic pacing in ns-3, and its similarities and differences to that in Linux.

Week 7 (July 13 - July 19)

  • Explored different topologies and configurations that would show the benefits of dynamic pacing.
  • Modified the pacing example to follow the topology as given in Figure 2 here.
  • Continued to work on RTT Independence and added/modified the following methods:
    • TcpPrague::AiAckIncrease (): Update the per-ACK cWnd AI increase factor depending on the current RTT scaling heuristic.
    • TcpPrague::IncreaseWindow (): Consider the RTT scaling factor when updating cWnd during AI.
    • TcpPrague::PktsAcked (): Apply the EWMA update equation and increase round count only if the value returned by TcpPrague::ShouldUpdateEwma () is true.

Week 8 (July 20 - July 26)

  • Improved and refactored the code for Prague RTT independence to align with Linux.
  • Added unit tests to check correct increment of Congestion window for different RTT scaling heuristics.
  • Fixed bugs in ECN++ and AccECN code that were causing DCTCP tests to fail.
  • Participated in the IETF 108 Hackathon and helped with https://gitlab.com/tomhenderson/ns-3-dev/-/commits/hackathon/master integration] of ns-3 Prague model alongside other L4S components (such as Dual Queue).

Week 9 (July 27 - August 02)

  • Setup a Linux kernel supporting TCP Prague, Dual Queue model and Accurate Ecn by referring to the contemporary Linux development branch maintained by the L4S team.
  • Worked on setting up a topology in this kernel corresponding to the one-flow scenario using Linux namespaces.

Week 10 (August 03 - August 09)

  • Worked on experiments using the l4s-evaluation module to show that Prague experiences higher throughput in presence of other Classic flows.

Week 11 (August 10 - August 16)

  • Major refactoring of ns-3 Prague code to match the Linux implementation. The following methods were added:
    • TcpPrague::UpdateCwnd (): Update the congestion window on receipt of each ACK, and use a "PRR-like" reduction on ECE marks.
    • TcpPrague::UpdateAlpha (): Update the value of alpha (which corresponds to an EWMA of the fraction of bytes that were CE marked) based on TcpPrague::ShouldUpdateEwma ().
    • TcpPrague::SlowStart (): When cWnd < ssThresh / 2 use a slow start algorithm similar to ns3::TcpLinuxReno.
    • TcpPrague::CwndChanged (): Call TcpPrague::AiAckIncrease whenever congestion window is updated.
    • TcpPrague::EnterLoss (): On encountering a packet loss, gradually reduce congestion window to half its original value.
  • Validated this refactored implementation against Linux namespaces and obtained alignment in the one-flow scenario.

Week 12 (August 17 - August 23)

  • Implemented a topology in Linux namespaces corresponding to the two-flow scenario, with Prague and Reno running over a common bottleneck supporting Dual Queue.
  • Obtained aligning results in the two-flow scenario that validates RTT independence in ns-3 Prague with that of Linux.
  • Worked on adding final documentation of TCP Prague to ns-3.
  • Worked on the project site.

Week 13 (August 24 - August 30)

  • Added doxygen comments to the ns-3 Prague model.
  • Updated the MR for ns-3 Prague model.
  • Fixed issues related to delayed acknowledgements in the TCP pacing test suite.
  • Worked on understanding how TCP system tests are written in ns-3.