-
Notifications
You must be signed in to change notification settings - Fork 4
ECN_PIE Pseudo code
Iamrupesh edited this page Nov 9, 2018
·
2 revisions
//Called on each packet arrival
enque(Packet packet) {
if (queue_.byte_length() + packet.size() > TAIL_DROP) {
drop(packet);
PIE->accu_prob_ = 0;
}
else if (PIE->active_ == TRUE && drop_early() == DROP && PIE->burst_allowance_ == 0) {
if (PIE->drop_prob_ < MAX_ECNTH && packet.ecn() == TRUE)
mark(packet);
else
drop(packet);
PIE->accu_prob_ = 0;
}
else {
queue_.enque(packet);
}
//If the queue is over a certain threshold, turn on PIE
if (PIE->active_ == INACTIVE && queue_.byte_length() >= TAIL_DROP/3) {
PIE->active_ = ACTIVE;
PIE->qdelay_old_ = 0;
PIE->drop_prob_ = 0;
PIE->in_measurement_ = TRUE;
PIE->dq_count_ = 0;
PIE->avg_dq_time_ = 0;
PIE->last_timestamp_ = now;
PIE->burst_allowance_ = MAX_BURST;
PIE->accu_prob_ = 0;
PIE->measurement_start_ = now;
}
//If the queue has been idle for a while, turn off PIE
//Reset counters when accessing the queue after some idle
//period if PIE was active before
if ( PIE->drop_prob_ == 0 && PIE->qdelay_old_ == 0 && current_qdelay == 0) {
PIE->active_ = INACTIVE;
PIE->in_measurement_ = FALSE;
}
}
drop_early() {
//PIE is active but the queue is not congested: return ENQUE
if ( (PIE->qdelay_old_ < QDELAY_REF/2 && PIE->drop_prob_ < 0.2) || (queue_.byte_length() <= 2 * MEAN_PKTSIZE) ) {
return ENQUE;
}
if (PIE->drop_prob_ == 0) {
PIE->accu_prob_ = 0;
}
//For practical reasons, drop probability can be further scaled
//according to packet size, but one needs to set a bound to
//avoid unnecessary bias
//Random drop
PIE->accu_prob_ += PIE->drop_prob_;
if (PIE->accu_prob_ < 0.85)
return ENQUE;
if (PIE->accu_prob_ >= 8.5)
return DROP;
double u = random();
if (u < PIE->drop_prob_) {
PIE->accu_prob_ = 0;
return DROP;
} else {
return ENQUE;
}
}
//Update periodically, T_UPDATE = 15 milliseconds
calculate_drop_prob() {
if ( (now - PIE->last_timestamp_) >= T_UPDATE && PIE->active_ == ACTIVE) {
//Can be implemented using integer multiply
//DQ_THRESHOLD is power of 2 value
current_qdelay = queue_.byte_length() *
PIE->avg_dq_time_/DQ_THRESHOLD;
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;
}
if (PIE->drop_prob_ >= 0.1 && p > 0.02) {
p = 0.02;
}
PIE->drop_prob_ += p;
//Exponentially decay drop prob when congestion goes away
if (current_qdelay < QDELAY_REF/2 && PIE->qdelay_old_ < QDELAY_REF/2) {
PIE->drop_prob_ *= 0.98; //1 - 1/64 is
//sufficient
}
//Bound drop probability
if (PIE->drop_prob_ < 0)
PIE->drop_prob_ = 0
if (PIE->drop_prob_ > 1)
PIE->drop_prob_ = 1
PIE->qdelay_old_ = current_qdelay;
PIE->last_timestamp_ = now;
PIE->burst_allowance_ = max(0,PIE->burst_allowance_ - T_UPDATE);
}
}
//Called on each packet departure
deque(Packet packet) {
//Dequeue rate estimation
if (PIE->in_measurement_ == TRUE) {
PIE->dq_count_ = packet.size() + PIE->dq_count_;
//Start a new measurement cycle if we have enough packets
if ( PIE->dq_count_ >= DQ_THRESHOLD) {
dq_time = now - PIE->measurement_start_;
if (PIE->avg_dq_time_ == 0) {
PIE->avg_dq_time_ = dq_time;
} else {
weight = DQ_THRESHOLD/2^16
PIE->avg_dq_time_ = dq_time * weight + PIE->avg_dq_time_ * (1 - weight);
}
PIE->in_measurement_ = FALSE;
}
}
//Start a measurement if we have enough data in the queue
if (queue_.byte_length() >= DQ_THRESHOLD && PIE->in_measurement_ == FALSE) {
PIE->in_measurement_ = TRUE;
PIE->measurement_start_ = now;
PIE->dq_count_ = 0;
}
}
Computer Networks Project
Under the guidance of Mohit P. Tahiliani