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

From: Dan Grossman <[email-masked]>
Date: Thu, 23 Dec 1999 13:30:02 -0500

All,
Here is another draft of the queues replacement text, taking into account the 
discussions of last week.  One thing I did was to change the thing formerly 
called 'queue' to 'queueing block' (which is parallel to traffic conditioning 
block', and related it back to this notion of a queuing system. 

I'll look forward to further discussion (and hopefully consensus) after the 
New Year.  Please note that in deference to the Y2K panic, I will not have 
email access until I get back on January 4th.

Best wishes to all for the holiday season and the New Year. 

rgds
Dan

Add (somewhere) "Specific policy objectives are presumed to be installed by
or retrieved from policy management mechanisms. However, diffserv routers
are subject to implementation decisions which form a meta-policy that scopes
the kinds of policies which can be created.  

6.6 [Delete]

7.  Queueing block
The queueing block modulates the transmission of packets belonging to the
different traffic streams and determines their ordering, 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 queueing block is being used
to alter the temporal properties of a traffic stream (i.e., shaping).
Packets are discarded either because of buffering limitations, because a
buffer threshold is exceeded (including when shaping is performed), as a
feedback control signal to reactive control protocols such as TCP, because a
meter exceeds a configured rate (i.e., policing).

The queueing block in this model is a logical abstraction of a queueing
system, which is used to configure PHB-related parameters.  There is no
conformance to this model.  The model can be used to represent a broad
variety of possible implementations.  However, it need not necessarily map
one-to-one with physical queueing systems in a specific router
implementation.   Implementors should map the configurable parameters of the
implementation's queueing systems to these queueing block 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.  

Queueing sytems, such as the queueing block defined in this model, 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 the queueing block into
the component elements that perform each of these functions.  These elements
which may be connected together either dynamically or statically to
construct queueing blocks.  A queuing block 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 queueing block.  

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.  

7.1.1  FIFO
A FIFO element 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.  

Typically, the FIFO element of this model will be implemented as a FIFO data
structure.    However, this does not preclude implementations which are not
strictly FIFO, in that they also support operations that remove or examine
packets (e.g., for use by discarders) other than at the tail.  However, such
operations MUST NOT have the effect of reordering 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:	QueuingBlock.input1
	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: 1000 octets 
	Threshold3: 10 packets
	Threshold4: 2000 octets

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) first come, first served (FCFS), 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 service discipline
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 an 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's operation is modelled
as a  side-effect on the FIFO upon which it operates, rather than as having
a discrete input and output. 

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.

Note that although a discarder may need to examine the DSCP or possibly
other fields in a packet, it may not modify them (i.e., it is not a marker).

A discarder might be represented using the following parameters:
	Discarder1:
	Type:			Discarder
	Trigger:		Internal
	Input:		QueuingBlock.input2
	Output:		FIFO1
	Discipline:		RIO

	Parameters:
	In-MinTh:		FIFO1.Threshold1
	In-MaxTh:		FIFO1.Threshold2
	Out-Minth:		FIFO1.Threshold3
	Out-Maxth:		FIFO1.Threshold4
	In-DSCP:		AFx1_recommended_DSCP
	Out-DSCP:		AFx2_recommended_DSCP
	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
	Operate_on		FIFO3
	Trigger:		FIFO3.depth > 100 packets
	Discipline:		Drop-all-out-packets

	Parameters:	
	Out-DSCP:		AFx2_recommended_DSCP | AFx3_recommended_DSCP

7.1.4 Constructing queueing blocks from the elements
A queuing block is constructed by concatenation of these elements so as to
meet the meta-policy objectives of the implementation, subject to the
grammar rules specified in this section.   

Elements of the same type may appear more than once in a queueing block,
either in parallel or in series. Typically, a queuing block will have
relatively many elements in parallel and few in series. Iteration and
recursion are not supported constructs in this grammar.  A queuing block
must have at least one FIFO, at least one discarder, and at least one
scheduler.   The following connections are allowed:

		The input of a FIFO may be the input of the queueing block,
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 FIFO, to the output of a discarder 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 block 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.  

------- End of Forwarded Message

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

---

From: Shahram Davari <[email-masked]>
Date: Fri, 24 Dec 1999 07:43:17 -0800

Hi Dan,

Good work. I have a few comments.

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.

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

3) I think your "priority" part requires some work. I will try to work on
it.

Thanks,
Shahram Davari
PMC-Sierra Inc.

> -----Original Message-----
> From: Dan Grossman [mailto:[email-masked]]
> Sent: Thursday, December 23, 1999 4:24 PM
> To: Andrew Smith
> Cc: 'Dan Grossman'; [email-masked]
> Subject: Re: [Diffserv] Model - queues (second draft) 
> 
> 
> > Thanks Dan,
> > 
> > A few more points:
> > 
> > 1. I am still uncomfortable with the notion that Discarders 
> might contain
> > their own classifier based on DSCP: the example discarders 
> should work based
> > on the *PHB*, not the DSCP. And we already have a 
> functional block that maps
> > from DSCPs into {other PHB-like stuff} - it's called a 
> "Classifier". I think
> > the management model is cleaner if we use that definition 
> instead of the
> > In-DSCP and Out-DSCP parameters that you have. One might 
> instanciate a
> > Classifier block solely for the purposes of driving a 
> Discarder but that's
> > fine: I'd rather re-use existing blocks (i.e. MIB agent code) where
> > possible. How about renaming these parameters as 
> "InProfileClassification"
> > and "OutofProfileClassification".
> So what you're saying is that the discarder isn't looking at 
> packet headers, 
> but rather at some sort of tag which has been bound to the 
> packet by the 
> classifier.
> 
> I can't see any reason why this won't work.
> > 
> > 2. Your formulation of the Scheduler.Priority parameter is 
> certainly one
> > possibility. As I read your text, the (example) scheduler 
> uses the Priority
> > as the parameter with the highest precedence, allowing it 
> to pre-empt even
> > the guarantees of MinRateProfile. I think that a more 
> useful (common?)
> > implementation is one that uses a Priority parameter to 
> assign only the
> > *spare* bandwidth i.e. MinRateProfile has the highest 
> precedence and only
> > after that has been satisfied for all queues/classes is 
> Priority used in
> > deciding who gets to use the excess. Then it is the 
> responsibility of
> > configuration management to ensure that the desired 
> guarantees are meetable
> > (i.e. sum(MinRateProfile) for all classes <= line rate). 
> This alternative
> > definition for the "Priority" parameter still supports 
> strict priority
> > scheduling (you just set MinRateProfile to 0 and 
> MaxRateProfile to 100%) and
> > WRR (you just set the Priority parameters of all queues to 
> be the same). So,
> > I would propose that we adopt this alternate wording. Change:
> > 
> The words came from the previous version of the draft.  I 
> hadn't thought too 
> much about this, mostly because I have a rather low opinion 
> of priority.  So 
> don't mind me :-)
> 
> > "This memo specifies a minimal set of queue parameters to
> > profile ... The strict
> > corresponding traffic stream."
> > 
> > to
> > 
> > "This memo specifies a minimal set of queue parameters to
> > service rate profile,  a service priority and a maximum service rate
> > profile ... The 
> > service priority is used only after the MinRateProfiles of 
> all inputs
> > have been satisfied in order to decide how to allocate any 
> remaining 
> > bandwidth. It is useful for implementing, for example, the EF PHB, 
> > using a strict priority scheduling algorithm on some links, 
> assuming 
> > that the aggregate EF rate has been appropriately bounded to avoid 
> > starvation: for this scheduler the MinRateProfile would be reported 
> > as zero and the MaxRateProfile reported as line rate.
> > value enables the scheduler to satisfy the minimum service rates for
> > each input, so long as the sum of all minimum service rates is less 
> > than or equal to the line rate."
> > 
> > [Disclaimer: this is how our implementation works so that 
> may be why I think
> > it more useful.]
> > 
> I don't mind if nobody else does...
> 
> > 3. Not sure that "Shaping" merits its own high-level 
> heading. Right now you
> > have:
> >    "7.  Queueing block
> >       7.1  Model
> >          7.1.1 FIFO
> >          7.1.2 Scheduler
> >          7.1.3 Discarder
> >       7.2  Shaping"
> > Suggest we renumber this to be:
> >    "7.  Queueing block
> >       7.1  Model
> >          7.1.1 FIFO
> >          7.1.2 Scheduler
> >          7.1.3 Discarder
> >       7.2 Constructing queueing blocks from the elements
> >          7.2.1 Shaper"
> Agree.
> 
> Dan
> 
>