Subject: AW: AW: [Diffserv] about the concern of a rate loss in the defin itio n ofdraft-charny-ef-definition-00

From: [email-masked]
Date: Thu, 10 Aug 2000 11:02:04 +0200

Anna,

thanks for your comments which help very much to make the context clearer.

>it is much less clear what 
>it looks like as it traverses a multi-hop DS cloud.

agree. therefore lets take a closer look at the PHB for a SINGLE NODE for the moment.

>First of all, it seems clear that in the very least that B must be at least 
>of the order of the number of inputs, since one EF packet may arrive from 
>each input at the same time and all these packets have to be buffered 
>somewhere. So your suggestion (below) on choosing B=2MTU does not appear to 
>work.   Suppose however,  that you do take B equal to some number N xMTU 
>(where N is the total number of inputs or some other number).  Suppose one 
>packet arrives from each input simultaneously, and they all just leave 
>the  output immediately one after another.  Then the burst at the output 
>link  will be equal to N.

Please notice that the rate R is assigned to the outgoing AGGREGATE of A NODE.
R may not exceed link band width C in bits/s.
Secondly, the buffer B in the definition should be considered for measurement use,
and the tokens are generated in R, not in C.

Lets consider now a router with 2 input ports (P1 and P2) and at least one output port P3.
Each of P1-P3 have a bandwidth of 2xR. Each of the input ports P1 and P2 carries an
EF (R, 2MTU) conform traffic which are to be aggregated into output port P3.
Assume all packets are of the size MTU

                     time --->

                     | T | and T = 2MTU/2R
At the Link of P1:   |x A|A x|x A|x A|A x|....(A packets belong to EF flow)
At the Link of P2:   |x B|B x|B x|x B|x B|....(B packets belong to EF flow)

At the Link of P3:   |x x|A B|B A|A B|A B|....(EF aggregate incl. A packets AND B packets)

The following can be observed from this trivial example:
- 2x2MTUs packet buffer are required in the node as you pointed out
- however, the resulting AGGREGATE would pass through a (2R, B) leaky bucket
  even for B = 1 bit! So NxMTU is not necessary in general.
- the characteristics of each (MICRO-) flow within the aggreagate depends clearly on
  the scheduler applied. But the EF definition applies only to the AGGREGATE.

Therefore we have to separate the internal packet buffer and that
used in the EF definition, conceptually.

Actually the node has performed an ideal Equalization. The equalized EF traffic
however can be disturbed in the next downstream node when multiplexed with
non-EF traffic. The scheduler there has then to keep the EF characteristics
of that NODE conform to the PHB spec.

It is also seen from this example that the intention is to define EF (R, B) for
a particular NODE (per-hop), not the same R and B for an entire DS domain. 

Note that it might be desirable to allow any reasonable B larger than 2MTU.

>This example may seem to suggest that we can just pick B=N^h, where h is 
>the max number of hops and N is the maximum fan-in of all 
>routers.  Unfortunately, even that is not the case, since we also must 
>account for accumulation of jitter of a single flow (note that in the 
>example above there was just a single packet per "flow" - just many flows, 
>each contributing a single packet to a burst).   An example of a network 
>where all links are utilized by EF traffic at most up to a desired fraction 
>alpha, where no EF "flow" traverses more than h hops, and where all 
>schedulers are PQ, in which jitter accumulates in proportion with 
>(1+alpha)^h can be found in 
>ftp://ftpeng.cisco.com/ftp/acharny/aggregate_delay_v4.ps.  This jitter 
>accumulation effect may cause more than one packet per "flow" contributing 
>to a single burst.
>While there are some known results that do allow bounding this jitter 
>accumulation in a general topology network, these results hold for quite 
>small EF utilization factors (see 
>ftp://ftpeng.cisco.com/ftp/acharny/qofis2000.ps) 

still reading your papers. Comments will come afterwards:-)

Regards,

Xiaoning

_______________________________________________
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, 10 Aug 2000 09:25:57 -0400

Xiaoning,

>and the tokens are generated in R, not in C.

That is correct, but the packets are supposed to be served at *at least* 
rate R. If you have PQ, for example, they will be served at rate C.
Insisting on service no faster than R at small time scales means you are 
insisting on a rate-controlled service, as I mentioned in my previous message.
Any work-conserving scheduler will simply drain the whole buffer at link 
rate, if no non-EF packets are in the system.

>used in the EF definition, conceptually.

It is true that the internal buffer and the leaky bucket parameter do not 
have to be the same for all R.  But as R becomes
smaller and the number of inputs becomes larger,  these two numbers become 
very close. In your example above if the
number of inputs is 100 instead of 2,  you will need to buffer almost all 
of the 100 packets that can arrive simultaneously, and for small R your
leaky bucket burst will also be close to 100 for any work-conserving 
scheduler, which, in the absence of any non EF traffic, would
simply drain the full buffer at link speed.  If R=C/2, still in this case B 
must be at least 50 packets, since in 100 packet times you should have sent
only 50 packets at rate R, but instead sent 100.

>Note that it might be desirable to allow any reasonable B larger than 2MTU.

The point I was trying to make is that you would typically not 
deterministically *know* how big B should be for a given node
inside the domain, because B does not depend only on the local 
characteristics of the node, but on the topology
and traffic characteristics upstream in the domain.  So it would not be 
clear how to use your definition with *numeric* parameters inside the domain.

Anna

>still reading your papers. Comments will come afterwards:-)

---------------------------------------
Anna Charny
Cisco Systems, Inc
300 Apollo Drive
Chelmsford, MA  01824
Tel. (978)-244-8172
Fax (978)-244-8126

---

From: Shahram Davari <[email-masked]>
Date: Thu, 10 Aug 2000 08:11:17 -0700

Xia,

Now let me give you a counter-example:

Lets consider now a router with 3 input ports (P1,P2,P3) and at least one
output port P4.
Each of P1-P4 have a bandwidth of =6xR. Each of the input ports P1 and P2
carries an EF (R, 2MTU) conform traffic which are to be aggregated into
output port P4.
Assume all packets are of the size MTU, and B=2MTU

                     time --->

At the Link of P1:   |xxxxxA|Axxxxx|xxAxxx|....(A packets belong to EF flow)
At the Link of P2:   |xxxxxB|Bxxxxx|xxBxxx|....(B packets belong to EF flow)
At the Link of P3:   |xxxxxC|Cxxxxx|xxCxxx|....(B packets belong to EF flow)

At the Link of P4:   |xxxxxx|ABCxxx|ABCxxx|....(EF aggregate incl. A, B, C
packets)
				    <------>
                                t

Now according to your definition the P4 flow must pass TB(3R, 2MTU), but as
you can see the packet C in the time interval "t" won't pass your TB,
because the first two packets (A, B) will drain the TB and it will take
MTU/3R time for the TB to be able to pass another MTU size packet, while the
C packet arrives only MTU/6R after packet "B".

Regards,
-Shahram

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]]
>Sent: Thursday, August 10, 2000 5:02 AM
>To: [email-masked]
>Cc: [email-masked]; [email-masked]
>Subject: AW: AW: [Diffserv] about the concern of a rate loss in the
>defin itio n ofdraft-charny-ef-definition-00
>
>
>Anna,
>

---

From: [email-masked]
Date: Fri, 11 Aug 2000 11:29:52 +0200

Shahram,

>Xia,
please use Xiaoning as a whole name, it has then another meaning in chinese:-). Thanks.

                     

>At the Link of P4:   |xxxxxx|ABCxxx|ABCxxx|....(EF aggregate incl. A, B, C packets)
>				    
>

If you consider the leaky bucket rate of 3R, you would have emptyed packet A
as C arrive so that no more 2 packet can be at the same time in the buffer.

At the Link of P4:   |xxxxxx|ABCxxx|ABCxxx|....(EF aggregate incl. A, B, C packets)
At the leaky bucket: |no EF-|A B C |....
                               ^ no more bit of A in the buffer

The max allowed number of back to back MTU-sized packets N < 6R x 2MTU/3R/MTU.
 
Clearly what you could not do is to allow large delay and running at rate 6R at the same time,
as I pointed out in the last mail to Anna. Please see the following:

At the Link of P1:   |xxxxxA|Axxxxx|Axxxxx|....(A packets belong to EF flow)
At the Link of P2:   |xxxxxB|Bxxxxx|Bxxxxx|....(B packets belong to EF flow)
At the Link of P3:   |xxxxxC|Cxxxxx|Cxxxxx|....(B packets belong to EF flow)

At the Link of P4:   |xxxxxx|ABCBCA|ABCxxx|xxxxxx|
 
I think this is what an EF-capable scheduler SHOULD avoid to do, which is not really
contradictary to the DEF1 of your draft proposal, because  the choice of
d(j) <= F(j) + E is not unique. (the question is only how can you say something is
DEF1 compliant by measurement).

Regards,

Xiaoning

---

From: Shahram Davari <[email-masked]>
Date: Fri, 11 Aug 2000 07:21:39 -0700

Xiaoning,

>Sent: Friday, August 11, 2000 5:30 AM
>To: [email-masked]
>Cc: [email-masked]; [email-masked]; [email-masked]

By coincidence I gave an example right at the boundary. Now let's assume a
link rate of 10R, then you will have:

At the Link of P1:   |xxxxxxxxxA|Axxxxxxxxx|....(A packets belong to EF
flow)
At the Link of P2:   |xxxxxxxxxB|Bxxxxxxxxx|....(B packets belong to EF
flow)
At the Link of P3:   |xxxxxxxxxC|Cxxxxxxxxx|....(C packets belong to EF
flow)

At the Link of P4:   |xxxxxxxxxx|ABCxxxxxxx|ABCxxxxxxx|
                		        <---- t --->

If you have a leaky bucket of rate 3R, then the arrival time of the last bit
of each packet and the EF bucket occupancy at that time in interval "t" are:
        
	 Packet
     arrival time		buffer occupancy

A       MTU/10R                MTU            
B       2MTU/10R		       2MTU
C       3MTU/10R               3MTU
x       4MTU/10R               2MTU (packet A goes out)
x       5MTU/10R               2MTU
x       6MTU/10R               2MTU 
x       7MTU/10R               MTU (packet B goes out)
x       8MTU/10R               MTU
x       9MTU/10R               MTU
x       10MTU/10R              0

As you can see there are instances that the buffer occupancy is more than
2MTU. In other words by the time that  B and C arrive, A still has not
departed from the leaky bucket.

>The max allowed number of back to back MTU-sized packets N < 

First of all I don't know where you got this limit from. Secondly RFC-2598
and certainly our draft does not set any limit on the number of back-to-back
packets. This limitation is not necessary and not practical unless you shape
in the core of a Diffserv network.

>I think this is what an EF-capable scheduler SHOULD avoid to 
>do, 

On the contrary, if you use a PQ scheduler, this is exactly what you would
get. And PQ is considered the best scheduler in RFC-2598 and VW-PDB.

which is not really
>DEF1 compliant by measurement).

Of course it is not unique. We are setting an upper bound on the departure
time of a packet, if it departs earlier it is definitely better, rather than
departing later. What you are suggesting is that because you have a
(unnecessary) TB in the downstream node therefore we are not allowed to send
the EF packets as soon as they arrive, or in other words you are excluding
PQ scheduler as a legitimate scheduler for EF.

I think your confusion comes from the fact that you like the EF packets to
be equally spaced even in the core of the Diffserv, which as I said is not
practical unless you shape it at every link.

Regards,
-Shahram