1 /*
2 * Copyright (c) 2022 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "modules/pacing/prioritized_packet_queue.h"
12
13 #include <utility>
14
15 #include "api/units/time_delta.h"
16 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
17 #include "modules/rtp_rtcp/source/rtp_packet_to_send.h"
18 #include "rtc_base/checks.h"
19 #include "test/gmock.h"
20 #include "test/gtest.h"
21
22 namespace webrtc {
23 namespace {
24
25 constexpr uint32_t kDefaultSsrc = 123;
26 constexpr int kDefaultPayloadSize = 789;
27
CreatePacket(RtpPacketMediaType type,uint16_t sequence_number,uint32_t ssrc=kDefaultSsrc)28 std::unique_ptr<RtpPacketToSend> CreatePacket(RtpPacketMediaType type,
29 uint16_t sequence_number,
30 uint32_t ssrc = kDefaultSsrc) {
31 auto packet = std::make_unique<RtpPacketToSend>(/*extensions=*/nullptr);
32 packet->set_packet_type(type);
33 packet->SetSsrc(ssrc);
34 packet->SetSequenceNumber(sequence_number);
35 packet->SetPayloadSize(kDefaultPayloadSize);
36 return packet;
37 }
38
39 } // namespace
40
TEST(PrioritizedPacketQueue,ReturnsPacketsInPrioritizedOrder)41 TEST(PrioritizedPacketQueue, ReturnsPacketsInPrioritizedOrder) {
42 Timestamp now = Timestamp::Zero();
43 PrioritizedPacketQueue queue(now);
44
45 // Add packets in low to high packet order.
46 queue.Push(now, CreatePacket(RtpPacketMediaType::kPadding, /*seq=*/1));
47 queue.Push(now, CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/2));
48 queue.Push(now, CreatePacket(RtpPacketMediaType::kForwardErrorCorrection,
49 /*seq=*/3));
50 queue.Push(now, CreatePacket(RtpPacketMediaType::kRetransmission, /*seq=*/4));
51 queue.Push(now, CreatePacket(RtpPacketMediaType::kAudio, /*seq=*/5));
52
53 // Packets should be returned in high to low order.
54 EXPECT_EQ(queue.Pop()->SequenceNumber(), 5);
55 EXPECT_EQ(queue.Pop()->SequenceNumber(), 4);
56 // Video and FEC prioritized equally - but video was enqueued first.
57 EXPECT_EQ(queue.Pop()->SequenceNumber(), 2);
58 EXPECT_EQ(queue.Pop()->SequenceNumber(), 3);
59 EXPECT_EQ(queue.Pop()->SequenceNumber(), 1);
60 }
61
TEST(PrioritizedPacketQueue,ReturnsEqualPrioPacketsInRoundRobinOrder)62 TEST(PrioritizedPacketQueue, ReturnsEqualPrioPacketsInRoundRobinOrder) {
63 Timestamp now = Timestamp::Zero();
64 PrioritizedPacketQueue queue(now);
65
66 // Insert video packets (prioritized equally), simulating a simulcast-type use
67 // case.
68 queue.Push(now,
69 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/1, /*ssrc=*/100));
70
71 queue.Push(now,
72 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/2, /*ssrc=*/101));
73 queue.Push(now,
74 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/3, /*ssrc=*/101));
75
76 queue.Push(now,
77 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/4, /*ssrc=*/102));
78 queue.Push(now,
79 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/5, /*ssrc=*/102));
80 queue.Push(now,
81 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/6, /*ssrc=*/102));
82 queue.Push(now,
83 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/7, /*ssrc=*/102));
84
85 // First packet from each SSRC.
86 EXPECT_EQ(queue.Pop()->SequenceNumber(), 1);
87 EXPECT_EQ(queue.Pop()->SequenceNumber(), 2);
88 EXPECT_EQ(queue.Pop()->SequenceNumber(), 4);
89
90 // Second packets from streams that have packets left.
91 EXPECT_EQ(queue.Pop()->SequenceNumber(), 3);
92 EXPECT_EQ(queue.Pop()->SequenceNumber(), 5);
93
94 // Only packets from last stream remaining.
95 EXPECT_EQ(queue.Pop()->SequenceNumber(), 6);
96 EXPECT_EQ(queue.Pop()->SequenceNumber(), 7);
97 }
98
TEST(PrioritizedPacketQueue,ReportsSizeInPackets)99 TEST(PrioritizedPacketQueue, ReportsSizeInPackets) {
100 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
101 EXPECT_EQ(queue.SizeInPackets(), 0);
102
103 queue.Push(/*enqueue_time=*/Timestamp::Zero(),
104 CreatePacket(RtpPacketMediaType::kVideo,
105 /*seq_no=*/1));
106 EXPECT_EQ(queue.SizeInPackets(), 1);
107
108 queue.Pop();
109 EXPECT_EQ(queue.SizeInPackets(), 0);
110 }
111
TEST(PrioritizedPacketQueue,ReportsPayloadSize)112 TEST(PrioritizedPacketQueue, ReportsPayloadSize) {
113 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
114 EXPECT_EQ(queue.SizeInPayloadBytes(), DataSize::Zero());
115
116 queue.Push(/*enqueue_time=*/Timestamp::Zero(),
117 CreatePacket(RtpPacketMediaType::kVideo,
118 /*seq_no=*/1));
119 EXPECT_EQ(queue.SizeInPayloadBytes(), DataSize::Bytes(kDefaultPayloadSize));
120
121 queue.Pop();
122 EXPECT_EQ(queue.SizeInPayloadBytes(), DataSize::Zero());
123 }
124
TEST(PrioritizedPacketQueue,ReportsPaddingSize)125 TEST(PrioritizedPacketQueue, ReportsPaddingSize) {
126 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
127 EXPECT_EQ(queue.SizeInPayloadBytes(), DataSize::Zero());
128 static constexpr DataSize kPaddingSize = DataSize::Bytes(190);
129
130 auto packet = std::make_unique<RtpPacketToSend>(/*extensions=*/nullptr);
131 packet->set_packet_type(RtpPacketMediaType::kPadding);
132 packet->SetSsrc(kDefaultSsrc);
133 packet->SetSequenceNumber(/*seq=*/1);
134 packet->SetPadding(kPaddingSize.bytes());
135 queue.Push(/*enqueue_time=*/Timestamp::Zero(), std::move(packet));
136 EXPECT_EQ(queue.SizeInPayloadBytes(), kPaddingSize);
137
138 queue.Pop();
139 EXPECT_EQ(queue.SizeInPayloadBytes(), DataSize::Zero());
140 }
141
TEST(PrioritizedPacketQueue,ReportsOldestEnqueueTime)142 TEST(PrioritizedPacketQueue, ReportsOldestEnqueueTime) {
143 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
144 EXPECT_EQ(queue.OldestEnqueueTime(), Timestamp::MinusInfinity());
145
146 // Add three packets, with the middle packet having higher prio.
147 queue.Push(Timestamp::Millis(10),
148 CreatePacket(RtpPacketMediaType::kPadding, /*seq=*/1));
149 queue.Push(Timestamp::Millis(20),
150 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/2));
151 queue.Push(Timestamp::Millis(30),
152 CreatePacket(RtpPacketMediaType::kPadding, /*seq=*/3));
153 EXPECT_EQ(queue.OldestEnqueueTime(), Timestamp::Millis(10));
154
155 queue.Pop(); // Pop packet with enqueue time 20.
156 EXPECT_EQ(queue.OldestEnqueueTime(), Timestamp::Millis(10));
157
158 queue.Pop(); // Pop packet with enqueue time 10.
159 EXPECT_EQ(queue.OldestEnqueueTime(), Timestamp::Millis(30));
160
161 queue.Pop(); // Pop packet with enqueue time 30, queue empty again.
162 EXPECT_EQ(queue.OldestEnqueueTime(), Timestamp::MinusInfinity());
163 }
164
TEST(PrioritizedPacketQueue,ReportsAverageQueueTime)165 TEST(PrioritizedPacketQueue, ReportsAverageQueueTime) {
166 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
167 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Zero());
168
169 // Add three packets, with the middle packet having higher prio.
170 queue.Push(Timestamp::Millis(10),
171 CreatePacket(RtpPacketMediaType::kPadding, /*seq=*/1));
172 queue.Push(Timestamp::Millis(20),
173 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/2));
174 queue.Push(Timestamp::Millis(30),
175 CreatePacket(RtpPacketMediaType::kPadding, /*seq=*/3));
176
177 queue.UpdateAverageQueueTime(Timestamp::Millis(40));
178 // Packets have waited 30, 20, 10 ms -> average = 20ms.
179 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(20));
180
181 queue.Pop(); // Pop packet with enqueue time 20.
182 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(20));
183
184 queue.Pop(); // Pop packet with enqueue time 10.
185 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(10));
186
187 queue.Pop(); // Pop packet with enqueue time 30, queue empty again.
188 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Zero());
189 }
190
TEST(PrioritizedPacketQueue,SubtractsPusedTimeFromAverageQueueTime)191 TEST(PrioritizedPacketQueue, SubtractsPusedTimeFromAverageQueueTime) {
192 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
193 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Zero());
194
195 // Add a packet and then enable paused state.
196 queue.Push(Timestamp::Millis(100),
197 CreatePacket(RtpPacketMediaType::kPadding, /*seq=*/1));
198 queue.SetPauseState(true, Timestamp::Millis(600));
199 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(500));
200
201 // Enqueue a packet 500ms into the paused state. Queue time of
202 // original packet is still seen as 500ms and new one has 0ms giving
203 // an average of 250ms.
204 queue.Push(Timestamp::Millis(1100),
205 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/2));
206 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(250));
207
208 // Unpause some time later, queue time still unchanged.
209 queue.SetPauseState(false, Timestamp::Millis(1600));
210 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(250));
211
212 // Update queue time 500ms after pause state ended.
213 queue.UpdateAverageQueueTime(Timestamp::Millis(2100));
214 EXPECT_EQ(queue.AverageQueueTime(), TimeDelta::Millis(750));
215 }
216
TEST(PrioritizedPacketQueue,ReportsLeadingPacketEnqueueTime)217 TEST(PrioritizedPacketQueue, ReportsLeadingPacketEnqueueTime) {
218 PrioritizedPacketQueue queue(/*creation_time=*/Timestamp::Zero());
219 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kAudio),
220 Timestamp::MinusInfinity());
221 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kVideo),
222 Timestamp::MinusInfinity());
223
224 queue.Push(Timestamp::Millis(10),
225 CreatePacket(RtpPacketMediaType::kVideo, /*seq=*/1));
226 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kAudio),
227 Timestamp::MinusInfinity());
228 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kVideo),
229 Timestamp::Millis(10));
230
231 queue.Push(Timestamp::Millis(20),
232 CreatePacket(RtpPacketMediaType::kAudio, /*seq=*/2));
233
234 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kAudio),
235 Timestamp::Millis(20));
236 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kVideo),
237 Timestamp::Millis(10));
238
239 queue.Pop(); // Pop audio packet.
240 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kAudio),
241 Timestamp::MinusInfinity());
242 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kVideo),
243 Timestamp::Millis(10));
244
245 queue.Pop(); // Pop video packet.
246 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kAudio),
247 Timestamp::MinusInfinity());
248 EXPECT_EQ(queue.LeadingPacketEnqueueTime(RtpPacketMediaType::kVideo),
249 Timestamp::MinusInfinity());
250 }
251
TEST(PrioritizedPacketQueue,PushAndPopUpdatesSizeInPacketsPerRtpPacketMediaType)252 TEST(PrioritizedPacketQueue,
253 PushAndPopUpdatesSizeInPacketsPerRtpPacketMediaType) {
254 Timestamp now = Timestamp::Zero();
255 PrioritizedPacketQueue queue(now);
256
257 // Initially all sizes are zero.
258 for (size_t i = 0; i < kNumMediaTypes; ++i) {
259 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[i], 0);
260 }
261
262 // Push packets.
263 queue.Push(now, CreatePacket(RtpPacketMediaType::kAudio, 1));
264 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[static_cast<size_t>(
265 RtpPacketMediaType::kAudio)],
266 1);
267
268 queue.Push(now, CreatePacket(RtpPacketMediaType::kVideo, 2));
269 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[static_cast<size_t>(
270 RtpPacketMediaType::kVideo)],
271 1);
272
273 queue.Push(now, CreatePacket(RtpPacketMediaType::kRetransmission, 3));
274 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[static_cast<size_t>(
275 RtpPacketMediaType::kRetransmission)],
276 1);
277
278 queue.Push(now, CreatePacket(RtpPacketMediaType::kForwardErrorCorrection, 4));
279 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[static_cast<size_t>(
280 RtpPacketMediaType::kForwardErrorCorrection)],
281 1);
282
283 queue.Push(now, CreatePacket(RtpPacketMediaType::kPadding, 5));
284 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[static_cast<size_t>(
285 RtpPacketMediaType::kPadding)],
286 1);
287
288 // Now all sizes are 1.
289 for (size_t i = 0; i < kNumMediaTypes; ++i) {
290 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[i], 1);
291 }
292
293 // Popping happens in a priority order based on media type. This test does not
294 // assert what this order is, only that the counter for the popped packet's
295 // media type is decremented.
296 for (size_t i = 0; i < kNumMediaTypes; ++i) {
297 auto popped_packet = queue.Pop();
298 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[static_cast<size_t>(
299 popped_packet->packet_type().value())],
300 0);
301 }
302
303 // We've popped all packets, so all sizes are zero.
304 for (size_t i = 0; i < kNumMediaTypes; ++i) {
305 EXPECT_EQ(queue.SizeInPacketsPerRtpPacketMediaType()[i], 0);
306 }
307 }
308
309 } // namespace webrtc
310