Difference between revisions of "GSOC2019DCN"

From Nsnam
Jump to: navigation, search
(Weekly Progress (Continuous update))
(Weekly Plan (Continuous Update))
Line 47: Line 47:
 
* Implement core functions of Multi-Level Feedback Queue (MLFQ) as a new queueing discipline for traffic control layer src/traffic-control/model/mlfq-queue-disc.{h,cc}.
 
* Implement core functions of Multi-Level Feedback Queue (MLFQ) as a new queueing discipline for traffic control layer src/traffic-control/model/mlfq-queue-disc.{h,cc}.
 
* Introduction of MLFQ functionality:
 
* Introduction of MLFQ functionality:
** MLFQ is installed at network end hosts to mimic Shortest-Job-First in order to minimize the Flow Completion Time of the Network.
+
** MLFQ is installed at network end hosts to mimic Shortest-Job-First (the flows with smaller flow size in bytes will be prioritized over those with larger flow size) in order to minimize the Flow Completion Time of the Network. The main configurations include the number of priorities K (max 16), K-1 thresholds (in bytes) separating different priorities, 
 
** MLFQ end host would maintain a hash table that would map the flow tuple (source IP, destination IP, source port, destination port, protocol) to flow priority, and another table to map it to the transmitted bytes.
 
** MLFQ end host would maintain a hash table that would map the flow tuple (source IP, destination IP, source port, destination port, protocol) to flow priority, and another table to map it to the transmitted bytes.
 
** When the packet is forwarded from the IP Layer to MLFQ (Traffic Control Layer), it will check the flow table and increment the transmitted bytes (if the flow does not exist, it will initialize the flow element with 0 bytes and top priority 0).  
 
** When the packet is forwarded from the IP Layer to MLFQ (Traffic Control Layer), it will check the flow table and increment the transmitted bytes (if the flow does not exist, it will initialize the flow element with 0 bytes and top priority 0).  
** If the historically transmitted bytes of the flow exceed the configured threshold for the next lower priority, the current priority would be changed to the lower priority (e.g., priority 0 to priority 1). Such information would be tagged on the packet (e.g., ToS field/DSCP field).
+
** If the historically transmitted bytes of the flow exceed the configured threshold for the next lower priority, the current priority would be changed to the lower priority (e.g., priority 0 to priority 1). Such information would be tagged on the packet (e.g., ToS field/DSCP field). The packet will be then forwared to one of the K FIFO queues based on the priority for transmission.
 
** Network switches will incorporate K priority queue (e.g., existing PrioQueueDisc) and upon receiving a packet, enqueue the packet based on the priority tagged on the packet.
 
** Network switches will incorporate K priority queue (e.g., existing PrioQueueDisc) and upon receiving a packet, enqueue the packet based on the priority tagged on the packet.
 
* Discussions
 
* Discussions
** How to tag priority information for the packet? When there is an incoming packet passing from the IP layer, MLFQ will check the flow table and decide on the priority of the packet (2~8, depending on the MLFQ configuration). Such priority information will be encoded at the packet header, typically the TypeOfService field. Shall we use the PacketTag (with an internal field of uint8_t) or ByteTag or others to tag such information?
+
** Since MLFQ will perform scheduling over the egress direction (during the transmission of the packet, IP=>TrafficControl=>NetDevice) and PrioQueue will perform scheduling over the ingress direction (NetDevice=>TrafficControl=>IP). I would like to make sure if both directions of calling are supported for the latest TrafficControl Layer?
** Concerns of packet fragmentation: will the tagging information be lost when passing through the network stack?
+
** How to tag priority information for the packet?
** MLFQ is for the network edges, when we use MLFQ, we need to use the existing PrioQueueDisc under the traffic control module to classify the packet to the corresponding FIFO queue (2~16 queues, depending on the PrioQueueDisc configuration) based on the priority information. We need to consider this when implementing the MLFQ and we probably need to modify PrioQueueDisc classifier as well.
+
*** One way I could think of is to use the custom PacketTag subclass from Tag and insert that PacketTag with the priority information (max 16, so uint8_t) to the packet. Meanwhile, as far as I know, such tag would not be lost when passing the tagged packet from Traffic Control Layer to NetDevice (which might conduct fragmentation based on MTU).
<pre>
+
*** Ideally, I feel it would be better if we directly tag the priority info to the packet header bytes (e.g., ToS/DSCP field)? Would be great if there are suggestions?
 +
*** We would also require some changes of the existing PrioQueue (src/traffic-control/model/prio-queue-disc.{cc,h}) on the DoEnqueue method, which needs to optionally extract that priority info and classify the packet to the corresponding FIFO queue.  
 +
<pre>  
 
</pre>
 
</pre>
  

Revision as of 09:30, 26 May 2019

GSOC2019DCN

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

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

Return to GSoC 2019 Projects page.

Project Overview

  • Project name: Framework of Studying Flow Completion Time Minimization for Data Center Networks
  • Abstract: This project aims to make NS-3 more friendly to researchers working on the contemporary research topic in Data Center Networks (DCN) to use NS-3 as an effective simulation tool to evaluate their ideas. The theme of the project is to augment NS-3 with further support of Data Center Network (DCN) related simulation and research, with a special focus in the flow-based performance optimization, e.g., implementing useful modules in NS-3 ecosystem including Multi Level Feedback Queue scheduling, spine-leaf topology helper, flow statistics analysis helper and so forth.
  • About Me: I will soon join the University of Pennsylvania as a first-year Ph.D. student focusing on Computer Systems and Networking. I obtained my master degree in Wireless Systems at KTH Royal Institute of Technology, Sweden and Bachelor of Engineering in Automatic Control at Zhejiang University, China.
  • Code: To be included.

Technical Approach

The big picture of the project is to augment DCN support for NS-3. This project specifically looks at supporting flow-based performance optimization in NS-3 which involves multiple aspects including packet scheduling, packet tagging, topology helper, performance evaluation helper, load balancing and so forth. The Multi-Level Feedback Queue scheduling disciplines and Shortest Job First are used to support minimizing Flow Completion Time (FCT) with or without the information of the flow size. The spine-leaf topology is often used in the DCN simulation to evaluate the DCN proposal and metrics such as the average FCT, 99th percentile are the indicators to analyze the potential DCN proposal that involves novel scheduling, congestion control, routing, or load balancing approaches for DCN. The implementation will align with the classical and state-of-the-art DCN research via incorporating these necessary components for DCN research.

Milestones and Deliverables

This project aims to make NS-3 more friendly to researchers working on the contemporary research topic in DCN to use NS-3 as an effective simulation tool to evaluate their ideas so we would adjust the deliverables to best serve the purposes. The entire GSoC period is divided into 3 phases. For now, the deliverables at the end of each phase are as mentioned below:

Phase 1

  • Implementation of Multi-Level Feedback Queue scheduling.
  • Implementation of Shorted Job First based scheduling.
  • Implementation of the tagging of the metadata of the (remaining) flow size in the packet with corresponding application or helpers.

Phase 2

  • Implementation of the spine-leaf DCN topology helper and NetAnim support.
  • Implementation of flow synthesizer and flow statistics analysis helper.
  • Provide examples of using representative traffic distribution in DCN for DCN simulation.

Phase 3

  • Provide example program for data center networking simulation in NS-3 reproducing the classical work in the domain, e.g., pFabric, PIAS.
  • Buffer time for adding other prioritized targets for supporting DCN research in NS-3, e.g., the load balancing algorithms (e.g., other than ECMP), congestion control, TCP incast simulation in DCN.

Weekly Plan (Continuous Update)

Below is the weekly plan including the core technical details.

Week1 May 27 - June 2

  • Implement core functions of Multi-Level Feedback Queue (MLFQ) as a new queueing discipline for traffic control layer src/traffic-control/model/mlfq-queue-disc.{h,cc}.
  • Introduction of MLFQ functionality:
    • MLFQ is installed at network end hosts to mimic Shortest-Job-First (the flows with smaller flow size in bytes will be prioritized over those with larger flow size) in order to minimize the Flow Completion Time of the Network. The main configurations include the number of priorities K (max 16), K-1 thresholds (in bytes) separating different priorities,
    • MLFQ end host would maintain a hash table that would map the flow tuple (source IP, destination IP, source port, destination port, protocol) to flow priority, and another table to map it to the transmitted bytes.
    • When the packet is forwarded from the IP Layer to MLFQ (Traffic Control Layer), it will check the flow table and increment the transmitted bytes (if the flow does not exist, it will initialize the flow element with 0 bytes and top priority 0).
    • If the historically transmitted bytes of the flow exceed the configured threshold for the next lower priority, the current priority would be changed to the lower priority (e.g., priority 0 to priority 1). Such information would be tagged on the packet (e.g., ToS field/DSCP field). The packet will be then forwared to one of the K FIFO queues based on the priority for transmission.
    • Network switches will incorporate K priority queue (e.g., existing PrioQueueDisc) and upon receiving a packet, enqueue the packet based on the priority tagged on the packet.
  • Discussions
    • Since MLFQ will perform scheduling over the egress direction (during the transmission of the packet, IP=>TrafficControl=>NetDevice) and PrioQueue will perform scheduling over the ingress direction (NetDevice=>TrafficControl=>IP). I would like to make sure if both directions of calling are supported for the latest TrafficControl Layer?
    • How to tag priority information for the packet?
      • One way I could think of is to use the custom PacketTag subclass from Tag and insert that PacketTag with the priority information (max 16, so uint8_t) to the packet. Meanwhile, as far as I know, such tag would not be lost when passing the tagged packet from Traffic Control Layer to NetDevice (which might conduct fragmentation based on MTU).
      • Ideally, I feel it would be better if we directly tag the priority info to the packet header bytes (e.g., ToS/DSCP field)? Would be great if there are suggestions?
      • We would also require some changes of the existing PrioQueue (src/traffic-control/model/prio-queue-disc.{cc,h}) on the DoEnqueue method, which needs to optionally extract that priority info and classify the packet to the corresponding FIFO queue.
 

Weekly Progress (Continuous update)

Below is the weekly progress including the core technical details.

Community Bonding Period

  • Prepared wiki page for the project and the introduction text to the NS-3 developer mailing list.
  • Met with mentors and discussed the details of the proposal.
    • Consider the trace, variables to be exposed to the users (e.g., TCP window size, queueing delay...)
    • Check Fqcodel for similar hashing implementation.
    • Complete the full cycle of the NS-3 feature before moving to the next (implementation, text, example, documentation)
  • Got familiar with the previous DCN project DCTCP (GSOC2017).
  • Forked the ns3-dev repo (sync with commit eda73a35) over GitLab and created a sample branch for review.

Week1 May 27 - June 2