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