Subject: Re: [Diffserv] MAX Threshold in RED

From: Simon Leinen <[email-masked]>
Date: 02 Mar 2001 17:13:34 +0100

Ratnakar,

>      In the Random Drop Table of the MIB, the random drop algorithm
> is to drop a Packet with a probability equal to the MaxProb
> specified , when the queue average crosses the the Maximum
> Thresholds. But isnt it that this specifies the Max Probability to
> be used only when the Queue average is between the minimum and
> maximum thresholds, and when the average crosses the maximum
> threshold , every packet should be dropped? If it is as specified in
> the MIB, then the Queue Average could increase even when the Queue
> Average is greater than the Maximum Threshold....

What you expect corresponds to classical RED as defined in [1,2]: When
the smoothed average queue length exceeds the second ("max")
threshold, all packets are dropped.

Section 3.5.2 of the I-D describes a variant of RED which is commonly
referred to as "gentle" RED.  Using my limited tools (no library but
WWW access), I couldn't come up with self-contained descriptions of
it.  The best approximation seems to be the last paragraph
http://www.aciri.org/floyd/REDfunc.txt (followed by an unfinished
ASCII art graph which should probably look somewhat like this:

    dropping probability
 1--+-------------------------------------------+
    |			              	      * |
    |			      	      	    *	|
    |	       		       	      	  *	|
    |			               	*	|
    |	       		       	      *		|
    |			            *		|
    |			       	  *		|
    |	       		       	*		|
maxp+-------------------------+-----------------+
    |  	                   *  |			|
    |	                *     |			|
    |	             *        |			|
    |	          *           |			|
    |	       *              |			|
    |_________________________|_________________|  average queue size
           |                  |                 |
        minthresh         maxthresh       maxthresh + XXX  [Sally's terms]
          Qmin              Qmax             Qclip [diffserv-mib-08 terms])

The MIB DEFINITIONS however don't contain a variable that would
correspond to Qclip.  This is at least confusing (maybe Qclip is meant
to be 2 * Qmax, as Sally suggested?).

I'm thinking about how this part of the MIB could be improved, but
currently I don't have time to write something down.

Regards,
-- 
Simon.

[1] Random Early Detection (RED) gateways for Congestion Avoidance,
Floyd, S. and V. Jacobson, IEEE/ACM Transactions on Networking, V.1
N.4, August 1993, p. 397-413.
<URL:http://www.aciri.org/floyd/papers/red/red.html>

[2] Recommendations on Queue Management and Congestion Avoidance in
the Internet, RFC 2309, B. Braden, D. Clark, J. Crowcroft, B. Davie,
S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall,
C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski,
L. Zhang, April 1998
<URL:ftp://ftp.isi.edu/in-notes/rfc2309.txt>

_______________________________________________
diffserv mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/diffserv
Archive: http://www2.ietf.org/mail-archive/working-groups/diffserv/current/maillist.html

---

From: Simon Leinen <[email-masked]>
Date: 03 Mar 2001 01:21:58 +0100

>>>>> "sl" == Simon Leinen <[email-masked]> writes:
> referred to as "gentle" RED. [...]

> correspond to Qclip.  This is at least confusing (maybe Qclip is
> meant to be 2 * Qmax, as Sally suggested?).

Sorry, I hadn't read the description thoroughly enough.  It says quite
clearly: "diffServAlgDropQThreshold represents Qclip".  Welllllllll...
in my opinion, Qclip should be independent of the physical size of the
queue, but the DESCRIPTION of diffServRandomDropMaxThreshBytes suggests
that, for random droppers, diffServAlgDropQThreshold is the queue depth.

I have another fundamental problem with the way the droppers, and in
particular the random dropper, are specified: it's not clear whether they
count packets or bytes.  The specific thresholds in the random dropper
both have a byte-counting variant as well as a packet-counting variant,
e.g. diffServRandomDropMinThreshBytes and diffServRandomDropMinThreshPkts.

It's fine if both packet-counting and byte-counting RED can be expressed,
but, in my limited imagination, a given RED can only do one at a time.
When I set diffServRandomDropMinThreshBytes, then that change "may or may
not be reflected in the reported value of
diffServRandomDropMinThreshPkts.", but how do I know whether the dropper
will listen to my byte-threshold or to a packet-threshold derived from
it? It certainly cannot do both.

Also note that for Qclip, there's only a byte-counting version
(diffServAlgDropQThreshold).  That currently breaks the possibility to
describe both byte- and packet-counting random droppers.

For the non-random droppers, it means that only byte-counting head/tail
droppers can be expressed.  Personally I think that's fine, but it may be
problematic for some types of queue implementations.  Fortunately I don't
build routers, I just operate them.  So let's leave it as is.

So here are my suggestions (a context diff relative to the -09 draft is
appended):

* Qclip should be independent from physical queue depth.  Add variables
  for Qclip to DiffServRandomDropEntry, let's say
  "diffServRandomDropClipThresh"{Bytes,Pkts}.

* It should be possible to specify all queue-size-valued parameters of
  the random dropper (diffServRandomDrop{Min,Max,Clip}Thresh) as either
  packets or bytes, but not independently, i.e. if one is specified in
  bytes, you cannot specify another in bytes (at least not in the same
  dropper).

  Each DiffServRandomDropEntry should have an additional variable
  "diffServRandomDropCountStyle" which can be packets(1) or octets(2).
  On some boxes this will be read-only (because they only support one
  style of counting), on others you can select the counting style per
  dropper.

  For each threshold, we can either keep separate bytes/packets
  variables, only one of which will be used depending on
  diffServRandomDropCountStyle, or have only one "overloaded" variable
  per threshold that should be interpreted depending on
  diffServRandomDropCountStyle.  I have no idea which is preferable, so
  let's leave it as is (two variables per threshold).

* "Bytes" should be renamed "Octets" everywhere to appease the God of MIBs.
-- 
Simon.
*** draft-ietf-diffserv-mib-09.txt	Sat Mar  3 01:04:56 2001
--- draft-ietf-diffserv-mib-09s00.txt	Sat Mar  3 01:20:04 2001
***************
*** 679,694 ****
  defines the queue length at which all packets will be dropped. Notice
  this is different from Tail Drop because this uses an averaged queue
! length.  Although it is possible for Qclip = Qmax.
  
! In the MIB module, diffServRandomDropMinThreshBytes and
  diffServRandomDropMinThreshPkts represent Qmin.
! diffServRandomDropMaxThreshBytes and diffServRandomDropMaxThreshPkts
! represent Qmax.  diffServAlgDropQThreshold represents Qclip.
! diffServRandomDropInvProbMax represents Pmax (inverse).  This MIB does
! not represent Pmin (assumed to be zero unless otherwise represented).
! In addition, since message memory is finite, queues generally have some
! upper bound above which they are incapable of storing additional
! traffic.  Normally this number is equal to Qclip, specified by
! diffServeAlgDropQThreshold.
  
  Each random dropper specification is associated with a queue. This
--- 679,695 ----
  defines the queue length at which all packets will be dropped. Notice
  this is different from Tail Drop because this uses an averaged queue
! length.
  
! In the MIB module, diffServRandomDropMinThreshOctets and
  diffServRandomDropMinThreshPkts represent Qmin.
! diffServRandomDropMaxThreshOctets and diffServRandomDropMaxThreshPkts
! represent Qmax.  diffServRandomDropClipThreshOctets and
! diffServRandomDropClipThreshPkts represent Qclip.
! diffServRandomDropProbMax represents Pmax.  This MIB does not represent
! Pmin (assumed to be zero unless otherwise represented).  In addition,
! diffServAlgDropQThreshold represents the maximum capacity of the queue
! beyond which no new packets can be stored.  diffServRandomDropCountStyle
! states whether the dropper operates on units of packets or octets.  This
! variable selects which set of the threshold variables will be used.
  
  Each random dropper specification is associated with a queue. This
***************
*** 701,712 ****
    --->| Next   ---------+--+------------------->| Next -+--> ...
        | QMeasure -------+--+                    | ...   |
!       | QThreshold      |     RandomDrop        +-------+
!       | Type=randomDrop |     +----------------+
!       | Specific -------+---->| MinThreshBytes |
!       +-----------------+     | MaxThreshBytes |
!                               | InvProbMax     |
!                               | InvWeight      |
!                               | SamplingRate   |
!                               +----------------+
  
    Figure 1: Example Use of the RandomDropTable for Random Droppers
--- 702,715 ----
    --->| Next   ---------+--+------------------->| Next -+--> ...
        | QMeasure -------+--+                    | ...   |
!       | QThreshold      |    RandomDrop         +-------+
!       | Type=randomDrop |    +-----------------+
!       | Specific -------+--->| MinThreshOctets |
!       +-----------------+    | MaxThreshOctets |
!                              | ClipThreshOctets|
!                              | ProbMax         |
!                              | InvWeight       |
!                              | SamplingRate    |
!                              | CountStyle      |
!                              +-----------------+
  
    Figure 1: Example Use of the RandomDropTable for Random Droppers
***************
*** 2774,2782 ****
  diffServTBParamBurstSize OBJECT-TYPE
      SYNTAX       BurstSize
!     UNITS        "Bytes"
      MAX-ACCESS   read-create
      STATUS       current
      DESCRIPTION
!        "The maximum number of bytes in a single transmission burst.
         This attribute is used for:  1. CBS and EBS in RFC 2697 for srTCM
         2. CBS and PBS in RFC 2698 for trTCM 3. Burst Size used in
--- 2777,2785 ----
  diffServTBParamBurstSize OBJECT-TYPE
      SYNTAX       BurstSize
!     UNITS        "octets"
      MAX-ACCESS   read-create
      STATUS       current
      DESCRIPTION
!        "The maximum number of octets in a single transmission burst.
         This attribute is used for:  1. CBS and EBS in RFC 2697 for srTCM
         2. CBS and PBS in RFC 2698 for trTCM 3. Burst Size used in
***************
*** 3547,3557 ****
  
         arrival, an algorithm is executed which may randomly drop the
!        packet, or drop other packet(s) from the queue in its place. The
!        specifics of the algorithm may be proprietary. For this
!        algorithm, diffServAlgDropSpecific points to a
         diffServRandomDropEntry that describes the algorithm.  For this
!        algorithm, diffServAlgQThreshold is understood to be the absolute
!        maximum size of the queue and additional parameters are described
!        in diffServRandomDropTable."
      ::= { diffServAlgDropEntry 2 }
  
--- 3550,3560 ----
  
         arrival, an algorithm is executed which may randomly drop the
!        packet, or drop other packet(s) from the queue in its
!        place. The specifics of the algorithm may be proprietary. For
!        this algorithm, diffServAlgDropSpecific points to a
         diffServRandomDropEntry that describes the algorithm.  For this
!        algorithm, diffServAlgDropQThreshold is understood to be the
!        absolute maximum size of the queue and additional parameters
!        are described in diffServRandomDropTable."
      ::= { diffServAlgDropEntry 2 }
  
***************
*** 3592,3596 ****
  diffServAlgDropQThreshold OBJECT-TYPE
      SYNTAX       Unsigned32
!     UNITS        "Bytes"

--- 3595,3599 ----
  diffServAlgDropQThreshold OBJECT-TYPE
      SYNTAX       Unsigned32
!     UNITS        "octets"

***************
*** 3609,3613 ****
      STATUS       current
      DESCRIPTION
!        "A threshold on the depth in bytes of the queue being measured at
         which a trigger is generated to the dropping algorithm.
  
--- 3612,3616 ----
      STATUS       current
      DESCRIPTION
!        "A threshold on the depth in octets of the queue being measured at
         which a trigger is generated to the dropping algorithm.
  
***************
*** 3771,3775 ****
  DiffServRandomDropEntry ::= SEQUENCE  {
      diffServRandomDropId               Unsigned32,
!     diffServRandomDropMinThreshBytes   Unsigned32,
      diffServRandomDropMinThreshPkts    Unsigned32,
  
--- 3774,3778 ----
  DiffServRandomDropEntry ::= SEQUENCE  {
      diffServRandomDropId               Unsigned32,
!     diffServRandomDropMinThreshOctets  Unsigned32,
      diffServRandomDropMinThreshPkts    Unsigned32,
  
***************
*** 3786,3794 ****

!     diffServRandomDropMaxThreshBytes   Unsigned32,
      diffServRandomDropMaxThreshPkts    Unsigned32,
!     diffServRandomDropProbMax       Unsigned32,
      diffServRandomDropInvWeight        Unsigned32,
      diffServRandomDropSamplingRate     Unsigned32,
      diffServRandomDropStatus           RowStatus
  }
--- 3789,3800 ----

!     diffServRandomDropMaxThreshOctets  Unsigned32,
      diffServRandomDropMaxThreshPkts    Unsigned32,
!     diffServRandomDropClipThreshOctets Unsigned32,
!     diffServRandomDropClipThreshPkts   Unsigned32,
!     diffServRandomDropProbMax          Unsigned32,
      diffServRandomDropInvWeight        Unsigned32,
      diffServRandomDropSamplingRate     Unsigned32,
+     diffServRandomDropCountStyle       INTEGER,
      diffServRandomDropStatus           RowStatus
  }
***************
*** 3805,3818 ****
      ::= { diffServRandomDropEntry 1 }
  
! diffServRandomDropMinThreshBytes OBJECT-TYPE
      SYNTAX       Unsigned32
!     UNITS        "bytes"
      MAX-ACCESS   read-create
      STATUS       current
      DESCRIPTION
!        "The average queue depth in bytes, beyond which traffic has a
!        non-zero probability of being dropped.  Changes in this variable
!        may or may not be reflected in the reported value of
!        diffServRandomDropMinThreshPkts."
      ::= { diffServRandomDropEntry 2 }
  
--- 3811,3824 ----
      ::= { diffServRandomDropEntry 1 }
  
! diffServRandomDropMinThreshOctets OBJECT-TYPE
      SYNTAX       Unsigned32
!     UNITS        "octets"
      MAX-ACCESS   read-create
      STATUS       current
      DESCRIPTION
!        "The average queue depth, in octets, beyond which traffic has a
!        non-zero probability of being dropped.  The value of this
!        variable is only relevant if diffServRandomDropCountStyle is
!        octets(1)."
      ::= { diffServRandomDropEntry 2 }
  
***************
*** 3823,3835 ****
      STATUS       current
      DESCRIPTION
!        "The average queue depth in packets, beyond which traffic has a
         non-zero probability of being dropped.  Changes in this variable
         may or may not be reflected in the reported value of
!        diffServRandomDropMinThreshBytes."
      ::= { diffServRandomDropEntry 3 }
  
! diffServRandomDropMaxThreshBytes OBJECT-TYPE
      SYNTAX       Unsigned32
!     UNITS        "bytes"
      MAX-ACCESS   read-create
  
--- 3829,3842 ----
      STATUS       current
      DESCRIPTION
!        "The average queue depth, in packets, beyond which traffic has a
         non-zero probability of being dropped.  Changes in this variable
         may or may not be reflected in the reported value of
!        diffServRandomDropMinThreshOctets.  The value of this variable is
!        only relevant if diffServRandomDropCountStyle is packets(2)."
      ::= { diffServRandomDropEntry 3 }
  
! diffServRandomDropMaxThreshOctets OBJECT-TYPE
      SYNTAX       Unsigned32
!     UNITS        "octets"
      MAX-ACCESS   read-create
  
***************
*** 3848,3857 ****
      STATUS       current
      DESCRIPTION
!        "The average queue depth beyond which traffic has a probability
         indicated by diffServRandomDropProbMax of being dropped or
!        marked. Note that this differs from the physical queue limit,
!        which is stored in diffServAlgDropQThreshold.  Changes in this
!        variable may or may not be reflected in the reported value of
!        diffServRandomDropMaxThreshPkts."
      ::= { diffServRandomDropEntry 4 }
  
--- 3855,3862 ----
      STATUS       current
      DESCRIPTION
!        "The average queue depth at which traffic has a probability
         indicated by diffServRandomDropProbMax of being dropped or
!        marked.  The value of this variable is only relevant if
!        diffServRandomDropCountStyle is octets(1)."
      ::= { diffServRandomDropEntry 4 }
  
***************
*** 3862,3874 ****
      STATUS       current
      DESCRIPTION
!        "The average queue depth beyond which traffic has a probability
         indicated by diffServRandomDropProbMax of being dropped or
!        marked. Note that this differs from the physical queue limit,
!        which is stored in diffServAlgDropQThreshold.  Changes in this
!        variable may or may not be reflected in the reported value of
!        diffServRandomDropMaxThreshBytes."
      ::= { diffServRandomDropEntry 5 }

  diffServRandomDropProbMax OBJECT-TYPE
      SYNTAX       Unsigned32
--- 3867,3904 ----
      STATUS       current
      DESCRIPTION
!        "The average queue depth at which traffic has a probability
         indicated by diffServRandomDropProbMax of being dropped or
!        marked.  The value of this variable is only relevant if
!        diffServRandomDropCountStyle is packets(2)."
      ::= { diffServRandomDropEntry 5 }

+ diffServRandomDropClipThreshOctets OBJECT-TYPE
+     SYNTAX       Unsigned32
+     UNITS        "octets"
+     MAX-ACCESS   read-create
+     STATUS       current
+     DESCRIPTION
+        "The average queue depth beyond which all traffic will be dropped
+        or marked.  The value of this variable is only relevant if
+        diffServRandomDropCountStyle is octets(1).  Note that this
+        differs from the physical queue limit, which is stored in
+        diffServAlgDropQThreshold."
+     ::= { diffServRandomDropEntry 6 }
+ 
+ diffServRandomDropClipThreshPkts OBJECT-TYPE
+     SYNTAX       Unsigned32
+     UNITS        "packets"
+     MAX-ACCESS   read-create
+     STATUS       current
+     DESCRIPTION
+        "The average queue depth beyond which all traffic will be dropped
+        or marked.  The value of this variable is only relevant if
+        diffServRandomDropCountStyle is packets(2).  Note that this
+        differs from the physical queue limit, which is stored in
+        diffServAlgDropQThreshold."
+     ::= { diffServRandomDropEntry 7 }
+ 
+ 
  diffServRandomDropProbMax OBJECT-TYPE
      SYNTAX       Unsigned32
***************
*** 3883,3887 ****
         case one percent (1%) of traffic may be dropped, it has the value
         10."
!    ::= { diffServRandomDropEntry 6 }
  
  diffServRandomDropInvWeight OBJECT-TYPE
--- 3913,3917 ----
         case one percent (1%) of traffic may be dropped, it has the value
         10."
!    ::= { diffServRandomDropEntry 8 }
  
  diffServRandomDropInvWeight OBJECT-TYPE
***************
*** 3911,3915 ****
         Implementations may choose to limit the acceptable set of values
         to a specified set, such as powers of 2."
!     ::= { diffServRandomDropEntry 7 }
  
  diffServRandomDropSamplingRate OBJECT-TYPE
--- 3941,3945 ----
         Implementations may choose to limit the acceptable set of values
         to a specified set, such as powers of 2."
!     ::= { diffServRandomDropEntry 9 }
  
  diffServRandomDropSamplingRate OBJECT-TYPE
***************
*** 3921,3925 ****
         average calculation.  A value of zero means the queue is sampled
         approximately each time a packet is enqueued (or dequeued)."
!     ::= { diffServRandomDropEntry 8 }
  
  diffServRandomDropStatus OBJECT-TYPE
--- 3951,3966 ----
         average calculation.  A value of zero means the queue is sampled
         approximately each time a packet is enqueued (or dequeued)."
!     ::= { diffServRandomDropEntry 10 }
! 
! diffServRandomCountStyle OBJECT-TYPE
!     SYNTAX  INTEGER {
!                 octets(1),
!                 packets(2)
!     }
!     MAX-ACCESS   read-create
!     STATUS       current
!     DESCRIPTION
!        "The unit in which the monitored queue is measured."
!     ::= { diffServRandomDropEntry 11 }
  
  diffServRandomDropStatus OBJECT-TYPE
***************
*** 3931,3935 ****
         deletion of this entry. Any writable variable may be modified
         whether the row is active or notInService."
!     ::= { diffServRandomDropEntry 9 }

--- 3972,3976 ----
         deletion of this entry. Any writable variable may be modified
         whether the row is active or notInService."
!     ::= { diffServRandomDropEntry 12 }

***************
*** 4873,4881 ****
  diffServShapingRateThreshold OBJECT-TYPE
      SYNTAX       BurstSize
!     UNITS        "Bytes"
      MAX-ACCESS   read-create
      STATUS       current
      DESCRIPTION
!        "The number of bytes of queue depth at which the rate of a
         multi-rate scheduler will increase to the next output rate. In
         the last conceptual row for such a shaper, this threshold is
--- 4914,4922 ----
  diffServShapingRateThreshold OBJECT-TYPE
      SYNTAX       BurstSize
!     UNITS        "octets"
      MAX-ACCESS   read-create
      STATUS       current
      DESCRIPTION
!        "The number of octets of queue depth at which the rate of a
         multi-rate scheduler will increase to the next output rate. In
         the last conceptual row for such a shaper, this threshold is
***************
*** 5261,5265 ****
         "Write access is not required."
  
!     OBJECT diffServRandomDropMinThreshBytes
      MIN-ACCESS read-only
      DESCRIPTION
--- 5302,5306 ----
         "Write access is not required."
  
!     OBJECT diffServRandomDropMinThreshOctets
      MIN-ACCESS read-only
      DESCRIPTION
***************
*** 5271,5275 ****
         "Write access is not required."
  
!     OBJECT diffServRandomDropMaxThreshBytes
      MIN-ACCESS read-only
  
--- 5312,5316 ----
         "Write access is not required."
  
!     OBJECT diffServRandomDropMaxThreshOctets
      MIN-ACCESS read-only
  
***************
*** 5294,5297 ****
--- 5335,5348 ----
         "Write access is not required."
  
+     OBJECT diffServRandomDropClipThreshOctets
+     MIN-ACCESS read-only
+     DESCRIPTION
+        "Write access is not required."
+ 
+     OBJECT diffServRandomDropClipThreshPkts
+     MIN-ACCESS read-only
+     DESCRIPTION
+        "Write access is not required."
+ 
      OBJECT diffServRandomDropProbMax
      MIN-ACCESS read-only
***************
*** 5314,5317 ****
--- 5365,5373 ----
         "Write access is not required."
  
+     OBJECT diffServRandomDropCountStyle
+     MIN-ACCESS read-only
+     DESCRIPTION
+        "Write access is not required."
+ 
      OBJECT diffServQNext
      MIN-ACCESS read-only
***************
*** 5657,5667 ****
  diffServMIBRandomDropGroup OBJECT-GROUP
      OBJECTS {
!         diffServRandomDropMinThreshBytes,
          diffServRandomDropMinThreshPkts,
!         diffServRandomDropMaxThreshBytes,
          diffServRandomDropMaxThreshPkts,
          diffServRandomDropProbMax,
          diffServRandomDropInvWeight,
          diffServRandomDropSamplingRate,
          diffServRandomDropStatus
      }
--- 5713,5726 ----
  diffServMIBRandomDropGroup OBJECT-GROUP
      OBJECTS {
!         diffServRandomDropMinThreshOctets,
          diffServRandomDropMinThreshPkts,
!         diffServRandomDropMaxThreshOctets,
          diffServRandomDropMaxThreshPkts,
+         diffServRandomDropClipThreshOctets,
+         diffServRandomDropClipThreshPkts,
          diffServRandomDropProbMax,
          diffServRandomDropInvWeight,
          diffServRandomDropSamplingRate,
+         diffServRandomDropCountStyle,
          diffServRandomDropStatus
      }