Subject: Comments on "Flow Grouping" RFC

From: [email-masked] (Konstantinos Dovrolis)
Date: Thu, 17 Jul 1997 20:10:39 -0500

Dear Sanjeev and Roch, 

I read your Internet draft "Flow Grouping for Reducing Reservation
Requirements for Guaranteed Delay Service". I have the following
question and comment:

Why do you ignore the peak rate p of the flow specification?
In all the related I.Ds it is assumed that a flow is bounded
by min{M+pt, b+rt} (where M is the flow's maximum packet size). 
I think that the approximation that you have made (i.e., that p=inf},
leads to some wrong conclusions.

Let us consider the case of two flows with the same traffic parameters
(M,b,r,p) and the same delay bound request D. For each flow we need
a reserved rate R to meet the delay bound D. For the two flows we 
would need 2R without grouping, and Rg with grouping. In your draft
you show that for the simpler traffic bound {b+rt}, Rg < 2R.
I claim that even with aggregation, Rg=2R.

Here is my explanation:

The bound for the group of the two flows is: min{2M+2pt,2b+2rt}.
Note that although the maximum packet size of the group of the
two flows is still M, the network can receive two such packets
simultaneously. 

The reserved rate R that is required for meeting a delay bound D is:

R = max{r, (p x + Ctot) / (x + D - Dtot) }

where x = (b-M)/(p-r).

(I use here the "standard nomenclature" of the IETF integrated
services framework that is a bit different from the one in your draft).

The term Ctot is K*M where K is the number of network elements that
the flow passes through, and the term  Dtot does not have to do
with any parameter of the flow.

For the group of the two flows we have that:

Rg = max{2r, (2p x + 2Ctot) / (x + D - Dtot) } = 2R

because x remains the same. 

Note that the numerator of the above
fraction has to include the term 2Ctot instead of Ctot, because
the "effective" maximum packet size for the group of the two flows
is 2M and not M. Intuitively, this happens when two maximum-size
packets arrive back-to-back at a network element; the one that is
second will experience a packetization delay of 2M/Rg. Rg has to
be large enough so that this delay is the same with the delay that
would result if the flow was not grouped: M/R. This means that
Rg has to be 2R.

Things become more complicated when flows have different 
traffic parameters. Note that in that case, the group is
bounded by an envelope that has several slopes and it is
more complicated to figure out the relation between
the reserved rate and the delay bound. I think that in that
case also there will be no gain from flow grouping (but I
leave the math to you ;-) ).

                      -- Constantinos Dovrolis 
--------
Graduate student		              [email-masked]
Dept. of Electrical & Computer Engr.          Tel: (608) 262-5130
University of Wisconsin-Madison               Fax: (608) 265-4623
1415 Engineering Drive                        http://www.cae.wisc.edu/~dovrolis
Madison, WI 53706.

---

From: [email-masked]
Date: Fri, 18 Jul 97 11:17:28 -0400

Hello Konstantinos, 

We hadn't considered a finite peak rate as a first approximation.
Even the original Guaranteed Service draft had the delay calculations
based on infinite peak rate. 

It is a good point you have brought up that a finite peak rate 
may nullify the gains of flow grouping. 

Am busy with stuff, so let me look at it over the weekend and get back 
to you next week  :-) ..
Thanks once again. 

Sanjeev.

---

From: Christophe Deleuze <[email-masked]>
Date: Fri, 18 Jul 1997 18:26:21 +0200 (CEST)

Hi,

I read the draft and the comments and would like to do some comments too.

z> I think that the approximation that you have made (i.e., that p=inf},
z> leads to some wrong conclusions.

hum... I may be wrong but... intuitively if p is less than inf, packets will
be injected slower in the network, queues will be shorter and so delay will be
shorter too. I think that considering p=inf is a worst-case.

z> For the group of the two flows we have that:
z> 
z> Rg = max{2r, (2p x + 2Ctot) / (x + D - Dtot) } = 2R
z> 
z> because x remains the same. 
z> 
z> Note that the numerator of the above
z> fraction has to include the term 2Ctot instead of Ctot, because
z> the "effective" maximum packet size for the group of the two flows
z> is 2M and not M. Intuitively, this happens when two maximum-size
z> packets arrive back-to-back at a network element; the one that is
z> second will experience a packetization delay of 2M/Rg. Rg has to
z> be large enough so that this delay is the same with the delay that
z> would result if the flow was not grouped: M/R. This means that
z> Rg has to be 2R.

But don't you thing this can happen only in the first hop? (or rather at the
place where the two flows are grouped). If two packets arrive back-to-back the
second one will have to wait because of the first one, but this does not
increase the delay in each hop (that's what you do by doubling Ctot!)

So your formulae would rather be:

    Rg = max{2r, (2p x + Ctot+M) / (x + D - Dtot) }

I hope someone will clarify it, 'cause I still don't see very clearly why
grouping flows should reduce bandwidth reservation. 

By the way, I think this grouping technique can be very interesting to reduce
computational needs at the scheduler.

------------------
Christophe Deleuze	    Laboratoire d'Informatique de Paris 6 (LIP6)
PhD Student		    Universite Pierre et Marie Curie
[email-masked]          Networks and Performance	
tel (+33) 1 44 27 71 26     (formerly MASI/IBP)

---

From: Roch Guerin <[email-masked]>
Date: Wed, 23 Jul 97 11:16:52 -0400

Konstantinos,
couple of comments on the note you sent earlier.

While accounting for the peak rate will certainly affect when it is
beneficial to group or not in general, I'm not sure I follow what you
are saying in your example.  Specifically, you say for the case of two

>because x remains the same. 

First, I don't think x remains the same as M does not change, but
that's a minor thing, so let's ignore it for the time being.  The more
important aspect is the 2Ctot term that you justify as follows.

>would result if the flow was not grouped: M/R. This means that

I don't really agree with the above.  What you say could be extended
to imply that you would be paying the b/R term at each node, which you
don't.  You will certainly have the possibility of simultaneous
arrivals at the first node, but that's already accounted for in the b
term.  At subsequent nodes, if you get back to back packets it will
typically mean that the second has been served faster than the
service rate at the previous node, so that you don't need to account
for additional delay in that case.  One way to see it is to look at a
special case, where the "reshaping" to rate Rg occurs at the first
node.  From there on, packets are played out by the first node at that
rate and you don't have the kind of situation you describe.  The same
will actually hold independent of where the reshaping delay happens.

To summarize, while peak rate clearly affects things in general, I do
not believe it changes the conclusion that when you have identical
flows on the same path, it always pays to group them.

Roch