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