12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "net/quic/congestion_control/tcp_cubic_sender.h" 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 74e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)#include <algorithm> 84e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) 98bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)#include "base/metrics/histogram.h" 10a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/quic/congestion_control/rtt_stats.h" 116e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles)#include "net/quic/crypto/crypto_protocol.h" 128bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) 13f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)using std::max; 145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using std::min; 15f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace net { 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace { 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Constants based on TCP defaults. 20f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// The minimum cwnd based on RFC 3782 (TCP NewReno) for cwnd reductions on a 21f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// fast retransmission. The cwnd after a timeout is still 1. 22f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)const QuicTcpCongestionWindow kMinimumCongestionWindow = 2; 231e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles)const QuicByteCount kMaxSegmentSize = kDefaultTCPMSS; 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const int64 kInitialCongestionWindow = 10; 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)const int kMaxBurstLength = 3; 26558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch}; // namespace 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 28ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben MurdochTcpCubicSender::TcpCubicSender( 29ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch const QuicClock* clock, 30a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const RttStats* rtt_stats, 31ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch bool reno, 32a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) QuicTcpCongestionWindow max_tcp_congestion_window, 33a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) QuicConnectionStats* stats) 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : hybrid_slow_start_(clock), 35a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) cubic_(clock, stats), 36a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) rtt_stats_(rtt_stats), 370529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch stats_(stats), 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) reno_(reno), 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) congestion_window_count_(0), 406e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) receive_window_(kDefaultSocketReceiveBuffer), 415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) prr_out_(0), 425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) prr_delivered_(0), 435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ack_count_since_loss_(0), 445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bytes_in_flight_before_loss_(0), 45f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) largest_sent_sequence_number_(0), 46f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) largest_acked_sequence_number_(0), 47f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) largest_sent_at_last_cutback_(0), 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) congestion_window_(kInitialCongestionWindow), 49116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch previous_congestion_window_(0), 50ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch slowstart_threshold_(max_tcp_congestion_window), 51116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch previous_slowstart_threshold_(0), 520529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch last_cutback_exited_slowstart_(false), 53a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) max_tcp_congestion_window_(max_tcp_congestion_window) { 54558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch} 55558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch 56558790d6acca3451cf3a6b497803a5f07d0bec58Ben MurdochTcpCubicSender::~TcpCubicSender() { 578bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles) UMA_HISTOGRAM_COUNTS("Net.QuicSession.FinalTcpCwnd", congestion_window_); 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 600f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles)void TcpCubicSender::SetFromConfig(const QuicConfig& config, bool is_server) { 616e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (is_server) { 626e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (config.HasReceivedConnectionOptions() && 636e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) ContainsQuicTag(config.ReceivedConnectionOptions(), kIW10)) { 646e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Initial window experiment. Ignore the initial congestion 656e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // window suggested by the client and use the default ICWND of 666e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // 10 instead. 676e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) congestion_window_ = kInitialCongestionWindow; 686e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } else if (config.HasReceivedInitialCongestionWindow()) { 696e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Set the initial window size. 706e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) congestion_window_ = min(kMaxInitialWindow, 716e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) config.ReceivedInitialCongestionWindow()); 726e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 736e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 746e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (config.HasReceivedSocketReceiveBuffer()) { 756e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) // Set the initial socket receive buffer size in bytes. 766e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) receive_window_ = config.ReceivedSocketReceiveBuffer(); 770f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) } 780f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles)} 790f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles) 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void TcpCubicSender::OnIncomingQuicCongestionFeedbackFrame( 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const QuicCongestionFeedbackFrame& feedback, 82a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) QuicTime feedback_receive_time) { 836e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) if (feedback.type == kTCP) { 846e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) receive_window_ = feedback.tcp.receive_window; 856e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) } 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 88010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)void TcpCubicSender::OnCongestionEvent( 89010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) bool rtt_updated, 90010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount bytes_in_flight, 911320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const CongestionVector& acked_packets, 921320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci const CongestionVector& lost_packets) { 93010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (rtt_updated && InSlowStart() && 94010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) hybrid_slow_start_.ShouldExitSlowStart(rtt_stats_->latest_rtt(), 95010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) rtt_stats_->min_rtt(), 96010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) congestion_window_)) { 97010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) slowstart_threshold_ = congestion_window_; 98010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) } 991320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (CongestionVector::const_iterator it = lost_packets.begin(); 100010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) it != lost_packets.end(); ++it) { 101010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) OnPacketLost(it->first, bytes_in_flight); 102010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) } 1031320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci for (CongestionVector::const_iterator it = acked_packets.begin(); 104010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) it != acked_packets.end(); ++it) { 105010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) OnPacketAcked(it->first, it->second.bytes_sent, bytes_in_flight); 106010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) } 107010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)} 108010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) 109f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void TcpCubicSender::OnPacketAcked( 110010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicPacketSequenceNumber acked_sequence_number, 111010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount acked_bytes, 112010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount bytes_in_flight) { 113f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) largest_acked_sequence_number_ = max(acked_sequence_number, 114f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) largest_acked_sequence_number_); 1150529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (InRecovery()) { 1160529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch PrrOnPacketAcked(acked_bytes); 1170529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return; 1180529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 119010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) MaybeIncreaseCwnd(acked_sequence_number, bytes_in_flight); 120e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch // TODO(ianswett): Should this even be called when not in slow start? 121e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch hybrid_slow_start_.OnPacketAcked(acked_sequence_number, InSlowStart()); 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 124f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void TcpCubicSender::OnPacketLost(QuicPacketSequenceNumber sequence_number, 125010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount bytes_in_flight) { 126f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // TCP NewReno (RFC6582) says that once a loss occurs, any losses in packets 127f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) // already sent should be treated as a single loss event, since it's expected. 128f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (sequence_number <= largest_sent_at_last_cutback_) { 1290529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (last_cutback_exited_slowstart_) { 1300529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch ++stats_->slowstart_packets_lost; 1310529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 132f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) DVLOG(1) << "Ignoring loss for largest_missing:" << sequence_number 133a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) << " because it was sent prior to the last CWND cutback."; 134f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return; 135f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 1360529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch ++stats_->tcp_loss_events; 1370529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch last_cutback_exited_slowstart_ = InSlowStart(); 1380529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (InSlowStart()) { 1390529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch ++stats_->slowstart_packets_lost; 1400529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 141010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) PrrOnPacketLost(bytes_in_flight); 1425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (reno_) { 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) congestion_window_ = congestion_window_ >> 1; 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) congestion_window_ = 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cubic_.CongestionWindowAfterPacketLoss(congestion_window_); 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) slowstart_threshold_ = congestion_window_; 150010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) // Enforce TCP's minimum congestion window of 2*MSS. 151f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (congestion_window_ < kMinimumCongestionWindow) { 1521e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) congestion_window_ = kMinimumCongestionWindow; 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 154f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) largest_sent_at_last_cutback_ = largest_sent_sequence_number_; 155a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // reset packet count from congestion avoidance mode. We start 156a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // counting again when we're out of recovery. 157a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) congestion_window_count_ = 0; 158a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DVLOG(1) << "Incoming loss; congestion window: " << congestion_window_ 159a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) << " slowstart threshold: " << slowstart_threshold_; 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 16268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)bool TcpCubicSender::OnPacketSent(QuicTime /*sent_time*/, 163010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount /*bytes_in_flight*/, 16468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) QuicPacketSequenceNumber sequence_number, 16568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) QuicByteCount bytes, 16668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) HasRetransmittableData is_retransmittable) { 167d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) // Only update bytes_in_flight_ for data packets. 168d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) if (is_retransmittable != HAS_RETRANSMITTABLE_DATA) { 169d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return false; 170d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) } 171d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) 1725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) prr_out_ += bytes; 17303b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) DCHECK_LT(largest_sent_sequence_number_, sequence_number); 17403b57e008b61dfcb1fbad3aea950ae0e001748b0Torne (Richard Coles) largest_sent_sequence_number_ = sequence_number; 1750529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch hybrid_slow_start_.OnPacketSent(sequence_number); 176d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles) return true; 1772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 179c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)QuicTime::Delta TcpCubicSender::TimeUntilSend( 18068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) QuicTime /* now */, 181010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount bytes_in_flight, 18246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) HasRetransmittableData has_retransmittable_data) const { 183e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch if (has_retransmittable_data == NO_RETRANSMITTABLE_DATA) { 18468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // For TCP we can always send an ACK immediately. 1852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return QuicTime::Delta::Zero(); 1862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1870529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (InRecovery()) { 188010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) return PrrTimeUntilSend(bytes_in_flight); 1892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 190010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (SendWindow() > bytes_in_flight) { 1915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return QuicTime::Delta::Zero(); 1925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return QuicTime::Delta::Infinite(); 1942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 19646d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)QuicByteCount TcpCubicSender::SendWindow() const { 19768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // What's the current send window in bytes. 1985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return min(receive_window_, GetCongestionWindow()); 1992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 201f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)QuicBandwidth TcpCubicSender::BandwidthEstimate() const { 202f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return QuicBandwidth::FromBytesAndTimeDelta(GetCongestionWindow(), 203a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) rtt_stats_->SmoothedRtt()); 204558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch} 205558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch 206116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool TcpCubicSender::HasReliableBandwidthEstimate() const { 207116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return !InSlowStart() && !InRecovery(); 208116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 209116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 210f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)QuicTime::Delta TcpCubicSender::RetransmissionDelay() const { 211a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (!rtt_stats_->HasUpdates()) { 212a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return QuicTime::Delta::Zero(); 213a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 214558790d6acca3451cf3a6b497803a5f07d0bec58Ben Murdoch return QuicTime::Delta::FromMicroseconds( 215a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) rtt_stats_->SmoothedRtt().ToMicroseconds() + 216a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 4 * rtt_stats_->mean_deviation().ToMicroseconds()); 2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 219f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)QuicByteCount TcpCubicSender::GetCongestionWindow() const { 2201e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) return congestion_window_ * kMaxSegmentSize; 2211e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles)} 2221e9bf3e0803691d0a228da41fc608347b6db4340Torne (Richard Coles) 223116680a4aac90f2aa7413d9095a592090648e557Ben Murdochbool TcpCubicSender::InSlowStart() const { 224116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return congestion_window_ < slowstart_threshold_; 225116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 226116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 227116680a4aac90f2aa7413d9095a592090648e557Ben MurdochQuicByteCount TcpCubicSender::GetSlowStartThreshold() const { 228116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return slowstart_threshold_ * kMaxSegmentSize; 229116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 230116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 231010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)bool TcpCubicSender::IsCwndLimited(QuicByteCount bytes_in_flight) const { 2322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const QuicByteCount congestion_window_bytes = congestion_window_ * 2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kMaxSegmentSize; 234010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (bytes_in_flight >= congestion_window_bytes) { 2352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 2362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 237010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) const QuicByteCount max_burst = kMaxBurstLength * kMaxSegmentSize; 238010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) const QuicByteCount available_bytes = 239010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) congestion_window_bytes - bytes_in_flight; 240010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) const bool slow_start_limited = InSlowStart() && 241010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) bytes_in_flight > congestion_window_bytes / 2; 242010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) return slow_start_limited || available_bytes <= max_burst; 2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool TcpCubicSender::InRecovery() const { 2465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return largest_acked_sequence_number_ <= largest_sent_at_last_cutback_ && 2475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) largest_acked_sequence_number_ != 0; 2485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2500f1bc08d4cfcc34181b0b5cbf065c40f687bf740Torne (Richard Coles)// Called when we receive an ack. Normal TCP tracks how many packets one ack 2512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// represents, but quic has a separate ack for each packet. 2525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void TcpCubicSender::MaybeIncreaseCwnd( 253010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicPacketSequenceNumber acked_sequence_number, 254010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) QuicByteCount bytes_in_flight) { 2550529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch LOG_IF(DFATAL, InRecovery()) << "Never increase the CWND during recovery."; 256010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (!IsCwndLimited(bytes_in_flight)) { 2572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // We don't update the congestion window unless we are close to using the 2582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // window we have available. 2592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 2602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 261e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch if (InSlowStart()) { 2622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // congestion_window_cnt is the number of acks since last change of snd_cwnd 263ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch if (congestion_window_ < max_tcp_congestion_window_) { 2643551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // TCP slow start, exponential growth, increase by one for each ACK. 2655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++congestion_window_; 2662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 267a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DVLOG(1) << "Slow start; congestion window: " << congestion_window_ 268a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) << " slowstart threshold: " << slowstart_threshold_; 2695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 2705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (congestion_window_ >= max_tcp_congestion_window_) { 2725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 2735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Congestion avoidance 2755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (reno_) { 2765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Classic Reno congestion avoidance provided for testing. 277a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 278a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) ++congestion_window_count_; 2795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (congestion_window_count_ >= congestion_window_) { 2805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++congestion_window_; 2815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) congestion_window_count_ = 0; 2822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 283a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 284a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DVLOG(1) << "Reno; congestion window: " << congestion_window_ 285a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) << " slowstart threshold: " << slowstart_threshold_ 286a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) << " congestion window count: " << congestion_window_count_; 2875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 288a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) congestion_window_ = min(max_tcp_congestion_window_, 289a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) cubic_.CongestionWindowAfterAck( 290a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) congestion_window_, rtt_stats_->min_rtt())); 291a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DVLOG(1) << "Cubic; congestion window: " << congestion_window_ 292a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) << " slowstart threshold: " << slowstart_threshold_; 2932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void TcpCubicSender::OnRetransmissionTimeout(bool packets_retransmitted) { 2975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) largest_sent_at_last_cutback_ = 0; 298116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!packets_retransmitted) { 299116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return; 300116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 301116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch cubic_.Reset(); 302116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch hybrid_slow_start_.Restart(); 303116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch previous_slowstart_threshold_ = slowstart_threshold_; 304116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch slowstart_threshold_ = congestion_window_ / 2; 305116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch previous_congestion_window_ = congestion_window_; 306116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch congestion_window_ = kMinimumCongestionWindow; 307116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 308116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 309116680a4aac90f2aa7413d9095a592090648e557Ben Murdochvoid TcpCubicSender::RevertRetransmissionTimeout() { 310116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (previous_congestion_window_ == 0) { 311116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LOG(DFATAL) << "No previous congestion window to revert to."; 312116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return; 3135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 314116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch congestion_window_ = previous_congestion_window_; 315116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch slowstart_threshold_ = previous_slowstart_threshold_; 316116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch previous_congestion_window_ = 0; 3172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 3182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 319010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)void TcpCubicSender::PrrOnPacketLost(QuicByteCount bytes_in_flight) { 3200529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch prr_out_ = 0; 321010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) bytes_in_flight_before_loss_ = bytes_in_flight; 322010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) prr_delivered_ = 0; 323010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) ack_count_since_loss_ = 0; 3240529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch} 3250529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch 3260529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochvoid TcpCubicSender::PrrOnPacketAcked(QuicByteCount acked_bytes) { 3270529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch prr_delivered_ += acked_bytes; 3280529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch ++ack_count_since_loss_; 3290529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch} 3300529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch 331010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)QuicTime::Delta TcpCubicSender::PrrTimeUntilSend( 33246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) QuicByteCount bytes_in_flight) const { 3330529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch DCHECK(InRecovery()); 334010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) // Return QuicTime::Zero In order to ensure limited transmit always works. 3351320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci if (prr_out_ == 0 || bytes_in_flight < kMaxSegmentSize) { 336010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) return QuicTime::Delta::Zero(); 337010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) } 338010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (SendWindow() > bytes_in_flight) { 3390529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // During PRR-SSRB, limit outgoing packets to 1 extra MSS per ack, instead 3400529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // of sending the entire available window. This prevents burst retransmits 3410529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // when more packets are lost than the CWND reduction. 3420529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // limit = MAX(prr_delivered - prr_out, DeliveredData) + MSS 343010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (prr_delivered_ + ack_count_since_loss_ * kMaxSegmentSize <= prr_out_) { 3440529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return QuicTime::Delta::Infinite(); 3450529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 3460529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return QuicTime::Delta::Zero(); 3470529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 3480529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // Implement Proportional Rate Reduction (RFC6937) 3490529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // Checks a simplified version of the PRR formula that doesn't use division: 3500529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // AvailableSendWindow = 3510529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch // CEIL(prr_delivered * ssthresh / BytesInFlightAtLoss) - prr_sent 3520529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch if (prr_delivered_ * slowstart_threshold_ * kMaxSegmentSize > 3530529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch prr_out_ * bytes_in_flight_before_loss_) { 3540529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return QuicTime::Delta::Zero(); 3550529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch } 3560529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch return QuicTime::Delta::Infinite(); 3570529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch} 3580529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch 3595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)CongestionControlType TcpCubicSender::GetCongestionControlType() const { 3605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return reno_ ? kReno : kCubic; 3615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 3625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace net 364