Home | History | Annotate | Download | only in quic
      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 <map>
      9 #include <set>
     10 #include <utility>
     11 #include <vector>
     12 
     13 #include "base/containers/hash_tables.h"
     14 #include "base/memory/scoped_ptr.h"
     15 #include "net/base/linked_hash_map.h"
     16 #include "net/quic/congestion_control/loss_detection_interface.h"
     17 #include "net/quic/congestion_control/rtt_stats.h"
     18 #include "net/quic/congestion_control/send_algorithm_interface.h"
     19 #include "net/quic/quic_ack_notifier_manager.h"
     20 #include "net/quic/quic_protocol.h"
     21 #include "net/quic/quic_sustained_bandwidth_recorder.h"
     22 #include "net/quic/quic_unacked_packet_map.h"
     23 
     24 namespace net {
     25 
     26 namespace test {
     27 class QuicConnectionPeer;
     28 class QuicSentPacketManagerPeer;
     29 }  // namespace test
     30 
     31 class QuicClock;
     32 class QuicConfig;
     33 struct QuicConnectionStats;
     34 
     35 // Class which tracks the set of packets sent on a QUIC connection and contains
     36 // a send algorithm to decide when to send new packets.  It keeps track of any
     37 // retransmittable data associated with each packet. If a packet is
     38 // retransmitted, it will keep track of each version of a packet so that if a
     39 // previous transmission is acked, the data will not be retransmitted.
     40 class NET_EXPORT_PRIVATE QuicSentPacketManager {
     41  public:
     42   // Interface which gets callbacks from the QuicSentPacketManager at
     43   // interesting points.  Implementations must not mutate the state of
     44   // the packet manager or connection as a result of these callbacks.
     45   class NET_EXPORT_PRIVATE DebugDelegate {
     46    public:
     47     virtual ~DebugDelegate() {}
     48 
     49     // Called when a spurious retransmission is detected.
     50     virtual void OnSpuriousPacketRetransmition(
     51         TransmissionType transmission_type,
     52         QuicByteCount byte_size) {}
     53 
     54     virtual void OnSentPacket(
     55         QuicPacketSequenceNumber sequence_number,
     56         QuicTime sent_time,
     57         QuicByteCount bytes,
     58         TransmissionType transmission_type) {}
     59 
     60     virtual void OnRetransmittedPacket(
     61         QuicPacketSequenceNumber old_sequence_number,
     62         QuicPacketSequenceNumber new_sequence_number,
     63         TransmissionType transmission_type,
     64         QuicTime time) {}
     65 
     66     virtual void OnIncomingAck(
     67         const QuicAckFrame& ack_frame,
     68         QuicTime ack_receive_time,
     69         QuicPacketSequenceNumber largest_observed,
     70         bool largest_observed_acked,
     71         QuicPacketSequenceNumber least_unacked_sent_packet) {}
     72 
     73     virtual void OnSerializedPacket(
     74         const SerializedPacket& packet) {}
     75   };
     76 
     77   // Interface which gets callbacks from the QuicSentPacketManager when
     78   // network-related state changes. Implementations must not mutate the
     79   // state of the packet manager as a result of these callbacks.
     80   class NET_EXPORT_PRIVATE NetworkChangeVisitor {
     81    public:
     82     virtual ~NetworkChangeVisitor() {}
     83 
     84     // Called when congestion window may have changed.
     85     virtual void OnCongestionWindowChange(QuicByteCount congestion_window) = 0;
     86     // TODO(jri): Add OnRttStatsChange() to this class as well.
     87   };
     88 
     89   // Struct to store the pending retransmission information.
     90   struct PendingRetransmission {
     91     PendingRetransmission(QuicPacketSequenceNumber sequence_number,
     92                           TransmissionType transmission_type,
     93                           const RetransmittableFrames& retransmittable_frames,
     94                           QuicSequenceNumberLength sequence_number_length)
     95             : sequence_number(sequence_number),
     96               transmission_type(transmission_type),
     97               retransmittable_frames(retransmittable_frames),
     98               sequence_number_length(sequence_number_length) {
     99         }
    100 
    101         QuicPacketSequenceNumber sequence_number;
    102         TransmissionType transmission_type;
    103         const RetransmittableFrames& retransmittable_frames;
    104         QuicSequenceNumberLength sequence_number_length;
    105   };
    106 
    107   QuicSentPacketManager(bool is_server,
    108                         const QuicClock* clock,
    109                         QuicConnectionStats* stats,
    110                         CongestionControlType congestion_control_type,
    111                         LossDetectionType loss_type);
    112   virtual ~QuicSentPacketManager();
    113 
    114   virtual void SetFromConfig(const QuicConfig& config);
    115 
    116   void SetHandshakeConfirmed() { handshake_confirmed_ = true; }
    117 
    118   // Called when a new packet is serialized.  If the packet contains
    119   // retransmittable data, it will be added to the unacked packet map.
    120   void OnSerializedPacket(const SerializedPacket& serialized_packet);
    121 
    122   // Called when a packet is retransmitted with a new sequence number.
    123   // Replaces the old entry in the unacked packet map with the new
    124   // sequence number.
    125   void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,
    126                              QuicPacketSequenceNumber new_sequence_number);
    127 
    128   // Processes the incoming ack.
    129   void OnIncomingAck(const QuicAckFrame& ack_frame,
    130                      QuicTime ack_receive_time);
    131 
    132   // Returns true if the non-FEC packet |sequence_number| is unacked.
    133   bool IsUnacked(QuicPacketSequenceNumber sequence_number) const;
    134 
    135   // Requests retransmission of all unacked packets of |retransmission_type|.
    136   void RetransmitUnackedPackets(TransmissionType retransmission_type);
    137 
    138   // Retransmits the oldest pending packet there is still a tail loss probe
    139   // pending.  Invoked after OnRetransmissionTimeout.
    140   bool MaybeRetransmitTailLossProbe();
    141 
    142   // Removes the retransmittable frames from all unencrypted packets to ensure
    143   // they don't get retransmitted.
    144   void NeuterUnencryptedPackets();
    145 
    146   // Returns true if the unacked packet |sequence_number| has retransmittable
    147   // frames.  This will only return false if the packet has been acked, if a
    148   // previous transmission of this packet was ACK'd, or if this packet has been
    149   // retransmitted as with different sequence number.
    150   bool HasRetransmittableFrames(QuicPacketSequenceNumber sequence_number) const;
    151 
    152   // Returns true if there are pending retransmissions.
    153   bool HasPendingRetransmissions() const;
    154 
    155   // Retrieves the next pending retransmission.
    156   PendingRetransmission NextPendingRetransmission();
    157 
    158   bool HasUnackedPackets() const;
    159 
    160   // Returns the smallest sequence number of a serialized packet which has not
    161   // been acked by the peer.
    162   QuicPacketSequenceNumber GetLeastUnacked() const;
    163 
    164   // Called when a congestion feedback frame is received from peer.
    165   virtual void OnIncomingQuicCongestionFeedbackFrame(
    166       const QuicCongestionFeedbackFrame& frame,
    167       const QuicTime& feedback_receive_time);
    168 
    169   // Called when we have sent bytes to the peer.  This informs the manager both
    170   // the number of bytes sent and if they were retransmitted.  Returns true if
    171   // the sender should reset the retransmission timer.
    172   virtual bool OnPacketSent(QuicPacketSequenceNumber sequence_number,
    173                             QuicTime sent_time,
    174                             QuicByteCount bytes,
    175                             TransmissionType transmission_type,
    176                             HasRetransmittableData has_retransmittable_data);
    177 
    178   // Called when the retransmission timer expires.
    179   virtual void OnRetransmissionTimeout();
    180 
    181   // Calculate the time until we can send the next packet to the wire.
    182   // Note 1: When kUnknownWaitTime is returned, there is no need to poll
    183   // TimeUntilSend again until we receive an OnIncomingAckFrame event.
    184   // Note 2: Send algorithms may or may not use |retransmit| in their
    185   // calculations.
    186   virtual QuicTime::Delta TimeUntilSend(QuicTime now,
    187                                         HasRetransmittableData retransmittable);
    188 
    189   // Returns amount of time for delayed ack timer.
    190   const QuicTime::Delta DelayedAckTime() const;
    191 
    192   // Returns the current delay for the retransmission timer, which may send
    193   // either a tail loss probe or do a full RTO.  Returns QuicTime::Zero() if
    194   // there are no retransmittable packets.
    195   const QuicTime GetRetransmissionTime() const;
    196 
    197   const RttStats* GetRttStats() const;
    198 
    199   // Returns the estimated bandwidth calculated by the congestion algorithm.
    200   QuicBandwidth BandwidthEstimate() const;
    201 
    202   // Returns true if the current instantaneous bandwidth estimate is reliable.
    203   bool HasReliableBandwidthEstimate() const;
    204 
    205   const QuicSustainedBandwidthRecorder& SustainedBandwidthRecorder() const;
    206 
    207   // Returns the size of the current congestion window in bytes.  Note, this is
    208   // not the *available* window.  Some send algorithms may not use a congestion
    209   // window and will return 0.
    210   QuicByteCount GetCongestionWindow() const;
    211 
    212   // Returns the size of the slow start congestion window in bytes,
    213   // aka ssthresh.  Some send algorithms do not define a slow start
    214   // threshold and will return 0.
    215   QuicByteCount GetSlowStartThreshold() const;
    216 
    217   // Enables pacing if it has not already been enabled.
    218   void EnablePacing();
    219 
    220   bool using_pacing() const { return using_pacing_; }
    221 
    222   void set_debug_delegate(DebugDelegate* debug_delegate) {
    223     debug_delegate_ = debug_delegate;
    224   }
    225 
    226   QuicPacketSequenceNumber largest_observed() const {
    227     return unacked_packets_.largest_observed();
    228   }
    229 
    230   QuicPacketSequenceNumber least_packet_awaited_by_peer() {
    231     return least_packet_awaited_by_peer_;
    232   }
    233 
    234   void set_network_change_visitor(NetworkChangeVisitor* visitor) {
    235     DCHECK(!network_change_visitor_);
    236     DCHECK(visitor);
    237     network_change_visitor_ = visitor;
    238   }
    239 
    240   size_t consecutive_rto_count() const {
    241     return consecutive_rto_count_;
    242   }
    243 
    244   size_t consecutive_tlp_count() const {
    245     return consecutive_tlp_count_;
    246   }
    247 
    248  private:
    249   friend class test::QuicConnectionPeer;
    250   friend class test::QuicSentPacketManagerPeer;
    251 
    252   // The retransmission timer is a single timer which switches modes depending
    253   // upon connection state.
    254   enum RetransmissionTimeoutMode {
    255     // A conventional TCP style RTO.
    256     RTO_MODE,
    257     // A tail loss probe.  By default, QUIC sends up to two before RTOing.
    258     TLP_MODE,
    259     // Retransmission of handshake packets prior to handshake completion.
    260     HANDSHAKE_MODE,
    261     // Re-invoke the loss detection when a packet is not acked before the
    262     // loss detection algorithm expects.
    263     LOSS_MODE,
    264   };
    265 
    266   typedef linked_hash_map<QuicPacketSequenceNumber,
    267                           TransmissionType> PendingRetransmissionMap;
    268 
    269   // Updates the least_packet_awaited_by_peer.
    270   void UpdatePacketInformationReceivedByPeer(const QuicAckFrame& ack_frame);
    271 
    272   // Process the incoming ack looking for newly ack'd data packets.
    273   void HandleAckForSentPackets(const QuicAckFrame& ack_frame);
    274 
    275   // Returns the current retransmission mode.
    276   RetransmissionTimeoutMode GetRetransmissionMode() const;
    277 
    278   // Retransmits all crypto stream packets.
    279   void RetransmitCryptoPackets();
    280 
    281   // Retransmits all the packets and abandons by invoking a full RTO.
    282   void RetransmitAllPackets();
    283 
    284   // Returns the timer for retransmitting crypto handshake packets.
    285   const QuicTime::Delta GetCryptoRetransmissionDelay() const;
    286 
    287   // Returns the timer for a new tail loss probe.
    288   const QuicTime::Delta GetTailLossProbeDelay() const;
    289 
    290   // Returns the retransmission timeout, after which a full RTO occurs.
    291   const QuicTime::Delta GetRetransmissionDelay() const;
    292 
    293   // Update the RTT if the ack is for the largest acked sequence number.
    294   // Returns true if the rtt was updated.
    295   bool MaybeUpdateRTT(const QuicAckFrame& ack_frame,
    296                       const QuicTime& ack_receive_time);
    297 
    298   // Invokes the loss detection algorithm and loses and retransmits packets if
    299   // necessary.
    300   void InvokeLossDetection(QuicTime time);
    301 
    302   // Invokes OnCongestionEvent if |rtt_updated| is true, there are pending acks,
    303   // or pending losses.  Clears pending acks and pending losses afterwards.
    304   // |bytes_in_flight| is the number of bytes in flight before the losses or
    305   // acks.
    306   void MaybeInvokeCongestionEvent(bool rtt_updated,
    307                                   QuicByteCount bytes_in_flight);
    308 
    309   // Marks |sequence_number| as having been revived by the peer, but not
    310   // received, so the packet remains pending if it is and the congestion control
    311   // does not consider the packet acked.
    312   void MarkPacketRevived(QuicPacketSequenceNumber sequence_number,
    313                          QuicTime::Delta delta_largest_observed);
    314 
    315   // Removes the retransmittability and pending properties from the packet at
    316   // |it| due to receipt by the peer.  Returns an iterator to the next remaining
    317   // unacked packet.
    318   void MarkPacketHandled(QuicPacketSequenceNumber sequence_number,
    319                          const TransmissionInfo& info,
    320                          QuicTime::Delta delta_largest_observed);
    321 
    322   // Request that |sequence_number| be retransmitted after the other pending
    323   // retransmissions.  Does not add it to the retransmissions if it's already
    324   // a pending retransmission.
    325   void MarkForRetransmission(QuicPacketSequenceNumber sequence_number,
    326                              TransmissionType transmission_type);
    327 
    328   // Notify observers about spurious retransmits.
    329   void RecordSpuriousRetransmissions(
    330       const SequenceNumberList& all_transmissions,
    331       QuicPacketSequenceNumber acked_sequence_number);
    332 
    333   // Newly serialized retransmittable and fec packets are added to this map,
    334   // which contains owning pointers to any contained frames.  If a packet is
    335   // retransmitted, this map will contain entries for both the old and the new
    336   // packet. The old packet's retransmittable frames entry will be NULL, while
    337   // the new packet's entry will contain the frames to retransmit.
    338   // If the old packet is acked before the new packet, then the old entry will
    339   // be removed from the map and the new entry's retransmittable frames will be
    340   // set to NULL.
    341   QuicUnackedPacketMap unacked_packets_;
    342 
    343   // Pending retransmissions which have not been packetized and sent yet.
    344   PendingRetransmissionMap pending_retransmissions_;
    345 
    346   // Tracks if the connection was created by the server.
    347   bool is_server_;
    348 
    349   // An AckNotifier can register to be informed when ACKs have been received for
    350   // all packets that a given block of data was sent in. The AckNotifierManager
    351   // maintains the currently active notifiers.
    352   AckNotifierManager ack_notifier_manager_;
    353 
    354   const QuicClock* clock_;
    355   QuicConnectionStats* stats_;
    356   DebugDelegate* debug_delegate_;
    357   NetworkChangeVisitor* network_change_visitor_;
    358   RttStats rtt_stats_;
    359   scoped_ptr<SendAlgorithmInterface> send_algorithm_;
    360   scoped_ptr<LossDetectionInterface> loss_algorithm_;
    361 
    362   // Least sequence number which the peer is still waiting for.
    363   QuicPacketSequenceNumber least_packet_awaited_by_peer_;
    364 
    365   // Tracks the first RTO packet.  If any packet before that packet gets acked,
    366   // it indicates the RTO was spurious and should be reversed(F-RTO).
    367   QuicPacketSequenceNumber first_rto_transmission_;
    368   // Number of times the RTO timer has fired in a row without receiving an ack.
    369   size_t consecutive_rto_count_;
    370   // Number of times the tail loss probe has been sent.
    371   size_t consecutive_tlp_count_;
    372   // Number of times the crypto handshake has been retransmitted.
    373   size_t consecutive_crypto_retransmission_count_;
    374   // Number of pending transmissions of TLP or crypto packets.
    375   size_t pending_timer_transmission_count_;
    376   // Maximum number of tail loss probes to send before firing an RTO.
    377   size_t max_tail_loss_probes_;
    378   bool using_pacing_;
    379 
    380   // Vectors packets acked and lost as a result of the last congestion event.
    381   SendAlgorithmInterface::CongestionVector packets_acked_;
    382   SendAlgorithmInterface::CongestionVector packets_lost_;
    383 
    384   // Set to true after the crypto handshake has successfully completed. After
    385   // this is true we no longer use HANDSHAKE_MODE, and further frames sent on
    386   // the crypto stream (i.e. SCUP messages) are treated like normal
    387   // retransmittable frames.
    388   bool handshake_confirmed_;
    389 
    390   // Records bandwidth from server to client in normal operation, over periods
    391   // of time with no loss events.
    392   QuicSustainedBandwidthRecorder sustained_bandwidth_recorder_;
    393 
    394   DISALLOW_COPY_AND_ASSIGN(QuicSentPacketManager);
    395 };
    396 
    397 }  // namespace net
    398 
    399 #endif  // NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_
    400