1// Copyright 2014 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 "net/quic/congestion_control/send_algorithm_simulator.h" 6 7#include <limits> 8 9#include "base/logging.h" 10#include "base/rand_util.h" 11#include "net/quic/crypto/quic_random.h" 12 13using std::list; 14using std::max; 15using std::min; 16 17namespace net { 18 19namespace { 20 21const QuicByteCount kPacketSize = 1200; 22 23} // namespace 24 25SendAlgorithmSimulator::SendAlgorithmSimulator( 26 SendAlgorithmInterface* send_algorithm, 27 MockClock* clock, 28 RttStats* rtt_stats, 29 QuicBandwidth bandwidth, 30 QuicTime::Delta rtt) 31 : send_algorithm_(send_algorithm), 32 clock_(clock), 33 rtt_stats_(rtt_stats), 34 next_sent_(1), 35 last_acked_(0), 36 next_acked_(1), 37 lose_next_ack_(false), 38 bytes_in_flight_(0), 39 forward_loss_rate_(0), 40 reverse_loss_rate_(0), 41 loss_correlation_(0), 42 bandwidth_(bandwidth), 43 rtt_(rtt), 44 buffer_size_(1000000), 45 max_cwnd_(0), 46 min_cwnd_(100000), 47 max_cwnd_drop_(0), 48 last_cwnd_(0) { 49 uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max()); 50 DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed; 51 simple_random_.set_seed(seed); 52} 53 54SendAlgorithmSimulator::~SendAlgorithmSimulator() {} 55 56// Sends the specified number of bytes as quickly as possible and returns the 57// average bandwidth in bytes per second. The time elapsed is based on 58// waiting for all acks to arrive. 59QuicBandwidth SendAlgorithmSimulator::SendBytes(size_t num_bytes) { 60 const QuicTime start_time = clock_->Now(); 61 size_t bytes_acked = 0; 62 while (bytes_acked < num_bytes) { 63 DVLOG(1) << "bytes_acked:" << bytes_acked << " bytes_in_flight_:" 64 << bytes_in_flight_ << " CWND(bytes):" 65 << send_algorithm_->GetCongestionWindow(); 66 // Determine the times of next send and of the next ack arrival. 67 QuicTime::Delta send_delta = send_algorithm_->TimeUntilSend( 68 clock_->Now(), bytes_in_flight_, HAS_RETRANSMITTABLE_DATA); 69 // If we've already sent enough bytes, wait for them to be acked. 70 if (bytes_acked + bytes_in_flight_ >= num_bytes) { 71 send_delta = QuicTime::Delta::Infinite(); 72 } 73 QuicTime::Delta ack_delta = NextAckDelta(); 74 // If both times are infinite, fire a TLP. 75 if (ack_delta.IsInfinite() && send_delta.IsInfinite()) { 76 DVLOG(1) << "Both times are infinite, simulating a TLP."; 77 // TODO(ianswett): Use a more sophisticated TLP timer. 78 clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100)); 79 SendDataNow(); 80 } else if (ack_delta < send_delta) { 81 DVLOG(1) << "Handling ack, advancing time:" 82 << ack_delta.ToMicroseconds() << "us"; 83 // Ack data all the data up to ack time and lose any missing sequence 84 // numbers. 85 clock_->AdvanceTime(ack_delta); 86 bytes_acked += HandlePendingAck(); 87 } else { 88 DVLOG(1) << "Sending, advancing time:" 89 << send_delta.ToMicroseconds() << "us"; 90 clock_->AdvanceTime(send_delta); 91 SendDataNow(); 92 } 93 RecordStats(); 94 } 95 return QuicBandwidth::FromBytesAndTimeDelta( 96 num_bytes, clock_->Now().Subtract(start_time)); 97} 98 99// NextAck takes into account packet loss in both forward and reverse 100// direction, as well as correlated losses. And it assumes the receiver acks 101// every other packet when there is no loss. 102QuicTime::Delta SendAlgorithmSimulator::NextAckDelta() { 103 if (sent_packets_.empty() || AllPacketsLost()) { 104 DVLOG(1) << "No outstanding packets to cause acks. sent_packets_.size():" 105 << sent_packets_.size(); 106 return QuicTime::Delta::Infinite(); 107 } 108 109 // If necessary, determine next_acked_. 110 // This is only done once to ensure multiple calls return the same time. 111 FindNextAcked(); 112 113 // If only one packet is acked, simulate a delayed ack. 114 if (next_acked_ - last_acked_ == 1) { 115 return sent_packets_.front().ack_time.Add( 116 QuicTime::Delta::FromMilliseconds(100)).Subtract(clock_->Now()); 117 } 118 for (list<SentPacket>::const_iterator it = sent_packets_.begin(); 119 it != sent_packets_.end(); ++it) { 120 if (next_acked_ == it->sequence_number) { 121 return it->ack_time.Subtract(clock_->Now()); 122 } 123 } 124 LOG(DFATAL) << "Error, next_acked_: " << next_acked_ 125 << " should have been found in sent_packets_"; 126 return QuicTime::Delta::Infinite(); 127} 128 129bool SendAlgorithmSimulator::AllPacketsLost() { 130 for (list<SentPacket>::const_iterator it = sent_packets_.begin(); 131 it != sent_packets_.end(); ++it) { 132 if (it->ack_time.IsInitialized()) { 133 return false; 134 } 135 } 136 return true; 137} 138 139void SendAlgorithmSimulator::FindNextAcked() { 140 // TODO(ianswett): Add a simpler mode which acks every packet. 141 bool packets_lost = false; 142 if (next_acked_ == last_acked_) { 143 // Determine if the next ack is lost only once, to ensure determinism. 144 lose_next_ack_ = 145 reverse_loss_rate_ * kuint64max > simple_random_.RandUint64(); 146 } 147 bool two_acks_remaining = lose_next_ack_; 148 next_acked_ = last_acked_; 149 // Remove any packets that are simulated as lost. 150 for (list<SentPacket>::const_iterator it = sent_packets_.begin(); 151 it != sent_packets_.end(); ++it) { 152 // Lost packets don't trigger an ack. 153 if (it->ack_time == QuicTime::Zero()) { 154 packets_lost = true; 155 continue; 156 } 157 // Buffer dropped packets are skipped automatically, but still end up 158 // being lost and cause acks to be sent immediately. 159 if (next_acked_ < it->sequence_number - 1) { 160 packets_lost = true; 161 } 162 next_acked_ = it->sequence_number; 163 if (packets_lost || (next_acked_ - last_acked_) % 2 == 0) { 164 if (two_acks_remaining) { 165 two_acks_remaining = false; 166 } else { 167 break; 168 } 169 } 170 } 171 DVLOG(1) << "FindNextAcked found next_acked_:" << next_acked_ 172 << " last_acked:" << last_acked_; 173} 174 175int SendAlgorithmSimulator::HandlePendingAck() { 176 DCHECK_LT(last_acked_, next_acked_); 177 SendAlgorithmInterface::CongestionMap acked_packets; 178 SendAlgorithmInterface::CongestionMap lost_packets; 179 // Some entries may be missing from the sent_packets_ array, if they were 180 // dropped due to buffer overruns. 181 SentPacket largest_observed = sent_packets_.front(); 182 while (last_acked_ < next_acked_) { 183 ++last_acked_; 184 TransmissionInfo info = TransmissionInfo(); 185 info.bytes_sent = kPacketSize; 186 info.in_flight = true; 187 // If it's missing from the array, it's a loss. 188 if (sent_packets_.front().sequence_number > last_acked_) { 189 DVLOG(1) << "Lost packet:" << last_acked_ 190 << " dropped by buffer overflow."; 191 lost_packets[last_acked_] = info; 192 continue; 193 } 194 if (sent_packets_.front().ack_time.IsInitialized()) { 195 acked_packets[last_acked_] = info; 196 } else { 197 lost_packets[last_acked_] = info; 198 } 199 // Remove all packets from the front to next_acked_. 200 largest_observed = sent_packets_.front(); 201 sent_packets_.pop_front(); 202 } 203 204 DCHECK(largest_observed.ack_time.IsInitialized()); 205 rtt_stats_->UpdateRtt( 206 largest_observed.ack_time.Subtract(largest_observed.send_time), 207 QuicTime::Delta::Zero(), 208 clock_->Now()); 209 send_algorithm_->OnCongestionEvent( 210 true, bytes_in_flight_, acked_packets, lost_packets); 211 DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()), 212 bytes_in_flight_); 213 bytes_in_flight_ -= 214 kPacketSize * (acked_packets.size() + lost_packets.size()); 215 return acked_packets.size() * kPacketSize; 216} 217 218void SendAlgorithmSimulator::SendDataNow() { 219 DVLOG(1) << "Sending packet:" << next_sent_ << " bytes_in_flight:" 220 << bytes_in_flight_; 221 send_algorithm_->OnPacketSent( 222 clock_->Now(), bytes_in_flight_, 223 next_sent_, kPacketSize, HAS_RETRANSMITTABLE_DATA); 224 // Lose the packet immediately if the buffer is full. 225 if (sent_packets_.size() * kPacketSize < buffer_size_) { 226 // TODO(ianswett): This buffer simulation is an approximation. 227 // An ack time of zero means loss. 228 bool packet_lost = 229 forward_loss_rate_ * kuint64max > simple_random_.RandUint64(); 230 // Handle correlated loss. 231 if (!sent_packets_.empty() && 232 !sent_packets_.back().ack_time.IsInitialized() && 233 loss_correlation_ * kuint64max > simple_random_.RandUint64()) { 234 packet_lost = true; 235 } 236 237 QuicTime ack_time = clock_->Now().Add(rtt_); 238 // If the number of bytes in flight are less than the bdp, there's 239 // no buffering delay. Bytes lost from the buffer are not counted. 240 QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_); 241 if (sent_packets_.size() * kPacketSize > bdp) { 242 QuicByteCount qsize = sent_packets_.size() * kPacketSize - bdp; 243 ack_time = ack_time.Add(bandwidth_.TransferTime(qsize)); 244 } 245 // If the packet is lost, give it an ack time of Zero. 246 sent_packets_.push_back(SentPacket( 247 next_sent_, clock_->Now(), packet_lost ? QuicTime::Zero() : ack_time)); 248 } 249 ++next_sent_; 250 bytes_in_flight_ += kPacketSize; 251} 252 253void SendAlgorithmSimulator::RecordStats() { 254 QuicByteCount cwnd = send_algorithm_->GetCongestionWindow(); 255 max_cwnd_ = max(max_cwnd_, cwnd); 256 min_cwnd_ = min(min_cwnd_, cwnd); 257 if (last_cwnd_ > cwnd) { 258 max_cwnd_drop_ = max(max_cwnd_drop_, last_cwnd_ - cwnd); 259 } 260 last_cwnd_ = cwnd; 261} 262 263// Advance the time by |delta| without sending anything. 264void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) { 265 clock_->AdvanceTime(delta); 266} 267 268// Elapsed time from the start of the connection. 269QuicTime SendAlgorithmSimulator::ElapsedTime() { 270 return clock_->Now(); 271} 272 273} // namespace net 274