Subject: [Diffserv] Model draft - model for algorithmic droppers

From: Andrew Smith <[email-masked]>
Date: Tue, 05 Dec 2000 12:11:05 -0800

This is a proposal for a solution to the first issue in my previous message.
Ref: http://www.ietf.org/internet-drafts/draft-ietf-diffserv-model-05.txt

1. Model for Algorithmic Droppers

The current figure 5 was put in at the last minute for draft-04 but I don't 
think it is as intuitive as the one I'd earlier proposed. In particular, the 
current figure 5 shows an AD as something that sits on the side of a main 
datapath performing its job by influencing a queue. I prefer the formulation 
that places an AD in-line, either before or after a queue: keeping it as is 
leads to quite a few awkward fixups and explanations throughout the document 
(this is the only case where we have an element "on the side of" a datapath so 
there are a bunch of "exception" cases to describe it). My original depiction of 
an AD doing tail-drop was:

            +------------------+      +-----------+
            | +-------+        |  n   |smoothing  |
            | |trigger|<----------/---|function(s)|
            | |calc.  |        |      |(optional) |
            | +-------+        |      +-----------+
            |     |            |          ^
            |     v            |          |Depth
   Input    | +-------+ no     |      ------------+   to Scheduler
   ---------->|discard|-------------->    |x|x|x|x|------->
            | |   ?   |        |      ------------+
            | +-------+        |           FIFO
            |    |yes          |
            |  | | |           |
            |  | v | count +   |
            |  +---+ bit-bucket|
            +------------------+
            Algorithmic
            Dropper

For head-drop the AD would be placed after the FIFO queue in the model. However, 
this simplified picture has a couple of shortcomings:
a) it cannot represent "middle drop" or "drop a random packet from the FIFO" 
scenarios.
b) it cannot easily be extended to do things other than "drop" e.g. to do 
something like ECN marking you would have to duplicate the AD with a different 
type of element (i.e. create an "Algorithmic Marker" element), rather than 
extending the base element type. Note: this is outside current scope.

Someone (was it Walter or Grenville?) proposed that the "correct" solution here 
is to explode the AD element into its component parts:
    i) a packet selector algorithm that indicates on which packet we are going 
to act (the one we're adding to the tail? one chosen at random from within the 
queue? the one at the head of the queue?).
    ii) a trigger algorithm: whether we are actually going to do anything to the 
packet (this is where the R in "RED" comes in: you select Random packets for 
dropping by running a probability algorithm on the packet you are just adding to 
the tail of the queue).
    iii) an action e.g. "drop it", "ECN-mark it" (this could re-use the "Action" 
elements from elsewhere in the Model)
    iv) optional smoothing function(s) - could be 1 or n per-queue, could be 1 
or m per-dropper. Suggest we leave this outside the discussion for now.

My proposal would be that we:
- explode the AD, somewhat more explicitly than we do now, into the above blocks.
- keep the Algorithmic Dropper element but give it some internal structure in 
the draft's text (explicitly endorsing a substructure that is just implicit in 
the figure right now).
- describe only head- and tail- packet selection, by examples and in figure 
(i.e. put the AD element back "in-line" in the data path: element placed either 
before or after the FIFO queue to indicate head or tail).
- describe only "apply probability algorithm" trigger by example.
- allow for external Action element ("drop it" as the only example).
- keep the smoothing function stuff external.

The example diagram (for a tail dropper), replacing current figure 5, would then be:

         +----------------+    +-----------+
         |  +-------+     | n  |smoothing  |
         |  |trigger|<------/--|function(s)|
         |  |alg.   |     |    |(optional) |
         |  +-------+     |    +-----------+
         |      |         |       ^
         |      v         |       |Depth
   Input |  +-------+ no  |   ------------+  to next
---------->|action |-----------> |x|x|x|x|------->
         |  |   ?   |     |   ------------+  e.g. Scheduler
         |  +-------+     |      FIFO
         +------|---------+
   Algorithmic  |yes
   Dropper      v
             +------+
             |Next  |e.g. AbsDrop,Mark
             |Action|
             +------+

This still leaves the problem of the name: everybody seems to complain about 
"Algorithmic Dropper" but nobody has/had a better name. And now it can do things 
other than Drop. How about "Algorithmic", "Algorithmic Element", "Algorithmic 
Trigger", "Trigger Condition", "Trigger Element" or "Trigger Action"? Vote early 
and often (assuming you like the proposed revision of course).

Andrew Smith
(editor of this draft)

_______________________________________________
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