Subject: RE: [Diffserv] Proposal for Diffserv MIB - droppers

From: Andrew Smith <[email-masked]>
Date: Wed, 31 May 2000 15:15:37 -0700

Fred,

Thanks for that concrete proposal. I agree with it in general and it fits
nicely in the current (-03) structures; just a couple of specifics, please
see below.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Tuesday, May 30, 2000 6:09 PM
> To: [email-masked]
> Subject: [Diffserv] Proposal for Diffserv MIB - droppers 
... 
> decision reached on the list: apparently we do need this option.
> <(21) Do we need diffServAlgDropType of both "headDrop" and 
> "tailDrop" or
> <     should we just represent the tail dropper by placing a dropper
> <     after the queue instead of before the queue, as linked by the
> <     diffServQNext and diffServAlgDropNext RowPointers? (the former).

[Andrew] I assume you mean "the former" and that we do *not* need to be
allowed to place droppers after the queue in the plumbing diagram, right?

...
> Add this text to diffServAlgDropType:
> diffServRandomDropType OBJECT-TYPE

[Andrew] Nit: above should be "diffServAlgDropType"

>     SYNTAX       INTEGER { other(1),
> 			   tailDrop(2),
> 			   headDrop(3),
> >			   randomDrop(4)
> 			 }
>     MAX-ACCESS   read-create
>     STATUS       current
>     DESCRIPTION
>        "The type of algorithm used by this dropper. A value of
>        tailDrop(2) or headDrop(3) represents an algorithm that is
>        completely specified by this MIB.  A value of other(1) requires
>        further specification in some other MIB module.
> 
>        The tailDrop(2) algorithm is described as follows:
>        diffServRandomDropQThreshold represents the depth of the queue
>        diffServRandomDropQMeasure at which all newly arriving 
> packets will
>        be dropped.
>
>        The headDrop(3) algorithm is described as follows: if a packet
>        arrives when the current depth of the queue
>        diffServRandomDropQMeasure is at 
> diffServRandomDropQThreshold, the
>        packet currently at the head of the queue is dropped 
> and the new
>        packet is enqueued at the tail of the queue.

[Andrew] Nit: replace "diffServRandomDrop" by "diffServAlgDrop" everywhere
in the above 2 paragraphs.

> >       The randomDrop algorithm is described as follows: on packet
> >       arrival, an algorithm is executed which may randomly 
> drop it, or
> >       drop another packet from the queue in its place. The specifics
> >       of the algorithm may be proprietary. In this case, a
> >       diffServRandomDropEntry is pointed to by 
> diffServAlgDropSpecific,
> >       diffServAlgQThreshold is understood to be the absolute maximum
> >       size of the queue, and additional parameters beyond 
> those in the
> >       diffServRandomDropTable may be found in a 
> vendor-specific MIB."
>     ::= { diffServRandomDropEntry 3 }

[Andrew] Not sure of the difference between diffServAlg(Drop)QThreshold in
the above description and diffServRandomDropMaxThreshold in the table below.
Please clarify.

> 
> New Text:
> 
> diffServRandomDropTable OBJECT-TYPE
>     SYNTAX       SEQUENCE OF DiffServRandomDropEntry
>     MAX-ACCESS   not-accessible
>     STATUS       current
>     DESCRIPTION
>        "The random drop table augments the algorithmic drop table. 
>        It contains entries describing a process that drops packets
>        randomly. It is pointed to by diffServAlgDropSpecific in such
>        cases."
>     REFERENCE
>         "[MODEL] section 7.1.3"
>     ::= { diffServTables ? }
> 
> Just a thought: this could literally AUGMENT {diffServTables 
> 8} using the
> Augments clause if we want it to. Not sure what anyone thinks.

[Andrew] They frown on "sparse augments" usage: elsewhere in this MIB I have
just re-used the same indices for things like this, as you have, and used a
"specific" pointer to point at the base of the table (*not* at a row entry
within the table) - this gives better efficiency of access for read and
create operations, without needing a new IANA registry for extension.

> diffServRandomDropEntry OBJECT-TYPE
>     SYNTAX       DiffServRandomDropEntry
>     MAX-ACCESS   not-accessible
>     STATUS       current
>     DESCRIPTION
>        "An entry describes a process that drops packets according to
>        a random Algorithm."
>     INDEX { ifIndex, diffServAlgDropIfDirection,
>             diffServAlgDropId }
>     ::= { diffServRandomDropTable 1 }
> 
> DiffServRandomDropEntry ::= SEQUENCE  {
>     diffServRandomDropMinThreshold     Unsigned32,
>     diffServRandomDropMaxThreshold     Unsigned32,
>     diffServRandomDropAvgInterval      Unsigned32,
>     diffServRandomDropMinSpace         Unsigned32,
>     diffServRandomDropStatus           RowStatus
> }
> 
> diffServRandomDropMinThreshold OBJECT-TYPE
>     SYNTAX       Unsigned32
>     UNITS        "packets"
>     MAX-ACCESS   read-create
>     STATUS       current
>     DESCRIPTION
>        "The target number of packets to be held in queue. If 
> the average
>        queue depth exceeds this amount, one will expect that traffic
>        exercising this action (which is to say, traffic which 
> either has
>        the indicated DSCP or which will be marked to it as 
> the result of a
>        meter overflowing) has a non-zero probability of being 
> dropped or
>        marked."
>     ::= { diffServRandomDropEntry 1 }

[Andrew] We need a way of indicating which indicated DSCP. This is where we
need a RowPointer to the specific classifier element (or filter element?).
Suggest we add in a new column:

   diffServRandomDropClassifier    RowPointer
      DESCRIPTION "The classification pattern indicating which traffic
        is to receive the drop treatment specified by this drop algorithm."

> diffServRandomDropMaxThreshold OBJECT-TYPE
>     SYNTAX       Unsigned32
>     UNITS        "packets"
>     MAX-ACCESS   read-create
>     STATUS       current
>     DESCRIPTION
>        "The limit number of packets to be held in queue. If 
> the average
>        queue depth exceeds this amount, one one may presume 
> that randomly
>        dropping or marking them has not been successful in 
> reducing the
>        source's rate, and these packets must be dropped."
>     ::= { diffServRandomDropEntry 2 }
> 
>  -- 
>  -- this can be done in many ways. One could, for example, maintain an
>  -- exponentially weighted moving average and put the binary logarithm
>  -- ("k" in 2^k) here, which is what Cisco equipment does. I 
> get lots of
>  -- questions of the form "what is this 'k' thingie for?", and Cisco
>  -- originally refused to put an equation into the manual, 
> claiming that
>  -- this was difficult for customers (read "English majors working in
>  -- tech pubs") to understand. Since Kathy seems to think 
> that an interval
>  -- of milliseconds is about right, I propose we go with that...

[Andrew] **** This is where I think we may be overstepping the mark into
implementation specifics. Fred, you seem here to have moved towards Kwok's
earlier position of including more knobs rather than fewer. I was
comfortable with min/max thresholds and some sort of generalised notion of
"weight" although I was waiting for some sort of definition for the latter. 

Last Friday you wrote (not sure if you have "minp" and "the weight"
interchanged here maybe?):
"So I think I am arguing toward min-threshold and max-threshold, as Kathy
suggested, an exponent to manage the exponential averaging (minp), and if
you like an upper bound on the drop rate (the weight)"

And, before Adelaide, Kathy was proposing something like:
"- Threshold for the averaged queue size below which no packet dropping
takes place (in 93RED this is min_thresh)
- Parameter for that average that controls the history of the averaging: a
filter "gain" or a "queue weight".
- Upper bound to the "controlled range": a value of the filtered or averaged
queue above which 100% of packets are dropped."

Your formulation below seems to stray from the "3-parameter RED" that we'd
talked about before. Are you saying that Interval is equivalent to the
"weight" we'd talked about before? I'm not sure that milliseconds are the
right units for one thing and I thought we'd already agreed that intervals
were not appropriate for implementations that were triggered by packet
events, not timers, no? And I thought Kathy and Van were arguing that maxP
(aka MinSpace) was not appropriate to "better" forms of RED (maybe I
misunderstood what Van was arguing for in Adelaide).

I'd just as soon stick with the 3 parameters using a "weight" not an
"interval". But I'm still struggling to find a definition for "weight" that
is general enough.
****

> diffServRandomDropAvgInterval OBJECT-TYPE
>     SYNTAX       Unsigned32
>     UNITS        "milliseconds"
>     MAX-ACCESS   read-create
>     STATUS       current
>     DESCRIPTION
>        "The number of milliseconds between calculations of 
> the required
>        drop rate, in milliseconds. Presumptively, every so often the
>        drop rate is calibrated, either increasing it due to increased
>        mean queue depth, or decreasing it because previous drops have
>        had the necessary effect."
>     ::= { diffServRandomDropEntry 3 }
> 
> diffServRandomDropMinSpace OBJECT-TYPE
>     SYNTAX       Unsigned32
>     MAX-ACCESS   read-create
>     STATUS       current
>     DESCRIPTION
>        "The minimum number of packets that must be forwarded between
>        successive marking or dropping events. The number zero 
> implies that
>        all packets are subject to drop; the number 99 
> indicates that at
>        most 1% of packets may be dropped, as between any two 
> packets there
>        must be at least 99 packets forwarded. This has the effect of
>        limiting the percentage drop rate to some bound."
>     ::= { diffServRandomDropEntry 4 }
> 
> diffServRandomDropStatus OBJECT-TYPE
>     SYNTAX       RowStatus
>     MAX-ACCESS   read-create
>     STATUS       current
>     DESCRIPTION
>        "The RowStatus variable controls the activation, 
> deactivation, or
>        deletion of this entry. Any writable variable may be modified
>        whether the row is active or notInService."
>     ::= { diffServRandomDropEntry 12 }

[Andrew] I think we can finesse the Status variable out of existence by
saying that these entries appear automatically when a diffServAlgDropEntry
of type randomDrop is created. That is what I'd propose for the
MeterTable/TBMeterTable pair as well.

...

Andrew

_______________________________________________
diffserv mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/diffserv
Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/

---

From: Fred Baker <[email-masked]>
Date: Wed, 31 May 2000 17:29:29 -0700

>allowed to place droppers after the queue in the plumbing diagram, right?

yes, and we do indeed allow for head droppers.

>the above description and diffServRandomDropMaxThreshold in the table below.

In the head/tail drop implementation, QThreshold is the actual size of the 
queue, and if we try to put more packets in it than it will hold, something 
falls on the floor. In the random drop implementation, the queue is 
actually larger than max-threshold; we don't start dropping everything 
until the *mean* queue depth exceeds max-threshold. It is quite possible 
for the instantaneous queue depth to greatly exceed max-threshold, but it 
cannot do so for very long.

So to me, the actual size of the queue and the place you start dropping 
should the mean exceed that are two very different things. You might, for 
example, configure:

         min-threshold[AFx3] = 0
         max-threshold[AFx3] <= min-threshold[AFx2]
         max-threshold[AFx2] <= min-threshold[AFx1]
         max-threshold[AFx1] = half the *actual* storage space available 
for the queue

In fact, I thought I heard someone say he literally wanted to be dropping 
all of AFxN+1 before dropping any of AFxN. Did you hear that desire?

If QThreshold tells me the actual size of the queue, that is potentially 
useful information, and I don't know how to interpret it in the above context.

>need a RowPointer to the specific classifier element (or filter element?).

Why? The classifier (or the meter, and in that AF case you presumably have 
just remarked the packet to the new DSCP) is what got you to this action, 
and is therefore implicit in the fact that you got here. We can add the 
column you propose, but we should add it to the AlgDropEntry, as the same 
question applies there, for tail drop (how did the packet get headed 
towards the queue that is deciding to drop it?). And I think we should not 
add it unless there is a real utility for it.

>talked about before.

Yes, mea culpa. Not that I tried to, but I tried to describe it in a way 
less tied to the moving average definition, and messed it up. I have since 
had some private email with Joel Halpern. The "interval" object I proposed 
is broken - we actually want something that will set the "k" in

                      2^k-1                         current queue depth
   mean queue depth = ----- * mean queue depth   + -------------------
                  i  2^k                    i-1         2^k

as opposed to trying to finesse that.

>"interval". But I'm still struggling to find a definition for "weight" that

weight is the one that follows - it tells us what the greatest possible 
drop rate is.

>MeterTable/TBMeterTable pair as well.

works for me.