Subject: [Diffserv] EF question !!!

From: Shahram Davari <[email-masked]>
Date: Thu, 6 Apr 2000 10:54:15 -0700

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.

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/

---

From: Anna Charny <[email-masked]>
Date: Fri, 07 Apr 2000 12:33:32 -0700

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:
>----------------------------------------------------------
>----------------------------------------------------------
>
>                 <------------------->
>                          3T
>
>

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

---

From: Shahram Davari <[email-masked]>
Date: Mon, 10 Apr 2000 06:30:30 -0700

Hi Carlo,

Apart from the little mistake that I had in my 2nd example, I think I prefer
Anna's 
explanation:

"EF should average its configured rate over any interval greater 
than the time that takes to send an MTU size packet with configured rate,
provided
that the EF queue is not empty" 

Because it can explain the rule even when the configured EF rate is higher
that the actual EF
rate. Probably the second part of the sentence: "... provided that the EF
queue is not empty" 
is implicit in RFC-2598!

Regards,

-Shahram 

>-----Original Message-----
>From: Carlo Matarasso [mailto:[email-masked]]
>Sent: Friday, April 07, 2000 12:27 PM
>To: Shahram Davari
>Cc: [email-masked]'; Anna Charny
>Subject: Re: FW: [Diffserv] EF question !!!
>
>
>Shahram,
>my observation is that the output signal is periodic with 
>period = 2T. Averages
>should be made on time intervals that are integer multiple of 
>its period
>(2T,4T,6T.....).
>
>regarding your second example, again you have a periodic 
>signal with period =
>10T, so correct time intervals are, in my opinion, 10T, 20T.....
>Let me also point out that in your second example you write
>
>"The interval of each packet in output link is T=MTU/10R"
>
>then you write
>
>"MTU/2R = 4T"
>
>but if T=MTU/10R then MTU/2R = 5T
>
>but if you consider 5T you violate the Nyquist principle and 
>you get aliasing in
>your result.
>
>again I think that only 10T, 20T...... give significant results.
>
>please correct me if I'm wrong !
>
>have a nice weekend
>
>Carlo
>
>
>Shahram Davari wrote:
>
>> Hi Carlo,
>>
>> I don't understand what you mean by "the time interval 
>should be independent
>> from its position in time?". Do you mean that I should slide the time
>> interval and average it over all the time scale? That 
>doesn't make sense
>> because by doing so you will get your configured rate 
>whether you use EF or
>> not!
>>
>> This example may be solved by requiring a "multiple" of the 
>time that it
>> takes to send an MTU size packet (as you and Siamak also 
>have mentioned).
>> But here is another example where the "multiple" requirement 
>won't help
>> either:
>>
>> Assume "2" EF flow each having a rate of "R" and one BE flow 
>having a rate
>> of "8R". Assume that the output link rate is "10R" to 
>accommodate these
>> flows. Further assume that all packets are of MTU size and 
>the EF flows are
>> shaped and exactly identical. Now using priority queuing (as 
>suggested by
>> RFC-2598) and looking at the time scale, we will have:
>>
>> <--------------------------- time increase ----------------
>>
>> BE-BE-BE-BE-BE-BE-BE-BE-EF-EF-BE-BE-BE-BE-BE-BE-BE-BE-EF-EF
>> <---------------------><---->
>>          8T              2T
>>
>> The interval of each packet in output link is T=MTU/10R. The 
>time that it
>> takes to send an MTU size packet at the EF configured rate 
>is MTU/2R = 4T.
>> Since the interval 8T shown in the picture is greater than 
>4T, according to
>> RFC-2598 we should get at least the EF configured rate. But 
>as you can see
>> there is no EF packet in this interval!!! (also note that 8T 
>is a multiple
>> of 4T).
>>
>> Regards,
>>
>> -Shahram
>>
>>
>>
>> >-----Original Message-----
>> >From: Carlo Matarasso [mailto:[email-masked]]
>> >Sent: Friday, April 07, 2000 3:36 AM
>> >To: Shahram Davari
>> >Cc: [email-masked]'
>> >Subject: Re: FW: [Diffserv] EF question !!!
>> >
>> >
>> >Shahram,
>> >
>> >when you calculate average values in steady state, the time
>> >interval you
>> >consider has to be independent from its position on the time
>> >axis. Yours is not:
>> >if you take the 3T interval right after yours, you' ll have 2
>> >EF MTU and 1 BE,
>> >that will even up the previous average.
>> >In you example you have to consider an interval that contains
>> >an evan amount of
>> >Ts.
>> >
>> >If you consider int. = 6T, in this interval the EF rate is
>> >3MTU/6T = MTU/2T = R
>> >
>> >Carlo
>> >
>> >Shahram Davari wrote:
>> >
>> >--
>> >---------------------------------------------------------------
>> >----------------------------
>> >
>> >DOTT. ING. CARLO MATARASSO
>> >
>> >[email-masked]
>> >TEL. +49 8153 28 2848
>> >FAX  +49 8153 28 2844
>> >
>> >DLR - DEUTSCHES ZENTRUM FUER LUFT UND RAUMFAHRT
>> >GERMAN AEROSPACE CENTER
>> >www.dlr.de
>> >POSTFACH 1116
>> >D - 82230   WESSLING - GERMANY
>> >
>> >---------------------------------------------------------------
>> >----------------------------
>> >
>> >
>> >
>> >
>--
>---------------------------------------------------------------
>----------------------------
>
>DOTT. ING. CARLO MATARASSO
>
>[email-masked]
>TEL. +49 8153 28 2848
>FAX  +49 8153 28 2844
>
>DLR - DEUTSCHES ZENTRUM FUER LUFT UND RAUMFAHRT
>GERMAN AEROSPACE CENTER
>www.dlr.de
>POSTFACH 1116
>D - 82230   WESSLING - GERMANY
>
>---------------------------------------------------------------
>----------------------------
>
>
>
>

---

From: "Zhao, Yongdong" <[email-masked]>
Date: Mon, 10 Apr 2000 17:32:59 -0500

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.

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.

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,

I hope this helps.

Regards,
Anna

---

From: Anna Charny <[email-masked]>
Date: Mon, 10 Apr 2000 19:18:34 -0700

Hi,

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

>MTU size the "practically interesting" time scale for EF service, probably

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