Home | History | Annotate | Download | only in congestion_control 
      1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "net/quic/congestion_control/channel_estimator.h"
      6 
      7 // To get information about bandwidth, our send rate for a pair of packets must
      8 // be much faster (ideally back to back) than the receive rate. In that
      9 // scenario, the arriving packet pair will tend to arrive at the max bandwidth
     10 // of the channel. Said another way, when our inter-departure time is a small
     11 // fraction of the inter-arrival time for the same pair of packets, then we can
     12 // get an estimate of bandwidth from that interarrival time. The following
     13 // constant is the threshold ratio for deriving bandwidth information.
     14 static const int kInterarrivalRatioThresholdForBandwidthEstimation = 5;
     15 static const size_t kMinNumberOfSamples = 10;
     16 static const size_t kMaxNumberOfSamples = 100;
     17 
     18 namespace net {
     19 
     20 ChannelEstimator::ChannelEstimator()
     21     : last_sequence_number_(0),
     22       last_send_time_(QuicTime::Zero()),
     23       last_receive_time_(QuicTime::Zero()),
     24       sorted_bitrate_estimates_(kMaxNumberOfSamples) {
     25 }
     26 
     27 ChannelEstimator::~ChannelEstimator() {
     28 }
     29 
     30 void ChannelEstimator::OnAcknowledgedPacket(
     31     QuicPacketSequenceNumber sequence_number,
     32     QuicByteCount packet_size,
     33     QuicTime send_time,
     34     QuicTime receive_time) {
     35   if (last_sequence_number_ > sequence_number) {
     36     // Old packet. The sequence_number use the full 64 bits even though it's
     37     // less on the wire.
     38     return;
     39   }
     40   if (last_sequence_number_ != sequence_number - 1) {
     41     DLOG(INFO) << "Skip channel estimator due to lost packet(s)";
     42   } else if (last_send_time_.IsInitialized()) {
     43     QuicTime::Delta sent_delta = send_time.Subtract(last_send_time_);
     44     QuicTime::Delta received_delta = receive_time.Subtract(last_receive_time_);
     45     if (received_delta.ToMicroseconds() >
     46         kInterarrivalRatioThresholdForBandwidthEstimation *
     47             sent_delta.ToMicroseconds()) {
     48       UpdateFilter(received_delta, packet_size, sequence_number);
     49     }
     50   }
     51   last_sequence_number_ = sequence_number;
     52   last_send_time_ = send_time;
     53   last_receive_time_ = receive_time;
     54 }
     55 
     56 ChannelEstimateState ChannelEstimator::GetChannelEstimate(
     57     QuicBandwidth* estimate) const {
     58   if (sorted_bitrate_estimates_.Size() < kMinNumberOfSamples) {
     59     // Not enough data to make an estimate.
     60     return kChannelEstimateUnknown;
     61   }
     62   // Our data is stored in a sorted map, we need to iterate through our map to
     63   // find the estimated bitrates at our targeted percentiles.
     64 
     65   // Calculate 25th percentile.
     66   size_t beginning_window = sorted_bitrate_estimates_.Size() / 4;
     67   // Calculate 50th percentile.
     68   size_t median = sorted_bitrate_estimates_.Size() / 2;
     69   // Calculate 75th percentile.
     70   size_t end_window = sorted_bitrate_estimates_.Size() - beginning_window;
     71 
     72   QuicBandwidth bitrate_25th_percentile = QuicBandwidth::Zero();
     73   QuicBandwidth median_bitrate = QuicBandwidth::Zero();
     74   QuicBandwidth bitrate_75th_percentile = QuicBandwidth::Zero();
     75   QuicMaxSizedMap<QuicBandwidth, QuicPacketSequenceNumber>::ConstIterator it =
     76       sorted_bitrate_estimates_.Begin();
     77 
     78   for (size_t i = 0; i <= end_window; ++i, ++it) {
     79     DCHECK(it != sorted_bitrate_estimates_.End());
     80     if (i == beginning_window) {
     81       bitrate_25th_percentile = it->first;
     82     }
     83     if (i == median) {
     84       median_bitrate = it->first;
     85     }
     86     if (i == end_window) {
     87       bitrate_75th_percentile = it->first;
     88     }
     89   }
     90   *estimate = median_bitrate;
     91   DLOG(INFO) << "Channel estimate is:"
     92              << median_bitrate.ToKBitsPerSecond() << " Kbit/s";
     93   // If the bitrates in our 25th to 75th percentile window varies more than
     94   // 25% of the median bitrate we consider the estimate to be uncertain.
     95   if (bitrate_75th_percentile.Subtract(bitrate_25th_percentile) >
     96       median_bitrate.Scale(0.25f)) {
     97     return kChannelEstimateUncertain;
     98   }
     99   return kChannelEstimateGood;
    100 }
    101 
    102 void ChannelEstimator::UpdateFilter(QuicTime::Delta received_delta,
    103                                     QuicByteCount size_delta,
    104                                     QuicPacketSequenceNumber sequence_number) {
    105   QuicBandwidth estimate =
    106       QuicBandwidth::FromBytesAndTimeDelta(size_delta, received_delta);
    107   sorted_bitrate_estimates_.Insert(estimate, sequence_number);
    108 }
    109 
    110 }  // namespace net
    111