java.lang.Object
net.i2p.util.SyntheticREDQueue
All Implemented Interfaces:
BandwidthEstimator
public class SyntheticREDQueueextends Object implements BandwidthEstimator
A "synthetic" queue that does not store data but estimates the average queue size assuming a fixed output bandwidth, and applies the Random Early Detection (RED) algorithm to decide probabilistically whether to accept or drop packets.

The purpose is to model queue behavior and preemptively drop packets to prevent congestion before an actual queue is affected downstream.

The average queue size is measured in bytes and is updated continuously, assuming the queue drains at a constant rate defined at construction.

Packet acceptance is based on the RED algorithm, which uses the current average queue size and the offered packet size to calculate a drop probability. The drop probability is adjusted by a factor parameter and limited by configurable minimum and maximum queue size thresholds.

This class also incorporates a Westwood+ bandwidth estimator that updates bandwidth estimates based on acknowledged packet sizes and timing, using an exponential weighted moving average (EWMA). Both bandwidth and queue size estimates are only updated when packets are accepted.

The implementation is adapted from the Linux kernel tcp_westwood.c logic and follows established research including: - Random Early Detection Gateways for Congestion Avoidance (Floyd & Jacobson) - TCP Westwood: End-to-End Congestion Control for Wired/Wireless Networks (Casetti et al.) - End-to-End Bandwidth Estimation for Congestion Control (Grieco & Mascolo)

Note: minThB (minimum threshold) must be less than maxThB (maximum threshold) for correct RED operation.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private float
    _avgQueueSize
    Average queue size estimate.
    private final int
    _bandwidthBps
    The link bandwidth, in bytes per second.
    private final float
    _bandwidthBytesPerMs
    The link bandwidth, in bytes per ms.
    private float
    _bKFiltered
    Filtered bandwidth-delay estimate.
    private float
    _bKNonSmoothed
    Unsmoothed bandwidth-delay estimate.
    private int
    _bytesAcked
    Bytes acknowledged in the current period.
    private final I2PAppContext
    _context
    The app context.
    private int
    _dropCount
    Packets dropped since the last ack, -1 if none.
    private long
    _lastAckTime
    When the last ack was received.
    private long
    _lastQueueUpdateTime
    When the queue estimate was last updated.
    private final Log
    _log
    Logger for the queue.
    private static float
    _maxDropProbability
    Largest drop probability used.
    private int
    _maxThresholdBytes
    Queue size where dropping is certain.
    private int
    _minThresholdBytes
    Queue size where dropping starts.
    private int
    _newDataSize
    Bytes queued but not sent yet.
    private float
    _queueSizeEstimate
    Current queue size estimate.
    private final Random
    _random
    Random source for the drop decisions.
    private static final int
    DECAY_FACTOR
    Divisor of the queue size decay.
    private static final int
    DEFAULT_HIGH_THRESHOLD_DIV
    Divisor giving the high queue threshold.
    private static final int
    DEFAULT_LOW_THRESHOLD_DIV
    Divisor giving the low queue threshold.
    private static final CopyOnWriteArrayList<WeakReference<SyntheticREDQueue>>
    INSTANCES
    Active instances for dynamic tuning — weak refs prevent leak when tunnels expire.
    private static final int
    WESTWOOD_RTT_MIN
    Smallest round trip time assumed, in ms.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SyntheticREDQueue(I2PAppContext ctx, int bwBps)
    With default queue size thresholds based on bandwidth.
    SyntheticREDQueue(I2PAppContext ctx, int bwBps, int minThB, int maxThB)
    With the given bandwidth and queue size thresholds.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addSample(int size)
    Unconditionally accepts the given packet size.
    private boolean
    addSampleInternal(int bytes, float factor, long now)
    Core synchronized update method that processes incoming byte packets, decides whether to accept or drop them based on queue size and probabilistic dropping, and updates bandwidth and queue statistics accordingly.
    private float
    computeBandwidthEstimate(long now, int rtt)
    Computes and updates the bandwidth estimate applying the Westwood EWMA filter.
    private void
    decayBandwidth()
    Applies an exponential weighted moving average (EWMA) decay to the bandwidth estimate, simulating bandwidth reduction when no packets have been received.
    private void
    decayQueue(int rtt)
    Applies EWMA decay to the queue size estimate to simulate queue draining over the given RTT.
    void
    dispose()
    Remove this instance from the tuning list.
    static void
    expungeStaleInstances()
    Remove cleared (GC'd) weak references from the list.
    float
    getBandwidthEstimate()
    Returns the current bandwidth estimate in bytes/ms.
    static float
    getCurrentMaxDropProbability()
    Returns current max drop probability across all instances.
    static int
    getCurrentMaxThreshold()
    Returns the maximum threshold from the first active instance, or -1 if none.
    static int
    getCurrentMinThreshold()
    Returns the minimum threshold from the first active instance, or -1 if none.
    static List<SyntheticREDQueue>
    getInstances()
    Returns a snapshot of all active SyntheticREDQueue instances.
    int
    getMaxBandwidth()
    Maximum bandwidth this queue is configured for.
    float
    getMaxDropProbability()
    The ceiling on the random drop probability for this queue.
    int
    getMaxThreshold()
    Returns the current maximum threshold in bytes.
    int
    getMinThreshold()
    Returns the current minimum threshold in bytes.
    float
    getQueueSizeEstimate()
    Returns the current estimated average queue size in bytes.
    boolean
    offer(int size, float factor)
    Offer a packet to the queue.
    String
    toString()
    Returns a human-readable string displaying the current bandwidth and queue size estimates, formatted for DEBUG logging.
    String
    toStringShort()
    Returns a cut-down status string with the bandwidth estimate and the configured limit, omitting the average queue size.
    static void
    updateAllMaxDropProbability(float probability)
    Update max drop probability on all active instances.
    static void
    updateAllMaxThresholds(int threshold)
    Update max threshold on all active instances.
    static void
    updateAllMinThresholds(int threshold)
    Update min threshold on all active instances.
    private void
    updateBandwidthEstimate(long time, int packets, int rtt)
    Updates the bandwidth estimate based on newly acknowledged bytes and elapsed time, applying Westwood EWMA filtering and injecting decay for periods with no packets.
    private void
    updateQueueSize(long time, long deltaT)
    Updates the average queue size estimator with new data sizes and elapsed time, applying EWMA filtering and decay to reflect queue drainage.
    private static float
    westwoodFilter(float oldVal, float newVal)
    Applies a Westwood exponential weighted moving average (EWMA) filter, combining previous and new sample values with a weighted average.

    Methods inherited from class Object

    clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • _maxDropProbability

      private static volatile float _maxDropProbability
      Largest drop probability used.

    • DECAY_FACTOR

      private static final int DECAY_FACTOR
      Divisor of the queue size decay.
      See Also:

    • WESTWOOD_RTT_MIN

      private static final int WESTWOOD_RTT_MIN
      Smallest round trip time assumed, in ms.
      See Also:

    • DEFAULT_LOW_THRESHOLD_DIV

      private static final int DEFAULT_LOW_THRESHOLD_DIV
      Divisor giving the low queue threshold.
      See Also:

    • DEFAULT_HIGH_THRESHOLD_DIV

      private static final int DEFAULT_HIGH_THRESHOLD_DIV
      Divisor giving the high queue threshold.
      See Also:

    • INSTANCES

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

    • _context

      private final I2PAppContext _context
      The app context.

    • _log

      private final Log _log
      Logger for the queue.

    • _random

      private final Random _random
      Random source for the drop decisions.

    • _lastAckTime

      private volatile long _lastAckTime
      When the last ack was received.

    • _bKFiltered

      private volatile float _bKFiltered
      Filtered bandwidth-delay estimate.

    • _bKNonSmoothed

      private float _bKNonSmoothed
      Unsmoothed bandwidth-delay estimate.

    • _bytesAcked

      private volatile int _bytesAcked
      Bytes acknowledged in the current period.

    • _dropCount

      private int _dropCount
      Packets dropped since the last ack, -1 if none.

    • _avgQueueSize

      private volatile float _avgQueueSize
      Average queue size estimate.

    • _queueSizeEstimate

      private float _queueSizeEstimate
      Current queue size estimate.

    • _newDataSize

      private int _newDataSize
      Bytes queued but not sent yet.

    • _lastQueueUpdateTime

      private volatile long _lastQueueUpdateTime
      When the queue estimate was last updated.

    • _minThresholdBytes

      private int _minThresholdBytes
      Queue size where dropping starts.

    • _maxThresholdBytes

      private int _maxThresholdBytes
      Queue size where dropping is certain.

    • _bandwidthBps

      private final int _bandwidthBps
      The link bandwidth, in bytes per second.

    • _bandwidthBytesPerMs

      private final float _bandwidthBytesPerMs
      The link bandwidth, in bytes per ms.

  • Constructor Details

    • SyntheticREDQueue

      public SyntheticREDQueue(I2PAppContext ctx, int bwBps)
      With default queue size thresholds based on bandwidth.
      Parameters:
      ctx - the I2P application context
      bwBps - nominal output bandwidth in bytes per second

    • SyntheticREDQueue

      public SyntheticREDQueue(I2PAppContext ctx, int bwBps, int minThB, int maxThB)
      With the given bandwidth and queue size thresholds.

      Queue size thresholds: - minThB: queue size in bytes to start probabilistically dropping packets - maxThB: queue size in bytes at which all packets are dropped (100% drop probability)

      NOTE: minThB must be less than maxThB for proper operation.

      Parameters:
      ctx - the I2P application context
      bwBps - nominal output bandwidth in bytes per second
      minThB - minimum threshold queue size to start dropping (Bytes)
      maxThB - maximum threshold queue size to drop all packets (Bytes)

  • 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.

    • updateAllMaxDropProbability

      public static void updateAllMaxDropProbability(float probability)
      Update max drop probability on all active instances.
      Parameters:
      probability - new max drop probability (0.0 - 1.0)

    • updateAllMinThresholds

      public static void updateAllMinThresholds(int threshold)
      Update min threshold on all active instances.
      Parameters:
      threshold - new minimum threshold in bytes (must be less than max)

    • updateAllMaxThresholds

      public static void updateAllMaxThresholds(int threshold)
      Update max threshold on all active instances.
      Parameters:
      threshold - new maximum threshold in bytes (must be greater than min)

    • getCurrentMaxDropProbability

      public static float getCurrentMaxDropProbability()
      Returns current max drop probability across all instances.
      Returns:
      the current max drop probability

    • getCurrentMinThreshold

      public static int getCurrentMinThreshold()
      Returns the minimum threshold from the first active instance, or -1 if none.
      Returns:
      the current min threshold

    • getCurrentMaxThreshold

      public static int getCurrentMaxThreshold()
      Returns the maximum threshold from the first active instance, or -1 if none.
      Returns:
      the current max threshold

    • getInstances

      public static List<SyntheticREDQueue> getInstances()
      Returns a snapshot of all active SyntheticREDQueue instances.
      Returns:
      the instances still strongly reachable, as the rest are held weakly

    • getMaxBandwidth

      public int getMaxBandwidth()
      Maximum bandwidth this queue is configured for.
      Returns:
      the configured maximum bandwidth in bytes per second

    • getMinThreshold

      public int getMinThreshold()
      Returns the current minimum threshold in bytes.
      Returns:
      the min threshold

    • getMaxThreshold

      public int getMaxThreshold()
      Returns the current maximum threshold in bytes.
      Returns:
      the max threshold

    • getMaxDropProbability

      public float getMaxDropProbability()
      The ceiling on the random drop probability for this queue.
      Returns:
      the max drop probability

    • addSample

      public void addSample(int size)
      Unconditionally accepts the given packet size. Updates queue size and bandwidth estimates accordingly.
      Specified by:
      addSample in interface BandwidthEstimator
      Parameters:
      size - size of packet in bytes

    • offer

      public boolean offer(int size, float factor)
      Offer a packet to the queue.

      The decision to accept or drop the packet is made based on RED algorithm using the current average queue size and the offered packet size with a drop probability. If packet is accepted, the queue size and bandwidth estimators are updated.

      Parameters:
      size - size in bytes of the packet
      factor - drop probability adjustment factor (1.0 for standard, 0 disables dropping)
      Returns:
      true if accepted, false if dropped

    • addSampleInternal

      private boolean addSampleInternal(int bytes, float factor, long now)
      Core synchronized update method that processes incoming byte packets, decides whether to accept or drop them based on queue size and probabilistic dropping, and updates bandwidth and queue statistics accordingly.
      Parameters:
      bytes - Number of bytes in the sample or packet received.
      factor - A factor affecting drop probability, typically related to congestion level (0 if no drop logic needed).
      now - Current timestamp in milliseconds.
      Returns:
      true if the bytes are accepted and stats updated, false if the sample is dropped.

    • getBandwidthEstimate

      public float getBandwidthEstimate()
      Returns the current bandwidth estimate in bytes/ms. Updates estimate if enough time elapsed since last update.
      Specified by:
      getBandwidthEstimate in interface BandwidthEstimator
      Returns:
      bandwidth estimate in bytes/ms

    • getQueueSizeEstimate

      public float getQueueSizeEstimate()
      Returns the current estimated average queue size in bytes. Updates estimate if enough time elapsed since last update.
      Returns:
      queue size estimate in bytes

    • computeBandwidthEstimate

      private float computeBandwidthEstimate(long now, int rtt)
      Computes and updates the bandwidth estimate applying the Westwood EWMA filter. Resets acknowledged byte count after update.
      Parameters:
      now - current time in milliseconds
      rtt - round-trip time in milliseconds (used as filter parameter)
      Returns:
      the updated bandwidth estimate in bytes/ms

    • decayBandwidth

      private void decayBandwidth()
      Applies an exponential weighted moving average (EWMA) decay to the bandwidth estimate, simulating bandwidth reduction when no packets have been received.

    • decayQueue

      private void decayQueue(int rtt)
      Applies EWMA decay to the queue size estimate to simulate queue draining over the given RTT. Ensures queue size estimate does not drop below zero.
      Parameters:
      rtt - round-trip time in milliseconds to use for decay calculation

    • updateBandwidthEstimate

      private void updateBandwidthEstimate(long time, int packets, int rtt)
      Updates the bandwidth estimate based on newly acknowledged bytes and elapsed time, applying Westwood EWMA filtering and injecting decay for periods with no packets.
      Parameters:
      time - current time in milliseconds
      packets - number of bytes acknowledged since last update
      rtt - current round-trip time in milliseconds (minimum enforced)

    • updateQueueSize

      private void updateQueueSize(long time, long deltaT)
      Updates the average queue size estimator with new data sizes and elapsed time, applying EWMA filtering and decay to reflect queue drainage.
      Parameters:
      time - current time in milliseconds
      deltaT - time elapsed since the last update in milliseconds

    • westwoodFilter

      private static float westwoodFilter(float oldVal, float newVal)
      Applies a Westwood exponential weighted moving average (EWMA) filter, combining previous and new sample values with a weighted average.
      Parameters:
      oldVal - previous filtered value
      newVal - new sample value
      Returns:
      updated filtered value

    • toString

      public String toString()
      Returns a human-readable string displaying the current bandwidth and queue size estimates, formatted for DEBUG logging.
      Overrides:
      toString in class Object
      Returns:
      formatted status string including bandwidth and average queue size

    • toStringShort

      public String toStringShort()
      Returns a cut-down status string with the bandwidth estimate and the configured limit, omitting the average queue size. The queue size is an internal RED estimator depth, useful when diagnosing the estimator at DEBUG but noise on an operator-facing summary row, so the I2PSnark netstatus debug section uses this form instead of toString().

      Values are separated by a bullet, matching the multi-value debug spans in KRPC. Inline HTML is deliberate: this method exists only for that single debug row.

      Returns:
      formatted status string with bandwidth and limit only