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
12#include "webrtc/call/bitrate_allocator.h"
13
14#include <algorithm>
15#include <utility>
16
17#include "webrtc/modules/bitrate_controller/include/bitrate_controller.h"
18
19namespace webrtc {
20
21// Allow packets to be transmitted in up to 2 times max video bitrate if the
22// bandwidth estimate allows it.
23const int kTransmissionMaxBitrateMultiplier = 2;
24const int kDefaultBitrateBps = 300000;
25
26BitrateAllocator::BitrateAllocator()
27    : crit_sect_(CriticalSectionWrapper::CreateCriticalSection()),
28      bitrate_observers_(),
29      bitrate_observers_modified_(false),
30      enforce_min_bitrate_(true),
31      last_bitrate_bps_(kDefaultBitrateBps),
32      last_fraction_loss_(0),
33      last_rtt_(0) {}
34
35uint32_t BitrateAllocator::OnNetworkChanged(uint32_t bitrate,
36                                            uint8_t fraction_loss,
37                                            int64_t rtt) {
38  CriticalSectionScoped lock(crit_sect_.get());
39  last_bitrate_bps_ = bitrate;
40  last_fraction_loss_ = fraction_loss;
41  last_rtt_ = rtt;
42  uint32_t allocated_bitrate_bps = 0;
43  ObserverBitrateMap allocation = AllocateBitrates();
44  for (const auto& kv : allocation) {
45    kv.first->OnNetworkChanged(kv.second, last_fraction_loss_, last_rtt_);
46    allocated_bitrate_bps += kv.second;
47  }
48  return allocated_bitrate_bps;
49}
50
51BitrateAllocator::ObserverBitrateMap BitrateAllocator::AllocateBitrates() {
52  if (bitrate_observers_.empty())
53    return ObserverBitrateMap();
54
55  uint32_t sum_min_bitrates = 0;
56  for (const auto& observer : bitrate_observers_)
57    sum_min_bitrates += observer.second.min_bitrate;
58  if (last_bitrate_bps_ <= sum_min_bitrates)
59    return LowRateAllocation(last_bitrate_bps_);
60  else
61    return NormalRateAllocation(last_bitrate_bps_, sum_min_bitrates);
62}
63
64int BitrateAllocator::AddBitrateObserver(BitrateObserver* observer,
65                                         uint32_t min_bitrate_bps,
66                                         uint32_t max_bitrate_bps) {
67  CriticalSectionScoped lock(crit_sect_.get());
68
69  BitrateObserverConfList::iterator it =
70      FindObserverConfigurationPair(observer);
71
72  // Allow the max bitrate to be exceeded for FEC and retransmissions.
73  // TODO(holmer): We have to get rid of this hack as it makes it difficult to
74  // properly allocate bitrate. The allocator should instead distribute any
75  // extra bitrate after all streams have maxed out.
76  max_bitrate_bps *= kTransmissionMaxBitrateMultiplier;
77  if (it != bitrate_observers_.end()) {
78    // Update current configuration.
79    it->second.min_bitrate = min_bitrate_bps;
80    it->second.max_bitrate = max_bitrate_bps;
81  } else {
82    // Add new settings.
83    bitrate_observers_.push_back(BitrateObserverConfiguration(
84        observer, BitrateConfiguration(min_bitrate_bps, max_bitrate_bps)));
85    bitrate_observers_modified_ = true;
86  }
87
88  ObserverBitrateMap allocation = AllocateBitrates();
89  int new_observer_bitrate_bps = 0;
90  for (auto& kv : allocation) {
91    kv.first->OnNetworkChanged(kv.second, last_fraction_loss_, last_rtt_);
92    if (kv.first == observer)
93      new_observer_bitrate_bps = kv.second;
94  }
95  return new_observer_bitrate_bps;
96}
97
98void BitrateAllocator::RemoveBitrateObserver(BitrateObserver* observer) {
99  CriticalSectionScoped lock(crit_sect_.get());
100  BitrateObserverConfList::iterator it =
101      FindObserverConfigurationPair(observer);
102  if (it != bitrate_observers_.end()) {
103    bitrate_observers_.erase(it);
104    bitrate_observers_modified_ = true;
105  }
106}
107
108void BitrateAllocator::GetMinMaxBitrateSumBps(int* min_bitrate_sum_bps,
109                                              int* max_bitrate_sum_bps) const {
110  *min_bitrate_sum_bps = 0;
111  *max_bitrate_sum_bps = 0;
112
113  CriticalSectionScoped lock(crit_sect_.get());
114  for (const auto& observer : bitrate_observers_) {
115    *min_bitrate_sum_bps += observer.second.min_bitrate;
116    *max_bitrate_sum_bps += observer.second.max_bitrate;
117  }
118}
119
120BitrateAllocator::BitrateObserverConfList::iterator
121BitrateAllocator::FindObserverConfigurationPair(
122    const BitrateObserver* observer) {
123  for (auto it = bitrate_observers_.begin(); it != bitrate_observers_.end();
124       ++it) {
125    if (it->first == observer)
126      return it;
127  }
128  return bitrate_observers_.end();
129}
130
131void BitrateAllocator::EnforceMinBitrate(bool enforce_min_bitrate) {
132  CriticalSectionScoped lock(crit_sect_.get());
133  enforce_min_bitrate_ = enforce_min_bitrate;
134}
135
136BitrateAllocator::ObserverBitrateMap BitrateAllocator::NormalRateAllocation(
137    uint32_t bitrate,
138    uint32_t sum_min_bitrates) {
139  uint32_t number_of_observers =
140      static_cast<uint32_t>(bitrate_observers_.size());
141  uint32_t bitrate_per_observer =
142      (bitrate - sum_min_bitrates) / number_of_observers;
143  // Use map to sort list based on max bitrate.
144  ObserverSortingMap list_max_bitrates;
145  for (const auto& observer : bitrate_observers_) {
146    list_max_bitrates.insert(std::pair<uint32_t, ObserverConfiguration>(
147        observer.second.max_bitrate,
148        ObserverConfiguration(observer.first, observer.second.min_bitrate)));
149  }
150  ObserverBitrateMap allocation;
151  ObserverSortingMap::iterator max_it = list_max_bitrates.begin();
152  while (max_it != list_max_bitrates.end()) {
153    number_of_observers--;
154    uint32_t observer_allowance =
155        max_it->second.min_bitrate + bitrate_per_observer;
156    if (max_it->first < observer_allowance) {
157      // We have more than enough for this observer.
158      // Carry the remainder forward.
159      uint32_t remainder = observer_allowance - max_it->first;
160      if (number_of_observers != 0) {
161        bitrate_per_observer += remainder / number_of_observers;
162      }
163      allocation[max_it->second.observer] = max_it->first;
164    } else {
165      allocation[max_it->second.observer] = observer_allowance;
166    }
167    list_max_bitrates.erase(max_it);
168    // Prepare next iteration.
169    max_it = list_max_bitrates.begin();
170  }
171  return allocation;
172}
173
174BitrateAllocator::ObserverBitrateMap BitrateAllocator::LowRateAllocation(
175    uint32_t bitrate) {
176  ObserverBitrateMap allocation;
177  if (enforce_min_bitrate_) {
178    // Min bitrate to all observers.
179    for (const auto& observer : bitrate_observers_)
180      allocation[observer.first] = observer.second.min_bitrate;
181  } else {
182    // Allocate up to |min_bitrate| to one observer at a time, until
183    // |bitrate| is depleted.
184    uint32_t remainder = bitrate;
185    for (const auto& observer : bitrate_observers_) {
186      uint32_t allocated_bitrate =
187          std::min(remainder, observer.second.min_bitrate);
188      allocation[observer.first] = allocated_bitrate;
189      remainder -= allocated_bitrate;
190    }
191  }
192  return allocation;
193}
194}  // namespace webrtc
195