Subject: [rmcat] Fw: New Version Notification for draft-hayes-rmcat-sbd-00.txt

From: David Hayes <[email-masked]>
Date: Fri, 10 Oct 2014 17:37:10 +0200

Dear All,

We have just submitted of our initial shared bottleneck detection
draft and will value your comments and suggestions.

Regards,

David 

Begin forwarded message:

Date: Fri, 10 Oct 2014 08:17:57 -0700
From: <[email-masked]>
To: Michael Welzl <[email-masked]>, David Hayes
<[email-masked]>, Michael Welzl <[email-masked]>, Simone Ferlin
<[email-masked]>, Simone Ferlin <[email-masked]>, David Hayes
<[email-masked]> Subject: New Version Notification for
draft-hayes-rmcat-sbd-00.txt

A new version of I-D, draft-hayes-rmcat-sbd-00.txt
has been successfully submitted by David Hayes and posted to the
IETF repository.

Name:		draft-hayes-rmcat-sbd
Revision:	00
Title:		Shared Bottleneck Detection for Coupled
Congestion Control for RTP Media. Document date:	2014-10-10
Group:		Individual Submission
Pages:		12
URL:
http://www.ietf.org/internet-drafts/draft-hayes-rmcat-sbd-00.txt
Status:         https://datatracker.ietf.org/doc/draft-hayes-rmcat-sbd/
Htmlized:       http://tools.ietf.org/html/draft-hayes-rmcat-sbd-00

Abstract:
   This document describes a mechanism to detect whether end-to-end data
   flows share a common bottleneck.  It relies on summary statistics
   that are calculated by a data receiver based on continuous
   measurements and regularly fed to a grouping algorithm that runs
   wherever the knowledge is needed.  This mechanism complements the
   coupled congestion control mechanism in draft-welzl-rmcat-coupled-cc.

Please note that it may take a couple of minutes from the time of
submission until the htmlized version and diff are available at
tools.ietf.org.

The IETF Secretariat

-- 

-------------------------
David Hayes
[email-masked]
Department of Informatics
University of Oslo

---

From: Mirja Kühlewind <[email-masked]>
Date: Tue, 21 Oct 2014 11:22:09 +0200

Hi David, hi all,

I've read your document and have a couple of questions (as an individual 
contributor):

1) You propose to use the OWD, to do all the calculation at the receiver and to 
signal the information to the sender. Did you also do some analysis how good 
your approach would be if you use RTT (because than the sender could also work 
independent of the receiver)?

2) You also talk about a receiver based approach. I'm not sure if this case is 
needed because that's the case where simply congestion control does its job. 
While if one sender has multiple flows it seems to be more reasonable for me to 
couple these.

3) Am I right to that you need an initial set-up time of 17.5 sec? Can you also 
explain a little further why you've chosen 350ms and N=50?

4) Can you also explain with which (network) effect you have skewness? Is this 
really an effect in real systems that gives you valuable information?

5) If you look at the variance (and use the max) you might want to apply some 
kind of filtering first e.g. to filter out single out liners (due to some 
processing delays).

6) Can you also explain a little more, why you also use the oscillation 
frequency and the value p_v=0.2? While the other metrics actually measures some 
kind of network behavior, e.g. delay variance is determined by the queue size, 
the oscillation size is determined by the congestion control behavior. I guess 
the flows have to use the same congestion control scheme...?

7) For packet loss you can also estimated the loss frequency. I would think if 
the congestion control operates loss-based that this would actually give you a 
pretty good estimate if flows share the same bottleneck. Or even easier if the 
loss of the flows always occur in the same RTT.

8) And one last question regarding the grouping: Do you always need to apply all 
three conditions? Why are those three needed?

Mirja

---

From: Michael Welzl <[email-masked]>
Date: Tue, 21 Oct 2014 11:58:50 +0200

Hi Mirja,

Thanks a lot for reading and for your comments!

I'd like to answer the first two items (and leave the others to my co-authors):

On 21. okt. 2014, at 11:22, Mirja Kühlewind wrote:

> Hi David, hi all,
> 
> I've read your document and have a couple of questions (as an individual contributor):
> 
> 1) You propose to use the OWD, to do all the calculation at the receiver and to signal the information to the sender. Did you also do some analysis how good your approach would be if you use RTT (because than the sender could also work independent of the receiver)?
> 
> 2) You also talk about a receiver based approach. I'm not sure if this case is needed because that's the case where simply congestion control does its job. While if one sender has multiple flows it seems to be more reasonable for me to couple these.

Not only is the RTT noisier, but one can also satisfy the requirement of limiting the amount of signaling while taking enough samples with this approach. If we were to go for a sender-only variant, we'd need to signal much more (even if the RTT was used, we'd need to have some form of per-packet ACK to get as many samples as we now have).

The whole point here was to try to construct something that can work reliably and without requiring too much signaling, hence the receiver / sender split of the algorithm.

Cheers,
Michael

---

From: David Hayes <[email-masked]>
Date: Tue, 21 Oct 2014 17:36:59 +0200

Hi Mirja,

Thank you for going through this and giving your comments and questions!

I have answered your questions inline.

Regards,

David

On Tue, 21 Oct 2014 11:22:09 +0200
Mirja Kühlewind <[email-masked]> wrote:

> 1) You propose to use the OWD, to do all the calculation at the
> receiver and to signal the information to the sender. Did you also do
> some analysis how good your approach would be if you use RTT (because
> than the sender could also work independent of the receiver)?
> 
> 2) You also talk about a receiver based approach. I'm not sure if
> this case is needed because that's the case where simply congestion
> control does its job. While if one sender has multiple flows it seems
> to be more reasonable for me to couple these.
> 
> 3) Am I right to that you need an initial set-up time of 17.5 sec?

Not quite. Decisions can start to be made after T (nominally 350ms),
though with far less accuracy, but increasingly more accurately as
time progresses. This needs to be outlined in the draft. 

> Can you also explain a little further why you've chosen 350ms and
> N=50?

Roughly, T should to be long enough to capture the short term variance
in the OWD, but not too long so as to be able to sample the low
frequency oscillations of OWD on the bottleneck. T=350ms provided
good results (though not necessarily optimal) on the two very different
networks we tested it on in the LCN paper. However, the dynamics on the
Internet can change. T is one the parameters sent in the initialisation
message, so although we want to recommend a good "all round" value for
it, it can be changed to suit specific network dynamics.

The system will need to keep N samples of many of the statistics. With
larger values of N, many of the parameters can be calculated more
accurately (or less noisily), but at the expense of memory and
sensitivity to changing network conditions. Also, if N is too small it
is difficult to get a good freq_est for comparison. N=50 was found to be
good "all round" value in our tests so far. It too is one of the
parameters sent during initialisation, potentially allowing an
application to set it according to its needs for network dynamic
sensitivity. 

> 4) Can you also explain with which (network) effect you have
> skewness? Is this really an effect in real systems that gives you
> valuable information?

OWD skewness (in an abstract way) is a function of the load at the
bottleneck and the traffic dynamics. When a queue becomes congested,
the queue distribution becomes skewed toward the back of the queue (At
extreme loads the dynamic changes again). It is important in the
algorithm for a number of reasons:
	1. If there is no congestion along the path, all of the delay
	statistics are too noisy to be useful for grouping flows
	(there is no bottleneck!). Skewness is used to determine
	whether a flow is experiencing congestion -- or to put it
	another way that the statistics will be reliable for grouping
	flows.

	Other possible metrics could be:
	- magnitude of delay (but we do not know how long the queue is
	  at the bottleneck and what the OWD_min is)
	- loss (loss can be caused by other factors, and may be to rare)
  	- ECN (this will be good in the future, but is not reliable
  	  now - the bottleneck may not be ECN enabled)
	- etc

	Skewness was found to be a reliable congestion indicator that
	did not require any prior knowledge of queuing along the path.

	2. Two similar bottlenecks with similar traffic but different
	loads can exhibit a similar variance, but will have a different
	skewness. This helps to distinguish this case.

> 
> 5) If you look at the variance (and use the max) you might want to
> apply some kind of filtering first e.g. to filter out single out
> liners (due to some processing delays).

This is a good point, especially the further from the network interface
measurements are made. Min would be a better option in terms of noise,
but (in theory) Min is load ambiguous (see 2. above) at similar loads
to where skewness is (there is a discussion in the LCN paper concerning
this). A simple filter, ie second highest OWD, may be enough.

> 
> 6) Can you also explain a little more, why you also use the
> oscillation frequency and the value p_v=0.2? While the other metrics
> actually measures some kind of network behavior, e.g. delay variance
> is determined by the queue size, the oscillation size is determined
> by the congestion control behavior. I guess the flows have to use the
> same congestion control scheme...?
> 

The low frequency oscillation of OWDs at a bottleneck depends on many
things including: the queue size, other traffic at the bottleneck (flows
starting, flows leaving, etc), and the combined behaviour of all of the
traffic's congestion controllers. In our experiments (and general
observations of OWD graphs), the low frequency oscillation of OWDs is
discernibly different between different bottlenecks. This metric tries
to capture that difference with an efficient estimate that can be
easily compared.

We use the short term variation in the signal, p_v, as a guide for
de-noising. The skewness congestion test 4)1. above helps to ensure
that we are measuring a signal and not just noise.

> 7) For packet loss you can also estimated the loss frequency. I would
> think if the congestion control operates loss-based that this would
> actually give you a pretty good estimate if flows share the same
> bottleneck. Or even easier if the loss of the flows always occur in
> the same RTT.

When the the packet loss rate is high, this becomes a reliable measure
and is used by the algorithm. However, when the packet loss rate is low
the signal is too rare to be useful.

Within an RTT (we are looking at OWD) not all flows traversing a
bottleneck will necessarily experience packet loss. Also, not  all flows
will necessarily have the same RTT, having different paths to their
destinations.

Hassayoun, Iyengar, and Ros in their paper "Dynamic window coupling for
multipath congestion control", look at a similar idea for MPTCP. The
SBD is intertwined with the congestion control, and although sufficient
for their purpose, has different objectives and I don't think can be
applied to achieve a reliable grouping in the RMCAT scenario.

> 
> 8) And one last question regarding the grouping: Do you always need
> to apply all three conditions? Why are those three needed?
> 

All the statistics are noisy making fine grain grouping based
on one statistic difficult. Using a number of statistics summarising
different aspects of the signal allows us to more coarsely group based
on each statistic (allowing for the noise) but still obtain a fine
enough grouping.

An aside on the noise: The noise is caused by the same things that we
are looking for in the "signal" from the bottleneck: queueing, packet
loss, etc. The bottleneck "signal" is generally stronger than the noise
from the other devices along the path, but still the signal and noise
have similar characteristics. This similarity makes filtering difficult.

> > <[email-masked]>, Michael Welzl <[email-masked]>, Simone
> > Ferlin <[email-masked]>, Simone Ferlin <[email-masked]>, David
> > Hayes <[email-masked]> Subject: New Version Notification for
> > Status:
> > https://datatracker.ietf.org/doc/draft-hayes-rmcat-sbd/
> >     This document describes a mechanism to detect whether
> > end-to-end data flows share a common bottleneck.  It relies on
> > summary statistics that are calculated by a data receiver based on
> > continuous measurements and regularly fed to a grouping algorithm
> > that runs wherever the knowledge is needed.  This mechanism
> > complements the coupled congestion control mechanism in
> > draft-welzl-rmcat-coupled-cc.
> >
> >
> >
> >

--

---

From: "Michael Ramalho (mramalho)" <[email-masked]>
Date: Tue, 21 Oct 2014 18:19:22 +0000

David/Mirja,

Thank you both for this thread.

This is the first time I recall that someone on the RMCAT list mentioned that an asymmetrical one way delay pdf (i.e., not assuming a symmetric smoothed delayed histogram in our discrete time work) could be used for some useful grouping or congestion purpose.

My only comment is in the thread below that mentions skewness. My comments are prefaced with "MAR:".

Michael Ramalho, Ph.D.

-----Original Message-----
From: rmcat [mailto:[email-masked]] On Behalf Of David Hayes
Sent: Tuesday, October 21, 2014 11:37 AM
To: Mirja Kühlewind
Cc: [email-masked]; Simone Ferlin-Oliveira; Michael Welzl Welzl
Subject: Re: [rmcat] Fw: New Version Notification for draft-hayes-rmcat-sbd-00.txt

Hi Mirja,

Regards,

David

> Hi David, hi all,

**** ... SNIP ... ****

> 4) Can you also explain with which (network) effect you have skewness? 
> Is this really an effect in real systems that gives you valuable 
> information?

OWD skewness (in an abstract way) is a function of the load at the bottleneck and the traffic dynamics. When a queue becomes congested, the queue distribution becomes skewed toward the back of the queue (At extreme loads the dynamic changes again). It is important in the algorithm for a number of reasons:

MAR: I have attached a slide that shows the delay of one VoIP flow when competing with 10 long-lived TCP flows in a bottleneck link of 1.024 Mbps. The VoIP flow is 96 kbps CBR and the TCPs have no propagation delay OTHER than the bottleneck queue (i.e., the measured RTT inside a given TCP is essentially a moving average of the bottleneck queue delay - so the dynamics of the TCPs are primarily a function the bottleneck queue delay evolution in time). The queue length was set so as to equal 500 ms at the link service rate. As there are more and more competing TCPs, the resultant smoothed histogram (bottom graph) has increasingly shorter tails in the direction toward 0 ms (i.e., modes and mean nearer to queue delay max), whereas a histogram from a minimally  utilized system will normally have a tail of the delays away from 0 (with mean and only mode near 0 ms).

MAR: So clearly competing with more sources that demand queue overflow for their congestion control will affect the observed skewness - with more "congestion" (I desire a better definition of that term) resulting in "tail skewness toward zero" and less variance about the mean (of the delay histogram).

MAR: If all competing flows are RMCAT flows, we expect them to oscillate about some equilibrium queue delay (hopefully some small amount) and thus should expect a "symmetric" distribution about this equilibrium (mean) value (assuming the queue never drains completely). When there are small periods of time with "no instantaneous congestion" (the queue drains every so often), there is yet again some bias toward the minimum OWD (and another mode in the distribution near zero queue delay).

MAR: Of course, if there are multiple bottlenecks - each experiencing some congestion - you can expect a convolution of the distributions resulting in multiple modes (i.e., multiple local maxima in the OWD histogram). So I am doubtful that this technique could be used for such cases - but I am listening here if you have analytical understanding counter to my intuition (that happens!).

MAR: Again, I have not thought of using such a metric ... but perhaps high skewness about a mean in a cluster of individual OWD data points near to the highest delay for the queue could signal such a congestion by non-delay adaptive sources. And  I think in this case a lower variance might indicate "more competing sources" (similar to my multiple TCP experiment).

MAR: Since the two "similar bottlenecks" (i.e., similar service rates) could have differing buffer lengths in front of them (i.e., the maximum delay of the two individual bottlenecks could be very different), I don't see how you can use this technique to differentiate between them. It looks like you assumed the two bottlenecks had similar worst-cast queuing delays (a poor assumption because one of the bottleneck links is often the access link with a typically larger worst-case delay).

MAR: For two bottlenecks each having traffic that demands queue overflow for their congestion control (e.g., TCP) I would expect the convolution of the individual modes. If the mean delay of both were sufficiently different, one might be able to differentiate the skewness of the individual modes for grouping purposes. Would be a nice Masters project to investigate (got a student in mind?).

> liners (due to some processing delays).

This is a good point, especially the further from the network interface measurements are made. Min would be a better option in terms of noise, but (in theory) Min is load ambiguous (see 2. above) at similar loads to where skewness is (there is a discussion in the LCN paper concerning this). A simple filter, ie second highest OWD, may be enough.

MAR: Outliers are outliers - you can't assume "just one" (in picking the "second highest OWD"). To do this correctly statistically you need to use clustering techniques to make sure your "max or min" samples are reasonable data points - but perhaps using data points within the CDF 5% to 95% region are good enough for a unimodal OWD histogram.

---

From: David hayes <[email-masked]>
Date: Tue, 21 Oct 2014 22:07:58 +0200

Hi Michael,

Thank you for your comments and suggestions, and your interest in
skewness. Thank you also for your illustrative figure.

It is probably good to note that although we talk about skewness, the
mechanism uses an estimate of skewness. It is not exactly the same
(much easier to calculate), but it does retain the properties that we
want for the mechanism.

One of my points I didn't explain clearly and lead you astray (sorry).
I've clarified it below and added some comments.

Thank you again for your interest.

David

On Tue, 21 Oct 2014 18:19:22 +0000
"Michael Ramalho (mramalho)" <[email-masked]> wrote:

> This is the first time I recall that someone on the RMCAT list
> mentioned that an asymmetrical one way delay pdf (i.e., not assuming
> a symmetric smoothed delayed histogram in our discrete time work)
> could be used for some useful grouping or congestion purpose.
> 
> the queue distribution becomes skewed toward the back of the queue
> (At extreme loads the dynamic changes again). It is important in the
> algorithm for a number of reasons: 1. If there is no congestion along
> the path, all of the delay statistics are too noisy to be useful for
> grouping flows (there is no bottleneck!). Skewness is used to
> determine whether a flow is experiencing congestion -- or to put it
> another way that the statistics will be reliable for grouping flows.
> 
> MAR: I have attached a slide that shows the delay of one VoIP flow
> when competing with 10 long-lived TCP flows in a bottleneck link of
> 1.024 Mbps. The VoIP flow is 96 kbps CBR and the TCPs have no
> propagation delay OTHER than the bottleneck queue (i.e., the measured
> RTT inside a given TCP is essentially a moving average of the
> bottleneck queue delay - so the dynamics of the TCPs are primarily a
> function the bottleneck queue delay evolution in time). The queue
> length was set so as to equal 500 ms at the link service rate. As
> there are more and more competing TCPs, the resultant smoothed
> histogram (bottom graph) has increasingly shorter tails in the
> direction toward 0 ms (i.e., modes and mean nearer to queue delay
> max), whereas a histogram from a minimally  utilized system will
> normally have a tail of the delays away from 0 (with mean and only
> mode near 0 ms).
> 
> MAR: So clearly competing with more sources that demand queue
> overflow for their congestion control will affect the observed
> skewness - with more "congestion" (I desire a better definition of
> that term) resulting in "tail skewness toward zero" and less variance
> about the mean (of the delay histogram).
> 
> MAR: If all competing flows are RMCAT flows, we expect them to
> oscillate about some equilibrium queue delay (hopefully some small
> amount) and thus should expect a "symmetric" distribution about this
> equilibrium (mean) value (assuming the queue never drains
> completely). When there are small periods of time with "no
> instantaneous congestion" (the queue drains every so often), there is
> yet again some bias toward the minimum OWD (and another mode in the
> distribution near zero queue delay).
> 

Our experiments to date have been with cross traffic. It will be
interesting to look at this in more detail when RMCAT's congestion
control mechanism is clear.

> MAR: Of course, if there are multiple bottlenecks - each experiencing
> some congestion - you can expect a convolution of the distributions
> resulting in multiple modes (i.e., multiple local maxima in the OWD
> histogram). So I am doubtful that this technique could be used for
> such cases - but I am listening here if you have analytical
> understanding counter to my intuition (that happens!).

I agree that the result of series bottlenecks would result in a
convolution of the distributions of the bottlenecks. However,
bottlenecks in series where the flows traversing them are not disjoint
are beyond what this mechanism can do. I mentioned this with an example
when I presented some results at the London meeting, where the comment
was that this would be very rare in the current Internet topology
anyway.

But back to the basics of the mechanism:  We use estimates of summary
shape metrics to group flows sharing common bottlenecks. Detailed
distributions although interesting and useful for the analysis
are not very practical for the mechanism itself.

> 
> MAR: Again, I have not thought of using such a metric ... but perhaps
> high skewness about a mean in a cluster of individual OWD data points
> near to the highest delay for the queue could signal such a
> congestion by non-delay adaptive sources. And  I think in this case a
> lower variance might indicate "more competing sources" (similar to my
> multiple TCP experiment).
> 
> 	loads can exhibit a similar variance, but will have a
> different skewness. This helps to distinguish this case.
> 

In this hypothetical example, I was meaning to describe two bottlenecks
with disjoint sets of flows traversing each, not two bottlenecks in
series. Sorry for the misunderstanding.

The idea was to make the point that a finite queue can exhibit the
same variance for two different loads, but that the skewness will
generally be different at those same loads.

I suppose the real point here is that having different "views" of the
distribution of delays at the bottleneck (including frequency) enables
the mechanism to better handle the noise in each measure when grouping.

> MAR: Since the two "similar bottlenecks" (i.e., similar service
> rates) could have differing buffer lengths in front of them (i.e.,
> the maximum delay of the two individual bottlenecks could be very
> different), I don't see how you can use this technique to
> differentiate between them. It looks like you assumed the two
> bottlenecks had similar worst-cast queuing delays (a poor assumption
> because one of the bottleneck links is often the access link with a
> typically larger worst-case delay).
> 
> MAR: For two bottlenecks each having traffic that demands queue
> overflow for their congestion control (e.g., TCP) I would expect the
> convolution of the individual modes. If the mean delay of both were
> sufficiently different, one might be able to differentiate the
> skewness of the individual modes for grouping purposes. Would be a
> nice Masters project to investigate (got a student in mind?).
> 
> > 
> This is a good point, especially the further from the network
> interface measurements are made. Min would be a better option in
> terms of noise, but (in theory) Min is load ambiguous (see 2. above)
> at similar loads to where skewness is (there is a discussion in the
> LCN paper concerning this). A simple filter, ie second highest OWD,
> may be enough.
> 
> MAR: Outliers are outliers - you can't assume "just one" (in picking
> the "second highest OWD"). To do this correctly statistically you
> need to use clustering techniques to make sure your "max or min"
> samples are reasonable data points - but perhaps using data points
> within the CDF 5% to 95% region are good enough for a unimodal OWD
> histogram.

-- 

+-------------------------------+
| David A. Hayes		|
| [email-masked]		|
+-------------------------------+

---

From: Dave Taht <[email-masked]>
Date: Tue, 21 Oct 2014 13:15:22 -0700

I am curious as to how these "skewness" plots are being derived?
Packet captures? Samples
from a traffic generator? We have a ton of stuff from netperf-wrapper runs that
might be analyzable via this metric.

---

From: "Michael Ramalho (mramalho)" <[email-masked]>
Date: Tue, 21 Oct 2014 21:27:18 +0000

Hi Dave (Taht),

Those were old plots of mine from a now crusty lab set up. I have much higher precision tools/toys now. I just picked a plot to show the general concept/idea of what I thought the David Hayes draft was attempting to describe in "skewness".

For FIFO, the shape of the OWD pdf can provide information (a first-order guess) on how many sources are contributing to the congestion. On oversubscribed ISP-to-ISP connections, I'll bet you will find a very skinny mode very close to the maximum queue delay on that interconnect. To me, David's {"skewness" + "variance"}  is a first-order proxy for "a shape characterization" for the distribution. I had not thought of those concepts that way before (and indeed, even now am thinking about something better than skewness I might pass by David).

To answer your questions:

1) The 10 long-lived TCPs were generated by an old server sending a very, very long file to another machine one router hop away in a lab. As the bottleneck link was so low (1 Mbps), the old machine had no problem keeping up.

2) The delays were the individual delays of the (96kbps CBR) VoIP on a packet capture. The VoIP packets emulated G.711 sent with ptime = 10ms. With no QoS or AQM (just FIFO), the individual TCP packets had similar delays of course. The different colors on the delay plots were median filtered versions of the original data (the blue line was an 11 point median filter applied to the individual samples).

3) I used MATLAB to generate a smoothed histogram of the delay samples for the period of time in which the TCP packets were competing with the VoIP packets. Namely:

%Create bins for the smoothed pdf (500ms was the highest possible OWD)
x_bins = 0:0.5:max(Packet_delays(1,begin_index:end_index));
%Create the smoothed pdf
ksdensity(Packet_delays(1,begin_index:end_index),x_bins);

... where begin_index and end_index were the discrete-time index for the VoIP flow that corresponded to the start and end times of the TCP flows.

We can continue this thread off the rmcat list for more details (I can think of experiments you can run).

Best,

Michael

-----Original Message-----
From: Dave Taht [mailto:[email-masked]] 
Sent: Tuesday, October 21, 2014 4:15 PM
To: David hayes
Cc: Michael Ramalho (mramalho); [email-masked]; Simone Ferlin-Oliveira; Mirja Kühlewind; Michael Welzl Welzl
Subject: Re: [rmcat] Fw: New Version Notification for draft-hayes-rmcat-sbd-00.txt

I am curious as to how these "skewness" plots are being derived?
Packet captures? Samples
from a traffic generator? We have a ton of stuff from netperf-wrapper runs that might be analyzable via this metric.

---

From: Stefan Holmer <[email-masked]>
Date: Wed, 22 Oct 2014 16:36:32 +0200

Nice draft! I have a few comments:

You're mentioning that skewness would require all delay measurements to be
stored, and therefore you're computing some different metric which is
related to skew. I wonder if it shouldn't be possible to more accurately
estimate the skew from a histogram instead? That way you at least won't
need to store all delay measurements. Might not be worth the trouble if
your metric works well.

As mentioned by Mirja, it seems a bit error prone to use the max of the OWD
(also, shouldn't it be max_T(OWD)?) when computing the PDV.

Somewhat related to this, I wonder if you have any plans to test this
algorithm on WiFi? I have seen many cases of WiFi with a lot of contention
and/or interference, where the delay gets skewed not because lack of
bandwidth, but because of lower layer retransmissions or because the access
point was busy serving someone else for a moment. I wonder if that can
cause you to incorrectly detect shared bottlenecks, where in reality there
was only a shared WiFi... Now that I think of it, the WiFi effect should
result in positive skewness, while you're looking for negative skewness, so
you may be ok here. :)

It would be good to have the diff() operation defined somewhere. Is it the
diff between successive measurements, or the diff between the flows?

/Stefan

---

From: Simone Ferlin-Oliveira <[email-masked]>
Date: Wed, 22 Oct 2014 17:20:00 +0200

Hi Stefan,

Thanks for your comments.

Would you have any traces of such WiFi cases you mention?
We plan to run other tests with the algorithm. I have already an
implementation and we are testing it with wired/3G/4G at the moment.

Simone (co-author)

On 22 October 2014 16:36, Stefan Holmer <[email-masked]> wrote:
> estimate the skew from a histogram instead? That way you at least won't need
> to store all delay measurements. Might not be worth the trouble if your
> metric works well.
>
> point was busy serving someone else for a moment. I wonder if that can cause
> you to incorrectly detect shared bottlenecks, where in reality there was
> only a shared WiFi... Now that I think of it, the WiFi effect should result
> in positive skewness, while you're looking for negative skewness, so you may
> be ok here. :)
>

---

From: Stefan Holmer <[email-masked]>
Date: Wed, 22 Oct 2014 17:22:51 +0200

If you checkout the webrtc repository you'll find one trace under:
webrtc/resources/google-wifi-3mbps.rx. It contains packet arrival times in
nanoseconds (I think) when the sender sent at a constant rate of 3 mbps.

On Wed, Oct 22, 2014 at 5:20 PM, Simone Ferlin-Oliveira <[email-masked]>
wrote:

> need
> cause

---

From: David hayes <[email-masked]>
Date: Wed, 22 Oct 2014 19:12:14 +0200

Hi Stefan,

Thanks for your comments! They are very much appreciated.

I have added some responses inline.

Kind regards,

David

On Wed, 22 Oct 2014 16:36:32 +0200
Stefan Holmer <[email-masked]> wrote:

> You're mentioning that skewness would require all delay measurements
> to be stored, and therefore you're computing some different metric
> which is related to skew. I wonder if it shouldn't be possible to
> more accurately estimate the skew from a histogram instead? That way
> you at least won't need to store all delay measurements. Might not be
> worth the trouble if your metric works well.

The 3rd central moment is difficult to calculate for a
number of reasons. Yes you need the mean to start with, which would
require storing all the delay measurements so that when you have the
mean, you can compare them with it. The other problem is, that being a
cubic function, it is very sensitive to outliers and therefore requires
a high number of samples for an accurate result. Skew_est is efficient
to calculate and less sensitive to outliers (the test is only above and
below the mean), meaning we don't need quite as many samples.

Using a histogram was one of the ideas I looked at. In the end I didn't
go with it for the following reasons. To do this we need to know what a
good bin size is, and probably need to use the same bin size for each
flow (a common base for comparing). If we know the min/max network
delays of every flow we can work out a good bin size, but
generally we don't know this a priori -- and it could also change with
new flows or changes in the network paths. We could use the previous
NT's PDV as a guide for this, but the flows we are comparing with are
probably going to different receivers. In this case we would need to
communicate the information between sender and receivers.

> 
> As mentioned by Mirja, it seems a bit error prone to use the max of
> the OWD (also, shouldn't it be max_T(OWD)?) when computing the PDV.
> 

max_T would be more consistent with our notation. Thanks.

We used max_T instead of min_T because of their relationship to
skew_est in a MM1K queueing model(LCN paper). However, the difference
between MM1K and real networks and the problem of coping with outliers
and may make min_T a better choice. In our tests we did not have any
significant problems, but we would not have had processing delays Mirja
pointed to.

> algorithm on WiFi? I have seen many cases of WiFi with a lot of
> contention and/or interference, where the delay gets skewed not
> because lack of bandwidth, but because of lower layer retransmissions
> or because the access point was busy serving someone else for a
> moment. I wonder if that can cause you to incorrectly detect shared
> bottlenecks, where in reality there was only a shared WiFi... Now
> that I think of it, the WiFi effect should result in positive
> skewness, while you're looking for negative skewness, so you may be
> ok here. :)
> 
Simone has answered here. Thanks!

> It would be good to have the diff() operation defined somewhere. Is
> it the diff between successive measurements, or the diff between the
> flows?
> 

Can you elaborate on this suggestion a bit more please. Thanks!

> >    This document describes a mechanism to detect whether end-to-end
> > data flows share a common bottleneck.  It relies on summary
> > statistics that are calculated by a data receiver based on

--

---

From: Mirja Kühlewind <[email-masked]>
Date: Wed, 22 Oct 2014 19:36:43 +0200

Hi David,

just again on the skewness point: Form my current understanding what you somehow 
want to measure with this is something like a standing queue..? Still the way 
you calculate the skewness seems very abstract to me. However, if it can be 
shown that this provides useful information, it definitely should be used. The 
question (for all the metrics that you propose) is how can you show that these 
are the right metrics. One approach is definitely to do more measurements in 
various scenario but could you also assess the risk of failures? Or (and this 
potentially is more a question for the cc congestion) how bad is if you group 
two flows together wrongly?

Mirja

-- 
------------------------------------------
Dipl.-Ing. Mirja Kühlewind
Communication Systems Group
Institute TIK, ETH Zürich
Gloriastrasse 35, 8092 Zürich, Switzerland

Room ETZ G93
phone: +41 44 63 26932
email: [email-masked]
------------------------------------------

---

From: Mirja Kühlewind <[email-masked]>
Date: Wed, 22 Oct 2014 19:44:13 +0200

Hi Stefan,

asking this because I'm personally curious but also as rmcat chair:

Are you planning to implement some kind of coupled congestion control in your 
system?

Mirja

Room ETZ G93
phone: +41 44 63 26932

---

From: Michael Welzl <[email-masked]>
Date: Thu, 23 Oct 2014 08:59:03 +0200

Hi,

Maybe I can help with this bit (and I hope David will correct me in case I put this wrongly) -

On 22. okt. 2014, at 19:36, Mirja Kühlewind wrote:

> Hi David,
> 
> just again on the skewness point: Form my current understanding what you somehow want to measure with this is something like a standing queue..? Still the way you calculate the skewness seems very abstract to me.

My understanding is that the intuition behind using skewness is that you'd get a negative skewness in the OWD distribution only if you have (common) congestion (the queue is often full and sometimes drains).

> However, if it can be shown that this provides useful information, it definitely should be used. The question (for all the metrics that you propose) is how can you show that these are the right metrics. One approach is definitely to do more measurements in various scenario but could you also assess the risk of failures? Or (and this potentially is more a question for the cc congestion) how bad is if you group two flows together wrongly?

Indeed that's a question about coupled-cc. My answer to "how bad is it ..." is: the behavior can be very wrong. E.g., assume priorities of 1/10 vs. 1. Coupled-cc will take the total and divide the rates accordingly. If these flows don't share a common bottleneck, that's just a very wrong thing to do - you may end up giving one flow much less and another flow much more than its own congestion controller has derived.

I think that sort of problem is unavoidable; the best one can do is to try to get the shared bottleneck detection scheme to be as reliable as possible (which is a part of why this work took us a long time, we really do believe that this is pretty reliable) and use it conservatively: e.g., one could turn on coupling only after a minute or multiple minutes of a stable positive signal, and immediately turn it off in case of a negative one. This would be extremely conservative, but I'm just saying it's a parameter that can be tuned.

Cheers,
Michael

---

From: Stefan Holmer <[email-masked]>
Date: Thu, 23 Oct 2014 11:28:22 +0200

On Thu, Oct 23, 2014 at 8:59 AM, Michael Welzl <[email-masked]> wrote:

> > just again on the skewness point: Form my current understanding what you
> somehow want to measure with this is something like a standing queue..?
> Still the way you calculate the skewness seems very abstract to me.
>
> My understanding is that the intuition behind using skewness is that you'd
> get a negative skewness in the OWD distribution only if you have (common)
> congestion (the queue is often full and sometimes drains).
>

Yes, that was my final conclusion about skewness as well when reading the
draft. I think that also should help avoid false classifications of
congestion when the channel periodically goes silent, for instance on some
WiFis. Do you guys have any idea of when this metric might fail?

>
>
> > However, if it can be shown that this provides useful information, it
> definitely should be used. The question (for all the metrics that you
> propose) is how can you show that these are the right metrics. One approach
> is definitely to do more measurements in various scenario but could you
> also assess the risk of failures? Or (and this potentially is more a
> question for the cc congestion) how bad is if you group two flows together
> wrongly?
>
> Indeed that's a question about coupled-cc. My answer to "how bad is it
> ..." is: the behavior can be very wrong. E.g., assume priorities of 1/10
> vs. 1. Coupled-cc will take the total and divide the rates accordingly. If
> these flows don't share a common bottleneck, that's just a very wrong thing
> to do - you may end up giving one flow much less and another flow much more
> than its own congestion controller has derived.
>
> I think that sort of problem is unavoidable; the best one can do is to try
> to get the shared bottleneck detection scheme to be as reliable as possible
> (which is a part of why this work took us a long time, we really do believe
> that this is pretty reliable) and use it conservatively: e.g., one could
> turn on coupling only after a minute or multiple minutes of a stable
> positive signal, and immediately turn it off in case of a negative one.
> This would be extremely conservative, but I'm just saying it's a parameter
> that can be tuned.
>
> Cheers,
> Michael
>
>

---

From: Stefan Holmer <[email-masked]>
Date: Thu, 23 Oct 2014 11:31:52 +0200

> communicate the information between sender and receivers.

Thanks for the background, I haven't researched this much, so I trust your
judgment. :)

> significant problems, but we would not have had processing delays Mirja

I see. As you say, some way of getting rid of outliers is probably a good
idea.

> Can you elaborate on this suggestion a bit more please. Thanks!

It just wasn't immediately obvious to me if diff() in for instance
"diff(freqest)
< p_f" took the difference over freqest over time or the difference over
pairs of flows at one time instant. I assume it's the latter though?

---

From: Stefan Holmer <[email-masked]>
Date: Thu, 23 Oct 2014 11:36:44 +0200

We don't have plans for it right now, but I can imagine that it might
happen sooner or later. I do think this draft could be useful in for
instance mesh conferences where your uplink bottleneck is on your access
link. The main question is if it's reliable enough that the benefits
clearly are greater than the downsides of incorrect classification.

On Wed, Oct 22, 2014 at 7:44 PM, Mirja Kühlewind <
[email-masked]> wrote:

> Are you planning to implement some kind of coupled congestion control in
> your system?
>
> Mirja
>
>
>

---

From: Zaheduzzaman Sarker <[email-masked]>
Date: Thu, 23 Oct 2014 09:51:18 +0000

Hi,

I would also like to see some statistics on the false positives while detecting the shared bottleneck with this method.

BR

Zahed

From: rmcat [mailto:[email-masked]] On Behalf Of Stefan Holmer
Sent: den 23 oktober 2014 11:28
To: Michael Welzl
Cc: [email-masked]; Simone Ferlin-Oliveira; Mirja Kühlewind; David Hayes
Subject: Re: [rmcat] Fw: New Version Notification for draft-hayes-rmcat-sbd-00.txt

On Thu, Oct 23, 2014 at 8:59 AM, Michael Welzl <[email-masked]<mailto:[email-masked]>> wrote:
Hi,

Yes, that was my final conclusion about skewness as well when reading the draft. I think that also should help avoid false classifications of congestion when the channel periodically goes silent, for instance on some WiFis. Do you guys have any idea of when this metric might fail?

Cheers,
Michael

---

From: Varun Singh <[email-masked]>
Date: Thu, 23 Oct 2014 15:26:30 +0300

On Thu, Oct 23, 2014 at 12:36 PM, Stefan Holmer <[email-masked]> wrote:
> We don't have plans for it right now, but I can imagine that it might happen
> sooner or later. I do think this draft could be useful in for instance mesh
> conferences where your uplink bottleneck is on your access link. The main
> question is if it's reliable enough that the benefits clearly are greater
> than the downsides of incorrect classification.
>

In a mesh the endpoint already knows that the outbound streams belong
to a group and the main thing to figure out which ones share a common
bottleneck, if not all of them.

Another possible simplification is that the flows are carrying the
same content, but may be at different rates (if each has an
independent congestion controller).

>
> On Wed, Oct 22, 2014 at 7:44 PM, Mirja Kühlewind
> <[email-masked]> wrote:
>>
>> Hi Stefan,
>>
>>> contention
>>>> data

-- 
http://www.netlab.tkk.fi/~varun/

---

From: David Hayes <[email-masked]>
Date: Thu, 23 Oct 2014 15:40:24 +0200

Hi Zahed and Stefan,

Thank you for your interest.

Our initial work has been presented in the LCN paper
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6925767

The detailed algorithm presented in the draft has some
improvements for implementation and robustness (over that used to
produce the LCN paper results). I will present some results using the
draft algorithm at the meeting in Honolulu.

We are currently working on quantitative statistics. Networks are
dynamic, and so are bottlenecks. It is also not just a right and
wrong answer. Our current work is looking at this in terms of "complete
group", "incomplete group", and "false group". We will be using the raw
queue data to independently (of the algorithm) determine bottlenecks.
I don't think this will be ready by Honolulu.

In addition to this, a coupled congestion controller may not want to
change coupling every T seconds, even if that reflects what is actually
happening in the network. What it should do may depend on all sorts of
things, possibly including the codec used. We plan to add a section to
the draft discussing this, and include recommendations on using the SBD
signal for different requirements.

Kind regards,

David

On Thu, 23 Oct 2014 09:51:18 +0000
Zaheduzzaman Sarker <[email-masked]> wrote:

> Hi,
> 
> I would also like to see some statistics on the false positives while
> detecting the shared bottleneck with this method.
> 
> BR
> 
> Zahed
> 
> Cc: [email-masked]; Simone Ferlin-Oliveira; Mirja Kühlewind; David
> Hayes Subject: Re: [rmcat] Fw: New Version Notification for
> On Thu, Oct 23, 2014 at 8:59 AM, Michael Welzl
> <[email-masked]<mailto:[email-masked]>> wrote: Hi,
> 
> > just again on the skewness point: Form my current understanding
> > what you somehow want to measure with this is something like a
> > standing queue..? Still the way you calculate the skewness seems
> > very abstract to me.
> 
> My understanding is that the intuition behind using skewness is that
> you'd get a negative skewness in the OWD distribution only if you
> have (common) congestion (the queue is often full and sometimes
> drains).
> 
> Yes, that was my final conclusion about skewness as well when reading
> the draft. I think that also should help avoid false classifications
> of congestion when the channel periodically goes silent, for instance
> on some WiFis. Do you guys have any idea of when this metric might
> fail?
> 
> 
> 
> > However, if it can be shown that this provides useful information,
> > it definitely should be used. The question (for all the metrics
> > that you propose) is how can you show that these are the right
> > metrics. One approach is definitely to do more measurements in
> > various scenario but could you also assess the risk of failures? Or
> > (and this potentially is more a question for the cc congestion) how
> > bad is if you group two flows together wrongly?
> 
> Indeed that's a question about coupled-cc. My answer to "how bad is
> it ..." is: the behavior can be very wrong. E.g., assume priorities
> of 1/10 vs. 1. Coupled-cc will take the total and divide the rates
> accordingly. If these flows don't share a common bottleneck, that's
> just a very wrong thing to do - you may end up giving one flow much
> less and another flow much more than its own congestion controller
> has derived.
> 
> I think that sort of problem is unavoidable; the best one can do is
> to try to get the shared bottleneck detection scheme to be as
> reliable as possible (which is a part of why this work took us a long
> time, we really do believe that this is pretty reliable) and use it
> conservatively: e.g., one could turn on coupling only after a minute
> or multiple minutes of a stable positive signal, and immediately turn
> it off in case of a negative one. This would be extremely
> conservative, but I'm just saying it's a parameter that can be tuned.
> 
> Cheers,
> Michael
> 

--

---

From: Stefan Holmer <[email-masked]>
Date: Thu, 23 Oct 2014 16:01:30 +0200

On Thu, Oct 23, 2014 at 2:26 PM, Varun Singh <[email-masked]> wrote:

> happen

What do you mean with "belong to a group"? What I mean could be useful is
to determine if the bottleneck is shared (e.g., the access link is the
bottleneck) and then use some sort of
coupled cc.

> >>> result in positive skewness, while you're looking for negative
> skewness,
> >>> so
> >>> you may be ok here. :)
> >>>
> Ferlin

---

From: Stefan Holmer <[email-masked]>
Date: Thu, 23 Oct 2014 16:03:12 +0200

Ok, those results would be interesting to see. It's unfortunately pretty
difficult to do quantitative analysis of these things...