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
24namespace net {
25
26namespace test {
27class QuicConnectionPeer;
28class QuicSentPacketManagerPeer;
29}  // namespace test
30
31class QuicClock;
32class QuicConfig;
33struct 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.
40class 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