Difference between revisions of "ECN support for qdiscs in ns-3"

From Nsnam
Jump to: navigation, search
Line 115: Line 115:
 
<u>ipv4-header.h and ipv4-header.cc</u>  
 
<u>ipv4-header.h and ipv4-header.cc</u>  
 
<pre>
 
<pre>
Ipv4 header also has the ECNtype enum with all 4 ECN codepoints  defined and also the setter(SetEcn()) and getter(GetEcn()) functions to set ECN values in m_tos and retrieve it. These functions haven’t been used in the implementation of any modules.  
+
Ipv4 header also has the ECNtype enum with all 4 ECN codepoints  defined and also the setter(SetEcn()) and getter
We will use these  setter and getter function for the  ECN manipulation in IPv4.
+
(GetEcn()) functions to set ECN values in m_tos and retrieve it. These functions haven’t been used in the implementation  
 +
of any modules. We will use these  setter and getter function for the  ECN manipulation in IPv4.
 
</pre>
 
</pre>
  
Line 122: Line 123:
  
 
<pre>
 
<pre>
* Declare Mark () method in QueueDiscItem :
+
* Declare Mark () method in QueueDiscItem :Mark () method has been declared as virtual in QueueDiscItem class in  
Mark () method has been declared as virtual in QueueDiscItem class in queue-disc.h because  
+
  queue-disc.h because marking is a feature that can be applied to a queue disc item. Classes in the internet model,  
marking is a feature that can be applied to a queue disc item. Classes in the internet model,  
+
  that inherit the QueueDiscItem, can implement the Mark () method based on the requirement.
that inherit the QueueDiscItem, can implement the Mark () method based on the requirement.
+
 
* List of methods to be modified to include ECN support :
+
* List of methods to be modified to include ECN support : DoEnqueue method in red-queue-disc.cc
  DoEnqueue method in red-queue-disc.cc
+
 
* Trace sources required for ECN :
+
* Trace sources required for ECN :In order to keep track of the statistics of forced and unforced marks, new variables  
In order to keep track of the statistics of forced and unforced marks, new variables of type  
+
  of type Stats should be implemented in red-queue-disc.cc. If the packet is marked, then there should be no forced or  
Stats should be implemented in red-queue-disc.cc. If the packet is marked, then there should  
+
  unforced drops.
be no forced or unforced drops.
+
 
</pre>
 
</pre>
  
Line 138: Line 138:
 
Following methods have been added to support ECN marking by queue discs:
 
Following methods have been added to support ECN marking by queue discs:
  
* IsEcnCapable () method: declared in queue-disc.h, ipv4-queue-disc-item.h  and implemented in  
+
* IsEcnCapable () method: declared in queue-disc.h, ipv4-queue-disc-item.h  and implemented in ipv4-queue-disc-item.cc.  
ipv4-queue-disc-item.cc. It is a boolean method and returns true if the packet is ECN-capable
+
  It is a boolean method and returns true if the packet is ECN-capable i.e., packets have ECT(0) or ECT(1) bit set in  
i.e., packets have ECT(0) or ECT(1) bit set in IP header.
+
  IP header.
  
* Mark () method: declared in queue-disc.h, ipv4-queue-disc-item.h and implemented in  
+
* Mark () method: declared in queue-disc.h, ipv4-queue-disc-item.h and implemented in ipv4-queue-disc-item.cc. It is a
ipv4-queue-disc-item.cc. It is a boolean method and returns true if marking the packet happens  
+
  boolean method and returns true if marking the packet happens successfully, i.e., it successfully sets the CE bit in  
successfully, i.e., it successfully sets the CE bit in IP header. The Mark () method calls the  
+
  IP header. The Mark () method calls the IsEcnCapable () method and marks the packet only if it is ECN-capable.
IsEcnCapable () method and marks the packet only if it is ECN-capable.
+
  
* IsMarked () method: declared in queue-disc.h, ipv4-queue-disc-item.h and implemented in  
+
* IsMarked () method: declared in queue-disc.h, ipv4-queue-disc-item.h and implemented in ipv4-queue-disc-item.cc. It is  
ipv4-queue-disc-item.cc. It is a boolean method and returns true if the packet is already
+
  a boolean method and returns true if the packet is already marked, i.e., it has CE bit already set (whether to update  
marked, i.e., it has CE bit already set (whether to update the unforcedMark or forcedMark  
+
  the unforcedMark or forcedMark stats in such cases is yet to be decided).  
stats in such cases is yet to be decided).  
+
  
 
</pre>
 
</pre>
Line 158: Line 156:
 
Following changes were made to incorporate ECN functionality in RED QueueDisc
 
Following changes were made to incorporate ECN functionality in RED QueueDisc
 
   
 
   
* The variables unforcedMark and forcedMark were added to the existing Stats in  
+
* The variables unforcedMark and forcedMark were added to the existing Stats in queue-disc-item.h, as shown below:
queue-disc-item.h, as shown below:
+
 
Stats {
 
Stats {
 
...
 
...
Line 166: Line 163:
 
}
 
}
  
They keep track of the packets which were marked either due to early probability (unforced)  
+
They keep track of the packets which were marked either due to early probability (unforced) or when qAvg exceeded the  
or when qAvg exceeded the max-threshold (forced), respectively.
+
max-threshold (forced), respectively.
  
* In DoEnqueue method, before calling  the Drop () method in forced and unforced cases,
+
* In DoEnqueue method, before calling  the Drop () method in forced and unforced cases, Mark () is called to check if the  
Mark () is called to check if the packet can be marked. If the packet cannot be marked  
+
  packet can be marked. If the packet cannot be marked (because it is not ECN capable), Drop () method is called and the  
(because it is not ECN capable), Drop () method is called and the Stats of drop are updated,  
+
  Stats of drop are updated, else the Stats of mark are updated.
else the Stats of mark are updated.
+
  
* Bug 2485 (https://www.nsnam.org/bugzilla/show_bug.cgi?id=2485) was spotted in this week and  
+
* Bug 2485 (https://www.nsnam.org/bugzilla/show_bug.cgi?id=2485) was spotted in this week and a patch to fix the same  
a patch to fix the same was developed.
+
  was developed.
  
 
</pre>
 
</pre>
Line 181: Line 177:
 
Tests for ECN functionality in RED QueueDisc
 
Tests for ECN functionality in RED QueueDisc
 
<pre>
 
<pre>
In order to test the functionality of ECN extension for RED, ecn-red-queue-disc-test-suite.cc  
+
In order to test the functionality of ECN extension for RED, ecn-red-queue-disc-test-suite.cc has been developed.It depends  
has been developed.It depends on the internet model and hence are placed in src/test/ns3tc.  
+
on the internet model and hence are placed in src/test/ns3tc.  
  
The total of six test cases are provided, which include, verifying that there should be no  
+
The total of six test cases are provided, which include, verifying that there should be no forcedDrop or unforIncedDrop  
forcedDrop or unforIncedDrop when ECN marking is enabled, and similarly, there should be no  
+
when ECN marking is enabled, and similarly, there should be no forcedMark or unforcedMark when ECN marking is disabled.
forcedMark or unforcedMark when ECN marking is disabled.
+
 
</pre>
 
</pre>
  
 
=== '''Week 5''' ===
 
=== '''Week 5''' ===
 
<pre>
 
<pre>
ECN support for IPv6:
+
* ECN support for IPv6:
Implemented the ECN codepoints, setter and getter functions for ECN in IPv6. ECN for IPv6 is  
+
Implemented the ECN codepoints, setter and getter functions for ECN in IPv6. ECN for IPv6 is quite similar to that of IPv4  
quite similar to that of IPv4 except for the following difference:
+
except for the following difference:
In IPv4, ECN bits are the last 2 bits in TOS field and occupy 14th and 15th bit in IPv4 header,  
+
* In IPv4, ECN bits are the last 2 bits in TOS field and occupy 14th and 15th bit in IPv4 header, whereas in IPv6, ECN bits  
whereas in IPv6, ECN bits are the last 2 bits of the Traffic class and occupy 10th and 11th bit  
+
  are the last 2 bits of the Traffic class and occupy 10th and 11th bit in the IPv6 header.  
in the IPv6 header.  
+
  
 
In ipv6-header.h, following codepoints and functions are declared:
 
In ipv6-header.h, following codepoints and functions are declared:
Line 226: Line 220:
 
   std::string EcnTypeToString (EcnType ecn) const;
 
   std::string EcnTypeToString (EcnType ecn) const;
  
In ipv6-queue-disc-item.h the following functions have been declared and they are implemented  
+
In ipv6-queue-disc-item.h the following functions have been declared and they are implemented in ipv6-queue-disc-item.cc
in ipv6-queue-disc-item.cc
+
  
 
virtual bool Mark ()
 
virtual bool Mark ()
Line 234: Line 227:
  
 
These functions are similar to the ones implemented in ipv4-queue-disc-item.cc
 
These functions are similar to the ones implemented in ipv4-queue-disc-item.cc
A test suite named ecn-ipv6-red-queue-disc-test-suite.cc is also provided in src/test/ns3tc to  
+
A test suite named ecn-ipv6-red-queue-disc-test-suite.cc is also provided in src/test/ns3tc to verify the working of ECN  
verify the working of ECN on RED QueueDisc with IPv6.
+
on RED QueueDisc with IPv6.
  
 
</pre>
 
</pre>

Revision as of 13:11, 29 August 2016

Project overview

  • Project: Enabling support for Explicit Congestion Notification (ECN) in ns-3 queue disciplines
  • Student: Shravya Kaudki Srinivas
  • Mentors: Mohit P. Tahiliani , Tom Henderson
  • Abstract: Explicit Congestion Notification (RFC 3168) is a mechanism for Active Queue Management (AQM) to notify endpoints of congestion that may be developing in a bottleneck queue, without resorting to packet drops. In ns-3, the current queue disciplines (e.g., RED) only support packet drops but not an ECN mode of operation. In this work, I plan to implement ECN mechanism in ns-3, enable its support in QueueDiscs and write tests to verify its functionality.
  • Project Code : ns3-ecn
  • Reference: The Addition of Explicit Congestion Notification (ECN) to IP (RFC 3168)
  • About me: I am pursuing B.Tech in Computer Science from National Institute of Technology Karnataka, Surathkal, India. Currently, I am a Mitacs intern working under Dr. Ehab Elmallah on Wireless Underwater Sensor Networks at University of Alberta, Canada.

Overview of ECN

ECN uses two bits in the IP header: ECN Capable Transport (ECT bit) and Congestion Experienced (CE bit), and two bits in the TCP header: Congestion Window Reduced (CWR) and ECN Echo (ECE). ns-3-dev already provides an implementation of ECN bits in the IP and TCP headers along with necessary setters and getters.

Although there has been a previous attempt to implement ECN in ns-3 [1], the approach adopted was non-trivial because of the lack of traffic-control layer in ns-3. Recently, traffic-control layer has been merged in the mainline of ns-3 and I plan to use the same for implementing ECN.

[1] Implementing explicit congestion notification in ns-3

Design assumptions and requirements

  1. Current behavior and performance of RED queue should be unaffected by the addition of ECN, if ECN is not in use.
  2. It should be possible to enable and disable ECN marking on a per-queue basis.
  3. Statistics for packets marked should be kept, and should be separate from drop statistics.
  4. A "Mark" trace source should be provided. It may or may not be appropriate to keep this in the QueueDisc base class, where a "Drop" trace source already exists, since marking may not be applicable to all QueueDiscs. (This item is an open issue)

Implementation plan

The overall implementation is planned for two phases. In the first phase, ECN marking capability will be provided to RED queue, and the capability will be unit tested by injecting packets directly to the queue disc, without the operation of TCP. In the second phase, TCP will be extended to support ECN, and the RED queue disc will be tested with TCP flows.

Weekly plan

Week 1 (July 19 - July 25)

* Walk through of RFC 3168
* Walk through of TrafficControlLayer and QueueDisc classes
* Walk through of RedQueueDisc class

Week 2 (July 26 - Aug 1)

* Prepare a plan to implement Mark() method. It includes identifying an appropriate class to contain this 
  method (i.e., QueueDisc or RedQueueDisc)
* Understanding the scope of existing trace sources in case of marking a packet and the need of new ones
* List the method(s) in RedQueueDisc that require modification to support ECN marking.

Week 3 (Aug 2 - Aug 8)

* Get the plan reviewed by mentors and make revisions to it
* Implement Mark () method. This method would check whether ECT bit is enabled, and if so, will set CE bit 
  in IPv4 header when RED detects congestion
* Provide support for generating ECN related stats (e.g., unforcedMark and forcedMark)

Week 4 (Aug 9 - Aug 15)

* Write unit tests by injecting packets directly to RedQueueDisc to verify the functionality of Mark(). These 
  tests will be defined in the internet module.
* Update the documentation
* Clean up the code and submit a patch for review

The first phase of the project gets completed here, and a mid term review can be scheduled around this period.

Week 5 (Aug 16 - Aug 22)

* Extend TCP to support ECN. It includes negotiating ECN feature during the handshake
* Update the documentation

Week 6 (Aug 23 - Aug 29)

* Test the implementation of ECN in RedQueueDisc with TCP flows
* Update the documentation
* Get feedback from the mentors and reviewers

Week 7 (Aug 30 - Sept 5)

* Extend other AQMs to support ECN
* Write unit tests for ECN support in each AQM
* Update the documentation

Week 8 (Sept 6 - Sept 12)

* Provide some examples for the user
* Update the documentation
* Incorporate final suggestions from the mentors and reviewers
* Make code merge ready

Weekly Progress

Week 1

After going through the existing TCP and IP model of ns-3, here are the points I found out:

tcp-header.h and tcp-header.cc

The TCP header has last 2 bits reserved for ECN, i.e ECE|CWR is already present

SetFlag(int)-> This function is used to set m_flags variable of TCP header. The current documentation mention it to be 
working as only a uint6_t variable as only 6 bits are in use, we will make use of the last two reserved bits for ECN. Since 
the function is already implemented we will call this with modified parameter.

For example: The negotiation step of ECN Enable TCP connection will be 
Sender to Receiver -> SetFlag(TcpHeader::SYN | TcpHeader::ECE | TcpHeader::CWR)
Receiver to Sender -> SetFlag(TcpHeader::SYN | TcpHeader::ECE | TcpHeader::ACK)
Sender to Receiver -> SetFlag(TcpHeader::ACK)

ipv4-header.h and ipv4-header.cc

Ipv4 header also has the ECNtype enum with all 4 ECN codepoints  defined and also the setter(SetEcn()) and getter
(GetEcn()) functions to set ECN values in m_tos and retrieve it. These functions haven’t been used in the implementation 
of any modules. We will use these  setter and getter function for the  ECN manipulation in IPv4.

Week 2

* Declare Mark () method in QueueDiscItem :Mark () method has been declared as virtual in QueueDiscItem class in 
  queue-disc.h because marking is a feature that can be applied to a queue disc item. Classes in the internet model, 
  that inherit the QueueDiscItem, can implement the Mark () method based on the requirement.

* List of methods to be modified to include ECN support : DoEnqueue method in red-queue-disc.cc

* Trace sources required for ECN :In order to keep track of the statistics of forced and unforced marks, new variables 
  of type Stats should be implemented in red-queue-disc.cc. If the packet is marked, then there should be no forced or 
  unforced drops.

Week 3

Following methods have been added to support ECN marking by queue discs:

* IsEcnCapable () method: declared in queue-disc.h, ipv4-queue-disc-item.h  and implemented in ipv4-queue-disc-item.cc. 
  It is a boolean method and returns true if the packet is ECN-capable i.e., packets have ECT(0) or ECT(1) bit set in 
  IP header.

* Mark () method: declared in queue-disc.h, ipv4-queue-disc-item.h and implemented in ipv4-queue-disc-item.cc. It is a  
  boolean method and returns true if marking the packet happens successfully, i.e., it successfully sets the CE bit in 
  IP header. The Mark () method calls the IsEcnCapable () method and marks the packet only if it is ECN-capable.

* IsMarked () method: declared in queue-disc.h, ipv4-queue-disc-item.h and implemented in ipv4-queue-disc-item.cc. It is 
  a boolean method and returns true if the packet is already marked, i.e., it has CE bit already set (whether to update 
  the unforcedMark or forcedMark  stats in such cases is yet to be decided). 

Week 4

Following changes were made to incorporate ECN functionality in RED QueueDisc
 
* The variables unforcedMark and forcedMark were added to the existing Stats in queue-disc-item.h, as shown below:
Stats {
...
uint32_t unforcedMark;  //!< Early probability marks
uint32_t forcedMark;    //!< Forced mark, qavg > max threshold
}

They keep track of the packets which were marked either due to early probability (unforced) or when qAvg exceeded the 
max-threshold (forced), respectively.

* In DoEnqueue method, before calling  the Drop () method in forced and unforced cases, Mark () is called to check if the 
  packet can be marked. If the packet cannot be marked (because it is not ECN capable), Drop () method is called and the 
  Stats of drop are updated, else the Stats of mark are updated.

* Bug 2485 (https://www.nsnam.org/bugzilla/show_bug.cgi?id=2485) was spotted in this week and a patch to fix the same 
  was developed.

Tests for ECN functionality in RED QueueDisc

In order to test the functionality of ECN extension for RED, ecn-red-queue-disc-test-suite.cc has been developed.It depends 
on the internet model and hence are placed in src/test/ns3tc. 

The total of six test cases are provided, which include, verifying that there should be no forcedDrop or unforIncedDrop 
when ECN marking is enabled, and similarly, there should be no forcedMark or unforcedMark when ECN marking is disabled.

Week 5

* ECN support for IPv6:
Implemented the ECN codepoints, setter and getter functions for ECN in IPv6. ECN for IPv6 is quite similar to that of IPv4 
except for the following difference:
* In IPv4, ECN bits are the last 2 bits in TOS field and occupy 14th and 15th bit in IPv4 header, whereas in IPv6, ECN bits 
  are the last 2 bits of the Traffic class and occupy 10th and 11th bit in the IPv6 header. 

In ipv6-header.h, following codepoints and functions are declared:

enum EcnType
   {
     // Prefixed with "ECN" to avoid name clash
     ECN_NotECT = 0x00,
     ECN_ECT1 = 0x01,
     ECN_ECT0 = 0x02,
     ECN_CE = 0x03
   }; 

  /**
   * \brief Set ECN Field
   * \param ecn ECN Type
   */
  void SetEcn (EcnType ecn);
 
  /**
   * \return the ECN field of this packet.
   */
  EcnType GetEcn (void) const;

  /**
   * \param ecn the ECNType
   * \return std::string of ECNType
   */
  std::string EcnTypeToString (EcnType ecn) const;

In ipv6-queue-disc-item.h the following functions have been declared and they are implemented in ipv6-queue-disc-item.cc

virtual bool Mark ()
virtual bool IsMarked ()
bool IsEcnCapable ()

These functions are similar to the ones implemented in ipv4-queue-disc-item.cc
A test suite named ecn-ipv6-red-queue-disc-test-suite.cc is also provided in src/test/ns3tc to verify the working of ECN 
on RED QueueDisc with IPv6.