Cast: Updated congestion control

Cast: Updated congestion control

This tries to update the bandwidth used to what is available.
The algorithm is essentially that we estimate how much bandwidth we've been sending recently.
Then we check how full our buffers are. We set a target for having our buffers be 90% empty.
If the buffer is more than 90% empty, we use more bandwidth than the resently sent, if
the buffer is less than 90% empty, we use less.

This change should be relatively safe since we normally set our min and max bandwidth to a
very limited range, and this change respects those limits.

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=276611

[Alpha Left Google, 2014-06-10 22:20:39]

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.cc (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:14: // This means that we
*try* to keep our buffer 90% empty.
Where is this "buffer"? Please elaborate. I think a short paragraph at the top
of this file to explain the goal of this algorithm (a some details) would be
very helpful.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:73: return
acked_bits_in_history_ / transmit_time;
What happens if transmit_time is very close to zero? I think a cap of say
20mbit/s would prevent that.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:79: DCHECK_LT(offset, 100);
Should be kHistorySize instead of 100.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:99: DCHECK_LT(offset,
static_cast<int32>(frame_stats_.size()));
This should be an if statement to prevent out of bounds access.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:141: return now + (now -
ret) / 2;
I don't think this is doing what the comments suggests. I suppose it should be:

return now + transmission_time / 2 + rtt_;

where

transmission_time = base::TimeDelta::FromSecondsD(frame_stats->frame_size /
bitrate);

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:152: FrameStats* frame_stats
= GetFrameStats(frame_id);
We should be able to get this from the pacer, why do estimation if we can get
the actual time? I guess I don't understand the definition of sending time.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:155: if
(frame_stats->sent_time.is_null()) {
How is this possible?

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:159: return std::max(ret,
frame_stats->sent_time);
This assumes there is a black box that sends the next after the previous frame
is acked. When the RTT has a high average (when AP is congested) I think the
sending time will be overestimated by quite a bit.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.h (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:27: void
UpdateRTT(base::TimeDelta rtt);
nit: This should be Rtt to be consistent with the rest of the code.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:28: void
SendFrameToTransport(uint32 frame_id,
Please document this method. When should this be called?

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:31: void AckFrame(uint32
frame_id, base::TimeTicks when);
Please document. A one line is sufficient.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:48: // Calculate how much
"dead air" there is between two frames.
Please be more descriptive of what "dead air" means. Does it mean the elapsed
time between sending two frames?

[Alpha Left Google, 2014-06-10 22:37:07]

By the way Patrik had make some comments about delaying sensing approach similar
to this one implemented.

I do agree. This approach maybe too pessimistic and the encoding bitrate would
hang in a low value if there is congestion going on in the AP.

The goal of this algorithm is to have very small number of unacked frames. It
hopes to maximize the chance of packets arriving in time. There may be times
when the latency is generally high but the majority of packets arrive in time. I
think actually measuring this percentage could be an improvement to make this
algorithm more forgiving.

[hubbe, 2014-06-11 00:04:15]

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.cc (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:14: // This means that we
*try* to keep our buffer 90% empty.
On 2014/06/10 22:20:39, Alpha wrote:
> Where is this "buffer"? Please elaborate. I think a short paragraph at the top
> of this file to explain the goal of this algorithm (a some details) would be
> very helpful.

Done.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:73: return
acked_bits_in_history_ / transmit_time;
On 2014/06/10 22:20:39, Alpha wrote:
> What happens if transmit_time is very close to zero? I think a cap of say
> 20mbit/s would prevent that.

It's pretty unlikely, except possibly for the first frame.
I could do something like min(transmit_time, 1ms) I suppose, since that should
never happen anyways...

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:79: DCHECK_LT(offset, 100);
On 2014/06/10 22:20:39, Alpha wrote:
> Should be kHistorySize instead of 100.

Done.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:99: DCHECK_LT(offset,
static_cast<int32>(frame_stats_.size()));
On 2014/06/10 22:20:38, Alpha wrote:
> This should be an if statement to prevent out of bounds access.

I don't think so. If an out-of-bounds indexing happens, then the code is
seriously broken. It should either be a CHECK or a DCHECK.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:141: return now + (now -
ret) / 2;
Changed the comment instead.

On 2014/06/10 22:20:39, Alpha wrote:
> I don't think this is doing what the comments suggests. I suppose it should
be:
> 
> return now + transmission_time / 2 + rtt_;
> 
> where
> 
> transmission_time = base::TimeDelta::FromSecondsD(frame_stats->frame_size /
> bitrate);

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:152: FrameStats* frame_stats
= GetFrameStats(frame_id);
On 2014/06/10 22:20:39, Alpha wrote:
> We should be able to get this from the pacer, why do estimation if we can get
> the actual time? I guess I don't understand the definition of sending time.

Sending time is when we start sending data for a frame. We sort of assume that
frames are sent in sequence, which isn't really true, but seems to work anyways.

Even if we can ask the pacer, we'll still need this function as we need to
estimate the sending time for frames that haven't been sent yet.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:155: if
(frame_stats->sent_time.is_null()) {
On 2014/06/10 22:20:38, Alpha wrote:
> How is this possible?

It hasn't been sent yet.
Note: "sent time" is when it was sent to the transport
"sending time" is when we actually started transmitting it.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:159: return std::max(ret,
frame_stats->sent_time);
On 2014/06/10 22:20:39, Alpha wrote:
> This assumes there is a black box that sends the next after the previous frame
> is acked. When the RTT has a high average (when AP is congested) I think the
> sending time will be overestimated by quite a bit.

In simulation, it works even with high latencies.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.h (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:27: void
UpdateRTT(base::TimeDelta rtt);
On 2014/06/10 22:20:39, Alpha wrote:
> nit: This should be Rtt to be consistent with the rest of the code.

Done.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:28: void
SendFrameToTransport(uint32 frame_id,
On 2014/06/10 22:20:39, Alpha wrote:
> Please document this method. When should this be called?

Done.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:31: void AckFrame(uint32
frame_id, base::TimeTicks when);
On 2014/06/10 22:20:39, Alpha wrote:
> Please document. A one line is sufficient.

Done.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:48: // Calculate how much
"dead air" there is between two frames.
On 2014/06/10 22:20:39, Alpha wrote:
> Please be more descriptive of what "dead air" means. Does it mean the elapsed
> time between sending two frames?

Done.

[hubbe, 2014-06-11 00:14:16]

On 2014/06/10 22:37:07, Alpha wrote:
> By the way Patrik had make some comments about delaying sensing approach
similar
> to this one implemented.
> 
> I do agree. This approach maybe too pessimistic and the encoding bitrate would
> hang in a low value if there is congestion going on in the AP.
> 
> The goal of this algorithm is to have very small number of unacked frames. It
> hopes to maximize the chance of packets arriving in time. There may be times
> when the latency is generally high but the majority of packets arrive in time.
I
> think actually measuring this percentage could be an improvement to make this
> algorithm more forgiving.

The algorithm seems to handle high latency relatively well, so I'm not too
concerned
about that. I am concerned that other protocols (TCP!) may aggressively take any
bandwidth
we don't use, causing this algorithm to back off too much. However, if we don't
back off
we sabotage ourselves, causing frames to arrive late.

Mark suggested that some level of FEC might help. This would allow us to eat up
the spare
bandwidth without causing more late frames.

Right now this is theoretical though. We need to actually try it and see what
happens.
Also, ANY algorithm would be better than the one we have today, so...

[Alpha Left Google, 2014-06-11 01:16:28]

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.cc (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:73: return
acked_bits_in_history_ / transmit_time;
Okay.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:99: DCHECK_LT(offset,
static_cast<int32>(frame_stats_.size()));
On 2014/06/11 00:04:15, hubbe wrote:
> On 2014/06/10 22:20:38, Alpha wrote:
> > This should be an if statement to prevent out of bounds access.
> 
> I don't think so. If an out-of-bounds indexing happens, then the code is
> seriously broken. It should either be a CHECK or a DCHECK.

If |offset| is trivial then I think CHECK would be better. But in this case
offset is not very obvious: it comes from a caller and there is arithmetic
operation (add) on it. The result of GetFrameStats always run through a DCHECK
so if later this breaks in the future the error will not go unnoticed. And there
is no risk of OOB access.

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.h (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.h:27: void
UpdateRTT(base::TimeDelta rtt);
On 2014/06/10 22:20:39, Alpha wrote:
> nit: This should be Rtt to be consistent with the rest of the code.

I mean UpdateRtt instead of UpdateRTT. The variable rtt was correct.

[hubbe, 2014-06-11 07:11:48]

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
File media/cast/congestion_control/congestion_control.cc (right):

https://codereview.chromium.org/326783002/diff/20001/media/cast/congestion_co...
media/cast/congestion_control/congestion_control.cc:99: DCHECK_LT(offset,
static_cast<int32>(frame_stats_.size()));
On 2014/06/11 01:16:28, Alpha wrote:
> On 2014/06/11 00:04:15, hubbe wrote:
> > On 2014/06/10 22:20:38, Alpha wrote:
> > > This should be an if statement to prevent out of bounds access.
> > 
> > I don't think so. If an out-of-bounds indexing happens, then the code is
> > seriously broken. It should either be a CHECK or a DCHECK.
> 
> If |offset| is trivial then I think CHECK would be better. But in this case
> offset is not very obvious: it comes from a caller and there is arithmetic
> operation (add) on it. The result of GetFrameStats always run through a DCHECK
> so if later this breaks in the future the error will not go unnoticed. And
there
> is no risk of OOB access.

Done.

[Alpha Left Google, 2014-06-11 17:32:19]

Note: CongestionControlTest fails on win_chromium_rel.

[hubbe, 2014-06-11 22:35:46]

On 2014/06/11 17:32:19, Alpha wrote:
> Note: CongestionControlTest fails on win_chromium_rel.

Tests now pass again. (Mixed up min/max)

[Alpha Left Google, 2014-06-11 22:55:14]

Okay. LGTM.

[hubbe, 2014-06-11 23:01:30]

The CQ bit was checked by hubbe@chromium.org

[commit-bot: I haz the power, 2014-06-11 23:03:24]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/hubbe@chromium.org/326783002/70001

[commit-bot: I haz the power, 2014-06-12 00:16:50]

FYI, CQ is re-trying this CL (attempt #1).
The failing builders are:
  android_dbg_triggered_tests on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/android_dbg_triggered...)
  ios_dbg_simulator on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/ios_dbg_simulator/bui...)
  ios_rel_device on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/ios_rel_device/builds...)
  ios_rel_device_ninja on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/ios_rel_device_ninja/...)
  mac_chromium_compile_dbg on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/mac_chromium_compile_...)
  mac_chromium_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/mac_chromium_rel/buil...)
  win_chromium_compile_dbg on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/win_chromium_compile_...)
  win_chromium_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/win_chromium_rel/buil...)
  win_chromium_x64_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/win_chromium_x64_rel/...)
  mac_gpu on tryserver.chromium.gpu
(http://build.chromium.org/p/tryserver.chromium.gpu/builders/mac_gpu/builds/15759)
  win_gpu on tryserver.chromium.gpu
(http://build.chromium.org/p/tryserver.chromium.gpu/builders/win_gpu/builds/18891)

[commit-bot: I haz the power, 2014-06-12 00:20:01]

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

[commit-bot: I haz the power, 2014-06-12 00:20:03]

Try jobs failed on following builders:
  win_chromium_rel on tryserver.chromium
(http://build.chromium.org/p/tryserver.chromium/builders/win_chromium_rel/buil...)

[hubbe, 2014-06-12 04:56:42]

The CQ bit was checked by hubbe@chromium.org

[commit-bot: I haz the power, 2014-06-12 04:58:31]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/hubbe@chromium.org/326783002/70001

[commit-bot: I haz the power, 2014-06-12 09:55:45]

Change committed as 276611