Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1417)

Unified Diff: net/quic/congestion_control/send_algorithm_simulator.cc

Issue 2193073003: Move shared files in net/quic/ into net/quic/core/ (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: io_thread_unittest.cc Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: net/quic/congestion_control/send_algorithm_simulator.cc
diff --git a/net/quic/congestion_control/send_algorithm_simulator.cc b/net/quic/congestion_control/send_algorithm_simulator.cc
deleted file mode 100644
index d1eac0c2a3f6b188ccab68a09d72c370c40ec4eb..0000000000000000000000000000000000000000
--- a/net/quic/congestion_control/send_algorithm_simulator.cc
+++ /dev/null
@@ -1,393 +0,0 @@
-// 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/send_algorithm_simulator.h"
-
-#include <stdint.h>
-
-#include <limits>
-
-#include "base/logging.h"
-#include "base/rand_util.h"
-#include "net/quic/crypto/quic_random.h"
-
-using std::list;
-using std::max;
-using std::min;
-using std::string;
-using std::vector;
-
-namespace net {
-
-namespace {
-
-const QuicByteCount kPacketSize = 1200;
-
-} // namespace
-
-SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
- RttStats* rtt_stats)
- : Sender(send_algorithm, rtt_stats, QuicTime::Delta::Zero()) {}
-
-SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
- RttStats* rtt_stats,
- QuicTime::Delta additional_rtt)
- : send_algorithm(send_algorithm),
- rtt_stats(rtt_stats),
- additional_rtt(additional_rtt),
- last_sent(0),
- last_acked(0),
- next_acked(1),
- max_cwnd(0),
- min_cwnd(100000),
- max_cwnd_drop(0),
- last_cwnd(0),
- last_transfer_bandwidth(QuicBandwidth::Zero()),
- last_transfer_loss_rate(0) {}
-
-SendAlgorithmSimulator::Transfer::Transfer(Sender* sender,
- QuicByteCount num_bytes,
- QuicTime start_time,
- string name)
- : sender(sender),
- num_bytes(num_bytes),
- bytes_acked(0),
- bytes_lost(0),
- bytes_in_flight(0),
- start_time(start_time),
- name(name) {}
-
-SendAlgorithmSimulator::SendAlgorithmSimulator(MockClock* clock,
- QuicBandwidth bandwidth,
- QuicTime::Delta rtt)
- : clock_(clock),
- lose_next_ack_(false),
- forward_loss_rate_(0),
- reverse_loss_rate_(0),
- loss_correlation_(0),
- bandwidth_(bandwidth),
- rtt_(rtt),
- buffer_size_(1000000),
- delayed_ack_timer_(QuicTime::Delta::FromMilliseconds(100)) {
- uint32_t seed = base::RandInt(0, std::numeric_limits<int32_t>::max());
- DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
- simple_random_.set_seed(seed);
-}
-
-SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
-
-void SendAlgorithmSimulator::AddTransfer(Sender* sender, size_t num_bytes) {
- AddTransfer(sender, num_bytes, clock_->Now(),
- StringPrintf("#%zu", pending_transfers_.size()));
-}
-
-void SendAlgorithmSimulator::AddTransfer(Sender* sender,
- size_t num_bytes,
- QuicTime start_time,
- string name) {
- pending_transfers_.push_back(Transfer(sender, num_bytes, start_time, name));
- // Record initial stats from when the transfer begins.
- pending_transfers_.back().sender->RecordStats();
-}
-
-void SendAlgorithmSimulator::TransferBytes() {
- TransferBytes(std::numeric_limits<uint64_t>::max(),
- QuicTime::Delta::Infinite());
-}
-
-void SendAlgorithmSimulator::TransferBytes(QuicByteCount max_bytes,
- QuicTime::Delta max_time) {
- const QuicTime end_time = max_time.IsInfinite()
- ? QuicTime::Zero() + QuicTime::Delta::Infinite()
- : clock_->Now() + max_time;
- QuicByteCount bytes_sent = 0;
- while (!pending_transfers_.empty() && clock_->Now() < end_time &&
- bytes_sent < max_bytes) {
- // Determine the times of next send and of the next ack arrival.
- PacketEvent send_event = NextSendEvent();
- PacketEvent ack_event = NextAckEvent();
- // If both times are infinite, fire a TLP.
- if (ack_event.time_delta.IsInfinite() &&
- send_event.time_delta.IsInfinite()) {
- DVLOG(1) << "Both times are infinite, simulating a TLP.";
- // TODO(ianswett): Use a more sophisticated TLP timer or never lose
- // the last ack?
- clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
- SendDataNow(&pending_transfers_.front());
- } else if (ack_event.time_delta < send_event.time_delta) {
- DVLOG(1) << "Handling ack of largest observed:"
- << ack_event.transfer->sender->next_acked
- << ", advancing time:" << ack_event.time_delta.ToMicroseconds()
- << "us";
- // Ack data all the data up to ack time and lose any missing packet
- // numbers.
- clock_->AdvanceTime(ack_event.time_delta);
- HandlePendingAck(ack_event.transfer);
- } else {
- DVLOG(1) << "Sending transfer '" << send_event.transfer->name
- << "', advancing time:" << send_event.time_delta.ToMicroseconds()
- << "us";
- clock_->AdvanceTime(send_event.time_delta);
- SendDataNow(send_event.transfer);
- bytes_sent += kPacketSize;
- }
- }
-}
-
-SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextSendEvent() {
- QuicTime::Delta next_send_time = QuicTime::Delta::Infinite();
- Transfer* transfer = nullptr;
- for (vector<Transfer>::iterator it = pending_transfers_.begin();
- it != pending_transfers_.end(); ++it) {
- // If we've already sent enough bytes, wait for them to be acked.
- if (it->bytes_acked + it->bytes_in_flight >= it->num_bytes) {
- continue;
- }
- // If the flow hasn't started, use the start time.
- QuicTime::Delta transfer_send_time = it->start_time - clock_->Now();
- if (clock_->Now() >= it->start_time) {
- transfer_send_time = it->sender->send_algorithm->TimeUntilSend(
- clock_->Now(), it->bytes_in_flight);
- }
- if (transfer_send_time < next_send_time) {
- next_send_time = transfer_send_time;
- transfer = &(*it);
- }
- }
- DVLOG(1) << "NextSendTime returning delta(ms):"
- << next_send_time.ToMilliseconds() << ", transfer '"
- << transfer->name;
- return PacketEvent(next_send_time, transfer);
-}
-
-// NextAck takes into account packet loss in both forward and reverse
-// direction, as well as correlated losses. And it assumes the receiver acks
-// every other packet when there is no loss.
-SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextAckEvent() {
- if (sent_packets_.empty()) {
- DVLOG(1) << "No outstanding packets to ack for any transfer.";
- return PacketEvent(QuicTime::Delta::Infinite(), nullptr);
- }
-
- // For each connection, find the next acked packet.
- QuicTime::Delta ack_time = QuicTime::Delta::Infinite();
- Transfer* transfer = nullptr;
- for (vector<Transfer>::iterator it = pending_transfers_.begin();
- it != pending_transfers_.end(); ++it) {
- QuicTime::Delta transfer_ack_time = FindNextAcked(&(*it));
- if (transfer_ack_time < ack_time) {
- ack_time = transfer_ack_time;
- transfer = &(*it);
- }
- }
-
- return PacketEvent(ack_time, transfer);
-}
-
-QuicTime::Delta SendAlgorithmSimulator::FindNextAcked(Transfer* transfer) {
- Sender* sender = transfer->sender;
- if (sender->next_acked == sender->last_acked) {
- // Determine if the next ack is lost only once, to ensure determinism.
- lose_next_ack_ = reverse_loss_rate_ * std::numeric_limits<uint64_t>::max() >
- simple_random_.RandUint64();
- }
-
- QuicPacketNumber next_acked = sender->last_acked;
- QuicTime::Delta next_ack_delay =
- FindNextAck(transfer, sender->last_acked, &next_acked);
- if (lose_next_ack_) {
- next_ack_delay = FindNextAck(transfer, next_acked, &next_acked);
- }
- sender->next_acked = next_acked;
- return next_ack_delay;
-}
-
-QuicTime::Delta SendAlgorithmSimulator::FindNextAck(
- const Transfer* transfer,
- QuicPacketNumber last_acked,
- QuicPacketNumber* next_acked) const {
- *next_acked = last_acked;
- QuicTime::Delta ack_delay = QuicTime::Delta::Infinite();
- // Remove any packets that are simulated as lost.
- for (list<SentPacket>::const_iterator it = sent_packets_.begin();
- it != sent_packets_.end(); ++it) {
- if (transfer != it->transfer) {
- continue;
- }
- // Skip over any packets less than or equal to last_acked.
- if (it->packet_number <= last_acked) {
- continue;
- }
- // Lost packets don't trigger an ack.
- if (it->lost) {
- continue;
- }
- DCHECK_LT(*next_acked, it->packet_number);
- // Consider a delayed ack for the current next_acked.
- if (ack_delay < it->ack_time - clock_->Now()) {
- break;
- }
- *next_acked = it->packet_number;
- ack_delay = it->ack_time - clock_->Now();
- if (HasRecentLostPackets(transfer, *next_acked) ||
- (*next_acked - last_acked) >= 2) {
- break;
- }
- ack_delay = ack_delay + delayed_ack_timer_;
- }
-
- DVLOG(1) << "FindNextAck found next_acked_:" << transfer->sender->next_acked
- << " last_acked:" << transfer->sender->last_acked
- << " ack_time(ms):" << ack_delay.ToMilliseconds();
- return ack_delay;
-}
-
-bool SendAlgorithmSimulator::HasRecentLostPackets(
- const Transfer* transfer,
- QuicPacketNumber next_acked) const {
- QuicPacketNumber last_packet = transfer->sender->last_acked;
- for (list<SentPacket>::const_iterator it = sent_packets_.begin();
- it != sent_packets_.end() && it->packet_number < next_acked; ++it) {
- if (transfer != it->transfer) {
- continue;
- }
- // Lost packets don't trigger an ack.
- if (it->lost) {
- return true;
- }
- // Buffer dropped packets are skipped automatically, but still end up
- // being lost and cause acks to be sent immediately.
- if (it->packet_number > last_packet + 1) {
- return true;
- }
- last_packet = it->packet_number;
- }
- return false;
-}
-
-void SendAlgorithmSimulator::HandlePendingAck(Transfer* transfer) {
- Sender* sender = transfer->sender;
- DCHECK_LT(sender->last_acked, sender->next_acked);
- SendAlgorithmInterface::CongestionVector acked_packets;
- SendAlgorithmInterface::CongestionVector lost_packets;
- DVLOG(1) << "Acking packets from:" << sender->last_acked << " to "
- << sender->next_acked
- << " bytes_in_flight:" << transfer->bytes_in_flight
- << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
- // Some entries may be missing from the sent_packets_ array, if they were
- // dropped due to buffer overruns.
- SentPacket largest_observed;
- list<SentPacket>::iterator it = sent_packets_.begin();
- while (sender->last_acked < sender->next_acked) {
- ++sender->last_acked;
- // Find the next SentPacket for this transfer.
- while (it->transfer != transfer) {
- DCHECK(it != sent_packets_.end());
- ++it;
- }
- // If it's missing from the array, it's a loss.
- if (it->packet_number > sender->last_acked) {
- DVLOG(1) << "Lost packet:" << sender->last_acked
- << " dropped by buffer overflow.";
- lost_packets.push_back(std::make_pair(sender->last_acked, kPacketSize));
- continue;
- }
- if (it->lost) {
- lost_packets.push_back(std::make_pair(sender->last_acked, kPacketSize));
- } else {
- acked_packets.push_back(std::make_pair(sender->last_acked, kPacketSize));
- }
- // This packet has been acked or lost, remove it from sent_packets_.
- largest_observed = *it;
- sent_packets_.erase(it++);
- }
-
- DCHECK(!largest_observed.lost);
- DVLOG(1) << "Updating RTT from send_time:"
- << largest_observed.send_time.ToDebuggingValue()
- << " to ack_time:" << largest_observed.ack_time.ToDebuggingValue();
- QuicTime::Delta measured_rtt =
- largest_observed.ack_time - largest_observed.send_time;
- DCHECK_GE(measured_rtt.ToMicroseconds(), rtt_.ToMicroseconds());
- sender->rtt_stats->UpdateRtt(measured_rtt, QuicTime::Delta::Zero(),
- clock_->Now());
- sender->send_algorithm->OnCongestionEvent(true, transfer->bytes_in_flight,
- acked_packets, lost_packets);
- DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()),
- transfer->bytes_in_flight);
- transfer->bytes_in_flight -=
- kPacketSize * (acked_packets.size() + lost_packets.size());
-
- sender->RecordStats();
- transfer->bytes_acked += acked_packets.size() * kPacketSize;
- transfer->bytes_lost += lost_packets.size() * kPacketSize;
- if (transfer->bytes_acked >= transfer->num_bytes) {
- // Remove completed transfers and record transfer bandwidth.
- QuicTime::Delta transfer_time = clock_->Now() - transfer->start_time;
- sender->last_transfer_loss_rate =
- static_cast<float>(transfer->bytes_lost) /
- (transfer->bytes_lost + transfer->bytes_acked);
- sender->last_transfer_bandwidth = QuicBandwidth::FromBytesAndTimeDelta(
- transfer->num_bytes, transfer_time);
- DCHECK_GE(bandwidth_.ToBitsPerSecond(),
- sender->last_transfer_bandwidth.ToBitsPerSecond());
- for (vector<Transfer>::iterator it = pending_transfers_.begin();
- it != pending_transfers_.end(); ++it) {
- if (transfer == &(*it)) {
- pending_transfers_.erase(it);
- break;
- }
- }
- }
-}
-
-void SendAlgorithmSimulator::SendDataNow(Transfer* transfer) {
- Sender* sender = transfer->sender;
- ++sender->last_sent;
- DVLOG(1) << "Sending packet:" << sender->last_sent
- << " name:" << transfer->name
- << " bytes_in_flight:" << transfer->bytes_in_flight
- << " cwnd:" << sender->send_algorithm->GetCongestionWindow()
- << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
- sender->send_algorithm->OnPacketSent(clock_->Now(), transfer->bytes_in_flight,
- sender->last_sent, kPacketSize,
- HAS_RETRANSMITTABLE_DATA);
- // Lose the packet immediately if the buffer is full.
- if (sent_packets_.size() * kPacketSize < buffer_size_) {
- // TODO(ianswett): This buffer simulation is an approximation.
- // An ack time of zero means loss.
- bool packet_lost =
- forward_loss_rate_ * std::numeric_limits<uint64_t>::max() >
- simple_random_.RandUint64();
- // Handle correlated loss.
- if (!sent_packets_.empty() && sent_packets_.back().lost &&
- loss_correlation_ * std::numeric_limits<uint64_t>::max() >
- simple_random_.RandUint64()) {
- packet_lost = true;
- }
- DVLOG(1) << "losing packet:" << sender->last_sent
- << " name:" << transfer->name << " due to random loss.";
-
- // If the number of bytes in flight are less than the bdp, there's
- // no buffering delay. Bytes lost from the buffer are not counted.
- QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_);
- QuicTime ack_time = clock_->Now() + rtt_ + sender->additional_rtt;
- if (kPacketSize > bdp) {
- ack_time = ack_time + bandwidth_.TransferTime(kPacketSize - bdp);
- }
- QuicTime queue_ack_time = sent_packets_.empty()
- ? QuicTime::Zero()
- : sent_packets_.back().ack_time +
- bandwidth_.TransferTime(kPacketSize);
- ack_time = std::max(ack_time, queue_ack_time);
- sent_packets_.push_back(SentPacket(sender->last_sent, clock_->Now(),
- ack_time, packet_lost, transfer));
- } else {
- DVLOG(1) << "losing packet:" << sender->last_sent
- << " name:" << transfer->name << " because the buffer was full.";
- }
- transfer->bytes_in_flight += kPacketSize;
-}
-
-} // namespace net
« no previous file with comments | « net/quic/congestion_control/send_algorithm_simulator.h ('k') | net/quic/congestion_control/tcp_cubic_sender_base.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698