Subject: [Diffserv] Model - queues

From: Dan Grossman <[email-masked]>
Date: Tue, 07 Dec 1999 18:04:02 -0500

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
[email-masked]
http://www.ietf.org/mailman/listinfo/diffserv
Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/

---

From: Roch Guerin <[email-masked]>
Date: Tue, 07 Dec 1999 19:38:45 -0500

Dan,

A quick comment on your model (which btw is quite comprehensive) and in
particular the FIFO and buffer management component.

It seems that the description you have is limited to buffer management
schemes that make acceptance decisions only at the time of packet
arrival.  This clearly represent the bulk of existing schemes, but there
are other options that i don't think we want to preclude in the future. 
In general, you can have a buffer management scheme that continuously
makes state-dependent decisions on packets already in the buffer, i.e.,
you have the option of changing your mind even after accepting the
packet.  One of the simplest example of such a scheme that has been used
(with limited success though) in ATM switches is the pushout scheme, but
there are other variations that are possible and I think we should try
to have a structure capable of accommodating this.

So I would say that a discarding element is an element which for every
state change in the buffer, i.e., a packet leaving or arriving, is
making decisions on which packets to keep/accept in the buffer based on
a discarding discipline.  This is not much different from what you have,
but I thought it might be important to clarify things.

One maybe trickier implication is wrt the FIFO structure as more complex
discard decisions may require additional information.  For example, a
pushout scheme may require multiple linked lists, one for each pushout
priority.  I don't think that we want to change the FIFO assumption but
it seems that there may be a need for additional "control" structures
together with it.  I don't think this drastically affects your outline,
but this is again something I felt might be useful to keep in mind.

Roch

---

From: Dan Grossman <[email-masked]>
Date: Wed, 08 Dec 1999 09:56:40 -0500

Hi Roch,
> arrival.
Not quite.  If a discarding element is placed after a queue (as the model 
permits) it can discard  one or more packets from the head of the queue.

  This clearly represent the bulk of existing schemes, but there
> are other options that i don't think we want to preclude in the future.
Sure.  I generally favor head dropping for real time traffic, although it 
tends to annoy hardware designers. 
> to have a structure capable of accommodating this.
Hmm.  I hadn't heard of this.  Do you have a reference?
> but I thought it might be important to clarify things.
What you're pointing out is that the description doesn't capture the notion of 
a trigger, which could either be fired by a packet arrival at the discarding 
element, some state change in the FIFO element, scheduler, or meter, or a 
timer.  That's useful. 
> but this is again something I felt might be useful to keep in mind.
I was being deliberately vague... er... inclusive here.

Rgds
Dan

---

From: Roch Guerin <[email-masked]>
Date: Wed, 08 Dec 1999 11:09:03 -0500

Dan,

> Hmm.  I hadn't heard of this.  Do you have a reference?

Here are a few pointers, mostly papers analyzing performance, although I
recall at least one paper by Landsberg and Zukowski (Columbia U.) which
was describing a VLSI design they had done for a scheme that was
actually
more generic than simple push-out.  I cannot put my hands on the exact 
ref right now, but maybe someone else will recall what I'm talking
about.
Most of it is also described in P. Landsberg PhD thesis entitled "VLSI
for packet switching nodes in communications networks." (don't have a
copy of that either, but maybe Paul has an online version somewhere).

- H. Kroner, G. Hebuterne, P. Boyer, and A. Gravey. "Priority management
in ATM switching nodes." IEEE Trans. Commun., vol. COM-9, No. 4, April
1991, pp. 418-427.

- J. Garcia and O. Casals. "Space priority mechanisms with bursty
traffic." 
IFIP Trans. C. Commun. Sys., Vol. C-4, 1992, pp. 393-412.
> > So I would say that a discarding element is an element which for every

- J. Garcia and O. Casals. "Stochastic models of space priority
mechanisms with 
Markovian arrival process."  Anals of Operations research, Vol. 35,
1992,
pp. 271-296.

> element, some state change in the FIFO element, scheduler, or meter, or a

And also that the discarding decision can apply to any packet in the
buffer,
not necessarily the arriving one or the one at the tail/end of a linked
list.
You could pick a random one (not sure why, though ;-) or actually more
than
one, e.g., kicking out several small packets to make room for a big one.

Roch

---

From: Zhen Liu <[email-masked]>
Date: Wed, 08 Dec 1999 17:36:36 +0100

> Here are a few pointers, mostly papers analyzing performance, although
> I recall at least one paper by Landsberg and Zukowski (Columbia U.)
> which was describing a VLSI design they had done for a scheme that was
> actually more generic than simple push-out.  

Here is another paper on the analysis of different discard policies
(including pushout, threshold and random dropping, etc.):

Z. Liu, R. Righter,
The Impact of Cell Dropping Policies in ATM Networks,
INRIA Research Report No. 3047, 1996.
to appear in Operations Research.
http://www-sop.inria.fr/mistral/personnel/Zhen.Liu/Papers/cell_drop.ps.gz

Zhen

---

From: Dan Grossman <[email-masked]>
Date: Wed, 08 Dec 1999 11:33:11 -0500

> one, e.g., kicking out several small packets to make room for a big one.
Two separate issues: if you wanted to allow picking a random packet to discard, then the data structure is no longer a FIFO.  We could do that, but since you're not sure why, and I'm not sure why, I'd just as soon not unless somebody else comes up with a reason why.  The proposal doesn't specify how many packets a discarding element can drop on a single trigger;  my assumption was 'zero or more'.  [As an aside, I'd be nervous about kicking out several small packets to make room for a large packet, since if the small packets are  TCP ACKs, you'd start getting into ack compression and slow start.]

---

From: Grenville Armitage <[email-masked]>
Date: Wed, 08 Dec 1999 09:21:24 -0800

Dan Grossman wrote:
	[..]
> Two separate issues: if you wanted to allow picking a random packet
> to discard, then the data structure is no longer a FIFO.  We could do
> that, but since you're not sure why, and I'm not sure why, I'd just as
> soon not unless somebody else comes up with a reason why.

Perhaps you could stretch the words to say "The scheduler stage
pulls packets from queues in FIFO sequence. However, the discard
stage may choose to select packets from anywhere in the FIFO queue.
Typically a packet from the tail or head of the queue would be
selected when discarding is triggered, but other choices are
possible."

(or something similar)

cheers,
gja
________________________________________________________________________
Grenville Armitage                            http://mh005.infi.net/~gja
Bell Labs Research, Lucent Technologies

---

From: Roch Guerin <[email-masked]>
Date: Wed, 08 Dec 1999 11:53:40 -0500

> Two separate issues: if you wanted to allow picking a random packet to discard, 
>then the data structure is no longer a FIFO.  We could do that, but since you're 
>not sure why, and I'm not sure why, I'd just as soon not unless somebody else 
>comes up with a reason why.  The proposal doesn't specify how many packets a 
>discarding element can drop on a single trigger;  my assumption was 'zero or 
>more'.  [As an aside, I'd be nervous about kicking out several small packets to 
>make room for a large packet, since if the small packets are  TCP ACKs, you'd 
>start getting into ack compression and slow start.]

Dan,

I think you may stray from a simple FIFO structure as soon as you need
to
keep track separately of different packet "types" in the buffer.  That's 
why I had mentioned the added control structures (linked lists) that may
be needed if you want to go back on your earlier decision of accepting
a packet.  Now, once you have those structures in place, e.g., linked
lists, it does not really matter which packet you end-up discarding. 
You
can just walk through the list until you find a packet that matches your
current criteria for discard.  For example, you could decide to drop the
first low priority (drop precedence) packet that exceeds a certain size.
In my mind FIFO refers more to the scheduling part than the buffer
management
one.  It implies that I don't send packets out of order, but does not
constrain the structure I maintain to keep track of which packets are
waiting to be transmitted.  Clearly, it is easiest to drop the packet at
the tail or head of a list, but once you have those lists in place you
can
afford to be more general.  And again I think they are needed as soon as
you consider keeping track of packets of different types in the buffer.

Coming to the second issue of dropping small packets, I agree that it
would
be a pretty bad idea in the case of TCP, and probably in general.  But
that
probably depends on the apps.  In any case, I was only using that as an
example and did not mean to recommend it ;-)

Roch

---

From: Dan Grossman <[email-masked]>
Date: Wed, 08 Dec 1999 12:59:18 -0500

> selected when discarding is triggered, but other choices are
I was trying to decouple the scheduling, discarding and FIFO elements to the 
extent possible. I also was being deliberately vague... er... inclusive as to 
whether packets are pushed or pulled.  

If we wanted to be inclusive of a non-FIFO data structure, than we could 
change the name to 'packet buffering structure' or something like that and 
give FIFO as an example.

Dan

---

From: Dan Grossman <[email-masked]>
Date: Wed, 08 Dec 1999 13:21:50 -0500

> This is a multi-part message in MIME format.
> --------------89294214678019D823F91B16
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
 
> first low priority (drop precedence) packet that exceeds a certain size.
Sounds like the case I was looking for to generalize.  I'll call it a 'packet 
buffering element'.  

> one.  
FIFO is overloaded.  In the context of the packet buffering element, it is a 
data structure.  In the context of scheduling, it is a service discipline.  I 
was working in the former context.
  
> It implies that I don't send packets out of order, but does not
> waiting to be transmitted.
Again, I'm trying to decouple scheduling from buffering and discarding. A pure 
FIFO scheduling element in the context of the model has one input and one 
output, and transfers packets from input to output whenever the output is not 
busy.

>  Clearly, it is easiest to drop the packet at
Sure, although I'd model it a bit differently so as to decouple the discarding and buffering elements.  In an actual implementation, it would probably tend to be more coupled.

---

From: Roch Guerin <[email-masked]>
Date: Wed, 08 Dec 1999 13:26:57 -0500

Dan,
SOunds good.  Thanks.  Roch

---

From: Grenville Armitage <[email-masked]>
Date: Wed, 08 Dec 1999 10:33:48 -0800

Dan Grossman wrote:
	[..]
> change the name to 'packet buffering structure' or something like that and

I'm uncomfortable with us heading off into descriptions of how
the data structures are built to instantiate the queues. How
about just using "FIFO" as a description of how the queue behaves
from the perspective of scheduling, then use functional descriptions
of how the discard might operate. The fact that a push-out discard
process might imply non-FIFO data structures is, to me, too much
detail.

cheers,
gja

---

From: Juha Heinanen <[email-masked]>
Date: Thu, 9 Dec 1999 11:24:36 +0200 (EET)

looks like you guys are trying to define a general switching
architecture that has very little to do just with diffserv.  although
interesting, i'm thus not sure if it makes sense to pursue this kind of
project in this working group.

-- juha

---

From: Dan Grossman <[email-masked]>
Date: Thu, 09 Dec 1999 10:53:09 -0500

> project in this working group.
The model is already a general (abstract) switching (meta) architecture.  We 
agreed we needed one in order to develop a reasonable MIB and PIB.  The point  
of this exercise was to allow the draft to model a variety of things that real 
nodes either do now or may want to do in the future, but which the current 
draft does not allow.  Otherwise, it won't be possible to configure and 
install policy into a variety of possible real devices without lots of 
enterprise-specific MIBs and PIBs.

It looks to me like the proposal has a lot of support in principle, although I 
haven't gotten feedback from Yoram, Andrew or Steve.   There is disagreement 
on the relationship between the FIFO and discarder but I have an idea how to 
deal the various concerns expressed on the list.

I'll draft up specific text for the list over the next day or so.

Dan

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 09 Dec 1999 09:47:22 -0600

I was beginning to think that myself. Our job here is only to define a minimal
set of constraints on implementations that are needed for diffserv to work.
As we've said oftem, the conceptual model is not a router design, and we
have carefully avoided talking about the routing core.

   Brian