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

From: Kathleen Nichols <[email-masked]>
Date: Tue, 25 Jul 2000 10:25:22 -0700

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/

---

From: "Bill Courtney" <[email-masked]>
Date: Tue, 25 Jul 2000 18:18:10 -0700

Kathie,

I have some questions and comments which are included in line with your
message below.

Bill Courtney
TRW, Network System Engineering
-----------------------------------
Kathie wrote
> opaque mathematics, here is a more formal description:

Certainly we read all of RFC 2598. I do not feel that by failing to use
extended quotations we were taking parts of the RFC out of context. The
RFC sets out an intuition of an EF PHB. The draft addresses the
quantitative criterion for EF given in the RFC, which is where difficulties
lie, and it quotes that criterion. The draft addresses the criterion in the
context you cite.

> RFC 2598.

The text between my previous comment and this comment is confusing to me.
First, the integral you give will not produce the result you state for I(T),
although replacing i(t) with (i(t)/dt) or i'(t) will. Similarly with R(T)
and O(T).

However, I can't tell whether you intend R(t) to be always non-negative
or always non-positive. (eq.1) would suggest that R(t) should always be <=
0, but
the text immediately above, with statements like "R(T)/T <= C/T" and
"I(T) + R(T) <= 1 packet," would suggest that R(t) should always be >= 0.
Thus,
I cannot figure out how to interpret "constrain the input rates such that
I(T) + R(T) <= 1 packet."

Further, when does time 0 occur in the "... <= 1 packet" statement? Do you
intend that any arbitrary time can be normalized to t = 0? Is there a
lower bound on T such as the time that it takes to send an output-link-MTU-
sized packet at the configured rate? Is there an upper bound on T so that
the constraint on the input rates will not have to bound I(T) + R(T) <= 1
packet for arbitrarily long intervals (else, almost no EF bits could be
admitted into the domain, it would seem)?

I certainly can't make out how this is equivalent to the RFC 2598 statement
that the EF traffic 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.

I'm not quibbling or fencing here; I just can't tell what you mean by this
text. If I'm the only one with this problem, I'll just wait for the meeting
and ask some kind DiffServer to explain it to me.

> Note that in the spirit of IETF standards being about how to

Correct me if I'm wrong, but isn't this comment intended to be sarcastic
rather than informative? I don't think that "continuously backlogged" is
hypothetical, that a FIFO is abstract, or that their combination is
theoretical.

> doing and only if you know what you're doing."

We assumed that the wording in the VW PDB draft was intentional and used
this as an example of why an implementable definition is important.

> appears to be a cautionary for the PHB the 13 co-authors

The comment in the draft relates to RFC 2598 in that it points
out that the departure rate criterion (aka the definition) implies
that the EF aggregate cannot have a configured rate greater than
50% of the output link rate (unless it is configured at 100%), even
if the output link is as extrordinarily well-behaved as a TDM
circuit. This limit is unnecessary, because there is no good reason
for such a limitation to exist. Rather, it seems to be an artifact of
the RFC definition. Whether it is an unavoidable artifact is a valid
point of discussion for the WG. The defintion proposed in the draft
does not have this limitation, so the comment is not a caution about
the draft definition.

> in RFC 2598 is the correct one.

I'll let someone more closely associated with high-speed router
development comment on this.

> By the way, the example of 1.2.2 does appear to be EF compliant.

The example is not compliant under the RFC definition because it
does not forward EF bits at the rate called for by that definition.

> difficult reading. Similarly, with draft-ietf-diffserv-vw-pdb.

It was our reading of the RFC that led to a long (in time and
message count) WG thread on the difficulties with the definition.
Our draft was, above all, a proposal to capture the intuition
of the RFC in an unambiguous and implementable form. The difficulties
with the current RFC definition will result in loose and varied
interpretations and implementations in the vendor community that
will create considerable uncertainty over what PHB is really being
offered by competing products. We hoped to demonstrate that the
definition requires fixing, and in a constructive mode, offered a
fix. The issues that persist, such as whether PDBs like
VW can be based on the fix, are important. I would hope
that interested DiffServers become involved in a forthright and
dispassionate discussion of the PHB.

---

From: Van Jacobson <[email-masked]>
Date: Wed, 26 Jul 2000 01:55:36 -0700

> hypothetical, that a FIFO is abstract, or that their combination is

The comment wasn't intended to be sarcastic. To a theorist a router is
simply a wire that ends in a queue so a detailed discussion of the
arrival pattern on the wire & service discipline of the queue says all
the one could possibly say. But a real router is vastly more complicated
than this: there are queues, schedulers and variable latencies due to
interrupts or bus contention in the input cards, in the fabric, even in
the various chips that make up the different line cards. All these
elements inject variable, complex, state & traffic dependent delays as a
packet winds its way from the input to the output. If you focus on just
the output queue you neglect 90% of the behavior. But any real,
operational, EF deployment will succeed or fail based on the behavior of
the router as a whole. A rigorous, first principles proof that the
latency variation through the output queue is only 10us isn't going to
do much to comfort angry customers if the variation input-to-output
through the box is 10ms.

One of the many misunderstandings that seem to underlie
draft-charny-ef-definition-00 is that RFC2598 was trying to specify the
behavior of an output queue but the authors were simply too
mathematically illiterate to do it right. I make no claims for our
literacy but our intent was to talk about input-output behavior of the
router as a whole, not just some of its pieces. To the best of my
knowledge, the state of the art in queuing theory is very, very far from
the point where one could hope to get a useful analytic model of a real
router so we made no attempt to *specify* the behavior. But there are
robust, mathematically verifiable ways to *characterise* the behavior
that basically derive from Little's law: you measure the total input &
output EF bits vs time while subjecting the box to a "realistic" traffic
mix. The distribution of the difference of these two measurements is the
distribution of the total delay variation through the box. The
difference between the max & min of this distribution is the EF bound.
It's hard to calculate but easy to measure.

 - Van

---

From: Anna Charny <[email-masked]>
Date: Wed, 26 Jul 2000 08:59:42 -0400

Van,

>mathematically illiterate to do it right.

I would like to point out here that we never intended to analyze anyone's 
literacy and I am surprised that you seem to interpret it that way.
We were addressing a technical issue and would very much like to keep our 
discussion precisely at the level of a technical discussion.

>  I make no claims for our
>router as a whole, not just some of its pieces.

Seems that you have missed the point of  at least part of the 
argument.  Our example of a router with the internal delay was put there to 
demonstrate that
the definition in the RFC in fact does NOT  work if you look at the 
"input-output behavior of the router as a whole, not just some of its 
pieces".  The definition that we
offer in fact does precisely what you are asking for.  If you disagree, 
perhaps you can present a technical explanation on why.

>  To the best of my

I have no problem with the statistical nature of this argument, although it 
would be nice to make it somewhat more rigorous.
This seems to me to have no bearing on the fact that the definition of EF 
RFC is NOT of statistical nature. It becomes especially obvious that this is so
in the VW draft, where the SHOULD is replaced by a MUST, and an attempt is 
made to derive worst case (and not statistical) properties.

It seems to me that while correct intuition is certainly very important, 
there could hardly be any harm in getting the definition right and 
unambiguous?
Don you think that our definition is wrong? Do you think other statements 
in our draft are wrong? Then perhaps you could explain why in more concrete
terms?  Otherwise, what is your objection to modifying the RFC to remove 
the ambiguities?

Regards,
Anna
_________________________________________
>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

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Wed, 26 Jul 2000 15:15:26 -0400 (EDT)

Van,

[...]
> It's hard to calculate but easy to measure.
If that was the intention of the definition, it should have
been stated as that. This new draft only attemtps to say,
that what is "stated" in the draft is not what it meant to say.

Your explanation talks for arbitrarily large averaging 
intervals (sine average numbers and Little's law only work 
as time-> infinity), and the statement in the draft talks 
about about specific inter-departure times. I have no problem 
to accept that the EF goal was to characterize traffic on 
the average. But if that is the goal, it is should be 
stated accordingly.

As stated by Anna, the goal of the draft is not to define a 
new service, but just clarify an incorrect representation
of intention.

My 2 cents,

Dimitri

---

From: Anna Charny <[email-masked]>
Date: Thu, 27 Jul 2000 12:40:00 -0400

Shobha,

First, thanks for you very constructive comments. Let me try to address them.

At 10:50 AM 7/27/00 -0400, Shobha Erramilli wrote:
>Anna,
>
>IMHO, part of the
>problem I see that's causing all the debate is this -
>While you and the other authors have done a good job in
>bringing out the problem with the RFC 2598 definition, there
>isn't as much explanation on your definition. The end of Section
>1 says that "we are proposing an alternate definition" and then
>Section 2 jumps straight into the math. It might help if you
>motivated that definition more strongly with some text, for
>those of us that are mathematically challenged.

Fair enough. We should definitely put such text in.

Let me restate  my earlier attempt to explain what that intuition actually 
is.  I will give it for the common case when EF packets are served in  FIFO 
order (that is, there are no multiple EF queues at one interface).   In 
plain English,  what our definition means is that given a desired error 
margin E,   the EF aggregate is given at least its configured rate (within 
the specified error margin) as long as there are any EF packets in the 
device to be served.  In other words, if an EF packet arrives to the device 
at time t and finds Q EF bits in the device (including the arrived packet 
itself), it must depart from this device no later than at time t+Q/R +E, 
where R is the configured rate.  So the configured rate is achieved when 
there is something to send.

The error margin E, which we refer in the draft as "latency term",   is 
intended to be small to ensure that when there is something to send, the 
configured rate is ensured at a small time scale.  Given E, one can attempt 
to construct a scheduler (and the architecture) that would in fact deliver 
the required behavior.  However, for a non-preemptive scheduler one cannot 
take E smaller than  MTU/C. We do not know any scheduler other than PQ that 
can in principle achieve E=MTU/C.    So the choice of E determines the set 
of possible scheduling implementations and router architectures that are 
capable of delivering it. Conversely, a given choice of the scheduler and 
architecture determines the minimal E it can support.

I would appreciate some feedback on whether this makes it any more 
intuitively clear.

>The way I understand it, section 1 is describing the pitfalls of
>a throughput based definition and in Section 2 you are proposing one that
>uses packet inter-departure times and define constraints
>on that, i.e. constraints on the delay variation.
>It might also help if you explained the math, e.g. eq_2 could
>do with a little bit of text that talks about each term.

We tried to do so in the section immediately after the formal 
definition...  Obviously it was not too clear. We will see how to explain 
it better - and of course would be grateful for any suggestions.

>I think you are taking care of the cases where the packets arrive
>too early or too late, right?

Yes, exactly.

>Next, how can we  evaluate the
>compliance of a router to this defintion based on externally
>observable events? Is it conditional upon knowing the
>scheduling method used and the number of queues?

What we envision here is that a router advertises what E it can support 
(with the connotation that the smaller the E the better).
Knowing E,  the conformance test then simply records the time packets enter 
and exit the network (A(i) and d(i) in our definition), compute F(i)  using 
the recusrion given in the definition and see if d(i) satisfy eq_2.    So 
no knowledge of the internals is necessary at all for the conformance test.

Of course, when *designing* a router and a scheduler, the desired value of 
E is critical, since some designs may not be capable of delivering small 
enough  E.

Thanks,
Anna

>Thanks,
>Shobha