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), |
| 33 received_packets_(kSetCapacity), |
| 34 rate_counter_(), |
| 35 loss_account_() { |
| 36 } |
| 37 |
| 38 BweReceiver::BweReceiver(int flow_id, int64_t window_size_ms) |
| 39 : flow_id_(flow_id), |
| 40 received_packets_(kSetCapacity), |
| 41 rate_counter_(window_size_ms), |
| 42 loss_account_() { |
| 43 } |
| 44 |
| 45 void BweReceiver::ReceivePacket(int64_t arrival_time_ms, |
| 46 const MediaPacket& media_packet) { |
| 47 if (received_packets_.size() == kSetCapacity) { |
| 48 RelieveSetAndUpdateLoss(); |
| 49 } |
| 50 |
| 51 received_packets_.Insert(media_packet.sequence_number(), |
| 52 media_packet.send_time_ms(), arrival_time_ms, |
| 53 media_packet.payload_size()); |
| 54 |
| 55 rate_counter_.UpdateRates(media_packet.send_time_ms() * 1000, |
| 56 static_cast<uint32_t>(media_packet.payload_size())); |
33 } | 57 } |
34 | 58 |
35 class NullBweSender : public BweSender { | 59 class NullBweSender : public BweSender { |
36 public: | 60 public: |
37 NullBweSender() {} | 61 NullBweSender() {} |
38 virtual ~NullBweSender() {} | 62 virtual ~NullBweSender() {} |
39 | 63 |
40 int GetFeedbackIntervalMs() const override { return 1000; } | 64 int GetFeedbackIntervalMs() const override { return 1000; } |
41 void GiveFeedback(const FeedbackPacket& feedback) override {} | 65 void GiveFeedback(const FeedbackPacket& feedback) override {} |
42 void OnPacketsSent(const Packets& packets) override {} | 66 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); | 114 return new NadaBweReceiver(flow_id); |
91 case kTcpEstimator: | 115 case kTcpEstimator: |
92 return new TcpBweReceiver(flow_id); | 116 return new TcpBweReceiver(flow_id); |
93 case kNullEstimator: | 117 case kNullEstimator: |
94 return new BweReceiver(flow_id); | 118 return new BweReceiver(flow_id); |
95 } | 119 } |
96 assert(false); | 120 assert(false); |
97 return NULL; | 121 return NULL; |
98 } | 122 } |
99 | 123 |
100 float BweReceiver::GlobalPacketLossRatio() { | 124 // Take into account all LinkedSet content. |
| 125 void BweReceiver::UpdateLoss() { |
| 126 loss_account_.Add(LinkedSetPacketLossRatio()); |
| 127 } |
| 128 |
| 129 // Preserve 10% latest packets and update packet loss based on the oldest |
| 130 // 90%, that will be removed. |
| 131 void BweReceiver::RelieveSetAndUpdateLoss() { |
| 132 // Compute Loss for the whole LinkedSet and updates loss_account_. |
| 133 UpdateLoss(); |
| 134 |
| 135 size_t num_preserved_elements = received_packets_.size() / 10; |
| 136 PacketNodeIt it = received_packets_.begin(); |
| 137 std::advance(it, num_preserved_elements); |
| 138 |
| 139 while (it != received_packets_.end()) { |
| 140 received_packets_.Erase(it++); |
| 141 } |
| 142 |
| 143 // Compute Loss for the preserved elements |
| 144 loss_account_.Subtract(LinkedSetPacketLossRatio()); |
| 145 } |
| 146 |
| 147 float BweReceiver::GlobalReceiverPacketLossRatio() { |
| 148 UpdateLoss(); |
| 149 return loss_account_.LossRatio(); |
| 150 } |
| 151 |
| 152 // This function considers at most kSetCapacity = 1000 packets. |
| 153 LossAccount BweReceiver::LinkedSetPacketLossRatio() { |
101 if (received_packets_.empty()) { | 154 if (received_packets_.empty()) { |
102 return 0.0f; | 155 return LossAccount(); |
103 } | 156 } |
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 | 157 |
109 int gap; | 158 uint16_t oldest_seq_num = received_packets_.OldestSeqNumber(); |
110 if (max - min < kMaxGap) { | 159 uint16_t newest_seq_num = received_packets_.NewestSeqNumber(); |
111 gap = max - min + 1; | 160 |
112 } else { // There was an overflow. | 161 size_t set_total_packets = |
113 max = received_packets_.upper_bound(kMaxGap); | 162 static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1); |
114 min = received_packets_.lower_bound(0xFFFF - kMaxGap); | 163 |
115 gap = max + (0xFFFF - min) + 2; | 164 size_t set_received_packets = received_packets_.size(); |
116 } | 165 size_t set_lost_packets = set_total_packets - set_received_packets; |
117 return static_cast<float>(received_packets_.size()) / gap; | 166 |
| 167 return LossAccount(set_total_packets, set_lost_packets); |
| 168 } |
| 169 |
| 170 uint32_t BweReceiver::RecentKbps() const { |
| 171 return (rate_counter_.bits_per_second() + 500) / 1000; |
118 } | 172 } |
119 | 173 |
120 // Go through a fixed time window of most recent packets received and | 174 // 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 | 175 // 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. | 176 // 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 | 177 // 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). | 178 // {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() { | 179 float BweReceiver::RecentPacketLossRatio() { |
126 if (received_packets_.empty()) { | 180 if (received_packets_.empty()) { |
127 return 0.0f; | 181 return 0.0f; |
128 } | 182 } |
129 int number_packets_received = 0; | 183 int number_packets_received = 0; |
130 | 184 |
131 PacketNodeIt node_it = received_packets_.begin(); // Latest. | 185 PacketNodeIt node_it = received_packets_.begin(); // Latest. |
132 | 186 |
133 // Lowest timestamp limit, oldest one that should be checked. | 187 // Lowest timestamp limit, oldest one that should be checked. |
134 int64_t time_limit_ms = (*node_it)->arrival_time_ms - kPacketLossTimeWindowMs; | 188 int64_t time_limit_ms = (*node_it)->arrival_time_ms - kPacketLossTimeWindowMs; |
135 // Oldest and newest values found within the given time window. | 189 // Oldest and newest values found within the given time window. |
136 uint16_t oldest_seq_nb = (*node_it)->sequence_number; | 190 uint16_t oldest_seq_num = (*node_it)->sequence_number; |
137 uint16_t newest_seq_nb = oldest_seq_nb; | 191 uint16_t newest_seq_num = oldest_seq_num; |
138 | 192 |
139 while (node_it != received_packets_.end()) { | 193 while (node_it != received_packets_.end()) { |
140 if ((*node_it)->arrival_time_ms < time_limit_ms) { | 194 if ((*node_it)->arrival_time_ms < time_limit_ms) { |
141 break; | 195 break; |
142 } | 196 } |
143 uint16_t seq_nb = (*node_it)->sequence_number; | 197 uint16_t seq_num = (*node_it)->sequence_number; |
144 if (IsNewerSequenceNumber(seq_nb, newest_seq_nb)) { | 198 if (IsNewerSequenceNumber(seq_num, newest_seq_num)) { |
145 newest_seq_nb = seq_nb; | 199 newest_seq_num = seq_num; |
146 } | 200 } |
147 if (IsNewerSequenceNumber(oldest_seq_nb, seq_nb)) { | 201 if (IsNewerSequenceNumber(oldest_seq_num, seq_num)) { |
148 oldest_seq_nb = seq_nb; | 202 oldest_seq_num = seq_num; |
149 } | 203 } |
150 ++node_it; | 204 ++node_it; |
151 ++number_packets_received; | 205 ++number_packets_received; |
152 } | 206 } |
153 // Interval width between oldest and newest sequence number. | 207 // Interval width between oldest and newest sequence number. |
154 // There was an overflow if newest_seq_nb < oldest_seq_nb. | 208 // 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); | 209 int gap = static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1); |
156 | 210 |
157 return static_cast<float>(gap - number_packets_received) / gap; | 211 return static_cast<float>(gap - number_packets_received) / gap; |
158 } | 212 } |
159 | 213 |
160 LinkedSet::~LinkedSet() { | 214 LinkedSet::~LinkedSet() { |
161 while (!empty()) | 215 while (!empty()) |
162 RemoveTail(); | 216 RemoveTail(); |
163 } | 217 } |
164 | 218 |
165 void LinkedSet::Insert(uint16_t sequence_number, | 219 void LinkedSet::Insert(uint16_t sequence_number, |
166 int64_t send_time_ms, | 220 int64_t send_time_ms, |
167 int64_t arrival_time_ms, | 221 int64_t arrival_time_ms, |
168 size_t payload_size) { | 222 size_t payload_size) { |
169 std::map<uint16_t, PacketNodeIt>::iterator it = map_.find(sequence_number); | 223 auto it = map_.find(sequence_number); |
170 if (it != map_.end()) { | 224 if (it != map_.end()) { |
171 PacketNodeIt node_it = it->second; | 225 PacketNodeIt node_it = it->second; |
172 PacketIdentifierNode* node = *node_it; | 226 PacketIdentifierNode* node = *node_it; |
173 node->arrival_time_ms = arrival_time_ms; | 227 node->arrival_time_ms = arrival_time_ms; |
174 if (node_it != list_.begin()) { | 228 if (node_it != list_.begin()) { |
175 list_.erase(node_it); | 229 list_.erase(node_it); |
176 list_.push_front(node); | 230 list_.push_front(node); |
177 map_[sequence_number] = list_.begin(); | 231 map_[sequence_number] = list_.begin(); |
178 } | 232 } |
179 } else { | 233 } else { |
180 if (size() == capacity_) { | 234 if (size() == capacity_) { |
181 RemoveTail(); | 235 RemoveTail(); |
182 } | 236 } |
183 UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms, | 237 UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms, |
184 arrival_time_ms, payload_size)); | 238 arrival_time_ms, payload_size)); |
185 } | 239 } |
186 } | 240 } |
| 241 |
| 242 void LinkedSet::Insert(PacketIdentifierNode packet_identifier) { |
| 243 Insert(packet_identifier.sequence_number, packet_identifier.send_time_ms, |
| 244 packet_identifier.arrival_time_ms, packet_identifier.payload_size); |
| 245 } |
| 246 |
187 void LinkedSet::RemoveTail() { | 247 void LinkedSet::RemoveTail() { |
188 map_.erase(list_.back()->sequence_number); | 248 map_.erase(list_.back()->sequence_number); |
189 delete list_.back(); | 249 delete list_.back(); |
190 list_.pop_back(); | 250 list_.pop_back(); |
191 } | 251 } |
192 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) { | 252 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) { |
193 list_.push_front(new_head); | 253 list_.push_front(new_head); |
194 map_[new_head->sequence_number] = list_.begin(); | 254 map_[new_head->sequence_number] = list_.begin(); |
195 } | 255 } |
196 | 256 |
| 257 void LinkedSet::Erase(PacketNodeIt node_it) { |
| 258 map_.erase((*node_it)->sequence_number); |
| 259 delete (*node_it); |
| 260 list_.erase(node_it); |
| 261 } |
| 262 |
| 263 void LossAccount::Add(LossAccount rhs) { |
| 264 num_total += rhs.num_total; |
| 265 num_lost += rhs.num_lost; |
| 266 } |
| 267 void LossAccount::Subtract(LossAccount rhs) { |
| 268 num_total -= rhs.num_total; |
| 269 num_lost -= rhs.num_lost; |
| 270 } |
| 271 |
| 272 float LossAccount::LossRatio() { |
| 273 if (num_total == 0) |
| 274 return 0.0f; |
| 275 return static_cast<float>(num_lost) / num_total; |
| 276 } |
| 277 |
197 } // namespace bwe | 278 } // namespace bwe |
198 } // namespace testing | 279 } // namespace testing |
199 } // namespace webrtc | 280 } // namespace webrtc |
OLD | NEW |