Home | History | Annotate | Download | only in test 
      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/bwe.h"
     12 
     13 #include <limits>
     14 
     15 #include "webrtc/base/common.h"
     16 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/nada.h"
     17 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/remb.h"
     18 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/send_side.h"
     19 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/tcp.h"
     20 
     21 namespace webrtc {
     22 namespace testing {
     23 namespace bwe {
     24 
     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
     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.
     29 const int kSetCapacity = 1000;
     30 
     31 BweReceiver::BweReceiver(int flow_id)
     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_() {
     43 }
     44 
     45 void BweReceiver::ReceivePacket(int64_t arrival_time_ms,
     46                                 const MediaPacket& media_packet) {
     47   if (received_packets_.size() == kSetCapacity) {
     48     RelieveSetAndUpdateLoss();
     49   }
     50 
     51   received_packets_.Insert(media_packet.sequence_number(),
     52                            media_packet.send_time_ms(), arrival_time_ms,
     53                            media_packet.payload_size());
     54 
     55   rate_counter_.UpdateRates(media_packet.send_time_ms() * 1000,
     56                             static_cast<uint32_t>(media_packet.payload_size()));
     57 }
     58 
     59 class NullBweSender : public BweSender {
     60  public:
     61   NullBweSender() {}
     62   virtual ~NullBweSender() {}
     63 
     64   int GetFeedbackIntervalMs() const override { return 1000; }
     65   void GiveFeedback(const FeedbackPacket& feedback) override {}
     66   void OnPacketsSent(const Packets& packets) override {}
     67   int64_t TimeUntilNextProcess() override {
     68     return std::numeric_limits<int64_t>::max();
     69   }
     70   int Process() override { return 0; }
     71 
     72  private:
     73   RTC_DISALLOW_COPY_AND_ASSIGN(NullBweSender);
     74 };
     75 
     76 int64_t GetAbsSendTimeInMs(uint32_t abs_send_time) {
     77   const int kInterArrivalShift = 26;
     78   const int kAbsSendTimeInterArrivalUpshift = 8;
     79   const double kTimestampToMs =
     80       1000.0 / static_cast<double>(1 << kInterArrivalShift);
     81   uint32_t timestamp = abs_send_time << kAbsSendTimeInterArrivalUpshift;
     82   return static_cast<int64_t>(timestamp) * kTimestampToMs;
     83 }
     84 
     85 BweSender* CreateBweSender(BandwidthEstimatorType estimator,
     86                            int kbps,
     87                            BitrateObserver* observer,
     88                            Clock* clock) {
     89   switch (estimator) {
     90     case kRembEstimator:
     91       return new RembBweSender(kbps, observer, clock);
     92     case kFullSendSideEstimator:
     93       return new FullBweSender(kbps, observer, clock);
     94     case kNadaEstimator:
     95       return new NadaBweSender(kbps, observer, clock);
     96     case kTcpEstimator:
     97       FALLTHROUGH();
     98     case kNullEstimator:
     99       return new NullBweSender();
    100   }
    101   assert(false);
    102   return NULL;
    103 }
    104 
    105 BweReceiver* CreateBweReceiver(BandwidthEstimatorType type,
    106                                int flow_id,
    107                                bool plot) {
    108   switch (type) {
    109     case kRembEstimator:
    110       return new RembReceiver(flow_id, plot);
    111     case kFullSendSideEstimator:
    112       return new SendSideBweReceiver(flow_id);
    113     case kNadaEstimator:
    114       return new NadaBweReceiver(flow_id);
    115     case kTcpEstimator:
    116       return new TcpBweReceiver(flow_id);
    117     case kNullEstimator:
    118       return new BweReceiver(flow_id);
    119   }
    120   assert(false);
    121   return NULL;
    122 }
    123 
    124 // Take into account all LinkedSet content.
    125 void BweReceiver::UpdateLoss() {
    126   loss_account_.Add(LinkedSetPacketLossRatio());
    127 }
    128 
    129 // Preserve 10% latest packets and update packet loss based on the oldest
    130 // 90%, that will be removed.
    131 void BweReceiver::RelieveSetAndUpdateLoss() {
    132   // Compute Loss for the whole LinkedSet and updates loss_account_.
    133   UpdateLoss();
    134 
    135   size_t num_preserved_elements = received_packets_.size() / 10;
    136   PacketNodeIt it = received_packets_.begin();
    137   std::advance(it, num_preserved_elements);
    138 
    139   while (it != received_packets_.end()) {
    140     received_packets_.Erase(it++);
    141   }
    142 
    143   // Compute Loss for the preserved elements
    144   loss_account_.Subtract(LinkedSetPacketLossRatio());
    145 }
    146 
    147 float BweReceiver::GlobalReceiverPacketLossRatio() {
    148   UpdateLoss();
    149   return loss_account_.LossRatio();
    150 }
    151 
    152 // This function considers at most kSetCapacity = 1000 packets.
    153 LossAccount BweReceiver::LinkedSetPacketLossRatio() {
    154   if (received_packets_.empty()) {
    155     return LossAccount();
    156   }
    157 
    158   uint16_t oldest_seq_num = received_packets_.OldestSeqNumber();
    159   uint16_t newest_seq_num = received_packets_.NewestSeqNumber();
    160 
    161   size_t set_total_packets =
    162       static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1);
    163 
    164   size_t set_received_packets = received_packets_.size();
    165   size_t set_lost_packets = set_total_packets - set_received_packets;
    166 
    167   return LossAccount(set_total_packets, set_lost_packets);
    168 }
    169 
    170 uint32_t BweReceiver::RecentKbps() const {
    171   return (rate_counter_.bits_per_second() + 500) / 1000;
    172 }
    173 
    174 // Go through a fixed time window of most recent packets received and
    175 // counts packets missing to obtain the packet loss ratio. If an unordered
    176 // packet falls out of the timewindow it will be counted as missing.
    177 // E.g.: for a timewindow covering 5 packets of the following arrival sequence
    178 // {10 7 9 5 6} 8 3 2 4 1, the output will be 1/6 (#8 is considered as missing).
    179 float BweReceiver::RecentPacketLossRatio() {
    180   if (received_packets_.empty()) {
    181     return 0.0f;
    182   }
    183   int number_packets_received = 0;
    184 
    185   PacketNodeIt node_it = received_packets_.begin();  // Latest.
    186 
    187   // Lowest timestamp limit, oldest one that should be checked.
    188   int64_t time_limit_ms = (*node_it)->arrival_time_ms - kPacketLossTimeWindowMs;
    189   // Oldest and newest values found within the given time window.
    190   uint16_t oldest_seq_num = (*node_it)->sequence_number;
    191   uint16_t newest_seq_num = oldest_seq_num;
    192 
    193   while (node_it != received_packets_.end()) {
    194     if ((*node_it)->arrival_time_ms < time_limit_ms) {
    195       break;
    196     }
    197     uint16_t seq_num = (*node_it)->sequence_number;
    198     if (IsNewerSequenceNumber(seq_num, newest_seq_num)) {
    199       newest_seq_num = seq_num;
    200     }
    201     if (IsNewerSequenceNumber(oldest_seq_num, seq_num)) {
    202       oldest_seq_num = seq_num;
    203     }
    204     ++node_it;
    205     ++number_packets_received;
    206   }
    207   // Interval width between oldest and newest sequence number.
    208   // There was an overflow if newest_seq_num < oldest_seq_num.
    209   int gap = static_cast<uint16_t>(newest_seq_num - oldest_seq_num + 1);
    210 
    211   return static_cast<float>(gap - number_packets_received) / gap;
    212 }
    213 
    214 LinkedSet::~LinkedSet() {
    215   while (!empty())
    216     RemoveTail();
    217 }
    218 
    219 void LinkedSet::Insert(uint16_t sequence_number,
    220                        int64_t send_time_ms,
    221                        int64_t arrival_time_ms,
    222                        size_t payload_size) {
    223   auto it = map_.find(sequence_number);
    224   if (it != map_.end()) {
    225     PacketNodeIt node_it = it->second;
    226     PacketIdentifierNode* node = *node_it;
    227     node->arrival_time_ms = arrival_time_ms;
    228     if (node_it != list_.begin()) {
    229       list_.erase(node_it);
    230       list_.push_front(node);
    231       map_[sequence_number] = list_.begin();
    232     }
    233   } else {
    234     if (size() == capacity_) {
    235       RemoveTail();
    236     }
    237     UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms,
    238                                         arrival_time_ms, payload_size));
    239   }
    240 }
    241 
    242 void LinkedSet::Insert(PacketIdentifierNode packet_identifier) {
    243   Insert(packet_identifier.sequence_number, packet_identifier.send_time_ms,
    244          packet_identifier.arrival_time_ms, packet_identifier.payload_size);
    245 }
    246 
    247 void LinkedSet::RemoveTail() {
    248   map_.erase(list_.back()->sequence_number);
    249   delete list_.back();
    250   list_.pop_back();
    251 }
    252 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) {
    253   list_.push_front(new_head);
    254   map_[new_head->sequence_number] = list_.begin();
    255 }
    256 
    257 void LinkedSet::Erase(PacketNodeIt node_it) {
    258   map_.erase((*node_it)->sequence_number);
    259   delete (*node_it);
    260   list_.erase(node_it);
    261 }
    262 
    263 void LossAccount::Add(LossAccount rhs) {
    264   num_total += rhs.num_total;
    265   num_lost += rhs.num_lost;
    266 }
    267 void LossAccount::Subtract(LossAccount rhs) {
    268   num_total -= rhs.num_total;
    269   num_lost -= rhs.num_lost;
    270 }
    271 
    272 float LossAccount::LossRatio() {
    273   if (num_total == 0)
    274     return 0.0f;
    275   return static_cast<float>(num_lost) / num_total;
    276 }
    277 
    278 }  // namespace bwe
    279 }  // namespace testing
    280 }  // namespace webrtc
    281