java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractQueue<E>
java.util.concurrent.LinkedBlockingQueue<E>
net.i2p.router.util.CoDelBlockingQueue<E>
Type Parameters:
E - type of elements in this queue
All Implemented Interfaces:
Serializable, Iterable<E>, Collection<E>, BlockingQueue<E>, Queue<E>
public class CoDelBlockingQueue<E extends CDQEntry>extends LinkedBlockingQueue<E>
CoDel (Controlled Delay) implementation of Active Queue Management.

Implements the CoDel algorithm from RFC 8289 for managing queue congestion and controlling latency through packet dropping. Provides active queue management with automatic dropping when queue delay exceeds configurable thresholds.

Code and comments are derived from RFC 8289 appendix, implementing the standard CoDel algorithm with configurable target delay and interval parameters. Monitors queue sojourn time and drops packets when above target to maintain optimal throughput and latency characteristics.

Input methods are overridden to add timestamps for delay calculation. Output methods implement AQM behavior with comprehensive statistics tracking for performance monitoring.

See Also:

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      Fixed id, the format is never serialized across versions.
      See Also:

    • _context

      private final transient I2PAppContext _context
      Supplies the clock and the statistics.

    • _log

      private final transient Log _log
      Logger for this class.

    • _name

      private final String _name
      Queue name.

    • _capacity

      private final int _capacity
      Maximum queue capacity.

    • _first_above_time

      private long _first_above_time
      Time when we'll declare we're above target (0 if below). One of four CoDel state variables below, all locked by this.

    • _drop_next

      private long _drop_next
      Time to drop next packet.

    • _count

      private int _count
      Packets dropped since going into drop state.

    • _dropping

      private boolean _dropping
      True if in drop state.

    • _now

      private long _now
      Per-request global for ease of use, locked by this.

    • __id

      private static final AtomicLong __id
      Unique ID generator for instances.

    • _id

      private final long _id
      Instance ID.

    • INSTANCES

      private static final CopyOnWriteArrayList<WeakReference<CoDelBlockingQueue>> INSTANCES
      Active instances for dynamic tuning — weak refs prevent leak when tunnels expire.

    • PROP_CODEL_TARGET

      public static final String PROP_CODEL_TARGET
      Property overriding the CoDel target delay in ms.
      See Also:

    • PROP_CODEL_INTERVAL

      public static final String PROP_CODEL_INTERVAL
      Property overriding the interval in ms between CoDel drop decisions.
      See Also:

    • DEFAULT_CODEL_TARGET

      private static final int DEFAULT_CODEL_TARGET
      Quote: Below a target of 5 ms, utilization suffers for some conditions and traffic loads; above 5 ms there is very little or no improvement in utilization.

      I2P: Lowered to 5ms for reduced latency in high-performance scenarios.

      See Also:

    • _target

      private volatile long _target
      CoDel target delay in ms.

    • DEFAULT_CODEL_INTERVAL

      private static final int DEFAULT_CODEL_INTERVAL
      Quote: A setting of 100 ms works well across a range of RTTs from 10 ms to 1 second

      I2P: Lowered to 50ms for faster reaction to congestion.

      See Also:

    • _interval

      private volatile long _interval
      CoDel interval in ms.

    • STAT_DELAY

      private final String STAT_DELAY
      RateStat name for message delay.

    • BACKLOG_TIME

      private static final long BACKLOG_TIME
      How long an item may sit before the queue counts as backlogged, in ms.

    • MAX_DROPS_PER_CALL

      private static final int MAX_DROPS_PER_CALL
      Most items dropped in one control-law call.
      See Also:

  • Constructor Details

    • CoDelBlockingQueue

      public CoDelBlockingQueue(I2PAppContext ctx, String name, int capacity)
      Queue with default CoDel target and interval from properties.
      Parameters:
      ctx - the I2P application context
      name - name for this queue instance
      capacity - the maximum capacity of the queue

    • CoDelBlockingQueue

      public CoDelBlockingQueue(I2PAppContext ctx, String name, int capacity, int target, int interval)
      Queue with explicit CoDel target and interval.
      Parameters:
      ctx - the I2P application context
      name - the label identifying this queue in log messages
      capacity - the maximum capacity of the queue
      target - the CoDel target delay in ms, held without delay
      interval - how long above target to start dropping (ms)

  • Method Details

    • dispose

      public void dispose()
      Remove this instance from the tuning list. Called when the owning tunnel/queue is no longer active.

    • expungeStaleInstances

      public static void expungeStaleInstances()
      Remove cleared (GC'd) weak references from the list.

    • updateAllTargets

      public static void updateAllTargets(long target)
      Update target on all active CoDelBlockingQueue instances.
      Parameters:
      target - the new target delay in ms

    • updateAllIntervals

      public static void updateAllIntervals(long interval)
      Update interval on all active CoDelBlockingQueue instances.
      Parameters:
      interval - the new interval in ms

    • getTarget

      public long getTarget()
      The CoDel target queuing delay, the delay considered acceptable before the queue is judged congested.
      Returns:
      the target delay in ms

    • setTarget

      public void setTarget(long target)
      Current CoDel target delay in ms.
      Parameters:
      target - the new target delay in ms

    • getInterval

      public long getInterval()
      The CoDel measuring interval, the sliding window over which the minimum queuing delay is observed.
      Returns:
      the interval in ms

    • setInterval

      public void setInterval(long interval)
      Current CoDel interval in ms.
      Parameters:
      interval - the new interval in ms

    • add

      public boolean add(E o)
      Add an element, recording the enqueue time.
      Specified by:
      add in interface BlockingQueue<E extends CDQEntry>
      Specified by:
      add in interface Collection<E extends CDQEntry>
      Specified by:
      add in interface Queue<E extends CDQEntry>
      Overrides:
      add in class AbstractQueue<E extends CDQEntry>

    • offer

      public boolean offer(E o)
      Offer an element, recording the enqueue time.
      Specified by:
      offer in interface BlockingQueue<E extends CDQEntry>
      Specified by:
      offer in interface Queue<E extends CDQEntry>
      Overrides:
      offer in class LinkedBlockingQueue<E extends CDQEntry>

    • offer

      public boolean offer(E o, long timeout, TimeUnit unit) throws InterruptedException
      Offer an element, recording the enqueue time.
      Specified by:
      offer in interface BlockingQueue<E extends CDQEntry>
      Overrides:
      offer in class LinkedBlockingQueue<E extends CDQEntry>
      Throws:
      InterruptedException

    • put

      public void put(E o) throws InterruptedException
      Put an element, recording the enqueue time.
      Specified by:
      put in interface BlockingQueue<E extends CDQEntry>
      Overrides:
      put in class LinkedBlockingQueue<E extends CDQEntry>
      Throws:
      InterruptedException

    • clear

      public void clear()
      Clear the queue and reset CoDel state.
      Specified by:
      clear in interface Collection<E extends CDQEntry>
      Overrides:
      clear in class LinkedBlockingQueue<E extends CDQEntry>

    • take

      public E take() throws InterruptedException
      Take the next element, applying CoDel drops as needed.
      Specified by:
      take in interface BlockingQueue<E extends CDQEntry>
      Overrides:
      take in class LinkedBlockingQueue<E extends CDQEntry>
      Throws:
      InterruptedException

    • poll

      public E poll()
      Poll the next element, applying CoDel drops as needed.
      Specified by:
      poll in interface Queue<E extends CDQEntry>
      Overrides:
      poll in class LinkedBlockingQueue<E extends CDQEntry>

    • drainTo

      public int drainTo(Collection<? super E> c)
      Updates stats and possibly drops while draining. May exit early if a CoDel drop occurs (poll() returns null for a dropped item).
      Specified by:
      drainTo in interface BlockingQueue<E extends CDQEntry>
      Overrides:
      drainTo in class LinkedBlockingQueue<E extends CDQEntry>

    • drainTo

      public int drainTo(Collection<? super E> c, int maxElements)
      Updates stats and possibly drops while draining. May exit early if a CoDel drop occurs (poll() returns null for a dropped item).
      Specified by:
      drainTo in interface BlockingQueue<E extends CDQEntry>
      Overrides:
      drainTo in class LinkedBlockingQueue<E extends CDQEntry>

    • drainAllTo

      public int drainAllTo(Collection<? super E> c)
      Drains all, without updating stats or dropping.
      Parameters:
      c - the collection to drain into
      Returns:
      the number of elements drained

    • isBacklogged

      public boolean isBacklogged()
      Has the head of the queue been waiting too long, or is the queue almost full?
      Returns:
      true if the queue is backlogged

    • updateVars

      private boolean updateVars(E entry)
      Caller must synch on this.
      Parameters:
      entry - may be null
      Returns:
      true if the sojourn time has been above target long enough to drop

    • deque

      private E deque() throws InterruptedException
      Dequeue the next element, applying CoDel drops as needed.
      Returns:
      if null, call again
      Throws:
      InterruptedException - if the calling thread is interrupted while waiting

    • codel

      private E codel(E rv)
      Apply CoDel control to the given entry, dropping if needed.
      Parameters:
      rv - may be null
      Returns:
      rv or a subequent entry or null if dropped

    • drop

      private void drop(E entry)
      Discards a backlogged item and logs it.
      Parameters:
      entry - the item to drop

    • control_law

      private void control_law(long t)
      Caller must synch on this.
      Parameters:
      t - the current time in ms, the base for the next drop time