Adding reordering logic in audio network adaptor.

webrtc/modules/audio_coding/audio_network_adaptor/controller_manager.cc

 /*
  *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
+#include "webrtc/modules/audio_coding/audio_network_adaptor/controller_manager.h"
+
+#include <cmath>
 #include <utility>
 
-#include "webrtc/modules/audio_coding/audio_network_adaptor/controller_manager.h"
-
 namespace webrtc {
 
-ControllerManagerImpl::Config::Config() = default;
+ControllerManagerImpl::Config::Config(int min_reordering_time_ms,
+                                      float min_reordering_squared_distance,
+                                      Clock* clock)
+    : min_reordering_time_ms(min_reordering_time_ms),
+      min_reordering_squared_distance(min_reordering_squared_distance),
+      clock(clock) {}
 
 ControllerManagerImpl::Config::~Config() = default;
 
 ControllerManagerImpl::ControllerManagerImpl(const Config& config)
-    : config_(config) {}
+    : ControllerManagerImpl(
+          config,
+          std::map<const Controller*, std::pair<int, float>>(),
+          std::vector<std::unique_ptr<Controller>>()) {}
 
 ControllerManagerImpl::ControllerManagerImpl(
     const Config& config,
+    const std::map<const Controller*, std::pair<int, float>>&
+        chracteristic_points,
     std::vector<std::unique_ptr<Controller>> controllers)
-    : config_(config), controllers_(std::move(controllers)) {
-  for (auto& controller : controllers_) {
+    : config_(config),
+      controllers_(std::move(controllers)),
+      last_reordering_time_ms_(rtc::Optional<int64_t>()),
+      last_scoring_point_(0, 0.0) {
+  for (auto& controller : controllers_)
     default_sorted_controllers_.push_back(controller.get());
+  sorted_controllers_ = default_sorted_controllers_;
+  for (auto& controller_point : chracteristic_points) {
+    controller_scoring_points_.insert(std::make_pair(
+        controller_point.first, ScoringPoint(controller_point.second.first,
+                                             controller_point.second.second)));
   }
 }
 
 ControllerManagerImpl::~ControllerManagerImpl() = default;
 
 std::vector<Controller*> ControllerManagerImpl::GetSortedControllers(
     const Controller::NetworkMetrics& metrics) {
-  // TODO(minyue): Reorder controllers according to their significance.
-  return default_sorted_controllers_;
+  int64_t now_ms = config_.clock->TimeInMilliseconds();
+
+  if (!metrics.uplink_bandwidth_bps || !metrics.uplink_packet_loss_fraction)
+    return sorted_controllers_;
+
+  if (last_reordering_time_ms_ &&
+      now_ms - *last_reordering_time_ms_ < config_.min_reordering_time_ms)
+    return sorted_controllers_;
+
+  ScoringPoint scoring_point(*metrics.uplink_bandwidth_bps,
+                             *metrics.uplink_packet_loss_fraction);
+
+  if (last_reordering_time_ms_ &&

[michaelt, 2016/09/19 08:22:45]

should work even without "last_reordering_time_ms_ &&" right ?

[minyue-webrtc, 2016/09/19 10:06:57]

If last_reordering_time_ms_ is none, it will try the following sorting.

[michaelt, 2016/09/22 06:57:16]

Acknowledged.

+      last_scoring_point_.SquaredDistanceTo(scoring_point) <
+          config_.min_reordering_squared_distance)
+    return sorted_controllers_;
+
+  // Sort controllers according to the distances of |scoring_point| to the
+  // characteristic scoring points of controllers.
+  //
+  // A controller that does not associate with any scoring point
+  // are treated as if
+  // 1) they are less important than any controller that has a scoring point,
+  // 2) they are equally important to any controller that has no scoring point,
+  //    and their relative order will follow |default_sorted_controllers_|.
+  std::vector<Controller*> sorted_controllers(default_sorted_controllers_);
+  std::stable_sort(
+      sorted_controllers.begin(), sorted_controllers.end(),
+      [this, &scoring_point](const Controller* lhs, const Controller* rhs) {
+        auto lhs_scoring_point = controller_scoring_points_.find(lhs);
+        auto rhs_scoring_point = controller_scoring_points_.find(rhs);
+
+        if (lhs_scoring_point != controller_scoring_points_.end() &&

[hlundin-webrtc, 2016/09/20 08:44:00]

You can swap the order of these two "end-cases":

if (lhs_scoring_point == controller_scoring_points_.end())
  return false;
if (rhs_scoring_point == controller_scoring_points_.end())
  return true;

[minyue-webrtc, 2016/09/21 07:42:58]

Done.

+            rhs_scoring_point == controller_scoring_points_.end())
+          return true;
+
+        if (lhs_scoring_point == controller_scoring_points_.end())
+          return false;
+
+        return lhs_scoring_point->second.SquaredDistanceTo(scoring_point) <
+               rhs_scoring_point->second.SquaredDistanceTo(scoring_point);
+      });
+
+  if (sorted_controllers_ != sorted_controllers) {
+    sorted_controllers_ = sorted_controllers;
+    last_reordering_time_ms_ = rtc::Optional<int64_t>(now_ms);
+    last_scoring_point_ = scoring_point;
+  }
+  return sorted_controllers_;
 }
 
 std::vector<Controller*> ControllerManagerImpl::GetControllers() const {
   return default_sorted_controllers_;
 }
 
+ControllerManagerImpl::ScoringPoint::ScoringPoint(
+    int uplink_bandwidth_bps,
+    float uplink_packet_loss_fraction)
+    : uplink_bandwidth_bps(uplink_bandwidth_bps),
+      uplink_packet_loss_fraction(uplink_packet_loss_fraction) {}
+
+namespace {
+
+constexpr int kMinUplinkBandwidthBps = 0;
+constexpr int kMaxUplinkBandwidthBps = 120000;

[michaelt, 2016/09/19 08:22:45]

should we inject this by the config. 
Or if not we should at least use 64kbps as max.

[minyue-webrtc, 2016/09/19 10:06:57]

I think the definition of distance can be hard coded, and let
min_reordering_distance to be trained for it. But I am open to suggestions
regarding this.

+
+float NormalizeUplinkBandwidth(int uplink_Bandwidth_bps) {

[hlundin-webrtc, 2016/09/20 08:44:00]

Small 'b' in the parameter name.

[minyue-webrtc, 2016/09/21 07:42:58]

oh, yes, my bad.

+  uplink_Bandwidth_bps =
+      std::min(kMaxUplinkBandwidthBps,
+               std::max(kMinUplinkBandwidthBps, uplink_Bandwidth_bps));
+  return static_cast<float>(uplink_Bandwidth_bps - kMinUplinkBandwidthBps) /
+         (kMaxUplinkBandwidthBps - kMinUplinkBandwidthBps);
+}
+
+float NormalizePacketLossFraction(float uplink_packet_loss_fraction) {
+  // |uplink_packet_loss_fraction| is seldom smaller than 0.3, so we scale it up

[hlundin-webrtc, 2016/09/20 08:44:00]

"seldom smaller" -> "seldom larger"?

[minyue-webrtc, 2016/09/21 07:42:58]

oh, my bad

+  // by 3.3333f.
+  return std::min(uplink_packet_loss_fraction * 3.3333f, 1.0f);
+}
+
+}  // namespace
+
+float ControllerManagerImpl::ScoringPoint::SquaredDistanceTo(
+    const ScoringPoint& scoring_point) const {
+  float diff_normalized_bitrate_bps =
+      NormalizeUplinkBandwidth(scoring_point.uplink_bandwidth_bps) -
+      NormalizeUplinkBandwidth(uplink_bandwidth_bps);
+  float diff_normalized_packet_loss =
+      NormalizePacketLossFraction(scoring_point.uplink_packet_loss_fraction) -
+      NormalizePacketLossFraction(uplink_packet_loss_fraction);
+  return std::pow(diff_normalized_bitrate_bps, 2) +
+         std::pow(diff_normalized_packet_loss, 2);
+}
+
 }  // namespace webrtc