Subject: [Diffserv] Possible compromise between EFRESOLVE and draft-charny

From: "Bruce Davie" <[email-masked]>
Date: Thu, 7 Dec 2000 23:19:46 -0500

We (the draft-charny authors) would like to propose a possible compromise
EF definition which we think should reconcile the differences between the
current definitions of draft-charny and EFRESOLVE. We think that it
addresses all the criticisms that have been raised to date of both existing
definitions, and satisfies the goals expressed in both drafts and RFC 2598.

The major criticism of draft-charny was that it didn't provide any bound on
the delay of an individual packet. This is because the definition only
requires that EF packets leave the node at something close to the
configured rate R. There is no requirement that EF packets are served in
FIFO order, and thus, as long as new packets keep arriving fast enough, an
individual packet could live inside a node forever without violating the
definition. (This property is shared by RFC 2598).

Among the criticisms of EFRESOLVE were

- it doesn't define behavior of a node outside of its operating region
- non-FIFO treatment of EF will typically lead to a large value of S
- S is not a good figure of merit, since non-ideal scheduling and non-FIFO
service are lumped in the same parameter; also very good devices with large
number of ports will look worse than small devices with bad scheduling
implementations
- it is not yet clear how to generalize the defintion to the multiple input,
multiple output case
- it allows arbitrarily large fixed delay (which isn't visible in a figure
of merit)

While we stand by these criticisms, we also recognize that the ability to
describe the delay bound on a per-packet basis under certain operating
conditions may be quite useful in constructing certain PDB's based on EF.
To address this, we propose to "clone" the original equations of
draft-charny. The original equations remain part of the definition, and we
now rename the error term E as E_a (aggregate error). We call this the
"colorblind" definition because it pays no attention to individual EF
packets. This part of the definition simply tells you how well the device
does at serving aggregate EF traffic at the configured rate - small E_a
means a better scheduler in this regard. (See the new
draft-charny-ef-definition-01.txt for more on the intuitive meaning of the
definition.) This part of the definition closely approximates the original
RFC 2598 definition, in that it admits all the implementations that were
mentioned in that RFC; it also gives a better figure of merit to
implementations that are intuitively "better" at delivering EF service at a
configured rate, e.g. a priority queue.

The extra set of new equations looks just like the old ones but with one
difference: this second part of the definition pays attention to individual
packets so that we can bound the delay experienced by an individual packet.
We call this the "color-aware" definition, because you can think of each
packet as being uniquely colored as it enters a node and then the time at
which that
actual packet leaves the node is noted.  The new error term from these
equations is called E_p (packet error, as distinct from E_a).   With this
second part of the definition, the delay experienced by a single packet is
bounded by B/R +E_p, where B is the bound on the burstiness of the input
traffic and R is the configured rate. Hence, as long as the rate and
burstiness of traffic that arrives at an output are bounded, the delay is
also bounded.

This additional part of the definition bears many similarities to the
EFRESOLVE definition. To get bounded and well-defined behavior under
EFRESOLVE, there need to be some constraints on the total offered traffic
destined for an output in terms of rate and burstiness. Under such
conditions, the per-packet delay is S*MTU/R plus the minimum fixed delay of
the device.  Similarly, under our "color-aware" definition when the offered
load to an output is bounded by rate R and burst  size B, the maximum
per-packet delay is B/R + E_p. Clearly both definitions provide bounded
delay under well-defined operating conditions. The second part of our
definition addresses the intent of EFRESOLVE, but differs from EFRESOLVE in
that it provides well-defined behavior for arbitrary inputs. In addition
while EFRESOLVE gives a fixed delay within a specified operating region,
our new definition allows an operator to achieve different performance goals
by specifying different ranges of B and R that achieve the desired delay
bounds.

The first part of the definition allows existing and operational rate-based
implementations and deployments of the EF PHB to continue to be deployed
and operated (e.g EF implementation in Internet 2 managed by Bandwidth
Brokers).  The second part of the definition provides the machinery for
computing the delay bound as a function of the operating conditions.

In summary, we think this addition to draft-charny addresses all the
criticisms made of that draft (except that it was too hard to understand)
and also avoids the problems of EFRESOLVE, while addressing its goals. We'll
address the "hard to understand" part in the WG meeting and, if necessary,
in another version of the draft.

We're hoping that we might be able to get WG consensus behind this
compromise.

Bruce Davie (on behalf of 12 co-authors of draft-charny)

----------
Equations for those who care:

The original colorblind equations from draft-charny-...-01 are eq_1a and
eq_2a. The new ones that achieve the compromise are eq_1b and eq_2b.
Although the latter equations are not in draft-charny...01, the intuitive
description of the equations in that draft may still be helpful in
understanding the equations.

    D(j) <= F(j) + E_a                                           (eq_1a)
    d(j) <= f(j) + E_p                                           (eq_1b)

where F(j) and f(j) are defined iteratively by

    F(0)=0, D(0) = 0
    f(0)=0, d(0) = 0

    F(j)=max(a(j), min(D(j-1), F(j-1)))+ L(j)/R,  for all j>0  (eq_2a)
    f(j)=max(a(j), min(d(j-1), f(j-1)))+ l(j)/R   for all j>0  (eq_2b)

Here:

D(j) is the time that the last bit of the j-th EF packet to depart from I
actually leaves the node.
d(j) is the time the last bit of the j-th packet to arrive for I from any
input interface actually leaves the node.
F(j) is the target departure (finishing) time for the j-th EF packet to
depart from I.
f(j) is the target departure (finishing) time for the departure of the j-th
packet in an ideal FIFO server.
a(j) is the time that the last bit of the j-th EF packet destined for I to
arrive to the device actually arrives at the node.
L(j) is the size of the j-th EF packet to depart from I.
l(j) is the size of the j-th EF packet destined for I to arrive to the
device.
R is the EF configured rate at I (in bits/second)

_______________________________________________
diffserv mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/diffserv
Archive: http://www2.ietf.org/mail-archive/working-groups/diffserv/current/maillist.html

---

From: demir <[email-masked]>
Date: Fri, 8 Dec 2000 08:18:39 -0800 (PST)

I think to understand "burstiness" requires understanding the network
toplogy and "burstiness" on a hop. Using B instead of MTU (in  
EFRESOLVE) solves the "burstiness" problem. However, I think it won't
achieve "optimum" delay bound (should I say "efficient", "well 
defined"?) without "understanding" support and achieving this requires
some research. How I see the new B is, it takesEFRESOLVE one step further.
The easiest way to bound delay is:
	D(i) < bound_function(i, ...)
	bound_function(i) = a_constant
To me new suggestion takes one step more on the way, but still has the
problem of "sacrifice". It seems it is more general to leave the
bound_function alone. I assume there would be a trend on selecting a
bound_function. It could be the this new suggested one. However, it seems
it has "danger(s)" to be standardized. 
- I have made this point before (I hope Brian won't get mad at me): AF PHB
has only "queuing and discard" behavior. Whereas "EF" is obseses with
"delay bound" (That is fine with me). It is okay to "drop" packets (I
assume this is valid for all PHBs). To me, this is a "base" behavior and
it should be okay to combine some set of PHBs if one wants to describe a
new behavior (object-oriented approach). It seems, this is missing. Each
PHB is isolating itself from each other. This can be a "fundamental" change. 
I think this is a nice property and "makes the archirecture" more general.

Alper K. Demir

---

From: Kathleen Nichols <[email-masked]>
Date: Fri, 08 Dec 2000 10:47:25 -0800

> definitions, and satisfies the goals expressed in both drafts and RFC 2598.

But the EFresolve document does specify the PHB intended in 2598, so it
is "complete". So why is a "compromise document" needed? After all, the 
EFresolve team WAS the "compromise". What purpose do you have in
prolonging
this? If you do not like the PHB of 2598/EFresolve, you may certainly
propose yours. The criticisms of draft-charny have to do with it not
being EF, which it purports to be. It is completely reasonable to
rewrite
2598 to say what was intended, but it is really too late to take the
existing well-established name and attach it to something else.

>the delay of an individual packet. ...

No, a *major* difference of draft-charny and EF is that the PHB proposed
by draft-charny doesn't bound the delay variation. This is what both
Guven and Van said in Pittsburgh.

...
> - it doesn't define behavior of a node outside of its operating region

Do you really mean what the above statement says? (I used to wonder why
they put those stickers on hair dryers that say "do not operate
underwater".)

> number of ports will look worse than small devices with bad scheduling

It doesn't matter what the value is, it DOES matter that the potential
user know what it is so as to know if it will suffice for the purpose
desired.
A device is not "bad" if it serves the purpose; a device is not "good"
if it doesn't serve the purpose. This is very key to the intention of
the EF PHB. A device should deliver that behavior under whatever
configuration it is to be used in.

> - it allows arbitrarily large fixed delay (which isn't visible in a figure

This is a red herring: first, "arbitrarily large" delays do show up in
the internet: transcontinental links are not banned or limited in
length.
Further, it is not important for a differentiated services
PHB to bound the delay if it isn't a critical property of the PHB. A
box with a delay that is not appropriate and competitive is not going to
find a market for long. Diffserv PHBs are not meant to replace the other
standards by which vendors and their customers buy a box. If so, we'd
have to put a long list of specs that aren't about what *distinguishes*
this PHB.  

	Kathie (speaking only for myself at present)

---

From: "Bruce Davie" <[email-masked]>
Date: Fri, 8 Dec 2000 14:40:23 -0500

Kathie,

> is "complete".

That is your opinion. My opinion is that it does not. You may claim to know
the intent of RFC2598 better than I do, since you were a co-author, but
since the RFC is the product of a working group, I think it is the job of
the WG to decide whether EFRESOLVE adequately defines the PHB intended when
the WG agreed to advance the RFC to  proposed standard. At least 12 members
of the WG have not yet reached the conclusion that it does.

> So why is a "compromise document" needed? After all, the

Again, this is just my opinion, but I think that EFRESOLVE does exactly
that - takes the PHB name of RFC2598 and attaches it to something else.

> Guven and Van said in Pittsburgh.

Apologies for the confusion. It has been criticized both for its inability
to bound per-packet delay and its inability to bound the variation of that
delay. The new compromise definition provides both these bounds.

> they put those stickers on hair dryers that say "do not operate

I'm not sure how far we want to go with that analogy. I would be interested
in a hair dryer warning that said "underwater use may lead to electrocution"
and another one that said "underwater use is safe for you but bad for the
hairdryer". The problem with EFRESOLVE is that it may be quite valid to use
the device outside of the restricted region that the draft allows (e.g. due
to rare but possible arrivals outside the maximum burst tolerace) and it
would seem better to have some idea of what happens in that case.

> configuration it is to be used in.

And the problem is that because S covers so many different forms of
deviation from "ideal" behavior I can't tell if a device is suitable for my
purposes or not just by knowing S.

> have to put a long list of specs that aren't about what *distinguishes*

Fair enough.

Bruce

---

From: demir <[email-masked]>
Date: Fri, 8 Dec 2000 14:38:46 -0800 (PST)

> toplogy and "burstiness" on a hop. Using B instead of MTU (in  

Ooops. I meant using B instead of S*MTU+E(i)*R....

Alper K. Demir

---

From: demir <[email-masked]>
Date: Fri, 8 Dec 2000 15:40:19 -0800 (PST)

I agrre with Katie's points. In addition to that, I think it should be
"avoided" using "topology-dependent" parameters.
- Let's assume that B = EF_buffer_size (why an operator choses such a
thing? I don't know. I guess laziness). This will operate same as without
using any "delay constraints".
-  B on a hop depends on the B(s) from where traffic comes and so on +
traffic contitioning actions taken at the edge. In order to "utilize" the
the "delay" using B, a PHB should aware of both previous B(s) + traffic
contidioning actions taken for the aggregate + how this traffic is
distributed to output interfaces within the hop (this is not a problem,
but requires some additional mechanisms).
- It seems this is a parameter that can be used by a PDB not by a PHB. 
- My question: is this fine with Diffserv Architecture? If so, there could
be two different PHBs. One is "unutilized delay bound" PHB and the other
one is "unutilized delay variance" PHB (in general this is the subset of
the previous PHB). However, I think both will be subset of current EF PHB
with supporting PDBs. 
- I believe that though current EF has its problems on achieving
"delay bound", this problem can be attacked by a PDB. I don't understand
why this is an "obsession" for EF PHB (I am aware of service
requirement. My point is why "embed" the "service" into a PHB. Diffserv
PHB is more than that, isn't it?).

Alper K. Demir