Subject: [Diffserv] Model - queues - replacement text

From: Dan Grossman <[email-masked]>
Date: Tue, 14 Dec 1999 15:44:15 -0500

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.

Following is proposed replacement text for the model.

6.6 [Delete]

7.  Queues
Queues order the transmission of packets belonging to the different traffic
streams, possibly storing them temporarily or discarding them. Packets are
usually stored either because there is a resource constraint (e.g.,
available bandwidth) which prevents immediate forwarding, or because the
queue is being used to alter the temporal properties of a traffic stream
(i.e., shaping).  Packets are discarded either because of buffering
limitations or as a feedback control signal to reactive control protocols
such as TCP.

It should be noted that the queues in this model are logical abstractions
used to configure PHB-related parameters.  The model can be used to
represent a broad variety of possible implementations.  However, it need not
necessarily map one-to-one with physical queues in a specific router
implementation.   Implementors should map the configurable parameters of the
physical queues to these queue parameters as appropriate to achieve
equivalent behaviors.

7.1  Model
Queuing is a function a which lends itself to innovation.  It must be
modelled to allow a broad range of possible implementations to be
represented using common structures and parameters.  This model uses
functional decomposition as a tool to permit the needed lattitude.  

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.  These elements
which may be connected together either dynamically or statically to
construct queueing subsystems.  A queue is thus composed of of one or more
FIFO, one or more scheduler, and one or more discarder.  See figure TBA for
an example of a queue.  

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.

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. 

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

7.1.2 Scheduler
A scheduler is an element which gates the departure of each packet that 
arrives at one of its inputs,  based on a service discipline. It has one or
more input and exactly one output.  Each input has an upstream element to
which it is connected, and a set of parameters that affects the
scheduling of packets received at that input.

The service discipline (also known as a scheduling algorithm) is an 
algorithm which may take as its inputs static parameters (such as 
relative priority, and/or absolute token bucket parameters for maximum or
minimum rates) associated with each of the scheduler's inputs; parameters
(such as packet length or DSCP) associated with the packet present at its
input; absolute time and/or local state.  

Possible service disciplines  fall into a number of categories, including
(but not limited to) strict priority, weighted fair bandwidth sharing (e.g.,
WFQ, WRR, etc.), rate-limited strict priority, and rate-based.    Service
disciplines can be further distinguished by whether they are work conserving
or non-work conserving.  A work conserving  service discipline transmits a
packet at every transmission opportunity if one is available.  A non-work
conserving algorithm transmits packets no sooner than a scheduled departure
time, even if it means leaving packets in a FIFO while the link is idle.
Non-work conserving schedulers  can be used to shape traffic streams by
delaying packets that would be deemed non-conforming by some traffic
profile.  The packet is delayed until such time as it would conform to a
meter using the same profile.

[DSARCH] defines PHBs without specifying required scheduling algorithms.
However, PHBs such as EF [EF-PHB] and AF [AF-PHB] have configuration
parameters which strongly suggest the sort of scheduling discipline needed
to implement them.  This memo specifies a minimal set of queue parameters to
enable realization of these per- hop behaviors.  These include a minimum
service rate profile,  a strict service priority and a maximum service rate
profile (the latter is for use only with a non-work conserving service
discipline). The minimum service rate allows rate guarantees for each
traffic stream  as required by EF and AF without specifying the details of
how excess bandwidth between these traffic streams is shared.   Additional
parameters to control this behavior should be made available, but are
dependent on the particular scheduling algorithm implemented.  The strict
service priority is useful for implementing EF on some links,assuming that
the aggregate EF rate has been appropriately bounded to avoid starvation.
Setting the service priority of each input to the scheduler to the same
value enables the scheduler to satisfy the minimum service rate for
corresponding traffic stream.

A non-work conserving scheduler might be represented using the following 
parameters:

	Scheduler1:
	Type:		 Scheduler

	Input1:		Discarder1
	MaxRateProfile:	Profile1
	MinRateProfile:	Profile2
	Priority:		None
	
	Input2:		Discarder1
	MaxRateProfile:	Profile3
	MinRateProfile:	Profile4
	Priority:		None

A work conserving scheduler might be represented using the following 
parameters:
	Scheduler2:	
	Type:			Scheduler

	Input1:		Scheduler1, 
	MaxRateProfile:	WorkConserving
	MinRateProfile:	Profile5
	Priority:		1

	Input2:		FIFO2
	MaxRateProfile:	WorkConserving
	MinRateProfile:	Profile6
	Priority:		2

	Input3:		FIFO3
	MaxRateProfile:	WorkConserving
	MinRateProfile:	None
	Priority:		3

			
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.  

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

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

		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.   

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.

7.2  Shaping
Traffic shaping is often used to condition traffic such that packets will be
deemed conforming by subsequent meters, e.g., in downstream Diffserv nodes.
Shaping may also be used to isolate certain traffic streams from the effects
of other traffic streams of the same BA. 

A shaper  is realized in this model by using a non-work conserving
scheduler.  Some implementations may elect to have queues whose sole purpose
is shaping, while others may integrate the shaping function with other
buffering, discarding and scheduling associated with access to a resource.
Shapers operate by delaying the departure of packets that would be deemed
non-conforming by a meter configured to the shaper's maximum service rate
profile.  The packet is scheduled to depart no sooner than such time that it
would become conforming.  

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

---

From: Grenville Armitage <[email-masked]>
Date: Tue, 14 Dec 1999 13:45:38 -0800

Dan,

	[..]
> 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?)

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

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 14 Dec 1999 16:49:12 -0600

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

---

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

> I disagree fundamentally with this description.
I don't know quite what to suggest.

The proposed text doesn't change the scope of the section entitled 'Queues', 
which also talks about scheduling and discarding.  The difference is that I've 
decomposed the queues into buffering, discarding and scheduling functions.  
But these were already there.   

> or discard stages. Queues peform data storage, nothing else.
I have a very nice two-volume set in my office called "Queueing Systems".  
It's full of math and graphs that describe the dynamics of queues.  There's 
material on priority queueing and queueing disciplines and work conservation 
and loss formulas and.... a lot more than the 20-odd pages on stacks and 
queues in my (nondescript) Data Structures reference text.

I think that if I'm stretching the definition of a queue, others have gotten 
there first. :-)

> defn be changed for routers?)
I think that this is another case of a word that's gotten overloaded.   And 
the broader context is appropriate here.

Unless you have another word that would 'drop in'?

Otherwise, maybe the thing to do is put in some words to the effect that the 
word "queue" is overloaded, and that this document uses it in its broader 
context.

> useful to an abstract router model. 
No, quite the contrary, acknowledging your observation and recognizing that 
there is more than one meaning which is commonly assigned to "FIFO".

---

From: Grenville Armitage <[email-masked]>
Date: Tue, 14 Dec 1999 15:53:09 -0800

> the model with the MIB, but one of the documents has to change anyway..

Noted that we're attempting to converge terminology use here.
I have no problem with the notion that an ordered store
plus add/discard/schedule engines is a queuing system.
Based on what you say above, I believe the MIB draft is
being over-inclusive. We should keep queues as ordered
stores.

cheers,
gja

---

From: Grenville Armitage <[email-masked]>
Date: Tue, 14 Dec 1999 15:57:58 -0800

Dan,

	[..]
> I think that if I'm stretching the definition of a queue, others have gotten

I suspect the books talk about the behaviors of queuing systems,
with "systems" implied and thereby including the components that
add/discard/schedule-removal.

(Interesting side-note, the term "queue" is used in non-technical
circles to refer to an ordered data store - e.g. people queue up
to board a bus, or to order tickets, or to purchase food... but
I'm aware such usage isn't common in the US, being more of a
british-ism. Perhaps my british-influenced background is demanding
purity here :-)

> Unless you have another word that would 'drop in'?

"Queuing systems perform three distinct, but related...."

cheers,
gja

---

From: [email-masked] (Daniel Awduche)
Date: Wed, 15 Dec 1999 01:05:40 -0500 (EST)

More precisely, a queue is a representation of a dynamic 
data set which depicts an ordered relation between 
set elements. 

The "representation" of the set and the "storage" 
of set elements are separable. The "queue" may be ordered, 
but the "storage" of set elements need not necessarily 
be ordered. The representation (e.g. a data structure
with keys and pointers) may support some elementary 
functions (insert/discard/etc) which may be activated 
by engines external to the representation. The queuing
system consists of the dynamic data set, the 
representation, storage, and activating engine(s).

Cheers,
/Dan