Subject: Re: Comments on "Flow Grouping" RFC

From: [email-masked] (Konstantinos Dovrolis)
Date: Wed, 23 Jul 1997 10:38:37 -0500

Roch,

It seems that something is wrong with the int-serv list server
because I (and I guess nobody else) received an e-mail
that I sent yesterday to Sanjeev and Christophe addressing some 
of the points that you make today.

So I first include that e-mail, and then I comment on your
points.

------------------------
Sanjeev and Christophe,

I read your messages carefully and I see your points regarding Ctot.
Indeed, if Ctot=KM for a flow with maximum packet size M
and with K  network elements along the flow's path, grouping 
N flows will result to Ctot=KM+(N-1)M = (K+N-1)M, and not
Ctot=K(N-1)M as I claimed before. I hope that I didn't cause
a lot of confusion...

However I still have some comments on the benefit that will
result from flow grouping.

1) The 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).

When we group N flows the reduction in the reserved rate R comes
only because Ctot does not increase proportionally to N. The point 
is: how important is the term Ctot compared to the term p x?
Note that p x is normally larger than the burstiness parameter b.
I know that for video streams (either video-conferencing, or 
movies) the burstiness b is often much larger than Ctot. Perhaps
the situation is different for audio applications where the 
burstiness is not so large.

In general, I think that it is a good idea if you do some calculations 
to quantify the benefit in terms of R that will result with flow
grouping for "typical" values of flow and network parameters.
Are we talking for some significant amount of bandwidth, or this
benefit is a second-order effect? 

2) I think that the calculation of the reserved rate should take
into account the peak rate, and not the approximations that set p=inf.
In anyway, the receivers will not make this approximation when they
calculate R. It is also clear from the above formula that if you 
set p=inf, the benefit that results from flow grouping appears as
larger (because p x > b-M).

3) As I mentioned in my first e-mail, if the grouped flows do not
have the same parameters, the envelope of the grouped flow consists
of several straight-line segments with gradually decreasing slopes.
The relation between the reserved rate R and the delay bound D
becomes more complicated, and
if we want the receiver to be able to calculate
accurately the reserved rate that is required for a delay bound D,
the Tspec has to be extended to cover multiple token bucket parameters.
As it is defined up to now, the only defined parameters are: b,r,p,M,m.

Please do not misunderstand my comments. I have them because I think
that your idea of flow grouping is interesting. It is just not clear
to me yet why are we having this bandwidth reduction (with a simple
and intuitive explanation) and how important is it.

Sincerely,
                      -- Constantinos Dovrolis 

------------------------

Now, regarding Roch's comments:

> 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
> identical flows: 
> 
> >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. 
> 
> 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.
> 

We now agree on the 2Ctot term (see above). But, I will insist that
x does not change. The "M" that appears in the x term is not the
maximum packet size. It is the value of the group's envelope at 
tau=0. In other words, it is the maximum amount of bytes that the
network can receive from the grouped flow instantaneously. And this
is NM, where N is the number of grouped flows. Please let me know
if you have a different opinion on this.

The next paragraph of your e-mail Roch refers to the Ctot term,
and as I wrote above, you are right, I am wrong. In fact, I believe that
the only rate reduction from flow grouping comes from the Ctot term.
But I have already written this above.

Sincerely,

                      -- 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: Roch Guerin <[email-masked]>
Date: Wed, 23 Jul 97 11:47:24 -0400

Konstantinos,

Something must indeed be wrong with the mailing list, and thanks for
forwarding the other note.  After reading it, I think we are in sync
as indeed you get nb-nM (M is now the max pkt size) when grouping n
identical flows.  I went over your note too quickly (too many things
at once ;-) and did not really take the time to work through what each
term was and how it should be modified.
Roch

---

From: [email-masked]
Date: Wed, 23 Jul 97 12:52:08 -0400

Konstatinos,

Fully agree with you that it would be good to quantify how much benefit 
there really is with grouping and one may want to use it only in 
cases where there is reasonable benefit. Also as I mentioned earlier, 
it may even be possible to extend this grouping on a per-node 
basis so that all flows coming in on the same input link and leaving on 
the same output link are grouped. That can lead to even greater benefits. 

I recall a posting from Srinivasan Keshav from Bell Labs many months 
back on the amount of reservation needed for Guaranteed Service for 
various combinations of data rates, max packet sizes, delay bounds etc
and those indicated a large contribution to the delay from the C_tot/R
term in many cases. Unfortunately I don't recall the exact numbers ...
Clearly grouping has benefits mainly when the C_tot/ R term is a 
significant part of the end-to-end delay (e.g. low data rate 
applications, large packets ...). 

Basically note that the term C_tot/R becomes a significant contributor to 
the delay in cases when it is not feasible to perform much reshaping
(i.e. have R much lower than the peak rate) so that the b/R reshaping 
delay is small. As an example, when R > p, note that the end to end delay 
becomes (M + C_tot)/ R + D_tot so that C_tot (which is (N-1)M) is clearly
dominant over the b term (which is simply M in that case). 

In general, when packetization delays are significant as compared to 
reshaping delays (b/R) and  constant delays (D_tot) then there may be  
benefit from flow grouping. 

Sanjeev. 

ps: If C_tot/R was *never* a signifncant contributor to the delay, then 
maybe most implementations would just ignore the term or approximately 
account for it  with a higher D_tot or whatever so that term would be 
sorta useless anyways :-)).