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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
// 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.
// This class is a helper class to the inter arrival congestion control. It
// provide a signal to the inter arrival congestion control of the estimated
// state of our transport channel. The estimate is based on the inter arrival
// time of the received packets relative to the time those packets were sent;
// we can estimate the build up of buffers on the network before packets are
// lost.
//
// Note: this class is not thread-safe.
#ifndef NET_QUIC_CONGESTION_CONTROL_INTER_ARRIVAL_OVERUSE_DETECTOR_H_
#define NET_QUIC_CONGESTION_CONTROL_INTER_ARRIVAL_OVERUSE_DETECTOR_H_
#include "base/basictypes.h"
#include "net/base/net_export.h"
#include "net/quic/quic_protocol.h"
#include "net/quic/quic_time.h"
namespace net {
enum NET_EXPORT_PRIVATE RateControlRegion {
kRateControlRegionUnknown = 0,
kRateControlRegionUnderMax = 1,
kRateControlRegionNearMax = 2
};
// Note: Order is important.
enum NET_EXPORT_PRIVATE BandwidthUsage {
kBandwidthSteady = 0,
kBandwidthUnderUsing = 1,
kBandwidthDraining = 2,
kBandwidthOverUsing = 3,
};
// Normal state transition diagram
//
// kBandwidthUnderUsing
// |
// |
// kBandwidthSteady
// | ^
// | |
// kBandwidthOverUsing |
// | |
// | |
// kBandwidthDraining
//
// The above transitions is in normal operation, with extreme values we don't
// enforce the state transitions, hence you could in extreme scenarios go
// between any states.
//
// kBandwidthSteady When the packets arrive in the same pace as we sent
// them. In this state we can increase our send pace.
//
// kBandwidthOverUsing When the packets arrive slower than the pace we sent
// them. In this state we should decrease our send pace.
// When we enter into this state we will also get an
// estimate on how much delay we have built up. The
// reduction in send pace should be chosen to drain the
// built up delay within reasonable time.
//
// kBandwidthUnderUsing When the packets arrive faster than the pace we sent
// them. In this state another stream disappeared from
// a shared link leaving us more available bandwidth.
// In this state we should hold our pace to make sure we
// fully drain the buffers before we start increasing
// our send rate. We do this to avoid operating with
// semi-full buffers.
//
// kBandwidthDraining We can only be in this state after we have been in a
// overuse state. In this state we should hold our pace
// to make sure we fully drain the buffers before we
// start increasing our send rate. We do this to avoid
// operating with semi-full buffers.
class NET_EXPORT_PRIVATE InterArrivalOveruseDetector {
public:
InterArrivalOveruseDetector();
// Update the statistics with the received delta times, call for every
// received delta time. This function assumes that there is no re-orderings.
// If multiple packets are sent at the same time (identical send_time)
// last_of_send_time should be set to false for all but the last calls to
// this function. If there is only one packet sent at a given time
// last_of_send_time must be true.
// received_delta is the time difference between receiving this packet and the
// previously received packet.
void OnAcknowledgedPacket(QuicPacketSequenceNumber sequence_number,
QuicTime send_time,
bool last_of_send_time,
QuicTime receive_time);
// Get the current estimated state and update the estimated congestion delay.
// |estimated_congestion_delay| will be updated with the estimated built up
// buffer delay; it must not be NULL as it will be updated with the estimate.
// Note 1: estimated_buffer_delay will only be valid when kBandwidthOverUsing
// is returned.
// Note 2: it's assumed that the pacer lower its send pace to drain the
// built up buffer within reasonable time. The pacer should use the
// estimated_buffer_delay as a guidance on how much to back off.
// Note 3: The absolute value of estimated_congestion_delay is less reliable
// than the state itself. It is also biased to low since we can't know
// how full the buffers are when the flow starts.
BandwidthUsage GetState(QuicTime::Delta* estimated_congestion_delay);
private:
struct PacketGroup {
PacketGroup()
: send_time(QuicTime::Zero()),
last_receive_time(QuicTime::Zero()) {
}
QuicTime send_time;
QuicTime last_receive_time;
};
// Update the statistics with the absolute receive time relative to the
// absolute send time.
void UpdateSendReceiveTimeOffset(QuicTime::Delta offset);
// Update the filter with this new data point.
void UpdateFilter(QuicTime::Delta received_delta,
QuicTime::Delta sent_delta);
// Update the estimate with this residual.
void UpdateDeltaEstimate(QuicTime::Delta residual);
// Estimate the state based on the slope of the changes.
void DetectSlope(int64 sigma_delta);
// Estimate the state based on the accumulated drift of the changes.
void DetectDrift(int64 sigma_delta);
// Current grouping of packets that were sent at the same time.
PacketGroup current_packet_group_;
// Grouping of packets that were sent at the same time, just before the
// current_packet_group_ above.
PacketGroup previous_packet_group_;
// Sequence number of the last acknowledged packet.
QuicPacketSequenceNumber last_sequence_number_;
// Number of received delta times with unique send time.
int num_of_deltas_;
// Estimated accumulation of received delta times.
// Note: Can be negative and can drift over time which is why we bias it
// towards 0 and reset it given some triggers.
QuicTime::Delta accumulated_deltas_;
// Current running mean of our received delta times.
int delta_mean_;
// Current running variance of our received delta times.
int64 delta_variance_;
// Number of overuse signals currently triggered in this state.
// Note: negative represent underuse.
int delta_overuse_counter_;
// State estimated by the delta times.
BandwidthUsage delta_estimate_;
// Number of overuse signals currently triggered in this state.
// Note: negative represent underuse.
int slope_overuse_counter_;
// State estimated by the slope of the delta times.
BandwidthUsage slope_estimate_;
// Lowest offset between send and receive time ever received in this session.
QuicTime::Delta send_receive_offset_;
// Last received time difference between our normalized send and receive time.
QuicTime::Delta estimated_congestion_delay_;
DISALLOW_COPY_AND_ASSIGN(InterArrivalOveruseDetector);
};
} // namespace net
#endif // NET_QUIC_CONGESTION_CONTROL_INTER_ARRIVAL_OVERUSE_DETECTOR_H_
|
