` time_t` is an integer time value in units convenient for the system. Resolution to at least a millisecond is required, and better resolution is useful up to the minimum possible packet time on the output link; 64- or 32-bit widths are acceptable but with 32 bits the resolution should be no finer than 2

` packet_t*` is a pointer to a packet descriptor. We assume it has a

` queue_t` is a base class for queue objects (the parent class for

` flag_t` is a Boolean.

; time_t first_above_time | Time when we'll declare we're above target (0 if below) |

; time_t drop_next | Time to drop next packet |

; uint32_t count | Packets dropped since going into drop state |

; flag_t dropping | Equal to 1 if in drop state |

time_t target = MS2TIME(5); | Target queue delay (5 ms) |

time_t interval = MS2TIME(100); | Sliding minimum time window width (100 ms) |

u_int maxpacket = 512; | Maximum packet size in bytes (should use interface MTU) |

`Enque` uses the generic system enqueue routine after it puts the current time in the packet's `tstamp` field so that the `deque` routine can compute the packet's sojourn time.

```
void codel_queue_t::enque(packet_t* pkt)
{
pkt->timestamp() = clock();
queue_t::enque(pkt);
}
```

Since the degree of multiplexing and nature of the traffic sources is unknown, CoDel acts as a closed-loop servo system that gradually increases the frequency of dropping until the queue is controlled (sojourn time goes below `target`). This is the control law that governs the servo. It has this form because of the `sqrt(p)` dependence of TCP throughput on drop probability.^{1} Note that for embedded systems or kernel implementation the inverse `sqrt` can be computed efficiently using only integer multiplication.

time_t codel_queue_t::control_law(time_t t) { return t + interval / sqrt(count); }

This is a helper routine the does the actual packet dequeue and tracks whether the sojourn time is above or below `target` and, if above, if it has remained above continuously for at least `interval.` It returns two values, a Boolean indicating whether it is OK to drop (sojourn time above target for at least `interval`) and the packet dequeued.

typedef struct { packet_t* p; flag_t ok_to_drop; } dodeque_result; dodeque_result codel_queue_t::dodeque(time_t now) { dodeque_result r = { 0, queue::deque() }; if (r.p == NULL) { first_above_time = 0; } else { time_t sojourn_time = now - r.p->tstamp; if (sojourn_time < target || bytes() < maxpacket) { // went below so we'll stay below for at least interval first_above_time = 0; } else { if (first_above_time == 0) { // just went above from below. if we stay above // for at least interval we'll say it's ok to drop first_above_time = now + interval; } else if (now >= first_above_time) { r.ok_to_drop = 1; } } } return r; }

All of the work of CoDel is done here. There are two branches: if we're in packet-dropping state (meaning that the queue-sojourn time has gone above `target` and hasn't come down yet), then we need to check if it's time to leave or if it's time for the next drop(s); if we're not in dropping state, then we need to decide if it's time to enter and do the initial drop.

packet_t* codel_queue_t::deque() { time_t now = clock(); dodeque_result r = dodeque(); if (r.p == NULL) { // an empty queue takes us out of dropping state dropping = 0; return r.p; } if (dropping) { if (! r.ok_to_drop) { // sojourn time below target - leave dropping state dropping = 0; } else if (now >= drop_next) {

It's time for the next drop. Drop the current packet and dequeue the next. The dequeue might take us out of dropping state. If not, schedule the next drop. A large backlog might result in drop rates so high that the next drop should happen now; hence, the `while` loop.

while (now >= drop_next && dropping) { drop(r.p); ++count; r = dodeque(); if (! r.ok_to_drop) // leave dropping state dropping = 0; else // schedule the next drop. drop_next = control_law(drop_next); } }

If we get here, then we're not in dropping state. If the sojourn time has been above `target` for `interval`, then we decide whether it's time to enter dropping state. We do so if we've been either in dropping state recently or above `target` for a relatively long time. The "recently" check helps ensure that when we're successfully controlling the queue we react quickly (in one `interval`) and start with the drop rate that controlled the queue last time rather than relearn the correct rate from scratch. If we haven't been dropping recently, the "long time above" check adds some hysteresis to the state entry so we don't drop on a slightly bigger-than-normal traffic pulse into an otherwise quiet queue.

} else if (r.ok_to_drop && ((now - drop_next < interval) || (now - first_above_time >= interval))) { drop(r.p); r = dodeque(); dropping = 1; // If we're in a drop cycle, the drop rate that controlled the queue // on the last cycle is a good starting point to control it now. if (now - drop_next < interval) count = count>2? count-2 : 1; else count = 1; drop_next = control_law(now); } return (r.p); }

1. Mathis, M., Semke, J., Mahdavi, J. 1997. The macroscopic behavior of the TCP congestion avoidance algorithm. *ACM SIGCOMM Computer Communication Review* 27(3).