[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [Diffserv] Model - queues - replacement text



Dan,

Some comments on your proposal - I like it (mostly). See [Andrew] below.

> -----Original Message-----
> From: Dan Grossman [mailto:dan@noah.dma.isg.mot.com]
> Sent: Tuesday, December 14, 1999 12:44 PM
> To: diffserv@ietf.org
> Subject: [Diffserv] Model - queues - replacement text
> 
> 
> 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.
> 
...
> 
> 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.

[Andrew] Suggest that we always stick to the former and never use the latter
in this document.

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

[Andrew] Suggest we not get into re-ordering issues here to any granularity
less than "per-queue": I think it suffices to say here "this does not
preclude implementions which support operations on the FIFO data structure
that remove or examine packets e.g. for use by discarders. The only
constraint on such operations is that they not add packets back into the
FIFO in a different order."

> 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

[Andrew] It might be worth changing one of the example thresholds to be,
say, "1000 bytes". Just to show that thresholds are not necessarily measured
in packets always.

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

[Andrew] I find this last paragraph a bit confusing where it says that the
thing has no inputs and no outputs! Maybe we could say that this type of
discarder has as its input a sort of random-access capability into the
upstream packet source (and no outputs)? BTW, the upstream source does not
necessarily have to be a FIFO does it?

> 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

[Andrew] Is it really necessary to allow another classifier in at this
point? ("parameters associated with the packet" implies a classifier here).
If so, can't we re-use the classifier definition from section 4 instead of
inventing a new (DSCP-specific) one here? I think I'm saying that I don't
like the In-mark and Out-mark included here - we've got remarkers already
defined in section 6.1.
 
> 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

[Andrew] Need to define what you mean by "meta-policy". Or else choose
different words.
 
> 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.  

[Andrew] Do you mean "may be connected to the output of a *FIFO*"? (I assume
so below).

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

[Andrew] I find this description confusing (backwards?). But I could not
find a formulation using go-to rather than come-from links ("the output of A
may go to the input of B") that has the same effect as your rules. Your
rules raise some questions in my mind: (1) do we need to be able to have a
Scheduler feed into a FIFO? (2) does a queue ever need to contain more than
one FIFO or discarder? (3) do we need to have queues be concatenated? (4)
don't we also need to be able to go Fifo->Discarder->Scheduler? I came up
with this formulation of your rules:

QueueDan ::= Fifo |
           Fifo Discarder |
           Fifo Scheduler* |
           Fifo Scheduler* Fifo |
           Discarder |
           Discarder Fifo |
           Discarder Fifo Discarder |
           Discarder Fifo Scheduler* |
           Discarder Fifo Scheduler* Fifo   (this starts to recurse ...)
+ etc. ad nauseum

If the answer to (4) is yes and we handle the recursion thing by making you
have multiple concatenated Queue blocks, I think we can use a simpler rule
like the following:

QueueAndrew ::= Fifo |
          Fifo Discarder | 
          Fifo Scheduler* | 
          Fifo Discarder Scheduler*  |
          Discarder |
          Discarder Fifo |
          Discarder Fifo Scheduler*

But I'm not sure it's any clearer than the words - probably not. Maybe a
picture with arrows would help (or not):
                    +-------------->+
                    |               |
Queue---+--->Fifo---+-->Discarder-->+-+->+-->Scheduler-->+-->+-->Queue
 In     |                             |  |               |   |    Out
        |                             |  +<--------------+   |
        |                             |                      |
        +-->Discarder-->+-->Fifo----->+-->+----------------->+
                        |                 |
                        +---------------->+

I think this meets the requirements.

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

I think this one might best be modelled by concatenating 2 queue blocks,
rather than recursing inside the queue block. Just a thought.


Andrew

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