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

From: "Nabil Seddigh" <[email-masked]>
Date: Thu, 01 Jun 2000 05:47:00 -0400

Fred,

I think the proposal addresses some of the RED-support
issues and is headed in the right direction. I have a 
few comments.

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

Can we extend the above with:

DiffServRandomDropEntry ::= SEQUENCE  {
     ....
     diffServRandomDropSpecific OBJECT IDENTIFIER,
     ....
}

diffServRandomDropSpecific OBJECT-TYPE
     SYNTAX       OBJECT IDENTIFIER
     MAX-ACCESS   read-create
     STATUS       current
     DESCRIPTION
        "Points to a table defined elsewhere that allows
         specification of vendor-specific parameters 
         and monitoring of various algorithm
         statistics."
     ::= { diffServRandomDropEntry 5 }

This would facilitate specification of vendor-specific
parameters and graceful evolvement of the MIB 
to support "new" RED parameters. In addition, 
folks wanting to provide monitoring support
for Q averages can include it here :)

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

Suggest rewording the above description along following lines:

DESCRIPTION
   "The average queue depth beyond which traffic has a
    non-zero probability of being dropped or marked"

I suggest the simplification because I wasn't comfortable
with the term "action" and the explanation of which
set of packets this threshold is applied against. As
I rewrote, it simply became longer and longer. Also,
I'm not sure minth (Qmin) is the "target".
Below minth we have no drops. Non-ECN enabled TCP 
requires pkt drops. So we actually want to operate
above Qmin. Can we get away with the simplification?

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

Another rewording suggestion for the DESCRIPTION:

DESCRIPTION:
   "The threshold that provides primary notification of
    a severe congestion level. If the average queue depth 
    exceeds this amount, the current rate of random dropping
    has not been successful in reducing congestion. 
    Beyond this threshold, either 100% of packets are 
    dropped or the packet drop probability is increased
    at a faster rate"

> 
> diffServRandomDropAvgInterval OBJECT-TYPE
>     SYNTAX       Unsigned32

I've seen some exchange between you and Andrew re:
this value. I would also prefer the "weight" to be
specified. That being said, the RED implementations
based on time-sampled queues probably prefer specification
of an Interval while implementations based on per-pkt
samples probably prefer specification of the 
weight. I'm not sure we can assume that 
one factor can be easily translated into the other. 
Can we provide both in the MIB? 

Andrew had earlier asked for a definition of "weight".
I'm not the best wordsmith but how is the following
attempt?

diffServRandomDropWeight OBJECT-TYPE
    SYNTAX       Unsigned32
    MAX-ACCESS   read-create
    STATUS       current
    DESCRIPTION
       "The weighting of past history in affecting the
        calculation of the current queue average. This 
        value is an exponent, the inverse of which can
        be used to calculate the actual weighting factor"
    ::= { diffServRandomDropEntry ? }

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

Seems like Pmax (as defined in RED-93 and Pg 7 of the
current MIB), can be obtained by inverting the above. 
Is that correct? If so, that's great! Am not quite 
comfortable with some of the "must" and "most" in the 
above. Would suggest some rewording along the following:

DESCRIPTION:
"An inverse of the drop probability when the average 
 queue size approaches diffServRandomDropMaxThreshold.
 This value is a reflected estimate of the number
 of packets forwarded between successive dropping
 or marking events. The number zero implies 
 that all packets are subject to drop; the number 99 indicates 
 that when the average queue size approaches 
 diffServRandomDropMaxThreshold roughly 1% of the 
 packets are dropped, as between any two dropped packets
 99 packets are forwarded."

I guess I'm happy with the 4-parameter RED as a start.

> At the end of the document, we need an appropriate 
>reference to RED93, and
> probably some subset of the papers that proceed from it.

Which papers?

Best,

-----
Nabil Seddigh
[email-masked]

_______________________________________________
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: Thu, 01 Jun 2000 11:21:07 -0700

>      diffServRandomDropSpecific OBJECT IDENTIFIER,

I'm not fundamentally opposed, but I do find myself wondering: why not just 
define:

vendorRandomDropEntry OBJECT-TYPE
      SYNTAX       VendorRandomDropEntry
      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 }

VendorRandomDropEntry ::= SEQUENCE  {
      whatever
  }

and identify that whenever your favorite vendor's equipment generates a 
diffServRandomDropEntry, it will also generate a vendorRandomDropEntry with 
the same index parameters? The vendor definition then becomes in some sense 
an extension of the standard parameters.

>above Qmin. Can we get away with the simplification?

Almost, except I am concerned about two things.

First, is Walter OK with this? As I understand it, his favorite algorithm 
isn't as well described. If he buys off, I'll fold.

Second, actually min-threshold is in effect a target queue depth. I'd like 
you to take a quick gander at three studies:

ftp://ftpeng.cisco.com/fred/diffserv/pingsfifo16.gif
ftp://ftpeng.cisco.com/fred/diffserv/std-red16.gif
ftp://ftpeng.cisco.com/fred/diffserv/fred-red16.gif

In each case, I configured the router in a lab with a set of parameters, 
opened up a "ping -s" to a machine at the plant in order to generate 
timings that I could easily graph, and then ran a succession of FTP file 
transfers between two Solaris boxes. The file being transferred was large 
enough to take about 30 seconds at the ambient line rate (2 MBPS). 
Successive waves of traffic carried one, two, three, ..., fourteen, or 
fifteen file transfers in parallel, started on five second intervals. If 
you look carefully, you can see something of a step function as the 
successive file transfers start and stop within each set. The "ping -s" in 
effect measures the queue depth. There is nothing magic about these numbers 
other than that with less than four simultaneous transfers one would expect 
minimal drops, due to the specific configuration, and when we get above ten 
or twelve the TCPs are driven into a state where no fast-recovery actions 
can happen - all recovery is done by time-outs. In between, TCP operates in 
its preferred manner.

OK, so then I did a simple data smoothing operation. I ran along the graph, 
for each set of four successive pings, four lines: min(set of ten numbers), 
max(set of ten numbers), average(set of ten numbers), and stdev(set of ten 
numbers).

The queue depth for the FIFO Tail Drop case, as you might expect, 
approximates the physical size of the queue.

The mean queue depth for each of the RED tests approximates min-threshold 
once we have to start dropping something. What tends to happen is that the 
TCPs build up to where the mean queue depth exceeds min-threshold, we drop 
a few things, the TCPs back off, we don't drop anything momentarily, the 
TCPs build up again... The difference between the two RED tests is that 
"std-red" is a RED93 implementation (shipping code), while the "fred-red" 
test is my prototype of Kathy's "Red-Light". One thing I draw out of 
comparing the two RED tests is that RED93, which has a predictable drop 
rate as the mean queue depth varies from min-threshold to max-threshold, 
appears to have a wider variability than Red-Light, which simply drops 
however many it takes to make sure that we approximate min-threshold. The 
STDEV for RED93 was in the 50-60 milliseconds of delay range, while for 
RED93 it was closer to 25 milliseconds, in the worst case, and was much 
more uniform for REd-Light than for RED93. I commented to the list a while 
back that I was much happier with RED-Light than with RED93; this, along 
with the simpler configuration and implementation, was my reason, long and 
short thereof.

So I will argue rather strongly that min-threshold is indeed a target queue 
depth. Yes, we overshoot the target and draw back to reach it, but that is 
an attribute of a target - if it were a fixed value, we would both describe 
it differently and observe that it behaved differently.

Can we compromise on:

DESCRIPTION
   "The target queue depth, beyond which traffic has a
    non-zero probability of being dropped or marked"

>     dropped or the packet drop probability is increased

s/. Beyond this threshold/; therefore/

otherwise, fine.

>     ::= { diffServRandomDropEntry ? }

is it the inverse of the exponent, or the inverse of the exponentiated 
exponent? I think it would be better to read

"The weighting of past history in affecting the calculation of the current 
queue average using  an exponentially weighted moving average. This value 
is an exponent of two; the factor for the new information is 
1/(2^diffServRandomDropWeight), and the factor for the history term is 
1-1/(2^diffServRandomDropWeight)."

Does that work?

>Is that correct? If so, that's great!

That's the intent, whatever you think of the execution :^).

>  queue size approaches diffServRandomDropMaxThreshold.

That statement is very specific to RED93, which has a defined slope. How 
about "The inverse of the worst case drop probability."?

>  99 packets are forwarded."

This (and my text that it came from) could be argued as being 
implementation specific. Maybe we should just drop it? That does modify the 
algorithm suggested slightly, but perhaps it is a good thing anyway.

I modelled this as "I drop something, I protect the next N packets from 
drops, and then I start deciding whether to randomly drop something, in 
most cases dropping something much later." In that model, the minimum 
number of things I can protect is 0, so N=0 gives me a potential of 100% 
drop probability, and N=99 gives me a 1% drop probability. However, if the 
number is the inverse of the drop probability, a potential drop probability 
of 1 has an inverse of 1, and a potential drop probability of 1% gives me 
an inverse of 100.

Are we precessing in a useful direction?