Subject: RE: [Diffserv] Comments on draft-charny-ef-definition-00

From: Shahram Davari <[email-masked]>
Date: Tue, 25 Jul 2000 14:39:36 -0700

Hi Kathy,

I hope you could at least reply to this email. I won't go to the details
now, but just want to make things clear. Are you suggesting that the
following EF statements are fine an implementable?

"the departure rate of the aggregate's packets from any diffserv node MUST
equal or exceed a configurable rate".

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

If so, why don't you explain how these statements apply to the examples in
section 1.2.1, 1.2.2 of Charney draft, and show that they are indeed EF
conformant.

Regards,
-Shahram

>-----Original Message-----
>From: Kathleen Nichols [mailto:[email-masked]]
>Sent: Tuesday, July 25, 2000 1:25 PM
>To: [email-masked]
>Subject: [Diffserv] Comments on draft-charny-ef-definition-00
>
>
>
>We are posting as co-authors of RFC 2598, An Expedited 
>Forwarding PHB. We got two things from draft-charny-ef-definition: 
>first, that there are some things in 2598 that are open to 
>misinterpretation that should be clarified and, second, that 
>the 13 co-authors of this draft have a rather different PHB 
>in mind from what we intend with the EF PHB. The PHB they 
>describe will not suffice for the VW PDB that can be used 
>for circuit replacement. It is certainly reasonable for the 
>document's co-authors to define a different PHB and  the PDB(s) i
>n which they believe it will be useful, but the "Expedited 
>Forwarding" name and EF abbreviation is already taken by a
>different behavior.
>
>Major points:
>
>1. About the definition:
>
>We found that draft-charny omits an important part of the EF PHB
>definition from RFC 2598. Here is what we actually said:
>
>   "The EF PHB is defined as a forwarding treatment for a particular
>   diffserv aggregate where the departure rate of the aggregate's
>   packets from any diffserv node MUST equal or exceed a configurable
>   rate.  The EF traffic SHOULD receive this rate independent of the
>   intensity of any other traffic attempting to transit the node.  It
>   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."
>
>We assumed this definition would be interpreted in the context of the
>RFC's preceding section which has a lengthy discussion of how 
>jitter and
>loss
>come from queues and queues come from input/output rate imbalance. The
>variety of interesting interpretations of this definition given on the
>diffserv mailing list, culminating in draft-charny, suggests this
>assumption was flawed. At the risk of obscuring a simple idea with
>opaque mathematics, here is a more formal description:
>
>A router is a device for moving bits from input wires to output wires.
>Routers tend to be most useful when all the bits that go in eventually
>come out. This state is called "flow balance" and it has a formal
>definition. If you measure at any particular time, some bits are
>arriving at the router, some are propagating through it and some are
>leaving. Say i(t) is the total number of EF marked bits destined for a
>particular output interface that arrive between t and t+dt, r(t) is the
>number in the router (including those that the router drops) 
>and o(t) is
>the number departing on that interface. Define:
>
>  I(T) = \int_0^T i(t)dt 
>
>(the \int_0^T is TeX notation for "definite integral from 0 to T" so
>this is the total number of bits that go in measured from time 
>0 to time
>T) and R(T) and O(T) similarly. Then it's always true that:
>
>  O(T) = I(T) + R(T)    [eq.1]
>
>which is to say that the total amount that comes out over time interval
>T is the amount that went in minus what's still in the router. The EF
>traffic is in flow balance if R(t) is bounded, i.e., if there exists
>some constant C such that R(t)<=C for all t (since R includes drops,
>this is just a complicated way of saying that everything that goes in
>comes out since otherwise R would increase over time). If you divide
>both side of eq.1 by T, the integration interval, you get the average
>output & input rates over interval T and you see that those rates must
>be equal over long times since R(T)/T <= C/T and the right hand side
>goes to 0 as T goes to infinity.
>
>Since the above only says that R() has to be bounded, you can 
>make a low
>loss behavior by policing the average input rate to something less than
>the achievable output rate then sticking enough buffer in the router to
>handle the worst case (measured) transit time. While this is a well
>defined behavior, it is *not* the EF behavior since it provides no
>contraints
>on jitter. Thus SLAs employing it can only talk of average rate over an
>unspecified interval and its behavior under aggregation & 
>disaggregation
>is at best complex. If, however, you measure the worst case R() then
>constrain the input rates such that I(T)+R(T) <= 1 packet, you get
>something that both has an explicit jitter bound for SLAs and 
>has a very
>simple algebraic structure under aggregation (described in 
>detail in the
>VW PDB document). This constraint is the same as saying there's at most
>one packet entering + in the router when measured over a packet time at
>the configured output link rate. I.e., this is exactly the 
>definition in
>RFC 2598. Note that in the spirit of IETF standards being about how to
>build real networks, this is a statement about something concrete and
>measurable (the balance between the average input & output flow rates)
>not a theoretical statement about how an abstract output queue service
>discipline might interact with a hypothetical "continuously backlogged"
>arrival pattern.
>
>Using the SHOULD as a MUST to deploy the VW PDB is completely
>intentional. If a domain is providing circuit replacement
>jitter is important. If the domain EF usage has other, less critical
>jitter demands, then the use of the SHOULD is probably 
>sufficient. We assume the "user beware" meaning of SHOULD
>from RFC 2119, that is, "violate this if you know what you're 
>doing and only if you know what you're doing."
>
>
>2. About the 50% limit and compliant schedulers
>
>The 50% is a theoretical upper limit for mixed traffic 
>beyond which the "EF bound" cannot be met. It is not an 
>intended or recommended operating region. The definition of 
>the EF PHB  says nothing about a 50% link bandwidth limit.
>
>Draft-charny-ef-definition-00 seems to have inverted this
>theoretical upper limit to a constraint which must be
>met by a scheduler in order to be EF compliant. On the
>contrary, the operating region for any EF compliant packet 
>scheduler is determined by the configuration for which it meets
>the EF definition. The amount of a link that can
>be allocated to EF (below the theoretical limit) depends in 
>large part on scheduler properties (specifically, granularity). 
>Our group at Cisco produced two reports on
>this (one by Kedar), pointers to which were given to the
>Cisco co-authors on the draft, so they know our thinking
>on this. We are hoping to make some of this material
>public soon, but it's not difficult to work out.
>
>In section 1.2.3 of draft-charny-ef-definition-00,
>the third paragraph proposes that it is "unnecessarily 
>limiting" to have a configured rate of EF that does not 
>exceed 50% of the link bandwidth. The paragraph
>after this points out that if the 50% is exceeded (a
>violation of the EF PHB, though apparently permitted by
>the PHB these 13 co-authors propose), a TDM circuit cannot
>meet the "EF bound".  This is a curious bit of discussion,
>as it is unclear how it relates to RFC 2598. Instead it
>appears to be a cautionary for the PHB the 13 co-authors
>are proposing.
>
>3. Latency through a network node
>
>Section 1.2.2 of draft-charny-ef-definition raises concerns
>about latency through a router. RFC 2598 intentionally says 
>nothing about latency through the box. In most cases, this
>is not all that critical as latency can be dealt with. In
>cases where it is critical, operational measurements will
>determine whether a particular envisioned service will or
>will not work. If it will not work, this will provide the
>kind of competitive pressure to get network boxes that do
>have low enough latency provided the desired latency is
>technologically achievable. If the desired latency bound
>is not technologically achievable, it's probably best to
>rethink the service.
>
>Latency really doesn't appear to be a problem for 21st century 
>high speed routers. We are aware of several Cisco emerging 
>hardware platforms that are quite adequate for a wide range
>of uses and assume that other vendors can say the
>same. Since we don't know the particular characteristics
>that a provider wants ahead of time and we don't know just
>how far router technology can be pushed over the next few
>years and we do know that latency is less critical than 
>jitter for the uses we envisioned (see for example
>draft-ietf-diffserv-vw-pdb-00), we believe that our approach
>in RFC 2598 is the correct one.
>
>By the way, the example of 1.2.2 does appear to be EF compliant.
>
>Finally, we request that interested parties *read* RFC2598. The
>body of the RFC (without the appendix) is not terribly long or
>difficult reading. Similarly, with draft-ietf-diffserv-vw-pdb.
>
>	Van Jacobson
>        Kathie Nichols
>        Kedar Poduri
>
>_______________________________________________
>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: Kathleen Nichols <[email-masked]>
Date: Wed, 26 Jul 2000 17:48:21 -0700

Thanks to Joel Halpern for pointing out that what we said
wasn't really what we meant in part of our comments. It
works best if you replace the paragraphs around eq 1 with
the edited ones below:

--------------------------------------------------------------

A router is a device for moving bits from input wires to output wires.
Routers tend to be most useful when all the bits that go in eventually
come out. This state is called "flow balance" and it has a formal
definition. If you measure at any particular time, some bits are
arriving at the router, some are propagating through it and some are
leaving. Say i(t) is the total number of EF marked bits destined for a
particular output interface that arrive between t and t+dt, o(t) is
the number departing on that interface. Further define r(t) as the
rate deficit, [i(t) - o(t)]. The rate deficit arises from bits in
transit
through the router and includes bits that never emerge, the router
drops.
Define:

  I(T) = \int_0^T i(t)dt 

(the \int_0^T is TeX notation for "definite integral from 0 to T" so
this is the total number of bits that go in measured from time 0 to time
T) and R(T) and O(T) similarly. Then it's always true that:

which is to say that the total amount that comes out over time interval
T is the amount that went in minus what's still in the router. R(T)
then has the interpretation of the number of bits that are in the router
(including drops) at time T. The EF
traffic is in flow balance if R(t) is bounded, i.e., if there exists
some constant C such that R(t)<=C for all t (since R includes drops,
this is just a complicated way of saying that everything that goes in
comes out since otherwise R would increase over time). If you divide
both side of eq.1 by T, the integration interval, you get the average
output & input rates over interval T and you see that those rates must
be equal over long times since R(T)/T <= C/T and the right hand side
goes to 0 as T goes to infinity.

---

From: "Kent Benson" <[email-masked]>
Date: Thu, 27 Jul 2000 13:17:46 -0500

Kathie,

Eq. 1 does not make sense to me.  If only 100 bits arrive between 0 and T
and they are all still in the router at T then it seems to me that
O(T)=0, I(T)=100 bits, and R(T)=100 bits (assuming R(0)=0).  Also, if
r(t)=i(t)-o(t) then integrating both sides does not give eq. 1.  Do you mean
the following (valid for R(0)=0)?

I(T) = O(T) + R(T)

In eq. 1 are you assuming that R(T)=0?

Also, are i(t) and o(t) rates?  This would result in I(T) and O(T) having
the right units.

The constraint that I(T)+R(T)<=1 packet seems odd since R(T) is bounded (or
at least should be for EF) and I(T) grows as packets arrive.  Do you mean
R(t)<=1 packet for all t?  Is R(t)<=1 packet for all t equivalent to the
definition in RFC 2598?

>From: [email-masked] [mailto:[email-masked]]On Behalf
>Of [email-masked]
>Sent: Wednesday, July 26, 2000 7:48 PM
>Cc: [email-masked]
>Subject: Re: [Diffserv] Comments on draft-charny-ef-definition-00
>
>
>

---

From: "Bill Courtney" <[email-masked]>
Date: Fri, 28 Jul 2000 01:13:08 -0700

Hi,

In the recent threads, there has been very little in the way of explicit
discussion of what has been proposed in the draft as the
re-definition of how EF PHB should forward bits. I'd like to take
advantage of the recent lull by hauling out the draft definition and
describing what it actually says:

   A target departure time (called F, the finishing time) is defined for
   the next EF packet to be forwarded (the jth packet) using the recursion

     F(j)=max(a(j), min(d(j-1), F(j-1)))+ L(j)/R for all j>0 [eq. 1]

   where,
     a(j) is the time of arrival of the jth EF packet to arrive at the
router
     d(j) is the actual time of forwarding (time of departure) of the jth
           EF packet to be forwarded by the router
     L(j) is the size of the jth EF packet to be forwarded by the router
     R is the configured rate of the EF aggregate

   Time at the arrival of the first packet is normalized so that a(1) = 0,
and
   similarly we normalize d(0) = 0 and F(0) = 0 (to get the recursion off
   the ground).

   We say that the behavior satisfies the draft criteria if

     d(j) <= F(j) + E      [eq. 2]

   where E is an allowed latency (or slack or error)

The meaning of the Max-Min expression is not immediately obvious, so let's
eliminate it by the simple expedient of setting the latency E to 0. Then,
right away we have d(j) <= F(j), for all j, from [eq. 2]. From this, we get
min(d(j-1), F(j-1)) = d(j-1) and

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

and since again d(j) <= F(j), this simplifies further to

   d(j) <= max(a(j), d(j-1)) + L(j)/R    [eq. 3]

Now the meaning is a bit clearer. We can clarify things further by
considering separately the cases where a(j) > d(j-1) and
a(j) <= d(j-1).

The case a(j) > d(j-1) occurs when an EF packet arrives at a router
and no EF packet is queued. (For definiteness in the discussion, assume
that a packet remains in the queue until service for it is completed.)
In this case,

   d(j) <= a(j) + L(j)/R   [eq. 4]

This says that in the next L(j)/R seconds, L(j) EF bits must be forwarded.
Put another way, this says that during the interval starting when packet
j arrived and ending when packet j is forwarded, L(j) EF bits must be
forwarded. Further, this must happen within L(j)/R seconds. So, during
this interval the EF service rate would be at least L(j)/[L(j)/R] = R.
This is exactly what we would want EF to do, I think.

Now consider the case a(j) <= d(j-1). This case occurs when the jth
packet arrives to find that another EF packet is in the queue. In this
case, [eq. 3] simplifies to

   d(j) <= d(j-1) + L(j)/R    [eq. 5]

This says that within the L(j)/R seconds following the forwarding of
the (j-1)st packet another L(j) EF bits must be forwarded. Note that
again L(j) bits must be forwarded within L(j)/R seconds, so again the
service rate must be at least L(j)/[L(j)/R] = R.

Without getting into the formality of a proof by induction, as long
as EF traffic keeps arriving at the router, we can keep projecting
a little bit further into the future, and we see that during each
projection, the draft criterion insists that the EF aggregate be
served at rate R or better. If EF traffic has a lull, the criterion
does not insist that any EF traffic be forwarded. Once EF traffic
starts arriving again, the criterion again insists that service at
rate R or better be given to it.

Also, if some EF packet or another is given service earlier than
[eq. 3] demands, no "credit" against future service is given. That
is, faster-than-configured service now cannot be banked against
slower-than-configured service in the future. This insistence
that the PHB continue cranking out EF packets at the configured
rate is the reason that the min(d(j-1), F(j-1)) term was
included in the draft definition.

Further, note that [eq. 3] applies regardless of whether the short-
term arrival rate of EF bits is <, =, or > R. Of course, if the
arrival rate is greater than R for a sustained period of time, a
queue will build up, jitter will increase, and all sorts of other
undesirable effects will happen. The draft is silent on this matter.
These situations are addressed elsewhere in RFC 2598, and the draft
is not trying to re-write that RFC.

Please note that the draft criterion demands that this EF service
be given at rate R even when very small time scales are considered.
In fact, even when time scales as small as L(j)/R are considered
(and note that L(j)/R <= MTU/R), service at rate R or better must
be given. This behavior is very much like what one would want from
EF. In fact, the second sentence of this paragraph is a virtual
paraphrasing of the definition given in RFC 2598. This why the
authors of the draft have been so insistent that their only
intention is to capture the intuition of RFC 2598 in an
unambiguous way.

Now, the discussion above has been made under the assumption that
the latency term, E, is 0. Building a router to deliver this
service with E = 0 may be something of a challenge. It is not
impossible, however. For example, a router with negligible internal
delay using PQ with configured rate R < C/2 (where C is the output
line rate), can have E = 0, if we also assume that both EF and
non-EF packets are uniformly of the same size (namely, equal in
size to an output MTU). Other configured rate/packet size
assumptions would also work in this example, as long as care is
taken to ensure that an EF packet arriving at an empty queue
while a non-EF packet is being served does not have to wait
longer than (L(j)/R) - (L(j)/C) before its service begins.

In general, a PQ server configured for any rate from 0 to C
and with no assumptions about EF vs. non-EF packet size has
a worst-case E = MTU/C.

This brings up the role of the latency term, E. It has been
included in the draft definition in a manner that does not
permit it to accumulate. That is, it is not the sort of
latency that allows one packet to be forwarded late and then,
after that packet has been finally served, allow the next
packet to also miss its target time with the same allowance.
Again the min(d(j-1), F(j-1)) term, prevents this from
happening, although exactly how this works is beyond the
scope of this already long-winded message.

The purpose of E is two-fold.

First, it is included to admit a wide variety of schedulers.
As has been pointed out several times over the last few days,
delay and jitter (within bounds, of course) are perfectly
acceptable for virtually every end-to-end service that might
make use of EF. A network operator must balance several
considerations in deciding how to provide a variety of
services. When we're in the trenches, defining a PHB or PDB,
it's easy to lose perspective and to come to think of the
current topic as the be-all and end-all. But, out in the world,
minimizing delay and jitter for EF will be only one of
many considerations. Fairness across several PHBs (including
BE) may be another prime consideration, as might protection
from an EF microflow that has somehow managed to become
abusive in its demands for bandwidth beyond its configured
rate. Thus, for this operator, PQ may not be the obvious
choice. The E term allows this operator to compromise
among his many concerns, to employ other schedulers, and to
still advertise EF service with an E > 0.

The second purpose of E is to allow all implementers to
advertise how close to ideal their implementation is. As E
is formulated, it can be used (like latency in the rate-
latency server formulation) by network engineers to estimate
per-domain and end-to-end delay and jitter.

(Warning: This paragraph is more controversial than any of
the others in this message. I don't want to start a fight,
so I'll try to be both forthright and dispasionate.)
There has been quite a bit of discussion about whether the
draft is just picking nits off of RFC 2598. This is a
difficult issue to address impartially. (Every person
thinks their baby is cute, and I'm no exception.) All I
can say on this matter, is that many of us have come to
agree that the RFC 2598 definition has some problems in
absolutely, formally being satisfied. The authors of the
draft (and maybe a few others) think these problems will
lead to difficulties in effective interoperability and in
the crafting of per-domain behaviors and end-to-end services.
We also feel that the draft definition is a worthy fix of
what is really a very small, though important, part of the
otherwise fine RFC 2598. One of the draft definition's
benefits, is that it eliminates the need for anyone to say,
"Oh come on, you know that the behavior my router offers is
close enough to the RFC." Instead, it allows the person to
say, "My router satisfies the RFC with E = x."

Finally, I would like to move the rather heated discussions
of the last few days to a more elevated plane. Toward this
end, I'd like to conclude with a list of issues regarding
whether this draft proposal to change one paragraph of RFC
2598 should be accepted, rejected, or reformed into a new
PHB. I'm sure that some of these will be regarded as non-
issues by many DiffServers, others will be valid but sort
of miss the point, etc. Probably, I've forgotten to include
issues that are very important to some or many in the WG.

The issues are written in a rather informal manner. Reading
them over, they seem provocative, but my intent is not to
provoke emotion or to debase the issues through flippancy.
I would like to face the issues, have a discussion, and
arrive at a consensus about this draft proposal with a
minimum of time and bother.

Issues:

1) Does this definition capture the intuition of RFC 2598? If
not, where does it fall short, or how does it utterly fail? Is
there a killer arrival pattern that makes mincemeat of the
definition? Does it persist in sending EF bits when it should
be dropping packets? If so, what drop criteria should be added,
or should reference to RFC 2598's drop criteria be made?

2) Does the definition support the development of PDBs that
are likely to be based on EF? In particular, does it support
VW (or whatever VW becomes once that separate discussion
concludes)?

3) Is the definition too complicated? Is it too hard to
understand, especially will it be too hard for implementers
to use? What simpler definition would suffice?

4) Is the definition just nit-picking? Is the decrease in
ambiguity and are the added benefits (such as E and the
lifting of the 50% configured rate limitation) worth
the bother?

5) Is E useful? Does it offer a figure-of-merit that
implementers, PDB definers, end-to-end service providers,
and other network engineers will use? Or is it just some
piece of mumbo-jumbo of interest only to researchers
interested in cranking out another paper or two? Does it
encourage laxity in router implementation and admit crummy
service into the EF fold? Is this laxity a problem if you
have to advertise how lax you've been, or is it a spur to
do better? (Is that last question so far out of bounds for
the IETF that Brian will special deliver a reprimand to me?)

6) Is the definition sufficiently different from the RFC 2598
defintion that the draft should be reformed into a new, stand-
alone PHB?

Thanks,
Bill Courtney
TRW, Network System Engineering

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 28 Jul 2000 11:30:20 -0500

Bill,

I would like to add a preliminary issue to your list, which I think 
is the first question to be answered by the WG:

0) Is it a requirement that PHB definitions are adequate to perform
mathematically rigorous conformance testing of implementations,
or is it sufficient that they give a general, intuitive
description of the behavior of an implementation?

I've re-read the relevant sections of RFCs 2474 and 2475 and they
do not answer this question, despite the use of the word
"conformance" in 2475, Section 3, paragraph G.9. 

   Brian

...