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> 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 31 LinkShare::LinkShare(ChokeFilter* choke_filter) 32 : choke_filter_(choke_filter), running_flows_(choke_filter->flow_ids()) { 33 } 34 35 void LinkShare::PauseFlow(int flow_id) { 36 running_flows_.erase(flow_id); 37 } 38 39 void LinkShare::ResumeFlow(int flow_id) { 40 running_flows_.insert(flow_id); 41 } 42 43 uint32_t LinkShare::TotalAvailableKbps() { 44 return choke_filter_->capacity_kbps(); 45 } 46 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 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 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 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 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> 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 151 void MetricRecorder::UpdateTimeMs(int64_t time_ms) { 152 now_ms_ = std::max(now_ms_, time_ms); 153 } 154 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 162 void MetricRecorder::UpdateSendingEstimateKbps(int64_t bitrate_kbps) { 163 plot_information_[kSendingEstimate].Update(now_ms_, bitrate_kbps); 164 } 165 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 171 void MetricRecorder::UpdateLoss(float loss_ratio) { 172 plot_information_[kLoss].Update(now_ms_, loss_ratio); 173 } 174 175 void MetricRecorder::UpdateObjective() { 176 plot_information_[kObjective].Update(now_ms_, ObjectiveFunction()); 177 } 178 179 uint32_t MetricRecorder::GetTotalAvailableKbps() { 180 if (link_share_ == nullptr) 181 return 0; 182 return link_share_->TotalAvailableKbps(); 183 } 184 185 uint32_t MetricRecorder::GetAvailablePerFlowKbps() { 186 if (link_share_ == nullptr) 187 return 0; 188 return link_share_->AvailablePerFlowKbps(flow_id_); 189 } 190 191 uint32_t MetricRecorder::GetSendingEstimateKbps() { 192 return static_cast<uint32_t>(plot_information_[kSendingEstimate].value); 193 } 194 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 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 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 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 258 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 298 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 305 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 336 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 347 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 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 365 void MetricRecorder::PauseFlow() { 366 PlotZero(); 367 link_share_->PauseFlow(flow_id_); 368 } 369 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 376 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 383 int64_t MetricRecorder::RunDurationMs(int64_t extra_offset_ms) const { 384 return now_ms_ - start_computing_metrics_ms_ - extra_offset_ms; 385 } 386 387 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_. 399 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. 416 double MetricRecorder::Renormalize(double x) const { 417 return (x * num_packets_received_) / now_ms_; 418 } 419 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 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. 432 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
