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/inter_arrival_sender.h"
      6 
      7 namespace net {
      8 
      9 namespace {
     10 const int64 kProbeBitrateKBytesPerSecond = 1200;  // 9.6 Mbit/s
     11 const float kPacketLossBitrateReduction = 0.7f;
     12 const float kUncertainSafetyMargin = 0.7f;
     13 const float kMaxBitrateReduction = 0.9f;
     14 const float kMinBitrateReduction = 0.05f;
     15 const uint64 kMinBitrateKbit = 10;
     16 const int kInitialRttMs = 60;  // At a typical RTT 60 ms.
     17 const float kAlpha = 0.125f;
     18 const float kOneMinusAlpha = 1 - kAlpha;
     19 
     20 static const int kBitrateSmoothingPeriodMs = 1000;
     21 static const int kMinBitrateSmoothingPeriodMs = 500;
     22 
     23 }  // namespace
     24 
     25 InterArrivalSender::InterArrivalSender(const QuicClock* clock)
     26     : probing_(true),
     27       max_segment_size_(kDefaultMaxPacketSize),
     28       current_bandwidth_(QuicBandwidth::Zero()),
     29       smoothed_rtt_(QuicTime::Delta::Zero()),
     30       channel_estimator_(new ChannelEstimator()),
     31       bitrate_ramp_up_(new InterArrivalBitrateRampUp(clock)),
     32       overuse_detector_(new InterArrivalOveruseDetector()),
     33       probe_(new InterArrivalProbe(max_segment_size_)),
     34       state_machine_(new InterArrivalStateMachine(clock)),
     35       paced_sender_(new PacedSender(QuicBandwidth::FromKBytesPerSecond(
     36           kProbeBitrateKBytesPerSecond), max_segment_size_)),
     37       accumulated_number_of_lost_packets_(0),
     38       bandwidth_usage_state_(kBandwidthSteady),
     39       back_down_time_(QuicTime::Zero()),
     40       back_down_bandwidth_(QuicBandwidth::Zero()),
     41       back_down_congestion_delay_(QuicTime::Delta::Zero()) {
     42 }
     43 
     44 InterArrivalSender::~InterArrivalSender() {
     45 }
     46 
     47 void InterArrivalSender::SetFromConfig(const QuicConfig& config,
     48                                        bool is_server) {
     49 }
     50 
     51 void InterArrivalSender::SetMaxPacketSize(QuicByteCount max_packet_size) {
     52   max_segment_size_ = max_packet_size;
     53   paced_sender_->set_max_segment_size(max_segment_size_);
     54   probe_->set_max_segment_size(max_segment_size_);
     55 }
     56 
     57 // TODO(pwestin): this is really inefficient (4% CPU on the GFE loadtest).
     58 // static
     59 QuicBandwidth InterArrivalSender::CalculateSentBandwidth(
     60     const SendAlgorithmInterface::SentPacketsMap& sent_packets_map,
     61     QuicTime feedback_receive_time) {
     62   const QuicTime::Delta kBitrateSmoothingPeriod =
     63       QuicTime::Delta::FromMilliseconds(kBitrateSmoothingPeriodMs);
     64   const QuicTime::Delta kMinBitrateSmoothingPeriod =
     65       QuicTime::Delta::FromMilliseconds(kMinBitrateSmoothingPeriodMs);
     66 
     67   QuicByteCount sum_bytes_sent = 0;
     68 
     69   // Sum packet from new until they are kBitrateSmoothingPeriod old.
     70   SendAlgorithmInterface::SentPacketsMap::const_reverse_iterator history_rit =
     71       sent_packets_map.rbegin();
     72 
     73   QuicTime::Delta max_diff = QuicTime::Delta::Zero();
     74   for (; history_rit != sent_packets_map.rend(); ++history_rit) {
     75     QuicTime::Delta diff =
     76         feedback_receive_time.Subtract(history_rit->second->send_timestamp());
     77     if (diff > kBitrateSmoothingPeriod) {
     78       break;
     79     }
     80     sum_bytes_sent += history_rit->second->bytes_sent();
     81     max_diff = diff;
     82   }
     83   if (max_diff < kMinBitrateSmoothingPeriod) {
     84     // No estimate.
     85     return QuicBandwidth::Zero();
     86   }
     87   return QuicBandwidth::FromBytesAndTimeDelta(sum_bytes_sent, max_diff);
     88 }
     89 
     90 void InterArrivalSender::OnIncomingQuicCongestionFeedbackFrame(
     91     const QuicCongestionFeedbackFrame& feedback,
     92     QuicTime feedback_receive_time,
     93     const SentPacketsMap& sent_packets) {
     94   DCHECK(feedback.type == kInterArrival);
     95 
     96   if (feedback.type != kInterArrival) {
     97     return;
     98   }
     99 
    100   QuicBandwidth sent_bandwidth = CalculateSentBandwidth(sent_packets,
    101                                                         feedback_receive_time);
    102 
    103   TimeMap::const_iterator received_it;
    104   for (received_it = feedback.inter_arrival.received_packet_times.begin();
    105       received_it != feedback.inter_arrival.received_packet_times.end();
    106       ++received_it) {
    107     QuicPacketSequenceNumber sequence_number = received_it->first;
    108 
    109     SentPacketsMap::const_iterator sent_it = sent_packets.find(sequence_number);
    110     if (sent_it == sent_packets.end()) {
    111       // Too old data; ignore and move forward.
    112       DVLOG(1) << "Too old feedback move forward, sequence_number:"
    113                  << sequence_number;
    114       continue;
    115     }
    116     QuicTime time_received = received_it->second;
    117     QuicTime time_sent = sent_it->second->send_timestamp();
    118     QuicByteCount bytes_sent = sent_it->second->bytes_sent();
    119 
    120     channel_estimator_->OnAcknowledgedPacket(
    121         sequence_number, bytes_sent, time_sent, time_received);
    122     if (probing_) {
    123       probe_->OnIncomingFeedback(
    124           sequence_number, bytes_sent, time_sent, time_received);
    125     } else {
    126       bool last_of_send_time = false;
    127       SentPacketsMap::const_iterator next_sent_it = ++sent_it;
    128       if (next_sent_it == sent_packets.end()) {
    129         // No more sent packets; hence this must be the last.
    130         last_of_send_time = true;
    131       } else {
    132         if (time_sent != next_sent_it->second->send_timestamp()) {
    133           // Next sent packet have a different send time.
    134           last_of_send_time = true;
    135         }
    136       }
    137       overuse_detector_->OnAcknowledgedPacket(
    138           sequence_number, time_sent, last_of_send_time, time_received);
    139     }
    140   }
    141   if (probing_) {
    142     probing_ = ProbingPhase(feedback_receive_time);
    143     return;
    144   }
    145 
    146   bool packet_loss_event = false;
    147   if (accumulated_number_of_lost_packets_ !=
    148       feedback.inter_arrival.accumulated_number_of_lost_packets) {
    149     accumulated_number_of_lost_packets_ =
    150         feedback.inter_arrival.accumulated_number_of_lost_packets;
    151     packet_loss_event = true;
    152   }
    153   InterArrivalState state = state_machine_->GetInterArrivalState();
    154 
    155   if (state == kInterArrivalStatePacketLoss ||
    156       state == kInterArrivalStateCompetingTcpFLow) {
    157     if (packet_loss_event) {
    158       if (!state_machine_->PacketLossEvent()) {
    159         // Less than one RTT since last PacketLossEvent.
    160         return;
    161       }
    162       EstimateBandwidthAfterLossEvent(feedback_receive_time);
    163     } else {
    164       EstimateNewBandwidth(feedback_receive_time, sent_bandwidth);
    165     }
    166     return;
    167   }
    168   EstimateDelayBandwidth(feedback_receive_time, sent_bandwidth);
    169 }
    170 
    171 bool InterArrivalSender::ProbingPhase(QuicTime feedback_receive_time) {
    172   QuicBandwidth available_channel_estimate = QuicBandwidth::Zero();
    173   if (!probe_->GetEstimate(&available_channel_estimate)) {
    174     // Continue probing phase.
    175     return true;
    176   }
    177   QuicBandwidth channel_estimate = QuicBandwidth::Zero();
    178   ChannelEstimateState channel_estimator_state =
    179       channel_estimator_->GetChannelEstimate(&channel_estimate);
    180 
    181   QuicBandwidth new_rate =
    182       available_channel_estimate.Scale(kUncertainSafetyMargin);
    183 
    184   switch (channel_estimator_state) {
    185     case kChannelEstimateUnknown:
    186       channel_estimate = available_channel_estimate;
    187       break;
    188     case kChannelEstimateUncertain:
    189       channel_estimate = channel_estimate.Scale(kUncertainSafetyMargin);
    190       break;
    191     case kChannelEstimateGood:
    192       // Do nothing.
    193       break;
    194   }
    195   new_rate = std::max(new_rate,
    196                        QuicBandwidth::FromKBitsPerSecond(kMinBitrateKbit));
    197 
    198   bitrate_ramp_up_->Reset(new_rate, available_channel_estimate,
    199                           channel_estimate);
    200 
    201   current_bandwidth_ = new_rate;
    202   paced_sender_->UpdateBandwidthEstimate(feedback_receive_time, new_rate);
    203   DVLOG(1) << "Probe result; new rate:"
    204              << new_rate.ToKBitsPerSecond() << " Kbits/s "
    205              << " available estimate:"
    206              << available_channel_estimate.ToKBitsPerSecond() << " Kbits/s "
    207              << " channel estimate:"
    208              << channel_estimate.ToKBitsPerSecond() << " Kbits/s ";
    209   return false;
    210 }
    211 
    212 void InterArrivalSender::OnPacketAcked(
    213     QuicPacketSequenceNumber /*acked_sequence_number*/,
    214     QuicByteCount acked_bytes,
    215     QuicTime::Delta rtt) {
    216   // RTT can't be negative.
    217   DCHECK_LE(0, rtt.ToMicroseconds());
    218 
    219   if (probing_) {
    220     probe_->OnAcknowledgedPacket(acked_bytes);
    221   }
    222 
    223   if (rtt.IsInfinite()) {
    224     return;
    225   }
    226 
    227   if (smoothed_rtt_.IsZero()) {
    228     smoothed_rtt_ = rtt;
    229   } else {
    230     smoothed_rtt_ = QuicTime::Delta::FromMicroseconds(
    231         kOneMinusAlpha * smoothed_rtt_.ToMicroseconds() +
    232         kAlpha * rtt.ToMicroseconds());
    233   }
    234   state_machine_->set_rtt(smoothed_rtt_);
    235 }
    236 
    237 void InterArrivalSender::OnPacketLost(
    238     QuicPacketSequenceNumber /*sequence_number*/,
    239     QuicTime ack_receive_time) {
    240   // Packet loss was reported.
    241   if (!probing_) {
    242     if (!state_machine_->PacketLossEvent()) {
    243       // Less than one RTT since last PacketLossEvent.
    244       return;
    245     }
    246     // Calculate new pace rate.
    247     EstimateBandwidthAfterLossEvent(ack_receive_time);
    248   }
    249 }
    250 
    251 bool InterArrivalSender::OnPacketSent(
    252     QuicTime sent_time,
    253     QuicPacketSequenceNumber sequence_number,
    254     QuicByteCount bytes,
    255     TransmissionType /*transmission_type*/,
    256     HasRetransmittableData /*has_retransmittable_data*/) {
    257   if (probing_) {
    258     probe_->OnPacketSent(bytes);
    259   }
    260   paced_sender_->OnPacketSent(sent_time, bytes);
    261   return true;
    262 }
    263 
    264 void InterArrivalSender::OnRetransmissionTimeout() {
    265   // TODO(ianswett): Decrease the available bandwidth.
    266 }
    267 
    268 void InterArrivalSender::OnPacketAbandoned(
    269     QuicPacketSequenceNumber /*sequence_number*/,
    270     QuicByteCount abandoned_bytes) {
    271   // TODO(pwestin): use for out outer_congestion_window_ logic.
    272   if (probing_) {
    273     probe_->OnAcknowledgedPacket(abandoned_bytes);
    274   }
    275 }
    276 
    277 QuicTime::Delta InterArrivalSender::TimeUntilSend(
    278     QuicTime now,
    279     TransmissionType /*transmission_type*/,
    280     HasRetransmittableData has_retransmittable_data,
    281     IsHandshake /*handshake*/) {
    282   // TODO(pwestin): implement outer_congestion_window_ logic.
    283   QuicTime::Delta outer_window = QuicTime::Delta::Zero();
    284 
    285   if (probing_) {
    286     if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA &&
    287         probe_->GetAvailableCongestionWindow() == 0) {
    288       outer_window = QuicTime::Delta::Infinite();
    289     }
    290   }
    291   return paced_sender_->TimeUntilSend(now, outer_window);
    292 }
    293 
    294 void InterArrivalSender::EstimateDelayBandwidth(QuicTime feedback_receive_time,
    295                                                 QuicBandwidth sent_bandwidth) {
    296   QuicTime::Delta estimated_congestion_delay = QuicTime::Delta::Zero();
    297   BandwidthUsage new_bandwidth_usage_state =
    298       overuse_detector_->GetState(&estimated_congestion_delay);
    299 
    300   switch (new_bandwidth_usage_state) {
    301     case kBandwidthDraining:
    302     case kBandwidthUnderUsing:
    303       // Hold our current bitrate.
    304       break;
    305     case kBandwidthOverUsing:
    306       if (!state_machine_->IncreasingDelayEvent()) {
    307         // Less than one RTT since last IncreasingDelayEvent.
    308         return;
    309       }
    310       EstimateBandwidthAfterDelayEvent(feedback_receive_time,
    311                                        estimated_congestion_delay);
    312       break;
    313     case kBandwidthSteady:
    314       // Calculate new pace rate.
    315       if (bandwidth_usage_state_ == kBandwidthDraining ||
    316           bandwidth_usage_state_ == kBandwidthOverUsing) {
    317         EstimateNewBandwidthAfterDraining(feedback_receive_time,
    318                                           estimated_congestion_delay);
    319       } else {
    320         EstimateNewBandwidth(feedback_receive_time, sent_bandwidth);
    321       }
    322       break;
    323   }
    324   bandwidth_usage_state_ = new_bandwidth_usage_state;
    325 }
    326 
    327 QuicBandwidth InterArrivalSender::BandwidthEstimate() const {
    328   return current_bandwidth_;
    329 }
    330 
    331 QuicTime::Delta InterArrivalSender::SmoothedRtt() const {
    332   if (smoothed_rtt_.IsZero()) {
    333     return QuicTime::Delta::FromMilliseconds(kInitialRttMs);
    334   }
    335   return smoothed_rtt_;
    336 }
    337 
    338 QuicTime::Delta InterArrivalSender::RetransmissionDelay() const {
    339   // TODO(pwestin): Calculate and return retransmission delay.
    340   // Use 2 * the smoothed RTT for now.
    341   return smoothed_rtt_.Add(smoothed_rtt_);
    342 }
    343 
    344 QuicByteCount InterArrivalSender::GetCongestionWindow() const {
    345   return 0;
    346 }
    347 
    348 void InterArrivalSender::EstimateNewBandwidth(QuicTime feedback_receive_time,
    349                                               QuicBandwidth sent_bandwidth) {
    350   QuicBandwidth new_bandwidth = bitrate_ramp_up_->GetNewBitrate(sent_bandwidth);
    351   if (current_bandwidth_ == new_bandwidth) {
    352     return;
    353   }
    354   current_bandwidth_ = new_bandwidth;
    355   state_machine_->IncreaseBitrateDecision();
    356 
    357   QuicBandwidth channel_estimate = QuicBandwidth::Zero();
    358   ChannelEstimateState channel_estimator_state =
    359       channel_estimator_->GetChannelEstimate(&channel_estimate);
    360 
    361   if (channel_estimator_state == kChannelEstimateGood) {
    362     bitrate_ramp_up_->UpdateChannelEstimate(channel_estimate);
    363   }
    364   paced_sender_->UpdateBandwidthEstimate(feedback_receive_time,
    365                                          current_bandwidth_);
    366   DVLOG(1) << "New bandwidth estimate in steady state:"
    367              << current_bandwidth_.ToKBitsPerSecond()
    368              << " Kbits/s";
    369 }
    370 
    371 // Did we drain the network buffers in our expected pace?
    372 void InterArrivalSender::EstimateNewBandwidthAfterDraining(
    373     QuicTime feedback_receive_time,
    374     QuicTime::Delta estimated_congestion_delay) {
    375   if (current_bandwidth_ > back_down_bandwidth_) {
    376     // Do nothing, our current bandwidth is higher than our bandwidth at the
    377     // previous back down.
    378     DVLOG(1) << "Current bandwidth estimate is higher than before draining";
    379     return;
    380   }
    381   if (estimated_congestion_delay >= back_down_congestion_delay_) {
    382     // Do nothing, our estimated delay have increased.
    383     DVLOG(1) << "Current delay estimate is higher than before draining";
    384     return;
    385   }
    386   DCHECK(back_down_time_.IsInitialized());
    387   QuicTime::Delta buffer_reduction =
    388       back_down_congestion_delay_.Subtract(estimated_congestion_delay);
    389   QuicTime::Delta elapsed_time =
    390       feedback_receive_time.Subtract(back_down_time_).Subtract(SmoothedRtt());
    391 
    392   QuicBandwidth new_estimate = QuicBandwidth::Zero();
    393   if (buffer_reduction >= elapsed_time) {
    394     // We have drained more than the elapsed time... go back to our old rate.
    395     new_estimate = back_down_bandwidth_;
    396   } else {
    397     float fraction_of_rate =
    398         static_cast<float>(buffer_reduction.ToMicroseconds()) /
    399             elapsed_time.ToMicroseconds();  // < 1.0
    400 
    401     QuicBandwidth draining_rate = back_down_bandwidth_.Scale(fraction_of_rate);
    402     QuicBandwidth max_estimated_draining_rate =
    403         back_down_bandwidth_.Subtract(current_bandwidth_);
    404     if (draining_rate > max_estimated_draining_rate) {
    405       // We drained faster than our old send rate, go back to our old rate.
    406       new_estimate = back_down_bandwidth_;
    407     } else {
    408       // Use our drain rate and our kMinBitrateReduction to go to our
    409       // new estimate.
    410       new_estimate = std::max(current_bandwidth_,
    411                               current_bandwidth_.Add(draining_rate).Scale(
    412                                   1.0f - kMinBitrateReduction));
    413       DVLOG(1) << "Draining calculation; current rate:"
    414                  << current_bandwidth_.ToKBitsPerSecond() << " Kbits/s "
    415                  << "draining rate:"
    416                  << draining_rate.ToKBitsPerSecond() << " Kbits/s "
    417                  << "new estimate:"
    418                  << new_estimate.ToKBitsPerSecond() << " Kbits/s "
    419                  << " buffer reduction:"
    420                  << buffer_reduction.ToMicroseconds() << " us "
    421                  << " elapsed time:"
    422                  << elapsed_time.ToMicroseconds()  << " us ";
    423     }
    424   }
    425   if (new_estimate == current_bandwidth_) {
    426     return;
    427   }
    428 
    429   QuicBandwidth channel_estimate = QuicBandwidth::Zero();
    430   ChannelEstimateState channel_estimator_state =
    431       channel_estimator_->GetChannelEstimate(&channel_estimate);
    432 
    433   // TODO(pwestin): we need to analyze channel_estimate too.
    434   switch (channel_estimator_state) {
    435     case kChannelEstimateUnknown:
    436       channel_estimate = current_bandwidth_;
    437       break;
    438     case kChannelEstimateUncertain:
    439       channel_estimate = channel_estimate.Scale(kUncertainSafetyMargin);
    440       break;
    441     case kChannelEstimateGood:
    442       // Do nothing, estimate is accurate.
    443       break;
    444   }
    445   bitrate_ramp_up_->Reset(new_estimate, back_down_bandwidth_, channel_estimate);
    446   state_machine_->IncreaseBitrateDecision();
    447   paced_sender_->UpdateBandwidthEstimate(feedback_receive_time, new_estimate);
    448   current_bandwidth_ = new_estimate;
    449   DVLOG(1) << "New bandwidth estimate after draining:"
    450              << new_estimate.ToKBitsPerSecond() << " Kbits/s";
    451 }
    452 
    453 void InterArrivalSender::EstimateBandwidthAfterDelayEvent(
    454     QuicTime feedback_receive_time,
    455     QuicTime::Delta estimated_congestion_delay) {
    456   QuicByteCount estimated_byte_buildup =
    457       current_bandwidth_.ToBytesPerPeriod(estimated_congestion_delay);
    458 
    459   // To drain all build up buffer within one RTT we need to reduce the
    460   // bitrate with the following.
    461   // TODO(pwestin): this is a crude first implementation.
    462   int64 draining_rate_per_rtt = (estimated_byte_buildup *
    463       kNumMicrosPerSecond) / SmoothedRtt().ToMicroseconds();
    464 
    465   float decrease_factor =
    466       draining_rate_per_rtt / current_bandwidth_.ToBytesPerSecond();
    467 
    468   decrease_factor = std::max(decrease_factor, kMinBitrateReduction);
    469   decrease_factor = std::min(decrease_factor, kMaxBitrateReduction);
    470   back_down_congestion_delay_ = estimated_congestion_delay;
    471   QuicBandwidth new_target_bitrate =
    472       current_bandwidth_.Scale(1.0f - decrease_factor);
    473 
    474   // While in delay sensing mode send at least one packet per RTT.
    475   QuicBandwidth min_delay_bitrate =
    476       QuicBandwidth::FromBytesAndTimeDelta(max_segment_size_, SmoothedRtt());
    477   new_target_bitrate = std::max(new_target_bitrate, min_delay_bitrate);
    478 
    479   ResetCurrentBandwidth(feedback_receive_time, new_target_bitrate);
    480 
    481   DVLOG(1) << "New bandwidth estimate after delay event:"
    482       << current_bandwidth_.ToKBitsPerSecond()
    483       << " Kbits/s min delay bitrate:"
    484       << min_delay_bitrate.ToKBitsPerSecond()
    485       << " Kbits/s RTT:"
    486       << SmoothedRtt().ToMicroseconds()
    487       << " us";
    488 }
    489 
    490 void InterArrivalSender::EstimateBandwidthAfterLossEvent(
    491     QuicTime feedback_receive_time) {
    492   ResetCurrentBandwidth(feedback_receive_time,
    493                         current_bandwidth_.Scale(kPacketLossBitrateReduction));
    494   DVLOG(1) << "New bandwidth estimate after loss event:"
    495              << current_bandwidth_.ToKBitsPerSecond()
    496              << " Kbits/s";
    497 }
    498 
    499 void InterArrivalSender::ResetCurrentBandwidth(QuicTime feedback_receive_time,
    500                                                QuicBandwidth new_rate) {
    501   new_rate = std::max(new_rate,
    502                       QuicBandwidth::FromKBitsPerSecond(kMinBitrateKbit));
    503   QuicBandwidth channel_estimate = QuicBandwidth::Zero();
    504   ChannelEstimateState channel_estimator_state =
    505       channel_estimator_->GetChannelEstimate(&channel_estimate);
    506 
    507   switch (channel_estimator_state) {
    508     case kChannelEstimateUnknown:
    509       channel_estimate = current_bandwidth_;
    510       break;
    511     case kChannelEstimateUncertain:
    512       channel_estimate = channel_estimate.Scale(kUncertainSafetyMargin);
    513       break;
    514     case kChannelEstimateGood:
    515       // Do nothing.
    516       break;
    517   }
    518   back_down_time_ = feedback_receive_time;
    519   back_down_bandwidth_ = current_bandwidth_;
    520   bitrate_ramp_up_->Reset(new_rate, current_bandwidth_, channel_estimate);
    521   if (new_rate != current_bandwidth_) {
    522     current_bandwidth_ = new_rate;
    523     paced_sender_->UpdateBandwidthEstimate(feedback_receive_time,
    524                                            current_bandwidth_);
    525     state_machine_->DecreaseBitrateDecision();
    526   }
    527 }
    528 
    529 }  // namespace net
    530