| // 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" |
| |
| using std::make_pair; |
| 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; |
| |
| // A test-only flag to prevent the RTO from backing off when multiple sequential |
| // tail drops occur. |
| bool FLAGS_limit_rto_increase_for_tests = 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; |
| |
| // We only retransmit 2 packets per ack. |
| static const size_t kMaxRetransmissionsPerAck = 2; |
| |
| // TCP retransmits after 3 nacks. |
| static const size_t kNumberOfNacksBeforeRetransmission = 3; |
| |
| 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()), |
| consecutive_rto_count_(0), |
| 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()); |
| } |
| 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); |
| } |
| |
| void QuicSentPacketManager::OnSerializedPacket( |
| const SerializedPacket& serialized_packet) { |
| if (serialized_packet.retransmittable_frames == NULL && |
| !serialized_packet.packet->is_fec_packet()) { |
| // Don't track ack/congestion feedback packets. |
| return; |
| } |
| |
| ack_notifier_manager_.OnSerializedPacket(serialized_packet); |
| |
| 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); |
| |
| UnackedPacketMap::iterator unacked_it = |
| unacked_packets_.find(old_sequence_number); |
| RetransmittableFrames* frames = unacked_it->second.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. |
| unacked_it->second.retransmittable_frames = NULL; |
| unacked_packets_[new_sequence_number] = |
| TransmissionInfo(frames, GetSequenceNumberLength(old_sequence_number)); |
| |
| // Keep track of all sequence numbers that this packet |
| // has been transmitted as. |
| SequenceNumberSet* previous_transmissions = |
| unacked_it->second.previous_transmissions; |
| if (previous_transmissions == NULL) { |
| // This is the first retransmission of this packet, so create a new entry. |
| previous_transmissions = new SequenceNumberSet; |
| unacked_it->second.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) { |
| // Determine if the least unacked sequence number is being acked. |
| QuicPacketSequenceNumber least_unacked_sent_before = |
| GetLeastUnackedSentPacket(); |
| bool new_least_unacked = !IsAwaitingPacket(received_info, |
| least_unacked_sent_before); |
| |
| HandleAckForSentPackets(received_info); |
| |
| SequenceNumberSet retransmission_packets = |
| OnIncomingAckFrame(received_info, ack_receive_time); |
| |
| for (SequenceNumberSet::const_iterator it = retransmission_packets.begin(); |
| it != retransmission_packets.end(); ++it) { |
| DCHECK(!ContainsKey(pending_packets_, *it)); |
| MarkForRetransmission(*it, NACK_RETRANSMISSION); |
| } |
| |
| if (new_least_unacked) { |
| consecutive_rto_count_ = 0; |
| } |
| |
| return new_least_unacked; |
| } |
| |
| void QuicSentPacketManager::DiscardUnackedPacket( |
| QuicPacketSequenceNumber sequence_number) { |
| MarkPacketReceivedByPeer(sequence_number); |
| } |
| |
| 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 = MarkPacketReceivedByPeer(sequence_number); |
| |
| // 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) { |
| 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; |
| } |
| unacked_packets_.erase(it++); |
| --num_to_clear; |
| } |
| } |
| |
| bool QuicSentPacketManager::HasRetransmittableFrames( |
| QuicPacketSequenceNumber sequence_number) const { |
| if (!ContainsKey(unacked_packets_, sequence_number)) { |
| return false; |
| } |
| |
| return unacked_packets_.find( |
| sequence_number)->second.retransmittable_frames != NULL; |
| } |
| |
| void QuicSentPacketManager::RetransmitUnackedPackets( |
| RetransmissionType retransmission_type) { |
| if (unacked_packets_.empty()) { |
| return; |
| } |
| |
| for (UnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin(); |
| unacked_it != unacked_packets_.end(); ++unacked_it) { |
| const RetransmittableFrames* frames = |
| unacked_it->second.retransmittable_frames; |
| if (frames == NULL) { |
| continue; |
| } |
| if (retransmission_type == ALL_PACKETS || |
| frames->encryption_level() == ENCRYPTION_INITIAL) { |
| // TODO(satyamshekhar): Think about congestion control here. |
| // Specifically, about the retransmission count of packets being sent |
| // proactively to achieve 0 (minimal) RTT. |
| OnPacketAbandoned(unacked_it->first); |
| if (!MarkForRetransmission(unacked_it->first, NACK_RETRANSMISSION)) { |
| DiscardUnackedPacket(unacked_it->first); |
| } |
| } |
| } |
| } |
| |
| bool QuicSentPacketManager::MarkForRetransmission( |
| QuicPacketSequenceNumber sequence_number, |
| TransmissionType transmission_type) { |
| DCHECK(ContainsKey(unacked_packets_, sequence_number)); |
| if (!HasRetransmittableFrames(sequence_number)) { |
| return false; |
| } |
| // If it's already in the retransmission map, don't add it again, just let |
| // the prior retransmission request win out. |
| if (ContainsKey(pending_retransmissions_, sequence_number)) { |
| return true; |
| } |
| |
| pending_retransmissions_[sequence_number] = transmission_type; |
| return true; |
| } |
| |
| 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 RetransmittableFrames* retransmittable_frames = |
| unacked_packets_[sequence_number].retransmittable_frames; |
| DCHECK(retransmittable_frames); |
| |
| return PendingRetransmission(sequence_number, |
| pending_retransmissions_.begin()->second, |
| *retransmittable_frames, |
| GetSequenceNumberLength(sequence_number)); |
| } |
| |
| bool QuicSentPacketManager::IsPreviousTransmission( |
| QuicPacketSequenceNumber sequence_number) const { |
| DCHECK(ContainsKey(unacked_packets_, sequence_number)); |
| |
| UnackedPacketMap::const_iterator it = unacked_packets_.find(sequence_number); |
| if (it->second.previous_transmissions == NULL) { |
| return false; |
| } |
| |
| SequenceNumberSet* previous_transmissions = it->second.previous_transmissions; |
| DCHECK(!previous_transmissions->empty()); |
| return *previous_transmissions->rbegin() != sequence_number; |
| } |
| |
| QuicSentPacketManager::UnackedPacketMap::iterator |
| QuicSentPacketManager::MarkPacketReceivedByPeer( |
| QuicPacketSequenceNumber sequence_number) { |
| DCHECK(ContainsKey(unacked_packets_, sequence_number)); |
| |
| // If this packet has never been retransmitted, then simply drop it. |
| UnackedPacketMap::const_iterator previous_it = |
| unacked_packets_.find(sequence_number); |
| if (previous_it->second.previous_transmissions == NULL) { |
| UnackedPacketMap::iterator next_unacked = |
| unacked_packets_.find(sequence_number); |
| ++next_unacked; |
| DiscardPacket(sequence_number); |
| return next_unacked; |
| } |
| |
| SequenceNumberSet* previous_transmissions = |
| previous_it->second.previous_transmissions; |
| DCHECK(!previous_transmissions->empty()); |
| SequenceNumberSet::reverse_iterator previous_transmissions_it = |
| previous_transmissions->rbegin(); |
| QuicPacketSequenceNumber newest_transmission = *previous_transmissions_it; |
| if (newest_transmission == sequence_number) { |
| DiscardPacket(newest_transmission); |
| } else { |
| // 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 unacked_packets_[newest_transmission].retransmittable_frames; |
| unacked_packets_[newest_transmission].retransmittable_frames = NULL; |
| unacked_packets_[newest_transmission].previous_transmissions = NULL; |
| pending_retransmissions_.erase(newest_transmission); |
| } |
| |
| // Clear out information all previous transmissions. |
| ++previous_transmissions_it; |
| while (previous_transmissions_it != previous_transmissions->rend()) { |
| QuicPacketSequenceNumber previous_transmission = *previous_transmissions_it; |
| ++previous_transmissions_it; |
| DiscardPacket(previous_transmission); |
| } |
| |
| delete previous_transmissions; |
| |
| 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); |
| // Packet was not meant to be retransmitted. |
| if (unacked_it == unacked_packets_.end()) { |
| return; |
| } |
| |
| // Delete the retransmittable frames. |
| delete unacked_it->second.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); |
| } |
| |
| QuicSequenceNumberLength QuicSentPacketManager::GetSequenceNumberLength( |
| QuicPacketSequenceNumber sequence_number) const { |
| DCHECK(ContainsKey(unacked_packets_, sequence_number)); |
| |
| return unacked_packets_.find(sequence_number)->second.sequence_number_length; |
| } |
| |
| bool QuicSentPacketManager::HasUnackedPackets() const { |
| return !unacked_packets_.empty(); |
| } |
| |
| 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; |
| } |
| |
| void QuicSentPacketManager::OnPacketSent( |
| QuicPacketSequenceNumber sequence_number, |
| QuicTime sent_time, |
| QuicByteCount bytes, |
| TransmissionType transmission_type, |
| HasRetransmittableData has_retransmittable_data) { |
| DCHECK_LT(0u, sequence_number); |
| DCHECK(!ContainsKey(pending_packets_, sequence_number)); |
| if (ContainsKey(unacked_packets_, sequence_number)) { |
| unacked_packets_[sequence_number].sent_time = sent_time; |
| } |
| |
| // Only track packets the send algorithm wants us to track. |
| if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes, |
| transmission_type, |
| has_retransmittable_data)) { |
| return; |
| } |
| packet_history_map_[sequence_number] = new SendAlgorithmInterface::SentPacket( |
| bytes, sent_time, has_retransmittable_data); |
| pending_packets_.insert(sequence_number); |
| CleanupPacketHistory(); |
| } |
| |
| void QuicSentPacketManager::OnRetransmissionTimeout() { |
| // Abandon all pending packets to ensure the congestion window |
| // opens up before we attempt to retransmit packets. |
| QuicTime::Delta retransmission_delay = GetRetransmissionDelay(); |
| QuicTime max_send_time = |
| clock_->ApproximateNow().Subtract(retransmission_delay); |
| for (SequenceNumberSet::iterator it = pending_packets_.begin(); |
| it != pending_packets_.end();) { |
| QuicPacketSequenceNumber sequence_number = *it; |
| DCHECK(ContainsKey(packet_history_map_, sequence_number)); |
| DCHECK(ContainsKey(unacked_packets_, sequence_number)); |
| const TransmissionInfo& transmission_info = |
| unacked_packets_.find(sequence_number)->second; |
| // Abandon retransmittable packet and old non-retransmittable packets. |
| if (transmission_info.retransmittable_frames || |
| transmission_info.sent_time <= max_send_time) { |
| pending_packets_.erase(it++); |
| send_algorithm_->OnPacketAbandoned( |
| sequence_number, packet_history_map_[sequence_number]->bytes_sent()); |
| } else { |
| ++it; |
| } |
| } |
| |
| // Attempt to send all the unacked packets when the RTO fires, let the |
| // congestion manager decide how many to send immediately and the remaining |
| // packets will be queued for future sending. |
| DVLOG(1) << "OnRetransmissionTimeout() fired with " |
| << unacked_packets_.size() << " unacked packets."; |
| |
| // Retransmit any packet with retransmittable frames. |
| bool packets_retransmitted = false; |
| for (UnackedPacketMap::const_iterator it = unacked_packets_.begin(); |
| it != unacked_packets_.end(); ++it) { |
| if (it->second.retransmittable_frames != NULL) { |
| packets_retransmitted = true; |
| MarkForRetransmission(it->first, RTO_RETRANSMISSION); |
| } |
| } |
| |
| // Only inform the sent packet manager of an RTO if data was retransmitted. |
| if (packets_retransmitted) { |
| ++consecutive_rto_count_; |
| send_algorithm_->OnRetransmissionTimeout(); |
| } |
| } |
| |
| void QuicSentPacketManager::OnPacketAbandoned( |
| QuicPacketSequenceNumber sequence_number) { |
| SequenceNumberSet::iterator it = pending_packets_.find(sequence_number); |
| if (it != pending_packets_.end()) { |
| DCHECK(ContainsKey(packet_history_map_, sequence_number)); |
| send_algorithm_->OnPacketAbandoned( |
| sequence_number, packet_history_map_[sequence_number]->bytes_sent()); |
| pending_packets_.erase(it); |
| } |
| } |
| |
| void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame( |
| const QuicCongestionFeedbackFrame& frame, |
| const QuicTime& feedback_receive_time) { |
| send_algorithm_->OnIncomingQuicCongestionFeedbackFrame( |
| frame, feedback_receive_time, packet_history_map_); |
| } |
| |
| SequenceNumberSet QuicSentPacketManager::OnIncomingAckFrame( |
| const ReceivedPacketInfo& received_info, |
| const QuicTime& ack_receive_time) { |
| MaybeUpdateRTT(received_info, ack_receive_time); |
| |
| // We want to. |
| // * Get all packets lower(including) than largest_observed |
| // from pending_packets_. |
| // * Remove all packets no longer being waited for(ie: acked). |
| // * Send each ACK in the list to send_algorithm_. |
| SequenceNumberSet::iterator it = pending_packets_.begin(); |
| SequenceNumberSet::iterator it_upper = |
| pending_packets_.upper_bound(received_info.largest_observed); |
| |
| SequenceNumberSet retransmission_packets; |
| SequenceNumberSet lost_packets; |
| while (it != it_upper) { |
| QuicPacketSequenceNumber sequence_number = *it; |
| const SendAlgorithmInterface::SentPacket* sent_packet = |
| packet_history_map_[sequence_number]; |
| if (!IsAwaitingPacket(received_info, sequence_number)) { |
| // Not missing, hence implicitly acked. |
| size_t bytes_sent = sent_packet->bytes_sent(); |
| send_algorithm_->OnPacketAcked(sequence_number, bytes_sent, rtt_sample_); |
| pending_packets_.erase(it++); // Must be incremented post to work. |
| continue; |
| } |
| |
| // The peer got packets after this sequence number. This is an explicit |
| // nack. |
| DVLOG(1) << "still missing packet " << sequence_number; |
| DCHECK(ContainsKey(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; |
| packet_history_map_[sequence_number]->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. |
| if (pending_packets_.size() <= kNumberOfNacksBeforeRetransmission && |
| sent_packet->has_retransmittable_data() == HAS_RETRANSMITTABLE_DATA && |
| *pending_packets_.rbegin() == received_info.largest_observed) { |
| num_nacks_needed = received_info.largest_observed - sequence_number; |
| } |
| |
| if (sent_packet->nack_count() < num_nacks_needed) { |
| ++it; |
| continue; |
| } |
| |
| // If the number of retransmissions has maxed out, don't lose or retransmit |
| // any more packets. |
| if (retransmission_packets.size() >= kMaxRetransmissionsPerAck) { |
| ++it; |
| continue; |
| } |
| |
| lost_packets.insert(sequence_number); |
| if (sent_packet->has_retransmittable_data() == HAS_RETRANSMITTABLE_DATA) { |
| retransmission_packets.insert(sequence_number); |
| } |
| |
| ++it; |
| } |
| // Abandon packets after the loop over pending packets, because otherwise it |
| // changes the early retransmit logic and iteration. |
| for (SequenceNumberSet::const_iterator it = lost_packets.begin(); |
| it != lost_packets.end(); ++it) { |
| // 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(*it, ack_receive_time); |
| OnPacketAbandoned(*it); |
| } |
| |
| return retransmission_packets; |
| } |
| |
| 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. |
| SendAlgorithmInterface::SentPacketsMap::iterator history_it = |
| packet_history_map_.find(received_info.largest_observed); |
| // TODO(satyamshekhar): largest_observed might be missing. |
| if (history_it == packet_history_map_.end()) { |
| return; |
| } |
| |
| QuicTime::Delta send_delta = ack_receive_time.Subtract( |
| history_it->second->send_timestamp()); |
| 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; |
| } |
| } |
| |
| 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() { |
| return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2); |
| } |
| |
| const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const { |
| size_t number_retransmissions = consecutive_rto_count_; |
| if (FLAGS_limit_rto_increase_for_tests) { |
| const size_t kTailDropWindowSize = 5; |
| const size_t kTailDropMaxRetransmissions = 4; |
| if (pending_packets_.size() <= kTailDropWindowSize) { |
| // Avoid exponential backoff of RTO when there are only a few packets |
| // outstanding. This helps avoid the situation where fake packet loss |
| // causes a packet and it's retransmission to be dropped causing |
| // test timouts. |
| if (number_retransmissions <= kTailDropMaxRetransmissions) { |
| number_retransmissions = 0; |
| } else { |
| number_retransmissions -= kTailDropMaxRetransmissions; |
| } |
| } |
| } |
| |
| 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 = QuicTime::Delta::FromMilliseconds( |
| retransmission_delay.ToMilliseconds() * static_cast<size_t>( |
| (1 << min<size_t>(number_retransmissions, 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(pending_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))); |
| } |
| |
| } // namespace net |