Subject: Re: [Diffserv] issues with RFC 2598

From: "Bill Courtney" <[email-masked]>
Date: Sun, 30 Apr 2000 22:37:11 -0700

Pawal,

I spoke too tersely and identified the wrong algorithm.  I should have said
"WF2Q+" rather than "WF2Q".  Also, the start and finish times in WF2Q+ are
kept "per session" (not necesarily "per queue").  I was assuming that each
session had a FIFO and that a representative of each session is kept in one
of two heaps, the ineligible heap or the eligible heap, based on start time
versus virtual time. (Thus my use of "queue" rather than "session".)
Clearly, this is my own interpretation of how one might implement WF2Q+, and
is not something that Bennett and Zhang said in "Hierarchical Packet Fair
Queuing Algorithms," although in that paper they do discuss maintaining only
one start and finish time per session.

My point in my previous posting was that with this algorithm (WF2Q+), very
good behavior is obtained and the finish time for a packet is not
necessarily calculated or even knowable when a packet arrives.  Following up
on this notion, I wondered whether using a definition for EF PHB that spoke
of a finish time only for the packet at the head of the EF aggregate queue
might not give us a simple and reasonable criterion for deciding when a
scheduler is compliant.  I then offered a simple criterion.  Whether it's
reasonable remains to be seen.

I apologize to Bennett & Zhang for misidentifying WF2Q and WF2Q+ in my
previous posting.  I apologize in advance if anything in this posting
misrepresents their work.

Bill

----- Original Message -----
From: Pawan Goyal <[email-masked]>
To: Bill Courtney <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>; <[email-masked]>
Sent: Sunday, April 30, 2000 3:52 PM
Subject: Re: [Diffserv] issues with RFC 2598

> > 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.
> >
>
> 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
>

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

---

From: Shahram Davari <[email-masked]>
Date: Tue, 2 May 2000 06:28:31 -0700

Hi,

May I ask the authors of RFC-2598 to comment on the latest thread regarding
EF implementation issues.

Regards,
-Shahram

>-----Original Message-----
>From: Anna Charny [mailto:[email-masked]]
>Sent: Tuesday, May 02, 2000 8:30 AM
>To: Bill Courtney; [email-masked]
>Cc: [email-masked]; [email-masked]
>Bill,
>I like this definition.  It seems that it has the desired properties:
>
>1) it is intuitively what we want
>2) it  seems to allow reasonable schedulers we can think of
>3) it is simple and is simple to test for conformance.
>
>As you say, we need some time to examine its possible side-effects, if 
>any.  But
>I do like it :-)
>
>Anna
>
>At 01:55 PM 4/30/00 -0700, Bill Courtney wrote:
>>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
>>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
>>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,
>>part of the algorithm or even a criterion that the algorithm 
>must satisfy.
>>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: Anna Charny <[email-masked]>
>>To: <[email-masked]>
>>Cc: <[email-masked]>; <[email-masked]>
>>Sent: Thursday, April 27, 2000 10:26 PM
>>Subject: RE: [Diffserv] issues with RFC 2598
>>
>>
>> > 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
>> >
>> > at 03:49 PM 4/27/00 -0500, Kent Benson wrote:
>> >
>> > >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
>> > > >
>> > > >
>> > > >
>> >
>> >

---

From: Jon Bennett <[email-masked]>
Date: Tue, 2 May 2000 12:11:53 -0400

(Sorry for not responding yesterday, but I did not receive messages from the
list over the weekend and had to have someone tell me to check the archive,
and yes I do have message delivery turned on, and have received messages
since,  although I note that at least one of the working group chairs still
has message delivery disabled..........)

Pawan,

Pawan Goyal writes

packet
known,
satisfy.
>> 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
made
>fairness and delay properties of WF2Q no longer hold.

While we only presented WF2Q+ with the use of per session rather than
per-packet timestamps it would apply equally to WF2Q. It certainly does not
impact on the fairness or delay properties of WF2Q. That it is valid to
maintain a timestamp for just the head of the queue is in fact the basis of
our presentation of the hierarchical implementation of WF2Q(+). While
per-queue timestamps may result in a slightly different output pattern of
packets compared to per-packet timestamps, the output is still *valid*, in
that it still maintains all the fairness and delay guarantees.

[NOTE :In the interests of total accuracy this strictly true only for the
case of Rate Proportional Processor Sharing (RPPS), for the non-RPPS case
there are a couple of ways this can be addressed in those cases where it
would actually matter. Since this is a very esoteric point I will not go
into the details. I will add that even in the non-RPPS case this would only
be an issue the presence of highly sophisticated rate/delay allocation
policies employing complex Call Admission Control (CAC) and very strict
leaky bucket *drop* policing of the type that would only be used for traffic
with per-flow reservations. So this would not be an issue for an aggregate
service such as diff-serv. If anyone has any questions on this I'll be happy
to take them directly.]

Jon C. R. Bennett
Chief Engineer
RiverDelta Networks 
3 Highwood Drive
Tewksbury, MA  01876
978.858.2300/2361 (direct)
978.858.2399 (Fax)

   -export-a-crypto-system-sig -RSA-3-lines-PERL

#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

---

From: Shahram Davari <[email-masked]>
Date: Wed, 3 May 2000 08:58:48 -0700

Brian,

Just to summarize there are currently two possibilities:

1) Small changes to the RFC-2598 wording. In which case EF can only be
implemented using priority scheduling, and has a 50% link share limitation.

2) Significant changes to RFC-2598. In which case EF can be implemented
using variety of schedulers, and alleviates the 50% share limitation.

Regards,
Shahram

>From: Brian E Carpenter [mailto:[email-masked]]
>Sent: Wednesday, May 03, 2000 10:01 AM
>To: Jon Bennett
>Cc: [email-masked]'; [email-masked]';
>[email-masked]'; [email-masked]>'; [email-masked]'
>Jon,
>I'm not claiming technical expertise and I'm not going to enter the
>technical argument. I'm asking that the people who assert that
>there is a problem with the EF definition cited below come up with
>a specific, simple proposed rewrite that we can then discuss with 
>the EF authors. 
>
>     Brian
>
>Jon Bennett wrote:
>> 
>> Brian,
>> 
>> > Kent reminded us of the key definition of the EF PHB:
>> >
>> > > "The EF PHB is defined as a forwarding treatment for
>> > > a particular diffserv aggregate where the departure rate of
>> > > 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."
>> >
>> > When we finalized RFC 2598 this wording seemed to be
>> > unambiguous, necessary, and sufficient, otherwise it
>> > would not have gained WG consensus.
>> 
>> Regardless of any previous consensus it has been demonstrated
>> that the definition in RFC 2598 can not be implemented by any
>> known scheduler. It has also been shown by several people that
>> the definition can not be implemented in principle by any known
>> or unknown work conserving scheduler. As a consequence it is not
>> implementable by a strict priority scheduler or by any of the
>> implementation examples presented in RFC 2598.
>> 
>> Do you have any technical arguments to counter these statements?
>> 
>> Unless you can present such arguments if would seem that the
>> definition in RFC 2598 can not be "necessary and sufficient".
>> 
>> > Would anyone like to propose a specific,
>> > simple change to this wording?
>> 
>> A number of proposals have been put forward, all of which are
>> substantial improvements over RFC 2598 in that they can actually
>> be implemented by a number of schedulers such as strict priority
>> or weighted fair queueing unlike RFC 2598 which has been repeatedly
>> shown to be unimplementable.
>> 
>> > On the other hand, discussion of implementation details belongs
>> > on the diffserv implementation list
>> > (see http://www.tip.csiro.au/dsimplementation )
>> 
>> The discussion of implementation details has been solely
>> for the purpose of determining that there exist reasonable
>> implementations of the definitions that have been proposed.
>> Are you suggesting that determining whether or not a
>> proposed standard can be successfully implemented is
>> not a relevant topic for discussion by an IETF WG?
>> 
>> jon
>> 
>-- 
>- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
>Brian E Carpenter 
>Program Director, Internet Standards & Technology, IBM 
>On assignment for IBM at http://www.iCAIR.org 
>Attend INET 2000: http://www.isoc.org/inet2000
>Non-IBM email: [email-masked]
>

---

From: Bill Courtney <[email-masked]>
Date: Wed, 3 May 2000 09:35:06 -0700

Kent,

Where do you find these extraordinary counter-examples? I think that your fusion of the two definitions into definition 3) is an excellent suggestion.  It addresses non-queuing delay in the router in a simple manner.  Where there is no non-queuing delay, it is equivalent to the two-state definition that I suggested earlier and uses a nice single-line definition.  It is unfortunate that each packet p_i has an associated arrival time, a_i, that needs to be kept in memory, but I cannot think of a simpler natural method that allows the definition to cope with non-queuing delay.

Thanks,
Bill

-----Original Message-----
From: Kent Benson [mailto:[email-masked]]
Sent: Tuesday, May 02, 2000 3:01 PM
To: [email-masked]; [email-masked]
Cc: [email-masked]
Subject: RE: [Diffserv] issues with RFC 2598

Bill,

Thanks for your suggestions.  Your definition seems to have quite a few nice
properties.  We've bounced quite a few scenarios off of it and so far the
results have been quite good.  There is one problem case described below but
a blending of our proposals fixes this while preserving the nice properties
of your criterion.  (I apologize in advance if I have misrepresented your
definition or screwed up the math.)

Our two proposals are (after a little re-writing)

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

and

2) F_i=min[d_(i-1),F_(i-1)]+(L_i/R_c) when Q=1
   F_i=a_i+(L_i/R_c) when Q=0

where d_i<=F_i+E in each case.  They could be combined to form this
definition

3) F_i=max{a_i,min[d_(i-1),F_(i-1)]}+(L_i/R_c)

This definition avoids the problem seen in the following example.  (This is
an example from a previous e-mail so it might look familiar.)  A link is
configured for 1/2 EF traffic.  Assume that MTU-sized EF packets are
arriving at only 2/3 of the configured rate or 1/3 of the link rate.  Assume
it takes T time units to send an MTU-sized packet at the line rate. For this
router, suppose that there is a fixed interval of time, 3T, between when a
packet arrives and when it becomes eligible to be transmitted on the output
link.  This delay could be caused by such things header processing and route
look-up as well as propagation delay through a multi-stage switching fabric.
Thus, packets arrive at the output link scheduler 3T later than they arrive
at the router.  If the router is lightly loaded each of the packets will
experience a delay of 4T (3T fixed delay, 0 scheduling delay, T transmission
delay). Thus, packet 1 has an arrival time of a_1=0 and a departure time of
d_1=4T, packet 2 has a_2=3T and d_2=7T, and so on.  (The arrival and
departure times of the EF packets are shown in the table below.)

Since there is always at least one EF packet in the router at all times, the
system stays at state Q=1 according to proposal 2 above.  In this state the
finish time of the packet i+1 can be at most L_i/R_c greater than the finish
time of packet i.  This is a problem since L_i/R_c=2T while packets are only
arriving every 3T time units.  Please see the table for the finishing times,
F_i (2), and latest allowed departure times (called max d_i (2) in the table
and calculated as F_i+E).  If this input pattern continues no any finite E
would prevent the departures times from eventually becoming non-conforming.

Definition 3 gives the finish times and the latest allowable departure times
F_i (3) and max d_i (3) as shown in the table.  Using definition 3 all of
the departure times for this input pattern are conforming as long as E>=2T.

EF Packet Number:          1      2      3      4      5      6 ...
Arrival (at router):       0     3T     6T     9T    12T    15T ...
Arrival (at output link): 3T     6T     9T    12T    15T    18T ...
Departure:                4T     7T    10T    13T    16T    19T ...
F_i (2):                  2T     4T     6T     8T    10T    12T ...
max d_i (2):            2T+E   4T+E   6T+E   8T+E  10T+E  12T+E ...
Fi (3):                   2T     5T     8T    11T    14T    17T ...
max d_i (3):            2T+E   5T+E   8T+E  11T+E  14T+E  17T+E ...

I don't think this new criterion affects any of the other properties of your
definition (except it does do away with the separation between the Q=0 and
Q=1 states).  Even though conformance definition 3 includes each packet's
arrival time to the system, a WFQ-like output link scheduler would not need
to know these times.  They would only be needed for conformance testing.
The output link scheduler could still use the time a packet arrives at the
output port for its internal calculations (as long as the E term is set
properly).

Thanks,
Kent