More Simulation Framework features

webrtc/modules/remote_bitrate_estimator/test/bwe.cc

 /*
  *  Copyright (c) 2015 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.
  */
 
@@ skipping 11 matching lines @@
 namespace testing {
 namespace bwe {
 
 // With the assumption that packet loss is lower than 97%, the max gap
 // between elements in the set is lower than 0x8000, hence we have a
 // total order in the set. For (x,y,z) subset of the LinkedSet,
 // (x<=y and y<=z) ==> x<=z so the set can be sorted.
 const int kSetCapacity = 1000;
 
 BweReceiver::BweReceiver(int flow_id)
-    : flow_id_(flow_id), received_packets_(kSetCapacity) {
+    : flow_id_(flow_id), received_packets_(kSetCapacity), loss_account() {
+}
+
+void BweSender::Pause() {
+  running_ = false;
+  bitrate_kbps_ = 0;

[stefan-webrtc, 2015/07/02 11:03:41]

I'm not sure this is the right way to handle a Pause. Has that been defined in
some ietf doc? I would like to keep the bitrate_kbps_ as is.

[magalhaesc, 2015/07/02 17:06:18]

Makes sense, it was set to zero since previously we were plotting sending
estimate.
The bitrate will remain unchanged and it will be handled before plotting

plot_kbps = 0
if (running)
   plot_kbps = bitrate_kbps

+}
+
+void BweSender::Resume() {
+  running_ = true;
+  bitrate_kbps_ = kMinBitrateKbps;
 }
 
 class NullBweSender : public BweSender {
  public:
   NullBweSender() {}
   virtual ~NullBweSender() {}
 
   int GetFeedbackIntervalMs() const override { return 1000; }
   void GiveFeedback(const FeedbackPacket& feedback) override {}
   void OnPacketsSent(const Packets& packets) override {}
@@ skipping 47 matching lines @@
       return new NadaBweReceiver(flow_id);
     case kTcpEstimator:
       return new TcpBweReceiver(flow_id);
     case kNullEstimator:
       return new BweReceiver(flow_id);
   }
   assert(false);
   return NULL;
 }
 
-float BweReceiver::GlobalPacketLossRatio() {
+// Take into account all LinkedSet content.
+void BweReceiver::UpdateLoss() {
+  loss_account.Add(LinkedSetPacketLossRatio());
+}
+
+void BweReceiver::ClearSet() {
+  received_packets_.Clear();
+}
+
+// Preserve 10% latest packets and update packet loss based on the oldest
+// 90%, that will be removed.
+void BweReceiver::RelieveSetAndUpdateLoss() {
+  // Compute Loss for the whole LinkedSet and updates loss_account_.
+  UpdateLoss();
+
+  std::vector<PacketIdentifierNode> buffer;
+  size_t num_preserved_elements = received_packets_.size() / 10;
+
+  PacketNodeIt node_it = received_packets_.begin();  // Latest.
+  while (node_it != received_packets_.end() && num_preserved_elements-- > 0) {
+    buffer.push_back((*node_it)->copy());

[stefan-webrtc, 2015/07/02 11:03:41]

Just do buffer.push_back(*node_it). In fact, I think you can do this even
simpler:
buffer.insert(buffer.begin(), received_packets_.begin(),
received_packets_.begin() + num_preserved_elements);

Or why not do:
received_packets_.erase(received_packets_.begin() + num_preserved_elements,
received_packets_.end());
that way you don't even need to have a temporary buffer.

[magalhaesc, 2015/07/02 17:06:17]

received_packets contains a list and a map, both have to be erased. So I should
iterate through the list to also clean elements from the map (they're not
necessarily sorted in the same order). 

+    ++node_it;
+  }
+
+  ClearSet();
+
+  // Reverse iteration to optimize insertion.
+  for (auto rit = buffer.rbegin(); rit != buffer.rend(); ++rit) {
+    received_packets_.Insert(*rit);
+  }
+
+  // Compute Loss for the preserved elements
+  loss_account.Subtract(LinkedSetPacketLossRatio());
+}
+
+float BweReceiver::GlobalReceiverPacketLossRatio() {
+  UpdateLoss();
+  return loss_account.LossRatio();
+}
+
+// This function considers at most kSetCapacity = 1000 packets.
+LossAccount BweReceiver::LinkedSetPacketLossRatio() {
   if (received_packets_.empty()) {
-    return 0.0f;
+    return LossAccount();
   }
-  // Possibly there are packets missing.
-  const uint16_t kMaxGap = 1.5 * kSetCapacity;
-  uint16_t min = received_packets_.find_min();
-  uint16_t max = received_packets_.find_max();
+
+  uint16_t oldest_seq_nb = received_packets_.OldestSeqNumber();
+  uint16_t newest_seq_nb = received_packets_.NewestSeqNumber();

[stefan-webrtc, 2015/07/02 11:03:41]

nb -> num, it better matches other code in webrtc.

[magalhaesc, 2015/07/02 17:06:17]

Done.

 
   int gap;
-  if (max - min < kMaxGap) {
-    gap = max - min + 1;
+  if (newest_seq_nb >= oldest_seq_nb) {
+    gap = newest_seq_nb - oldest_seq_nb + 1;
   } else {  // There was an overflow.
-    max = received_packets_.upper_bound(kMaxGap);
-    min = received_packets_.lower_bound(0xFFFF - kMaxGap);
-    gap = max + (0xFFFF - min) + 2;
+    gap = newest_seq_nb + (0xFFFF - oldest_seq_nb) + 2;
   }

[stefan-webrtc, 2015/07/02 11:03:41]

This code can be replaced with;
gap = static_cast<uint16_t>(newest_seq_nb - oldest_seq_nb + 1);

[magalhaesc, 2015/07/02 17:06:18]

Done.

-  return static_cast<float>(received_packets_.size()) / gap;
+
+  float set_loss_ratio =
+      static_cast<float>(gap - received_packets_.size()) / gap;
+  size_t set_received_packets = received_packets_.size();

[stefan-webrtc, 2015/07/02 11:03:41]

This variable can be defined on line 165 and used in the loss ratio calculation.

[magalhaesc, 2015/07/02 17:06:17]

Done.

+  size_t set_total_packets = set_received_packets / (1.0f - set_loss_ratio);

[stefan-webrtc, 2015/07/02 11:03:41]

This is a bit odd, and I would be worried that you get rounding errors. Isn't it
better to keep a count of the number of packets received? Isn't gap equal to the
number of packets you should have received?

[magalhaesc, 2015/07/02 17:06:18]

Yes, right. Gap is the total number of packets that should have been received.

+  size_t set_lost_packets = set_total_packets - set_received_packets;
+
+  return LossAccount(static_cast<uint32_t>(set_total_packets),
+                     static_cast<uint32_t>(set_lost_packets));

[stefan-webrtc, 2015/07/02 11:03:41]

Why do you have to cast? Change the input types to LossAccount instead maybe?

[magalhaesc, 2015/07/02 17:06:17]

Done.

+}
+
+uint32_t BweReceiver::RecentKbps() {
+  return (rate_counter_.bits_per_second() + 500) / 1000;
 }
 
 // Go through a fixed time window of most recent packets received and
 // counts packets missing to obtain the packet loss ratio. If an unordered
 // packet falls out of the timewindow it will be counted as missing.
 // E.g.: for a timewindow covering 5 packets of the following arrival sequence
 // {10 7 9 5 6} 8 3 2 4 1, the output will be 1/6 (#8 is considered as missing).
 float BweReceiver::RecentPacketLossRatio() {
   if (received_packets_.empty()) {
     return 0.0f;
@@ skipping 44 matching lines @@
       map_[sequence_number] = list_.begin();
     }
   } else {
     if (size() == capacity_) {
       RemoveTail();
     }
     UpdateHead(new PacketIdentifierNode(sequence_number, send_time_ms,
                                         arrival_time_ms, payload_size));
   }
 }
+
+void LinkedSet::Insert(PacketIdentifierNode packet_identifier) {
+  Insert(packet_identifier.sequence_number, packet_identifier.send_time_ms,
+         packet_identifier.arrival_time_ms, packet_identifier.payload_size);
+}
+
 void LinkedSet::RemoveTail() {
   map_.erase(list_.back()->sequence_number);
   list_.pop_back();
 }
 void LinkedSet::UpdateHead(PacketIdentifierNode* new_head) {
   list_.push_front(new_head);
   map_[new_head->sequence_number] = list_.begin();
 }
 
+uint16_t LinkedSet::OldestSeqNumber() {
+  if (IsNewerSequenceNumber(Max(), Min()) || Max() == Min()) {
+    return Min();  // An empty set will return Max = Min = 0.
+  } else {         // There was an overflow.
+    return map_.lower_bound(0x8000)->first;
+  }
+}
+
+uint16_t LinkedSet::NewestSeqNumber() {
+  if (IsNewerSequenceNumber(Max(), Min()) || Max() == Min()) {
+    return Max();  // An empty set will return Max = Min = 0.
+  } else {         // There was an overflow.
+    return (--map_.lower_bound(0x8000))->first;
+  }
+}
+
+PacketIdentifierNode PacketIdentifierNode::copy() {
+  return PacketIdentifierNode(sequence_number, send_time_ms, arrival_time_ms,
+                              payload_size);
+}
+
+void LossAccount::Add(LossAccount addend) {
+  num_total += addend.num_total;
+  num_lost += addend.num_lost;
+}
+void LossAccount::Subtract(LossAccount subtrahend) {
+  num_total -= subtrahend.num_total;
+  num_lost -= subtrahend.num_lost;
+}
+
+float LossAccount::LossRatio() {
+  return static_cast<float>(num_lost) / num_total;
+}
+
 }  // namespace bwe
 }  // namespace testing
 }  // namespace webrtc