Subject: RE: [Diffserv] about the concern of a rate loss in the definitio n ofdraft-charny-ef-definition-00

From: "Casati, Alessio (Alessio)" <[email-masked]>
Date: Mon, 7 Aug 2000 08:21:57 +0100

OK, let's give a shot with a quotation:

	As far as the laws of mathematics refer to reality, they are not
certain; 
	and as far as they are certain, they do not refer to reality. 

-- Albert Einstein 

Both Anna and Van are trying to
converge (aymptotically) on agreeing 
that the first part 
of the quotation or the second is true.

PS Do you like this, John?

> ----------
> From: 	Anna Charny[SMTP:[email-masked]]
> Sent: 	07 August 2000 05:27
> To: 	Van Jacobson
> Cc: 	[email-masked]
> Subject: 	Re: [Diffserv] about the concern of a rate loss in  the
> definition  ofdraft-charny-ef-definition-00
> 
> 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:
> >Anna Charny wrote:
> > > 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.
> >
> >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.
> 
> 
> 
> 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
> >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.
> 
> 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.
> 
> >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.
> 
> 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.
> 
> 
> > > 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
> >[email-masked]
> >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. (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/
> 

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

---

From: [email-masked]
Date: Tue, 8 Aug 2000 14:08:03 +0200

Anna Charny wrotes

>which can happen in any of the schedulers listed in RFC 2598...

Well the point still seems to be that RFC 2598 intends to define EF PHB by measuring
the output of the hop which is not precise enough for obtaining a correct implementation
as observed by the authors of draft-charny-ef-definition-00. On the other hand
draft-charny-ef-definition-00 defines EF by constraining the behavior of the scheduler,
whereas how to measure the EF PHB of a particular hop is only given implicitly.

We may be able to unify both by redefining the EF behavior in a way such that
1) it suggests at least one precise and explicit method of measurement.
2) it is possible to be implemented by using all the schedulers indicated in 
   draft-charny-ef-definition-00.
3) it meets the intention of RFC 2598.

Lets consider an application such as VoIP where we wish to read out the bits
from a buffer of a certain size at a certain rate at the receiver. Assume that
the DS domain has only to carry a single data stream for VoIP, a VoIP receiver
can work correctly if for the data stream arriving at each downstream node,
the same constraints for the buffer size and read-out-rate are satisfied.
So lets suggest the following modification for an explicitly measureable EF definition:

Let R be the bit rate in bits/s and B the buffer size in bits. An EF PHB (R,B) is given
if the given DS aggregate at the output link (or arriving downstream node)
can pass through the Leaky Bucket (R, B)and
B(0)=0 without loss of bits. R is the guaranteed bit rate and B the jitter bound.

As it is pointed out in PDB-VW-draft Certain Invariance Property is very important
with respect to Aggregation. The above definition can clearly be applied recursively and
thus results in the invariance of the properties (R, B) over a DS domain.

Advantages seem to be:
- The Problem of Addressing the start and end time of arrival and departure is avoided.
- It is more explicit for measurements and for creating DS services.
- It does not say any thing about implementation (how to aggregate ingres traffic, which
internal delay, which scheduler, whether simulating GPS or not).

It can be shown that if (R, B) is properly specified, any scheduler from RFC 2598
and draft-charny-ef-definition-00 can be used. EF with (R, 2* MTU) seems to 
cover the intended Behavior of the current RFC 2598. 

- Xiaoning Nie

---

From: Anna Charny <[email-masked]>
Date: Tue, 08 Aug 2000 14:50:57 -0400

Xiaoning,

Please see some comments  below:

>thus results in the invariance of the properties (R, B) over a DS domain.

The problem that I see with your approach is that whether or not an EF 
aggregate can pass through a token bucket with a given B very much
depends on what that EF aggregate looks like at the input to that 
output.   While it is pretty clear what EF traffic looks like at the 
ingress edge (i.e. it is ideally shaped
on each ingress link to some negotiated rate), it is much less clear what 
it looks like as it traverses a multi-hop DS cloud.  In particular, it is 
actually unknown how to deterministically achieve the desired property  of 
invariance under aggregation in a general topology network, unless EF 
utilization factor is very small. Please
see more on that below.

First of all, it seems clear that in the very least that B must be at least 
of the order of the number of inputs, since one EF packet may arrive from 
each input at the same time and all these packets have to be buffered 
somewhere. So your suggestion (below) on choosing B=2MTU does not appear to 
work.   Suppose however,  that you do take B equal to some number N xMTU 
(where N is the total number of inputs or some other number).  Suppose one 
packet arrives from each input simultaneously, and they all just leave 
the  output immediately one after another.  Then the burst at the output 
link  will be equal to N.  If you now take N of such routers, and bring 
their outputs together
as inputs to a "second-level" router, then what you will see is that the 
total burst coming to that second-level router is (N^2)xMTU, since now N 
back-to-back packets are coming from each of the N  inputs. (Of course we 
must ensure that no link is overbooked, so we must assume that the rate of 
each individual EF "flow" is less than R/(N^2).  Assuming all links are the 
same speed,  that means that N^2-N packets must be buffered at such second 
hop (because while N packets fully arrived on each of N inputs, at most N 
packets could have left the output), so B=NxMTU is no longer sufficient at 
the second hop.

This example may seem to suggest that we can just pick B=N^h, where h is 
the max number of hops and N is the maximum fan-in of all 
routers.  Unfortunately, even that is not the case, since we also must 
account for accumulation of jitter of a single flow (note that in the 
example above there was just a single packet per "flow" - just many flows, 
each contributing a single packet to a burst).   An example of a network 
where all links are utilized by EF traffic at most up to a desired fraction 
alpha, where no EF "flow" traverses more than h hops, and where all 
schedulers are PQ, in which jitter accumulates in proportion with 
(1+alpha)^h can be found in 
ftp://ftpeng.cisco.com/ftp/acharny/aggregate_delay_v4.ps.  This jitter 
accumulation effect may cause more than one packet per "flow" contributing 
to a single burst.
While there are some known results that do allow bounding this jitter 
accumulation in a general topology network, these results hold for quite 
small EF utilization factors (see 
ftp://ftpeng.cisco.com/ftp/acharny/qofis2000.ps) To the best of my 
knowledge it is not known how to limit the effect of jitter accumulation 
for larger utilization factors in general topology networks.    This effect 
of jitter accumulation makes it very difficult to ensure the desired 
"invariance under aggregation"  other than in very simple topologies with 
small hop count, or for rather small EF utilization factors.  In the 
context of your proposal, it also makes it very difficult to figure out 
just exactly how to choose the parameters of the token bucket so that no 
loss indeed occurs inside the network.

One other approach might be to reshape EF traffic at each hop. Then at 
least all inputs in the network would look the same, and indeed having the 
same token bucket at all hops would indeed become possible.  But requiring 
per hop reshaping would immediately outlaw all work-conserving schedulers, 
including PQ, WFQ, etc. This does not seem to be an acceptable approach for 
a definition, since it imposes too strict a constraint on scheduling 
implementations.

So it seems to me that your proposal has a number of open issues with it 
that need to be addressed before it can become a viable definition candidate.

>- The Problem of Addressing the start and end time of arrival and 

just a question - what is the *problem* that you see with looking at the 
time of arrival and departure?

>- It is more explicit for measurements and for creating DS services

Actually, I am not that the fact that your definition does not tell us 
anything about implementation is good, because at the moment, (as I 
mentioned above) to the
best of my knowledge, it is actually not known at all how to achieve the 
desired property in your definition for a general topology network where 
each flow traverses several hops, and the schedulers are work-conserving, 
unless EF utilization factor is very small.  So some hint on how to 
achieve  the desired behavior deterministically with some known schedulers 
expected to deliver EF (such as PQ, for example) would in fact  be not a 
bad thing to have :-)

Regards,
Anna

---

From: Jon Bennett <[email-masked]>
Date: Wed, 9 Aug 2000 10:02:04 -0400

xiaoning,

There seems to be a rather significant problem with what 
you are proposing.

> Let R be the bit rate in bits/s and B the buffer size in 
> bits. An EF PHB (R,B) is given if the given DS aggregate 
> at the output link (or arriving  downstream node)
> can pass through the Leaky Bucket (R, B)and B(0)=0 without 
> loss of bits. R is the guaranteed bit rate and 
> B the jitter bound.

Under this definition as long as a router does not drop any 
packets it can delay them for as long as it wants, putting
arbitrarily large gaps in the output packet stream. This
would not seem to be form of behavior desired for the EF PHB.

jon

---

From: Shahram Davari <[email-masked]>
Date: Wed, 9 Aug 2000 11:33:59 -0700

Xiaoning,

In a router with more than 2 inputs, potentially an EF packet could have a
jitter of > 2MTU. It follows from your definition of EF (B=2MTU) that we
can't have a router which has more than 2 inputs. Which is a significant
restriction.

Regards,
-Shahram 

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]]
>Sent: Tuesday, August 08, 2000 8:08 AM
>To: [email-masked]; [email-masked]
>Cc: [email-masked]
>Subject: AW: [Diffserv] about the concern of a rate loss in the
>definitio n ofdraft-charny-ef-definition-00
>
>
>
>
>Anna Charny wrotes

---

From: Jon Bennett <[email-masked]>
Date: Thu, 10 Aug 2000 09:12:47 -0400

Xiaoning,

> Right. Thanks for pointing out this. EF PHB should somehow to sustain
> the promised rate even if a lasting pause follows the last packet.
> Lets add the following:

I was not referring to a gap caused by the 'last packet' but to a 
gap caused by the fact that you definition specifies an UPPER bound
on the rate, whereas all other discussions of the EF PHB have specified 
a LOWER bound on the rate.

> ... If buffer content size B(k) at time k becomes zero,
> there must be no to be departed packet of the aggregate 
> remaining in the node.

I can not understand what you mean to say here, you appear to be
using B as both the leaky bucket burst size and as a measure of 
the buffer occupancy of the node. But neither of these uses makes
sense when you state that B(k)=0 -> no packets in the node. 
Perhaps you could (a) clarify which use of B you meant, and 
(b) restate this comment so that it is clear what you mean.

> At least this still seems to be measurable.

My point was that it appears that what it measures is
not something which is useful to measure.

jon

---

From: Shahram Davari <[email-masked]>
Date: Thu, 10 Aug 2000 07:38:46 -0700

Xia,

I think you are confusing something. B is in bytes, therefore when your
token bucket has a depth of B=2MTU, it means that independent of you rate R
(R < C) you can't accept 3 back-to-back EF packets. What you are suggesting
is that we can't have 3 back-to-back EF aggregate packets at any interface,
right?

This has nothing to do with 2MTU/R jitter or VW-PDB.

Regards,
-Shahram

>Sent: Thursday, August 10, 2000 5:20 AM
>To: [email-masked]
>Cc: [email-masked]; [email-masked]
>Shahram,
>Do you want to say that you can not find ANY scheduler which lets
>the EF packet jitter less than T = 2MTU/R if your Router has > 
>2 inputs?
>
>If I understand correctly, the VW PDB draft by Van et. proved 
>the opposite.
>
>Note that the spirit of the DS suggests to define PHB only 
>with respect to
>the traffic AGGREGATE, not to each flow within the Aggregate.  
>
>
>Regards,
>-Xiaoning
>