net/quic/congestion_control/send_algorithm_simulator.cc - platform/external/chromium_org - Git at Google

 // 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 <limits>

 #include "base/logging.h"
 #include "base/rand_util.h"
 #include "net/quic/crypto/quic_random.h"

 using std::list;
 using std::make_pair;
 using std::max;
 using std::min;
 using std::vector;

 namespace net {

 namespace {

 const QuicByteCount kPacketSize = 1200;

 }  // namespace

 SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
                                        RttStats* rtt_stats)
     : send_algorithm(send_algorithm),
       rtt_stats(rtt_stats),
       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::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 seed = base::RandInt(0, std::numeric_limits<int32>::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());
 }

 void SendAlgorithmSimulator::AddTransfer(
     Sender* sender, size_t num_bytes, QuicTime start_time) {
   pending_transfers_.push_back(Transfer(sender, num_bytes, start_time));
   // Record initial stats from when the transfer begins.
   pending_transfers_.back().sender->RecordStats();
 }

 void SendAlgorithmSimulator::TransferBytes() {
   TransferBytes(kuint64max, QuicTime::Delta::Infinite());
 }

 void SendAlgorithmSimulator::TransferBytes(QuicByteCount max_bytes,
                                            QuicTime::Delta max_time) {
   const QuicTime end_time = max_time.IsInfinite() ?
       QuicTime::Zero().Add(QuicTime::Delta::Infinite()) :
       clock_->Now().Add(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 sequence
       // numbers.
       clock_->AdvanceTime(ack_event.time_delta);
       HandlePendingAck(ack_event.transfer);
     } else {
       DVLOG(1) << "Sending, 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.Subtract(clock_->Now());
     if (clock_->Now() >= it->start_time) {
       transfer_send_time =
           it->sender->send_algorithm->TimeUntilSend(
               clock_->Now(), it->bytes_in_flight, HAS_RETRANSMITTABLE_DATA);
     }
     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();
   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_ * kuint64max > simple_random_.RandUint64();
   }

   QuicPacketSequenceNumber 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,
     QuicPacketSequenceNumber last_acked,
     QuicPacketSequenceNumber* 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->sequence_number <= last_acked) {
       continue;
     }
     // Lost packets don't trigger an ack.
     if (it->lost) {
       continue;
     }
     DCHECK_LT(*next_acked, it->sequence_number);
     // Consider a delayed ack for the current next_acked.
     if (ack_delay < it->ack_time.Subtract(clock_->Now())) {
       break;
     }
     *next_acked = it->sequence_number;
     ack_delay = it->ack_time.Subtract(clock_->Now());
     if (HasRecentLostPackets(transfer, *next_acked) ||
         (*next_acked - last_acked) >= 2) {
       break;
     }
     ack_delay = ack_delay.Add(delayed_ack_timer_);
   }

   DVLOG(1) << "FindNextAcked found next_acked_:"
            << transfer->sender->next_acked
            << " last_acked:" << transfer->sender->last_acked
            << " ack_delay(ms):" << ack_delay.ToMilliseconds();
   return ack_delay;
 }

 bool SendAlgorithmSimulator::HasRecentLostPackets(
     const Transfer* transfer, QuicPacketSequenceNumber next_acked) const {
   QuicPacketSequenceNumber last_packet = transfer->sender->last_acked;
   for (list<SentPacket>::const_iterator it = sent_packets_.begin();
        it != sent_packets_.end() && it->sequence_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->sequence_number > last_packet + 1) {
       return true;
     }
     last_packet = it->sequence_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;
     TransmissionInfo info = TransmissionInfo();
     info.bytes_sent = kPacketSize;
     info.in_flight = true;
     // 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->sequence_number > sender->last_acked) {
       DVLOG(1) << "Lost packet:" << sender->last_acked
                << " dropped by buffer overflow.";
       lost_packets.push_back(make_pair(sender->last_acked, info));
       continue;
     }
     if (it->lost) {
       lost_packets.push_back(make_pair(sender->last_acked, info));
     } else {
       acked_packets.push_back(make_pair(sender->last_acked, info));
     }
     // This packet has been acked or lost, remove it from sent_packets_.
     largest_observed = *it;
     sent_packets_.erase(it++);
   }

   DCHECK(largest_observed.ack_time.IsInitialized());
   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.Subtract(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().Subtract(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
            << " bytes_in_flight:" << transfer->bytes_in_flight
            << " 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_ * kuint64max > simple_random_.RandUint64();
     // Handle correlated loss.
     if (!sent_packets_.empty() && sent_packets_.back().lost &&
         loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
       packet_lost = true;
     }
     DVLOG(1) << "losing packet:" << sender->last_sent
              << " 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().Add(rtt_);
     if (kPacketSize > bdp) {
       ack_time = ack_time.Add(bandwidth_.TransferTime(kPacketSize - bdp));
     }
     QuicTime queue_ack_time = sent_packets_.empty() ? QuicTime::Zero() :
         sent_packets_.back().ack_time.Add(bandwidth_.TransferTime(kPacketSize));
     ack_time = QuicTime::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
              << " because the buffer was full.";
   }
   transfer->bytes_in_flight += kPacketSize;
 }

 // Advance the time by |delta| without sending anything.
 void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
   clock_->AdvanceTime(delta);
 }

 }  // namespace net
	// 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 <limits>

	#include "base/logging.h"
	#include "base/rand_util.h"
	#include "net/quic/crypto/quic_random.h"

	using std::list;
	using std::make_pair;
	using std::max;
	using std::min;
	using std::vector;

	namespace net {

	namespace {

	const QuicByteCount kPacketSize = 1200;

	} // namespace

	SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
	RttStats* rtt_stats)
	: send_algorithm(send_algorithm),
	rtt_stats(rtt_stats),
	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::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 seed = base::RandInt(0, std::numeric_limits<int32>::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());
	}

	void SendAlgorithmSimulator::AddTransfer(
	Sender* sender, size_t num_bytes, QuicTime start_time) {
	pending_transfers_.push_back(Transfer(sender, num_bytes, start_time));
	// Record initial stats from when the transfer begins.
	pending_transfers_.back().sender->RecordStats();
	}

	void SendAlgorithmSimulator::TransferBytes() {
	TransferBytes(kuint64max, QuicTime::Delta::Infinite());
	}

	void SendAlgorithmSimulator::TransferBytes(QuicByteCount max_bytes,
	QuicTime::Delta max_time) {
	const QuicTime end_time = max_time.IsInfinite() ?
	QuicTime::Zero().Add(QuicTime::Delta::Infinite()) :
	clock_->Now().Add(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 sequence
	// numbers.
	clock_->AdvanceTime(ack_event.time_delta);
	HandlePendingAck(ack_event.transfer);
	} else {
	DVLOG(1) << "Sending, 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.Subtract(clock_->Now());
	if (clock_->Now() >= it->start_time) {
	transfer_send_time =
	it->sender->send_algorithm->TimeUntilSend(
	clock_->Now(), it->bytes_in_flight, HAS_RETRANSMITTABLE_DATA);
	}
	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();
	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_ * kuint64max > simple_random_.RandUint64();
	}

	QuicPacketSequenceNumber 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,
	QuicPacketSequenceNumber last_acked,
	QuicPacketSequenceNumber* 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->sequence_number <= last_acked) {
	continue;
	}
	// Lost packets don't trigger an ack.
	if (it->lost) {
	continue;
	}
	DCHECK_LT(*next_acked, it->sequence_number);
	// Consider a delayed ack for the current next_acked.
	if (ack_delay < it->ack_time.Subtract(clock_->Now())) {
	break;
	}
	*next_acked = it->sequence_number;
	ack_delay = it->ack_time.Subtract(clock_->Now());
	if (HasRecentLostPackets(transfer, *next_acked) \|\|
	(*next_acked - last_acked) >= 2) {
	break;
	}
	ack_delay = ack_delay.Add(delayed_ack_timer_);
	}

	DVLOG(1) << "FindNextAcked found next_acked_:"
	<< transfer->sender->next_acked
	<< " last_acked:" << transfer->sender->last_acked
	<< " ack_delay(ms):" << ack_delay.ToMilliseconds();
	return ack_delay;
	}

	bool SendAlgorithmSimulator::HasRecentLostPackets(
	const Transfer* transfer, QuicPacketSequenceNumber next_acked) const {
	QuicPacketSequenceNumber last_packet = transfer->sender->last_acked;
	for (list<SentPacket>::const_iterator it = sent_packets_.begin();
	it != sent_packets_.end() && it->sequence_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->sequence_number > last_packet + 1) {
	return true;
	}
	last_packet = it->sequence_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;
	TransmissionInfo info = TransmissionInfo();
	info.bytes_sent = kPacketSize;
	info.in_flight = true;
	// 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->sequence_number > sender->last_acked) {
	DVLOG(1) << "Lost packet:" << sender->last_acked
	<< " dropped by buffer overflow.";
	lost_packets.push_back(make_pair(sender->last_acked, info));
	continue;
	}
	if (it->lost) {
	lost_packets.push_back(make_pair(sender->last_acked, info));
	} else {
	acked_packets.push_back(make_pair(sender->last_acked, info));
	}
	// This packet has been acked or lost, remove it from sent_packets_.
	largest_observed = *it;
	sent_packets_.erase(it++);
	}

	DCHECK(largest_observed.ack_time.IsInitialized());
	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.Subtract(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().Subtract(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
	<< " bytes_in_flight:" << transfer->bytes_in_flight
	<< " 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_ * kuint64max > simple_random_.RandUint64();
	// Handle correlated loss.
	if (!sent_packets_.empty() && sent_packets_.back().lost &&
	loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
	packet_lost = true;
	}
	DVLOG(1) << "losing packet:" << sender->last_sent
	<< " 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().Add(rtt_);
	if (kPacketSize > bdp) {
	ack_time = ack_time.Add(bandwidth_.TransferTime(kPacketSize - bdp));
	}
	QuicTime queue_ack_time = sent_packets_.empty() ? QuicTime::Zero() :
	sent_packets_.back().ack_time.Add(bandwidth_.TransferTime(kPacketSize));
	ack_time = QuicTime::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
	<< " because the buffer was full.";
	}
	transfer->bytes_in_flight += kPacketSize;
	}

	// Advance the time by \|delta\| without sending anything.
	void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
	clock_->AdvanceTime(delta);
	}

	} // namespace net