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

From Nsnam
Jump to: navigation, search
(Week 4(Aug 9- Aug 16))
(Final Review)
 
(45 intermediate revisions by 2 users not shown)
Line 4: Line 4:
 
* '''Mentors:''' [mailto:tahiliani.nitk@gmail.com Mohit P. Tahiliani] , [mailto:tomh@tomh.org Tom Henderson]
 
* '''Mentors:''' [mailto:tahiliani.nitk@gmail.com Mohit P. Tahiliani] , [mailto:tomh@tomh.org 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.
 
* '''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 :''' [https://github.com/shravya-ks/ECN-ns3 ns3-ecn]
+
* '''Project Code :'''  
 +
*[https://github.com/shravya-ks/ns-3-dev-git/tree/ecn-queue Phase 1: ECN implementation for queue discs]
 +
*[https://github.com/shravya-ks/ns-3-dev-git/tree/ecn-tcp Phase 2: ECN implementation for TCP]
 
* '''Reference:''' The Addition of Explicit Congestion Notification (ECN) to IP ([https://tools.ietf.org/html/rfc3168  RFC 3168])
 
* '''Reference:''' The Addition of Explicit Congestion Notification (ECN) to IP ([https://tools.ietf.org/html/rfc3168  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.
 
* '''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.
Line 29: Line 31:
 
   
 
   
 
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.
 
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.
 +
 +
The weekly progress report for week 6 describes the TCP implementation plan.
  
 
== Weekly plan ==
 
== Weekly plan ==
  
=== '''Week 1''' ===
+
=== '''Week 1 (July 19 - July 25)''' ===
 
<pre>
 
<pre>
 
* Walk through of RFC 3168
 
* Walk through of RFC 3168
Line 39: Line 43:
 
</pre>
 
</pre>
  
=== '''Week 2''' ===
+
=== '''Week 2 (July 26 - Aug 1)''' ===
 
<pre>
 
<pre>
 
* Prepare a plan to implement Mark() method. It includes identifying an appropriate class to contain this  
 
* Prepare a plan to implement Mark() method. It includes identifying an appropriate class to contain this  
   method (i.e., QueueDisc or   RedQueueDisc)
+
   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
 
* 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.
 
* List the method(s) in RedQueueDisc that require modification to support ECN marking.
 
</pre>
 
</pre>
  
=== '''Week 3''' ===
+
=== '''Week 3 (Aug 2 - Aug 8)''' ===
 
<pre>
 
<pre>
 
* Get the plan reviewed by mentors and make revisions to it
 
* Get the plan reviewed by mentors and make revisions to it
Line 65: Line 69:
 
The first phase of the project gets completed here, and a mid term review can be scheduled around this period.
 
The first phase of the project gets completed here, and a mid term review can be scheduled around this period.
  
=== '''Week 5''' ===
+
=== '''Week 5 (Aug 16 - Aug 22)''' ===
 
<pre>
 
<pre>
 
* Extend TCP to support ECN. It includes negotiating ECN feature during the handshake
 
* Extend TCP to support ECN. It includes negotiating ECN feature during the handshake
Line 71: Line 75:
 
</pre>
 
</pre>
  
=== '''Week 6''' ===
+
=== '''Week 6 (Aug 23 - Aug 29) ''' ===
 
<pre>
 
<pre>
 
* Test the implementation of ECN in RedQueueDisc with TCP flows
 
* Test the implementation of ECN in RedQueueDisc with TCP flows
Line 78: Line 82:
 
</pre>
 
</pre>
  
=== '''Week 7''' ===
+
=== '''Week 7 (Aug 30 - Sept 5)''' ===
 
<pre>
 
<pre>
 
* Extend other AQMs to support ECN
 
* Extend other AQMs to support ECN
Line 85: Line 89:
 
</pre>
 
</pre>
  
=== '''Week 8''' ===
+
=== '''Week 8 (Sept 6 - Sept 12)''' ===
 
<pre>
 
<pre>
 
* Provide some examples for the user
 
* Provide some examples for the user
Line 94: Line 98:
  
 
== Weekly Progress ==
 
== Weekly Progress ==
=== '''Week 1''' ===
+
=== '''Week 1 (July 19 - July 25)''' ===
 
<pre>
 
<pre>
After going through the existing tcp and ip model of ns-3 , here are the points I found out:
+
After going through the existing TCP and IP model of ns-3, here are the points I found out:
 
</pre>
 
</pre>
  
 
<u> tcp-header.h and tcp-header.cc</u>  
 
<u> tcp-header.h and tcp-header.cc</u>  
 
<pre>
 
<pre>
The tcp header has last 2 bits reserved for ecn, i.e Ece|cwr is already present
+
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
+
SetFlag(int)-> This function is used to set m_flags variable of TCP header. The current documentation mention it to be  
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
+
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.  
implemented we will call this with modified parameter.
+
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  
 
For example: The negotiation step of ECN Enable TCP connection will be  
Line 111: Line 115:
 
Receiver to Sender -> SetFlag(TcpHeader::SYN | TcpHeader::ECE | TcpHeader::ACK)
 
Receiver to Sender -> SetFlag(TcpHeader::SYN | TcpHeader::ECE | TcpHeader::ACK)
 
Sender to Receiver -> SetFlag(TcpHeader::ACK)
 
Sender to Receiver -> SetFlag(TcpHeader::ACK)
 +
 
</pre>
 
</pre>
 
<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  
+
IPv4 header also has the EcnType enum with all 4 ECN codepoints  defined and also the setter(SetEcn()) and getter
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  
+
(GetEcn()) functions to set ECN values in m_tos and retrieve it. These functions haven’t been used in the implementation  
setter and getter function for the  ECN manipulation in Ipv4.
+
of any modules. We will use these setter and getter function for the  ECN manipulation in IPv4.
 +
</pre>
  
 +
=== '''Week 2 (July 26 - Aug 1)''' ===
  
 +
<pre>
 +
* 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 in RED QueueDisc 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.
 
</pre>
 
</pre>
 +
 +
=== '''Week 3 (Aug 2 - Aug 8)''' ===
 +
<pre>
 +
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).
 +
 +
</pre>
 +
 +
=== '''Week 4 (Aug 9 - Aug 15)''' ===
 +
<pre>
 +
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.
 +
 +
</pre>
 +
 +
<u>Tests for ECN functionality in RED QueueDisc </u>
 +
<pre>
 +
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 is 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.
 +
</pre>
 +
 +
=== '''Week 5 (Aug 16 - Aug 22)''' ===
 +
 +
<u> ECN support for IPv6 </u>
 +
<pre>
 +
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.
 +
 +
</pre>
 +
 +
=== '''Week 6 (Aug 23 - Aug 29)''' ===
 +
<pre>
 +
* Patch posted for mid-term review here: https://codereview.appspot.com/304520043/
 +
</pre>
 +
 +
<u> ECN support for TCP </u>
 +
<pre>
 +
* Following ECN states have been declared in src/internet/model/tcp-socket.h
 +
 +
typedef enum {
 +
    NO_ECN = 0,      //!< ECN disabled traffic
 +
    ECN_IDLE,        //!< ECN is enabled  but currently there is no action pertaining to ECE or CWR to be taken
 +
    ECN_CE_RCVD,      //!< This state indicates that the receiver has received a packet with CE bit set in IP header
 +
    ECN_ECE_SENT,    //!< This state indicates that the receiver has sent an ACK with ECE bit set in TCP header
 +
    ECN_ECE_RCVD,    //!< This state indicates that the sender has received an ACK with ECE bit set in TCP header
 +
    ECN_CWR_SENT      //!< This state indicates that the sender has reduced the congestion window, and sent a packet
 +
                        with CWR bit set in TCP header
 +
  } EcnStates_t;
 +
 +
* Following ECN parameters were added in src/internet/model/tcp-socket-base.h
 +
 +
// ECN parameters
 +
bool                    m_ecn;            //!< Socket ECN capability
 +
TracedValue<EcnStates_t> m_ecnState;        //!< Current ECN State, represented as combination of EcnState values
 +
TracedValue<SequenceNumber32> m_ecnEchoSeq; //< Sequence number of the last received  ECN Echo
 +
 +
* In src/internet/model/tcp-header.cc, a minor change has been made to TcpHeader::Deserialize method to account for
 +
the ECN bits in TCP header.
 +
 +
Initially it was:
 +
m_flags = field & 0x3F;
 +
 +
Now it is:
 +
m_flags = field & 0xFF;
 +
 +
* ECN negotiation has been implemented, and following are the steps for same:
 +
 +
1. Sender sends SYN + CWR + ECE
 +
Methods modified: DoConnect ( ), DoRetransmit ( )
 +
Changes required while sending SYN packet :
 +
if (m_ecn)
 +
  {
 +
    SendEmptyPacket (TcpHeader::SYN | TcpHeader::ECE | TcpHeader::CWR);
 +
  }
 +
else
 +
  {
 +
    SendEmptyPacket (TcpHeader::SYN);
 +
  }
 +
m_ecnState = NO_ECN;
 +
 +
2. Receiver sends SYN + ACK + ECE
 +
Methods modified: ProcessSynSent( ) , ProcessSynRcvd ( ), CompleteFork ( )
 +
Changes required while sending SYN + ACK packet :
 +
if (m_ecn && (tcpHeader.GetFlags () & (TcpHeader::CWR | TcpHeader::ECE)) == (TcpHeader::CWR | TcpHeader::ECE))
 +
  {
 +
    SendEmptyPacket (TcpHeader::SYN | TcpHeader::ACK |TcpHeader::ECE);
 +
    m_ecnState = ECN_IDLE;
 +
  }
 +
else
 +
  {
 +
    SendEmptyPacket (TcpHeader::SYN | TcpHeader::ACK);
 +
    m_ecnState = NO_ECN;
 +
  }
 +
 +
3. Sender sends ACK
 +
Methods modified: ProcessSynSent ( )
 +
Changes required while sending an ACK packet :
 +
if (m_ecn &&  (tcpHeader.GetFlags () & (TcpHeader::CWR | TcpHeader::ECE)) == (TcpHeader::ECE))
 +
  {
 +
    m_ecnState = ECN_IDLE;
 +
  }
 +
else
 +
  {
 +
    m_ecnState = NO_ECN;
 +
  }
 +
 +
Once the ECN-negotiation is successful, sender sends data packets with ECT bits set.
 +
 +
Note: As mentioned in Section 6.1.1 of RFC 3168, ECT bits should not be set during ECN negotiation.
 +
ECN negotiation implemented in ns-3 follows this guideline.
 +
 +
* To inform the IP-layer to send packets with ECT bit set, packet tag has been added.
 +
 +
For IPv4 :
 +
ipTosTag.SetTos (GetTos( ) | 0x02);
 +
p->AddPacketTag (ipTosTag);
 +
 +
For IPv6 :
 +
ipTclassTag.SetTclass (GetIpv6Tclass () | 0x2);
 +
p->AddPacketTag (ipTclassTag);
 +
</pre>
 +
 +
=== '''Week 7 (Aug 30 - Sept 5)''' ===
 +
<pre>
 +
* We received following suggestions on our mid-term patch:
 +
 +
1. Use m_header in Mark( ) implementation in Ipv{4,6}QueueDiscItem instead of removing, modifying and re-adding
 +
  the IP header.
 +
 +
2. Remove IsEcnCapable ( ) as the implementation is simple  and can be directly implemented as follows:
 +
  (m_header.GetEcn ( ) == Ipv4Header::ECN_ECT1 || m_header.GetEcn () == Ipv4Header::ECN_ECT0)
 +
 +
3. Remove IsMarked ( ) function. The IsMarked( ) function was implemented because of the use-case to check if the
 +
  queue was trying to mark an already marked packet.  However, whether the item is already marked or not causes any
 +
  change in queue disc behavior.
 +
 +
* The suggested modifications were incorporated, and a new patch was uploaded to Rietveld.
 +
See Patch 2 for the modified code: https://codereview.appspot.com/304520043/
 +
 +
</pre>
 +
 +
<u> ECN Support for TCP continued ...</u>
 +
 +
<pre>
 +
* Incorporated the following functionalities in tcp-socket-base.cc:
 +
 +
1. TCP Receiver sets ECE bit in the ACK sent to sender in following cases :
 +
  A. On receipt of a packet with CE bit set. The IPv4 header in tcp-socket-base is available in the function
 +
      TcpSocketBase::ForwardUp and the IPv6 header is available in the function TcpSocketBase::ForwardUp6
 +
  B. If the receiver sent the last ACK with ECE bit set, and the sender has not yet responded to the ECE notification. 
 +
2.  TCP Sender reacts to the congestion notification indicated by ECE bit set in the ACK from the receiver by doing
 +
    the following :
 +
  A. Halves the congestion window
 +
  B. Sets the ssthreshold to cwnd/2
 +
  C. Sets CWR flags in the subsequent data packets sent to receiver
 +
 +
 +
* ECN State Transitions:
 +
1. Initially both sender and receiver have their m_ecnState set as NO_ECN
 +
2. Once, the ECN negotiation is successful, their states are set to ECN_IDLE
 +
3. On receipt of a packet with CE bits set in IP header, receiver changes it’s state to ECN_CE_RCVD
 +
4. When the receiver sends an ACK with ECE bit set, it’s state is set as ECN_ECE_SENT
 +
5. When the sender receives an ACK with ECE bit set from receiver, it’s state is set as ECN_ECE_RCVD
 +
6. When the sender sends the packet with CWR bit set, it’s state is set as ECN_CWR_SENT
 +
7. When the receiver receives the packet with CWR bit set, it’s state is set as ECN_IDLE
 +
</pre>
 +
 +
=== '''Week 8 (Sept 6 - Sept 12)''' ===
 +
<pre>
 +
* Depending on the suggestions provided in RFC 3168, following features have been ensured while implementing
 +
  ECN support for TCP:
 +
 +
1. Pure ACK packets should not have ECT bit set (Section 6.1.4).
 +
2. Retransmitted packets should not have ECT bit set in order to prevent DoS attack (Section 6.1.5).
 +
3. Sender should should reduce the congestion window only once in each window (Section 6.1.2).
 +
4. Receiver should ignore the CE bits set in the packet which arrived out of window (Section  6.1.5).
 +
5. Sender should ignore the ECE bits set in the packet which arrived out of window (Section 6.1.2).
 +
 +
* Following issues are to be addressed, and any suggestions in these directions would be much appreciated:
 +
 +
1. Retransmitted packets with CWR bit set should not have CWR bit set (Section 6.1.5 of RFC 3168).
 +
However, in ECN implementation of ns-2, there is a attribute called SetCwrOnRetransmit which gives the flexibility
 +
to decide whether CWR should be set on retransmitted packets.
 +
 +
2. Despite the congestion window size being 1 MSS, the sender should reduce its congestion window by half when
 +
it receives a packet with ECE bit set. The sender must reset the retransmit timer on receiving the ECN-Echo packet
 +
when the congestion window is one.  The sending TCP will then be able to send a new packet only when the retransmit
 +
timer expires (Section 6.1.2 of RFC 3168).
 +
 +
In ns-2, there is a function rtt-backoff ( ) which is  invoked by the sender on receipt of packet with ECE flags
 +
set when the congestion window size is less than or equal to 1 MSS. Should this be implemented in ns-3?
 +
 
 +
3. Implementation of setter and getter methods for ECN to decide if the outgoing and incoming traffic should be
 +
ECN-capable.
 +
 +
The Linux kernel supports following three working modes of the ECN for TCP, as configured by value of
 +
/proc/sys/net/ipv4/tcp_ecn variable, through the sysctl interface:[11 - tcp_ecn in Documentation/networking
 +
/ip-sysctl.txt]
 +
 +
0 – disable ECN and neither initiate nor accept it
 +
1 – enable ECN when requested by incoming connections, and also request ECN on outgoing connection attempts
 +
2 – enable ECN when requested by incoming connections, but do not request ECN on outgoing connections.
 +
 +
The default value in Linux kernel is 2, meaning that by default ECN is enabled when requested by incoming connections,
 +
but it is not requested on outgoing connections.
 +
 +
4) Should the queue-discs be given a feature to enable or disable ECN? This is because there could be scenarios where
 +
router cannot support ECN marking.
 +
</pre>
 +
 +
=== '''Week 9 (Sept 13 - Sept 19)''' ===
 +
<pre>
 +
1) Added Test cases for ECN implementation in adaptive-red-tests, red-tests and adaptive-red-queue-disc-test-suite.
 +
  * In traffic-control/examples/adaptive-red-tests.cc, the following tests were added :
 +
    Test 3 which is similar to test 1, but with ECN enabled
 +
    Test 4 which is similar to test 2, but with ECN enabled
 +
    Test 11 which is similar to test 10, but with ECN enabled
 +
 +
  * In traffic-control/examples/red-tests.cc, the following tests were added :
 +
    Test 2 which is similar to test 1, but with ECN enabled
 +
 +
    All the above test cases are similar to the ones used in ns-2.
 +
 +
  * In test/ns3tc/adaptive-red-queue-disc-test-suite.cc, the function RunAdaptiveRedDiscTest ( ) has been modified
 +
    to include a test case for ECN.
 +
 +
2) Fixed bugs in red-queue-disc-test-suite.cc and adaptive-red-queue-disc-test-suite.cc to reduce the difference in
 +
  number of drops in byte and packet mode.
 +
 +
3) Cleaned the code and included log messages.
 +
</pre>
 +
 +
=== '''Week 10 (Sept 20 - Sept 26)''' ===
 +
<pre>
 +
1) forcedMark has been removed from Stats. forcedMark was recommended in the original RED paper but the RFC recommends
 +
  not to mark the packets when queue length exceeds MaxTh.
 +
 +
  * Made modifications in the following files to remove forcedMark
 +
    red-queue-disc.h
 +
    red-queue-disc.cc
 +
    ecn-red-queue-disc-test-suite.cc
 +
    ecn-ipv6-red-queue-disc-test-suite.cc
 +
    adaptive-red-queue-disc-test-suite.cc
 +
    adaptive-red-tests.cc
 +
    red-tests.cc
 +
 +
2)  Fixed the ecn-red-queue-disc-test-suite and ecn-ipv6-red-queue-disc-test-suite  to remove the differences in
 +
    packet drops between byte mode and packet mode.
 +
 +
3) Enabled the traces for m_ecnState, m_EcnEchoSeq, m_EcnCESeq and m_EcnCWRSeq.
 +
</pre>
 +
 +
=== '''Week 11 (Sept 27 - Oct 3)''' ===
 +
<pre>
 +
1) Prepared the final code and documentation. Sent it for review to mentors.
 +
2) Addressed the mentors' feedback and revised the code accordingly.
 +
3) Cleaned up the git repository to prepare final patches for the project
 +
</pre>
 +
 +
=== '''Week 12 (Oct 4 - Oct 10)''' ===
 +
<pre>
 +
1) Prepared two separate patches, one for each phase of the project: ecn-queue.patch and ecn-tcp.patch
 +
2) Uploaded both the patches to Rietveld. Please refer to "Final review" section below.
 +
3) Asked for final code review on ns-developers list
 +
</pre>
 +
 +
== Final Review ==
 +
The project code has been uploaded to Rietveld in two patches for final review:
 +
 +
* Phase 1 patch (i.e., ECN implementation for queue discs): https://codereview.appspot.com/306660043/
 +
* Phase 2 patch (i.e., ECN implementation for TCP): https://codereview.appspot.com/314790043/
 +
 +
Any suggestions / feedback would be much appreciated.
 +
 +
Thanks,
 +
Shravya K. S.

Latest revision as of 03:08, 11 October 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 :
  • Phase 1: ECN implementation for queue discs
  • Phase 2: ECN implementation for TCP
  • 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.

The weekly progress report for week 6 describes the TCP implementation plan.

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 (July 19 - July 25)

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 (July 26 - Aug 1)

* 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 in RED QueueDisc 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 (Aug 2 - Aug 8)

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 (Aug 9 - Aug 15)

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 is 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 (Aug 16 - Aug 22)

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.

Week 6 (Aug 23 - Aug 29)

* Patch posted for mid-term review here: https://codereview.appspot.com/304520043/

ECN support for TCP

* Following ECN states have been declared in src/internet/model/tcp-socket.h

 typedef enum {
    NO_ECN = 0,       //!< ECN disabled traffic 
    ECN_IDLE,         //!< ECN is enabled  but currently there is no action pertaining to ECE or CWR to be taken 
    ECN_CE_RCVD,      //!< This state indicates that the receiver has received a packet with CE bit set in IP header 
    ECN_ECE_SENT,     //!< This state indicates that the receiver has sent an ACK with ECE bit set in TCP header
    ECN_ECE_RCVD,     //!< This state indicates that the sender has received an ACK with ECE bit set in TCP header 
    ECN_CWR_SENT      //!< This state indicates that the sender has reduced the congestion window, and sent a packet
                         with CWR bit set in TCP header
  } EcnStates_t;

* Following ECN parameters were added in src/internet/model/tcp-socket-base.h

 // ECN parameters
 bool                     m_ecn;             //!< Socket ECN capability
 TracedValue<EcnStates_t> m_ecnState;        //!< Current ECN State, represented as combination of EcnState values
 TracedValue<SequenceNumber32> m_ecnEchoSeq; //< Sequence number of the last received   ECN Echo

* In src/internet/model/tcp-header.cc, a minor change has been made to TcpHeader::Deserialize method to account for 
the ECN bits in TCP header.

Initially it was:
m_flags = field & 0x3F;

Now it is:
m_flags = field & 0xFF;

* ECN negotiation has been implemented, and following are the steps for same:

1. Sender sends SYN + CWR + ECE
Methods modified: DoConnect ( ), DoRetransmit ( )
Changes required while sending SYN packet :
if (m_ecn)
  { 
    SendEmptyPacket (TcpHeader::SYN | TcpHeader::ECE | TcpHeader::CWR);
  }
else
  {
    SendEmptyPacket (TcpHeader::SYN);
  }
m_ecnState = NO_ECN;

2. Receiver sends SYN + ACK + ECE
Methods modified: ProcessSynSent( ) , ProcessSynRcvd ( ), CompleteFork ( )
Changes required while sending SYN + ACK packet :
if (m_ecn && (tcpHeader.GetFlags () & (TcpHeader::CWR | TcpHeader::ECE)) == (TcpHeader::CWR | TcpHeader::ECE))
  {
    SendEmptyPacket (TcpHeader::SYN | TcpHeader::ACK |TcpHeader::ECE);
    m_ecnState = ECN_IDLE;
  }
else
  {
    SendEmptyPacket (TcpHeader::SYN | TcpHeader::ACK);
    m_ecnState = NO_ECN;
  }

3. Sender sends ACK
Methods modified: ProcessSynSent ( )
Changes required while sending an ACK packet :
if (m_ecn &&  (tcpHeader.GetFlags () & (TcpHeader::CWR | TcpHeader::ECE)) == (TcpHeader::ECE))
  {
    m_ecnState = ECN_IDLE;
  }
else
  {
    m_ecnState = NO_ECN;
  }

Once the ECN-negotiation is successful, sender sends data packets with ECT bits set.

Note: As mentioned in Section 6.1.1 of RFC 3168, ECT bits should not be set during ECN negotiation. 
ECN negotiation implemented in ns-3 follows this guideline.

* To inform the IP-layer to send packets with ECT bit set, packet tag has been added. 

For IPv4 :
ipTosTag.SetTos (GetTos( ) | 0x02);
p->AddPacketTag (ipTosTag);

For IPv6 :
ipTclassTag.SetTclass (GetIpv6Tclass () | 0x2);
p->AddPacketTag (ipTclassTag);

Week 7 (Aug 30 - Sept 5)

* We received following suggestions on our mid-term patch:

1. Use m_header in Mark( ) implementation in Ipv{4,6}QueueDiscItem instead of removing, modifying and re-adding 
   the IP header.

2. Remove IsEcnCapable ( ) as the implementation is simple  and can be directly implemented as follows:
  (m_header.GetEcn ( ) == Ipv4Header::ECN_ECT1 || m_header.GetEcn () == Ipv4Header::ECN_ECT0)

3. Remove IsMarked ( ) function. The IsMarked( ) function was implemented because of the use-case to check if the 
   queue was trying to mark an already marked packet.  However, whether the item is already marked or not causes any 
   change in queue disc behavior.

* The suggested modifications were incorporated, and a new patch was uploaded to Rietveld.
See Patch 2 for the modified code: https://codereview.appspot.com/304520043/

ECN Support for TCP continued ...

* Incorporated the following functionalities in tcp-socket-base.cc:

1. TCP Receiver sets ECE bit in the ACK sent to sender in following cases :
   A. On receipt of a packet with CE bit set. The IPv4 header in tcp-socket-base is available in the function
      TcpSocketBase::ForwardUp and the IPv6 header is available in the function TcpSocketBase::ForwardUp6
   B. If the receiver sent the last ACK with ECE bit set, and the sender has not yet responded to the ECE notification.  
2.  TCP Sender reacts to the congestion notification indicated by ECE bit set in the ACK from the receiver by doing 
    the following :
   A. Halves the congestion window
   B. Sets the ssthreshold to cwnd/2 
   C. Sets CWR flags in the subsequent data packets sent to receiver 

 
* ECN State Transitions:
1. Initially both sender and receiver have their m_ecnState set as NO_ECN
2. Once, the ECN negotiation is successful, their states are set to ECN_IDLE 
3. On receipt of a packet with CE bits set in IP header, receiver changes it’s state to ECN_CE_RCVD
4. When the receiver sends an ACK with ECE bit set, it’s state is set as ECN_ECE_SENT
5. When the sender receives an ACK with ECE bit set from receiver, it’s state is set as ECN_ECE_RCVD
6. When the sender sends the packet with CWR bit set, it’s state is set as ECN_CWR_SENT
7. When the receiver receives the packet with CWR bit set, it’s state is set as ECN_IDLE

Week 8 (Sept 6 - Sept 12)

* Depending on the suggestions provided in RFC 3168, following features have been ensured while implementing 
  ECN support for TCP:

1. Pure ACK packets should not have ECT bit set (Section 6.1.4).
2. Retransmitted packets should not have ECT bit set in order to prevent DoS attack (Section 6.1.5). 
3. Sender should should reduce the congestion window only once in each window (Section 6.1.2).
4. Receiver should ignore the CE bits set in the packet which arrived out of window (Section  6.1.5). 
5. Sender should ignore the ECE bits set in the packet which arrived out of window (Section 6.1.2).

* Following issues are to be addressed, and any suggestions in these directions would be much appreciated:

1. Retransmitted packets with CWR bit set should not have CWR bit set (Section 6.1.5 of RFC 3168).
However, in ECN implementation of ns-2, there is a attribute called SetCwrOnRetransmit which gives the flexibility 
to decide whether CWR should be set on retransmitted packets.

2. Despite the congestion window size being 1 MSS, the sender should reduce its congestion window by half when 
it receives a packet with ECE bit set. The sender must reset the retransmit timer on receiving the ECN-Echo packet 
when the congestion window is one.  The sending TCP will then be able to send a new packet only when the retransmit 
timer expires (Section 6.1.2 of RFC 3168).
 
In ns-2, there is a function rtt-backoff ( ) which is  invoked by the sender on receipt of packet with ECE flags 
set when the congestion window size is less than or equal to 1 MSS. Should this be implemented in ns-3?
  
3. Implementation of setter and getter methods for ECN to decide if the outgoing and incoming traffic should be 
ECN-capable.

The Linux kernel supports following three working modes of the ECN for TCP, as configured by value of 
/proc/sys/net/ipv4/tcp_ecn variable, through the sysctl interface:[11 - tcp_ecn in Documentation/networking
/ip-sysctl.txt]

0 – disable ECN and neither initiate nor accept it
1 – enable ECN when requested by incoming connections, and also request ECN on outgoing connection attempts
2 – enable ECN when requested by incoming connections, but do not request ECN on outgoing connections. 

The default value in Linux kernel is 2, meaning that by default ECN is enabled when requested by incoming connections, 
but it is not requested on outgoing connections. 

4) Should the queue-discs be given a feature to enable or disable ECN? This is because there could be scenarios where 
router cannot support ECN marking.

Week 9 (Sept 13 - Sept 19)

1) Added Test cases for ECN implementation in adaptive-red-tests, red-tests and adaptive-red-queue-disc-test-suite.
   * In traffic-control/examples/adaptive-red-tests.cc, the following tests were added :
     Test 3 which is similar to test 1, but with ECN enabled
     Test 4 which is similar to test 2, but with ECN enabled
     Test 11 which is similar to test 10, but with ECN enabled

   * In traffic-control/examples/red-tests.cc, the following tests were added :
     Test 2 which is similar to test 1, but with ECN enabled

    All the above test cases are similar to the ones used in ns-2.

   * In test/ns3tc/adaptive-red-queue-disc-test-suite.cc, the function RunAdaptiveRedDiscTest ( ) has been modified 
     to include a test case for ECN.

2) Fixed bugs in red-queue-disc-test-suite.cc and adaptive-red-queue-disc-test-suite.cc to reduce the difference in 
   number of drops in byte and packet mode.

3) Cleaned the code and included log messages.

Week 10 (Sept 20 - Sept 26)

1) forcedMark has been removed from Stats. forcedMark was recommended in the original RED paper but the RFC recommends
   not to mark the packets when queue length exceeds MaxTh.

   * Made modifications in the following files to remove forcedMark 
     red-queue-disc.h
     red-queue-disc.cc
     ecn-red-queue-disc-test-suite.cc
     ecn-ipv6-red-queue-disc-test-suite.cc
     adaptive-red-queue-disc-test-suite.cc
     adaptive-red-tests.cc
     red-tests.cc

2)  Fixed the ecn-red-queue-disc-test-suite and ecn-ipv6-red-queue-disc-test-suite  to remove the differences in 
    packet drops between byte mode and packet mode.

3) Enabled the traces for m_ecnState, m_EcnEchoSeq, m_EcnCESeq and m_EcnCWRSeq.

Week 11 (Sept 27 - Oct 3)

1) Prepared the final code and documentation. Sent it for review to mentors.
2) Addressed the mentors' feedback and revised the code accordingly.
3) Cleaned up the git repository to prepare final patches for the project

Week 12 (Oct 4 - Oct 10)

1) Prepared two separate patches, one for each phase of the project: ecn-queue.patch and ecn-tcp.patch
2) Uploaded both the patches to Rietveld. Please refer to "Final review" section below.
3) Asked for final code review on ns-developers list

Final Review

The project code has been uploaded to Rietveld in two patches for final review:

Any suggestions / feedback would be much appreciated.

Thanks, Shravya K. S.