[Diffserv] Model - queues

[Dan Grossman <dan@xxxxxxxxxxxxxxxxxxxx>]

All,
I had an action item out of the Washington meeting to come up with a more 
general model of queueing in the DS model draft.  Before I try to propose text 
for the draft, I'd like to have some discussion on the list of the following 
concepts:

A queuing element is composed of one or more FIFO element, one or more 
scheduling element, and possibly one or more discarding element. [I was 
thinking about making the buffer data structure more general than 'FIFO' but 
decided not to for lack of a reason why one would need another data structure 
-- can anybody think of one?]

A FIFO element is a data structure which at any time may contain zero or more 
buffers.  It has a depth, and may have one or more threshold associated with 
it.  If there are multiple instances of a FIFO element, their buffers may or 
may not be allocated out of the same free buffer pool.  Free buffer pools may 
also have one or more threshold associated with them.  A FIFO element has one 
or more inputs and exactly one output.

A scheduling element is a functional element which gates the departure of each 
packet that arrives at one of its inputs,  based on a service discipline.  It 
has more than one [?] input and exactly one output.   The service discipline 
is an algorithm which may take as its inputs fixed parameters (such as 
relative priority, relative weighting and/or absolute token bucket parameters 
for maximum or minimum rates) associated with each of its inputs; parameters 
(such as packet length or DSCP [?]) associated with the packet present at its 
input; absolute time and/or local state.  Service disciplines may be work 
conserving or non-work conserving.

A discarding element is a functional element which selectively discards 
packets that arrive at its input, based on a discarding discipline.  It has 
one input and one output.  The discarding discipline is an algorithm which 
takes as its parameters some set of dynamic parameters (such as averaged FIFO 
depth) and some set of fixed parameters (such as  queue depth or free buffer 
pool thresholds) and possibly parameters associated with the packet (e.g. its 
DSCP).  RED is an example of a discarding discipline.

A queueing element is thus constructed by concatenation of these elements so 
as to meet meta-policy [I don't think we've discussed this, but it makes a lot 
of sense] objectives.  The input of a FIFO element may be the input of the 
queuing element, or it may be connected to the output of a discarding element 
or to an output of a scheduling element.  An input of a scheduling element may 
be connected to the output of a queuing element or of another scheduling 
element.  The input of a discarding element may be the input of the queueing 
element, or it may be connected to the output of a FIFO element (e.g., head 
dropping).  The output of the queueing element may be the output of a FIFO 
element, a discarding element or a scheduling element. [are there other 
reasonable concatenations from input to output?].  

Note, in particular, that scheduling elements may operate in series such that 
a packet at the head of a queue feeding the concatenated scheduling elements 
is serviced only after all of the scheduling criteria are met.  For example, 
EF traffic streams may be served first by a non-work conserving scheduler to 
achieve limit maximum rate, then mixed with other traffic streams by a work 
conserving scheduler.  Alternatively, there might be a FIFO element and/or a 
discarding element between the two schedulers.

[All of which begs for a picture, which would be a horror show to do in ASCII 
art. But since Yoram et al set such a fine example, I suppose I'd have to 
break down and do it once we got closure on the principles.]

Comments?

Dan


_______________________________________________
diffserv mailing list
diffserv@ietf.org
http://www.ietf.org/mailman/listinfo/diffserv
Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/