1 // Copyright 2015 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 #include "quiche/quic/core/congestion_control/general_loss_algorithm.h"
6
7 #include "quiche/quic/core/congestion_control/rtt_stats.h"
8 #include "quiche/quic/core/quic_packets.h"
9 #include "quiche/quic/platform/api/quic_bug_tracker.h"
10 #include "quiche/quic/platform/api/quic_flag_utils.h"
11 #include "quiche/quic/platform/api/quic_flags.h"
12
13 namespace quic {
14
15 namespace {
DetectionResponseTime(QuicTime::Delta rtt,QuicTime send_time,QuicTime detection_time)16 float DetectionResponseTime(QuicTime::Delta rtt, QuicTime send_time,
17 QuicTime detection_time) {
18 if (detection_time <= send_time || rtt.IsZero()) {
19 // Time skewed, assume a very fast detection where |detection_time| is
20 // |send_time| + |rtt|.
21 return 1.0;
22 }
23 float send_to_detection_us = (detection_time - send_time).ToMicroseconds();
24 return send_to_detection_us / rtt.ToMicroseconds();
25 }
26
GetMaxRtt(const RttStats & rtt_stats)27 QuicTime::Delta GetMaxRtt(const RttStats& rtt_stats) {
28 return std::max(kAlarmGranularity,
29 std::max(rtt_stats.previous_srtt(), rtt_stats.latest_rtt()));
30 }
31
32 } // namespace
33
34 // Uses nack counts to decide when packets are lost.
DetectLosses(const QuicUnackedPacketMap & unacked_packets,QuicTime time,const RttStats & rtt_stats,QuicPacketNumber largest_newly_acked,const AckedPacketVector & packets_acked,LostPacketVector * packets_lost)35 LossDetectionInterface::DetectionStats GeneralLossAlgorithm::DetectLosses(
36 const QuicUnackedPacketMap& unacked_packets, QuicTime time,
37 const RttStats& rtt_stats, QuicPacketNumber largest_newly_acked,
38 const AckedPacketVector& packets_acked, LostPacketVector* packets_lost) {
39 DetectionStats detection_stats;
40
41 loss_detection_timeout_ = QuicTime::Zero();
42 if (!packets_acked.empty() && least_in_flight_.IsInitialized() &&
43 packets_acked.front().packet_number == least_in_flight_) {
44 if (packets_acked.back().packet_number == largest_newly_acked &&
45 least_in_flight_ + packets_acked.size() - 1 == largest_newly_acked) {
46 // Optimization for the case when no packet is missing. Please note,
47 // packets_acked can include packets of different packet number space, so
48 // do not use this optimization if largest_newly_acked is not the largest
49 // packet in packets_acked.
50 least_in_flight_ = largest_newly_acked + 1;
51 return detection_stats;
52 }
53 // There is hole in acked_packets, increment least_in_flight_ if possible.
54 for (const auto& acked : packets_acked) {
55 if (acked.packet_number != least_in_flight_) {
56 break;
57 }
58 ++least_in_flight_;
59 }
60 }
61
62 const QuicTime::Delta max_rtt = GetMaxRtt(rtt_stats);
63
64 QuicPacketNumber packet_number = unacked_packets.GetLeastUnacked();
65 auto it = unacked_packets.begin();
66 if (least_in_flight_.IsInitialized() && least_in_flight_ >= packet_number) {
67 if (least_in_flight_ > unacked_packets.largest_sent_packet() + 1) {
68 QUIC_BUG(quic_bug_10430_1) << "least_in_flight: " << least_in_flight_
69 << " is greater than largest_sent_packet + 1: "
70 << unacked_packets.largest_sent_packet() + 1;
71 } else {
72 it += (least_in_flight_ - packet_number);
73 packet_number = least_in_flight_;
74 }
75 }
76 // Clear least_in_flight_.
77 least_in_flight_.Clear();
78 QUICHE_DCHECK_EQ(packet_number_space_,
79 unacked_packets.GetPacketNumberSpace(largest_newly_acked));
80 for (; it != unacked_packets.end() && packet_number <= largest_newly_acked;
81 ++it, ++packet_number) {
82 if (unacked_packets.GetPacketNumberSpace(it->encryption_level) !=
83 packet_number_space_) {
84 // Skip packets of different packet number space.
85 continue;
86 }
87
88 if (!it->in_flight) {
89 continue;
90 }
91
92 if (parent_ != nullptr && largest_newly_acked != packet_number) {
93 parent_->OnReorderingDetected();
94 }
95
96 if (largest_newly_acked - packet_number >
97 detection_stats.sent_packets_max_sequence_reordering) {
98 detection_stats.sent_packets_max_sequence_reordering =
99 largest_newly_acked - packet_number;
100 }
101
102 // Packet threshold loss detection.
103 // Skip packet threshold loss detection if largest_newly_acked is a runt.
104 const bool skip_packet_threshold_detection =
105 !use_packet_threshold_for_runt_packets_ &&
106 it->bytes_sent >
107 unacked_packets.GetTransmissionInfo(largest_newly_acked).bytes_sent;
108 if (!skip_packet_threshold_detection &&
109 largest_newly_acked - packet_number >= reordering_threshold_) {
110 packets_lost->push_back(LostPacket(packet_number, it->bytes_sent));
111 detection_stats.total_loss_detection_response_time +=
112 DetectionResponseTime(max_rtt, it->sent_time, time);
113 continue;
114 }
115
116 // Time threshold loss detection.
117 const QuicTime::Delta loss_delay = max_rtt + (max_rtt >> reordering_shift_);
118 QuicTime when_lost = it->sent_time + loss_delay;
119 if (time < when_lost) {
120 if (time >=
121 it->sent_time + max_rtt + (max_rtt >> (reordering_shift_ + 1))) {
122 ++detection_stats.sent_packets_num_borderline_time_reorderings;
123 }
124 loss_detection_timeout_ = when_lost;
125 if (!least_in_flight_.IsInitialized()) {
126 // At this point, packet_number is in flight and not detected as lost.
127 least_in_flight_ = packet_number;
128 }
129 break;
130 }
131 packets_lost->push_back(LostPacket(packet_number, it->bytes_sent));
132 detection_stats.total_loss_detection_response_time +=
133 DetectionResponseTime(max_rtt, it->sent_time, time);
134 }
135 if (!least_in_flight_.IsInitialized()) {
136 // There is no in flight packet.
137 least_in_flight_ = largest_newly_acked + 1;
138 }
139
140 return detection_stats;
141 }
142
GetLossTimeout() const143 QuicTime GeneralLossAlgorithm::GetLossTimeout() const {
144 return loss_detection_timeout_;
145 }
146
SpuriousLossDetected(const QuicUnackedPacketMap & unacked_packets,const RttStats & rtt_stats,QuicTime ack_receive_time,QuicPacketNumber packet_number,QuicPacketNumber previous_largest_acked)147 void GeneralLossAlgorithm::SpuriousLossDetected(
148 const QuicUnackedPacketMap& unacked_packets, const RttStats& rtt_stats,
149 QuicTime ack_receive_time, QuicPacketNumber packet_number,
150 QuicPacketNumber previous_largest_acked) {
151 if (use_adaptive_time_threshold_ && reordering_shift_ > 0) {
152 // Increase reordering fraction such that the packet would not have been
153 // declared lost.
154 QuicTime::Delta time_needed =
155 ack_receive_time -
156 unacked_packets.GetTransmissionInfo(packet_number).sent_time;
157 QuicTime::Delta max_rtt =
158 std::max(rtt_stats.previous_srtt(), rtt_stats.latest_rtt());
159 while (max_rtt + (max_rtt >> reordering_shift_) < time_needed &&
160 reordering_shift_ > 0) {
161 --reordering_shift_;
162 }
163 }
164
165 if (use_adaptive_reordering_threshold_) {
166 QUICHE_DCHECK_LT(packet_number, previous_largest_acked);
167 // Increase reordering_threshold_ such that packet_number would not have
168 // been declared lost.
169 reordering_threshold_ = std::max(
170 reordering_threshold_, previous_largest_acked - packet_number + 1);
171 }
172 }
173
Initialize(PacketNumberSpace packet_number_space,LossDetectionInterface * parent)174 void GeneralLossAlgorithm::Initialize(PacketNumberSpace packet_number_space,
175 LossDetectionInterface* parent) {
176 parent_ = parent;
177 if (packet_number_space_ < NUM_PACKET_NUMBER_SPACES) {
178 QUIC_BUG(quic_bug_10430_2) << "Cannot switch packet_number_space";
179 return;
180 }
181
182 packet_number_space_ = packet_number_space;
183 }
184
Reset()185 void GeneralLossAlgorithm::Reset() {
186 loss_detection_timeout_ = QuicTime::Zero();
187 least_in_flight_.Clear();
188 }
189
190 } // namespace quic
191