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

From: Andrew Smith <[email-masked]>
Date: Thu, 23 Dec 1999 12:00:38 -0800

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

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:

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

to

"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 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.
Setting the service priority of each input to the scheduler to the same
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.]

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.1.4 Constructing queueing blocks from the elements
      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"

Other edits look good to me.

Andrew

> -----Original Message-----
> From: Dan Grossman [mailto:[email-masked]]
> Sent: Thursday, December 23, 1999 10:30 AM
> To: [email-masked]
> Subject: [Diffserv] Model - queues (second draft)
> 
> 
> 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/
> 

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

---

From: Dan Grossman <[email-masked]>
Date: Thu, 23 Dec 1999 16:24:16 -0500

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

> [Disclaimer: this is how our implementation works so that may be why I think
I don't mind if nobody else does...

>       7.2 Constructing queueing blocks from the elements
Agree.

Dan