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

net/quic/quic_connection.cc

Index: net/quic/quic_connection.cc
diff --git a/net/quic/quic_connection.cc b/net/quic/quic_connection.cc
index 9905fec12f20ad09396b546f1ad52282e67f59a9..9c937b9af0eea62c808795d165918a6958c1e599 100644
--- a/net/quic/quic_connection.cc
+++ b/net/quic/quic_connection.cc
@@ -24,14 +24,14 @@ 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,
@@ -105,8 +105,7 @@ bool QuicConnection::OnPacketHeader(const QuicPacketHeader& header) {
   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;
   }
 
@@ -168,12 +167,10 @@ bool QuicConnection::ValidateAckFrame(const QuicAckFrame& incoming_ack) {
     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_) {
@@ -199,9 +196,7 @@ void QuicConnection::UpdatePacketInformationReceivedByPeer(
   // 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.
@@ -236,17 +231,9 @@ void QuicConnection::UpdatePacketInformationReceivedByPeer(
   // 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;
   }
@@ -254,22 +241,11 @@ void QuicConnection::UpdatePacketInformationReceivedByPeer(
 
 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;
   }
 
@@ -394,23 +370,7 @@ bool QuicConnection::OnCanWrite() {
 
 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();
@@ -471,11 +431,6 @@ bool QuicConnection::SendPacket(QuicPacketSequenceNumber sequence_number,
         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));