summaryrefslogtreecommitdiffstats
path: root/net/quic/congestion_control
diff options
context:
space:
mode:
authorrtenneti@chromium.org <rtenneti@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>2014-02-27 00:09:03 +0000
committerrtenneti@chromium.org <rtenneti@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>2014-02-27 00:09:03 +0000
commit93dd91ff7c039a6db4798f40b212e1aaa380befb (patch)
treed8577ffd679249784cedf8cd4b3d3511cdb538fe /net/quic/congestion_control
parent91256e4f440f2588594359fe5e3ac78636448f1f (diff)
downloadchromium_src-93dd91ff7c039a6db4798f40b212e1aaa380befb.zip
chromium_src-93dd91ff7c039a6db4798f40b212e1aaa380befb.tar.gz
chromium_src-93dd91ff7c039a6db4798f40b212e1aaa380befb.tar.bz2
Land Recent QUIC Changes.
These LOG(INFO)s claimed 8-9% of time under a load test. Reduce logspam in QuicUnackedPacketMap. Merge internal change: 61895796 https://codereview.chromium.org/179773007/ QUIC WINDOW_UPDATE and BLOCKED frames instigate ACKs. Merge internal change: 61894847 https://codereview.chromium.org/180013004/ Avoiding quic double-close bugs by detecting it at the connection. Merge internal change: 61890466 https://codereview.chromium.org/180793003/ BLOCKED frames not being cleared. These are not yet used. (minor) Clear last BLOCKED frames in QuicConnection Merge internal change: 61875848 https://codereview.chromium.org/180793002/ QUIC - minor cleanup while merging internal change. Merge internal change: 61850595 https://codereview.chromium.org/177073016/ Create QUIC_VERSION_16 which breaks the sent_info field out of the ACK frame into a new STOP_WAITING frame. Does not change when this information is sent. That will happen in a follow-up CL. Send STOP_WAITING_FRAME for QUIC version 16 and above with Ack frame. Added logging for WINDOW_UPDATE and BLOCKED frames. Merge internal change: 61838258 https://codereview.chromium.org/180383004/ QUIC test refactor to move tests from the QuicSentPacketManagerTest to the new TcpLossAlgorithmTest. Merge internal change: 61837708 https://codereview.chromium.org/177203008/ Ctrl-F for "packet XY" in debug logs now matches sent packets "Sending packet XY", and received packets "Got packet XY". (minor) Improve QUIC packet sent debug log message Merge internal change: 61836667 https://codereview.chromium.org/177003007/ Auotmated rollback of internal changelist 57996291. *** Reason for rollback *** Now that clients no longer suggests 100 by default, it would be nice to experiment with allowing the client to suggest larger CWNDs. *** Original change description *** Temporarily change the maximum server initial congestion window to 10 from 100, because many existing Chrome clients are still negotiating 100, causing visible performance issues, particularly for YouTube rebuffers. *** Merge internal change: 61825277 https://codereview.chromium.org/178853003/ Refactor to create a new LossDetectionInterface used by the QuicSentPacketManager. Merge internal change: 61813052 https://codereview.chromium.org/178453005/ Preparation for only writing a fraction of the iov due to flow control blocking in ReliableQuicStream::WritevData. Add max_bytes argument to QuicSession::WritevData Merge internal change: 61810929 https://codereview.chromium.org/177203006/ R=rch@chromium.org Review URL: https://codereview.chromium.org/180723003 git-svn-id: svn://svn.chromium.org/chrome/trunk/src@253647 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'net/quic/congestion_control')
-rw-r--r--net/quic/congestion_control/loss_detection_interface.cc16
-rw-r--r--net/quic/congestion_control/loss_detection_interface.h35
-rw-r--r--net/quic/congestion_control/tcp_loss_algorithm.cc51
-rw-r--r--net/quic/congestion_control/tcp_loss_algorithm.h36
-rw-r--r--net/quic/congestion_control/tcp_loss_algorithm_test.cc147
5 files changed, 285 insertions, 0 deletions
diff --git a/net/quic/congestion_control/loss_detection_interface.cc b/net/quic/congestion_control/loss_detection_interface.cc
new file mode 100644
index 0000000..ddb5b43
--- /dev/null
+++ b/net/quic/congestion_control/loss_detection_interface.cc
@@ -0,0 +1,16 @@
+// Copyright 2014 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/congestion_control/loss_detection_interface.h"
+
+#include "net/quic/congestion_control/tcp_loss_algorithm.h"
+
+namespace net {
+
+// Factory for loss detection algorithm.
+LossDetectionInterface* LossDetectionInterface::Create() {
+ return new TCPLossAlgorithm();
+}
+
+} // namespace net
diff --git a/net/quic/congestion_control/loss_detection_interface.h b/net/quic/congestion_control/loss_detection_interface.h
new file mode 100644
index 0000000..65240a2
--- /dev/null
+++ b/net/quic/congestion_control/loss_detection_interface.h
@@ -0,0 +1,35 @@
+// Copyright 2014 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.
+//
+// The pure virtual class for send side loss detection algorithm.
+
+#ifndef NET_QUIC_CONGESTION_CONTROL_LOSS_DETECTION_INTERFACE_H_
+#define NET_QUIC_CONGESTION_CONTROL_LOSS_DETECTION_INTERFACE_H_
+
+#include "base/basictypes.h"
+#include "net/quic/quic_protocol.h"
+#include "net/quic/quic_time.h"
+
+namespace net {
+
+class QuicUnackedPacketMap;
+
+class NET_EXPORT_PRIVATE LossDetectionInterface {
+ public:
+ // Creates a TCP loss detector.
+ static LossDetectionInterface* Create();
+
+ virtual ~LossDetectionInterface() {}
+
+ // Called when a new ack arrives or the loss alarm fires.
+ virtual SequenceNumberSet DetectLostPackets(
+ const QuicUnackedPacketMap& unacked_packets,
+ const QuicTime& time,
+ QuicPacketSequenceNumber largest_observed,
+ QuicTime::Delta srtt) = 0;
+};
+
+} // namespace net
+
+#endif // NET_QUIC_CONGESTION_CONTROL_LOSS_DETECTION_INTERFACE_H_
diff --git a/net/quic/congestion_control/tcp_loss_algorithm.cc b/net/quic/congestion_control/tcp_loss_algorithm.cc
new file mode 100644
index 0000000..d4f2cf1
--- /dev/null
+++ b/net/quic/congestion_control/tcp_loss_algorithm.cc
@@ -0,0 +1,51 @@
+// Copyright 2014 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/congestion_control/tcp_loss_algorithm.h"
+
+#include "net/quic/quic_protocol.h"
+
+namespace net {
+
+namespace {
+// TCP retransmits after 3 nacks.
+static const size_t kNumberOfNacksBeforeRetransmission = 3;
+}
+
+TCPLossAlgorithm::TCPLossAlgorithm() { }
+
+// Uses nack counts to decide when packets are lost.
+SequenceNumberSet TCPLossAlgorithm::DetectLostPackets(
+ const QuicUnackedPacketMap& unacked_packets,
+ const QuicTime& time,
+ QuicPacketSequenceNumber largest_observed,
+ QuicTime::Delta srtt) {
+ SequenceNumberSet lost_packets;
+
+ for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin();
+ it != unacked_packets.end() && it->first <= largest_observed; ++it) {
+ if (!it->second.pending) {
+ continue;
+ }
+ size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission;
+ // Check for early retransmit(RFC5827) when the last packet gets acked and
+ // the there are fewer than 4 pending packets.
+ // TODO(ianswett): Set a retransmission timer instead of losing the packet
+ // and retransmitting immediately.
+ if (it->second.retransmittable_frames &&
+ unacked_packets.largest_sent_packet() == largest_observed) {
+ num_nacks_needed = largest_observed - it->first;
+ }
+
+ if (it->second.nack_count < num_nacks_needed) {
+ continue;
+ }
+
+ lost_packets.insert(it->first);
+ }
+
+ return lost_packets;
+}
+
+} // namespace net
diff --git a/net/quic/congestion_control/tcp_loss_algorithm.h b/net/quic/congestion_control/tcp_loss_algorithm.h
new file mode 100644
index 0000000..a7599aa
--- /dev/null
+++ b/net/quic/congestion_control/tcp_loss_algorithm.h
@@ -0,0 +1,36 @@
+// Copyright 2014 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.
+
+#ifndef NET_QUIC_CONGESTION_CONTROL_TCP_LOSS_ALGORITHM_H_
+#define NET_QUIC_CONGESTION_CONTROL_TCP_LOSS_ALGORITHM_H_
+
+#include <algorithm>
+#include <map>
+
+#include "base/basictypes.h"
+#include "net/quic/congestion_control/loss_detection_interface.h"
+#include "net/quic/quic_protocol.h"
+#include "net/quic/quic_time.h"
+#include "net/quic/quic_unacked_packet_map.h"
+
+namespace net {
+
+// Class which implement's TCP's approach of detecting loss when 3 nacks have
+// been received for a packet. Also implements TCP's early retransmit(RFC5827).
+class NET_EXPORT_PRIVATE TCPLossAlgorithm : public LossDetectionInterface {
+ public:
+ TCPLossAlgorithm();
+ virtual ~TCPLossAlgorithm() {}
+
+ // Uses nack counts to decide when packets are lost.
+ virtual SequenceNumberSet DetectLostPackets(
+ const QuicUnackedPacketMap& unacked_packets,
+ const QuicTime& time,
+ QuicPacketSequenceNumber largest_observed,
+ QuicTime::Delta srtt) OVERRIDE;
+};
+
+} // namespace net
+
+#endif // NET_QUIC_CONGESTION_CONTROL_TCP_LOSS_ALGORITHM_H_
diff --git a/net/quic/congestion_control/tcp_loss_algorithm_test.cc b/net/quic/congestion_control/tcp_loss_algorithm_test.cc
new file mode 100644
index 0000000..d2737df
--- /dev/null
+++ b/net/quic/congestion_control/tcp_loss_algorithm_test.cc
@@ -0,0 +1,147 @@
+// Copyright 2014 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/congestion_control/tcp_loss_algorithm.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+#include "base/stl_util.h"
+#include "net/quic/quic_unacked_packet_map.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+namespace test {
+namespace {
+
+class TcpLossAlgorithmTest : public ::testing::Test {
+ protected:
+ TcpLossAlgorithmTest()
+ : unacked_packets_(true),
+ srtt_(QuicTime::Delta::FromMilliseconds(10)) { }
+
+ void SendDataPacket(QuicPacketSequenceNumber sequence_number) {
+ SerializedPacket packet(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER,
+ NULL, 0, new RetransmittableFrames());
+ unacked_packets_.AddPacket(packet);
+ unacked_packets_.SetPending(sequence_number, QuicTime::Zero(), 1000);
+ }
+
+ void VerifyLosses(QuicPacketSequenceNumber largest_observed,
+ QuicPacketSequenceNumber* losses_expected,
+ size_t num_losses) {
+ SequenceNumberSet lost_packets =
+ loss_algorithm_.DetectLostPackets(
+ unacked_packets_, QuicTime::Zero(), largest_observed, srtt_);
+ EXPECT_EQ(num_losses, lost_packets.size());
+ for (size_t i = 0; i < num_losses; ++i) {
+ EXPECT_TRUE(ContainsKey(lost_packets, losses_expected[i]));
+ }
+ }
+
+ QuicUnackedPacketMap unacked_packets_;
+ TCPLossAlgorithm loss_algorithm_;
+ QuicTime::Delta srtt_;
+};
+
+TEST_F(TcpLossAlgorithmTest, NackRetransmit1Packet) {
+ const size_t kNumSentPackets = 5;
+ // Transmit 5 packets.
+ for (size_t i = 1; i <= kNumSentPackets; ++i) {
+ SendDataPacket(i);
+ }
+ // No loss on one ack.
+ unacked_packets_.SetNotPending(2);
+ unacked_packets_.NackPacket(1, 1);
+ VerifyLosses(2, NULL, 0);
+ // No loss on two acks.
+ unacked_packets_.SetNotPending(3);
+ unacked_packets_.NackPacket(1, 2);
+ VerifyLosses(3, NULL, 0);
+ // Loss on three acks.
+ unacked_packets_.SetNotPending(4);
+ unacked_packets_.NackPacket(1, 3);
+ QuicPacketSequenceNumber lost[] = { 1 };
+ VerifyLosses(4, lost, arraysize(lost));
+}
+
+// A stretch ack is an ack that covers more than 1 packet of previously
+// unacknowledged data.
+TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketWith1StretchAck) {
+ const size_t kNumSentPackets = 10;
+ // Transmit 10 packets.
+ for (size_t i = 1; i <= kNumSentPackets; ++i) {
+ SendDataPacket(i);
+ }
+
+ // Nack the first packet 3 times in a single StretchAck.
+ unacked_packets_.NackPacket(1, 3);
+ unacked_packets_.SetNotPending(2);
+ unacked_packets_.SetNotPending(3);
+ unacked_packets_.SetNotPending(4);
+ QuicPacketSequenceNumber lost[] = { 1 };
+ VerifyLosses(4, lost, arraysize(lost));
+}
+
+// Ack a packet 3 packets ahead, causing a retransmit.
+TEST_F(TcpLossAlgorithmTest, NackRetransmit1PacketSingleAck) {
+ const size_t kNumSentPackets = 10;
+ // Transmit 10 packets.
+ for (size_t i = 1; i <= kNumSentPackets; ++i) {
+ SendDataPacket(i);
+ }
+
+ // Nack the first packet 3 times in an AckFrame with three missing packets.
+ unacked_packets_.NackPacket(1, 3);
+ unacked_packets_.NackPacket(2, 2);
+ unacked_packets_.NackPacket(3, 1);
+ unacked_packets_.SetNotPending(4);
+ QuicPacketSequenceNumber lost[] = { 1 };
+ VerifyLosses(4, lost, arraysize(lost));
+}
+
+TEST_F(TcpLossAlgorithmTest, EarlyRetransmit1Packet) {
+ const size_t kNumSentPackets = 2;
+ // Transmit 2 packets.
+ for (size_t i = 1; i <= kNumSentPackets; ++i) {
+ SendDataPacket(i);
+ }
+ // Early retransmit when the final packet gets acked and the first is nacked.
+ unacked_packets_.SetNotPending(2);
+ unacked_packets_.NackPacket(1, 1);
+ QuicPacketSequenceNumber lost[] = { 1 };
+ VerifyLosses(2, lost, arraysize(lost));
+}
+
+TEST_F(TcpLossAlgorithmTest, EarlyRetransmitAllPackets) {
+ const size_t kNumSentPackets = 5;
+ for (size_t i = 1; i <= kNumSentPackets; ++i) {
+ SendDataPacket(i);
+ }
+ // Early retransmit when the final packet gets acked and the first 4 are
+ // nacked multiple times via FACK.
+ unacked_packets_.SetNotPending(kNumSentPackets);
+ for (size_t i = 1; i < kNumSentPackets; ++i) {
+ unacked_packets_.NackPacket(i, kNumSentPackets - i);
+ }
+ QuicPacketSequenceNumber lost[] = { 1, 2, 3, 4 };
+ VerifyLosses(kNumSentPackets, lost, arraysize(lost));
+}
+
+TEST_F(TcpLossAlgorithmTest, DontEarlyRetransmitNeuteredPacket) {
+ const size_t kNumSentPackets = 2;
+ // Transmit 2 packets.
+ for (size_t i = 1; i <= kNumSentPackets; ++i) {
+ SendDataPacket(i);
+ }
+ // Early retransmit when the final packet gets acked and the first is nacked.
+ unacked_packets_.SetNotPending(2);
+ unacked_packets_.NackPacket(1, 1);
+ unacked_packets_.NeuterPacket(1);
+ VerifyLosses(2, NULL, 0);
+}
+
+} // namespace
+} // namespace test
+} // namespace net