Subject: Re: [Diffserv] issues with RFC 2598

From: Jon Bennett <[email-masked]>
Date: Tue, 2 May 2000 12:46:22 -0400

Bill Courtney writes

>I spoke too tersely and identified the wrong algorithm.  I should have said
>"WF2Q+" rather than "WF2Q".  Also, the start and finish times in WF2Q+ are
>kept "per session" (not necesarily "per queue").  

For the record Pawan was right to complain (and I missed the point he was
making in my first response) that if you just make the change of
implementing per-queue timestamps with the *fluid* virtual time function of
WF2Q that things could go wrong. While this can be fixed in much the same
way as the non-RPPS case can be handled, his statement was in fact correct. 

I suspect that it would be best if everyone just assumed that WF2Q+ was
implied anytime implementation was being discussed unless it is explicitly
stated that the fluid model is being discussed to avoid the confusion that
keeps resulting.

>I was assuming that each
>session had a FIFO and that a representative of each session is kept in one
>of two heaps, the ineligible heap or the eligible heap, based on start time
>versus virtual time. (Thus my use of "queue" rather than "session".)
>Clearly, this is my own interpretation of how one might implement WF2Q+,
and
>is not something that Bennett and Zhang said in "Hierarchical Packet Fair
>Queuing Algorithms," although in that paper they do discuss maintaining
only
>one start and finish time per session.

Actually the two heap implementation has a problem when lots of ineligible
sessions become eligible, because you may need to move everyone from one
heap to the other in a single packet time. We present a number of hardware
implementations that avoid this problem in our various papers. For software
implementations one of Hui Zhang's students, Ion Stoica has a very elegant
data structure that effectively combines the two heaps eliminating the need
to move sessions between the two heaps. (I should add that he developed this
independently of the work I did with Hui Zhang, and prior to his becoming
Hui's student.)

>My point in my previous posting was that with this algorithm (WF2Q+), very
>good behavior is obtained and the finish time for a packet is not
>necessarily calculated or even knowable when a packet arrives.  Following
up
>on this notion, I wondered whether using a definition for EF PHB that spoke
>of a finish time only for the packet at the head of the EF aggregate queue
>might not give us a simple and reasonable criterion for deciding when a
>scheduler is compliant.  I then offered a simple criterion.  Whether it's
>reasonable remains to be seen.

Your approach does seem to have yielded a very nice formulation of the
problem. An additional benefit that it appears to have is that by not
concentrating on the delay of an individual packet it allows the EF traffic
to be served by policies such as round robin rather than implying the EF
aggregate must be served by a FIFO. 

Jon C. R. Bennett
Chief Engineer
RiverDelta Networks 
3 Highwood Drive
Tewksbury, MA  01876
978.858.2300/2361 (direct)
978.858.2399 (Fax)

   -export-a-crypto-system-sig -RSA-3-lines-PERL

#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

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

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 02 May 2000 17:43:24 -0500

This discussion is going a lot deeper into implementation details
than is really relevant to an IETF WG. We don't do formal compliance
work in the IETF. Personally I think you are (collectively) trying to
refine the details too much and losing sight of the global constraints,
which is all that a PHB spec such as RFC 2598 is intended to specify.

Kent reminded us of the key definition of the EF PHB:

> "The EF PHB is defined as a forwarding
> treatment for a particular diffserv aggregate where the departure rate of
> the aggregate's packets from any diffserv node must equal or exceed a
> configurable rate.  The EF traffic SHOULD receive this rate independent of
> the intensity of any other traffic attempting to transit the node."

When we finalized RFC 2598 this wording seemed to be unambiguous, necessary, 
and sufficient, otherwise it would not have gained WG consensus.
Would anyone like to propose a specific, simple change to this wording? 

On the other hand, discussion of implementation details belongs
on the diffserv implementation list 
(see http://www.tip.csiro.au/dsimplementation )

   Brian Carpenter
   diffserv co-chair

-- 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Brian E Carpenter 
Program Director, Internet Standards & Technology, IBM 
On assignment for IBM at http://www.iCAIR.org 
Attend INET 2000: http://www.isoc.org/inet2000
Non-IBM email: [email-masked]