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);

  • 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