OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. | 2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license | 4 * Use of this source code is governed by a BSD-style license |
5 * that can be found in the LICENSE file in the root of the source | 5 * that can be found in the LICENSE file in the root of the source |
6 * tree. An additional intellectual property rights grant can be found | 6 * tree. An additional intellectual property rights grant can be found |
7 * in the file PATENTS. All contributing project authors may | 7 * in the file PATENTS. All contributing project authors may |
8 * be found in the AUTHORS file in the root of the source tree. | 8 * be found in the AUTHORS file in the root of the source tree. |
9 */ | 9 */ |
10 | 10 |
(...skipping 11 matching lines...) Expand all Loading... | |
22 namespace testing { | 22 namespace testing { |
23 namespace bwe { | 23 namespace bwe { |
24 | 24 |
25 // With the assumption that packet loss is lower than 97%, the max gap | 25 // With the assumption that packet loss is lower than 97%, the max gap |
26 // between elements in the set is lower than 0x8000, hence we have a | 26 // between elements in the set is lower than 0x8000, hence we have a |
27 // total order in the set. For (x,y,z) subset of the LinkedSet, | 27 // total order in the set. For (x,y,z) subset of the LinkedSet, |
28 // (x<=y and y<=z) ==> x<=z so the set can be sorted. | 28 // (x<=y and y<=z) ==> x<=z so the set can be sorted. |
29 const int kSetCapacity = 1000; | 29 const int kSetCapacity = 1000; |
30 | 30 |
31 BweReceiver::BweReceiver(int flow_id) | 31 BweReceiver::BweReceiver(int flow_id) |
32 : flow_id_(flow_id), received_packets_(kSetCapacity) { | 32 : flow_id_(flow_id), received_packets_(kSetCapacity), loss_account() { |
33 } | |
34 | |
35 void BweSender::Pause() { | |
36 running_ = false; | |
37 } | |
38 | |
39 void BweSender::Resume() { | |
40 running_ = true; | |
33 } | 41 } |
34 | 42 |
35 class NullBweSender : public BweSender { | 43 class NullBweSender : public BweSender { |
36 public: | 44 public: |
37 NullBweSender() {} | 45 NullBweSender() {} |
38 virtual ~NullBweSender() {} | 46 virtual ~NullBweSender() {} |
39 | 47 |
40 int GetFeedbackIntervalMs() const override { return 1000; } | 48 int GetFeedbackIntervalMs() const override { return 1000; } |
41 void GiveFeedback(const FeedbackPacket& feedback) override {} | 49 void GiveFeedback(const FeedbackPacket& feedback) override {} |
42 void OnPacketsSent(const Packets& packets) override {} | 50 void OnPacketsSent(const Packets& packets) override {} |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
90 return new NadaBweReceiver(flow_id); | 98 return new NadaBweReceiver(flow_id); |
91 case kTcpEstimator: | 99 case kTcpEstimator: |
92 return new TcpBweReceiver(flow_id); | 100 return new TcpBweReceiver(flow_id); |
93 case kNullEstimator: | 101 case kNullEstimator: |
94 return new BweReceiver(flow_id); | 102 return new BweReceiver(flow_id); |
95 } | 103 } |
96 assert(false); | 104 assert(false); |
97 return NULL; | 105 return NULL; |
98 } | 106 } |
99 | 107 |
100 float BweReceiver::GlobalPacketLossRatio() { | 108 // Take into account all LinkedSet content. |
109 void BweReceiver::UpdateLoss() { | |
110 loss_account.Add(LinkedSetPacketLossRatio()); | |
111 } | |
112 | |
113 void BweReceiver::ClearSet() { | |
114 received_packets_.Clear(); | |
115 } | |
116 | |
117 // Preserve 10% latest packets and update packet loss based on the oldest | |
118 // 90%, that will be removed. | |
119 void BweReceiver::RelieveSetAndUpdateLoss() { | |
120 // Compute Loss for the whole LinkedSet and updates loss_account_. | |
121 UpdateLoss(); | |
122 | |
123 size_t num_deleted_elements = (9 * received_packets_.size()) / 10; | |
stefan-webrtc
2015/07/03 09:32:11
num_elements_to_delete
magalhaesc
2015/07/03 11:55:12
Done.
| |
124 | |
125 for (PacketNodeIt it = --received_packets_.end(); num_deleted_elements > 0; | |
126 --it) { | |
127 received_packets_.Erase(it); | |
stefan-webrtc
2015/07/03 09:32:11
This is still a fairly slow way of doing the erase
magalhaesc
2015/07/03 11:55:13
Kept with the map lookup for every list element to
| |
128 --num_deleted_elements; | |
129 } | |
130 | |
131 // Compute Loss for the preserved elements | |
132 loss_account.Subtract(LinkedSetPacketLossRatio()); | |
133 } | |
134 | |
135 float BweReceiver::GlobalReceiverPacketLossRatio() { | |
136 UpdateLoss(); | |
137 return loss_account.LossRatio(); | |
138 } | |
139 | |
140 // This function considers at most kSetCapacity = 1000 packets. | |
141 LossAccount BweReceiver::LinkedSetPacketLossRatio() { | |
101 if (received_packets_.empty()) { | 142 if (received_packets_.empty()) { |
102 return 0.0f; | 143 return LossAccount(); |
103 } | 144 } |
104 // Possibly there are packets missing. | |
105 const uint16_t kMaxGap = 1.5 * kSetCapacity; | |
106 uint16_t min = received_packets_.find_min(); | |
107 uint16_t max = received_packets_.find_max(); | |
108 | 145 |
109 int gap; | 146 uint16_t oldest_seq_num = received_packets_.OldestSeqNumber(); |
110 if (max - min < kMaxGap) { | 147 uint16_t newest_seq_num = received_packets_.NewestSeqNumber(); |
111 gap = max - min + 1; | 148 |
112 } else { // There was an overflow. | 149 size_t set_total_packets = |
113 max = received_packets_.upper_bound(kMaxGap); | 150 static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1); |
114 min = received_packets_.lower_bound(0xFFFF - kMaxGap); | 151 |
115 gap = max + (0xFFFF - min) + 2; | 152 size_t set_received_packets = received_packets_.size(); |
116 } | 153 size_t set_lost_packets = set_total_packets - set_received_packets; |
117 return static_cast<float>(received_packets_.size()) / gap; | 154 |
155 return LossAccount(set_total_packets, set_lost_packets); | |
156 } | |
157 | |
158 uint32_t BweReceiver::RecentKbps() { | |
159 return (rate_counter_.bits_per_second() + 500) / 1000; | |
118 } | 160 } |
119 | 161 |
120 // Go through a fixed time window of most recent packets received and | 162 // Go through a fixed time window of most recent packets received and |
121 // counts packets missing to obtain the packet loss ratio. If an unordered | 163 // counts packets missing to obtain the packet loss ratio. If an unordered |
122 // packet falls out of the timewindow it will be counted as missing. | 164 // packet falls out of the timewindow it will be counted as missing. |
123 // E.g.: for a timewindow covering 5 packets of the following arrival sequence | 165 // E.g.: for a timewindow covering 5 packets of the following arrival sequence |
124 // {10 7 9 5 6} 8 3 2 4 1, the output will be 1/6 (#8 is considered as missing). | 166 // {10 7 9 5 6} 8 3 2 4 1, the output will be 1/6 (#8 is considered as missing). |
125 float BweReceiver::RecentPacketLossRatio() { | 167 float BweReceiver::RecentPacketLossRatio() { |
126 if (received_packets_.empty()) { | 168 if (received_packets_.empty()) { |
127 return 0.0f; | 169 return 0.0f; |
128 } | 170 } |
129 int number_packets_received = 0; | 171 int number_packets_received = 0; |
130 | 172 |
131 PacketNodeIt node_it = received_packets_.begin(); // Latest. | 173 PacketNodeIt node_it = received_packets_.begin(); // Latest. |
132 | 174 |
133 // Lowest timestamp limit, oldest one that should be checked. | 175 // Lowest timestamp limit, oldest one that should be checked. |
134 int64_t time_limit_ms = (*node_it)->arrival_time_ms - kPacketLossTimeWindowMs; | 176 int64_t time_limit_ms = (*node_it)->arrival_time_ms - kPacketLossTimeWindowMs; |
135 // Oldest and newest values found within the given time window. | 177 // Oldest and newest values found within the given time window. |
136 uint16_t oldest_seq_nb = (*node_it)->sequence_number; | 178 uint16_t oldest_seq_num = (*node_it)->sequence_number; |
137 uint16_t newest_seq_nb = oldest_seq_nb; | 179 uint16_t newest_seq_num = oldest_seq_num; |
138 | 180 |
139 while (node_it != received_packets_.end()) { | 181 while (node_it != received_packets_.end()) { |
140 if ((*node_it)->arrival_time_ms < time_limit_ms) { | 182 if ((*node_it)->arrival_time_ms < time_limit_ms) { |
141 break; | 183 break; |
142 } | 184 } |
143 uint16_t seq_nb = (*node_it)->sequence_number; | 185 uint16_t seq_nb = (*node_it)->sequence_number; |
144 if (IsNewerSequenceNumber(seq_nb, newest_seq_nb)) { | 186 if (IsNewerSequenceNumber(seq_nb, newest_seq_num)) { |
145 newest_seq_nb = seq_nb; | 187 newest_seq_num = seq_nb; |
146 } | 188 } |
147 if (IsNewerSequenceNumber(oldest_seq_nb, seq_nb)) { | 189 if (IsNewerSequenceNumber(oldest_seq_num, seq_nb)) { |
148 oldest_seq_nb = seq_nb; | 190 oldest_seq_num = seq_nb; |
149 } | 191 } |
150 ++node_it; | 192 ++node_it; |
151 ++number_packets_received; | 193 ++number_packets_received; |
152 } | 194 } |
153 // Interval width between oldest and newest sequence number. | 195 // Interval width between oldest and newest sequence number. |
154 // There was an overflow if newest_seq_nb < oldest_seq_nb. | 196 // There was an overflow if newest_seq_num < oldest_seq_num. |
155 int gap = static_cast<uint16_t>(newest_seq_nb - oldest_seq_nb + 1); | 197 int gap = static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1); |
156 | 198 |
157 return static_cast<float>(gap - number_packets_received) / gap; | 199 return static_cast<float>(gap - number_packets_received) / gap; |
158 } | 200 } |
159 | 201 |
160 void LinkedSet::Insert(uint16_t sequence_number, | 202 void LinkedSet::Insert(uint16_t sequence_number, |
161 int64_t send_time_ms, | 203 int64_t send_time_ms, |
162 int64_t arrival_time_ms, | 204 int64_t arrival_time_ms, |
163 size_t payload_size) { | 205 size_t payload_size) { |
164 std::map<uint16_t, PacketNodeIt>::iterator it = map_.find(sequence_number); | 206 std::map<uint16_t, PacketNodeIt>::iterator it = map_.find(sequence_number); |
165 if (it != map_.end()) { | 207 if (it != map_.end()) { |
166 PacketNodeIt node_it = it->second; | 208 PacketNodeIt node_it = it->second; |
167 PacketIdentifierNode* node = *node_it; | 209 PacketIdentifierNode* node = *node_it; |
168 node->arrival_time_ms = arrival_time_ms; | 210 node->arrival_time_ms = arrival_time_ms; |
169 if (node_it != list_.begin()) { | 211 if (node_it != list_.begin()) { |
170 list_.erase(node_it); | 212 list_.erase(node_it); |
171 list_.push_front(node); | 213 list_.push_front(node); |
172 map_[sequence_number] = list_.begin(); | 214 map_[sequence_number] = list_.begin(); |
173 } | 215 } |
174 } else { | 216 } else { |
175 if (size() == capacity_) { | 217 if (size() == capacity_) { |
176 RemoveTail(); | 218 RemoveTail(); |
177 } | 219 } |
178 UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms, | 220 UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms, |
179 arrival_time_ms, payload_size)); | 221 arrival_time_ms, payload_size)); |
180 } | 222 } |
181 } | 223 } |
224 | |
225 void LinkedSet::Insert(PacketIdentifierNode packet_identifier) { | |
226 Insert(packet_identifier.sequence_number, packet_identifier.send_time_ms, | |
227 packet_identifier.arrival_time_ms, packet_identifier.payload_size); | |
228 } | |
229 | |
182 void LinkedSet::RemoveTail() { | 230 void LinkedSet::RemoveTail() { |
183 map_.erase(list_.back()->sequence_number); | 231 Erase(--end()); |
184 list_.pop_back(); | |
185 } | 232 } |
186 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) { | 233 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) { |
187 list_.push_front(new_head); | 234 list_.push_front(new_head); |
188 map_[new_head->sequence_number] = list_.begin(); | 235 map_[new_head->sequence_number] = list_.begin(); |
189 } | 236 } |
190 | 237 |
238 uint16_t LinkedSet::OldestSeqNumber() { | |
239 if (IsNewerSequenceNumber(Max(), Min()) || Max() == Min()) { | |
240 return Min(); // An empty set will return Max = Min = 0. | |
241 } else { // There was an overflow. | |
242 return map_.lower_bound(0x8000)->first; | |
243 } | |
244 } | |
245 | |
246 uint16_t LinkedSet::NewestSeqNumber() { | |
247 if (IsNewerSequenceNumber(Max(), Min()) || Max() == Min()) { | |
248 return Max(); // An empty set will return Max = Min = 0. | |
249 } else { // There was an overflow. | |
250 return (--map_.lower_bound(0x8000))->first; | |
251 } | |
252 } | |
253 | |
254 void LinkedSet::Erase(PacketNodeIt node_it) { | |
255 map_.erase((*node_it)->sequence_number); | |
256 list_.erase(node_it); | |
257 } | |
258 | |
259 void LossAccount::Add(LossAccount rhs) { | |
260 num_total += rhs.num_total; | |
261 num_lost += rhs.num_lost; | |
262 } | |
263 void LossAccount::Subtract(LossAccount rhs) { | |
264 num_total -= rhs.num_total; | |
265 num_lost -= rhs.num_lost; | |
266 } | |
267 | |
268 float LossAccount::LossRatio() { | |
269 return static_cast<float>(num_lost) / num_total; | |
270 } | |
271 | |
191 } // namespace bwe | 272 } // namespace bwe |
192 } // namespace testing | 273 } // namespace testing |
193 } // namespace webrtc | 274 } // namespace webrtc |
OLD | NEW |