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

From: Shahram Davari <[email-masked]>
Date: Thu, 6 Jan 2000 08:49:37 -0800

Hi Dan,

Please see comments:

> -----Original Message-----
> From: Dan Grossman [mailto:[email-masked]]
> Sent: Thursday, January 06, 2000 11:28 AM
> To: Shahram Davari
> Cc: 'Dan Grossman'; Andrew Smith; [email-masked]
> Subject: Re: [Diffserv] Model - queues (second draft) 
> 
> 
> > 1) Although you mention that a FIFO is identified by its depth,
> > threshold,... But in your FIFO examples there is no Depth 
> parameter. So I
> > suggest adding it to the example.
> The depth is a variable, not a configuration parameter.  I'll 
> add clarifying 
> text.

Agreed. My mistake, I was thinking about the MAX-depth, which of course can
be configured using one of the thresholds.

> > 
> > 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.

In case of serial packet flow, the multiple inputs can be directly connected
to a single line like following:

In1 -------|
In2 -------|-------> FIFO ---->
In3 -------|

So I think there is no need to include this as part of the FIFO model,
because it will generate confusion in case of non-serial packet flows.

> > 3) I think your "priority" part requires some work. I will 
> try to work on
> > it.
> I've incorporated Andrew's text. Hope that works for you.
> 
> Will send the updated text to the list shortly.
> > 
> 

Great.

-Shahram

_______________________________________________
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: Thu, 6 Jan 2000 10:47:52 -0800

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

> From: Grenville Armitage [mailto:[email-masked]]
> Sent: Thursday, January 06, 2000 9:56 AM
> To: Dan Grossman
> Cc: [email-masked]
> Dan Grossman wrote:
> 	[..]
> > > 2) You mention that a FIFO can have more than one input. 
> I think if there
> > > 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".
> > >
> > more than one classifier feeding the same queue.  If the 
> flow of packets is
> 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
>

---

From: Shahram Davari <[email-masked]>
Date: Thu, 6 Jan 2000 11:43:00 -0800

In the example that I described there is no need to preserve the ordering of
the packets from flow A and B, because they belong to different microflows,
but there is a possibility that they collide at the input of the FIFO (i.e.,
output of the Meter). So either a kind of FCFS Muxing, or a scheduler or
some speed-up is required.

I think if you mention in your model that: "provided that the there is no
time overlap between the packets arriving from different inputs", then it
should be OK.

-Shahram

> From: Andrew Smith [mailto:[email-masked]]
> Sent: Thursday, January 06, 2000 2:24 PM
> To: 'Shahram Davari'
> Cc: [email-masked]
> Subject: RE: [Diffserv] Model - queues (second draft)
> 
> 
> 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
> 
> > 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
> > 
> > > 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,
> > >

---

From: Andrew Smith <[email-masked]>
Date: Thu, 6 Jan 2000 12:17:19 -0800

OK, so I *was* answering the right question: if we define "first" as an
instantaneous event then there is no possibility of overlap. I suggested
that "first" be defined as the instantaneous start of a packet.

Andrew

> Sent: Thursday, January 06, 2000 11:43 AM
> To: 'Andrew Smith'; Shahram Davari
> Cc: [email-masked]

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Thu, 6 Jan 2000 15:09:42 -0500

> some speed-up is required.

I think your example was pretty much the general case. And, in fact, each of
those incoming flows could very well be at drastically different rates,
which means that the general case could very well have several packets from
the same incoming microflow appear consecutively at the output of the FIFO,
occasionally interrupted by other intruder troublemakers.

The fact that a merge point could easily introduce some amount of "clumping"
among packets of any given microflow, I think, is well known. Which is why I
believe we should continue to permit shaping not only at egress routers, but
possibly also within the core?

In any event, I don't see that a scheduler is an essential part of a FIFO
when there are multiple input flows. Most data flows don't care too much
about clumping.

Bert
[email-masked]

---

From: Shahram Davari <[email-masked]>
Date: Thu, 6 Jan 2000 14:31:30 -0800

Hi Brian,

Since multiple input behavior can be constructed by cascading a traffic
conditioning element (like MUX) in front of the input to a queue, then there
is no need to include the MUX function in the definition of FIFO (it is
redundant, right?

-Shahram

> From: Brian E Carpenter [mailto:[email-masked]]
> Sent: Thursday, January 06, 2000 5:04 PM
> To: Shahram Davari
> Cc: 'Andrew Smith'; 'Grenville Armitage'; [email-masked]
> Shahram,
> I think we agreed that elements can be cascaded; what you are 
> describing is
> cascading traffic conditioners in front of the input to a 
> queue. I think we had
> the notion that the input to a queue is a multiplexer rather 
> than a wire a
> long time ago. So I think the text should make it clear that 
> the input to
> a queue may be a multiplexer, but the queue certainly doesn't 
> include the
> traffic conditioners feeding that multiplexer.
> 
> Apart from this point, where we need one more spin, I'm going 
> to pick up 
> my co-chair's gavel and say that Dan's text should go into 
> the pending 
> revision of the model draft.
> 
>