// Copyright 2013 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "net/quic/quic_sent_packet_manager.h" #include "base/logging.h" #include "base/stl_util.h" #include "net/quic/congestion_control/pacing_sender.h" #include "net/quic/quic_ack_notifier_manager.h" #include "net/quic/quic_utils_chromium.h" using std::make_pair; using std::max; using std::min; // TODO(rtenneti): Remove this. // Do not flip this flag until the flakiness of the // net/tools/quic/end_to_end_test is fixed. // If true, then QUIC connections will track the retransmission history of a // packet so that an ack of a previous transmission will ack the data of all // other transmissions. bool FLAGS_track_retransmission_history = false; // Do not remove this flag until the Finch-trials described in b/11706275 // are complete. // If true, QUIC connections will support the use of a pacing algorithm when // sending packets, in an attempt to reduce packet loss. The client must also // request pacing for the server to enable it. bool FLAGS_enable_quic_pacing = false; namespace net { namespace { static const int kBitrateSmoothingPeriodMs = 1000; static const int kHistoryPeriodMs = 5000; static const int kDefaultRetransmissionTimeMs = 500; // TCP RFC calls for 1 second RTO however Linux differs from this default and // define the minimum RTO to 200ms, we will use the same until we have data to // support a higher or lower value. static const int kMinRetransmissionTimeMs = 200; static const int kMaxRetransmissionTimeMs = 60000; static const size_t kMaxRetransmissions = 10; // TCP retransmits after 3 nacks. static const size_t kNumberOfNacksBeforeRetransmission = 3; // Only exponentially back off the handshake timer 5 times due to a timeout. static const size_t kMaxHandshakeRetransmissionBackoffs = 5; static const size_t kMinHandshakeTimeoutMs = 10; // Sends up to two tail loss probes before firing an RTO, // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe. static const size_t kDefaultMaxTailLossProbes = 2; static const int64 kMinTailLossProbeTimeoutMs = 10; COMPILE_ASSERT(kHistoryPeriodMs >= kBitrateSmoothingPeriodMs, history_must_be_longer_or_equal_to_the_smoothing_period); } // namespace #define ENDPOINT (is_server_ ? "Server: " : " Client: ") QuicSentPacketManager::HelperInterface::~HelperInterface() { } QuicSentPacketManager::QuicSentPacketManager(bool is_server, HelperInterface* helper, const QuicClock* clock, CongestionFeedbackType type) : is_server_(is_server), helper_(helper), clock_(clock), send_algorithm_(SendAlgorithmInterface::Create(clock, type)), rtt_sample_(QuicTime::Delta::Infinite()), pending_crypto_packet_count_(0), consecutive_rto_count_(0), consecutive_tlp_count_(0), consecutive_crypto_retransmission_count_(0), max_tail_loss_probes_(kDefaultMaxTailLossProbes), using_pacing_(false) { } QuicSentPacketManager::~QuicSentPacketManager() { for (UnackedPacketMap::iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { delete it->second.retransmittable_frames; // Only delete previous_transmissions once, for the newest packet. if (it->second.previous_transmissions != NULL && it->first == *it->second.previous_transmissions->rbegin()) { delete it->second.previous_transmissions; } } STLDeleteValues(&packet_history_map_); } void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) { if (config.initial_round_trip_time_us() > 0 && rtt_sample_.IsInfinite()) { // The initial rtt should already be set on the client side. DVLOG_IF(1, !is_server_) << "Client did not set an initial RTT, but did negotiate one."; rtt_sample_ = QuicTime::Delta::FromMicroseconds(config.initial_round_trip_time_us()); send_algorithm_->UpdateRtt(rtt_sample_); } if (config.congestion_control() == kPACE) { MaybeEnablePacing(); } send_algorithm_->SetFromConfig(config, is_server_); } void QuicSentPacketManager::SetMaxPacketSize(QuicByteCount max_packet_size) { send_algorithm_->SetMaxPacketSize(max_packet_size); } // TODO(ianswett): Combine this method with OnPacketSent once packets are always // sent in order and the connection tracks RetransmittableFrames for longer. void QuicSentPacketManager::OnSerializedPacket( const SerializedPacket& serialized_packet) { if (serialized_packet.retransmittable_frames) { ack_notifier_manager_.OnSerializedPacket(serialized_packet); if (serialized_packet.retransmittable_frames->HasCryptoHandshake() == IS_HANDSHAKE) { ++pending_crypto_packet_count_; } } DCHECK(unacked_packets_.empty() || unacked_packets_.rbegin()->first < serialized_packet.sequence_number); unacked_packets_[serialized_packet.sequence_number] = TransmissionInfo(serialized_packet.retransmittable_frames, serialized_packet.sequence_number_length); } void QuicSentPacketManager::OnRetransmittedPacket( QuicPacketSequenceNumber old_sequence_number, QuicPacketSequenceNumber new_sequence_number) { DCHECK(ContainsKey(unacked_packets_, old_sequence_number)); DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number)); DCHECK(unacked_packets_.empty() || unacked_packets_.rbegin()->first < new_sequence_number); pending_retransmissions_.erase(old_sequence_number); // TODO(ianswett): Discard and lose the packet lazily instead of immediately. TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, old_sequence_number); RetransmittableFrames* frames = transmission_info->retransmittable_frames; DCHECK(frames); // A notifier may be waiting to hear about ACKs for the original sequence // number. Inform them that the sequence number has changed. ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number, new_sequence_number); // We keep the old packet in the unacked packet list until it, or one of // the retransmissions of it are acked. transmission_info->retransmittable_frames = NULL; unacked_packets_[new_sequence_number] = TransmissionInfo(frames, transmission_info->sequence_number_length); // Keep track of all sequence numbers that this packet // has been transmitted as. SequenceNumberSet* previous_transmissions = transmission_info->previous_transmissions; if (previous_transmissions == NULL) { // This is the first retransmission of this packet, so create a new entry. previous_transmissions = new SequenceNumberSet; transmission_info->previous_transmissions = previous_transmissions; previous_transmissions->insert(old_sequence_number); } previous_transmissions->insert(new_sequence_number); unacked_packets_[new_sequence_number].previous_transmissions = previous_transmissions; DCHECK(HasRetransmittableFrames(new_sequence_number)); } bool QuicSentPacketManager::OnIncomingAck( const ReceivedPacketInfo& received_info, QuicTime ack_receive_time) { // We rely on delta_time_largest_observed to compute an RTT estimate, so // we only update rtt when the largest observed gets acked. bool largest_observed_acked = ContainsKey(unacked_packets_, received_info.largest_observed); MaybeUpdateRTT(received_info, ack_receive_time); HandleAckForSentPackets(received_info); MaybeRetransmitOnAckFrame(received_info, ack_receive_time); // Anytime we are making forward progress and have a new RTT estimate, reset // the backoff counters. if (largest_observed_acked) { // Reset all retransmit counters any time a new packet is acked. consecutive_rto_count_ = 0; consecutive_tlp_count_ = 0; consecutive_crypto_retransmission_count_ = 0; } // Always reset the retransmission alarm when an ack comes in, since we now // have a better estimate of the current rtt than when it was set. return true; } void QuicSentPacketManager::DiscardUnackedPacket( QuicPacketSequenceNumber sequence_number) { MarkPacketHandled(sequence_number, NOT_RECEIVED_BY_PEER); } void QuicSentPacketManager::HandleAckForSentPackets( const ReceivedPacketInfo& received_info) { // Go through the packets we have not received an ack for and see if this // incoming_ack shows they've been seen by the peer. UnackedPacketMap::iterator it = unacked_packets_.begin(); while (it != unacked_packets_.end()) { QuicPacketSequenceNumber sequence_number = it->first; if (sequence_number > received_info.largest_observed) { // These are very new sequence_numbers. break; } if (IsAwaitingPacket(received_info, sequence_number)) { ++it; continue; } // Packet was acked, so remove it from our unacked packet list. DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number; // If data is associated with the most recent transmission of this // packet, then inform the caller. it = MarkPacketHandled(sequence_number, RECEIVED_BY_PEER); // The AckNotifierManager is informed of every ACKed sequence number. ack_notifier_manager_.OnPacketAcked(sequence_number); } // If we have received a truncated ack, then we need to // clear out some previous transmissions to allow the peer // to actually ACK new packets. if (received_info.is_truncated) { ClearPreviousRetransmissions(received_info.missing_packets.size() / 2); } } void QuicSentPacketManager::ClearPreviousRetransmissions(size_t num_to_clear) { UnackedPacketMap::iterator it = unacked_packets_.begin(); while (it != unacked_packets_.end() && num_to_clear > 0) { QuicPacketSequenceNumber sequence_number = it->first; // If this is not a previous transmission then there is no point // in clearing out any further packets, because it will not affect // the high water mark. SequenceNumberSet* previous_transmissions = it->second.previous_transmissions; if (previous_transmissions == NULL) { if (it->second.retransmittable_frames == NULL) { // This is a current transmission, but a previous transmission has // been acked, so it's safe to remove. it = MarkPacketHandled(sequence_number, NOT_RECEIVED_BY_PEER); --num_to_clear; continue; } break; } QuicPacketSequenceNumber newest_transmission = *previous_transmissions->rbegin(); if (sequence_number == newest_transmission) { break; } DCHECK(it->second.retransmittable_frames == NULL); previous_transmissions->erase(sequence_number); if (previous_transmissions->size() == 1) { unacked_packets_[newest_transmission].previous_transmissions = NULL; delete previous_transmissions; } DCHECK(!it->second.pending); unacked_packets_.erase(it++); --num_to_clear; } } bool QuicSentPacketManager::HasRetransmittableFrames( QuicPacketSequenceNumber sequence_number) const { const TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, sequence_number); if (transmission_info == NULL) { return false; } return transmission_info->retransmittable_frames != NULL; } void QuicSentPacketManager::RetransmitUnackedPackets( RetransmissionType retransmission_type) { if (unacked_packets_.empty()) { return; } for (UnackedPacketMap::iterator unacked_it = unacked_packets_.begin(); unacked_it != unacked_packets_.end(); ++unacked_it) { const RetransmittableFrames* frames = unacked_it->second.retransmittable_frames; if (retransmission_type == ALL_PACKETS || (frames != NULL && frames->encryption_level() == ENCRYPTION_INITIAL)) { if (frames) { OnPacketAbandoned(unacked_it); MarkForRetransmission(unacked_it->first, NACK_RETRANSMISSION); } else { DiscardUnackedPacket(unacked_it->first); } } } } void QuicSentPacketManager::MarkForRetransmission( QuicPacketSequenceNumber sequence_number, TransmissionType transmission_type) { DCHECK(ContainsKey(unacked_packets_, sequence_number)); DCHECK(HasRetransmittableFrames(sequence_number)); // TODO(ianswett): Currently the RTO can fire while there are pending NACK // retransmissions for the same data, which is not ideal. if (ContainsKey(pending_retransmissions_, sequence_number)) { return; } pending_retransmissions_[sequence_number] = transmission_type; } bool QuicSentPacketManager::HasPendingRetransmissions() const { return !pending_retransmissions_.empty(); } QuicSentPacketManager::PendingRetransmission QuicSentPacketManager::NextPendingRetransmission() { DCHECK(!pending_retransmissions_.empty()); QuicPacketSequenceNumber sequence_number = pending_retransmissions_.begin()->first; DCHECK(ContainsKey(unacked_packets_, sequence_number)); const TransmissionInfo& transmission_info = FindOrDie(unacked_packets_, sequence_number); DCHECK(transmission_info.retransmittable_frames); return PendingRetransmission(sequence_number, pending_retransmissions_.begin()->second, *transmission_info.retransmittable_frames, transmission_info.sequence_number_length); } bool QuicSentPacketManager::IsPreviousTransmission( QuicPacketSequenceNumber sequence_number) const { DCHECK(ContainsKey(unacked_packets_, sequence_number)); UnackedPacketMap::const_iterator unacked_it = unacked_packets_.find(sequence_number); if (unacked_it == unacked_packets_.end()) { return false; } const TransmissionInfo* transmission_info = &unacked_it->second; if (transmission_info->previous_transmissions == NULL) { return false; } SequenceNumberSet* previous_transmissions = transmission_info->previous_transmissions; DCHECK(!previous_transmissions->empty()); return *previous_transmissions->rbegin() != sequence_number; } // static bool QuicSentPacketManager::HasCryptoHandshake( const TransmissionInfo& transmission_info) { if (transmission_info.retransmittable_frames == NULL) { return false; } return transmission_info.retransmittable_frames->HasCryptoHandshake() == IS_HANDSHAKE; } QuicSentPacketManager::UnackedPacketMap::iterator QuicSentPacketManager::MarkPacketHandled( QuicPacketSequenceNumber sequence_number, ReceivedByPeer received_by_peer) { DCHECK(ContainsKey(unacked_packets_, sequence_number)); // If this packet is pending, remove it and inform the send algorithm. UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); if (it->second.pending) { size_t bytes_sent = packet_history_map_[sequence_number]->bytes_sent(); if (received_by_peer == RECEIVED_BY_PEER) { send_algorithm_->OnPacketAcked(sequence_number, bytes_sent); } else { // It's been abandoned. send_algorithm_->OnPacketAbandoned(sequence_number, bytes_sent); } it->second.pending = false; } // If this packet has never been retransmitted, then simply drop it. if (it->second.previous_transmissions == NULL) { ++it; DiscardPacket(sequence_number); return it; } SequenceNumberSet* previous_transmissions = it->second.previous_transmissions; DCHECK(!previous_transmissions->empty()); SequenceNumberSet::reverse_iterator previous_transmissions_it = previous_transmissions->rbegin(); QuicPacketSequenceNumber newest_transmission = *previous_transmissions_it; TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, newest_transmission); if (newest_transmission == sequence_number) { DiscardPacket(newest_transmission); } else if (HasCryptoHandshake(*transmission_info)) { // If it's a crypto handshake packet, discard it and all retransmissions, // since they won't be acked now that one has been processed. if (transmission_info->pending) { OnPacketAbandoned(unacked_packets_.find(newest_transmission)); } DiscardPacket(newest_transmission); } else { TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, newest_transmission); // If we have received an ack for a previous transmission of a packet, // we want to keep the "new" transmission of the packet unacked, // but prevent the data from being retransmitted. delete transmission_info->retransmittable_frames; transmission_info->retransmittable_frames = NULL; transmission_info->previous_transmissions = NULL; } // Clear out information all previous transmissions unless they're pending. ++previous_transmissions_it; while (previous_transmissions_it != previous_transmissions->rend()) { QuicPacketSequenceNumber previous_transmission = *previous_transmissions_it; ++previous_transmissions_it; // If the packet was TLP retransmitted, the old copy is still pending. // Keep it until it is lost or acked. if (unacked_packets_[previous_transmission].pending) { // Previous transmissions will be deleted, so set it to NULL. unacked_packets_[previous_transmission].previous_transmissions = NULL; } else { DiscardPacket(previous_transmission); } } delete previous_transmissions; if (ContainsKey(pending_retransmissions_, newest_transmission)) { pending_retransmissions_.erase(newest_transmission); if (!unacked_packets_[newest_transmission].pending) { // If the newest transmission has already been marked for retransmission // and has already been abandoned, then we should remove it from // unacked_packets_, as well as cancel the retransmission. DCHECK(ContainsKey(unacked_packets_, newest_transmission)); DCHECK(!unacked_packets_[newest_transmission].previous_transmissions); unacked_packets_.erase(newest_transmission); } } UnackedPacketMap::iterator next_unacked = unacked_packets_.begin(); while (next_unacked != unacked_packets_.end() && next_unacked->first < sequence_number) { ++next_unacked; } return next_unacked; } void QuicSentPacketManager::DiscardPacket( QuicPacketSequenceNumber sequence_number) { UnackedPacketMap::iterator unacked_it = unacked_packets_.find(sequence_number); DCHECK(unacked_it != unacked_packets_.end()); // Ensure the packet is no longer pending when it's discarded. DCHECK(!unacked_it->second.pending); RetransmittableFrames* retransmittable_frames = unacked_it->second.retransmittable_frames; if (HasCryptoHandshake(unacked_it->second)) { --pending_crypto_packet_count_; } // Delete the retransmittable frames. delete retransmittable_frames; unacked_packets_.erase(unacked_it); pending_retransmissions_.erase(sequence_number); return; } bool QuicSentPacketManager::IsUnacked( QuicPacketSequenceNumber sequence_number) const { return ContainsKey(unacked_packets_, sequence_number); } bool QuicSentPacketManager::HasUnackedPackets() const { return !unacked_packets_.empty(); } bool QuicSentPacketManager::HasPendingPackets() const { for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) { if (it->second.pending) { return true; } } return false; } size_t QuicSentPacketManager::GetNumRetransmittablePackets() const { size_t num_unacked_packets = 0; for (UnackedPacketMap::const_iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { QuicPacketSequenceNumber sequence_number = it->first; if (HasRetransmittableFrames(sequence_number)) { ++num_unacked_packets; } } return num_unacked_packets; } QuicPacketSequenceNumber QuicSentPacketManager::GetLeastUnackedSentPacket() const { if (unacked_packets_.empty()) { // If there are no unacked packets, set the least unacked packet to // the sequence number of the next packet sent. return helper_->GetNextPacketSequenceNumber(); } return unacked_packets_.begin()->first; } SequenceNumberSet QuicSentPacketManager::GetUnackedPackets() const { SequenceNumberSet unacked_packets; for (UnackedPacketMap::const_iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { unacked_packets.insert(it->first); } return unacked_packets; } bool QuicSentPacketManager::OnPacketSent( QuicPacketSequenceNumber sequence_number, QuicTime sent_time, QuicByteCount bytes, TransmissionType transmission_type, HasRetransmittableData has_retransmittable_data) { DCHECK_LT(0u, sequence_number); UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); // In rare circumstances, the packet could be serialized, sent, and then acked // before OnPacketSent is called. if (it == unacked_packets_.end()) { return false; } DCHECK(!it->second.pending); // Only track packets the send algorithm wants us to track. if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes, transmission_type, has_retransmittable_data)) { DCHECK(it->second.retransmittable_frames == NULL); unacked_packets_.erase(it); // Do not reset the retransmission timer, since the packet isn't tracked. return false; } const bool set_retransmission_timer = !HasPendingPackets(); it->second.sent_time = sent_time; it->second.pending = true; packet_history_map_[sequence_number] = new SendAlgorithmInterface::SentPacket(bytes, sent_time); CleanupPacketHistory(); // Reset the retransmission timer anytime a packet is sent in tail loss probe // mode or before the crypto handshake has completed. return set_retransmission_timer || GetRetransmissionMode() != RTO_MODE; } void QuicSentPacketManager::OnRetransmissionTimeout() { DCHECK(HasPendingPackets()); // Handshake retransmission, TLP, and RTO are implemented with a single alarm. // The handshake alarm is set when the handshake has not completed, and the // TLP and RTO alarms are set after that. // The TLP alarm is always set to run for under an RTO. switch (GetRetransmissionMode()) { case HANDSHAKE_MODE: RetransmitCryptoPackets(); return; case TLP_MODE: // If no tail loss probe can be sent, because there are no retransmittable // packets, execute a conventional RTO to abandon old packets. RetransmitOldestPacket(); return; case RTO_MODE: RetransmitAllPackets(); return; } } void QuicSentPacketManager::RetransmitCryptoPackets() { DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode()); // TODO(ianswett): Typical TCP implementations only retransmit 5 times. consecutive_crypto_retransmission_count_ = min(kMaxHandshakeRetransmissionBackoffs, consecutive_crypto_retransmission_count_ + 1); bool packet_retransmitted = false; for (UnackedPacketMap::iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { QuicPacketSequenceNumber sequence_number = it->first; const RetransmittableFrames* frames = it->second.retransmittable_frames; // Only retransmit frames which are pending, and therefore have been sent. if (!it->second.pending || frames == NULL || frames->HasCryptoHandshake() != IS_HANDSHAKE) { continue; } DCHECK(ContainsKey(packet_history_map_, sequence_number)); packet_retransmitted = true; MarkForRetransmission(sequence_number, TLP_RETRANSMISSION); // Abandon all the crypto retransmissions now so they're not lost later. OnPacketAbandoned(it); } DCHECK(packet_retransmitted) << "No crypto packets found to retransmit."; } void QuicSentPacketManager::RetransmitOldestPacket() { DCHECK_EQ(TLP_MODE, GetRetransmissionMode()); ++consecutive_tlp_count_; for (UnackedPacketMap::const_iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { QuicPacketSequenceNumber sequence_number = it->first; const RetransmittableFrames* frames = it->second.retransmittable_frames; // Only retransmit frames which are pending, and therefore have been sent. if (!it->second.pending || frames == NULL) { continue; } DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake()); MarkForRetransmission(sequence_number, TLP_RETRANSMISSION); return; } DLOG(FATAL) << "No retransmittable packets, so RetransmitOldestPacket failed."; } void QuicSentPacketManager::RetransmitAllPackets() { // Abandon all retransmittable packets and packets older than the // retransmission delay. DVLOG(1) << "OnRetransmissionTimeout() fired with " << unacked_packets_.size() << " unacked packets."; // Request retransmission of all retransmittable packets when the RTO // fires, and let the congestion manager decide how many to send // immediately and the remaining packets will be queued. // Abandon any non-retransmittable packets that are sufficiently old. bool packets_retransmitted = false; for (UnackedPacketMap::iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { it->second.pending = false; if (it->second.retransmittable_frames != NULL) { packets_retransmitted = true; MarkForRetransmission(it->first, RTO_RETRANSMISSION); } } send_algorithm_->OnRetransmissionTimeout(packets_retransmitted); if (packets_retransmitted) { ++consecutive_rto_count_; } } QuicSentPacketManager::RetransmissionTimeoutMode QuicSentPacketManager::GetRetransmissionMode() const { DCHECK(HasPendingPackets()); if (pending_crypto_packet_count_ > 0) { return HANDSHAKE_MODE; } if (consecutive_tlp_count_ < max_tail_loss_probes_) { // Ensure there are retransmittable frames. for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) { if (it->second.pending && it->second.retransmittable_frames) { return TLP_MODE; } } } return RTO_MODE; } void QuicSentPacketManager::OnPacketAbandoned(UnackedPacketMap::iterator it) { DCHECK(it != unacked_packets_.end()); QuicPacketSequenceNumber sequence_number = it->first; DCHECK(ContainsKey(packet_history_map_, sequence_number)); if (it->second.pending) { send_algorithm_->OnPacketAbandoned( sequence_number, packet_history_map_[sequence_number]->bytes_sent()); it->second.pending = false; } } void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame( const QuicCongestionFeedbackFrame& frame, const QuicTime& feedback_receive_time) { send_algorithm_->OnIncomingQuicCongestionFeedbackFrame( frame, feedback_receive_time, packet_history_map_); } void QuicSentPacketManager::MaybeRetransmitOnAckFrame( const ReceivedPacketInfo& received_info, const QuicTime& ack_receive_time) { // Go through all pending packets up to the largest observed and see if any // need to be retransmitted or lost. size_t num_retransmitted = 0; UnackedPacketMap::iterator it = unacked_packets_.begin(); while (it != unacked_packets_.end() && it->first <= received_info.largest_observed) { if (!it->second.pending) { ++it; continue; } QuicPacketSequenceNumber sequence_number = it->first; DVLOG(1) << "still missing packet " << sequence_number; // Acks must be handled previously, so ensure it's missing and not acked. DCHECK(IsAwaitingPacket(received_info, sequence_number)); DCHECK(ContainsKey(packet_history_map_, sequence_number)); const TransmissionInfo& transmission_info = it->second; SendAlgorithmInterface::SentPacket* sent_packet = packet_history_map_[sequence_number]; // Consider it multiple nacks when there is a gap between the missing packet // and the largest observed, since the purpose of a nack threshold is to // tolerate re-ordering. This handles both StretchAcks and Forward Acks. // TODO(ianswett): This relies heavily on sequential reception of packets, // and makes an assumption that the congestion control uses TCP style nacks. size_t min_nacks = received_info.largest_observed - sequence_number; sent_packet->Nack(min_nacks); size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission; // Check for early retransmit(RFC5827) when the last packet gets acked and // the there are fewer than 4 pending packets. // TODO(ianswett): Set a retransmission timer instead of losing the packet // and retransmitting immediately. Also consider only invoking OnPacketLost // and OnPacketAbandoned when they're actually retransmitted in case they // arrive while queued for retransmission. if (transmission_info.retransmittable_frames && packet_history_map_.rbegin()->first == received_info.largest_observed) { num_nacks_needed = received_info.largest_observed - sequence_number; } if (sent_packet->nack_count() < num_nacks_needed) { ++it; continue; } // TODO(ianswett): OnPacketLost is also called from TCPCubicSender when // an FEC packet is lost, but FEC loss information should be shared among // congestion managers. Additionally, if it's expected the FEC packet may // repair the loss, it should be recorded as a loss to the congestion // manager, but not retransmitted until it's known whether the FEC packet // arrived. send_algorithm_->OnPacketLost(sequence_number, ack_receive_time); OnPacketAbandoned(it); if (transmission_info.retransmittable_frames) { ++num_retransmitted; MarkForRetransmission(sequence_number, NACK_RETRANSMISSION); ++it; } else { // Since we will not retransmit this, we need to remove it from // unacked_packets_. This is either the current transmission of // a packet whose previous transmission has been acked, or it // is a packet that has been TLP retransmitted. RemovePreviousTransmission(sequence_number); unacked_packets_.erase(it++); } } } void QuicSentPacketManager::MaybeUpdateRTT( const ReceivedPacketInfo& received_info, const QuicTime& ack_receive_time) { // We calculate the RTT based on the highest ACKed sequence number, the lower // sequence numbers will include the ACK aggregation delay. const TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, received_info.largest_observed); if (transmission_info == NULL) { return; } // Don't update the RTT if it hasn't been sent. if (transmission_info->sent_time == QuicTime::Zero()) { return; } QuicTime::Delta send_delta = ack_receive_time.Subtract(transmission_info->sent_time); if (send_delta > received_info.delta_time_largest_observed) { rtt_sample_ = send_delta.Subtract( received_info.delta_time_largest_observed); } else if (rtt_sample_.IsInfinite()) { // Even though we received information from the peer suggesting // an invalid (negative) RTT, we can use the send delta as an // approximation until we get a better estimate. rtt_sample_ = send_delta; } send_algorithm_->UpdateRtt(rtt_sample_); } QuicTime::Delta QuicSentPacketManager::TimeUntilSend( QuicTime now, TransmissionType transmission_type, HasRetransmittableData retransmittable, IsHandshake handshake) { return send_algorithm_->TimeUntilSend(now, transmission_type, retransmittable, handshake); } // Ensures that the Delayed Ack timer is always set to a value lesser // than the retransmission timer's minimum value (MinRTO). We want the // delayed ack to get back to the QUIC peer before the sender's // retransmission timer triggers. Since we do not know the // reverse-path one-way delay, we assume equal delays for forward and // reverse paths, and ensure that the timer is set to less than half // of the MinRTO. // There may be a value in making this delay adaptive with the help of // the sender and a signaling mechanism -- if the sender uses a // different MinRTO, we may get spurious retransmissions. May not have // any benefits, but if the delayed ack becomes a significant source // of (likely, tail) latency, then consider such a mechanism. const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const { return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2); } const QuicTime QuicSentPacketManager::GetRetransmissionTime() const { // Don't set the timer if there are no pending packets. if (!HasPendingPackets()) { return QuicTime::Zero(); } switch (GetRetransmissionMode()) { case HANDSHAKE_MODE: return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay()); case TLP_MODE: { // TODO(ianswett): When CWND is available, it would be preferable to // set the timer based on the earliest retransmittable packet. // Base the updated timer on the send time of the last packet. UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); while (it != unacked_packets_.rend() && (!it->second.pending || it->second.retransmittable_frames == NULL)) { ++it; } DCHECK(it != unacked_packets_.rend()); const QuicTime& sent_time = it->second.sent_time; const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay()); // Ensure the tlp timer never gets set to a time in the past. return QuicTime::Max(clock_->ApproximateNow(), tlp_time); } case RTO_MODE: { // The RTO is based on the first pending packet. UnackedPacketMap::const_iterator it = unacked_packets_.begin(); while (it != unacked_packets_.end() && !it->second.pending) { ++it; } DCHECK(it != unacked_packets_.end()); const QuicTime& sent_time = it->second.sent_time; // Always wait at least 1.5 * RTT after the first sent packet. QuicTime min_timeout = clock_->ApproximateNow().Add( SmoothedRtt().Multiply(1.5)); QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay()); return QuicTime::Max(min_timeout, rto_timeout); } } DCHECK(false); return QuicTime::Zero(); } const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay() const { // This is equivalent to the TailLossProbeDelay, but slightly more aggressive // because crypto handshake messages don't incur a delayed ack time. int64 delay_ms = max(kMinHandshakeTimeoutMs, 1.5 * SmoothedRtt().ToMilliseconds()); return QuicTime::Delta::FromMilliseconds( delay_ms << consecutive_crypto_retransmission_count_); } const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const { QuicTime::Delta srtt = SmoothedRtt(); size_t num_pending = 0; for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) { if (it->second.pending) { ++num_pending; if (num_pending > 1) { break; } } } DCHECK_LT(0u, num_pending); if (num_pending == 1) { return QuicTime::Delta::Max( srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2)); } return QuicTime::Delta::FromMilliseconds( max(kMinTailLossProbeTimeoutMs, static_cast(2 * srtt.ToMilliseconds()))); } const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const { QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay(); if (retransmission_delay.IsZero()) { // We are in the initial state, use default timeout values. retransmission_delay = QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs); } // Calculate exponential back off. retransmission_delay = retransmission_delay.Multiply( 1 << min(consecutive_rto_count_, kMaxRetransmissions)); // TODO(rch): This code should move to |send_algorithm_|. if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) { return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs); } if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) { return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs); } return retransmission_delay; } const QuicTime::Delta QuicSentPacketManager::SmoothedRtt() const { return send_algorithm_->SmoothedRtt(); } QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const { return send_algorithm_->BandwidthEstimate(); } QuicByteCount QuicSentPacketManager::GetCongestionWindow() const { return send_algorithm_->GetCongestionWindow(); } void QuicSentPacketManager::CleanupPacketHistory() { const QuicTime::Delta kHistoryPeriod = QuicTime::Delta::FromMilliseconds(kHistoryPeriodMs); QuicTime now = clock_->ApproximateNow(); SendAlgorithmInterface::SentPacketsMap::iterator history_it = packet_history_map_.begin(); for (; history_it != packet_history_map_.end(); ++history_it) { if (now.Subtract(history_it->second->send_timestamp()) <= kHistoryPeriod) { return; } // Don't remove packets which have not been acked. if (ContainsKey(unacked_packets_, history_it->first)) { continue; } delete history_it->second; packet_history_map_.erase(history_it); history_it = packet_history_map_.begin(); } } void QuicSentPacketManager::MaybeEnablePacing() { if (!FLAGS_enable_quic_pacing) { return; } if (using_pacing_) { return; } using_pacing_ = true; send_algorithm_.reset( new PacingSender(send_algorithm_.release(), QuicTime::Delta::FromMicroseconds(1))); } void QuicSentPacketManager::RemovePreviousTransmission( QuicPacketSequenceNumber sequence_number) { SequenceNumberSet* previous_transmissions = unacked_packets_[sequence_number].previous_transmissions; if (!previous_transmissions) { return; } previous_transmissions->erase(sequence_number); if (previous_transmissions->size() == 1) { QuicPacketSequenceNumber current = *previous_transmissions->begin(); unacked_packets_[current].previous_transmissions = NULL; delete previous_transmissions; } } } // namespace net