#include "net/quic/quic_sent_packet_manager.h"
+#include <algorithm>
+
#include "base/logging.h"
#include "base/stl_util.h"
+#include "net/quic/congestion_control/pacing_sender.h"
+#include "net/quic/crypto/crypto_protocol.h"
#include "net/quic/quic_ack_notifier_manager.h"
+#include "net/quic/quic_connection_stats.h"
+#include "net/quic/quic_flags.h"
+#include "net/quic/quic_utils_chromium.h"
using std::make_pair;
-
-// 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;
+using std::max;
+using std::min;
namespace net {
+namespace {
+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;
+
+// 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;
+
+bool HasCryptoHandshake(const TransmissionInfo& transmission_info) {
+ if (transmission_info.retransmittable_frames == NULL) {
+ return false;
+ }
+ return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
+ IS_HANDSHAKE;
+}
-#define ENDPOINT (is_server_ ? "Server: " : " Client: ")
+} // namespace
-QuicSentPacketManager::HelperInterface::~HelperInterface() {
-}
+#define ENDPOINT (is_server_ ? "Server: " : " Client: ")
QuicSentPacketManager::QuicSentPacketManager(bool is_server,
- HelperInterface* helper)
- : is_server_(is_server),
- helper_(helper) {
+ const QuicClock* clock,
+ QuicConnectionStats* stats,
+ CongestionFeedbackType type,
+ LossDetectionType loss_type)
+ : unacked_packets_(),
+ is_server_(is_server),
+ clock_(clock),
+ stats_(stats),
+ send_algorithm_(
+ SendAlgorithmInterface::Create(clock, &rtt_stats_, type, stats)),
+ loss_algorithm_(LossDetectionInterface::Create(loss_type)),
+ largest_observed_(0),
+ consecutive_rto_count_(0),
+ consecutive_tlp_count_(0),
+ consecutive_crypto_retransmission_count_(0),
+ max_tail_loss_probes_(kDefaultMaxTailLossProbes),
+ using_pacing_(false) {
}
QuicSentPacketManager::~QuicSentPacketManager() {
- STLDeleteValues(&unacked_packets_);
- while (!previous_transmissions_map_.empty()) {
- SequenceNumberSet* previous_transmissions =
- previous_transmissions_map_.begin()->second;
- for (SequenceNumberSet::const_iterator it = previous_transmissions->begin();
- it != previous_transmissions->end(); ++it) {
- DCHECK(ContainsKey(previous_transmissions_map_, *it));
- previous_transmissions_map_.erase(*it);
- }
- delete previous_transmissions;
- }
}
-void QuicSentPacketManager::OnSerializedPacket(
- const SerializedPacket& serialized_packet, QuicTime serialized_time) {
- if (serialized_packet.packet->is_fec_packet()) {
- DCHECK(!serialized_packet.retransmittable_frames);
- unacked_fec_packets_.insert(make_pair(
- serialized_packet.sequence_number, serialized_time));
- return;
+void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
+ if (config.HasReceivedInitialRoundTripTimeUs() &&
+ config.ReceivedInitialRoundTripTimeUs() > 0) {
+ rtt_stats_.set_initial_rtt_us(min(kMaxInitialRoundTripTimeUs,
+ config.ReceivedInitialRoundTripTimeUs()));
}
-
- if (serialized_packet.retransmittable_frames == NULL) {
- // Don't track ack/congestion feedback packets.
- return;
+ if (config.congestion_control() == kPACE) {
+ MaybeEnablePacing();
}
+ if (config.HasReceivedLossDetection() &&
+ config.ReceivedLossDetection() == kTIME) {
+ loss_algorithm_.reset(LossDetectionInterface::Create(kTime));
+ }
+ send_algorithm_->SetFromConfig(config, is_server_);
+}
- ack_notifier_manager_.OnSerializedPacket(serialized_packet);
+// 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);
+ }
- DCHECK(unacked_packets_.empty() ||
- unacked_packets_.rbegin()->first <
- serialized_packet.sequence_number);
- unacked_packets_[serialized_packet.sequence_number] =
- serialized_packet.retransmittable_frames;
- retransmission_map_[serialized_packet.sequence_number] =
- RetransmissionInfo(serialized_packet.sequence_number,
- serialized_packet.sequence_number_length);
+ unacked_packets_.AddPacket(serialized_packet);
}
void QuicSentPacketManager::OnRetransmittedPacket(
QuicPacketSequenceNumber old_sequence_number,
QuicPacketSequenceNumber new_sequence_number) {
- DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
- DCHECK(ContainsKey(retransmission_map_, 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);
- RetransmissionInfo retransmission_info(
- new_sequence_number, GetSequenceNumberLength(old_sequence_number));
- retransmission_info.number_retransmissions =
- retransmission_map_[old_sequence_number].number_retransmissions + 1;
- retransmission_map_.erase(old_sequence_number);
- retransmission_map_[new_sequence_number] = retransmission_info;
-
- RetransmittableFrames* frames = unacked_packets_[old_sequence_number];
- 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);
- if (FLAGS_track_retransmission_history) {
- // We keep the old packet in the unacked packet list until it, or one of
- // the retransmissions of it are acked.
- unacked_packets_[old_sequence_number] = NULL;
- } else {
- unacked_packets_.erase(old_sequence_number);
- }
- unacked_packets_[new_sequence_number] = frames;
-
- if (!FLAGS_track_retransmission_history) {
- return;
- }
- // Keep track of all sequence numbers that this packet
- // has been transmitted as.
- SequenceNumberSet* previous_transmissions;
- PreviousTransmissionMap::iterator it =
- previous_transmissions_map_.find(old_sequence_number);
- if (it == previous_transmissions_map_.end()) {
- // This is the first retransmission of this packet, so create a new entry.
- previous_transmissions = new SequenceNumberSet;
- previous_transmissions_map_[old_sequence_number] = previous_transmissions;
- previous_transmissions->insert(old_sequence_number);
- } else {
- // Otherwise, use the existing entry.
- previous_transmissions = it->second;
- }
- previous_transmissions->insert(new_sequence_number);
- previous_transmissions_map_[new_sequence_number] = previous_transmissions;
-
- DCHECK(HasRetransmittableFrames(new_sequence_number));
+ unacked_packets_.OnRetransmittedPacket(old_sequence_number,
+ new_sequence_number);
}
void QuicSentPacketManager::OnIncomingAck(
const ReceivedPacketInfo& received_info,
- bool is_truncated_ack) {
- HandleAckForSentPackets(received_info, is_truncated_ack);
- HandleAckForSentFecPackets(received_info);
+ QuicTime ack_receive_time) {
+ QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight();
+
+ // We rely on delta_time_largest_observed to compute an RTT estimate, so
+ // we only update rtt when the largest observed gets acked.
+ largest_observed_ = received_info.largest_observed;
+ bool largest_observed_acked = MaybeUpdateRTT(received_info, ack_receive_time);
+ HandleAckForSentPackets(received_info);
+ InvokeLossDetection(ack_receive_time);
+ MaybeInvokeCongestionEvent(largest_observed_acked, bytes_in_flight);
+
+ // 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;
+ }
+}
+
+void QuicSentPacketManager::MaybeInvokeCongestionEvent(
+ bool rtt_updated, QuicByteCount bytes_in_flight) {
+ if (rtt_updated || !packets_acked_.empty() ||
+ !packets_lost_.empty()) {
+ send_algorithm_->OnCongestionEvent(
+ rtt_updated, bytes_in_flight, packets_acked_, packets_lost_);
+ packets_acked_.clear();
+ packets_lost_.clear();
+ }
}
void QuicSentPacketManager::DiscardUnackedPacket(
QuicPacketSequenceNumber sequence_number) {
- MarkPacketReceivedByPeer(sequence_number);
+ MarkPacketHandled(sequence_number, QuicTime::Delta::Zero());
}
void QuicSentPacketManager::HandleAckForSentPackets(
- const ReceivedPacketInfo& received_info,
- bool is_truncated_ack) {
+ 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();
+ QuicTime::Delta delta_largest_observed =
+ received_info.delta_time_largest_observed;
+ QuicUnackedPacketMap::const_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.
+ // These packets are still in flight.
break;
}
- if (!IsAwaitingPacket(received_info, sequence_number)) {
- // 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 (IsAwaitingPacket(received_info, sequence_number)) {
+ // Remove any packets not being tracked by the send algorithm, allowing
+ // the high water mark to be raised if necessary.
+ if (QuicUnackedPacketMap::IsSentAndNotPending(it->second)) {
+ it = MarkPacketHandled(sequence_number, delta_largest_observed);
+ } else {
+ // 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.
+ // The nack count only increases when the largest observed increases.
+ size_t min_nacks = received_info.largest_observed - sequence_number;
+ // Truncated acks can nack the largest observed, so use a min of 1.
+ if (min_nacks == 0) {
+ min_nacks = 1;
+ }
+ unacked_packets_.NackPacket(sequence_number, min_nacks);
+ ++it;
+ }
continue;
}
- // The peer got packets after this sequence number. This is an explicit
- // nack.
-
- // TODO(rch): move this to the congestion manager, and fix the logic.
- // This is a packet which we planned on retransmitting and has not been
- // seen at the time of this ack being sent out. See if it's our new
- // lowest unacked packet.
- DVLOG(1) << ENDPOINT << "still missing packet " << sequence_number;
- ++it;
- RetransmissionMap::iterator retransmission_it =
- retransmission_map_.find(sequence_number);
- if (retransmission_it == retransmission_map_.end()) {
- 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.
+ if (it->second.pending) {
+ packets_acked_[sequence_number] = it->second;
}
- size_t nack_count = ++(retransmission_it->second.number_nacks);
- helper_->OnPacketNacked(sequence_number, nack_count);
+ it = MarkPacketHandled(sequence_number, delta_largest_observed);
+ }
+
+ // Discard any retransmittable frames associated with revived packets.
+ for (SequenceNumberSet::const_iterator revived_it =
+ received_info.revived_packets.begin();
+ revived_it != received_info.revived_packets.end(); ++revived_it) {
+ MarkPacketRevived(*revived_it, delta_largest_observed);
}
- // If we have received a trunacted ack, then we need to
+ // 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 (is_truncated_ack) {
- size_t num_to_clear = received_info.missing_packets.size() / 2;
- UnackedPacketMap::iterator it = unacked_packets_.begin();
- while (it != unacked_packets_.end() && num_to_clear > 0) {
- QuicPacketSequenceNumber sequence_number = it->first;
- ++it;
- // 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.
- if (!IsPreviousTransmission(sequence_number)) {
- break;
- }
-
- DCHECK(ContainsKey(previous_transmissions_map_, sequence_number));
- DCHECK(!ContainsKey(retransmission_map_, sequence_number));
- DCHECK(!HasRetransmittableFrames(sequence_number));
- unacked_packets_.erase(sequence_number);
- SequenceNumberSet* previous_transmissions =
- previous_transmissions_map_[sequence_number];
- previous_transmissions_map_.erase(sequence_number);
- previous_transmissions->erase(sequence_number);
- if (previous_transmissions->size() == 1) {
- previous_transmissions_map_.erase(*previous_transmissions->begin());
- delete previous_transmissions;
- }
- --num_to_clear;
- }
+ if (received_info.is_truncated) {
+ unacked_packets_.ClearPreviousRetransmissions(
+ received_info.missing_packets.size() / 2);
}
}
bool QuicSentPacketManager::HasRetransmittableFrames(
QuicPacketSequenceNumber sequence_number) const {
- if (!ContainsKey(unacked_packets_, sequence_number)) {
- return false;
+ return unacked_packets_.HasRetransmittableFrames(sequence_number);
+}
+
+void QuicSentPacketManager::RetransmitUnackedPackets(
+ RetransmissionType retransmission_type) {
+ QuicUnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
+ while (unacked_it != unacked_packets_.end()) {
+ const RetransmittableFrames* frames =
+ unacked_it->second.retransmittable_frames;
+ // Only mark it as handled if it can't be retransmitted and there are no
+ // pending retransmissions which would be cleared.
+ if (frames == NULL && unacked_it->second.all_transmissions->size() == 1 &&
+ retransmission_type == ALL_PACKETS) {
+ unacked_it = MarkPacketHandled(unacked_it->first,
+ QuicTime::Delta::Zero());
+ continue;
+ }
+ // If it had no other transmissions, we handle it above. If it has
+ // other transmissions, one of them must have retransmittable frames,
+ // so that gets resolved the same way as other retransmissions.
+ // TODO(ianswett): Consider adding a new retransmission type which removes
+ // all these old packets from unacked and retransmits them as new sequence
+ // numbers with no connection to the previous ones.
+ if (frames != NULL && (retransmission_type == ALL_PACKETS ||
+ frames->encryption_level() == ENCRYPTION_INITIAL)) {
+ unacked_packets_.SetNotPending(unacked_it->first);
+ MarkForRetransmission(unacked_it->first, ALL_UNACKED_RETRANSMISSION);
+ }
+ ++unacked_it;
}
+}
- return unacked_packets_.find(sequence_number)->second != NULL;
+void QuicSentPacketManager::DiscardUnencryptedPackets() {
+ QuicUnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
+ while (unacked_it != unacked_packets_.end()) {
+ const RetransmittableFrames* frames =
+ unacked_it->second.retransmittable_frames;
+ if (frames != NULL && frames->encryption_level() == ENCRYPTION_NONE) {
+ // Once you're forward secure, no unencrypted packets will be sent.
+ // Additionally, it's likely the peer will be forward secure, and no acks
+ // for these packets will be received, so mark the packet as handled.
+ pending_retransmissions_.erase(unacked_it->first);
+ unacked_it = MarkPacketHandled(unacked_it->first,
+ QuicTime::Delta::Zero());
+ continue;
+ }
+ ++unacked_it;
+ }
}
-bool QuicSentPacketManager::MarkForRetransmission(
+void 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.
+ const TransmissionInfo& transmission_info =
+ unacked_packets_.GetTransmissionInfo(sequence_number);
+ LOG_IF(DFATAL, transmission_info.retransmittable_frames == NULL);
+ // 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 true;
+ return;
}
pending_retransmissions_[sequence_number] = transmission_type;
- return true;
}
bool QuicSentPacketManager::HasPendingRetransmissions() const {
DCHECK(!pending_retransmissions_.empty());
QuicPacketSequenceNumber sequence_number =
pending_retransmissions_.begin()->first;
- DCHECK(ContainsKey(unacked_packets_, sequence_number));
- DCHECK(unacked_packets_[sequence_number]);
+ TransmissionType transmission_type = pending_retransmissions_.begin()->second;
+ if (unacked_packets_.HasPendingCryptoPackets()) {
+ // Ensure crypto packets are retransmitted before other packets.
+ PendingRetransmissionMap::const_iterator it =
+ pending_retransmissions_.begin();
+ do {
+ if (HasCryptoHandshake(unacked_packets_.GetTransmissionInfo(it->first))) {
+ sequence_number = it->first;
+ transmission_type = it->second;
+ break;
+ }
+ ++it;
+ } while (it != pending_retransmissions_.end());
+ }
+ DCHECK(unacked_packets_.IsUnacked(sequence_number));
+ const TransmissionInfo& transmission_info =
+ unacked_packets_.GetTransmissionInfo(sequence_number);
+ DCHECK(transmission_info.retransmittable_frames);
return PendingRetransmission(sequence_number,
- pending_retransmissions_.begin()->second,
- GetRetransmittableFrames(sequence_number),
- GetSequenceNumberLength(sequence_number));
+ transmission_type,
+ *transmission_info.retransmittable_frames,
+ transmission_info.sequence_number_length);
}
-bool QuicSentPacketManager::IsPreviousTransmission(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(ContainsKey(unacked_packets_, sequence_number));
+void QuicSentPacketManager::MarkPacketRevived(
+ QuicPacketSequenceNumber sequence_number,
+ QuicTime::Delta delta_largest_observed) {
+ if (!unacked_packets_.IsUnacked(sequence_number)) {
+ return;
+ }
+ // This packet has been revived at the receiver. If we were going to
+ // retransmit it, do not retransmit it anymore.
+ pending_retransmissions_.erase(sequence_number);
- PreviousTransmissionMap::const_iterator it =
- previous_transmissions_map_.find(sequence_number);
- if (it == previous_transmissions_map_.end()) {
- return false;
+ const TransmissionInfo& transmission_info =
+ unacked_packets_.GetTransmissionInfo(sequence_number);
+ // The AckNotifierManager needs to be notified for revived packets,
+ // since it indicates the packet arrived from the appliction's perspective.
+ if (transmission_info.retransmittable_frames) {
+ ack_notifier_manager_.OnPacketAcked(
+ sequence_number, delta_largest_observed);
}
- SequenceNumberSet* previous_transmissions = it->second;
- DCHECK(!previous_transmissions->empty());
- return *previous_transmissions->rbegin() != sequence_number;
+ unacked_packets_.NeuterIfPendingOrRemovePacket(sequence_number);
}
-QuicPacketSequenceNumber QuicSentPacketManager::GetMostRecentTransmission(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(ContainsKey(unacked_packets_, sequence_number));
-
- PreviousTransmissionMap::const_iterator it =
- previous_transmissions_map_.find(sequence_number);
- if (it == previous_transmissions_map_.end()) {
- return sequence_number;
+QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled(
+ QuicPacketSequenceNumber sequence_number,
+ QuicTime::Delta delta_largest_observed) {
+ if (!unacked_packets_.IsUnacked(sequence_number)) {
+ LOG(DFATAL) << "Packet is not unacked: " << sequence_number;
+ return unacked_packets_.end();
+ }
+ const TransmissionInfo& transmission_info =
+ unacked_packets_.GetTransmissionInfo(sequence_number);
+ // If this packet is pending, remove it and inform the send algorithm.
+ if (transmission_info.pending) {
+ unacked_packets_.SetNotPending(sequence_number);
}
- SequenceNumberSet* previous_transmissions =
- previous_transmissions_map_.find(sequence_number)->second;
- DCHECK(!previous_transmissions->empty());
- return *previous_transmissions->rbegin();
-}
+ SequenceNumberSet all_transmissions = *transmission_info.all_transmissions;
+ SequenceNumberSet::reverse_iterator all_transmissions_it =
+ all_transmissions.rbegin();
+ QuicPacketSequenceNumber newest_transmission = *all_transmissions_it;
+ if (newest_transmission != sequence_number) {
+ stats_->bytes_spuriously_retransmitted += transmission_info.bytes_sent;
+ ++stats_->packets_spuriously_retransmitted;
+ }
-QuicSentPacketManager::UnackedPacketMap::iterator
-QuicSentPacketManager::MarkPacketReceivedByPeer(
- QuicPacketSequenceNumber sequence_number) {
- DCHECK(ContainsKey(unacked_packets_, sequence_number));
- UnackedPacketMap::iterator next_unacked =
- unacked_packets_.find(sequence_number);
- ++next_unacked;
-
- // If this packet has never been retransmitted, then simply drop it.
- if (!ContainsKey(previous_transmissions_map_, sequence_number)) {
- DiscardPacket(sequence_number);
- return next_unacked;
- }
-
- SequenceNumberSet* previous_transmissions =
- previous_transmissions_map_.find(sequence_number)->second;
- SequenceNumberSet::reverse_iterator previous_transmissions_it
- = previous_transmissions->rbegin();
- DCHECK(previous_transmissions_it != previous_transmissions->rend());
-
- QuicPacketSequenceNumber new_packet = *previous_transmissions_it;
- bool is_new_packet = new_packet == sequence_number;
- if (is_new_packet) {
- DiscardPacket(new_packet);
- } else {
- if (next_unacked->first == new_packet) {
- ++next_unacked;
+ // The AckNotifierManager needs to be notified about the most recent
+ // transmission, since that's the one only one it tracks.
+ ack_notifier_manager_.OnPacketAcked(newest_transmission,
+ delta_largest_observed);
+
+ bool has_crypto_handshake = HasCryptoHandshake(
+ unacked_packets_.GetTransmissionInfo(newest_transmission));
+ while (all_transmissions_it != all_transmissions.rend()) {
+ QuicPacketSequenceNumber previous_transmission = *all_transmissions_it;
+ // If this packet was marked for retransmission, don't bother retransmitting
+ // it anymore.
+ pending_retransmissions_.erase(previous_transmission);
+ if (has_crypto_handshake) {
+ // If it's a crypto handshake packet, discard it and all retransmissions,
+ // since they won't be acked now that one has been processed.
+ unacked_packets_.SetNotPending(previous_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 unacked_packets_[new_packet];
- unacked_packets_[new_packet] = NULL;
- pending_retransmissions_.erase(new_packet);
- }
- previous_transmissions_map_.erase(new_packet);
-
- // 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;
- DCHECK(ContainsKey(previous_transmissions_map_, previous_transmission));
- previous_transmissions_map_.erase(previous_transmission);
- if (next_unacked != unacked_packets_.end() &&
- next_unacked->first == previous_transmission) {
- ++next_unacked;
- }
- DiscardPacket(previous_transmission);
+ unacked_packets_.NeuterIfPendingOrRemovePacket(previous_transmission);
+ ++all_transmissions_it;
}
- delete previous_transmissions;
-
- next_unacked = unacked_packets_.begin();
+ QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin();
while (next_unacked != unacked_packets_.end() &&
next_unacked->first < sequence_number) {
- ++next_unacked;
- }
+ ++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()) {
- DCHECK(!ContainsKey(retransmission_map_, sequence_number));
- return;
+bool QuicSentPacketManager::IsUnacked(
+ QuicPacketSequenceNumber sequence_number) const {
+ return unacked_packets_.IsUnacked(sequence_number);
+}
+
+bool QuicSentPacketManager::HasUnackedPackets() const {
+ return unacked_packets_.HasUnackedPackets();
+}
+
+QuicPacketSequenceNumber
+QuicSentPacketManager::GetLeastUnackedSentPacket() const {
+ return unacked_packets_.GetLeastUnackedSentPacket();
+}
+
+bool QuicSentPacketManager::OnPacketSent(
+ QuicPacketSequenceNumber sequence_number,
+ QuicTime sent_time,
+ QuicByteCount bytes,
+ TransmissionType transmission_type,
+ HasRetransmittableData has_retransmittable_data) {
+ DCHECK_LT(0u, sequence_number);
+ LOG_IF(DFATAL, bytes == 0) << "Cannot send empty packets.";
+ // In rare circumstances, the packet could be serialized, sent, and then acked
+ // before OnPacketSent is called.
+ if (!unacked_packets_.IsUnacked(sequence_number)) {
+ return false;
}
- // Delete the unacked packet.
- delete unacked_it->second;
- unacked_packets_.erase(unacked_it);
- retransmission_map_.erase(sequence_number);
- pending_retransmissions_.erase(sequence_number);
- return;
+ // Only track packets as pending that the send algorithm wants us to track.
+ if (!send_algorithm_->OnPacketSent(sent_time,
+ unacked_packets_.bytes_in_flight(),
+ sequence_number,
+ bytes,
+ has_retransmittable_data)) {
+ unacked_packets_.SetSent(sequence_number, sent_time, bytes, false);
+ // Do not reset the retransmission timer, since the packet isn't tracked.
+ return false;
+ }
+
+ const bool set_retransmission_timer = !unacked_packets_.HasPendingPackets();
+
+ unacked_packets_.SetSent(sequence_number, sent_time, bytes, true);
+
+ // 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::HandleAckForSentFecPackets(
- const ReceivedPacketInfo& received_info) {
- UnackedFecPacketMap::iterator it = unacked_fec_packets_.begin();
- while (it != unacked_fec_packets_.end()) {
- QuicPacketSequenceNumber sequence_number = it->first;
- if (sequence_number > received_info.largest_observed) {
- break;
+void QuicSentPacketManager::OnRetransmissionTimeout() {
+ DCHECK(unacked_packets_.HasPendingPackets());
+ // Handshake retransmission, timer based loss detection, TLP, and RTO are
+ // implemented with a single alarm. The handshake alarm is set when the
+ // handshake has not completed, the loss alarm is set when the loss detection
+ // algorithm says to, 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:
+ ++stats_->crypto_retransmit_count;
+ RetransmitCryptoPackets();
+ return;
+ case LOSS_MODE: {
+ ++stats_->loss_timeout_count;
+ QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight();
+ InvokeLossDetection(clock_->Now());
+ MaybeInvokeCongestionEvent(false, bytes_in_flight);
+ 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.
+ ++stats_->tlp_count;
+ RetransmitOldestPacket();
+ return;
+ case RTO_MODE:
+ ++stats_->rto_count;
+ RetransmitAllPackets();
+ return;
+ }
+}
- if (!IsAwaitingPacket(received_info, sequence_number)) {
- DVLOG(1) << ENDPOINT << "Got an ack for fec packet: " << sequence_number;
- unacked_fec_packets_.erase(it++);
- } else {
- // TODO(rch): treat these packets more consistently. They should
- // be subject to NACK and RTO based loss. (Thought obviously, they
- // should not be retransmitted.)
- DVLOG(1) << ENDPOINT << "Still missing ack for fec packet: "
- << sequence_number;
- ++it;
+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 (QuicUnackedPacketMap::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 ||
+ frames->HasCryptoHandshake() != IS_HANDSHAKE) {
+ continue;
}
+ packet_retransmitted = true;
+ MarkForRetransmission(sequence_number, HANDSHAKE_RETRANSMISSION);
+ // Abandon all the crypto retransmissions now so they're not lost later.
+ unacked_packets_.SetNotPending(sequence_number);
}
+ DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
}
-void QuicSentPacketManager::DiscardFecPacket(
- QuicPacketSequenceNumber sequence_number) {
- DCHECK(ContainsKey(unacked_fec_packets_, sequence_number));
- unacked_fec_packets_.erase(sequence_number);
+void QuicSentPacketManager::RetransmitOldestPacket() {
+ DCHECK_EQ(TLP_MODE, GetRetransmissionMode());
+ ++consecutive_tlp_count_;
+ for (QuicUnackedPacketMap::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.";
}
-bool QuicSentPacketManager::IsRetransmission(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(HasRetransmittableFrames(sequence_number));
- RetransmissionMap::const_iterator it =
- retransmission_map_.find(sequence_number);
- return it != retransmission_map_.end() &&
- it->second.number_retransmissions > 0;
-}
+void QuicSentPacketManager::RetransmitAllPackets() {
+ // Abandon all retransmittable packets and packets older than the
+ // retransmission delay.
-size_t QuicSentPacketManager::GetRetransmissionCount(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(HasRetransmittableFrames(sequence_number));
- DCHECK(ContainsKey(retransmission_map_, sequence_number));
- RetransmissionMap::const_iterator it =
- retransmission_map_.find(sequence_number);
- return it->second.number_retransmissions;
-}
+ DVLOG(1) << "OnRetransmissionTimeout() fired with "
+ << unacked_packets_.GetNumUnackedPackets() << " unacked packets.";
-bool QuicSentPacketManager::IsUnacked(
- QuicPacketSequenceNumber sequence_number) const {
- return ContainsKey(unacked_packets_, sequence_number);
+ // 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 (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+ it != unacked_packets_.end(); ++it) {
+ unacked_packets_.SetNotPending(it->first);
+ 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_;
+ }
}
-bool QuicSentPacketManager::IsFecUnacked(
- QuicPacketSequenceNumber sequence_number) const {
- return ContainsKey(unacked_fec_packets_, sequence_number);
+QuicSentPacketManager::RetransmissionTimeoutMode
+ QuicSentPacketManager::GetRetransmissionMode() const {
+ DCHECK(unacked_packets_.HasPendingPackets());
+ if (unacked_packets_.HasPendingCryptoPackets()) {
+ return HANDSHAKE_MODE;
+ }
+ if (loss_algorithm_->GetLossTimeout() != QuicTime::Zero()) {
+ return LOSS_MODE;
+ }
+ if (consecutive_tlp_count_ < max_tail_loss_probes_) {
+ if (unacked_packets_.HasUnackedRetransmittableFrames()) {
+ return TLP_MODE;
+ }
+ }
+ return RTO_MODE;
}
-const RetransmittableFrames& QuicSentPacketManager::GetRetransmittableFrames(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(ContainsKey(unacked_packets_, sequence_number));
- DCHECK(ContainsKey(retransmission_map_, sequence_number));
+void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
+ const QuicCongestionFeedbackFrame& frame,
+ const QuicTime& feedback_receive_time) {
+ send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
+ frame, feedback_receive_time);
+}
- return *unacked_packets_.find(sequence_number)->second;
+void QuicSentPacketManager::InvokeLossDetection(QuicTime time) {
+ SequenceNumberSet lost_packets =
+ loss_algorithm_->DetectLostPackets(unacked_packets_,
+ time,
+ largest_observed_,
+ rtt_stats_);
+ for (SequenceNumberSet::const_iterator it = lost_packets.begin();
+ it != lost_packets.end(); ++it) {
+ QuicPacketSequenceNumber sequence_number = *it;
+ const TransmissionInfo& transmission_info =
+ unacked_packets_.GetTransmissionInfo(sequence_number);
+ // TODO(ianswett): If it's expected the FEC packet may repair the loss, it
+ // should be recorded as a loss to the send algorithm, but not retransmitted
+ // until it's known whether the FEC packet arrived.
+ ++stats_->packets_lost;
+ packets_lost_[sequence_number] = transmission_info;
+ unacked_packets_.SetNotPending(sequence_number);
+
+ if (transmission_info.retransmittable_frames != NULL) {
+ MarkForRetransmission(sequence_number, LOSS_RETRANSMISSION);
+ } 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.
+ unacked_packets_.NeuterIfPendingOrRemovePacket(sequence_number);
+ }
+ }
}
-QuicSequenceNumberLength QuicSentPacketManager::GetSequenceNumberLength(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(ContainsKey(unacked_packets_, sequence_number));
- DCHECK(ContainsKey(retransmission_map_, sequence_number));
+bool QuicSentPacketManager::MaybeUpdateRTT(
+ const ReceivedPacketInfo& received_info,
+ const QuicTime& ack_receive_time) {
+ if (!unacked_packets_.IsUnacked(received_info.largest_observed)) {
+ return false;
+ }
+ // 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 =
+ unacked_packets_.GetTransmissionInfo(received_info.largest_observed);
+ // Don't update the RTT if it hasn't been sent.
+ if (transmission_info.sent_time == QuicTime::Zero()) {
+ return false;
+ }
- return retransmission_map_.find(
- sequence_number)->second.sequence_number_length;
+ QuicTime::Delta send_delta =
+ ack_receive_time.Subtract(transmission_info.sent_time);
+ rtt_stats_.UpdateRtt(
+ send_delta, received_info.delta_time_largest_observed, ack_receive_time);
+ return true;
}
-QuicTime QuicSentPacketManager::GetFecSentTime(
- QuicPacketSequenceNumber sequence_number) const {
- DCHECK(ContainsKey(unacked_fec_packets_, sequence_number));
+QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
+ QuicTime now,
+ TransmissionType transmission_type,
+ HasRetransmittableData retransmittable) {
+ // The TLP logic is entirely contained within QuicSentPacketManager, so the
+ // send algorithm does not need to be consulted.
+ if (transmission_type == TLP_RETRANSMISSION) {
+ return QuicTime::Delta::Zero();
+ }
+ return send_algorithm_->TimeUntilSend(
+ now, unacked_packets_.bytes_in_flight(), retransmittable);
+}
- return unacked_fec_packets_.find(sequence_number)->second;
+// 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);
}
-bool QuicSentPacketManager::HasUnackedPackets() const {
- return !unacked_packets_.empty();
+const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
+ // Don't set the timer if there are no pending packets.
+ if (!unacked_packets_.HasPendingPackets()) {
+ return QuicTime::Zero();
+ }
+ switch (GetRetransmissionMode()) {
+ case HANDSHAKE_MODE:
+ return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
+ case LOSS_MODE:
+ return loss_algorithm_->GetLossTimeout();
+ 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.
+ const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
+ 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.
+ const QuicTime sent_time =
+ unacked_packets_.GetFirstPendingPacketSentTime();
+ QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay());
+ // Always wait at least 1.5 * RTT from now.
+ QuicTime min_timeout = clock_->ApproximateNow().Add(
+ rtt_stats_.SmoothedRtt().Multiply(1.5));
+
+ return QuicTime::Max(min_timeout, rto_timeout);
+ }
+ }
+ DCHECK(false);
+ return QuicTime::Zero();
}
-size_t QuicSentPacketManager::GetNumUnackedPackets() const {
- return unacked_packets_.size();
+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<int64>(kMinHandshakeTimeoutMs,
+ 1.5 * rtt_stats_.SmoothedRtt().ToMilliseconds());
+ return QuicTime::Delta::FromMilliseconds(
+ delay_ms << consecutive_crypto_retransmission_count_);
}
-bool QuicSentPacketManager::HasUnackedFecPackets() const {
- return !unacked_fec_packets_.empty();
+const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
+ QuicTime::Delta srtt = rtt_stats_.SmoothedRtt();
+ if (!unacked_packets_.HasMultiplePendingPackets()) {
+ return QuicTime::Delta::Max(
+ srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2));
+ }
+ return QuicTime::Delta::FromMilliseconds(
+ max(kMinTailLossProbeTimeoutMs,
+ static_cast<int64>(2 * srtt.ToMilliseconds())));
}
-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();
+const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
+ QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
+ // TODO(rch): This code should move to |send_algorithm_|.
+ if (retransmission_delay.IsZero()) {
+ // We are in the initial state, use default timeout values.
+ retransmission_delay =
+ QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
+ } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
+ retransmission_delay =
+ QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
}
- return unacked_packets_.begin()->first;
-}
+ // Calculate exponential back off.
+ retransmission_delay = retransmission_delay.Multiply(
+ 1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));
-QuicPacketSequenceNumber
-QuicSentPacketManager::GetLeastUnackedFecPacket() const {
- if (unacked_fec_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();
+ if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
+ return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
}
+ return retransmission_delay;
+}
- return unacked_fec_packets_.begin()->first;
+const RttStats* QuicSentPacketManager::GetRttStats() const {
+ return &rtt_stats_;
}
-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);
+QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
+ return send_algorithm_->BandwidthEstimate();
+}
+
+QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
+ return send_algorithm_->GetCongestionWindow();
+}
+
+void QuicSentPacketManager::MaybeEnablePacing() {
+ if (!FLAGS_enable_quic_pacing) {
+ return;
}
- return unacked_packets;
+
+ if (using_pacing_) {
+ return;
+ }
+
+ using_pacing_ = true;
+ send_algorithm_.reset(
+ new PacingSender(send_algorithm_.release(),
+ QuicTime::Delta::FromMicroseconds(1)));
}
} // namespace net
projects / platform / framework / web / crosswalk.git / blobdiff