1// Copyright (c) 2013 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/pacing_sender.h"
6
7#include "base/logging.h"
8#include "base/memory/scoped_ptr.h"
9#include "net/quic/quic_protocol.h"
10#include "net/quic/test_tools/mock_clock.h"
11#include "net/quic/test_tools/quic_test_utils.h"
12#include "testing/gtest/include/gtest/gtest.h"
13
14using testing::Return;
15using testing::StrictMock;
16using testing::_;
17
18namespace net {
19namespace test {
20
21const QuicByteCount kBytesInFlight = 1024;
22
23class PacingSenderTest : public ::testing::Test {
24 protected:
25  PacingSenderTest()
26      : zero_time_(QuicTime::Delta::Zero()),
27        infinite_time_(QuicTime::Delta::Infinite()),
28        sequence_number_(1),
29        mock_sender_(new StrictMock<MockSendAlgorithm>()),
30        pacing_sender_(new PacingSender(mock_sender_,
31                                        QuicTime::Delta::FromMilliseconds(1),
32                                        0)) {
33    // Pick arbitrary time.
34    clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(9));
35  }
36
37  virtual ~PacingSenderTest() {}
38
39  void CheckPacketIsSentImmediately() {
40    // In order for the packet to be sendable, the underlying sender must
41    // permit it to be sent immediately.
42    for (int i = 0; i < 2; ++i) {
43      EXPECT_CALL(*mock_sender_, TimeUntilSend(clock_.Now(),
44                                               kBytesInFlight,
45                                               HAS_RETRANSMITTABLE_DATA))
46          .WillOnce(Return(zero_time_));
47      // Verify that the packet can be sent immediately.
48      EXPECT_EQ(zero_time_,
49                pacing_sender_->TimeUntilSend(clock_.Now(),
50                                              kBytesInFlight,
51                                              HAS_RETRANSMITTABLE_DATA));
52    }
53
54    // Actually send the packet.
55    EXPECT_CALL(*mock_sender_,
56                OnPacketSent(clock_.Now(), kBytesInFlight, sequence_number_,
57                             kMaxPacketSize, HAS_RETRANSMITTABLE_DATA));
58    pacing_sender_->OnPacketSent(clock_.Now(), kBytesInFlight,
59                                 sequence_number_++, kMaxPacketSize,
60                                 HAS_RETRANSMITTABLE_DATA);
61  }
62
63  void CheckAckIsSentImmediately() {
64    // In order for the ack to be sendable, the underlying sender must
65    // permit it to be sent immediately.
66    EXPECT_CALL(*mock_sender_, TimeUntilSend(clock_.Now(),
67                                             0,
68                                             NO_RETRANSMITTABLE_DATA))
69        .WillOnce(Return(zero_time_));
70    // Verify that the ACK can be sent immediately.
71    EXPECT_EQ(zero_time_,
72              pacing_sender_->TimeUntilSend(clock_.Now(),
73                                            0,
74                                            NO_RETRANSMITTABLE_DATA));
75
76    // Actually send the packet.
77    EXPECT_CALL(*mock_sender_,
78                OnPacketSent(clock_.Now(), 0, sequence_number_,
79                             kMaxPacketSize, NO_RETRANSMITTABLE_DATA));
80    pacing_sender_->OnPacketSent(clock_.Now(), 0,
81                                 sequence_number_++, kMaxPacketSize,
82                                 NO_RETRANSMITTABLE_DATA);
83  }
84
85  void CheckPacketIsDelayed(QuicTime::Delta delay) {
86    // In order for the packet to be sendable, the underlying sender must
87    // permit it to be sent immediately.
88    for (int i = 0; i < 2; ++i) {
89      EXPECT_CALL(*mock_sender_, TimeUntilSend(clock_.Now(),
90                                               kBytesInFlight,
91                                               HAS_RETRANSMITTABLE_DATA))
92          .WillOnce(Return(zero_time_));
93      // Verify that the packet is delayed.
94      EXPECT_EQ(delay.ToMicroseconds(),
95                pacing_sender_->TimeUntilSend(
96                    clock_.Now(), kBytesInFlight,
97                    HAS_RETRANSMITTABLE_DATA).ToMicroseconds());
98    }
99  }
100
101  const QuicTime::Delta zero_time_;
102  const QuicTime::Delta infinite_time_;
103  MockClock clock_;
104  QuicPacketSequenceNumber sequence_number_;
105  StrictMock<MockSendAlgorithm>* mock_sender_;
106  scoped_ptr<PacingSender> pacing_sender_;
107};
108
109TEST_F(PacingSenderTest, NoSend) {
110  for (int i = 0; i < 2; ++i) {
111    EXPECT_CALL(*mock_sender_, TimeUntilSend(clock_.Now(),
112                                             kBytesInFlight,
113                                             HAS_RETRANSMITTABLE_DATA))
114        .WillOnce(Return(infinite_time_));
115    EXPECT_EQ(infinite_time_,
116              pacing_sender_->TimeUntilSend(clock_.Now(),
117                                            kBytesInFlight,
118                                            HAS_RETRANSMITTABLE_DATA));
119  }
120}
121
122TEST_F(PacingSenderTest, SendNow) {
123  for (int i = 0; i < 2; ++i) {
124    EXPECT_CALL(*mock_sender_, TimeUntilSend(clock_.Now(),
125                                             kBytesInFlight,
126                                             HAS_RETRANSMITTABLE_DATA))
127        .WillOnce(Return(zero_time_));
128    EXPECT_EQ(zero_time_,
129              pacing_sender_->TimeUntilSend(clock_.Now(),
130                                            kBytesInFlight,
131                                            HAS_RETRANSMITTABLE_DATA));
132  }
133}
134
135TEST_F(PacingSenderTest, VariousSending) {
136  // Start the test in slow start.
137  EXPECT_CALL(*mock_sender_, InSlowStart()).WillRepeatedly(Return(true));
138
139  // Configure bandwith of 1 packet per 2 ms, for which the pacing rate
140  // will be 1 packet per 1 ms.
141  EXPECT_CALL(*mock_sender_, BandwidthEstimate())
142      .WillRepeatedly(Return(QuicBandwidth::FromBytesAndTimeDelta(
143          kMaxPacketSize, QuicTime::Delta::FromMilliseconds(2))));
144
145  // Send a whole pile of packets, and verify that they are not paced.
146  for (int i = 0 ; i < 1000; ++i) {
147    CheckPacketIsSentImmediately();
148  }
149
150  // Now update the RTT and verify that packets are actually paced.
151  EXPECT_CALL(*mock_sender_, OnCongestionEvent(true, kBytesInFlight, _, _));
152  SendAlgorithmInterface::CongestionVector empty_map;
153  pacing_sender_->OnCongestionEvent(true, kBytesInFlight, empty_map, empty_map);
154
155  CheckPacketIsSentImmediately();
156  CheckPacketIsSentImmediately();
157  CheckPacketIsSentImmediately();
158
159  // The first packet was a "make up", then we sent two packets "into the
160  // future", so the delay should be 2.
161  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
162
163  // Wake up on time.
164  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(2));
165  CheckPacketIsSentImmediately();
166  CheckPacketIsSentImmediately();
167  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
168  CheckAckIsSentImmediately();
169
170  // Wake up late.
171  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(4));
172  CheckPacketIsSentImmediately();
173  CheckPacketIsSentImmediately();
174  CheckPacketIsSentImmediately();
175  CheckPacketIsSentImmediately();
176  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
177
178  // Wake up really late.
179  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(8));
180  CheckPacketIsSentImmediately();
181  CheckPacketIsSentImmediately();
182  CheckPacketIsSentImmediately();
183  CheckPacketIsSentImmediately();
184  CheckPacketIsSentImmediately();
185  CheckPacketIsSentImmediately();
186  CheckPacketIsSentImmediately();
187  CheckPacketIsSentImmediately();
188  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
189
190  // Wake up really late again, but application pause partway through.
191  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(8));
192  CheckPacketIsSentImmediately();
193  CheckPacketIsSentImmediately();
194  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
195  CheckPacketIsSentImmediately();
196  CheckPacketIsSentImmediately();
197  CheckPacketIsSentImmediately();
198  CheckPacketIsSentImmediately();
199  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
200
201  // Wake up too early.
202  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
203
204  // Wake up early, but after enough time has passed to permit a send.
205  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(1));
206  CheckPacketIsSentImmediately();
207  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
208}
209
210TEST_F(PacingSenderTest, CongestionAvoidanceSending) {
211  // Start the test in congestion avoidance.
212  EXPECT_CALL(*mock_sender_, InSlowStart()).WillRepeatedly(Return(false));
213
214  // Configure bandwith of 1 packet per 2 ms, for which the pacing rate
215  // will be 1 packet per 1 ms.
216  EXPECT_CALL(*mock_sender_, BandwidthEstimate())
217      .WillRepeatedly(Return(QuicBandwidth::FromBytesAndTimeDelta(
218          kMaxPacketSize, QuicTime::Delta::FromMilliseconds(2))));
219
220  // Send a whole pile of packets, and verify that they are not paced.
221  for (int i = 0 ; i < 1000; ++i) {
222    CheckPacketIsSentImmediately();
223  }
224
225  // Now update the RTT and verify that packets are actually paced.
226  EXPECT_CALL(*mock_sender_, OnCongestionEvent(true, kBytesInFlight, _, _));
227  SendAlgorithmInterface::CongestionVector empty_map;
228  pacing_sender_->OnCongestionEvent(true, kBytesInFlight, empty_map, empty_map);
229
230  CheckPacketIsSentImmediately();
231  CheckPacketIsSentImmediately();
232
233  // The first packet was a "make up", then we sent two packets "into the
234  // future", so the delay should be 2200us.
235  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(2200));
236
237  // Wake up on time.
238  clock_.AdvanceTime(QuicTime::Delta::FromMicroseconds(2200));
239  CheckPacketIsSentImmediately();
240  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(1600));
241  CheckAckIsSentImmediately();
242
243  // Wake up late.
244  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(4));
245  CheckPacketIsSentImmediately();
246  CheckPacketIsSentImmediately();
247  CheckPacketIsSentImmediately();
248  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(2400));
249
250  // Wake up really late.
251  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(8));
252  CheckPacketIsSentImmediately();
253  CheckPacketIsSentImmediately();
254  CheckPacketIsSentImmediately();
255  CheckPacketIsSentImmediately();
256  CheckPacketIsSentImmediately();
257  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(2400));
258
259  // Wake up really late again, but application pause partway through.
260  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(8));
261  CheckPacketIsSentImmediately();
262  CheckPacketIsSentImmediately();
263  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
264  CheckPacketIsSentImmediately();
265  CheckPacketIsSentImmediately();
266  CheckPacketIsSentImmediately();
267  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(2200));
268
269  // Wake up too early.
270  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(2200));
271
272  // Wake up early, but after enough time has passed to permit a send.
273  clock_.AdvanceTime(QuicTime::Delta::FromMicroseconds(1200));
274  CheckPacketIsSentImmediately();
275  CheckPacketIsDelayed(QuicTime::Delta::FromMicroseconds(2600));
276}
277
278TEST_F(PacingSenderTest, InitialBurst) {
279  pacing_sender_.reset();
280  mock_sender_ = new StrictMock<MockSendAlgorithm>();
281  pacing_sender_.reset(new PacingSender(mock_sender_,
282                                        QuicTime::Delta::FromMilliseconds(1),
283                                        10));
284  // Start the test in slow start.
285  EXPECT_CALL(*mock_sender_, InSlowStart()).WillRepeatedly(Return(true));
286
287  // Configure bandwith of 1 packet per 2 ms, for which the pacing rate
288  // will be 1 packet per 1 ms.
289  EXPECT_CALL(*mock_sender_, BandwidthEstimate())
290      .WillRepeatedly(Return(QuicBandwidth::FromBytesAndTimeDelta(
291          kMaxPacketSize, QuicTime::Delta::FromMilliseconds(2))));
292
293  // Update the RTT and verify that the first 10 packets aren't paced.
294  EXPECT_CALL(*mock_sender_, OnCongestionEvent(true, kBytesInFlight, _, _));
295  SendAlgorithmInterface::CongestionVector empty_map;
296  pacing_sender_->OnCongestionEvent(true, kBytesInFlight, empty_map, empty_map);
297
298  // Send 10 packets, and verify that they are not paced.
299  for (int i = 0 ; i < 10; ++i) {
300    CheckPacketIsSentImmediately();
301  }
302
303  CheckPacketIsSentImmediately();
304  CheckPacketIsSentImmediately();
305  CheckPacketIsSentImmediately();
306
307  // The first packet was a "make up", then we sent two packets "into the
308  // future", so the delay should be 2.
309  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
310  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(5));
311  CheckPacketIsSentImmediately();
312
313  // Next time TimeUntilSend is called with no bytes in flight, the tokens
314  // should be refilled and there should be no delay.
315  EXPECT_CALL(*mock_sender_,
316              TimeUntilSend(clock_.Now(),
317                            0,
318                            HAS_RETRANSMITTABLE_DATA)).
319      WillOnce(Return(zero_time_));
320  EXPECT_EQ(zero_time_,
321            pacing_sender_->TimeUntilSend(clock_.Now(),
322                                          0,
323                                          HAS_RETRANSMITTABLE_DATA));
324  for (int i = 0 ; i < 10; ++i) {
325    CheckPacketIsSentImmediately();
326  }
327
328  CheckPacketIsSentImmediately();
329  CheckPacketIsSentImmediately();
330  CheckPacketIsSentImmediately();
331
332  CheckPacketIsDelayed(QuicTime::Delta::FromMilliseconds(2));
333}
334
335}  // namespace test
336}  // namespace net
337