Skip to content

Home

Jump to bottom
Sumukha Pk edited this page Oct 29, 2018 · 19 revisions

Welcome to the FQ-PIE-ns-3 wiki!

  • 29-9-18: Added ns3 dev to the repo

  • 11-10-18: Added information about FQ-PIE

About the protocol PIE:

  1. FQ-PIE is FlowQueue combined with Proportional Integral controller Enhanced (PIE) algorithm to address the problem of bufferbloat in the network.

  2. Bufferbloat is a phenomenon in which excess buffers in the network cause high latency and latency variation.

  3. PIE,Proportional Integrated controller Enhanced can effectively control the average queuing delay to a target value.

  4. PIE, aims to keep the benefits of RED(Random Early Detection) and also include easy implementation and scalability to high speeds(Both are the reasons why RED failed).

  5. PIE drops random packets at the onset of congestion (like RED, for congestion control) but congestion detection is based on queuing latency rather than the queuing length as with RED. PIE uses a derivative of queuing latency to help determine congestion levels and an appropriate response. The control parameters of PIE are chosen by control theory but can also be made self tuning based on circumstances.

  6. The structure of PIE

     
     Random Drop
             /               --------------
     -------/  -------------->    | | | | | -------------->
           /|\                   | | | | |
             |               --------------
             |             Queue Buffer   \
             |                     |       \
             |                     |Queue   \
             |                     |Length   \
             |                     |          \
             |                    \|/         \/
             |          -----------------    -------------------
             |          |     Drop      |    |                 |
             -----<-----|  Probability  |<---|   Latency       |
                        |  Calculation  |    |  Calculation    |
                        -----------------    -------------------

    When a packet arrives, a random decision is made regarding whether to drop thepacket. The drop probability is updated periodically based on how far the current latency is away from the target value and whether thequeuing latency is currently trending up or down. The queuing latency can be obtained using direct measurements or using estimations calculated from the queue length and the dequeue rate.

  7. Random dropping: Dropping of an incoming packet is decided based upon a certain drop probability which is obtained from the drop-probability-calculation-component of PIE. The random drop is bypassed if the older queue delay sample is less than half the target latency value when the drop probability is <0.2 or queue has less than a couple of packets.

    In conclusion,on packet arrival,

    if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2)
    || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) )
        return ENQUE;
else
  randomly drop the packet with a probability of
  PIE->drop_prob_.

  8. Drop probability calculation: The drop probability is periodically updated based on the latency samples collected over a period of time. But when the congestion period ends, we might end up with high drop probabilty values, so PIE algorithm has a mechanism by which the drop probability decays exonentially when congestion doesn't exist. The update interval (T_UPDATE) of the drop-probability is defaulted to 15ms(MAY be reduced in high speed links for smoother response).

    The control parameters alpha and beta(in Hz) are designed using feedback loop analysis. If T_UPDATE is cut in half, alpha must also be cut in half and beta must be increased by 0.25*alpha.

  9. Latency calculation:

    • Little's law method: current_qdelay = queue_.byte_length()/dequeue_rate;

    • The packets can be time-stamped at enqueue which will be used to calculate latency later.

  10. Burst tolerance: PIE does not penalize short term packet bursts. Its calculated as follows:

      if PIE->burst_allowance_ > 0
    enqueue packet;
  else
    drop_packet(drop_probability);

  if (PIE->drop_prob_ == 0 and current_qdelay < QDELAY_REF/2 and
      PIE->qdelay_old_ < QDELAY_REF/2)
          PIE->burst_allowance_ = MAX_BURST;
  
  PIE->burst_allowance_ = max(0,PIE->burst_allowance_ - T_UPDATE);

About FQ-PIE

  1. FQ-PIE is the combination of FQ-CoDel's FlowQueue logic with PIE queue management on every dynamically created sub-queue.

  2. Goal - Control queuing delays while sharing bottleneck capacity relatively evenly among competing flows.

  3. We set each instance of PIE to use timestamps (ts) rather than departure rate estimation (dre) in the context of FQ-PIE.

FQ-PIE parameters/options

  1. FQ-PIE Parameters

    a. target: The acceptable persistent queue delay. Drop probability increases as queue delay increases higher than target.

    b. tupdate: The frequency of drop probability recalculation.

    c. alpha and beta are drop probability weights.

    d. max_burst: The maximum period of time that PIE does not drop/mark packets.

    e. max_ecnth: When ECN is enabled, PIE drops packets instead of marking them when drop probability becomes higher than ECN probability threshold max_ecnth.

    f. quantum: number of bytes a queue can be served before being moved to the tail of old queues list.

    g. limit: hard size limit of all queues managed by an instance of the fq_pie scheduler.

    h. flows: number of flow queues that fq_pie creates and manages.

  2. FQ-PIE Options

    a. [no] ecn: enable (ecn) or disable (noecn) ECN marking for ECN-enabled TCP flows.

    b. [no] capdrop: enable (capdrop) or disable (nocapdrop) cap drop adjustment.

    c. [no] derand: enable or disable drop probability de-randomisation. De-randomisation eliminates the problem of dropping packets too close or too far.

    d. onoff: enable turning FQ-PIE on and off depending on queue load. PIE turns on when over 1/3 of queue becomes full.

    e. [dre/ts]: calculate queue delay using departure rate estimation (dre) or timestamps (ts).

About FQ

  1. The intention of FQ-CoDel's scheduler is to give each flow its own queue, hence the term 'flow queuing'. Rather than a perfect realization of this, a hashing based scheme is used, where flows are hashed into a number of buckets, each of which has its own queue.

  2. The number of buckets is configurable and presently defaults to 1024 in the Linux implementation.

  3. By default, the flow hashing is performed on the 5-tuple of source and destination IP addresses, source and destination port numbers, and protocol number.

  4. FQ-CoDel's DRR scheduler is byte-based, employing a DRR mechanism between queues. This works by keeping a track of the current number of "byte-credits" of each queue. This number is initialized to the configurable quantum; each time a queue gets dequeue opportunity, it gets to dequeue packets, thus decreasing the number of credits by the packet size for each packet. This continues until the value of the byte credits counter becomes zero or less, at which point the counter is increased by one quantum, and the dequeue opportunity ends.

  • 12-10-18(onwards): Read up the PIE ns3 code and understand how to integrate FQ based on FQ-CoDel

  • 20-10-18: Added some points about FQ-CoDel

  • 24-10-18: Studied ns3 code of pie-example, pie-queue-disc, codel, fq-codel. Obtained a basic idea of how exactly the codes work and how exactly our part of the port must be executed

Clone this wiki locally