附录：CoDel 伪代码

数据类型

time_t是一个整数时间值，单位对于系统来说是方便的。需要至少毫秒级的分辨率，并且更好的分辨率对于输出链路上的最小可能数据包时间也很有用；可以使用 64 位或 32 位宽度，但如果使用 32 位，则分辨率不应高于 2^-16，以便有足够的动态范围来表示各种队列等待时间。更窄的宽度也会因溢出（回绕）和下溢（因截断为零而导致的极限环）而产生实现问题，这些问题在本伪代码中未解决。此处提供的代码使用 0 作为标志值来指示“未设置时间”。

packet_t*是指向数据包描述符的指针。我们假设它有一个tstamp字段，能够容纳一个time_ttime_t 值，并且该字段可供 CoDel 使用（它将由enque例程设置，并由deque例程使用）。

queue_t是队列对象的基类（codel_queue_t对象的父类）。我们假设它有enque()和方法的锁。方法，这些方法可以在子类中实现。我们假设它有一个bytes()方法，该方法返回当前队列大小（以字节为单位）。这可以是一个近似值。该方法在方法的锁。codel_dequeue()enque()方法中调用，但不应需要与

flag_t是一个布尔值。

每队列状态 (codel_queue_t 实例变量)

常量

入队 (Enque)在将当前时间放入数据包的tstamptstampdeque字段后，使用通用系统入队例程，以便

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

codel_dequeue()例程可以计算数据包的驻留时间。由于多路复用的程度和流量源的性质是未知的，CoDel 充当一个闭环伺服系统，逐渐增加丢包的频率，直到队列被控制（驻留时间低于target）。这是控制伺服系统的控制律。它具有这种形式是因为 TCP 吞吐量对丢包概率的sqrt(p)依赖性¹。请注意，对于嵌入式系统或内核实现，反

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

sqrt例程可以计算数据包的驻留时间。可以使用仅整数乘法有效地计算出来。这是一个辅助例程，它执行实际的数据包出队操作，并跟踪驻留时间是否高于或低于target，以及如果高于，是否已持续高于至少interval。

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

它返回两个值：一个布尔值，指示是否可以丢包（驻留时间高于目标至少例程可以计算数据包的驻留时间。interval

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

），以及出队的数据包。CoDel 的所有工作都在这里完成。这里有两个分支：如果我们处于丢包状态（意味着队列驻留时间已高于target

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

且尚未降下来），那么我们需要检查是否应该离开丢包状态，或者是否应该进行下一次（或多次）丢包；如果我们没有处于丢包状态，那么我们需要决定是否应该进入丢包状态并进行初始丢包。例程可以计算数据包的驻留时间。现在是下一次丢包的时间。丢弃当前数据包并使下一个数据包出队。出队操作可能会使我们脱离丢包状态。如果不是，则安排下一次丢包。大量的积压可能会导致丢包率非常高，以至于下一次丢包应该立即发生；因此，有，以及如果高于，是否已持续高于至少while例程可以计算数据包的驻留时间。循环。，以及如果高于，是否已持续高于至少如果我们到达这里，那么我们没有处于丢包状态。如果驻留时间高于

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

target

已超过