Subject: [Diffserv] Simpler EF redefinition

From: Stefano Salsano <[email-masked]>
Date: Wed, 02 Aug 2000 11:52:48 +0200

Hi,

I don't know if any discussion/decision in Pittsburgh will 
close the issue of EF definition... I'm not attending the
meeting... but just in case it's still open, here is a proposal 
for a simpler redefinition of EF. It should solve the problems 
outlined in draft-charny, yet it is more intuitive because 
it is based on measuring amount of EF traffic in arbitrary 
time intervals.

This redefinition of EF PHB captures the original intention 
of RFC 2598 and is also adequate to verify if a node implements 
the EF PHB. Similarly to RFC 2598 this definition defines a 
lower bound to the rate of EF aggregate exiting a
node during a given interval. The lower bound depends on the
configured EF rate, on the input traffic and on a latency term
representing the router behavior.

The proposed redefinition is described in a draft named 
draft-salsano-simpler-ef-redef-00.txt, also available at:
ftp://ftp.coritel.it/pub/id/draft-salsano-simpler-ef-00.txt

Below you can find the most important text:

2. Redefinition of EF PHB

The EF PHB is defined as a forwarding treatment for a particular
diffserv aggregate where the amount of the aggregate's traffic
departing from the router in a given time interval MUST equal or
exceed a quantifiable lower bound which is given below. The lower
bound depends on the amount of the aggregate input traffic in that
time interval, on the configured rate R for EF traffic and on a
latency term which takes into account the router behavior.

Let I(t1, t2) be the amount of EF traffic directed to a given
outgoing port that entered the router in the interval (t1, t2) and
let O(t1,t2) the amount of EF traffic that exited the given port in
the interval (t1, t2). A packet has entered the router when the last
bit of the packet has entered the router and it has exited the router
when its last bit has left the router.

Let R be the configured rate for EF traffic, R <= C where C is the
link capacity.

A node supports the EF PHB at a rate R with a latency term E if for
each t1 and t2, where t2 > t1 + E

O (t1, t2) >= min (R*(t2-t1-E), I(t1,t2-E))

The above condition applies under the hypothesis that no loss occurs
for the EF traffic under observation.

Note that actually the lower bound on the amount of output traffic in
the interval (t1,t2) depends on the amount of input traffic in the
interval (t1,t2-E)

3.  Comments

The lower bound basically says that the rate of outgoing EF traffic
is always greater or equal than the configured EF rate if there is
enough EF traffic to be transmitted. Otherwise the outgoing rate will
follow the incoming rate. A latency term must be included to define
the interval in which the rates can be measured. This latency term
takes into account the short term behavior of the router, including
processing delays and scheduling delays. [...]
[...]

More comments and the evaluation of E term for priority queueing
are given in draft-salsano-simpler-ef-00.txt

Regards,
Stefano

-- 
*******************************************************************
Stefano Salsano
CoRiTeL - Consorzio di Ricerca sulle Telecomunicazioni
                  
E-mail  : [email-masked]      URL     : http://www.coritel.it
Tel.    : +39 06 20410029         Address : Via di Tor Vergata, 135     
Fax.    : +39 06 20410037                   00133 Roma - ITALY          
*******************************************************************

_______________________________________________
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: Wed, 02 Aug 2000 23:11:26 -0400

Stefano,

It seems to me there is a problem with your definition. Please see below 
and let me know
if I misunderstood something.

>for the EF traffic under observation.

Consider a  router with 10 input ports.  There is an EF stream on each 
input, all 10 streams converging to a single output of speed C, which 
implements PQ and has Ef configured rate R=C/2.  Suppose that the 10 EF 
streams have input rates C/100 each (or in fact just about any other rate 
such that  sum of all input rates is smaller than R).  According to your 
draft for PQ E=2MTU/C, so consider some  t1 and t2 > t1+E such that

t2-t1=22MTU/C

and such that no packets arrive in the interval  (t1, t2-E epsilon), and 
then 10 MTU-sized Ef packets arrive from the 10 inputs (one packet per 
input). This can clearly happen.

                        20 MTU/C                                  E=2MTU/C
t1 <------------------------------------------->t2-E<---------------->t2

                                                                 ^
                                                                 |
                                                             1 packet from 
each of 10 input arrive
                                                              at time 
t2-E-epsilon

Then you get

R*(t2 - t1-E)=R *20MTU/C=10MTU,
I(t1, t2-E) = 10MTU

so according to your definition you MUST send at least

min (R*(t2-t1-E), I(t1,t2-E))=10MTU/C

in the interval (t1, t2).  Yet, when you finally receive the packets, you 
have only time E+epsilon = MTU/C+epsilon left in that interval (t1, t2).
Now, to satisfy your definition, you MUST send 10 MTU-size packets in the 
time slightly exceeding 2MTU/C, which is clearly impossible, since you only 
have time to send 2MTU +epsilon/C.

Regards,
Anna

---------------------------------------
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: Thu, 3 Aug 2000 17:36:56 -0400 (EDT)

Anna, 

Actually, I think that Stefano's definition can be easily
fixed, if you account for the proper trigger condition for
starting the counting process. 

What is missing from the definition is the fact
that t1,t2 can not be arbitrary times. If t1 is defined
as the time that the an EF packet arrives at 
the router, then your counter-example
will not hold any more. I think that it is possible
to form such a non-recursive definition, that is 
equivalent to the recursive definition.

A node supports the EF PHD at a rate R with a latency E,
if for every t1 that a packet arrived at the router, and 
any t2>=t1,
 
    O(t1,t2) >= max( min(R*(t2-t1-E), I(t1,t2-E)) , 0 )

The max factor accounts for the intervals of length less than E.

The min factor accounts for a long latency within the
box. (i.e. when the rate is smaller than the 
guaranteed, but the box seems backlogged from an external
viewer.) 

When comparing with the recursive definition, the above 
process initiates counting at the same point (as F0),
and then provides a  closed form inequality for the 
bin-counting process.

Note that since the definition holds for every
packet arrival, a W2FQ scheduler would satisfy it, whereas
a WFQ scheduler would give a very large E !

Am I missing something ?

Dimitri

---

From: Anna Charny <[email-masked]>
Date: Thu, 03 Aug 2000 21:27:25 -0400

Dimitri,

>starting the counting process.

It is certainly possible that it can be fixed. I was merely addressing the
fact that as written, it did not work

>equivalent to the recursive definition.

Again, it should indeed be possible.  I did not think it was necessary, 
since I personally doubt the end
result will be substantially more intuitive than the definition we had in 
the draft.  I certainly may be wrong.

I do not think that your attempt to fix Stefano's proposal works, 
though.... Please see below.

>a WFQ scheduler would give a very large E !

Well, I think my example for the original Stefano's definition can be 
easily modified to be a counter-example for this
definition as well.   All you need to do is to make a single EF packet 
arrive at time t1 of my previous example and let if leave immediately.
Then the interval I considered will start with a new arrival of Ef packet, 
but the rest will remain the same....
If the interval-based definition is to work, it appears it needs to be more 
complicated than what you suggest.

Here goes the modified example....

Consider a  router with 11 input ports.  There is an EF stream on each 
input, all 11 streams converging to a single output of speed C, which 
implements PQ and has Ef configured rate R=C/2.  Suppose that the 11 EF 
streams have input rates C/100 each (or in fact just about any other rate 
such that  sum of all input rates is smaller than R).
I will continue to assume that E=2MTU/C, as Stefano suggested (it really 
doesn't matter since I can easily modify the example for any other fixed E).

Consider a time t1 when a single  EF packet arrives on input 11.   Consider 
an interval  (t1, t2)  such that t2-t1=22MTU/C and such that no packets 
arrive in the interval  (t1, t2-E epsilon),  with the exception of the one 
packet arriving at time t1, and then 10 MTU-sized Ef packets arrive from 
inputs 1-10 (one packet per input). This can clearly happen.  Assume that 
the single packet which arrived at time t1 left at time t1+MTU/C.

>      ^                                                          ^
>        |                                                          |
>      1 paclket                              1 packet from each of inputs 
> 1-10 arrive
>      arrives on                                                      at 
> time t2-E-epsilon
>       input 11 and
>       leaves immediately

Then you get

I(t1, t2-E) = 11MTU

so according to your modified definition you MUST send at least

max( min(R*(t2-t1-E), I(t1,t2-E)) , 0 ) = 10 MTU  in the interval (t1, 
t2).  Yet, when you finally receive 10 of 11 packets, you have only time 
E+epsilon = MTU/C+epsilon left in that interval (t1, t2).  Since you only 
sent one packet before time t2-E--epsilon, now, to satisfy your definition, 
you MUST send  9 MTU-size packets in the time slightly exceeding 2MTU/C, 
which is clearly impossible, since you only have time to send 2MTU +epsilon/C.

Is it my turn to miss something?

Anna

---

From: Stefano Salsano <[email-masked]>
Date: Fri, 04 Aug 2000 17:29:12 +0200

Anna Charny wrote:
> Stefano,
> 
> It seems to me there is a problem with your definition. Please 
> see below and let me know if I misunderstood something.
....

> starting the counting process. 
...

Hi,

following Anna's and Dimitri's comments, I tried to fix the
problem in the simpler EF definition I proposed.

The result of this work is again a definition based on a lower
bound on the amount of EF traffic that must depart from a router 
in a generic interval. 

The redefinition appears to be of similar complexity than 
the one provided in draft-charny :-(
In fact the arrival times and lenghts of the packets in the 
generic (t1,t2) must be taken into account and compared to 
the configured EF rate in a non-trivial way.

Only if you are interested in this exercise... you can give 
a look below or better get:

ftp://ftp.coritel.it/pub/id/not-simpler-ef.pdf

where beatiful pictures explain the proposed definitions  

Regards,
Stefano

 Let (t1,t2) be a generic time interval. Assume that K packet directed
 to a given output port has entered the router in this interval, let
 Tin(i) be the time that the i-th packet has entered the router and
 let L(i) be the packet length. Let O(t1,t2) be the amount of EF
 traffic that exited the given port in the interval (t1, t2). A packet
 has entered the router when the last bit of the packet has entered
 the router and it has exited the router when its last bit has left
 the router.

 A node supports the EF PHB at a rate R with a latency term E if for
 each t1 and t2, where t2 > t1

 O (t1, t2+E) >= LB (K)

 Where LB(i) represents the lower bound on the amount of EF traffic
 that must exit the router in (t1, t2+E) taking into account the
 arrival of packets from 1 up to i.
 LB(i) is evaluated considering the ingress packet times and packet
 lengths and the auxiliary function A(i) as follows:

 For i = 1:

 LB(1) = min ( L(1), R*(t2-Tin(1)) )
 A(1) = max ( 0, R*(t2-Tin(1)-L(1) )

 And for i = 2 .. K:
 LB(i) = LB(i-1) + min ( L(i), R*(t2-Tin(i)), A(i-1) )
 A(i) = max ( 0, min ( R*(t2-Tin(i)), A(i-1)) _ L(i) )

 The auxiliary function A(i) takes into account the amount of traffic
 that can be still provided to the EF aggregate for packets arriving
 after packet i.

 The above bound applies under the hypothesis that no loss occurs for
 the EF traffic under observation.

 Note that actually the lower bound on the amount of output traffic in
 the interval (t1,t2+E) depends on the amount of input traffic in the
 interval (t1,t2)

 3.  Comments

[...]

 The explanation and the derivation of the lower bound is given below.
 As shown in figure 1, one has to consider the arrivals of packets in
 the interval (t1,t2).

                    Figure 1

 Consider the first packet that enters the router in the interval
 (t1,t2) at time tin(1). This packet will bring a contribution to the
 output traffic which is bounded by the EF configured rate multiplied
 by the duration t2-tin(1).
 If L(1)< R*(t2-Tin(1)) as in figure 2, the LB(1) is equal to L(1) and
 there is some capacity left for the EF aggregate in the (tin(1),t2)
 interval which is taken into account by A(1).

                    Figure 2

 If L(1)>= R*(t2-Tin(1)) as in figure 3, the LB(1) is equal to
 R*(t2-Tin(1)) and there is no capacity left for the EF aggregate in
 the (tin(1),t2) interval. Therefore A(1)=0.

                    Figure 3

 When the generic packet i enters the router, if there is some
 capacity left (i.e. A(i-1)>0) then the Lower Bound on the output
 traffic must be updated. In this case we have to consider that the
 packets that has already entered the router can be still in the
 router or not. Therefore we assume that the EF traffic is serviced at
 least at the EF configured rate and we can identify two cases:
 a) a packet arrive and there can be still an amount of EF traffic in
 the router
 b) a packet arrives when the all the EF traffic has exited the router
 It can be easily shown that case a) holds if tin(i)<t2-A(i-1)/R and
 case b) holds if tin(i)>=t2-A(i-1)/R.

 Hereafter the examples show how to calculate the LB and A for the
 second packet.
 Figure 4 shows what happens if the packet 2 arrives and there can be
 still EF traffic in the router.
     
                    Figure 4

 Figure 5 shows what happens if the packet 2 arrives when all the EF
 traffic must have exited the router considering at least the rate R.
     
                    Figure 5

 The example for packet 2 can be generalized, the generic formulas for
 the i packet are:
 
[...] 
more on ftp://ftp.coritel.it/pub/id/not-simpler-ef.pdf