| OLD | NEW |
|---|
| (Empty) |
| 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 <stdint.h> | |
| 8 | |
| 9 #include <limits> | |
| 10 | |
| 11 #include "base/logging.h" | |
| 12 #include "base/rand_util.h" | |
| 13 #include "net/quic/crypto/quic_random.h" | |
| 14 | |
| 15 using std::list; | |
| 16 using std::max; | |
| 17 using std::min; | |
| 18 using std::string; | |
| 19 using std::vector; | |
| 20 | |
| 21 namespace net { | |
| 22 | |
| 23 namespace { | |
| 24 | |
| 25 const QuicByteCount kPacketSize = 1200; | |
| 26 | |
| 27 } // namespace | |
| 28 | |
| 29 SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm, | |
| 30 RttStats* rtt_stats) | |
| 31 : Sender(send_algorithm, rtt_stats, QuicTime::Delta::Zero()) {} | |
| 32 | |
| 33 SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm, | |
| 34 RttStats* rtt_stats, | |
| 35 QuicTime::Delta additional_rtt) | |
| 36 : send_algorithm(send_algorithm), | |
| 37 rtt_stats(rtt_stats), | |
| 38 additional_rtt(additional_rtt), | |
| 39 last_sent(0), | |
| 40 last_acked(0), | |
| 41 next_acked(1), | |
| 42 max_cwnd(0), | |
| 43 min_cwnd(100000), | |
| 44 max_cwnd_drop(0), | |
| 45 last_cwnd(0), | |
| 46 last_transfer_bandwidth(QuicBandwidth::Zero()), | |
| 47 last_transfer_loss_rate(0) {} | |
| 48 | |
| 49 SendAlgorithmSimulator::Transfer::Transfer(Sender* sender, | |
| 50 QuicByteCount num_bytes, | |
| 51 QuicTime start_time, | |
| 52 string name) | |
| 53 : sender(sender), | |
| 54 num_bytes(num_bytes), | |
| 55 bytes_acked(0), | |
| 56 bytes_lost(0), | |
| 57 bytes_in_flight(0), | |
| 58 start_time(start_time), | |
| 59 name(name) {} | |
| 60 | |
| 61 SendAlgorithmSimulator::SendAlgorithmSimulator(MockClock* clock, | |
| 62 QuicBandwidth bandwidth, | |
| 63 QuicTime::Delta rtt) | |
| 64 : clock_(clock), | |
| 65 lose_next_ack_(false), | |
| 66 forward_loss_rate_(0), | |
| 67 reverse_loss_rate_(0), | |
| 68 loss_correlation_(0), | |
| 69 bandwidth_(bandwidth), | |
| 70 rtt_(rtt), | |
| 71 buffer_size_(1000000), | |
| 72 delayed_ack_timer_(QuicTime::Delta::FromMilliseconds(100)) { | |
| 73 uint32_t seed = base::RandInt(0, std::numeric_limits<int32_t>::max()); | |
| 74 DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed; | |
| 75 simple_random_.set_seed(seed); | |
| 76 } | |
| 77 | |
| 78 SendAlgorithmSimulator::~SendAlgorithmSimulator() {} | |
| 79 | |
| 80 void SendAlgorithmSimulator::AddTransfer(Sender* sender, size_t num_bytes) { | |
| 81 AddTransfer(sender, num_bytes, clock_->Now(), | |
| 82 StringPrintf("#%zu", pending_transfers_.size())); | |
| 83 } | |
| 84 | |
| 85 void SendAlgorithmSimulator::AddTransfer(Sender* sender, | |
| 86 size_t num_bytes, | |
| 87 QuicTime start_time, | |
| 88 string name) { | |
| 89 pending_transfers_.push_back(Transfer(sender, num_bytes, start_time, name)); | |
| 90 // Record initial stats from when the transfer begins. | |
| 91 pending_transfers_.back().sender->RecordStats(); | |
| 92 } | |
| 93 | |
| 94 void SendAlgorithmSimulator::TransferBytes() { | |
| 95 TransferBytes(std::numeric_limits<uint64_t>::max(), | |
| 96 QuicTime::Delta::Infinite()); | |
| 97 } | |
| 98 | |
| 99 void SendAlgorithmSimulator::TransferBytes(QuicByteCount max_bytes, | |
| 100 QuicTime::Delta max_time) { | |
| 101 const QuicTime end_time = max_time.IsInfinite() | |
| 102 ? QuicTime::Zero() + QuicTime::Delta::Infinite() | |
| 103 : clock_->Now() + max_time; | |
| 104 QuicByteCount bytes_sent = 0; | |
| 105 while (!pending_transfers_.empty() && clock_->Now() < end_time && | |
| 106 bytes_sent < max_bytes) { | |
| 107 // Determine the times of next send and of the next ack arrival. | |
| 108 PacketEvent send_event = NextSendEvent(); | |
| 109 PacketEvent ack_event = NextAckEvent(); | |
| 110 // If both times are infinite, fire a TLP. | |
| 111 if (ack_event.time_delta.IsInfinite() && | |
| 112 send_event.time_delta.IsInfinite()) { | |
| 113 DVLOG(1) << "Both times are infinite, simulating a TLP."; | |
| 114 // TODO(ianswett): Use a more sophisticated TLP timer or never lose | |
| 115 // the last ack? | |
| 116 clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100)); | |
| 117 SendDataNow(&pending_transfers_.front()); | |
| 118 } else if (ack_event.time_delta < send_event.time_delta) { | |
| 119 DVLOG(1) << "Handling ack of largest observed:" | |
| 120 << ack_event.transfer->sender->next_acked | |
| 121 << ", advancing time:" << ack_event.time_delta.ToMicroseconds() | |
| 122 << "us"; | |
| 123 // Ack data all the data up to ack time and lose any missing packet | |
| 124 // numbers. | |
| 125 clock_->AdvanceTime(ack_event.time_delta); | |
| 126 HandlePendingAck(ack_event.transfer); | |
| 127 } else { | |
| 128 DVLOG(1) << "Sending transfer '" << send_event.transfer->name | |
| 129 << "', advancing time:" << send_event.time_delta.ToMicroseconds() | |
| 130 << "us"; | |
| 131 clock_->AdvanceTime(send_event.time_delta); | |
| 132 SendDataNow(send_event.transfer); | |
| 133 bytes_sent += kPacketSize; | |
| 134 } | |
| 135 } | |
| 136 } | |
| 137 | |
| 138 SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextSendEvent() { | |
| 139 QuicTime::Delta next_send_time = QuicTime::Delta::Infinite(); | |
| 140 Transfer* transfer = nullptr; | |
| 141 for (vector<Transfer>::iterator it = pending_transfers_.begin(); | |
| 142 it != pending_transfers_.end(); ++it) { | |
| 143 // If we've already sent enough bytes, wait for them to be acked. | |
| 144 if (it->bytes_acked + it->bytes_in_flight >= it->num_bytes) { | |
| 145 continue; | |
| 146 } | |
| 147 // If the flow hasn't started, use the start time. | |
| 148 QuicTime::Delta transfer_send_time = it->start_time - clock_->Now(); | |
| 149 if (clock_->Now() >= it->start_time) { | |
| 150 transfer_send_time = it->sender->send_algorithm->TimeUntilSend( | |
| 151 clock_->Now(), it->bytes_in_flight); | |
| 152 } | |
| 153 if (transfer_send_time < next_send_time) { | |
| 154 next_send_time = transfer_send_time; | |
| 155 transfer = &(*it); | |
| 156 } | |
| 157 } | |
| 158 DVLOG(1) << "NextSendTime returning delta(ms):" | |
| 159 << next_send_time.ToMilliseconds() << ", transfer '" | |
| 160 << transfer->name; | |
| 161 return PacketEvent(next_send_time, transfer); | |
| 162 } | |
| 163 | |
| 164 // NextAck takes into account packet loss in both forward and reverse | |
| 165 // direction, as well as correlated losses. And it assumes the receiver acks | |
| 166 // every other packet when there is no loss. | |
| 167 SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextAckEvent() { | |
| 168 if (sent_packets_.empty()) { | |
| 169 DVLOG(1) << "No outstanding packets to ack for any transfer."; | |
| 170 return PacketEvent(QuicTime::Delta::Infinite(), nullptr); | |
| 171 } | |
| 172 | |
| 173 // For each connection, find the next acked packet. | |
| 174 QuicTime::Delta ack_time = QuicTime::Delta::Infinite(); | |
| 175 Transfer* transfer = nullptr; | |
| 176 for (vector<Transfer>::iterator it = pending_transfers_.begin(); | |
| 177 it != pending_transfers_.end(); ++it) { | |
| 178 QuicTime::Delta transfer_ack_time = FindNextAcked(&(*it)); | |
| 179 if (transfer_ack_time < ack_time) { | |
| 180 ack_time = transfer_ack_time; | |
| 181 transfer = &(*it); | |
| 182 } | |
| 183 } | |
| 184 | |
| 185 return PacketEvent(ack_time, transfer); | |
| 186 } | |
| 187 | |
| 188 QuicTime::Delta SendAlgorithmSimulator::FindNextAcked(Transfer* transfer) { | |
| 189 Sender* sender = transfer->sender; | |
| 190 if (sender->next_acked == sender->last_acked) { | |
| 191 // Determine if the next ack is lost only once, to ensure determinism. | |
| 192 lose_next_ack_ = reverse_loss_rate_ * std::numeric_limits<uint64_t>::max() > | |
| 193 simple_random_.RandUint64(); | |
| 194 } | |
| 195 | |
| 196 QuicPacketNumber next_acked = sender->last_acked; | |
| 197 QuicTime::Delta next_ack_delay = | |
| 198 FindNextAck(transfer, sender->last_acked, &next_acked); | |
| 199 if (lose_next_ack_) { | |
| 200 next_ack_delay = FindNextAck(transfer, next_acked, &next_acked); | |
| 201 } | |
| 202 sender->next_acked = next_acked; | |
| 203 return next_ack_delay; | |
| 204 } | |
| 205 | |
| 206 QuicTime::Delta SendAlgorithmSimulator::FindNextAck( | |
| 207 const Transfer* transfer, | |
| 208 QuicPacketNumber last_acked, | |
| 209 QuicPacketNumber* next_acked) const { | |
| 210 *next_acked = last_acked; | |
| 211 QuicTime::Delta ack_delay = QuicTime::Delta::Infinite(); | |
| 212 // Remove any packets that are simulated as lost. | |
| 213 for (list<SentPacket>::const_iterator it = sent_packets_.begin(); | |
| 214 it != sent_packets_.end(); ++it) { | |
| 215 if (transfer != it->transfer) { | |
| 216 continue; | |
| 217 } | |
| 218 // Skip over any packets less than or equal to last_acked. | |
| 219 if (it->packet_number <= last_acked) { | |
| 220 continue; | |
| 221 } | |
| 222 // Lost packets don't trigger an ack. | |
| 223 if (it->lost) { | |
| 224 continue; | |
| 225 } | |
| 226 DCHECK_LT(*next_acked, it->packet_number); | |
| 227 // Consider a delayed ack for the current next_acked. | |
| 228 if (ack_delay < it->ack_time - clock_->Now()) { | |
| 229 break; | |
| 230 } | |
| 231 *next_acked = it->packet_number; | |
| 232 ack_delay = it->ack_time - clock_->Now(); | |
| 233 if (HasRecentLostPackets(transfer, *next_acked) || | |
| 234 (*next_acked - last_acked) >= 2) { | |
| 235 break; | |
| 236 } | |
| 237 ack_delay = ack_delay + delayed_ack_timer_; | |
| 238 } | |
| 239 | |
| 240 DVLOG(1) << "FindNextAck found next_acked_:" << transfer->sender->next_acked | |
| 241 << " last_acked:" << transfer->sender->last_acked | |
| 242 << " ack_time(ms):" << ack_delay.ToMilliseconds(); | |
| 243 return ack_delay; | |
| 244 } | |
| 245 | |
| 246 bool SendAlgorithmSimulator::HasRecentLostPackets( | |
| 247 const Transfer* transfer, | |
| 248 QuicPacketNumber next_acked) const { | |
| 249 QuicPacketNumber last_packet = transfer->sender->last_acked; | |
| 250 for (list<SentPacket>::const_iterator it = sent_packets_.begin(); | |
| 251 it != sent_packets_.end() && it->packet_number < next_acked; ++it) { | |
| 252 if (transfer != it->transfer) { | |
| 253 continue; | |
| 254 } | |
| 255 // Lost packets don't trigger an ack. | |
| 256 if (it->lost) { | |
| 257 return true; | |
| 258 } | |
| 259 // Buffer dropped packets are skipped automatically, but still end up | |
| 260 // being lost and cause acks to be sent immediately. | |
| 261 if (it->packet_number > last_packet + 1) { | |
| 262 return true; | |
| 263 } | |
| 264 last_packet = it->packet_number; | |
| 265 } | |
| 266 return false; | |
| 267 } | |
| 268 | |
| 269 void SendAlgorithmSimulator::HandlePendingAck(Transfer* transfer) { | |
| 270 Sender* sender = transfer->sender; | |
| 271 DCHECK_LT(sender->last_acked, sender->next_acked); | |
| 272 SendAlgorithmInterface::CongestionVector acked_packets; | |
| 273 SendAlgorithmInterface::CongestionVector lost_packets; | |
| 274 DVLOG(1) << "Acking packets from:" << sender->last_acked << " to " | |
| 275 << sender->next_acked | |
| 276 << " bytes_in_flight:" << transfer->bytes_in_flight | |
| 277 << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms"; | |
| 278 // Some entries may be missing from the sent_packets_ array, if they were | |
| 279 // dropped due to buffer overruns. | |
| 280 SentPacket largest_observed; | |
| 281 list<SentPacket>::iterator it = sent_packets_.begin(); | |
| 282 while (sender->last_acked < sender->next_acked) { | |
| 283 ++sender->last_acked; | |
| 284 // Find the next SentPacket for this transfer. | |
| 285 while (it->transfer != transfer) { | |
| 286 DCHECK(it != sent_packets_.end()); | |
| 287 ++it; | |
| 288 } | |
| 289 // If it's missing from the array, it's a loss. | |
| 290 if (it->packet_number > sender->last_acked) { | |
| 291 DVLOG(1) << "Lost packet:" << sender->last_acked | |
| 292 << " dropped by buffer overflow."; | |
| 293 lost_packets.push_back(std::make_pair(sender->last_acked, kPacketSize)); | |
| 294 continue; | |
| 295 } | |
| 296 if (it->lost) { | |
| 297 lost_packets.push_back(std::make_pair(sender->last_acked, kPacketSize)); | |
| 298 } else { | |
| 299 acked_packets.push_back(std::make_pair(sender->last_acked, kPacketSize)); | |
| 300 } | |
| 301 // This packet has been acked or lost, remove it from sent_packets_. | |
| 302 largest_observed = *it; | |
| 303 sent_packets_.erase(it++); | |
| 304 } | |
| 305 | |
| 306 DCHECK(!largest_observed.lost); | |
| 307 DVLOG(1) << "Updating RTT from send_time:" | |
| 308 << largest_observed.send_time.ToDebuggingValue() | |
| 309 << " to ack_time:" << largest_observed.ack_time.ToDebuggingValue(); | |
| 310 QuicTime::Delta measured_rtt = | |
| 311 largest_observed.ack_time - largest_observed.send_time; | |
| 312 DCHECK_GE(measured_rtt.ToMicroseconds(), rtt_.ToMicroseconds()); | |
| 313 sender->rtt_stats->UpdateRtt(measured_rtt, QuicTime::Delta::Zero(), | |
| 314 clock_->Now()); | |
| 315 sender->send_algorithm->OnCongestionEvent(true, transfer->bytes_in_flight, | |
| 316 acked_packets, lost_packets); | |
| 317 DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()), | |
| 318 transfer->bytes_in_flight); | |
| 319 transfer->bytes_in_flight -= | |
| 320 kPacketSize * (acked_packets.size() + lost_packets.size()); | |
| 321 | |
| 322 sender->RecordStats(); | |
| 323 transfer->bytes_acked += acked_packets.size() * kPacketSize; | |
| 324 transfer->bytes_lost += lost_packets.size() * kPacketSize; | |
| 325 if (transfer->bytes_acked >= transfer->num_bytes) { | |
| 326 // Remove completed transfers and record transfer bandwidth. | |
| 327 QuicTime::Delta transfer_time = clock_->Now() - transfer->start_time; | |
| 328 sender->last_transfer_loss_rate = | |
| 329 static_cast<float>(transfer->bytes_lost) / | |
| 330 (transfer->bytes_lost + transfer->bytes_acked); | |
| 331 sender->last_transfer_bandwidth = QuicBandwidth::FromBytesAndTimeDelta( | |
| 332 transfer->num_bytes, transfer_time); | |
| 333 DCHECK_GE(bandwidth_.ToBitsPerSecond(), | |
| 334 sender->last_transfer_bandwidth.ToBitsPerSecond()); | |
| 335 for (vector<Transfer>::iterator it = pending_transfers_.begin(); | |
| 336 it != pending_transfers_.end(); ++it) { | |
| 337 if (transfer == &(*it)) { | |
| 338 pending_transfers_.erase(it); | |
| 339 break; | |
| 340 } | |
| 341 } | |
| 342 } | |
| 343 } | |
| 344 | |
| 345 void SendAlgorithmSimulator::SendDataNow(Transfer* transfer) { | |
| 346 Sender* sender = transfer->sender; | |
| 347 ++sender->last_sent; | |
| 348 DVLOG(1) << "Sending packet:" << sender->last_sent | |
| 349 << " name:" << transfer->name | |
| 350 << " bytes_in_flight:" << transfer->bytes_in_flight | |
| 351 << " cwnd:" << sender->send_algorithm->GetCongestionWindow() | |
| 352 << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms"; | |
| 353 sender->send_algorithm->OnPacketSent(clock_->Now(), transfer->bytes_in_flight, | |
| 354 sender->last_sent, kPacketSize, | |
| 355 HAS_RETRANSMITTABLE_DATA); | |
| 356 // Lose the packet immediately if the buffer is full. | |
| 357 if (sent_packets_.size() * kPacketSize < buffer_size_) { | |
| 358 // TODO(ianswett): This buffer simulation is an approximation. | |
| 359 // An ack time of zero means loss. | |
| 360 bool packet_lost = | |
| 361 forward_loss_rate_ * std::numeric_limits<uint64_t>::max() > | |
| 362 simple_random_.RandUint64(); | |
| 363 // Handle correlated loss. | |
| 364 if (!sent_packets_.empty() && sent_packets_.back().lost && | |
| 365 loss_correlation_ * std::numeric_limits<uint64_t>::max() > | |
| 366 simple_random_.RandUint64()) { | |
| 367 packet_lost = true; | |
| 368 } | |
| 369 DVLOG(1) << "losing packet:" << sender->last_sent | |
| 370 << " name:" << transfer->name << " due to random loss."; | |
| 371 | |
| 372 // If the number of bytes in flight are less than the bdp, there's | |
| 373 // no buffering delay. Bytes lost from the buffer are not counted. | |
| 374 QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_); | |
| 375 QuicTime ack_time = clock_->Now() + rtt_ + sender->additional_rtt; | |
| 376 if (kPacketSize > bdp) { | |
| 377 ack_time = ack_time + bandwidth_.TransferTime(kPacketSize - bdp); | |
| 378 } | |
| 379 QuicTime queue_ack_time = sent_packets_.empty() | |
| 380 ? QuicTime::Zero() | |
| 381 : sent_packets_.back().ack_time + | |
| 382 bandwidth_.TransferTime(kPacketSize); | |
| 383 ack_time = std::max(ack_time, queue_ack_time); | |
| 384 sent_packets_.push_back(SentPacket(sender->last_sent, clock_->Now(), | |
| 385 ack_time, packet_lost, transfer)); | |
| 386 } else { | |
| 387 DVLOG(1) << "losing packet:" << sender->last_sent | |
| 388 << " name:" << transfer->name << " because the buffer was full."; | |
| 389 } | |
| 390 transfer->bytes_in_flight += kPacketSize; | |
| 391 } | |
| 392 | |
| 393 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2193073003:
Move shared files in net/quic/ into net/quic/core/ (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master