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