Subject: Re: Comments on "Flow Grouping" RFC

From: [email-masked] (Konstantinos Dovrolis)
Date: Fri, 18 Jul 1997 12:04:41 -0500

Dear Christophe,

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

Correct. This is why we should not assume that p=inf. In any real network
interface, p is finite and if you exploit this you can meet a delay bound
with a rate that is smaller than the rate that you would need if p=inf.
Both the receiver (that is the one who requests the reservations)
and the network elements (that actually make the reservations) will be
interested in minimizing the reserved rate that is needed for a delay
bound. Why would anybody do the assumption p=inf? If the relation
between R and D or the admission control tests were really complicated, 
perhaps this approximation would help. But for WFQ or even for EDF (with
the RCS parameters given in the SIGCOMM'96 paper by Guerin et al.) these
calculations are simple.  

> 
> 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 do not agree. Here is a simple example: assume that each of the two
flows sends only one maximum-size packet M  (hmmm....  I guess that 
somebody will say that this in not really a flow...)
Anyway, the traffic envelope of the grouped flow is 2M.

Suppose now that the two flows generate their packets simultaneously
and that we have reserved a rate Rg at each network element of the
grouped flow's path.

The delay bound of the second packet after the first hop is
2M/Rg + D1, where D1 is the propagation and non-preemption latencies
at the first hop.

At the second hop the same thing happens: the two packets are still one
after the other (assuming that the transmission of the second
packet cannot be preempted by another packet)
and the delay bound for the second packet is:

2(2M/Rg) +D1+D2

After K network elements the delay bound for the second packet
becomes: 

2KM/Rg + Dtot = 2Ctot + Dtot. 

I hope that this helps.

Regards,

                      -- 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: Tue, 22 Jul 97 11:54:21 -0400

Konstatinos, 

Some quick replies to your comments from last week:

(Been having mailer foulups the last couple of days so apologise for 
the late response or if this is a duplicate ...). 

Your assertion that using a finite peak rate instead of the infinite 
peak rate approximation nullifies the benefits of flow grouping is 
incorrect. There will be rate reduction for both infinite and finite 
peak rate cases. 

The bandwidth reduction (or really the delay bound reduction which we exploit 
to then reduce the rate) occurs because the contribution of the C_tot /R 
term is reduced via grouping. (We cannot alter the b/R component 
nor the D_tot component of the end to end delay bound but we can play with 
C_tot/R ). 

(ps: Christophe, you will see that we exploit the delay bandwidth coupling 
property here by  increasing the denonimator (R) while not 
necessarily increasing C_tot by the same ratio). 

This is true for both infinite and finite peak rates. This was correctly
pointed out by  Christophe and I believe your counter argument to that 
was not quite correct. Another way of seeing it is that if we have a single
flow and an ``infinite'' peak rate, just because we get two back to back
packets of size M doesn't mean that the max packet size 
of the flow is 2M, it is still M. 

Basically this is because of the ``serialization'' of packets that occurs 
after the first hop. The flow group can in fact be treated like a single flow
with max packet size M. 

However you are correct that for the new term which 
is contributed by the finite peak rate (the [ (b - M)/R*(p - R)/ (p - r)} or 
whatever we must use 2M instead of M. However the C_tot term which is what 
really causes the rate reduction does not follow along the same lines. 
Also, we would have to inform intermediate 
nodes that the max packet size is still M but the receiver which calculates 
the delay bound would need to use n*M for this component of the delay term ...
However it remains that there is a reduction in the C_tot/R term. 

Incidentally you can extend the same argument to note that all packets 
from the same upstream link and being routed to the same output link at a node 
can infact be potentially grouped (even if their ultimate origin nodes were 
different) because they have been ``serialized'' by the upstream node). 
So there is potentially even more benefit possible. However there are 
some other issues to be sorted out there ...

Does this make sense ? Or is there something I have missed ?
 
Thanks. 
Sanjeev.

---

From: [email-masked] (Konstantinos Dovrolis)
Date: Tue, 22 Jul 1997 13:45:04 -0500

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