Re: [Diffserv] about the concern of a rate loss in the definition ofdraft-charny-ef-definition-00

[Anna Charny <[e-mail]>]

Jon,

Please see below...

At 09:26 AM 8/7/00 +0100, Jon Crowcroft wrote:

>In message <[e-mail]>, Anna 
>Charny typed:
>
>  >>It is certainly true that the above behavior is acceptable for a 
> scheduler
>  >>with E=9 under definition of draft-charny-ef-definition-00.
>I would like to point out once again that for ANY  non-preemptive scheduler
>  >>with a given E you cannot avoid this temporary loss for the committed 
> rate
>  >>your chose in your example.   For instance, the exact transmission 
> pattern
>  >>you give in your example can be seen in a WRR scheduler with 10 queues.
>  >>Assume Ef packets arrive at times 0, 1+, 2,3,  while a single packet of
>  >>each of 9 non-EF queues arrives at time 1-;  which causes the scheduling
>  >>order just as in your example for any rate assignments of the 10 queues.
>
>anna,
>
>i think there's something very wreong about this - i can't put my finger 
>on it, but
>let me point out that if you have an admission test (or provcisioning 
>rule) for a
>diffeserv class, then the FIRST thing it must do is pass for the average rate.

I think we have established in our previous exchange with Van that no 
asymptotic rate loss occurs. So that is OK. The next, crucial, question is
over what interval can you expect to get the *exact* configured rate, if 
you do not impose any constraints on that rate?
That interval depends on the configured rate and E.  As your configured 
rate tends to link speed, regardless of E the interval over which you can 
recover your rate
after even a single missed packet transmission opportunity goes to 
infinity. In the example above, as long as the configured
rate is approaching the link speed, you can only hope to recover the rate 
asymptotically. A test that intends to measure the average service rate in 
the interval (0,t) will then  have to look at asymptotically long intervals 
to decide that in fact everything is fine.  Or, you could allow an error 
term that would be valid for any finite interval, and then run your test on 
whatever intervals you choose.

>this means that the average interarrival time for packets is also 
>respected, but
>that we can work ahead or lag behind, (depending on work conservation or not)
>
>the confusion here seems to be about what happens if we fall behind - we 
>don't stay
>behind unless the other traffic persistently just leads rather than a random
>sequence of permutations of interleaves, effectively alternating
>leading and lagging the arrival of the EF class...

Please correct me if I am wrong, but I think what you are saying here is 
that a scheduler is supposed to be able to catch up for lost
service opportunities by sending Ef traffic faster at some later 
point.   The problem is that there are 3 legitimate cases I can think of 
that would NOT allow you to catch up on the rate after such lost 
service.  Since these cases appear to be totally legitimate and realistic 
(at least to me they do), it seems that they should be accounted for by the 
definition (as they indeed are, in either DEF_1 or rate-latency curve 
DEF_2).  These three cases are considered below.

1) You cannot possibly catch up on your configured rate after missing even 
one packet time  if your configured rate is link speed (as in the PQ 
examples I gave in my previous message).

  For any configured rate strictly less than link speed,  as long as the 
input is not smaller than the configured rate, PQ will catch up over
a finite interval of time. That interval, however, asymptotically goes to 
infinity as the configured rate approaches full link speed.

For the WRR example above, if configured rate is asymptotically close to 
link speed, the rate recovery is possible only over asymptotically long 
time intervals as well.
For configured rates smaller than link speed rate recovery is possible 
(assuming input rates of all queues are not overbooked), but the recovery 
time is a function of both E and the relative rates in the scheduler, and 
hence can still be very large.

2) You cannot possibly catch up with configured rate if the input rate is 
smaller than configured rate.  In the case of PQ, if the input rate is 
strictly less than the configured rate, then the EF queue drains between 
"talk spurts", which is what makes it possible to suffer the delay of  E at 
the beginning of each talk spurt.  (On the other hand, if the input rate is 
equal to the  configured rate, then delay due to non-EF packet transmission 
will eventually cause the standing queue, and the scheduler will indeed 
catch up for any configured rate smaller than link speed).

3) You cannot possibly catch up if the delay of E is due to internal 
(variable) non-scheduling latency of the device  (such as the delay through 
a multistage switching fabric).  In that case even if your input rate is 
exactly equal to the configured rate (even if the latter is strictly 
smaller than link speed) all or some of  your packets may still show up on 
the output  as being delayed by E (or, equivalently, the plot will be above 
the straight line with slope R shifted to the right by E).

All of these cases are legitimate real world scenarios that both the 
rate-latency server and DEF_1 of draft-charny-ef-definition-00 account 
for.  That is why the behavior described by Van is indeed possible under 
either of these definitions.  Which to me seems like a good rather than a 
bad thing.


>so what we are looking at is the 2nd moment of the arrival processes - 
>necessarily,
>this is constrained, (otherwise ALL scheudles for all schedulers will fail the
>first hurdle) - what's the most general form of the constrait? well, that 
>the 2nd
>moment is 2nd order.......
>
>so what does this mean about the math? well, i think it means you need to 
>revisit
>the model with some assumption about the traffic sources.....i..e there's 
>a missing
>constraint on the arrival process (think of it as plausible deniability 
>for now:-)
>anyhow, i don't understand this sort of stuff, so i will now go on 
>vacation....

Have a good vacation,
Anna

>  >>The same phenomenon is possible with  PQ, for which E=1 (in your
>  >>units).  To see this, consider the case when the first Ef packet 
> arrives at
>  >>time zero and is immediately sent because there is no non-Ef traffic 
> in the
>  >>router. At time 1-, right before the first Ef packet is fully 
> transmitted,
>  >>a non-Ef packet arrives, and the second EF packet arrives at time 1+,
>  >>immediately after the non-EF packet starts its transmission at time
>  >>1.  Therefore, the second packet is delayed by time 1-, so the 
> transmission
>  >>of EF packets now will be at times 1,3,4,5..., and hence again only one
>  >>packet goes in the interval (0,2), and so the configured rate is attained
>  >>only asymptotically....
>  >>
>  >>As you can see, the fact that you can only get the desired rate
>  >>asymptotically has nothing to do with the definition of
>  >>draft-ef-definition-00. Rather, it follows from the fact that all
>  >>non-preemptive schedulers deviate from the ideal constant rate "fluid" 
> server.
>  >>
>  >>Note that all of these examples demonstrate the asymptotic rate loss 
> simply
>  >>because the configured rate is chosen to be sufficiently high.  All of
>  >>these examples can be made to get the configured rate at timescales of
>  >>packet time at configured rate or larger, as long as we add the 
> restriction
>  >>that R<1/(E+1)  is introduced (e.g. 50% of link speed for PQ,  10% of 
> link
>  >>speed for your initial example).  There is nothing in our definition that
>  >>disallows any additional rate restrictions, if there is any need to have
>  >>them. However, we do not impose any restrictions a priori, since these
>  >>restrictions may not always be necessary to obtain the desired jitter 
> bounds.
>  >>
>  >>Finally note that all these examples can be repeated for any "talk spur".
>  >>For example, a PQ can delay *every* talk spur by one packet time at link
>  >>speed, as long as there  is a gap between talk spurs long enough to drain
>  >>the EF queue.  Likewise, the example you give can be recreated for each
>  >>"talk spur" with WRR (an in fact many of the WFQ implementations) as
>  >>well.  Hence, it is not a property of our definition, but rather a 
> property
>  >>of the schedulers you listed as compliant in RFC 2598.
>  >>
>  >>
>  >>> > Here is  a reasonably simple argument why it cannot be so.
>  >>> >
>  >>> > Consider  a recursion given by
>  >>> >
>  >>> > F'(0)=0;
>  >>> > F'(j)=max(a(j), F'(j-1))+L(j)/R     (rec_1)
>  >>>...
>  >>>
>  >>>The rest of your note appears to be a detailed derivation of why
>  >>>something that I never said is incorrect. Since there are many things
>  >>>I've never said and many of them are indeed incorrect, further
>  >>>discussion isn't warranted. However I should note that you don't need to
>  >>>quote large excerpts from Jean-Yves Le Boudec's papers just for my
>  >>>benefit. Although I am not as familiar with them as I would like to be,
>  >>>I have always found his writing to be lucid and his reasoning concise
>  >>>and I have had occasion to read his Network Calculus & Min-Plus papers
>  >>>several times over the past few years. Had I been aware of his recent
>  >>>work with Chang, Cruz & Thiran on constrained traffic regulation back in
>  >>>98 when we wrote the draft that became RFC2598, I would have tried to
>  >>>reference it and use its terminology and constraints in the EF
>  >>>definition.
>  >>
>  >>Well, actually, none of what I was writing to you was actually in the
>  >>papers you mention, since I was only addressing DEF_1
>  >>of draft-charny-ef-definition-00 which is *not* discussed in any of the
>  >>quite distinguished work you mention above.
>  >>
>  >>>It's worth pointing out that Le Boudec's F' doesn't have the problem I
>  >>>described above for your F.
>  >>
>  >>I am assuming that by "Le Boudec's F' " you mean the rate-latency curve
>  >>(since I doubt you refer to an ideal fluid scheduler that way) and by 
> "your
>  >>F" you mean DEF_1 in draft-charny-ef-definition-00, on which Jean-Yves Le
>  >>Boudec also happens to be a co-author.   But  you are quite 
> mistaken:  the
>  >>example you give is a perfectly feasible output for the rate-latency 
> curve
>  >>as well.   The point you seem to be missing is that the rate-latency 
> curve
>  >>also has a latency term similar to that of DEF_1.  That is, while the
>  >>target  F's of the rate-latency  curve are indeed computed according 
> to the
>  >>finishing times of the ideal fluid scheduler, the packet transmissions 
> are
>  >>allowed to be within a fixed latency term of those target F's.  DEF_2  in
>  >>draft-charny-ef-definition-00 is equivalent to the rate-latency curve
>  >>(please see reference [4] in the draft). In fact, as we mention in
>  >>draft-charny-ef-definition-00,  DEF_1 is a stronger definition than the
>  >>rate-latency curve in the sense that any behavior legal under DEF_1 is 
> also
>  >>legal under the rate-latency curve.  A simple intuitive reason for 
> that is
>  >>that the deadline for packet transmission under DEF_1 is never later than
>  >>the deadline for the same packet in the rate-latency curve.
>  >>
>  >>>  If one plots a sequence of sends with 'bits
>  >>>sent' on the y axis & d(j) (time send completed) on the x axis, his F'
>  >>>condition that you reproduced above says that all points the trajectory
>  >>>traced by the sends must be on or above a line of slope R passing
>  >>>through the origin (first bit of first send).
>  >>
>  >>No, you are mistaken again.  The rate-latency curve ensures that the
>  >>plot  is above the line of slope R
>  >>shifted by latency E to the right.  You seem to be confusing the
>  >>rate-latency curve with the ideal constant rate "fluid" server.
>  >>The straight line  that goes through the origin corresponds to an ideal
>  >>fluid server which is unattainable in practice for any non-preemptive
>  >>scheduler.
>  >>
>  >>>Since the average
>  >>>bandwidth up to and including some send is just the slope of a line from
>  >>>the origin to the point representing that send, if all points are above
>  >>>the slope R line then the average bandwidth is always >= R. In the
>  >>>graphical depiction of your equations that I showed in
>  >>>Pittsburgh, the core problem with your F seemed to be that it allowed
>  >>>points to be as much as E*R below the slope R line and the average
>  >>>bandwidth up to any of those points would be < R. Since your definition
>  >>>allows all but the first point to be below the R line, it allows entire
>  >>>trajectories that never achieve their committed rate.
>  >>
>  >>As I have argued above,  your complaint is not about the definition, but
>  >>rather about the fact of life that all non-preemptive schedulers cannot
>  >>deliver ideal "fluid" service rate at all times. Both the rate-latency
>  >>curve and  the definition DEF_1of draft-charny-ef-definition-00 simply
>  >>capture this phenomenon in a formal way.  The difference between the
>  >>rate-latency curve and DEF_1 is that the rate-latency curve allows large
>  >>service gaps following  faster-than-configured rate service, while DEF_1
>  >>does not "punish" EF for earlier faster service and insists that EF is
>  >>given at least its configured rate at a smaller time scale than possible
>  >>with the rate-latency curve.
>  >>
>  >>Regards,
>  >>Anna
>  >>
>  >>
>  >>>  - Van
>  >>>
>  >>>_______________________________________________
>  >>>diffserv mailing list
>  >>>[e-mail]
>  >>>http://www1.ietf.org/mailman/listinfo/diffserv
>  >>>Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
>  >>>
>  >>
>  >>
>  >>---------------------------------------
>  >>Anna Charny
>  >>Cisco Systems, Inc
>  >>300 Apollo Drive
>  >>Chelmsford, MA  01824
>  >>Tel. [phone]
>  >>Fax [phone]
>  >>
>  >>
>  >>_______________________________________________
>  >>diffserv mailing list
>  >>[e-mail]
>  >>http://www1.ietf.org/mailman/listinfo/diffserv
>  >>Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
>  >>
>
>  cheers
>
>    jon
>
>
>_______________________________________________
>diffserv mailing list
>[e-mail]
>http://www1.ietf.org/mailman/listinfo/diffserv
>Archive: http://www-nrg.ee.lbl.gov/diff-serv-arch/
>


---------------------------------------
Anna Charny
Cisco Systems, Inc
300 Apollo Drive
Chelmsford, MA  01824
Tel. [phone]
Fax [phone]


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