Subject: RE: [Diffserv] issues with RFC 2598

From: "Kent Benson" <[email-masked]>
Date: Thu, 27 Apr 2000 15:49:18 -0500

Anna,

Thanks for your suggestions.  We (my colleagues and I) aren't exactly sure
what kinds of behavior RFC 2598 was trying to allow and what behaviors it
was trying to forbid.  One reasonable guess we had comes straight from the
first two sentences in section 2 ("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.").  One
possible way of interpreting these sentences would be this: the EF aggregate
should receive service equal to or greater than the service it would receive
from a fluid flow server from which it receives a minimum service rate equal
to some configured rate.  (Note that the fluid flow server does not have to
be a Fluid Flow Queuing Server (Generalized Processor Sharing Server).  In
fact, it does not even have to be work conserving.)  The discussions on the
list have shown that this requirement needs a phrase like "within some
tolerance" added to it somewhere for two reasons.  First, realizable
schedulers cannot give service that is identical to a fluid flow server
since they can only transmit one packet at a time.  Thus, packets must often
be sent earlier or later than their fluid flow finish times.  Second, many
routers are not purely output buffered and so cannot be modeled as a
collection of independent multiplexers feeding output links.  A tolerance
would allow for multistage switch fabrics with multiple contention points.

It looks like the conformance definition from your last e-mail can give some
behavior that does not fit with the "fluid flow server" criterion above.
This definition can be restated as follows (this makes the third or fourth
restatement from various people I think).  Assume EF packet P_i with length
L_i arrives at time a_i.  Letting Q(t) be the number of EF bits in a device
at time t, P_i finds Q(a_i-) bits in the system.  (Note that
Q(a_i+)=Q(a_i-)+L_i.)  We require d_i, the departure time of P_i (the time
P_i actually leaves the system) to satisfy

d_i<=a_i+[Q(a_i+)/R_c]+E

where R_c is the EF configured rate and E is a tolerance/error term.

Assume it takes time T to serve a packet of length L at rate R_c.  A series
of packets of length of L arrive at times 0, T, 2T, 3T, and so on.  P_1
arrives at time 0, finds 0 EF bits in the system.  Thus,
d_1<=a_1+[Q(0+)/R_c]+E=0+[L/R_c]+E=T+E.  If E is large enough such that P_2
arrives (at time T) before P_1 begins service (at time T+E-(L/C)) then P_2
could find L bits still in the system.  Thus, the largest d_2 could be is
T+[2L/R_c]+E=3T+E.  Continuing, the worst case allowable behavior is

Packet #  1     2     3     4     5     6     7     8
a_i       0     T    2T    3T    4T    5T     6T    7T
d_i      T+E  3T+E  4T+E  6T+E  7T+E  8T+E  10T+E  11T+E

The possible departure times can creep away from the fluid flow server
ideal.  Obviously, if you pick a different EF criterion then this behavior
might not be considered undesirable.

Our restatement of the EF definition given above leads pretty directly to
the following requirement:

F_i=max{a_i,F_(i-1)}+(L_i/R_c)

d_i<=F_i+g(E)

where F_i is the finish time of packet i in a fluid flow server that gives
the EF aggregate service of exactly R_c at all times, d_i is the time by
which packet i must be sent by the actual system, and g(E) is some
tolerance/error function.  I split the function g(E) out from F_i so it
can't loop back and accumulate in the finish times.

This Virtual Clock-like criterion would allow most common schedulers such as
WFQ, WF2Q, SCFQ, and strict priority.  This requirement has its drawbacks,
of course, but it is something to think about.

Kent

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]]
>Sent: Tuesday, April 18, 2000 2:29 AM
>To: [email-masked]
>Cc: [email-masked]
>Subject: OOPS: CORRECTIONS TO PREVIOUS MESSAGE. RE: [Diffserv] issues
>with RFC 2598
>
>
>Kent and Diffservers,
>
>The previous message I sent earlier tonight seems to have more
>than one
>problem. Please see corrections below.  My apologies.
>It's a late hour...
>
>Anna
>===============================================================
>=============
>===================
>
> >Kent,
>
> >Thank you for bringing up this issue. I think the point you
>are raising
>is very valid.    My attempt to retain as much of the wording of
>the >current EF definition as possible caused this issue  that I
>overlooked.   While the definitions I gave allow many
>reasonable >schedulers/devices to be compliant, it still does
>not cover
>some reasonable cases such as you are describing. Since these are
>indeed >both reasonable and useful cases, this issue needs to
>be addressed.
>
>
>At second glance the following attempt of a definition does
>not seem right
>at all.  Aside from a misplaced parenthes,  it looks like this
>approach
>does not accounts for a fixed delay in the box,  At the moment
>I cannot
>figure out how to make it right.   Please disregard it for now.
>
> >If I understand it correctly,  a standard way of dealing
>with the problem
>you are describing  would be to say that if at time 0 there is no
>EF >traffic in the queue, then for any t>0 the amount of
>traffic served by
>the EF aggregate  by time t must be at least min(A(t), tR_conf-E),
>where >A(t) denotes the number of EF bits that arrived to the
>queue in the
>interval (0, t), R_conf is the configured rate of the EF
>queue, and E is
>the >error term (tolerance term) (in bits).
> >A straightforward conformance test would then need to look
>at intervals
>of type (0, t) rather than at intervals of type (t1, t2).
>
>The following text has been corrected to fix a typo and to include the
>length of the arriving packet that I previously forgot.
>Otherwise it still appears to be correct.
>
> >Another way of addressing  this issue might be to require that an EF
>packet of length L entering a device at time t  and finding Q EF bits
>in >the device must leave the device no later than at time
>t+E+(Q+L)/R_conf  (where E is in units of time).  It may be
>convenient to
> >split the error term into fixed and rate-proportional delay
>similarly to
>how it is done done in RFC 2212.   Choosing E to cover the
>fixed >delay
>should fix your problem ( in your example the only cause of
>the delay is
>the fixed delay, but of course E should also account for >scheduling
>errors, etc).
> >A straightforward conformance test would now keep track of
>the number of
>bits still in the box at the time of arrival of a given packet
>and >see if
>its departure time conforms to the definition.
>
>
> >It seems to me that these two definitions still capture the original
>intent of EF definition,  allows all of the schedulers that would be
>allowed >under the two alternatives I previously suggested,
>and also take
>care  of the issues you brought up.  Certainly these also need to
>be >scrutinized for unnoticed and unwanted side effects. At
>the moment I do
>not see any.
> >Unfortunately, these are much farther away from the original
>wording of
>the EF definition.
> >So I guess we now have 4 options to consider.  It is not getting any
>easier :-).
>
>Well, we are down to three now :-)
>
>Anna
>
>
>

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

---

From: Anna Charny <[email-masked]>
Date: Thu, 27 Apr 2000 22:26:24 -0700

Kent,

Thanks for your comments.  Yes, I am by now aware of the side effect of the 
last definition I gave. While it does seem to allow all the known 
scheduling implementations I have thought of that appear reasonable for EF, 
it also allows a compliant scheduling sequence that gives only asymptotic 
rate guarantees.

The problem that we are facing appears to be that all the "simple" 
definitions we have so far come up with
appear either to disallow many or some reasonable schedulers, or allow some 
schedulers which appear to obviously
not be  "good" for EF.

We have discussed at length that the current definition in RFC 2598 does 
not allow any schedulers at all.
A simple addition of the busy period allows some schedulers, but imposes 
rate limitations that may be unnecessary. An addition of
a slack term allows all the WFQ-like schedulers, but still does not work 
for purely delay-based schedulers.  As mentioned above, and as your example 
indicates, the definition based on the time to drain the queue at the right 
rate (with the slack term) appears to allow the common reasonable 
schedulers, but in addition allows the cases such as you give in your 
example, where rate is guaranteed only asymptotically.

Finally, your definition that you give below appears to have an unwanted 
side effect of the virtual clock scheduler, which is that a flow that sends 
more packets initially (and gets transmitted in the absence of competing 
traffic) then can get punished later.  For example, suppose
EF aggregate has configured rate 1/2 of the output link speed.  Suppose at 
time zero a 100 packets arrive, each from a separate input. Then, when 
the   F_i will be updated to account for all packets, it will set to 200T, 
where T is the  packet time at link speed.  Suppose at time 101T a new 
packet arrives from yet another link. Its finish time is then set to max 
(101T, 200T)+2T,  and its deadline is then 202T_g(E).

Then the following scheduling sequence is compliant under your definition:

send packets 1-100 back to back at times 1T,2T,3T...100T, then send packet 
101 at time 202T+g(E)

So in the interval  (101T, 202T+ g(E)) nothing is sent without violating 
compliance, while the queue is continuously busy in that interval.
It seems that this is not what we want either... Would you agree?

I have been talking to Jean-Yves Le Boudec about this problem. He is of the 
opinion that the only way we could avoid these problems is to  use the 
definition based on service curves, as introduced by Cruz, and as used in 
the Intserv context.  We are still in the process of figuring out some 
issues surrounding this.  I am copying Jean-Yves directly  in case he would 
like to comment.

In any case, it seems clear that either we should settle on a simple 
definition that has some known drawbacks (e.g. allows some  (perhaps not as 
complete as we would like) set of known schedulers that seem reasonable for 
EF implementation,  and does not allow those which are obviously bad), or 
the definition must be substantially more complicated than has been 
originally envisioned.

Regards,
Anna

---

From: "Kent Benson" <[email-masked]>
Date: Fri, 28 Apr 2000 16:00:58 -0500

Anna,

Everything you say is true, I fear.  It may be necessary to choose one of
the following options:  some "reasonable" output patterns are not compliant,
some "unreasonable" output patterns are compliant, or the compliance
definition is quite complicated.  I suppose it comes down to how desirable
the "reasonable" cases would be, how undesirable the "unreasonable" cases
would be, how complex the "complicated" standard would be, and how people
are willing to trade off these factors.  The likelihood of the particular
circumstances that could lead to an undesirable output could also be a
factor.

It does look like both of our recent compliance definitions would allow a
scheduler to produce an output with large gaps between EF packets.  It would
be nice if WFQ with the minimum EF rate set equal to the EF configured rate
would be compliant under any new conformance definition.  Since WFQ can
produce surprisingly large inter-packet gaps under some conditions, however,
any conformance criterion that rules out certain gaps between EF packets
will eliminate WFQ from consideration (at least using this simple
configuration).  Maybe saving this simple configuration is not worth the
downside and anyone wanting to use WFQ should just be careful to set the EF
weight high enough.  It would be nice if a simple rule for "high enough"
could be found.

On a related note, does anyone know of any results that bound the real time
difference between a packet's departure time and its finish time, for
example as a function of the number of other flows and their weights?
What's the tightest bound for a flow that does not have the largest weight,
for instance.

Thanks,
Kent

>Sent: Friday, April 28, 2000 12:26 AM
>Cc: [email-masked]; [email-masked]
>Subject: RE: [Diffserv] issues with RFC 2598
>
>
>Kent,
>

---

From: "Bill Courtney" <[email-masked]>
Date: Sun, 30 Apr 2000 13:55:06 -0700

Anna & Kent,

I believe that the recent difficulties our WG has been having in defining a
conforming service for the EF PHB are stemming from our trying to mold a
descriptive equation of a conforming scheduler into a prescriptive equation.
Specifically, I'm referring to the assignment of target departure times on a
per-packet basis and at the time of the packet's arrival at the scheduler.

Kent's group observed that a scheduler can benefit from an accumulation of
late delivery tolerances, causing the throughput to creep away from the
ideal fluid server.  Anna observed that Kent's group's proposed separation
of tolerance/error from the target departure time can lead to a crediting of
the scheduler for past better-than-ideal service and to huge service
droughts.  Yet, both of these behaviors would be compliant under the
respective proposed definitions.

I think that the root of the problem with both unreasonably compliant
behaviors lies in the attempt to define a target departure time for a packet
when it arrives. If we consider the fairest packet scheduler that is known,
WF2Q, we see that it assigns a start and finish time not to each queued
packet, but rather to each queue.  The excellent WFI that results is not
part of the algorithm or even a criterion that the algorithm must satisfy.
It is simply a description of the outcome of the algorithm's performance.

In this vein, I'd like to propose a simple criterion as a definition of
conformant EF PHB.  As with WF2Q, the criterion does not assign finish times
to packets.  Instead, it assigns a target finish time and a tolerance to the
EF queue, or, if you will, to the earliest arriving EF packet still in the
system (i.e., in service or in the EF queue).  The criterion uses a small
number of terms, namely

R, the configured rate of the EF aggregate (bits/second)
L, the length of the earliest arriving EF packet in the system (bits)
Q, a state variable indicating whether (Q=1) or not (Q=0) the EF aggregate
has a packet in the system
F, the target finish time of the earliest-arriving EF packet in the system
(undefined if Q=0) (seconds)
E, the tolerance/error term (seconds)
t, wall-clock time (seconds)

As in previous discussions, a packet is deemed to have arrived when its last
bit arrives and to have departed when its last bit is transmitted.

If Q=0, then F is undefined.
If Q=0 when an EF packet arrives at time t, then
     Q = 1
     F = t + L/R
If Q=1, an EF packet departs at time t, and an EF packet is in the queue,
     F = L/R + min(t, F)
If an EF packet departs and the EF queue is empty, then
     Q = 0

We say that the scheduler is compliant with the EF PHB if the
earliest-arriving EF packet in the system departs at time d and

     d <= F + E

(Following Jon Bennett's suggestion, E can comprise a rate-dependent term
and a rate-independent term to enable more useful advertisement of the
scheduler's capability.)

As in Kent's group's definition, the tolerance/error term is isolated from
the target departure time, so the definition avoids creeping away from the
ideal.  Unlike that definition, the target departure time is not defined for
each packet, so the accumulation of credit that Anna observed does not
occur.  The scheduler is neither rewarded for past better-than-ideal
service, nor is it forgiven for past worse-than-ideal service (at least not
until no more EF packets are in the system).  Both of the unreasonably
compliant behaviors you observed would be non-compliant under this
definition.

I believe that most commonly used schedulers (except perhaps VC, about which
I know little) have finite tolerance/error terms with this definition.  It
seems that WRR, WFQ, and SCFQ have relatively large t/e terms, while PQ, TDM
circuits, and WF2Q have relatively small ones.  This would be appropriate,
since we would like more "circuit-like" schedulers to have better advertised
performance.  I speculate that the t/e term will be closely related to the
WFI of the scheduler whenever that metric can be applied, but that's just a
conjecture.

Further investigation is needed to such for hidden flaws.  Provided that no
one discovers a glaring flaw right off the bat (in which case I'll go into
hiding for a while), I'd be glad to dig depper into things.

Do you think that this definition holds any water?

Bill

---

From: Pawan Goyal <[email-masked]>
Date: Sun, 30 Apr 2000 17:52:43 -0500 (CDT)

> It is simply a description of the outcome of the algorithm's performance.

The assertion that WF2Q assigns a start and finish tag to each queue rather
than each packet is incorrect. It can be shown that if a modification is made
to assign start and finish tags to each queue rather than packet, then the
fairness and delay properties of WF2Q no longer hold.

Pawan