Subject: typo in prev message - Fwd: RE: FW: [Diffserv] EF question !!!

From: Anna Charny <[email-masked]>
Date: Mon, 10 Apr 2000 22:04:05 -0700

Hi,

  There was a typo in prev message: the sentence  " In that case in you 
example above the queue is technically empty after the last bit of the 
previous packet left, and before the first bit of the next packet 
arrived"  should obviously be  " In that case in you example above the 
queue is technically empty after the last bit of the previous packet left, 
and before the *last* bit of the next packet arrived". I hope it was clear 
from the context...

Anna
==========================================================================
X-Sender: [email-masked]
X-Mailer: QUALCOMM Windows Eudora Pro Version 4.2.0.58
Date: Mon, 10 Apr 2000 19:18:34 -0700
To: "Zhao, Yongdong" <[email-masked]>, "'Anna Charny'" <[email-masked]>
From: Anna Charny <[email-masked]>
Subject: RE: FW: [Diffserv] EF question !!!
Cc: "[email-masked]'" <[email-masked]>
In-Reply-To: <[email-masked]
  m>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
X-UIDL: 09f4093dcd7d17da1681619f61a49c0e

Hi,

At 05:32 PM 4/10/00 -0500, Zhao, Yongdong wrote:
>Hi,
>
>It seems to me that there are still problems on the service rate definition
>even if you only consider busy period. Here is an example. First some
>assumptions:
>(1) queue is built up from time T_0=0, i.e. queue is empty before time T_0,
>(2) EF packet size is L,
>(3) it takes S(second) for a packet being switched into the queue, (e.g.
>s=L/C, C is the fabric bandwidth)
>(4) it takes R(second) to pull a packet out of the queue, (e.g. r=L/D, D is
>the port bandwidth)
>(5) a packet can be served only after the entire packet has been saved in
>the queue.
>
>Now from T_0=0 to T_1=S, The first packet is put into the queue. The EF
>queue cannot be served even though the queue is continuously built up. From
>T_1=S to T_2=S+R, the EF queue receives service. Now assume that right
>before the queue is about to be empty, i.e. at time T_2 -e where e<<1,
>another packet starts to arrive the queue. The second will be fully in the
>queue at time
>T_3=S+R-e+S. Now from T_0=0 to T_3=2S+R-e, the EF queue is served for
>T_2-T_1=R (second). Certainly T_3-T_1 is larger than the
>MTU/Port_bandwidth=R, and the queue is not empty during this period of time.
>But if the service rate is measured over this time interval, the percentage
>of bandwidth received by EF queue is
>R/(2S+R-e)=1/(1+2S/R-e/R).
>Assume that e/R<<1, the percentage of bandwidth received by the EF queue
>becomes approximately 1/(1+2S/R). Now with situation of S/R=1, such as in
>routers where one line card can host only one port, only 1/3 of the port
>bandwidth is received by the EF queue.

I was using the standard convention that a packet arrives to the queue when 
its last bit arrives to the queue.
In that case in you example above the queue is technically empty after the 
last bit of the previous packet left, and before the first bit of the next 
packet arrived.

>It seems that the EF service rate should be measured over "practically
>interesting" time scale. Is the time scale of serving a single packet of the
>MTU size the "practically interesting" time scale for EF service, probably
>not.

I think it really depends on what you mean by "practically 
interesting".   If you want to have minimal jitter,  then the smaller the
timescale you can guarantee, the better. If all you want is average 
bandwidth, then you can live with longer timescales.

Regards,
Anna

>Best regards,
>
>Yongdong Zhao
>
>SBC Technology Resources, Inc.
>
>-----Original Message-----
>From: Anna Charny [mailto:[email-masked]]
>Sent: Friday, April 07, 2000 2:34 PM
>To: Shahram Davari; [email-masked]'
>Subject: Re: FW: [Diffserv] EF question !!!
>
>
>Shahram,
>
>At 11:07 AM 4/6/00 -0700, Shahram Davari wrote:
> >"The figure was messed up in previous email. Please use this one:"
> >
> >Hi,
> >
> >RFC-2598 says:
> >"EF SHOULD average at least the configured rate when measured over any time
> >interval equal to or longer than the time it takes to send an output link
> >MTU sized packet at the configured rate"
> >
> >Lets assume 2 PHB queues: an EF and a BE each of rate R (both nicely
> >shaped). Let's assume the output link rate is 2R so that 50% of the link BW
> >(=R) is assigned to EF and 50% (=R) to BE. Let's also assume that packet
> >sizes are all MTU size. Now on the output link we will have EF and BE
> >packets one after another as following:
> >
> >
> >----------------------------------------------------------
> >|  BE   |  EF   |  BE  |  EF  | BE  |  EF  |   .....       |
> >----------------------------------------------------------
> >
> >                 <------------------->
> >                          3T
> >
> >
> >The duration of each packet at the output link is T= MTU/2R. Now assume the
> >time from the beginning of a BE packet to the end of another BE packet;
>this
> >time = 3T (notice that there is only one EF packet in this interval). Also
> >the time to send an MTU size packet at EF configured rate is MTU/R = 2T.
> >
> >Since 3T  > 2T then according to RFC-2598 we should average the configured
> >rate in the 3T interval. But as you can see the average EF rate in the 3T
> >interval is MTU/3T = 2R/3 which is 2/3 of the EF configured rate R.
> >
> >Either I am missing something or there is a problem with the RFC-2598.
>
>It seems to me that in this particular example there is really no actual
>problem, because in the interval of length 3T you consider there  is only a
>single EF packet in the queue, assuming the packets arrive ideally space at
>the rate, as I think you have done.  I think the statement that a queue
>must receive some service X only applies to the case when there are
>actually packets in that queue to send. Otherwise it is impossible in
>principle to guarantee this even if there is just a single EF stream on a
>link with absolutely no contention from BE (That is, just remove BE packets
>in your example - if EF packets arrive ideally spaced, they will also leave
>ideally spaced, since there is no contention, but it would still be the
>case that  there will be intervals of length 3T where only one EF packet
>will be served).
>
>I think that as far as the *total* aggregate of all EF "streams" on a given
>link goes, it does receive the service R (in the case of priority FIFO
>implementation)  over any interval of length MTU/R or longer *as long as
>the EF queue is continuously backlogged during that interval*, and as long
>as rate of EF  does not exceed C/2, where C is the capacity of the link. To
>see this, consider some a busy period (t1, t2) of the EF queue, where t1 is
>the time when the queue changed its state from being empty to being busy,
>and t2 is the first time after t1 when the queue became empty again (we do
>not care here whether t2 is finite or not).  In the case of strict priority
>queueing, the EF queue will be continuously served from time
>t1 <= t3 <=t1 + MTU/C   until the queue becomes empty.  That is because a
>BE packet may be served in the interval (t1, t3).
>
>So for any interval of the form (t4, t5) of length > MTU/R , where
>t3<=t4<=t5<=t2, the EF queue receives the service equal to (t5-t4)C  bits
>which is strictly greater than its ideal service (t5-t4)R that it should
>have received in this interval.  So for any such interval the statement of
>RFC 2598 is correct.
>
>Now consider any interval (t6, t7) such that t1<=t6<=t3 <=t7<=t2. (Note
>that in order for (t6, t7) be  longer than MTU/R,  t7 must be greater than
>t3).  In any such interval the EF queue is continuously backlogged, but  in
>the interval (t1, t3) no EF bits are served.  So the amount of service that
>will be received by the EF queue in the interval (t6, t7) is at least
>(t7-t3)C >= (t7-t6)C - MTU  bits. So the average rate that the EF aggregate
>will get over (t6, t7) is equal to  C - MTU/(t7-t6) >= C - MTU/(MTU/R) =
>C-R >= 2R - R >= R.
>
>Since (t1, t2) is an arbitrary busy period,  this covers all possible cases
>of continuously busy intervals of length MTU/R or greater.
>
>This shows that in any interval of time longer than or equal to  MTU/R  *in
>which the priority queue is continuously  backlogged* AND the EF rate does
>not exceed 50% of the speed of the link, the EF queue does receive its
>average rate R.
>
>Now, as I argued above,  it does not seem reasonable to request that this
>holds for *ANY* interval MTU/R or longer in which the queue is *not*
>necessarily continuously backlogged - as your example shows - so it seems
>that a reasonable thing to do might be to put a clarification in RFC 2598
>that it only requires the rate for "busy" intervals only, and that the 50%
>rate limitation is necessary.  I am not sure what the procedure is of
>updating RFC's , though.
>
>Note that  if the EF queue is not served at highest priority (such as in
>the case of a class-based WFQ scheduler) , the start time of service for a
>busy queue may be longer than MTU/C, which would lead to a tighter than 50%
>limitation on Ef aggregate rate.
>
>Finally,  it seems important to emphasize that while the above is true for
>a total EF aggregate on the link (subject to 50% limitation and the
>requirement that the service is computed over busy periods only) , it is no
>longer true for individual "EF streams" of which the total EF aggregate on
>a link is composed.  Jim Robert's example and Jean-Yves Le Boudec's
>concerns in an earlier  message relate to those "streams", or "edge-to-edge
>aggregates", as discussed in the VW draft.  But RFC 2598 seems to apply
>to  EF BA understood as *total link* EF aggregates, as defined in RFC 2475:
>
>    DS behavior aggregate     a collection of packets with the same DS
>                               codepoint crossing a link in a particular
>                               direction.
>
>I hope this helps.
>
>Regards,
>Anna
>
>
>
>
>
> >Any comments?
> >
> >
> >Shahram Davari
> >Systems Engineer, Product Research
> >PMC-Sierra Inc.
> >555 Legget drive,
> >Suit 834, Tower B,
> >Ottawa, ON K2K 2X3, Canada
> >Phone: +1 (613) 271-4018
> >Fax  : +1 (613) 271-7007
> >
> >
> >
> >_______________________________________________
> >diffserv mailing list
> >[email-masked]
> >http://www1.ietf.org/mailman/listinfo/diffserv
> >Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
> >
> >_______________________________________________
> >diffserv mailing list
> >[email-masked]
> >http://www1.ietf.org/mailman/listinfo/diffserv
> >Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
> >
>
>
>_______________________________________________
>diffserv mailing list
>[email-masked]
>http://www1.ietf.org/mailman/listinfo/diffserv
>Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
>
>_______________________________________________
>diffserv mailing list
>[email-masked]
>http://www1.ietf.org/mailman/listinfo/diffserv
>Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/

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