src/net/quic/quic_sent_packet_manager.h

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_
   6 #define NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_
   7
   8 #include <deque>
   9 #include <list>
  10 #include <map>
  11 #include <queue>
  12 #include <set>
  13 #include <utility>
  14 #include <vector>
  15
  16 #include "base/containers/hash_tables.h"
  17 #include "base/memory/scoped_ptr.h"
  18 #include "net/base/linked_hash_map.h"
  19 #include "net/quic/congestion_control/loss_detection_interface.h"
  20 #include "net/quic/congestion_control/rtt_stats.h"
  21 #include "net/quic/congestion_control/send_algorithm_interface.h"
  22 #include "net/quic/quic_ack_notifier_manager.h"
  23 #include "net/quic/quic_protocol.h"
  24 #include "net/quic/quic_unacked_packet_map.h"
  25
  26 NET_EXPORT_PRIVATE extern bool FLAGS_track_retransmission_history;
  27 NET_EXPORT_PRIVATE extern bool FLAGS_enable_quic_pacing;
  28
  29 namespace net {
  30
  31 namespace test {
  32 class QuicConnectionPeer;
  33 class QuicSentPacketManagerPeer;
  34 }  // namespace test
  35
  36 class QuicClock;
  37 class QuicConfig;
  38 struct QuicConnectionStats;
  39
  40 // Class which tracks the set of packets sent on a QUIC connection and contains
  41 // a send algorithm to decide when to send new packets.  It keeps track of any
  42 // retransmittable data associated with each packet. If a packet is
  43 // retransmitted, it will keep track of each version of a packet so that if a
  44 // previous transmission is acked, the data will not be retransmitted.
  45 class NET_EXPORT_PRIVATE QuicSentPacketManager {
  46  public:
  47   // Struct to store the pending retransmission information.
  48   struct PendingRetransmission {
  49     PendingRetransmission(QuicPacketSequenceNumber sequence_number,
  50                           TransmissionType transmission_type,
  51                           const RetransmittableFrames& retransmittable_frames,
  52                           QuicSequenceNumberLength sequence_number_length)
  53             : sequence_number(sequence_number),
  54               transmission_type(transmission_type),
  55               retransmittable_frames(retransmittable_frames),
  56               sequence_number_length(sequence_number_length) {
  57         }
  58
  59         QuicPacketSequenceNumber sequence_number;
  60         TransmissionType transmission_type;
  61         const RetransmittableFrames& retransmittable_frames;
  62         QuicSequenceNumberLength sequence_number_length;
  63   };
  64
  65   QuicSentPacketManager(bool is_server,
  66                         const QuicClock* clock,
  67                         QuicConnectionStats* stats,
  68                         CongestionFeedbackType congestion_type);
  69   virtual ~QuicSentPacketManager();
  70
  71   virtual void SetFromConfig(const QuicConfig& config);
  72
  73   // Called when a new packet is serialized.  If the packet contains
  74   // retransmittable data, it will be added to the unacked packet map.
  75   void OnSerializedPacket(const SerializedPacket& serialized_packet);
  76
  77   // Called when a packet is retransmitted with a new sequence number.
  78   // Replaces the old entry in the unacked packet map with the new
  79   // sequence number.
  80   void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,
  81                              QuicPacketSequenceNumber new_sequence_number);
  82
  83   // Processes the incoming ack and returns true if the retransmission or ack
  84   // alarm should be reset.
  85   bool OnIncomingAck(const ReceivedPacketInfo& received_info,
  86                      QuicTime ack_receive_time);
  87
  88   // Discards any information for the packet corresponding to |sequence_number|.
  89   // If this packet has been retransmitted, information on those packets
  90   // will be discarded as well.  Also discards it from the congestion window if
  91   // it is present.
  92   void DiscardUnackedPacket(QuicPacketSequenceNumber sequence_number);
  93
  94   // Returns true if the non-FEC packet |sequence_number| is unacked.
  95   bool IsUnacked(QuicPacketSequenceNumber sequence_number) const;
  96
  97   // Requests retransmission of all unacked packets of |retransmission_type|.
  98   void RetransmitUnackedPackets(RetransmissionType retransmission_type);
  99
 100   // Returns true if the unacked packet |sequence_number| has retransmittable
 101   // frames.  This will only return false if the packet has been acked, if a
 102   // previous transmission of this packet was ACK'd, or if this packet has been
 103   // retransmitted as with different sequence number.
 104   bool HasRetransmittableFrames(QuicPacketSequenceNumber sequence_number) const;
 105
 106   // Returns true if there are pending retransmissions.
 107   bool HasPendingRetransmissions() const;
 108
 109   // Retrieves the next pending retransmission.
 110   PendingRetransmission NextPendingRetransmission();
 111
 112   bool HasUnackedPackets() const;
 113
 114   // Returns the smallest sequence number of a serialized packet which has not
 115   // been acked by the peer.  If there are no unacked packets, returns 0.
 116   QuicPacketSequenceNumber GetLeastUnackedSentPacket() const;
 117
 118   // Called when a congestion feedback frame is received from peer.
 119   virtual void OnIncomingQuicCongestionFeedbackFrame(
 120       const QuicCongestionFeedbackFrame& frame,
 121       const QuicTime& feedback_receive_time);
 122
 123   // Called when we have sent bytes to the peer.  This informs the manager both
 124   // the number of bytes sent and if they were retransmitted.  Returns true if
 125   // the sender should reset the retransmission timer.
 126   virtual bool OnPacketSent(QuicPacketSequenceNumber sequence_number,
 127                             QuicTime sent_time,
 128                             QuicByteCount bytes,
 129                             TransmissionType transmission_type,
 130                             HasRetransmittableData has_retransmittable_data);
 131
 132   // Called when the retransmission timer expires.
 133   virtual void OnRetransmissionTimeout();
 134
 135   // Calculate the time until we can send the next packet to the wire.
 136   // Note 1: When kUnknownWaitTime is returned, there is no need to poll
 137   // TimeUntilSend again until we receive an OnIncomingAckFrame event.
 138   // Note 2: Send algorithms may or may not use |retransmit| in their
 139   // calculations.
 140   virtual QuicTime::Delta TimeUntilSend(QuicTime now,
 141                                         TransmissionType transmission_type,
 142                                         HasRetransmittableData retransmittable,
 143                                         IsHandshake handshake);
 144
 145   // Returns amount of time for delayed ack timer.
 146   const QuicTime::Delta DelayedAckTime() const;
 147
 148   // Returns the current delay for the retransmission timer, which may send
 149   // either a tail loss probe or do a full RTO.  Returns QuicTime::Zero() if
 150   // there are no retransmittable packets.
 151   const QuicTime GetRetransmissionTime() const;
 152
 153   // Returns the estimated smoothed RTT calculated by the congestion algorithm.
 154   const QuicTime::Delta SmoothedRtt() const;
 155
 156   // Returns the estimated bandwidth calculated by the congestion algorithm.
 157   QuicBandwidth BandwidthEstimate() const;
 158
 159   // Returns the size of the current congestion window in bytes.  Note, this is
 160   // not the *available* window.  Some send algorithms may not use a congestion
 161   // window and will return 0.
 162   QuicByteCount GetCongestionWindow() const;
 163
 164   // Enables pacing if it has not already been enabled, and if
 165   // FLAGS_enable_quic_pacing is set.
 166   void MaybeEnablePacing();
 167
 168   bool using_pacing() const { return using_pacing_; }
 169
 170  private:
 171   friend class test::QuicConnectionPeer;
 172   friend class test::QuicSentPacketManagerPeer;
 173
 174   enum ReceivedByPeer {
 175     RECEIVED_BY_PEER,
 176     NOT_RECEIVED_BY_PEER,
 177   };
 178
 179   // The retransmission timer is a single timer which switches modes depending
 180   // upon connection state.
 181   enum RetransmissionTimeoutMode {
 182     // A conventional TCP style RTO.
 183     RTO_MODE,
 184     // A tail loss probe.  By default, QUIC sends up to two before RTOing.
 185     TLP_MODE,
 186     // Retransmission of handshake packets prior to handshake completion.
 187     HANDSHAKE_MODE,
 188     // Re-invoke the loss detection when a packet is not acked before the
 189     // loss detection algorithm expects.
 190     LOSS_MODE,
 191   };
 192
 193   typedef linked_hash_map<QuicPacketSequenceNumber,
 194                           TransmissionType> PendingRetransmissionMap;
 195
 196   // Process the incoming ack looking for newly ack'd data packets.
 197   void HandleAckForSentPackets(const ReceivedPacketInfo& received_info);
 198
 199   // Called when a packet is timed out, such as an RTO.  Removes the bytes from
 200   // the congestion manager, but does not change the congestion window size.
 201   void OnPacketAbandoned(QuicPacketSequenceNumber sequence_number);
 202
 203   // Returns the current retransmission mode.
 204   RetransmissionTimeoutMode GetRetransmissionMode() const;
 205
 206   // Retransmits all crypto stream packets.
 207   void RetransmitCryptoPackets();
 208
 209   // Retransmits the oldest pending packet.
 210   void RetransmitOldestPacket();
 211
 212   // Retransmits all the packets and abandons by invoking a full RTO.
 213   void RetransmitAllPackets();
 214
 215   // Returns the timer for retransmitting crypto handshake packets.
 216   const QuicTime::Delta GetCryptoRetransmissionDelay() const;
 217
 218   // Returns the timer for a new tail loss probe.
 219   const QuicTime::Delta GetTailLossProbeDelay() const;
 220
 221   // Returns the retransmission timeout, after which a full RTO occurs.
 222   const QuicTime::Delta GetRetransmissionDelay() const;
 223
 224   // Update the RTT if the ack is for the largest acked sequence number.
 225   void MaybeUpdateRTT(const ReceivedPacketInfo& received_info,
 226                       const QuicTime& ack_receive_time);
 227
 228   // Chooses whether to nack retransmit any packets based on the receipt info.
 229   // All acks have been handled before this method is invoked.
 230   void MaybeRetransmitOnAckFrame(const ReceivedPacketInfo& received_info,
 231                                  const QuicTime& ack_receive_time);
 232
 233   // Invokes the loss detection algorithm and loses and retransmits packets if
 234   // necessary.
 235   void InvokeLossDetection(QuicTime time);
 236
 237   // Marks |sequence_number| as being fully handled, either due to receipt
 238   // by the peer, or having been discarded as indecipherable.  Returns an
 239   // iterator to the next remaining unacked packet.
 240   QuicUnackedPacketMap::const_iterator MarkPacketHandled(
 241       QuicPacketSequenceNumber sequence_number,
 242       ReceivedByPeer received_by_peer);
 243
 244   // Request that |sequence_number| be retransmitted after the other pending
 245   // retransmissions.  Does not add it to the retransmissions if it's already
 246   // a pending retransmission.
 247   void MarkForRetransmission(QuicPacketSequenceNumber sequence_number,
 248                              TransmissionType transmission_type);
 249
 250   // Newly serialized retransmittable and fec packets are added to this map,
 251   // which contains owning pointers to any contained frames.  If a packet is
 252   // retransmitted, this map will contain entries for both the old and the new
 253   // packet. The old packet's retransmittable frames entry will be NULL, while
 254   // the new packet's entry will contain the frames to retransmit.
 255   // If the old packet is acked before the new packet, then the old entry will
 256   // be removed from the map and the new entry's retransmittable frames will be
 257   // set to NULL.
 258   QuicUnackedPacketMap unacked_packets_;
 259
 260   // Pending retransmissions which have not been packetized and sent yet.
 261   PendingRetransmissionMap pending_retransmissions_;
 262
 263   // Tracks if the connection was created by the server.
 264   bool is_server_;
 265
 266   // An AckNotifier can register to be informed when ACKs have been received for
 267   // all packets that a given block of data was sent in. The AckNotifierManager
 268   // maintains the currently active notifiers.
 269   AckNotifierManager ack_notifier_manager_;
 270
 271   const QuicClock* clock_;
 272   QuicConnectionStats* stats_;
 273   RttStats rtt_stats_;
 274   scoped_ptr<SendAlgorithmInterface> send_algorithm_;
 275   scoped_ptr<LossDetectionInterface> loss_algorithm_;
 276
 277   QuicPacketSequenceNumber largest_observed_;  // From the most recent ACK.
 278   // Number of times the RTO timer has fired in a row without receiving an ack.
 279   size_t consecutive_rto_count_;
 280   // Number of times the tail loss probe has been sent.
 281   size_t consecutive_tlp_count_;
 282   // Number of times the crypto handshake has been retransmitted.
 283   size_t consecutive_crypto_retransmission_count_;
 284   // Maximum number of tail loss probes to send before firing an RTO.
 285   size_t max_tail_loss_probes_;
 286   bool using_pacing_;
 287
 288   DISALLOW_COPY_AND_ASSIGN(QuicSentPacketManager);
 289 };
 290
 291 }  // namespace net
 292
 293 #endif  // NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_