src/net/quic/quic_received_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 // Manages the packet entropy calculation for both sent and received packets
   6 // for a connection.
   7
   8 #ifndef NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
   9 #define NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_
  10
  11 #include "net/quic/congestion_control/receive_algorithm_interface.h"
  12 #include "net/quic/quic_framer.h"
  13 #include "net/quic/quic_protocol.h"
  14
  15 namespace net {
  16
  17 namespace test {
  18 class EntropyTrackerPeer;
  19 class QuicConnectionPeer;
  20 class QuicReceivedPacketManagerPeer;
  21 }  // namespace test
  22
  23 struct QuicConnectionStats;
  24
  25 // Records all received packets by a connection and tracks their entropy.
  26 // Also calculates the correct entropy for the framer when it truncates an ack
  27 // frame being serialized.
  28 class NET_EXPORT_PRIVATE QuicReceivedPacketManager :
  29     public QuicReceivedEntropyHashCalculatorInterface {
  30  public:
  31   class NET_EXPORT_PRIVATE EntropyTracker {
  32    public:
  33     EntropyTracker();
  34     ~EntropyTracker();
  35
  36     // Compute the XOR of the entropy of all received packets up to
  37     // and including sequence_number.
  38     // Requires that either:
  39     //   sequence_number == largest_observed_
  40     // or:
  41     //   sequence_number > first_gap_ &&
  42     //   sequence_number < largest_observed_ &&
  43     //   sequence_number in packets_entropy_
  44     QuicPacketEntropyHash EntropyHash(
  45         QuicPacketSequenceNumber sequence_number) const;
  46
  47     // Record the received entropy hash against |sequence_number|.
  48     // Performs garbage collection to advance first_gap_ if
  49     // sequence_number == first_gap_.
  50     void RecordPacketEntropyHash(QuicPacketSequenceNumber sequence_number,
  51                                  QuicPacketEntropyHash entropy_hash);
  52
  53     // Sets the entropy hash up to but not including a sequence number based
  54     // on the hash provided by a StopWaiting frame.  Clears older packet
  55     // entropy entries and performs garbage collection up to the first gap.
  56     void SetCumulativeEntropyUpTo(QuicPacketSequenceNumber sequence_number,
  57                                   QuicPacketEntropyHash entropy_hash);
  58
  59    private:
  60     friend class test::EntropyTrackerPeer;
  61
  62     typedef std::map<QuicPacketSequenceNumber,
  63                      QuicPacketEntropyHash> ReceivedEntropyMap;
  64
  65     // Recomputes first_gap_ and removes packets_entropy_ entries that are no
  66     // longer needed to compute EntropyHash.
  67     void AdvanceFirstGapAndGarbageCollectEntropyMap();
  68
  69     // TODO(satyamshekhar): Can be optimized using an interval set like data
  70     // structure.
  71     // Map of received sequence numbers to their corresponding entropy.
  72     // Stores an entry for every received packet whose sequence_number is larger
  73     // than first_gap_.  Packets without the entropy bit set have an entropy
  74     // value of 0.
  75     // TODO(ianswett): When the entropy flag is off, the entropy
  76     // should not be 0.
  77     ReceivedEntropyMap packets_entropy_;
  78
  79     // Cumulative hash of entropy of all received packets.
  80     QuicPacketEntropyHash packets_entropy_hash_;
  81
  82     // Sequence number of the first packet that we do not know the entropy of.
  83     // If there are no gaps in the received packet sequence,
  84     // packets_entropy_ will be empty and first_gap_ will be equal to
  85     // 'largest_observed_ + 1' since that's the first packet for which
  86     // entropy is unknown.  If there are gaps, packets_entropy_ will
  87     // contain entries for all received packets with sequence_number >
  88     // first_gap_.
  89     QuicPacketSequenceNumber first_gap_;
  90
  91     // Sequence number of the largest observed packet.
  92     QuicPacketSequenceNumber largest_observed_;
  93
  94     DISALLOW_COPY_AND_ASSIGN(EntropyTracker);
  95   };
  96
  97   explicit QuicReceivedPacketManager(CongestionFeedbackType congestion_type,
  98                                      QuicConnectionStats* stats);
  99   virtual ~QuicReceivedPacketManager();
 100
 101   // Updates the internal state concerning which packets have been received.
 102   // bytes: the packet size in bytes including Quic Headers.
 103   // header: the packet header.
 104   // timestamp: the arrival time of the packet.
 105   void RecordPacketReceived(QuicByteCount bytes,
 106                             const QuicPacketHeader& header,
 107                             QuicTime receipt_time);
 108
 109   void RecordPacketRevived(QuicPacketSequenceNumber sequence_number);
 110
 111   // Checks whether |sequence_number| is missing and less than largest observed.
 112   bool IsMissing(QuicPacketSequenceNumber sequence_number);
 113
 114   // Checks if we're still waiting for the packet with |sequence_number|.
 115   bool IsAwaitingPacket(QuicPacketSequenceNumber sequence_number);
 116
 117   // Update the |ack_frame| for an outgoing ack.
 118   void UpdateReceivedPacketInfo(QuicAckFrame* ack_frame,
 119                                 QuicTime approximate_now);
 120
 121   // Should be called before sending an ACK packet, to decide if we need
 122   // to attach a QuicCongestionFeedbackFrame block.
 123   // Returns false if no QuicCongestionFeedbackFrame block is needed.
 124   // Otherwise fills in feedback and returns true.
 125   virtual bool GenerateCongestionFeedback(
 126       QuicCongestionFeedbackFrame* feedback);
 127
 128   // QuicReceivedEntropyHashCalculatorInterface
 129   // Called by QuicFramer, when the outgoing ack gets truncated, to recalculate
 130   // the received entropy hash for the truncated ack frame.
 131   virtual QuicPacketEntropyHash EntropyHash(
 132       QuicPacketSequenceNumber sequence_number) const OVERRIDE;
 133
 134   // Updates internal state based on |ack_frame|.
 135   void UpdatePacketInformationReceivedByPeer(const QuicAckFrame& ack_frame);
 136   // Updates internal state based on |stop_waiting|.
 137   void UpdatePacketInformationSentByPeer(
 138       const QuicStopWaitingFrame& stop_waiting);
 139
 140   // Returns whether the peer is missing packets.
 141   bool HasMissingPackets();
 142
 143   // Returns true when there are new missing packets to be reported within 3
 144   // packets of the largest observed.
 145   bool HasNewMissingPackets();
 146
 147   QuicPacketSequenceNumber peer_largest_observed_packet() {
 148     return peer_largest_observed_packet_;
 149   }
 150
 151   QuicPacketSequenceNumber least_packet_awaited_by_peer() {
 152     return least_packet_awaited_by_peer_;
 153   }
 154
 155   QuicPacketSequenceNumber peer_least_packet_awaiting_ack() {
 156     return peer_least_packet_awaiting_ack_;
 157   }
 158
 159  private:
 160   friend class test::QuicConnectionPeer;
 161   friend class test::QuicReceivedPacketManagerPeer;
 162
 163   // Deletes all missing packets before least unacked. The connection won't
 164   // process any packets with sequence number before |least_unacked| that it
 165   // received after this call. Returns true if there were missing packets before
 166   // |least_unacked| unacked, false otherwise.
 167   bool DontWaitForPacketsBefore(QuicPacketSequenceNumber least_unacked);
 168
 169   // Tracks entropy hashes of received packets.
 170   EntropyTracker entropy_tracker_;
 171
 172   // Track some peer state so we can do less bookkeeping.
 173   // Largest sequence number that the peer has observed. Mostly received,
 174   // missing in case of truncated acks.
 175   QuicPacketSequenceNumber peer_largest_observed_packet_;
 176   // Least sequence number which the peer is still waiting for.
 177   QuicPacketSequenceNumber least_packet_awaited_by_peer_;
 178   // Least sequence number of the the packet sent by the peer for which it
 179   // hasn't received an ack.
 180   QuicPacketSequenceNumber peer_least_packet_awaiting_ack_;
 181
 182   // Received packet information used to produce acks.
 183   QuicAckFrame ack_frame_;
 184
 185   // The time we received the largest_observed sequence number, or zero if
 186   // no sequence numbers have been received since UpdateReceivedPacketInfo.
 187   // Needed for calculating delta_time_largest_observed.
 188   QuicTime time_largest_observed_;
 189
 190   scoped_ptr<ReceiveAlgorithmInterface> receive_algorithm_;
 191
 192   QuicConnectionStats* stats_;
 193
 194   DISALLOW_COPY_AND_ASSIGN(QuicReceivedPacketManager);
 195 };
 196
 197 }  // namespace net
 198
 199 #endif  // NET_QUIC_QUIC_RECEIVED_PACKET_MANAGER_H_