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

From: Anna Charny <[email-masked]>
Date: Thu, 03 Aug 2000 17:58:58 -0400

Van,

At the meeting in Pittsburgh yesterday, you raised a concern that the 
mathematical definition of draft-charny-ef-definition-00 might allow 
asymptotic loss of EF bandwidth due to the existence of the error (slack) 
term E in the definition.

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)

where a(j) is the time of the j-th arrival, L(j) is the length of the j-th 
departure and R is the configured rate.  If for all j the j-th departure 
occurs exactly at time F'(j), then
rec_1 describes a constant rate server that drains the buffer exactly at 
rate R.   This system obviously guarantees the rate R.

Consider now the definition in draft-charny-ef-definition-00. It says this:

for all j, the time d(j) of the j-th departure must satsify

d(j) <= F(j)+E                ( eq 1)

where  F(j) is given by the recusrion

F(0)=d(0)=0
F(j)=max(a(j), min(d(j-1), F(j-1))+L(j)/R       (rec_2)

Consider now a reference server that serves packets exactly at rate R, and 
for the same arrival pattern  it chooses the same sequence of packets to 
transmit
as the server satisfying  (eq 1)  and (rec 2).  This server will be 
referred to as a constant rate reference server.

Note now that the  "target departure time" F(j)  in (rec 2) occurs no later 
than the corresponding finishing  time F'(j) in the  constant rate 
reference server
given by (rec 1).

That is, for all j

F(j) <= F'(j)                                          (eq 3)

(eq 3)  follows immediately from the fact that   min(d(j-1), F(j-1))<= 
F(j-1) for all j, and can be trivially shown by induction on j.

In turn,  since the actual departure times in a server satisfying the draft 
definition must  satisfy

d(j) <= F(j)+E                                   (eq 4)

(eq 3)  and (eq 4) now  imply that it is also true that

d(j) <= F'(j) + E                                              (eq 5).

(eq 5)  means that for all j  the j-th departure occurs no later than 
within a fixed time E of the corresponding departure in the constant-rate 
reference server.  Since E does not depend on time.  This means that  there 
cannot be any asymptotic bandwidth loss.

Please let me know if you do not find this argument convincing enough - in 
which case please let me know where you see a problem with it.

Regards,
Anna

---------------------------------------
Anna Charny
Cisco Systems, Inc
300 Apollo Drive
Chelmsford, MA  01824
Tel. (978)-244-8172
Fax (978)-244-8126

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

---

From: Van Jacobson <[email-masked]>
Date: Sun, 06 Aug 2000 12:14:58 -0700

> term E in the definition.

Anna, the above is a misrepresentation. I did not say that DEF_1 in
draft-charny-ef-definition had an asymptotic loss of EF bandwidth. I
said almost the opposite: there is a physically plausible scheduler
which exactly conforms to eq. 1 & 2 in your document and can
persistently deliver an average bandwidth less than R and the average
only approaches R asymptotically. Although you have stated that you can
express the intent of RFC2598 much better than any of its authors, I
should point out that waiting an infinite time for a node to deliver its
committed rate is very far from out intent.

A numerical example of the problem follows. For simplicity, take L(j) =
L (constant packet size), L/R = 1 (committed rate of one packet per
clock tick), a(j)=j-1 and E=9 [none of these values are special, they
were just chosen to eliminate irrelevant detail]. Say that the first
packet is sent as soon as it arrives so d(1)=a(1)+L/R=0+1=1. All
remaining packets are delayed by E then sent at the committed rate R.
Since d(j) is the time that the last bit of packet j is sent and the
first bit of the first packet is sent at time zero, the average
delivered bandwidth up to time d(j) is B(j)=j/d(j). For these
conditions, a table of the parameters from DEF_1 in draft-charny-ef,
plus the average bandwidth B, is:

	j	F(j)	d(j)	B(j)
	0	 0	 0	 -
	1	 1	 1	 1
	2	 2	10	0.20
	3	 3	11	0.27
	4	 4	12	0.33
	5	 5	13	0.39
	...
	500	500	508	0.98
	...

After the first packet this system never achieves its committed rate.
The average rate over the first 10 packets is only .5 R and it takes 500
packets for the average rate to get within 2% of the committed value. As
I said in Pittsburgh, this could be a significant problem since none of
the expected uses of EF have infinite duration and many are episodic
with relatively short episodes, such as talk spurts in Voice over IP.
Because of the a(j) term in "F(j) = max(a(j), min(F(j-1), d(j-1))) ..."
from DEF_1 of draft-charny-ef, the timing essentially restarts from zero
at every gap in the arrival stream so each talk spurt would have a
pattern like the above and none would get its correct rate. For typical
voice packet times of 20ms and average talk spurt durations of 10 sec
(500 20ms packets), this says that even with 1 second of playback delay
(jitter buffer) at the receiver, 13% of the first second and 5% overall
gets lost.

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

It's worth pointing out that Le Boudec's F' doesn't have the problem I
described above for your F. 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). 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.

 - Van

---

From: Anna Charny <[email-masked]>
Date: Mon, 07 Aug 2000 00:27:56 -0400

Van,

I am afraid there is a substantial misunderstanding in what you 
wrote.  Please see below for detailed comments.

At 12:14 PM 8/6/00 -0700, Van Jacobson wrote:
>only approaches R asymptotically.

I certainly apologize for any misrepresentation that might have occurred. 
It was not intentional.  I am also aware that many other people in the 
audience thought that
the concern you had was the one I addressed in my previous message.   Part 
of the reason I thought you were concerned about the asymptotic loss of 
bandwidth was that I found it hard to believe that you were actually 
complaining about a one-time loss of bandwidth which is entirely  due to 
the allowed deviation of the device/scheduler from the ideal fluid model, 
which can happen in any of the schedulers listed in RFC 2598...

>Although you have stated that you can

Unfortunately,  whether or not it was the intent of RFC 2598,  temporary 
bandwidth loss is an unavoidable phenomenon
which is due to a non-preemptive scheduler transmitting one or more packets 
from non-EF queues and possibly non-scheduling latency.
Please see more below.

>plus the average bandwidth B, is:

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.

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.

>reference it and use its terminology and constraints in the EF

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.

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

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

---

From: Jon Crowcroft <[email-masked]>
Date: Mon, 07 Aug 2000 09:26:52 +0100

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

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

 >>with the rate-latency curve.

 cheers

   jon

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Mon, 7 Aug 2000 10:08:48 -0400 (EDT)

> anyhow, i don't understand this sort of stuff, so i will now go on vacation....

In none of the examples there is asymptotic loss of 
bandwidth if a service equal to the arrival rate
is offered to the queue. Remember, we can not serve
faster than what receive.

If the arrival traffic has rate less than R, then the
rate will be provided after some latency. i.e., in 
Vans example if you start counting after time 9,
you will get rate of 1. Remember, the latency is an
one time hit, and that's the way you are supposed
to count. 

If the arrival traffic has rate exactly R (or greater),
then queues will build up and they will extend the
busy period of the system. As a result, the offered
service will match the committed service. 

I particular, for the example, with spurs of voice traffic,
I don't agree that the behavior is wrong. If the 
aggregate bandwidth of the spurs of voice traffic
becomes close to R, the queues will build up,
the busy periods between spurs of traffic will be
concatenated because of the latency, and the 
committed rate will be offered for the concatenated
busy periods, thus matching the requirements. 

If the bursts of voice traffic are far appart,
the model will only create some extra jitter. 

Dimitri

---

From: Anna Charny <[email-masked]>
Date: Mon, 07 Aug 2000 11:01:36 -0400

Jon,

Please see below...

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

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

>anyhow, i don't understand this sort of stuff, so i will now go on 

Have a good vacation,
Anna

---

From: Jon Crowcroft <[email-masked]>
Date: Mon, 07 Aug 2000 16:49:03 +0100

>>examples I gave in my previous message).

you can't offer differentiated services between a flow occupying 100% of a link and
other flows, so lets leave this one aside.
 
 >>catch up for any configured rate smaller than link speed).

yes, use it or lose it.
 
 >>the straight line with slope R shifted to the right by E).

ah, i see where the confusion is coming from - 

If you have already determined the delay bound for the call, sure, you can't catch
up. but say you are in the process of deciding it: then you can choose to allow for
more interleaves, and therefore more jitter and warn the receiver to use a larger 
playout....

i.e. we have a dynamic adaptive delay bound service...in terms of thhe set of
users, but a specific delay bound for any guiven specific user (call/flow)

ah well, off to the airport...

cheers

jon

---

From: Anna Charny <[email-masked]>
Date: Mon, 07 Aug 2000 12:37:43 -0400

Jon,

In case this still catches you :-)

>other flows, so lets leave this one aside.

Actually, you can, if you are assuming that on the average you will 
actually have less EF traffic than full link speed, but occasionally you 
can in fact get
lots of EF "talk spurts" at the same time.  Then, by setting EF configured 
rate to 100% and running the rest at lower priority you can fill in the 
link with BE
traffic when there is something left to fill in (which is probably most of 
the times), but let Ef traffic take advantage of full link speed when it is 
there.  part of the confusion here is simply due to the usage of the word 
"configured rate". I have been using it as the rate that must be guaranteed 
by the scheduler to EF traffic when it is there - the input rate does not 
have to be as high.  But even if your average input rate is smaller than 
link speed, you can still get enough of a burst that you can in fact send 
it at link speed for a while. In that case, no matter how long that burst 
is you cannot catch up on your *configured* rate while your EF queue is 
busy (certainly you cannot hope to achieve it averaged over a longer time, 
since you do not have enough input to sustain it).

>  >>catch up for any configured rate smaller than link speed).

Quite so.  This was also raised by Dimitri's message earlier today.

>users, but a specific delay bound for any guiven specific user (call/flow)

I understand that you can avoid knowing the exact bound on latency by 
allowing more jitter - but just exactly how much you need *in the worst 
case* you will not really know.  Sure, you can try to determine it 
experimentally, which is OK, but that will be difficult to express in a 
mathematical definition  that is intended to facilitate worst case 
analysis, such as intended in the VW draft.  So I think these are all valid 
points, but not in the context of a definition suitable for deterministic 
worst case analysis.  If we choose to depart from this deterministic worst 
case requirement, other approaches become possible. But I do not think that 
we as a group decided that such departure is what we want?  In the meantime 
the definition we gave accounts for the worst case latency which is *known* 
for a given device....   Or did I misunderstand what you are trying to say?

>ah well, off to the airport...

Have a safe flight,
Anna