Subject: RE: [Diffserv] Model - queues (second draft)

From: Andrew Smith <[email-masked]>
Date: Thu, 6 Jan 2000 11:24:23 -0800

OK, that's a completely different issue to what I thought you were talking
about. I was answering what I understood to be Grenville's point about how
to merge the outputs of the preceding stages as a combinatorial sort of
thing without any state or delaying etc..

Are you saying that you need a *real* scheduler at the outputs to your
microflow-metering and your aggregate-metering blocks in order to get the
packets for flows A and B back into the order in which they arrived, before
you place them into the FIFO? If so then I think you do need to model that
as a block that has real queues and schedulers of its own, before you get to
the FIFO that we were talking about (you can do this with the model as it
currently is although I'm not sure it's something a manager would be
interested in seeing). If not then I don't see a need for another block at
this point in the path. 

Maybe you can explain further - I think I'm still confused about the problem
that you see.

Andrew

> -----Original Message-----
> From: Shahram Davari [mailto:[email-masked]]
> Sent: Thursday, January 06, 2000 11:06 AM
> To: 'Andrew Smith'; 'Grenville Armitage'
> Cc: [email-masked]
> Subject: RE: [Diffserv] Model - queues (second draft)
> 
> 
> Hi Andrew, 
> 
> Imagine an edge router which has two Metering stages: a 
> Microflow and an
> Aggregate Metering stage. Now imagine that flow A is not marked by the
> customer, and needs both Microflow and Aggregate metering. 
> Also imagine flow
> B is already marked by the customer and needs only aggregate 
> metering. Now
> if the metering stage is a parallel processing system in 
> which flow A and B
> can be metered simultaneously, then it is possible for a 
> packet from flow B
> to overtake a packet from flow A even if it had arrived later 
> (because it
> needs less processing). 
> 
> So I don't think assumption of serial delivery to the FIFO is 
> implicit in
> the concept of packet FIFO.
> 
> -Shahram
> 
> > -----Original Message-----
> > From: Andrew Smith [mailto:[email-masked]]
> > Sent: Thursday, January 06, 2000 1:48 PM
> > To: 'Grenville Armitage'
> > Cc: [email-masked]
> > Subject: RE: [Diffserv] Model - queues (second draft)
> > 
> > 
> > Grenville,
> > 
> > I think that's implicit in the concept of a packet FIFO: I 
> > think the way
> > packets from multiple sources make their way into the FIFO 
> > *is* an attribute
> > of the FIFO queueing stage. If the FIFO worked on units of 
> > less than one
> > packet (e.g. 53-byte chunks of it :-)) then, I agree, some 
> > sort of merge
> > block might be needed. 
> > 
> > Maybe the clarification should be just the "packet" part of 
> > this: there is
> > no smaller unit of time under consideration here than a 
> > complete packet time
> > so the use the word "First" in "First In First Out" implies 
> > "the time at
> > which the start of the packet arrives at the queue" (or 
> > should it be the end
> > of the packet?). It is arguable that any definition that 
> > involves "first" or
> > "the time at which ..." implies a scheduling stage but I 
> > think, in this
> > case, that is splitting hairs.
> > 
> > Andrew
> > 
> > > -----Original Message-----
> > > From: Grenville Armitage [mailto:[email-masked]]
> > > Sent: Thursday, January 06, 2000 9:56 AM
> > > To: Dan Grossman
> > > Cc: [email-masked]
> > > Subject: Re: [Diffserv] Model - queues (second draft)
> > > 
> > > 
> > > 
> > > 
> > > Dan Grossman wrote:
> > > 	[..]
> > > > > 2) You mention that a FIFO can have more than one input. 
> > > I think if there
> > > > > are more that one inputs, then there should be another 
> > > element (i.e.,
> > > > > scheduler elements such as FCFS or MUX) before the FIFO. 
> > > So I suggest
> > > > > changing the text to "A FIFO has one input and one 
> > > output, but if more that
> > > > > one input are required for a FIFO they have to pass 
> > > through a scheduler
> > > > > element".
> > > > >
> > > > I thought about this and don't agree.  It would be common, 
> > > for example to have
> > > > more than one classifier feeding the same queue.  If the 
> > > flow of packets is
> > > > assumed to be serial, there is no scheduler element required.
> > > 
> > > Dan,  I think I agree with Shahram's observation here. If 
> we assume
> > > the packets arrive serially from the outputs of preceding 
> > classifiers
> > > then the merging (aka 'multiple inputs') isn't really an attribute
> > > of the queue/buffering stage - its a simple 'OR' function of
> > > multiple streams of packets, which might happen anywhere prior to
> > > the FIFO.  At the very least, add text clarifying
> > > the assumption that the multiple inputs are in fact being fed
> > > by synchronized packet streams (i.e. synchronized to have
> > > non-overlapping arrival times at the FIFO input{s} )
> > > 
> > > cheers,
> > > gja
> > > 
> > > _______________________________________________
> > > 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/
> > 
> 

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

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 06 Jan 2000 16:23:42 -0600

Grenville Armitage wrote:
...
> 
> There's an alternative hypothetical case which I take to be
> what triggered Shahram's observation: Consider if a router's
> architecture allowed packets from multiple parallel
> classifiers (heading into the FIFO's buffer) to have concurrent
> or overlapping arrival times. Iff this second (more general) case
> is allowed, then there has to be some element that (at least
> notionally) decides which packet gets into the buffer 'first'.
> Thats a scheduler.

Only if it is allowed to look ahead in time. Otherwise, the only
tricky case is a race condition where the first bit of each packet
arrives simultaneously. But I think this is far too detailed to cover
in the model; I think we should simply observe that a FIFO may need
to multiplex inputs and leave the rest to the imagination of the
reader. I remind you all once again that we are not designing a router
here, and conceptual models don't have to be perfect.

  Brian

---

From: Grenville Armitage <[email-masked]>
Date: Thu, 06 Jan 2000 14:56:42 -0800

Brian E Carpenter wrote:
	[..]
> I remind you all once again that we are not designing a router

I'd settle for un-ambiguous. It seems reasonable to reduce
ambiguity by elaborating on the packet arrival assumptions in
the 'multiple input' FIFO element. Or just remove references
to a FIFO element having multiple inputs (I personally think
_this_ description is the one being too detailed - any router
designer knows they can make a single input element into a
multiple input element with queue-less packet merging, no need
to call it out explicitly).

cheers,
gja

---

From: Grenville Armitage <[email-masked]>
Date: Thu, 06 Jan 2000 13:57:22 -0800

Andrew,

Now that we're all happily tied up in knots....

> thing without any state or delaying etc..

To clarify the words I used below: 

	[..]
> > > > non-overlapping arrival times at the FIFO input{s} )

I'm stating that _IF_ the packets arriving from different
classifiers are known to have non-overlapping arrival times
into a particular FIFO's buffer stage, then the notion of
a multiple input FIFO is probably not worth pointing out.
It is a simple queue-less merge, which I dont believe is a
notable attribute of a FIFO stage per se.

cheers,
gja