1 /*
2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
3 *
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
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "webrtc/modules/remote_bitrate_estimator/test/metric_recorder.h"
12
13 #include <algorithm>
14
15 #include "webrtc/modules/remote_bitrate_estimator/test/packet_sender.h"
16
17 namespace webrtc {
18 namespace testing {
19 namespace bwe {
20
21 namespace {
22 // Holder mean, Manhattan distance for p=1, EuclidianNorm/sqrt(n) for p=2.
23 template <typename T>
NormLp(T sum,size_t size,double p)24 double NormLp(T sum, size_t size, double p) {
25 return pow(sum / size, 1.0 / p);
26 }
27 }
28
29 const double kP = 1.0; // Used for Norm Lp.
30
LinkShare(ChokeFilter * choke_filter)31 LinkShare::LinkShare(ChokeFilter* choke_filter)
32 : choke_filter_(choke_filter), running_flows_(choke_filter->flow_ids()) {
33 }
34
PauseFlow(int flow_id)35 void LinkShare::PauseFlow(int flow_id) {
36 running_flows_.erase(flow_id);
37 }
38
ResumeFlow(int flow_id)39 void LinkShare::ResumeFlow(int flow_id) {
40 running_flows_.insert(flow_id);
41 }
42
TotalAvailableKbps()43 uint32_t LinkShare::TotalAvailableKbps() {
44 return choke_filter_->capacity_kbps();
45 }
46
AvailablePerFlowKbps(int flow_id)47 uint32_t LinkShare::AvailablePerFlowKbps(int flow_id) {
48 uint32_t available_capacity_per_flow_kbps = 0;
49 if (running_flows_.find(flow_id) != running_flows_.end()) {
50 available_capacity_per_flow_kbps =
51 TotalAvailableKbps() / static_cast<uint32_t>(running_flows_.size());
52 }
53 return available_capacity_per_flow_kbps;
54 }
55
MetricRecorder(const std::string algorithm_name,int flow_id,PacketSender * packet_sender,LinkShare * link_share)56 MetricRecorder::MetricRecorder(const std::string algorithm_name,
57 int flow_id,
58 PacketSender* packet_sender,
59 LinkShare* link_share)
60 : algorithm_name_(algorithm_name),
61 flow_id_(flow_id),
62 link_share_(link_share),
63 now_ms_(0),
64 sum_delays_ms_(0),
65 delay_histogram_ms_(),
66 sum_delays_square_ms2_(0),
67 sum_throughput_bytes_(0),
68 last_unweighted_estimate_error_(0),
69 optimal_throughput_bits_(0),
70 last_available_bitrate_per_flow_kbps_(0),
71 start_computing_metrics_ms_(0),
72 started_computing_metrics_(false),
73 num_packets_received_(0) {
74 std::fill_n(sum_lp_weighted_estimate_error_, 2, 0);
75 if (packet_sender != nullptr)
76 packet_sender->set_metric_recorder(this);
77 }
78
SetPlotInformation(const std::vector<std::string> & prefixes,bool plot_delay,bool plot_loss)79 void MetricRecorder::SetPlotInformation(
80 const std::vector<std::string>& prefixes,
81 bool plot_delay,
82 bool plot_loss) {
83 assert(prefixes.size() == kNumMetrics);
84 for (size_t i = 0; i < kNumMetrics; ++i) {
85 plot_information_[i].prefix = prefixes[i];
86 }
87 plot_information_[kThroughput].plot_interval_ms = 100;
88 plot_information_[kSendingEstimate].plot_interval_ms = 100;
89 plot_information_[kDelay].plot_interval_ms = 100;
90 plot_information_[kLoss].plot_interval_ms = 500;
91 plot_information_[kObjective].plot_interval_ms = 1000;
92 plot_information_[kTotalAvailable].plot_interval_ms = 1000;
93 plot_information_[kAvailablePerFlow].plot_interval_ms = 1000;
94
95 for (int i = kThroughput; i < kNumMetrics; ++i) {
96 plot_information_[i].last_plot_ms = 0;
97 switch (i) {
98 case kSendingEstimate:
99 case kObjective:
100 case kAvailablePerFlow:
101 plot_information_[i].plot = false;
102 break;
103 case kLoss:
104 plot_information_[i].plot = plot_loss;
105 break;
106 case kDelay:
107 plot_information_[i].plot = plot_delay;
108 break;
109 default:
110 plot_information_[i].plot = true;
111 }
112 }
113 }
114
PlotAllDynamics()115 void MetricRecorder::PlotAllDynamics() {
116 for (int i = kThroughput; i < kNumMetrics; ++i) {
117 if (plot_information_[i].plot &&
118 now_ms_ - plot_information_[i].last_plot_ms >=
119 plot_information_[i].plot_interval_ms) {
120 PlotDynamics(i);
121 }
122 }
123 }
124
PlotDynamics(int metric)125 void MetricRecorder::PlotDynamics(int metric) {
126 if (metric == kTotalAvailable) {
127 BWE_TEST_LOGGING_PLOT_WITH_NAME(
128 0, plot_information_[kTotalAvailable].prefix, now_ms_,
129 GetTotalAvailableKbps(), "Available");
130 } else if (metric == kAvailablePerFlow) {
131 BWE_TEST_LOGGING_PLOT_WITH_NAME(
132 0, plot_information_[kAvailablePerFlow].prefix, now_ms_,
133 GetAvailablePerFlowKbps(), "Available_per_flow");
134 } else {
135 PlotLine(metric, plot_information_[metric].prefix,
136 plot_information_[metric].time_ms,
137 plot_information_[metric].value);
138 }
139 plot_information_[metric].last_plot_ms = now_ms_;
140 }
141
142 template <typename T>
PlotLine(int windows_id,const std::string & prefix,int64_t time_ms,T y)143 void MetricRecorder::PlotLine(int windows_id,
144 const std::string& prefix,
145 int64_t time_ms,
146 T y) {
147 BWE_TEST_LOGGING_PLOT_WITH_NAME(windows_id, prefix, time_ms,
148 static_cast<double>(y), algorithm_name_);
149 }
150
UpdateTimeMs(int64_t time_ms)151 void MetricRecorder::UpdateTimeMs(int64_t time_ms) {
152 now_ms_ = std::max(now_ms_, time_ms);
153 }
154
UpdateThroughput(int64_t bitrate_kbps,size_t payload_size)155 void MetricRecorder::UpdateThroughput(int64_t bitrate_kbps,
156 size_t payload_size) {
157 // Total throughput should be computed before updating the time.
158 PushThroughputBytes(payload_size, now_ms_);
159 plot_information_[kThroughput].Update(now_ms_, bitrate_kbps);
160 }
161
UpdateSendingEstimateKbps(int64_t bitrate_kbps)162 void MetricRecorder::UpdateSendingEstimateKbps(int64_t bitrate_kbps) {
163 plot_information_[kSendingEstimate].Update(now_ms_, bitrate_kbps);
164 }
165
UpdateDelayMs(int64_t delay_ms)166 void MetricRecorder::UpdateDelayMs(int64_t delay_ms) {
167 PushDelayMs(delay_ms, now_ms_);
168 plot_information_[kDelay].Update(now_ms_, delay_ms);
169 }
170
UpdateLoss(float loss_ratio)171 void MetricRecorder::UpdateLoss(float loss_ratio) {
172 plot_information_[kLoss].Update(now_ms_, loss_ratio);
173 }
174
UpdateObjective()175 void MetricRecorder::UpdateObjective() {
176 plot_information_[kObjective].Update(now_ms_, ObjectiveFunction());
177 }
178
GetTotalAvailableKbps()179 uint32_t MetricRecorder::GetTotalAvailableKbps() {
180 if (link_share_ == nullptr)
181 return 0;
182 return link_share_->TotalAvailableKbps();
183 }
184
GetAvailablePerFlowKbps()185 uint32_t MetricRecorder::GetAvailablePerFlowKbps() {
186 if (link_share_ == nullptr)
187 return 0;
188 return link_share_->AvailablePerFlowKbps(flow_id_);
189 }
190
GetSendingEstimateKbps()191 uint32_t MetricRecorder::GetSendingEstimateKbps() {
192 return static_cast<uint32_t>(plot_information_[kSendingEstimate].value);
193 }
194
PushDelayMs(int64_t delay_ms,int64_t arrival_time_ms)195 void MetricRecorder::PushDelayMs(int64_t delay_ms, int64_t arrival_time_ms) {
196 if (ShouldRecord(arrival_time_ms)) {
197 sum_delays_ms_ += delay_ms;
198 sum_delays_square_ms2_ += delay_ms * delay_ms;
199 if (delay_histogram_ms_.find(delay_ms) == delay_histogram_ms_.end()) {
200 delay_histogram_ms_[delay_ms] = 0;
201 }
202 ++delay_histogram_ms_[delay_ms];
203 }
204 }
205
UpdateEstimateError(int64_t new_value)206 void MetricRecorder::UpdateEstimateError(int64_t new_value) {
207 int64_t lp_value = pow(static_cast<double>(std::abs(new_value)), kP);
208 if (new_value < 0) {
209 sum_lp_weighted_estimate_error_[0] += lp_value;
210 } else {
211 sum_lp_weighted_estimate_error_[1] += lp_value;
212 }
213 }
214
PushThroughputBytes(size_t payload_size,int64_t arrival_time_ms)215 void MetricRecorder::PushThroughputBytes(size_t payload_size,
216 int64_t arrival_time_ms) {
217 if (ShouldRecord(arrival_time_ms)) {
218 ++num_packets_received_;
219 sum_throughput_bytes_ += payload_size;
220
221 int64_t current_available_per_flow_kbps =
222 static_cast<int64_t>(GetAvailablePerFlowKbps());
223
224 int64_t current_bitrate_diff_kbps =
225 static_cast<int64_t>(GetSendingEstimateKbps()) -
226 current_available_per_flow_kbps;
227
228 int64_t weighted_estimate_error =
229 (((current_bitrate_diff_kbps + last_unweighted_estimate_error_) *
230 (arrival_time_ms - plot_information_[kThroughput].time_ms)) /
231 2);
232
233 UpdateEstimateError(weighted_estimate_error);
234
235 optimal_throughput_bits_ +=
236 ((current_available_per_flow_kbps +
237 last_available_bitrate_per_flow_kbps_) *
238 (arrival_time_ms - plot_information_[kThroughput].time_ms)) /
239 2;
240
241 last_available_bitrate_per_flow_kbps_ = current_available_per_flow_kbps;
242 }
243 }
244
ShouldRecord(int64_t arrival_time_ms)245 bool MetricRecorder::ShouldRecord(int64_t arrival_time_ms) {
246 if (arrival_time_ms >= start_computing_metrics_ms_) {
247 if (!started_computing_metrics_) {
248 start_computing_metrics_ms_ = arrival_time_ms;
249 now_ms_ = arrival_time_ms;
250 started_computing_metrics_ = true;
251 }
252 return true;
253 } else {
254 return false;
255 }
256 }
257
PlotThroughputHistogram(const std::string & title,const std::string & bwe_name,size_t num_flows,int64_t extra_offset_ms,const std::string optimum_id) const258 void MetricRecorder::PlotThroughputHistogram(
259 const std::string& title,
260 const std::string& bwe_name,
261 size_t num_flows,
262 int64_t extra_offset_ms,
263 const std::string optimum_id) const {
264 double optimal_bitrate_per_flow_kbps = static_cast<double>(
265 optimal_throughput_bits_ / RunDurationMs(extra_offset_ms));
266
267 double neg_error = Renormalize(
268 NormLp(sum_lp_weighted_estimate_error_[0], num_packets_received_, kP));
269 double pos_error = Renormalize(
270 NormLp(sum_lp_weighted_estimate_error_[1], num_packets_received_, kP));
271
272 double average_bitrate_kbps = AverageBitrateKbps(extra_offset_ms);
273
274 // Prevent the error to be too close to zero (plotting issue).
275 double extra_error = average_bitrate_kbps / 500;
276
277 std::string optimum_title =
278 optimum_id.empty() ? "optimal_bitrate" : "optimal_bitrates#" + optimum_id;
279
280 BWE_TEST_LOGGING_LABEL(4, title, "average_bitrate_(kbps)", num_flows);
281 BWE_TEST_LOGGING_LIMITERRORBAR(
282 4, bwe_name, average_bitrate_kbps,
283 average_bitrate_kbps - neg_error - extra_error,
284 average_bitrate_kbps + pos_error + extra_error, "estimate_error",
285 optimal_bitrate_per_flow_kbps, optimum_title, flow_id_);
286
287 BWE_TEST_LOGGING_LOG1("RESULTS >>> " + bwe_name + " Channel utilization : ",
288 "%lf %%",
289 100.0 * static_cast<double>(average_bitrate_kbps) /
290 optimal_bitrate_per_flow_kbps);
291
292 RTC_UNUSED(pos_error);
293 RTC_UNUSED(neg_error);
294 RTC_UNUSED(extra_error);
295 RTC_UNUSED(optimal_bitrate_per_flow_kbps);
296 }
297
PlotThroughputHistogram(const std::string & title,const std::string & bwe_name,size_t num_flows,int64_t extra_offset_ms) const298 void MetricRecorder::PlotThroughputHistogram(const std::string& title,
299 const std::string& bwe_name,
300 size_t num_flows,
301 int64_t extra_offset_ms) const {
302 PlotThroughputHistogram(title, bwe_name, num_flows, extra_offset_ms, "");
303 }
304
PlotDelayHistogram(const std::string & title,const std::string & bwe_name,size_t num_flows,int64_t one_way_path_delay_ms) const305 void MetricRecorder::PlotDelayHistogram(const std::string& title,
306 const std::string& bwe_name,
307 size_t num_flows,
308 int64_t one_way_path_delay_ms) const {
309 double average_delay_ms =
310 static_cast<double>(sum_delays_ms_) / num_packets_received_;
311
312 // Prevent the error to be too close to zero (plotting issue).
313 double extra_error = average_delay_ms / 500;
314 double tenth_sigma_ms = DelayStdDev() / 10.0 + extra_error;
315 int64_t percentile_5_ms = NthDelayPercentile(5);
316 int64_t percentile_95_ms = NthDelayPercentile(95);
317
318 BWE_TEST_LOGGING_LABEL(5, title, "average_delay_(ms)", num_flows)
319 BWE_TEST_LOGGING_ERRORBAR(5, bwe_name, average_delay_ms, percentile_5_ms,
320 percentile_95_ms, "5th and 95th percentiles",
321 flow_id_);
322
323 // Log added latency, disregard baseline path delay.
324 BWE_TEST_LOGGING_LOG1("RESULTS >>> " + bwe_name + " Delay average : ",
325 "%lf ms", average_delay_ms - one_way_path_delay_ms);
326 BWE_TEST_LOGGING_LOG1("RESULTS >>> " + bwe_name + " Delay 5th percentile : ",
327 "%ld ms", percentile_5_ms - one_way_path_delay_ms);
328 BWE_TEST_LOGGING_LOG1("RESULTS >>> " + bwe_name + " Delay 95th percentile : ",
329 "%ld ms", percentile_95_ms - one_way_path_delay_ms);
330
331 RTC_UNUSED(tenth_sigma_ms);
332 RTC_UNUSED(percentile_5_ms);
333 RTC_UNUSED(percentile_95_ms);
334 }
335
PlotLossHistogram(const std::string & title,const std::string & bwe_name,size_t num_flows,float global_loss_ratio) const336 void MetricRecorder::PlotLossHistogram(const std::string& title,
337 const std::string& bwe_name,
338 size_t num_flows,
339 float global_loss_ratio) const {
340 BWE_TEST_LOGGING_LABEL(6, title, "packet_loss_ratio_(%)", num_flows)
341 BWE_TEST_LOGGING_BAR(6, bwe_name, 100.0f * global_loss_ratio, flow_id_);
342
343 BWE_TEST_LOGGING_LOG1("RESULTS >>> " + bwe_name + " Loss Ratio : ", "%f %%",
344 100.0f * global_loss_ratio);
345 }
346
PlotObjectiveHistogram(const std::string & title,const std::string & bwe_name,size_t num_flows) const347 void MetricRecorder::PlotObjectiveHistogram(const std::string& title,
348 const std::string& bwe_name,
349 size_t num_flows) const {
350 BWE_TEST_LOGGING_LABEL(7, title, "objective_function", num_flows)
351 BWE_TEST_LOGGING_BAR(7, bwe_name, ObjectiveFunction(), flow_id_);
352 }
353
PlotZero()354 void MetricRecorder::PlotZero() {
355 for (int i = kThroughput; i <= kLoss; ++i) {
356 if (plot_information_[i].plot) {
357 std::stringstream prefix;
358 prefix << "Receiver_" << flow_id_ << "_" + plot_information_[i].prefix;
359 PlotLine(i, prefix.str(), now_ms_, 0);
360 plot_information_[i].last_plot_ms = now_ms_;
361 }
362 }
363 }
364
PauseFlow()365 void MetricRecorder::PauseFlow() {
366 PlotZero();
367 link_share_->PauseFlow(flow_id_);
368 }
369
ResumeFlow(int64_t paused_time_ms)370 void MetricRecorder::ResumeFlow(int64_t paused_time_ms) {
371 UpdateTimeMs(now_ms_ + paused_time_ms);
372 PlotZero();
373 link_share_->ResumeFlow(flow_id_);
374 }
375
AverageBitrateKbps(int64_t extra_offset_ms) const376 double MetricRecorder::AverageBitrateKbps(int64_t extra_offset_ms) const {
377 int64_t duration_ms = RunDurationMs(extra_offset_ms);
378 if (duration_ms == 0)
379 return 0.0;
380 return static_cast<double>(8 * sum_throughput_bytes_ / duration_ms);
381 }
382
RunDurationMs(int64_t extra_offset_ms) const383 int64_t MetricRecorder::RunDurationMs(int64_t extra_offset_ms) const {
384 return now_ms_ - start_computing_metrics_ms_ - extra_offset_ms;
385 }
386
DelayStdDev() const387 double MetricRecorder::DelayStdDev() const {
388 if (num_packets_received_ == 0) {
389 return 0.0;
390 }
391 double mean = static_cast<double>(sum_delays_ms_) / num_packets_received_;
392 double mean2 =
393 static_cast<double>(sum_delays_square_ms2_) / num_packets_received_;
394 return sqrt(mean2 - pow(mean, 2.0));
395 }
396
397 // Since delay values are bounded in a subset of [0, 5000] ms,
398 // this function's execution time is O(1), independend of num_packets_received_.
NthDelayPercentile(int n) const399 int64_t MetricRecorder::NthDelayPercentile(int n) const {
400 if (num_packets_received_ == 0) {
401 return 0;
402 }
403 size_t num_packets_remaining = (n * num_packets_received_) / 100;
404 for (auto hist : delay_histogram_ms_) {
405 if (num_packets_remaining <= hist.second)
406 return static_cast<int64_t>(hist.first);
407 num_packets_remaining -= hist.second;
408 }
409
410 assert(false);
411 return -1;
412 }
413
414 // The weighted_estimate_error_ was weighted based on time windows.
415 // This function scales back the result before plotting.
Renormalize(double x) const416 double MetricRecorder::Renormalize(double x) const {
417 return (x * num_packets_received_) / now_ms_;
418 }
419
U(int64_t x,double alpha)420 inline double U(int64_t x, double alpha) {
421 if (alpha == 1.0) {
422 return log(static_cast<double>(x));
423 }
424 return pow(static_cast<double>(x), 1.0 - alpha) / (1.0 - alpha);
425 }
426
U(size_t x,double alpha)427 inline double U(size_t x, double alpha) {
428 return U(static_cast<int64_t>(x), alpha);
429 }
430
431 // TODO(magalhaesc): Update ObjectiveFunction.
ObjectiveFunction() const432 double MetricRecorder::ObjectiveFunction() const {
433 const double kDelta = 0.15; // Delay penalty factor.
434 const double kAlpha = 1.0;
435 const double kBeta = 1.0;
436
437 double throughput_metric = U(sum_throughput_bytes_, kAlpha);
438 double delay_penalty = kDelta * U(sum_delays_ms_, kBeta);
439
440 return throughput_metric - delay_penalty;
441 }
442
443 } // namespace bwe
444 } // namespace testing
445 } // namespace webrtc
446