Subject: RE: [Diffserv] Model - queues - replacement text

From: Andrew Smith <[email-masked]>
Date: Tue, 14 Dec 1999 15:40:30 -0800

Dan,

Some comments on your proposal - I like it (mostly). See [Andrew] below.

> -----Original Message-----
> From: Dan Grossman [mailto:[email-masked]]
> Sent: Tuesday, December 14, 1999 12:44 PM
> To: [email-masked]
> Subject: [Diffserv] Model - queues - replacement text
> 
> 
> All,
> Here is a cut at replacement text, based on the discussion of 
> last week.  I'll 
> be interested to see how well this tracks (or not) the 
> information model that 
> Walter et al were working on.
> 
...
> 
> Note that the term FIFO is overloaded (i.e., has more than 
> one meaning).  In
> common usage it is taken to mean, among other things, a data 
> structure that
> permits items to be removed only in the order in which they 
> were inserted,
> and a service discipline which is non-reordering.  In this 
> model, the former
> context is used except when explicitly noted.

[Andrew] Suggest that we always stick to the former and never use the latter
in this document.

> 7.1.1  FIFO
> A FIFO is a data structure which at any time may contain zero or more 
> packets.  It has a depth, which indicates the number of 
> packets that it
> contains at a particular time.  It may have one or more 
> threshold associated
> with  it.    A FIFO has one or more inputs and exactly one 
> output. It must
> support an enqueue operation to add a packet to the tail of 
> the queue, and a
> dequeue operation to remove a packet from the head of the 
> queue. Packets
> must be dequeued in the order in which they were enqueued.  
> However, this
> does not preclude implementions which support operations on 
> the FIFO data
> structure that remove or examine packets (e.g., for use by 
> discarders), as
> long as no operation reorder packets belonging to the same microflow. 

[Andrew] Suggest we not get into re-ordering issues here to any granularity
less than "per-queue": I think it suffices to say here "this does not
preclude implementions which support operations on the FIFO data structure
that remove or examine packets e.g. for use by discarders. The only
constraint on such operations is that they not add packets back into the
FIFO in a different order."

> In an implementation, packets are presumed to be stored in one or more
> buffer.  Buffers are allocated from one or more free buffer 
> pool.  If there
> are multiple instances of a FIFO, their packet 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, which may affect 
> discarding
> and/or scheduling.  Otherwise, buffering mechanisms are implementation
> specific and not part of this model.
> 
> A FIFO might be represented using the following parameters:
> 	FIFO1:
> 	Type:		FIFO
> 	Input:	Classifier Output A
> 	Output:	Discarder2
> 	Threshold1: 3 packets
> 
> 
> Another FIFO may be represented using the following parameters:
> 	FIFO2:
> 	Type:		FIFO
> 	Input:	Discarder1
> 	Output:	Scheduler1
> 	Threshold1: 3 packets
> 	Threshold2: 100 packets
> 	Threshold3: 10 packets
> 	Threshold4: 200 packets

[Andrew] It might be worth changing one of the example thresholds to be,
say, "1000 bytes". Just to show that thresholds are not necessarily measured
in packets always.

> 7.1.2 Scheduler
...			
> 7.1.3 Discarder
> A discarder 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.  In this model (but not 
> necessarily in a 
> real implementation), a packet enters the discarder at the input, and 
> either its buffer is returned to a free buffer pool or it exits the
> discarder at the output. 
> 
> Alternatively, a discarder may invoke operations on a FIFO 
> which selectively
> remove packets, then return those packets to the free buffer 
> pool, based on
> a discarding discipline.  In this case, the discarder has no inputs or
> outputs.  

[Andrew] I find this last paragraph a bit confusing where it says that the
thing has no inputs and no outputs! Maybe we could say that this type of
discarder has as its input a sort of random-access capability into the
upstream packet source (and no outputs)? BTW, the upstream source does not
necessarily have to be a FIFO does it?

> A discarder has a trigger that causes the discarder to make a 
> decision 
> whether or not to drop one (or possibly more than one) packet.  The 
> trigger may internal (i.e., the arrival of a packet at the 
> input to the 
> discarder), or it may be external (i.e., resulting from one or more 
> state change at another element, such as a FIFO depth exceeding a 
> threshold or a scheduling event).  A trigger may be a boolean 
> combination of events (e.g., a FIFO depth exceeding a threshold OR a 
> buffer pool depth falling below a threshold).
>  
> The discarding discipline is an algorithm which makes a decision to 
> forward or discard a packet.  It takes as its parameters some set of 
> dynamic parameters (e.g., averaged or instantaneous FIFO 
> depth) and some 
> set of static parameters (e.g. thresholds) and possibly parameters 
> associated with the packet (e.g. its DSCP). It may also have internal 
> state. RED, RIO, and drop-on-threhold are examples of a discarding
> discipline.  Tail dropping and head dropping are effected by 
> the location of
> the discarder relative to the FIFO.
>
> A discarder might be represented using the following parameters:
> 	Discarder1:
> 	Type:			Discarder
> 	Trigger:		Internal
> 	Input:  		Classifier.outputB
> 	Output:	        	FIFO1
> 	Discipline:		RIO
> 
> 	Parameters:
> 	In-MinTh:		FIFO1.Threshold1
> 	In-MaxTh:		FIFO1.Threshold2
> 	Out-Minth:		FIFO1.Threshold3
> 	Out-Maxth:		FIFO1.Threshold4
> 	In-mark:		AFx1
> 	Out-mark:		AFx2
> 	W_q			.002
> 	Max_p			.01

[Andrew] Is it really necessary to allow another classifier in at this
point? ("parameters associated with the packet" implies a classifier here).
If so, can't we re-use the classifier definition from section 4 instead of
inventing a new (DSCP-specific) one here? I think I'm saying that I don't
like the In-mark and Out-mark included here - we've got remarkers already
defined in section 6.1.
 
> Another discarder might be represented using the following parameters:
> 	Discarder2:
> 	Type:			Discarder
> 	Trigger:		
> 	Input:			FIFO2
> 	Output:			Scheduler1.input1
> 	Discipline:		Drop-on-threshold
> 
> 	Parameters:
> 	Threshold		FIFO2.Threshold1
> 
> Yet another discarder (not part of the example) might be represented 
> with the following parameters:
> 	Discarder3:
> 	Type:			Discarder
> 	Trigger:		FIFO3.depth > 100 packets
> 	Discipline:		Drop-all-out-packets
> 
> 	Parameters:	
> 	Out-mark:		AFx2 | AFx3
> 	
> 
> 
> 7.1.4 Constructing queues from the elements
> A queue is constructed by concatenation of these elements so 
> as to meet the
> meta-policy objectives of the implementation.  Elements of 
> the same type may

[Andrew] Need to define what you mean by "meta-policy". Or else choose
different words.
 
> appear more than once in a queue, either in parallel or in 
> series.  The
> following connections are allowed:
> 
> 		The input of a FIFO may be the input of the 
> queue, or it may
> 		be connected to the output of a discarder or to 
> an output of a 			scheduler. 
>   
> 		Each input of a scheduler may be connected to 
> the output of
> 		a queue or to the output of another scheduler.  

[Andrew] Do you mean "may be connected to the output of a *FIFO*"? (I assume
so below).

> 		The input of a discarder  may be the input of the
> 		queue, or it may be connected to the output of 
> a FIFO (e.g., 			head 
> dropping).
> 
> 		The output of the queueing  may be the output of a
> 		FIFO element, a discarding element or a 
> scheduling element.   

[Andrew] I find this description confusing (backwards?). But I could not
find a formulation using go-to rather than come-from links ("the output of A
may go to the input of B") that has the same effect as your rules. Your
rules raise some questions in my mind: (1) do we need to be able to have a
Scheduler feed into a FIFO? (2) does a queue ever need to contain more than
one FIFO or discarder? (3) do we need to have queues be concatenated? (4)
don't we also need to be able to go Fifo->Discarder->Scheduler? I came up
with this formulation of your rules:

QueueDan ::= Fifo |
           Fifo Discarder |
           Fifo Scheduler* |
           Fifo Scheduler* Fifo |
           Discarder |
           Discarder Fifo |
           Discarder Fifo Discarder |
           Discarder Fifo Scheduler* |
           Discarder Fifo Scheduler* Fifo   (this starts to recurse ...)
+ etc. ad nauseum

If the answer to (4) is yes and we handle the recursion thing by making you
have multiple concatenated Queue blocks, I think we can use a simpler rule
like the following:

QueueAndrew ::= Fifo |
          Fifo Discarder | 
          Fifo Scheduler* | 
          Fifo Discarder Scheduler*  |
          Discarder |
          Discarder Fifo |
          Discarder Fifo Scheduler*

But I'm not sure it's any clearer than the words - probably not. Maybe a
picture with arrows would help (or not):
                    +-------------->+
                    |               |
Queue---+--->Fifo---+-->Discarder-->+-+->+-->Scheduler-->+-->+-->Queue
 In     |                             |  |               |   |    Out
        |                             |  +<--------------+   |
        |                             |                      |
        +-->Discarder-->+-->Fifo----->+-->+----------------->+
                        |                 |
                        +---------------->+

I think this meets the requirements.

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

I think this one might best be modelled by concatenating 2 queue blocks,
rather than recursing inside the queue block. Just a thought.

Andrew

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

---

From: Dan Grossman <[email-masked]>
Date: Tue, 14 Dec 1999 18:49:10 -0500

Andrew and Linsong,
Thanks for the comments.  I'm stuck on jury duty tomorrow, and will get back 
to you as soon as I can.
rgds
Dan

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 15 Dec 1999 09:45:36 -0600

Andrew Smith wrote:
...
> FIFO in a different order."

Well, some months back we had implementors *insisting* on the per-microflow
language rather than per-queue, so that the diffserv model would
be compatible with MF-classifier based ASICs. I think that was for the
specific case of AF, but I suspect the argument is generic.

   Brian

---

From: Dan Grossman <[email-masked]>
Date: Wed, 15 Dec 1999 18:07:17 -0500

Andrew, 
Comments inline.  Mostly agree.
> [Andrew] Suggest that we always stick to the former and never use the latter
I thought I might need to to talk about a FIFO scheduling discipline.  It 
doesn't seem necessary, and somebody suggested FCFS if it were to become so.  
So, agreed.

> FIFO in a different order."
See discussion with Brian.
> say, "1000 bytes". Just to show that thresholds are not necessarily measured
Can do.  Would probably want to make that units on one fifo in bytes, the 
other in packets.

> necessarily have to be a FIFO does it?
I'll try to think of some better wording.  

> like the In-mark and Out-mark included here - we've got remarkers already

Two things seem to have gotten confused here.  The "Classifier.outputB" 
parameter was an attempt to show that the input to the discarder is also the 
input to the queueing system, and is fed by the output of the classifier.  I'm 
not completely happy with this model, and would welcome suggestions.

The In-mark and Out-mark parameters are an attempt to model RIO;  that is, 
start probabilistically discarding packets marked as AFx1 when average queue 
depth exceeds In-Minth, and start probabilistically discarding packets marked 
as AFx2 when average queue depth exceeds Out-Minth.  Maybe some additional 
words are needed?
> [Andrew] Need to define what you mean by "meta-policy". Or else choose
Can do that.  What I meant was that policy objectives are presumed to be 
installed by/retrieved from policy management machinery.  However, 
implemention decisions form a meta-policy (policy for making policies) that 
scope the kinds of policies that can be created.

> [Andrew] Do you mean "may be connected to the output of a *FIFO*"? (I assume
Yes.  Ooops.  Thanks. <blush>

> may go to the input of B") that has the same effect as your rules.
I hadn't thought about that...  could be.
> Your
> Scheduler feed into a FIFO?
Possibly.  For example, we feed a non-work conserving scheduler into a FIFO, 
and then into a work conserving scheduler.
 (2) does a queue ever need to contain more than
> one FIFO or discarder? 
Lots of them in parallel.  Possibly multiples in series, particularly in a DS 
edge router, where we need to aggregate microflows.

(3) do we need to have queues be concatenated? 
I can't think of a reason to do this.

>(4)
Yes.  I thought the rules covered that.

>            Discarder Fifo Scheduler* Fifo   (this starts to recurse ...)
There has to be at least one FIFO, one discarder and one scheduler.

Also, it's not intended to recurse (not that again! :-)) or even iterate, but 
rather repeat a small number of times.

Definitely need more words to that effect.  

> But I'm not sure it's any clearer than the words - probably not.
Not.  And not quite correct.  But good try.
> Maybe a
Except if there is a FIFO and/or a discarder between two schedulers. (I think)
> rather than recursing inside the queue block. Just a thought.
I'm not sure how you'd do what I'm proposing here by two separate queue blocks.
Dan