1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "net/quic/congestion_control/channel_estimator.h"
// To get information about bandwidth, our send rate for a pair of packets must
// be much faster (ideally back to back) than the receive rate. In that
// scenario, the arriving packet pair will tend to arrive at the max bandwidth
// of the channel. Said another way, when our inter-departure time is a small
// fraction of the inter-arrival time for the same pair of packets, then we can
// get an estimate of bandwidth from that interarrival time. The following
// constant is the threshold ratio for deriving bandwidth information.
static const int kInterarrivalRatioThresholdForBandwidthEstimation = 5;
static const size_t kMinNumberOfSamples = 10;
static const size_t kMaxNumberOfSamples = 100;
namespace net {
ChannelEstimator::ChannelEstimator()
: last_sequence_number_(0),
last_send_time_(QuicTime::Zero()),
last_receive_time_(QuicTime::Zero()),
sorted_bitrate_estimates_(kMaxNumberOfSamples) {
}
ChannelEstimator::~ChannelEstimator() {
}
void ChannelEstimator::OnAcknowledgedPacket(
QuicPacketSequenceNumber sequence_number,
QuicByteCount packet_size,
QuicTime send_time,
QuicTime receive_time) {
if (last_sequence_number_ > sequence_number) {
// Old packet. The sequence_number use the full 64 bits even though it's
// less on the wire.
return;
}
if (last_sequence_number_ != sequence_number - 1) {
DLOG(INFO) << "Skip channel estimator due to lost packet(s)";
} else if (last_send_time_.IsInitialized()) {
QuicTime::Delta sent_delta = send_time.Subtract(last_send_time_);
QuicTime::Delta received_delta = receive_time.Subtract(last_receive_time_);
if (received_delta.ToMicroseconds() >
kInterarrivalRatioThresholdForBandwidthEstimation *
sent_delta.ToMicroseconds()) {
UpdateFilter(received_delta, packet_size, sequence_number);
}
}
last_sequence_number_ = sequence_number;
last_send_time_ = send_time;
last_receive_time_ = receive_time;
}
ChannelEstimateState ChannelEstimator::GetChannelEstimate(
QuicBandwidth* estimate) const {
if (sorted_bitrate_estimates_.Size() < kMinNumberOfSamples) {
// Not enough data to make an estimate.
return kChannelEstimateUnknown;
}
// Our data is stored in a sorted map, we need to iterate through our map to
// find the estimated bitrates at our targeted percentiles.
// Calculate 25th percentile.
size_t beginning_window = sorted_bitrate_estimates_.Size() / 4;
// Calculate 50th percentile.
size_t median = sorted_bitrate_estimates_.Size() / 2;
// Calculate 75th percentile.
size_t end_window = sorted_bitrate_estimates_.Size() - beginning_window;
QuicBandwidth bitrate_25th_percentile = QuicBandwidth::Zero();
QuicBandwidth median_bitrate = QuicBandwidth::Zero();
QuicBandwidth bitrate_75th_percentile = QuicBandwidth::Zero();
QuicMaxSizedMap<QuicBandwidth, QuicPacketSequenceNumber>::ConstIterator it =
sorted_bitrate_estimates_.Begin();
for (size_t i = 0; i <= end_window; ++i, ++it) {
DCHECK(it != sorted_bitrate_estimates_.End());
if (i == beginning_window) {
bitrate_25th_percentile = it->first;
}
if (i == median) {
median_bitrate = it->first;
}
if (i == end_window) {
bitrate_75th_percentile = it->first;
}
}
*estimate = median_bitrate;
DLOG(INFO) << "Channel estimate is:"
<< median_bitrate.ToKBitsPerSecond() << " Kbit/s";
// If the bitrates in our 25th to 75th percentile window varies more than
// 25% of the median bitrate we consider the estimate to be uncertain.
if (bitrate_75th_percentile.Subtract(bitrate_25th_percentile) >
median_bitrate.Scale(0.25f)) {
return kChannelEstimateUncertain;
}
return kChannelEstimateGood;
}
void ChannelEstimator::UpdateFilter(QuicTime::Delta received_delta,
QuicByteCount size_delta,
QuicPacketSequenceNumber sequence_number) {
QuicBandwidth estimate =
QuicBandwidth::FromBytesAndTimeDelta(size_delta, received_delta);
sorted_bitrate_estimates_.Insert(estimate, sequence_number);
}
} // namespace net
|
