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

From: "Larkland Morley" <[email-masked]>
Date: Tue, 14 Dec 1999 16:39:29 -0800

Hello:

Does any vendor offer a protocol decode for COPS-PR..

Regards

Larkland Morley
Nortel Networks

-----Original Message-----
From: Brian E Carpenter [mailto:[email-masked]]
Sent: Tuesday, December 14, 1999 2:49 PM
To: Grenville Armitage
Cc: Dan Grossman; [email-masked]
Subject: Re: [Diffserv] Model - queues - replacement text

Grenville,

Let's be clear that this is a discussion about terminology, and the question
is whether the term "queue" refers only to an ordered data store (your view)
or to an ordered data store plus the engine(s) that act on that store (Dan's
view).

The -01 version of the model draft clearly uses "queue" in the narrow sense
of an ordered data store. The -01 version of the MIB uses it in the broader
sense of store + engines. So we do have to resolve this; Dan's text aligns
the model with the MIB, but one of the documents has to change anyway..

   Brian

Grenville Armitage wrote:
> 
> Dan,
> 
>         [..]
> > Queues perform three distinct, but related, functions:  they store
packets,
> > they modulate the departure of packets belonging to various traffic
streams
> > and they selectively discard packets.  This model decomposes queues into
the
> > component elements that perform each of these functions.
> 
> I disagree fundamentally with this description.
> 
> Queues are places where things are stored. Queues are acted upon
> to effect addition to, or subtraction from, the queue's contents.
> Addition is enqueuing. Subtraction is either a discard action,
> or a scheduler action. A queue per se does no action to either
> schedule or discard packets. That's the role of the scheduler
> or discard stages. Queues peform data storage, nothing else.
> 
> (When I wrote code to hold data elements in a queue, the 'queue'
> itself never modulated departure of data elements. Why should the
> defn be changed for routers?)
> 
>         [..]
> > 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.
> 
> So, totally ignoring the observation I (and I think Roch) made last
> week - that in this case, 'FIFO' characterizes the scheduling behavior
> applied to the queue.  Focussing on FIFO as descriptive of the queue's
data
> structure just serves to complicate the whole discussion, and isn't really
> useful to an abstract router model.
> 
> The descriptions of all the individual elements are good material.
> But the above, expansive definition of 'a queue' is too much.
> 
> cheers,
> gja
> ________________________________________________________________________
> Grenville Armitage                            http://mh005.infi.net/~gja
> Bell Labs Research, Lucent Technologies
> 
> _______________________________________________
> diffserv mailing list
> [email-masked]
> http://www.ietf.org/mailman/listinfo/diffserv
> Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/

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

---

From: Andrew Smith <[email-masked]>
Date: Wed, 15 Dec 1999 15:32:36 -0800

Dan,

More below (stuff that I agree on deleted).

> From: Dan Grossman [mailto:[email-masked]]
> Sent: Wednesday, December 15, 1999 3:07 PM
> To: Andrew Smith
> Cc: 'Dan Grossman'; [email-masked]
...
> > > 
> > > 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.
> > 
> Can do.  Would probably want to make that units on one fifo 
> in bytes, the 
> other in packets.

[Andrew] Not necessarily: buffer management might be in packets, even when
RED is in bytes. Might be applying discard based on both at the same time.

> > >
> > > 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.
> 
> 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] Suggest you have In-Mark and Out-mark as classifier outputs too,
rather than PHBs: surprisingly, this is the only place in the model that
mentions PHBs (as opposed to DSCPs) at present: we'd have to add a new
module to the model that did mapping of DSCP->PHB if you want to refer to
PHBs here.

> 
> > > 		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).
> > 
> Yes.  Ooops.  Thanks. <blush>
> 
> > > 		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.
> I hadn't thought about that...  could be.
> > Your
> > rules raise some questions in my mind: (1) do we need to be 
> able to have a
> > 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)
> > don't we also need to be able to go 
> Fifo->Discarder->Scheduler? I came up
> > with this formulation of your rules:
> Yes.  I thought the rules covered that.

[Andrew] Not as I read them: you said that a Scheduler could only be fed
from a FIFO or another Scheduler: you didn't allow Discarder to feed a
Scheduler.

> 
> > 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
> > 
> There has to be at least one FIFO, one discarder and one scheduler.

[Andrew] That's OK: I actually prefer the model where you have to have (at
least one) of each but allow any of them to be "NULL" functions.

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

[Andrew] Does "small" = 1 or 2? (Don't forget that this whole
"classifier+TCB" thing is allowed to repeat twice already according to the
model, once for router inputs, once for outputs).

> Definitely need more words to that effect.  
> 
... picture/grammar stuff deleted ...

> I'm not sure how you'd do what I'm proposing here by two 
> separate queue blocks.

[Andrew] Will revisit pictorial representations of this when we've agreed a
set of composition rules.
 
> Dan

Thanks,

Andrew

---

From: [email-masked]
Date: Tue, 21 Dec 1999 20:43:46 -0500

> if i've read the text below properly, the problem lies
> with the notion that a discarding engine might need random
> access into the queue itself?  that certainly makes the
> queue difficult to describe as a pure FIFO. it is also
> one of the reasons i suggested using FIFO term only to describe
> the ordering relationship between packets that simply pass
> through the queue/buffer without being subject to discard.
> the actual internal structure of the queue/buffer doesn't
> even need to be defined, just its external behavior, viz.:
>
> 	- Scheduler pulls packets out in FIFO order
> 	- Discarder pulls packets out using random access
> 	- Queue internals are irrelevant (ummm... open to
> 	  individual implementation choices :-)

Even that won't quite suffice.  At least one of the hardware
implementations that motivated the original concern over
FIFO vs. "don't reorder within any microflow" can reorder packets
in what would be the scheduler in Grenville's above model.
My understanding of the "can" and "would" in the previous
sentence is that the box in question provides a proof by
example that wire speed microflow classification (including
automatic on the fly flow detection) is indeed possible if
one throws enough hardware at the problem.

--David

---------------------------------------------------
David L. Black, Senior Technologist
EMC Corporation, 42 South St., Hopkinton, MA  01748
+1 (508) 435-1000 x75140, FAX: +1 (508) 497-6909
[email-masked]
---------------------------------------------------