Week 1 Synopsis - siddeshlc8/PIE-in-ns3 GitHub Wiki

PIE (Proportional Integral controller Enhanced)

Introduction

PIE (Proportional Integral controller Enhanced) that can effectively control the average queuing latency to a target value. Congestion detection, however, is based on the queuing latency instead of the queue length.

Design Goals of PIE:

queuing latency, instead of queue length, is controlled.
PIE aims to attain high link utilization.
the scheme should be simple to implement and easily scalable in both hardware and software.
the scheme should ensure system stability for various network topologies and scale well across an arbitrary number of streams.

The Basic PIE Scheme

PIE is comprised of three simple basic components:

random dropping at enqueuing,
periodic drop probability updates and

latency calculation.

      Random Drop
           /               --------------
   -------/ -------------->  | | | | |   -------------->
         /|\                 | | | | |
          |                 --------------
          |                Queue Buffer    \
          |                         |       \
          |                         |Queue   \
          |                         |Length   \
          |                         |          \
          |                        \|/         \/
          |              -----------------     -------------------
          |              | Drop           |    |                  |
          ---------<-----| Probability    |<---| Latency          |
                         | Calculation    |    | Calculation      |
                         -----------------     -------------------
                           Figure 1: The PIE Structure

Random Dropping

PIE randomly drops a packet upon its arrival to a queue according to a drop probability, PIE->drop_prob_, that is obtained from the drop-probability-calculation component. The random drop is triggered by a packet’s arrival before enqueuing into a queue.

Drop Probability Calculation

The PIE algorithm periodically updates the drop probability based on the latency samples -- not only the current latency sample but also whether the latency is trending up or down.

PIE adopts the PI controller for controlling latency. The algorithm also auto-adjusts the control parameters based on how heavy the congestion is, which is reflected in the current drop probability.

When a congestion period ends, we might be left with a high drop probability with light packet arrivals. Hence, the PIE algorithm includes a mechanism by which the drop probability decays exponentially (rather than linearly) when the system is not congested. This would help the drop probability converge to 0 more quickly, while the PI controller ensures that it would eventually reach zero. The decay parameter of 2% gives us a time constant around 50 * T_UPDATE.

calculate drop probability PIE->drop_prob_, and autotune it as follows:

 every T_UPDATE interval:

 p = alpha * (current_qdelay - QDELAY_REF) + beta * (current_qdelay - PIE->qdelay_old_);
 if (PIE->drop_prob_ < 0.000001) {
     p /= 2048;
 } else if (PIE->drop_prob_ < 0.00001) {
     p /= 512;
 } else if (PIE->drop_prob_ < 0.0001) {
     p /= 128;
 } else if (PIE->drop_prob_ < 0.001) {
     p /= 32;
 } else if (PIE->drop_prob_ < 0.01) {
     p /= 8;
 } else if (PIE->drop_prob_ < 0.1) {
     p /= 2;
 } else {
     p = p;
 }
PIE->drop_prob_ += p;

decay the drop probability exponentially:

 if (current_qdelay == 0 && PIE->qdelay_old_ == 0) {
     PIE->drop_prob_ = PIE->drop_prob_ * 0.98;
  }

The update interval, T_UPDATE, is defaulted to be 15 milliseconds. It MAY be reduced on high-speed links in order to provide a smoother response. The target latency value, QDELAY_REF, SHOULD be set to 15 milliseconds.

Latency Calculation

The PIE algorithm uses latency to calculate drop probability in one of two ways:

It estimates the current queuing latency using Little’s law

   current_qdelay = current_queue_.byte_length()/dequeue_rate;

It may use other techniques for calculating queuing latency, e.g., time-stamp the packets at enqueue, and use the timestamps to calculate latency during dequeue.

Implementation of PIE in NS-3

Note: This section only concerned with the queue delay/latency calculation. For more implementation details click here

The NS-3 implementation uses the Little's Law to calculate the current queue delay or latency. Click Here to see the code
```
         current_qdelay = current_qlength/dequeue_rate
```
How dequeue_rate calculated?

dequeue_rate calculated using EWMA(Exponential Moving Weighted Average). Click Here to see the code

        dequeue_rate = old_dequeue_rate*(1-w) + current_dequeue_rate
        w = 0.5 in RFC as well as in NS-3

How current_dequeue_rate obtained?
In NS-3, PIE only measures current_dequeue_rate when there is sufficient data in the buffer, i.e. when the queue length is over a certain threshold (DQ_THRESHOLD)
When the data dequeued ( dqCount) from the queue in PIE is greater than the DQ_THRESHOLD value PIE updates the current_dequeue_rate. Click Here to see the code
```
       current_dequeue_rate = dqCount / t
       t = Time taken to dequeue dqCount amount of data
```

Implementation of PIE in FreeBSD

Note: This section only concerned with the queue delay/latency calculation. For more implementation details click here

FreeBSD uses both ways to calculate latency/current queue delay

   1. Little’s law 
   2. Timestamps to calculate latency during dequeue.

The FreeBSD's implementation of Little's Law is same as ns-3. Click Here to see code

In FreeBSD dequeue_rate is not calculated instead avg_dequeue_time calculated using EWMA(Exponential Moving Weighted Average). Click Here to see the code

        avg_dequeue_time = avg_dequeue_time*(1-w) + current_dequeue_time

        weight(w) = PIE_DQ_THRESHOLD/2^6, but in freebsd w is scaled by 2^8. Thus, scaled weight(w) = DQ_THRESHOLD /2^8

What is avg_dequeue_time?
The avg_dequeue_time is calculated when data dequeued (dq_Count) is greater than or equal to DQ_THRESHOLD and avg_dequeue_time is the time taken to dequeue dq_Count amount of data from queue and its unit is time per bit.
Now, How the curren_queue_delay calculated?

curren_queue_delay calculated as Click Here to see the code

       curren_queue_delay = current_queue_length * avg_dequeue_time

Difference Between NS-3 & FreeBSD PIE Implementation

_Note: This section only concerned with the queue delay/latency calculation.

NS-3 uses only Little's law. FreeBSD has two options use of Little's Law and Timestamp
In NS-3 avg_dequeue_rate and in FreeBSD avg_dequeue_time used to calculate the current_queue-delay when Little's law is used.

Future Plan

To implement the timestamp method of calculating current_queue-delay in NS-3