Adding transmission times for every QUIC packet received in the AckFrame.

net/quic/quic_connection.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/quic/quic_connection.h"
 
 #include <algorithm>
 
 #include "base/logging.h"
 #include "base/stl_util.h"
 #include "net/base/net_errors.h"
 #include "net/quic/congestion_control/quic_receipt_metrics_collector.h"
 #include "net/quic/congestion_control/quic_send_scheduler.h"
 #include "net/quic/quic_utils.h"
 
 using base::hash_map;
 using base::hash_set;
 using base::StringPiece;
 using std::list;
 using std::min;
 using std::vector;
 using std::set;
 
 namespace net {
 
 // An arbitrary number we'll probably want to tune.

[jar (doing other things), 2012/11/29 21:51:40]

nit: Please add a comment explaining the intent of the constant, rather than
just saying it is arbitrary.  I had some (mis)understanding with the old name,
but given this transition, I'm left unclear as to the intent (original, or
current).

[Ian Swett, 2012/12/04 21:40:19]

I changed the naming and check back to the old approach and added a comment in
the cleanup CL, but this number seems high to me, even as a starting point. 
Ryan, any thoughts?

[Ryan Hamilton, 2012/12/04 21:52:54]

Not really.  I suspect that until we have flow control sorted out it might well
be possible to end up with more dropped packets than we might expected, but
honestly I'm not sure what the number threshold is.

-const QuicPacketSequenceNumber kMaxUnackedPackets = 5000u;
+const QuicPacketSequenceNumber kMaxAckedPackets = 5000u;
 
 // The amount of time we wait before resending a packet.
 const int64 kDefaultResendTimeMs = 500;
 
 bool Near(QuicPacketSequenceNumber a, QuicPacketSequenceNumber b) {
   QuicPacketSequenceNumber delta = (a > b) ? a - b : b - a;
-  return delta <= kMaxUnackedPackets;
+  return delta <= kMaxAckedPackets;
 }
 
 QuicConnection::QuicConnection(QuicGuid guid,
                                IPEndPoint address,
                                QuicConnectionHelperInterface* helper)
     : helper_(helper),
       framer_(QuicDecrypter::Create(kNULL), QuicEncrypter::Create(kNULL)),
       clock_(helper->GetClock()),
       guid_(guid),
       peer_address_(address),
@@ skipping 53 matching lines @@
 bool QuicConnection::OnPacketHeader(const QuicPacketHeader& header) {
   if (!Near(header.packet_sequence_number,
             last_header_.packet_sequence_number)) {
     DLOG(INFO) << "Packet out of bounds.  Discarding";
     return false;
   }
 
   ReceivedPacketInfo info = outgoing_ack_.received_info;
   // If this packet has already been seen, or that the sender
   // has told us will not be resent, then stop processing the packet.
-  if (header.packet_sequence_number <= info.largest_received &&
-      info.missing_packets.count(header.packet_sequence_number) != 1) {
+  if (info.ContainsAck(header.packet_sequence_number)) {
     return false;
   }
 
   last_header_ = header;
   return true;
 }
 
 void QuicConnection::OnFecProtectedPayload(StringPiece payload) {
   DCHECK_NE(0, last_header_.fec_group);
   QuicFecGroup* group = GetFecGroup();
@@ skipping 41 matching lines @@
 bool QuicConnection::ValidateAckFrame(const QuicAckFrame& incoming_ack) {
   if (incoming_ack.received_info.largest_received >
       packet_creator_.sequence_number()) {
     DLOG(ERROR) << "Client acked unsent packet:"
                 << incoming_ack.received_info.largest_received << " vs "
                 << packet_creator_.sequence_number();
     // We got an error for data we have not sent.  Error out.
     return false;
   }
 
-  // We can't have too many missing or retransmitting packets, or our ack
-  // frames go over kMaxPacketSize.
-  DCHECK_LT(incoming_ack.received_info.missing_packets.size(),
-            kMaxUnackedPackets);
-  DCHECK_LT(incoming_ack.sent_info.non_retransmiting.size(),
-            kMaxUnackedPackets);
+  // We can't have too many acked packets, or our ack frames go over

[jar (doing other things), 2012/11/29 21:51:40]

nit: This limitation is probably on the count of selectively NACKed packets, so
I don't understand the comment.

Alyssa also advocated for a run-length coding compression for a sequence of
NACKed packets (so that it wouldn't blow the one packet limit), and perhaps that
would be worthy of a TODO.  I could also go and put this into the design doc if
folks would like (i.e., try to define the details).

[Ian Swett, 2012/12/04 21:40:19]

Changed back to the old comment and check in the cleanup CL.   I've added a
TODO.  I'm not sure if now is the right time to  finalize our ack framing with
variable length ints and/or other optimizations, but it may be, since it keeps
coming up and acks are clearly very important.

+  // kMaxPacketSize.
+  DCHECK_LT(incoming_ack.received_info.received_packet_times.size(),
+            kMaxAckedPackets);
 
   if (incoming_ack.sent_info.least_unacked != 0 &&
       incoming_ack.sent_info.least_unacked < least_packet_awaiting_ack_) {
     DLOG(INFO) << "Client sent low least_unacked";
     // We never process old ack frames, so this number should only increase.
     return false;
   }
 
   return true;
 }
 
 void QuicConnection::UpdatePacketInformationReceivedByPeer(
     const QuicAckFrame& incoming_ack) {
   QuicConnectionVisitorInterface::AckedPackets acked_packets;
 
   // Initialize the lowest unacked packet to the lower of the next outgoing
   // sequence number and the largest received packed in the incoming ack.
   QuicPacketSequenceNumber lowest_unacked = min(
       packet_creator_.sequence_number() + 1,
       incoming_ack.received_info.largest_received + 1);
 
   // 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();
   while (it != unacked_packets_.end()) {
-    if ((it->first < incoming_ack.received_info.largest_received &&
-         !ContainsKey(incoming_ack.received_info.missing_packets, it->first)) ||
-        it->first == incoming_ack.received_info.largest_received) {
+    if (incoming_ack.received_info.ContainsAck(it->first)) {
       // Packet was acked, so remove it from our unacked packet list.
       DVLOG(1) << "Got an ack for " << it->first;
       // TODO(rch): This is inefficient and should be sped up.
       // The acked packet might be queued (if a resend had been attempted).
       for (QueuedPacketList::iterator q = queued_packets_.begin();
            q != queued_packets_.end(); ++q) {
         if (q->sequence_number == it->first) {
           queued_packets_.erase(q);
           break;
         }
@@ skipping 14 matching lines @@
       ++it;
     }
   }
   if (acked_packets.size() > 0) {
     visitor_->OnAck(acked_packets);
   }
 
   // If we've gotten an ack for the lowest packet we were waiting on,
   // update that and the list of packets we advertise we will not resend.
   if (lowest_unacked > outgoing_ack_.sent_info.least_unacked) {
-    SequenceSet* non_retrans = &outgoing_ack_.sent_info.non_retransmiting;
-    // We don't need to advertise not-resending packets between the old
-    // and new values.
-    for (QuicPacketSequenceNumber i = outgoing_ack_.sent_info.least_unacked;
-         i < lowest_unacked; ++i) {
-      non_retrans->erase(i);
-    }
     // If all packets we sent have been acked, use the special value of 0
     if (lowest_unacked > packet_creator_.sequence_number()) {
       lowest_unacked = 0;
-      DCHECK_EQ(0u, non_retrans->size());
     }
     outgoing_ack_.sent_info.least_unacked = lowest_unacked;
   }
 }
 
 void QuicConnection::UpdatePacketInformationSentByPeer(
     const QuicAckFrame& incoming_ack) {
-  // Iteratate through the packets which will the peer will not resend and
-  // remove them from our missing list.
-  for (SequenceSet::const_iterator it =
-           incoming_ack.sent_info.non_retransmiting.begin();
-       it != incoming_ack.sent_info.non_retransmiting.end(); ++it) {
-    DVLOG(1) << "no longer expecting " << *it;
-    outgoing_ack_.received_info.missing_packets.erase(*it);
-  }
-
-  // Make sure we also don't expect any packets lower than the peer's
+  // Make sure we also don't ack any packets lower than the peer's
   // last-packet-awaiting-ack.
   if (incoming_ack.sent_info.least_unacked > least_packet_awaiting_ack_) {
-    for (QuicPacketSequenceNumber i = least_packet_awaiting_ack_;
-         i < incoming_ack.sent_info.least_unacked; ++i) {
-      outgoing_ack_.received_info.missing_packets.erase(i);
-    }
+    outgoing_ack_.received_info.ClearAcksBefore(
+        incoming_ack.sent_info.least_unacked);
     least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
   }
 
   // Possibly close any FecGroups which are now irrelevant
   CloseFecGroupsBefore(incoming_ack.sent_info.least_unacked + 1);
 }
 
 void QuicConnection::OnFecData(const QuicFecData& fec) {
   DCHECK_NE(0, last_header_.fec_group);
   QuicFecGroup* group = GetFecGroup();
@@ skipping 104 matching lines @@
     num_queued_packets = queued_packets_.size();
     QueuedPacket p = queued_packets_.front();
     queued_packets_.pop_front();
     SendPacket(p.sequence_number, p.packet, p.resend, false, p.retransmit);
   }
   return !write_blocked_;
 }
 
 void QuicConnection::AckPacket(const QuicPacketHeader& header) {
   QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
-  if (sequence_number > outgoing_ack_.received_info.largest_received) {
-    // We've got a new high sequence number.  Note any new intermediate missing
-    // packets, and update the last_ack data.
-    for (QuicPacketSequenceNumber i =
-             outgoing_ack_.received_info.largest_received + 1;
-         i < sequence_number; ++i) {
-      DVLOG(1) << "missing " << i;
-      outgoing_ack_.received_info.missing_packets.insert(i);
-    }
-    outgoing_ack_.received_info.largest_received = sequence_number;
-    outgoing_ack_.received_info.time_received = clock_->Now();
-  } else {
-    // We've gotten one of the out of order packets - remove it from our
-    // "missing packets" list.
-    DVLOG(1) << "Removing "  << sequence_number << " from missing list";
-    outgoing_ack_.received_info.missing_packets.erase(sequence_number);
-  }
+  outgoing_ack_.received_info.RecordAck(sequence_number, clock_->Now());
   // TODO(alyssar) delay sending until we have data, or enough time has elapsed.
   if (frames_.size() > 0) {
     SendAck();
   }
 }
 
 void QuicConnection::MaybeResendPacket(
     QuicPacketSequenceNumber sequence_number) {
   UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 
@@ skipping 40 matching lines @@
     }
   }
   if (should_resend) {
     helper_->SetResendAlarm(sequence_number, DefaultResendTime());
     // The second case should never happen in the real world, but does here
     // because we sometimes send out of order to validate corner cases.
     if (outgoing_ack_.sent_info.least_unacked == 0 ||
         sequence_number < outgoing_ack_.sent_info.least_unacked) {
       outgoing_ack_.sent_info.least_unacked = sequence_number;
     }
-  } else {
-    if (outgoing_ack_.sent_info.least_unacked != 0 &&
-        sequence_number > outgoing_ack_.sent_info.least_unacked) {
-      outgoing_ack_.sent_info.non_retransmiting.insert(sequence_number);
-    }
   }
 
   scoped_ptr<QuicEncryptedPacket> encrypted(framer_.EncryptPacket(*packet));
   int error;
   DLOG(INFO) << "Sending packet : "
              << (should_resend ? "data bearing " : " ack only ")
              << "packet " << sequence_number;
   int rv = helper_->WritePacketToWire(*encrypted, &error);
   if (rv == -1) {
     if (error == ERR_IO_PENDING) {
@@ skipping 109 matching lines @@
            << " delta:" << delta.ToMicroseconds();
   if (delta >= timeout_) {
     SendConnectionClose(QUIC_CONNECTION_TIMED_OUT);
     return true;
   }
   helper_->SetTimeoutAlarm(timeout_.Subtract(delta));
   return false;
 }
 
 }  // namespace net