Use bayesian estimate of acked bitrate.

Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short period of very few packets delivered, followed by the rate resuming at the regular rate. It specifically avoids the BWE going down to super low values as a response delay spikes.

BUG=webrtc:6566
R=terelius@webrtc.org

Committed: https://crrev.com/492ee28b731e33913acbd4bd62dd45432df58af2
Cr-Commit-Position: refs/heads/master@{#14802}

[stefan-webrtc, 2016-10-17 01:52:27]

The CQ bit was checked by stefan@webrtc.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-17 01:52:31]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...

[commit-bot: I haz the power, 2016-10-17 02:28:53]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-17 02:28:54]

Dry run: Try jobs failed on following builders:
  presubmit on master.tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/presubmit/builds/9210)

[stefan-webrtc, 2016-10-20 03:56:09]

rebase

[stefan-webrtc, 2016-10-20 04:16:39]

Description was changed from

==========
Use bayesian estimate of acked bitrate.

Fix simulator

BUG=
==========

to

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
==========

[stefan-webrtc, 2016-10-20 04:18:23]

The CQ bit was checked by stefan@webrtc.org to run a CQ dry run

[stefan-webrtc, 2016-10-20 04:18:31]

stefan@webrtc.org changed reviewers:
+ terelius@webrtc.org

[commit-bot: I haz the power, 2016-10-20 04:18:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...

[terelius, 2016-10-21 10:15:52]

Great to hear that this is getting solved!

Some questions/comments below:

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:55: // current estimate,
and how many payloads it based on.
nit: it is based on

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:56: float
sample_uncertainty =
This essentially means that we make smaller changes to the estimate if the
difference between the estimate and the measured value is large.
Shouldn't the sample uncertainty be based on the spread of recently measured
values instead? For example
sample_var = 1/N \sum (x_i - x)^2   where x = 1/N \sum x_i

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:69: bitrate_estimate_ =
I believe that the reason we are slow to recover from a delay spike is that we
weight the measurement and the previous estimate differently, and the weights
changes during the execution. Since this update is similar, we should monitor
the variances to ensure that we don't get the same problem here.

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:71:
bitrate_estimate_std_ * bitrate_estimate_std_;
This update could alternatively be written as

estimate = (estimate*(sample-estimate)^2 + sample*old_estimate_std^2) /
           ((sample-estimate)^2 + old_estimate_std^2)

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:94: return
bitrate_estimate_ * 1000;
Why multiply by 1000?

[stefan-webrtc, 2016-10-24 10:55:14]

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:55: // current estimate,
and how many payloads it based on.
On 2016/10/21 10:15:52, terelius wrote:
> nit: it is based on

Done.

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:56: float
sample_uncertainty =
On 2016/10/21 10:15:52, terelius wrote:
> This essentially means that we make smaller changes to the estimate if the
> difference between the estimate and the measured value is large.
> Shouldn't the sample uncertainty be based on the spread of recently measured
> values instead? For example
> sample_var = 1/N \sum (x_i - x)^2   where x = 1/N \sum x_i

Yes, maybe. I'm worried that the window would have to be too large, which is why
I went with this approach. I can run some tests with your suggestion though. It
should in theory have similar properties, but I'm afraid that the averaging may
mean that a single deviating sample won't be suppressed as much as we'd like?

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:69: bitrate_estimate_ =
On 2016/10/21 10:15:52, terelius wrote:
> I believe that the reason we are slow to recover from a delay spike is that we
> weight the measurement and the previous estimate differently, and the weights
> changes during the execution. Since this update is similar, we should monitor
> the variances to ensure that we don't get the same problem here.

Good point. The problem would occur if for instance the bitrate temporarily
increases to something very large, and then decreases to something very small.
In that case it may take us a longer time to adapt.

I'm not entirely sure about this approach, so let me know if you have
suggestions. I experimented a bit with a max filter too, which could be an
alternative, and perhaps a bit simpler. A max filter relies more on the window
being correctly chosen though...

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:71:
bitrate_estimate_std_ * bitrate_estimate_std_;
On 2016/10/21 10:15:52, terelius wrote:
> This update could alternatively be written as
> 
> estimate = (estimate*(sample-estimate)^2 + sample*old_estimate_std^2) /
>            ((sample-estimate)^2 + old_estimate_std^2)
>            

Do you prefer that?

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:94: return
bitrate_estimate_ * 1000;
On 2016/10/21 10:15:52, terelius wrote:
> Why multiply by 1000?

I wanted the returned value to be bits/s. Should probably change to bits/s
everywhere instead though.

[terelius, 2016-10-24 11:20:38]

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:56: float
sample_uncertainty =
On 2016/10/24 10:55:14, stefan-webrtc (holmer) wrote:
> On 2016/10/21 10:15:52, terelius wrote:
> > This essentially means that we make smaller changes to the estimate if the
> > difference between the estimate and the measured value is large.
> > Shouldn't the sample uncertainty be based on the spread of recently measured
> > values instead? For example
> > sample_var = 1/N \sum (x_i - x)^2   where x = 1/N \sum x_i
> 
> Yes, maybe. I'm worried that the window would have to be too large, which is
why
> I went with this approach. I can run some tests with your suggestion though.
It
> should in theory have similar properties, but I'm afraid that the averaging
may
> mean that a single deviating sample won't be suppressed as much as we'd like?

Maybe it is difficult to do what I suggested since it would require a list of
recent bitrate measurements, whereas the current window holds a list of packets
which only gives us a single bitrate. Feel free to disregard my original comment
if you want.

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:71:
bitrate_estimate_std_ * bitrate_estimate_std_;
On 2016/10/24 10:55:14, stefan-webrtc (holmer) wrote:
> On 2016/10/21 10:15:52, terelius wrote:
> > This update could alternatively be written as
> > 
> > estimate = (estimate*(sample-estimate)^2 + sample*old_estimate_std^2) /
> >            ((sample-estimate)^2 + old_estimate_std^2)
> >            
> 
> Do you prefer that?

I think I'd prefer
estimate = (sample_var * estimate + old_estimate_var * sample) / (sample_var +
old_estimate_var)

AFAIK, that's the most common form for the bayesian update, and it is
independent of how we estimate the variances. It also makes it clear that we are
taking a weighted average (i.e. that the coefficients sum to 1).

https://codereview.chromium.org/2422063002/diff/100001/webrtc/modules/congest...
webrtc/modules/congestion_controller/delay_based_bwe.cc:94: return
bitrate_estimate_ * 1000;
On 2016/10/24 10:55:14, stefan-webrtc (holmer) wrote:
> On 2016/10/21 10:15:52, terelius wrote:
> > Why multiply by 1000?
> 
> I wanted the returned value to be bits/s. Should probably change to bits/s
> everywhere instead though.

Oh, right. It would have been bits/ms otherwise.

[stefan-webrtc, 2016-10-25 08:11:51]

Tests fixed.

[stefan-webrtc, 2016-10-25 08:54:10]

Tuned

[stefan-webrtc, 2016-10-25 11:04:33]

Changed to a fixed non-overlapping sampling interval as discussed yesterday.

https://codereview.webrtc.org/2422063002/diff/100001/webrtc/modules/congestio...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.webrtc.org/2422063002/diff/100001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:71:
bitrate_estimate_std_ * bitrate_estimate_std_;
On 2016/10/24 11:20:38, terelius wrote:
> On 2016/10/24 10:55:14, stefan-webrtc (holmer) wrote:
> > On 2016/10/21 10:15:52, terelius wrote:
> > > This update could alternatively be written as
> > > 
> > > estimate = (estimate*(sample-estimate)^2 + sample*old_estimate_std^2) /
> > >            ((sample-estimate)^2 + old_estimate_std^2)
> > >            
> > 
> > Do you prefer that?
> 
> I think I'd prefer
> estimate = (sample_var * estimate + old_estimate_var * sample) / (sample_var +
> old_estimate_var)
> 
> AFAIK, that's the most common form for the bayesian update, and it is
> independent of how we estimate the variances. It also makes it clear that we
are
> taking a weighted average (i.e. that the coefficients sum to 1).
> 

Yes, the sums to 1 is a nice thing to show clearly.

[terelius, 2016-10-25 11:42:14]

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:67:
bitrate_estimate_std_ = sqrt(1.0f / denom);
Maybe we could skip the sqrt and the denom computation, and do
bitrate_estimate_var = sample_var*bitrate_estimate_var /
(sample_var+bitrate_estimate_var);

WDYT?

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:70: (sample_var +
bitrate_estimate_var);
I think this is supposed to be the old estimate variance (before you update it)

[terelius, 2016-10-25 12:51:19]

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:52: std::pair<float,
int> bitrate_sample = UpdateWindow(now_ms, bytes);
Are we using the bitrate_sample.second anywhere?

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:70: (sample_var +
bitrate_estimate_var);
On 2016/10/25 11:42:13, terelius wrote:
> I think this is supposed to be the old estimate variance (before you update
it)

Nvm, it is based on the old variance.

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:86: if (current_win_ms_
>= kRateWindowMs) {
If we receive packets at 1Mbps and then receive nothing for a time much longer
than kRateWindowMs, then the next time we get a packet it will still report a
bitrate 1Mbps?

[stefan-webrtc, 2016-10-26 11:23:17]

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:52: std::pair<float,
int> bitrate_sample = UpdateWindow(now_ms, bytes);
On 2016/10/25 12:51:19, terelius wrote:
> Are we using the bitrate_sample.second anywhere?

Yes, line 57 :)

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:67:
bitrate_estimate_std_ = sqrt(1.0f / denom);
On 2016/10/25 11:42:14, terelius wrote:
> Maybe we could skip the sqrt and the denom computation, and do
> bitrate_estimate_var = sample_var*bitrate_estimate_var /
> (sample_var+bitrate_estimate_var);
> 
> WDYT? 

Done.

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:86: if (current_win_ms_
>= kRateWindowMs) {
On 2016/10/25 12:51:19, terelius wrote:
> If we receive packets at 1Mbps and then receive nothing for a time much longer
> than kRateWindowMs, then the next time we get a packet it will still report a
> bitrate 1Mbps?

Yes, you are right. I guess the option would be to update twice in the case
where an acked packet results in both the current window and the next window
being filled?

The way it works now the second update will come one packet later.

Not sure what I prefer, but the current approach is at least simpler. WDYT?

[stefan-webrtc, 2016-10-26 11:47:13]

Rebase

[stefan-webrtc, 2016-10-26 12:51:11]

The CQ bit was checked by stefan@webrtc.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-26 12:51:22]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...

[commit-bot: I haz the power, 2016-10-26 12:53:51]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-26 12:53:52]

Dry run: Try jobs failed on following builders:
  ios64_sim_dbg on master.tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/ios64_sim_dbg/builds/11890)
  ios_arm64_dbg on master.tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/ios_arm64_dbg/builds/14223)

[terelius, 2016-10-26 13:05:02]

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
File webrtc/modules/congestion_controller/delay_based_bwe.cc (right):

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:52: std::pair<float,
int> bitrate_sample = UpdateWindow(now_ms, bytes);
On 2016/10/26 11:23:17, stefan-webrtc (holmer) wrote:
> On 2016/10/25 12:51:19, terelius wrote:
> > Are we using the bitrate_sample.second anywhere?
> 
> Yes, line 57 :)

Acknowledged.

https://codereview.webrtc.org/2422063002/diff/160001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe.cc:86: if (current_win_ms_
>= kRateWindowMs) {
On 2016/10/26 11:23:17, stefan-webrtc (holmer) wrote:
> On 2016/10/25 12:51:19, terelius wrote:
> > If we receive packets at 1Mbps and then receive nothing for a time much
longer
> > than kRateWindowMs, then the next time we get a packet it will still report
a
> > bitrate 1Mbps?
> 
> Yes, you are right. I guess the option would be to update twice in the case
> where an acked packet results in both the current window and the next window
> being filled?
> 
> The way it works now the second update will come one packet later.
> 
> Not sure what I prefer, but the current approach is at least simpler. WDYT?

Maybe current_win_ms_ %= kRateWindowMs instead of current_win_ms_ -=
kRateWindowMs?

[stefan-webrtc, 2016-10-26 13:10:59]

Comment addressed.

[stefan-webrtc, 2016-10-26 14:08:09]

Window changes.

[stefan-webrtc, 2016-10-26 14:24:57]

.

[stefan-webrtc, 2016-10-26 14:26:08]

Correct merge.

[stefan-webrtc, 2016-10-26 14:27:20]

The CQ bit was checked by stefan@webrtc.org to run a CQ dry run

[commit-bot: I haz the power, 2016-10-26 14:27:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...

[commit-bot: I haz the power, 2016-10-26 14:35:17]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-26 14:35:18]

Dry run: Try jobs failed on following builders:
  win_rel on master.tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/win_rel/builds/19370)

[terelius, 2016-10-26 14:35:46]

lgtm assuming tests and simulation results look good.

https://codereview.webrtc.org/2422063002/diff/240001/webrtc/modules/congestio...
File webrtc/modules/congestion_controller/delay_based_bwe_unittest.cc (right):

https://codereview.webrtc.org/2422063002/diff/240001/webrtc/modules/congestio...
webrtc/modules/congestion_controller/delay_based_bwe_unittest.cc:135:
CapacityDropTestHelper(1, false, 1967, 30000);
Could you check why the time has increased so much in this case?

[stefan-webrtc, 2016-10-27 12:30:33]

Normalize uncertainty to bitrate and retune.

[stefan-webrtc, 2016-10-27 12:59:01]

Tests passing again.

[stefan-webrtc, 2016-10-27 13:00:50]

Added normalization and did some retuning.

Will add an experiment around this next, but PTAL at these changes now already.

[stefan-webrtc, 2016-10-27 13:44:06]

Add experiment.

[terelius, 2016-10-27 14:01:33]

lgtm

[terelius, 2016-10-27 14:37:25]

still lgtm

[stefan-webrtc, 2016-10-27 14:38:01]

The CQ bit was checked by stefan@webrtc.org

[commit-bot: I haz the power, 2016-10-27 14:38:03]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...

[commit-bot: I haz the power, 2016-10-27 15:11:40]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-10-27 15:11:42]

Try jobs failed on following builders:
  win_x64_dbg on master.tryserver.webrtc (JOB_FAILED,
http://build.chromium.org/p/tryserver.webrtc/builders/win_x64_dbg/builds/2530)

[stefan-webrtc, 2016-10-27 15:19:38]

Description was changed from

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
==========

to

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
R=terelius@webrtc.org

Committed:
https://chromium.googlesource.com/external/webrtc/+/492ee28b731e33913acbd4bd6...
==========

[stefan-webrtc, 2016-10-27 15:19:40]

Committed patchset #19 (id:360001) manually as
492ee28b731e33913acbd4bd62dd45432df58af2 (presubmit successful).

[commit-bot: I haz the power, 2016-10-27 15:57:48]

Description was changed from

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
R=terelius@webrtc.org

Committed:
https://chromium.googlesource.com/external/webrtc/+/492ee28b731e33913acbd4bd6...
==========

to

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
R=terelius@webrtc.org

Committed: https://crrev.com/492ee28b731e33913acbd4bd62dd45432df58af2
Cr-Commit-Position: refs/heads/master@{#14802}
==========

[juberti, 2016-11-04 06:03:54]

On 2016/10/27 15:19:40, stefan-webrtc (holmer) wrote:
> Committed patchset #19 (id:360001) manually as
> 492ee28b731e33913acbd4bd62dd45432df58af2 (presubmit successful).

Have we tested this against RTC event logs where delay spikes are known to
occur?

[juberti, 2016-11-04 06:04:13]

Description was changed from

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
R=terelius@webrtc.org

Committed: https://crrev.com/492ee28b731e33913acbd4bd62dd45432df58af2
Cr-Commit-Position: refs/heads/master@{#14802}
==========

to

==========
Use bayesian estimate of acked bitrate.

This helps a lot to avoid reducing the bitrate too quickly when there's a short
period of very few packets delivered, followed by the rate resuming at the
regular rate. It specifically avoids the BWE going down to super low values as a
response delay spikes.

BUG=webrtc:6566
R=terelius@webrtc.org

Committed: https://crrev.com/492ee28b731e33913acbd4bd62dd45432df58af2
Cr-Commit-Position: refs/heads/master@{#14802}
==========

[stefan-webrtc, 2016-11-07 13:41:27]

On 2016/11/04 06:03:54, juberti wrote:
> On 2016/10/27 15:19:40, stefan-webrtc (holmer) wrote:
> > Committed patchset #19 (id:360001) manually as
> > 492ee28b731e33913acbd4bd62dd45432df58af2 (presubmit successful).
> 
> Have we tested this against RTC event logs where delay spikes are known to
> occur?

Yes. It clearly improves the behavior when the delay spikes happen, but it's
hard to fully assess the impact based on event logs since the packets recorded
in the log are fixed.