1 /* 2 * Copyright (c) 2012 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 #include "webrtc/modules/remote_bitrate_estimator/remote_bitrate_estimator_unittest_helper.h" 11 12 #include <algorithm> 13 #include <utility> 14 15 namespace webrtc { 16 17 enum { kMtu = 1200 }; 18 19 namespace testing { 20 21 void TestBitrateObserver::OnReceiveBitrateChanged( 22 const std::vector<unsigned int>& ssrcs, 23 unsigned int bitrate) { 24 latest_bitrate_ = bitrate; 25 updated_ = true; 26 } 27 28 RtpStream::RtpStream(int fps, 29 int bitrate_bps, 30 unsigned int ssrc, 31 unsigned int frequency, 32 uint32_t timestamp_offset, 33 int64_t rtcp_receive_time) 34 : fps_(fps), 35 bitrate_bps_(bitrate_bps), 36 ssrc_(ssrc), 37 frequency_(frequency), 38 next_rtp_time_(0), 39 next_rtcp_time_(rtcp_receive_time), 40 rtp_timestamp_offset_(timestamp_offset), 41 kNtpFracPerMs(4.294967296E6) { 42 assert(fps_ > 0); 43 } 44 45 void RtpStream::set_rtp_timestamp_offset(uint32_t offset) { 46 rtp_timestamp_offset_ = offset; 47 } 48 49 // Generates a new frame for this stream. If called too soon after the 50 // previous frame, no frame will be generated. The frame is split into 51 // packets. 52 int64_t RtpStream::GenerateFrame(int64_t time_now_us, PacketList* packets) { 53 if (time_now_us < next_rtp_time_) { 54 return next_rtp_time_; 55 } 56 assert(packets != NULL); 57 int bits_per_frame = (bitrate_bps_ + fps_ / 2) / fps_; 58 int n_packets = std::max((bits_per_frame + 4 * kMtu) / (8 * kMtu), 1); 59 int packet_size = (bits_per_frame + 4 * n_packets) / (8 * n_packets); 60 assert(n_packets >= 0); 61 for (int i = 0; i < n_packets; ++i) { 62 RtpPacket* packet = new RtpPacket; 63 packet->send_time = time_now_us + kSendSideOffsetUs; 64 packet->size = packet_size; 65 packet->rtp_timestamp = rtp_timestamp_offset_ + static_cast<uint32_t>( 66 ((frequency_ / 1000) * packet->send_time + 500) / 1000); 67 packet->ssrc = ssrc_; 68 packets->push_back(packet); 69 } 70 next_rtp_time_ = time_now_us + (1000000 + fps_ / 2) / fps_; 71 return next_rtp_time_; 72 } 73 74 // The send-side time when the next frame can be generated. 75 double RtpStream::next_rtp_time() const { 76 return next_rtp_time_; 77 } 78 79 // Generates an RTCP packet. 80 RtpStream::RtcpPacket* RtpStream::Rtcp(int64_t time_now_us) { 81 if (time_now_us < next_rtcp_time_) { 82 return NULL; 83 } 84 RtcpPacket* rtcp = new RtcpPacket; 85 int64_t send_time_us = time_now_us + kSendSideOffsetUs; 86 rtcp->timestamp = rtp_timestamp_offset_ + static_cast<uint32_t>( 87 ((frequency_ / 1000) * send_time_us + 500) / 1000); 88 rtcp->ntp_secs = send_time_us / 1000000; 89 rtcp->ntp_frac = static_cast<int64_t>((send_time_us % 1000000) * 90 kNtpFracPerMs); 91 rtcp->ssrc = ssrc_; 92 next_rtcp_time_ = time_now_us + kRtcpIntervalUs; 93 return rtcp; 94 } 95 96 void RtpStream::set_bitrate_bps(int bitrate_bps) { 97 ASSERT_GE(bitrate_bps, 0); 98 bitrate_bps_ = bitrate_bps; 99 } 100 101 int RtpStream::bitrate_bps() const { 102 return bitrate_bps_; 103 } 104 105 unsigned int RtpStream::ssrc() const { 106 return ssrc_; 107 } 108 109 bool RtpStream::Compare(const std::pair<unsigned int, RtpStream*>& left, 110 const std::pair<unsigned int, RtpStream*>& right) { 111 return left.second->next_rtp_time_ < right.second->next_rtp_time_; 112 } 113 114 StreamGenerator::StreamGenerator(int capacity, double time_now) 115 : capacity_(capacity), 116 prev_arrival_time_us_(time_now) {} 117 118 StreamGenerator::~StreamGenerator() { 119 for (StreamMap::iterator it = streams_.begin(); it != streams_.end(); 120 ++it) { 121 delete it->second; 122 } 123 streams_.clear(); 124 } 125 126 // Add a new stream. 127 void StreamGenerator::AddStream(RtpStream* stream) { 128 streams_[stream->ssrc()] = stream; 129 } 130 131 // Set the link capacity. 132 void StreamGenerator::set_capacity_bps(int capacity_bps) { 133 ASSERT_GT(capacity_bps, 0); 134 capacity_ = capacity_bps; 135 } 136 137 // Divides |bitrate_bps| among all streams. The allocated bitrate per stream 138 // is decided by the current allocation ratios. 139 void StreamGenerator::SetBitrateBps(int bitrate_bps) { 140 ASSERT_GE(streams_.size(), 0u); 141 int total_bitrate_before = 0; 142 for (StreamMap::iterator it = streams_.begin(); it != streams_.end(); ++it) { 143 total_bitrate_before += it->second->bitrate_bps(); 144 } 145 int64_t bitrate_before = 0; 146 int total_bitrate_after = 0; 147 for (StreamMap::iterator it = streams_.begin(); it != streams_.end(); ++it) { 148 bitrate_before += it->second->bitrate_bps(); 149 int64_t bitrate_after = (bitrate_before * bitrate_bps + 150 total_bitrate_before / 2) / total_bitrate_before; 151 it->second->set_bitrate_bps(bitrate_after - total_bitrate_after); 152 total_bitrate_after += it->second->bitrate_bps(); 153 } 154 ASSERT_EQ(bitrate_before, total_bitrate_before); 155 EXPECT_EQ(total_bitrate_after, bitrate_bps); 156 } 157 158 // Set the RTP timestamp offset for the stream identified by |ssrc|. 159 void StreamGenerator::set_rtp_timestamp_offset(unsigned int ssrc, 160 uint32_t offset) { 161 streams_[ssrc]->set_rtp_timestamp_offset(offset); 162 } 163 164 // TODO(holmer): Break out the channel simulation part from this class to make 165 // it possible to simulate different types of channels. 166 int64_t StreamGenerator::GenerateFrame(RtpStream::PacketList* packets, 167 int64_t time_now_us) { 168 assert(packets != NULL); 169 assert(packets->empty()); 170 assert(capacity_ > 0); 171 StreamMap::iterator it = std::min_element(streams_.begin(), streams_.end(), 172 RtpStream::Compare); 173 (*it).second->GenerateFrame(time_now_us, packets); 174 int i = 0; 175 for (RtpStream::PacketList::iterator packet_it = packets->begin(); 176 packet_it != packets->end(); ++packet_it) { 177 int capacity_bpus = capacity_ / 1000; 178 int64_t required_network_time_us = 179 (8 * 1000 * (*packet_it)->size + capacity_bpus / 2) / capacity_bpus; 180 prev_arrival_time_us_ = std::max(time_now_us + required_network_time_us, 181 prev_arrival_time_us_ + required_network_time_us); 182 (*packet_it)->arrival_time = prev_arrival_time_us_; 183 ++i; 184 } 185 it = std::min_element(streams_.begin(), streams_.end(), RtpStream::Compare); 186 return (*it).second->next_rtp_time(); 187 } 188 } // namespace testing 189 190 RemoteBitrateEstimatorTest::RemoteBitrateEstimatorTest() 191 : clock_(0), 192 bitrate_observer_(new testing::TestBitrateObserver), 193 stream_generator_(new testing::StreamGenerator( 194 1e6, // Capacity. 195 clock_.TimeInMicroseconds())) {} 196 197 RemoteBitrateEstimatorTest::~RemoteBitrateEstimatorTest() {} 198 199 void RemoteBitrateEstimatorTest::AddDefaultStream() { 200 stream_generator_->AddStream(new testing::RtpStream( 201 30, // Frames per second. 202 3e5, // Bitrate. 203 1, // SSRC. 204 90000, // RTP frequency. 205 0xFFFFF000, // Timestamp offset. 206 0)); // RTCP receive time. 207 } 208 209 uint32_t RemoteBitrateEstimatorTest::AbsSendTime(int64_t t, int64_t denom) { 210 return (((t << 18) + (denom >> 1)) / denom) & 0x00fffffful; 211 } 212 213 uint32_t RemoteBitrateEstimatorTest::AddAbsSendTime(uint32_t t1, uint32_t t2) { 214 return (t1 + t2) & 0x00fffffful; 215 } 216 217 const unsigned int RemoteBitrateEstimatorTest::kDefaultSsrc = 1; 218 219 void RemoteBitrateEstimatorTest::IncomingPacket(uint32_t ssrc, 220 uint32_t payload_size, 221 int64_t arrival_time, 222 uint32_t rtp_timestamp, 223 uint32_t absolute_send_time) { 224 RTPHeader header; 225 memset(&header, 0, sizeof(header)); 226 header.ssrc = ssrc; 227 header.timestamp = rtp_timestamp; 228 header.extension.absoluteSendTime = absolute_send_time; 229 bitrate_estimator_->IncomingPacket(arrival_time + kArrivalTimeClockOffsetMs, 230 payload_size, header); 231 } 232 233 // Generates a frame of packets belonging to a stream at a given bitrate and 234 // with a given ssrc. The stream is pushed through a very simple simulated 235 // network, and is then given to the receive-side bandwidth estimator. 236 // Returns true if an over-use was seen, false otherwise. 237 // The StreamGenerator::updated() should be used to check for any changes in 238 // target bitrate after the call to this function. 239 bool RemoteBitrateEstimatorTest::GenerateAndProcessFrame(unsigned int ssrc, 240 unsigned int bitrate_bps) { 241 stream_generator_->SetBitrateBps(bitrate_bps); 242 testing::RtpStream::PacketList packets; 243 int64_t next_time_us = stream_generator_->GenerateFrame( 244 &packets, clock_.TimeInMicroseconds()); 245 bool overuse = false; 246 while (!packets.empty()) { 247 testing::RtpStream::RtpPacket* packet = packets.front(); 248 bitrate_observer_->Reset(); 249 // The simulated clock should match the time of packet->arrival_time 250 // since both are used in IncomingPacket(). 251 clock_.AdvanceTimeMicroseconds(packet->arrival_time - 252 clock_.TimeInMicroseconds()); 253 IncomingPacket(packet->ssrc, 254 packet->size, 255 (packet->arrival_time + 500) / 1000, 256 packet->rtp_timestamp, 257 AbsSendTime(packet->send_time, 1000000)); 258 if (bitrate_observer_->updated()) { 259 // Verify that new estimates only are triggered by an overuse and a 260 // rate decrease. 261 overuse = true; 262 EXPECT_LE(bitrate_observer_->latest_bitrate(), bitrate_bps); 263 } 264 delete packet; 265 packets.pop_front(); 266 } 267 bitrate_estimator_->Process(); 268 clock_.AdvanceTimeMicroseconds(next_time_us - clock_.TimeInMicroseconds()); 269 return overuse; 270 } 271 272 // Run the bandwidth estimator with a stream of |number_of_frames| frames, or 273 // until it reaches |target_bitrate|. 274 // Can for instance be used to run the estimator for some time to get it 275 // into a steady state. 276 unsigned int RemoteBitrateEstimatorTest::SteadyStateRun( 277 unsigned int ssrc, 278 int max_number_of_frames, 279 unsigned int start_bitrate, 280 unsigned int min_bitrate, 281 unsigned int max_bitrate, 282 unsigned int target_bitrate) { 283 unsigned int bitrate_bps = start_bitrate; 284 bool bitrate_update_seen = false; 285 // Produce |number_of_frames| frames and give them to the estimator. 286 for (int i = 0; i < max_number_of_frames; ++i) { 287 bool overuse = GenerateAndProcessFrame(ssrc, bitrate_bps); 288 if (overuse) { 289 EXPECT_LT(bitrate_observer_->latest_bitrate(), max_bitrate); 290 EXPECT_GT(bitrate_observer_->latest_bitrate(), min_bitrate); 291 bitrate_bps = bitrate_observer_->latest_bitrate(); 292 bitrate_update_seen = true; 293 } else if (bitrate_observer_->updated()) { 294 bitrate_bps = bitrate_observer_->latest_bitrate(); 295 bitrate_observer_->Reset(); 296 } 297 if (bitrate_update_seen && bitrate_bps > target_bitrate) { 298 break; 299 } 300 } 301 EXPECT_TRUE(bitrate_update_seen); 302 return bitrate_bps; 303 } 304 305 void RemoteBitrateEstimatorTest::InitialBehaviorTestHelper( 306 unsigned int expected_converge_bitrate) { 307 const int kFramerate = 50; // 50 fps to avoid rounding errors. 308 const int kFrameIntervalMs = 1000 / kFramerate; 309 const uint32_t kFrameIntervalAbsSendTime = AbsSendTime(1, kFramerate); 310 unsigned int bitrate_bps = 0; 311 uint32_t timestamp = 0; 312 uint32_t absolute_send_time = 0; 313 std::vector<unsigned int> ssrcs; 314 EXPECT_FALSE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps)); 315 EXPECT_EQ(0u, ssrcs.size()); 316 clock_.AdvanceTimeMilliseconds(1000); 317 bitrate_estimator_->Process(); 318 EXPECT_FALSE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps)); 319 EXPECT_FALSE(bitrate_observer_->updated()); 320 bitrate_observer_->Reset(); 321 clock_.AdvanceTimeMilliseconds(1000); 322 // Inserting a packet. Still no valid estimate. We need to wait 1 second. 323 IncomingPacket(kDefaultSsrc, kMtu, clock_.TimeInMilliseconds(), timestamp, 324 absolute_send_time); 325 bitrate_estimator_->Process(); 326 EXPECT_FALSE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps)); 327 EXPECT_EQ(0u, ssrcs.size()); 328 EXPECT_FALSE(bitrate_observer_->updated()); 329 bitrate_observer_->Reset(); 330 // Inserting packets for one second to get a valid estimate. 331 for (int i = 0; i < kFramerate; ++i) { 332 IncomingPacket(kDefaultSsrc, kMtu, clock_.TimeInMilliseconds(), timestamp, 333 absolute_send_time); 334 clock_.AdvanceTimeMilliseconds(1000 / kFramerate); 335 timestamp += 90 * kFrameIntervalMs; 336 absolute_send_time = AddAbsSendTime(absolute_send_time, 337 kFrameIntervalAbsSendTime); 338 } 339 bitrate_estimator_->Process(); 340 EXPECT_TRUE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps)); 341 ASSERT_EQ(1u, ssrcs.size()); 342 EXPECT_EQ(kDefaultSsrc, ssrcs.front()); 343 EXPECT_EQ(expected_converge_bitrate, bitrate_bps); 344 EXPECT_TRUE(bitrate_observer_->updated()); 345 bitrate_observer_->Reset(); 346 EXPECT_EQ(bitrate_observer_->latest_bitrate(), bitrate_bps); 347 bitrate_estimator_->RemoveStream(kDefaultSsrc); 348 EXPECT_TRUE(bitrate_estimator_->LatestEstimate(&ssrcs, &bitrate_bps)); 349 ASSERT_EQ(0u, ssrcs.size()); 350 EXPECT_EQ(0u, bitrate_bps); 351 } 352 353 void RemoteBitrateEstimatorTest::RateIncreaseReorderingTestHelper( 354 uint32_t expected_bitrate_bps) { 355 const int kFramerate = 50; // 50 fps to avoid rounding errors. 356 const int kFrameIntervalMs = 1000 / kFramerate; 357 const uint32_t kFrameIntervalAbsSendTime = AbsSendTime(1, kFramerate); 358 uint32_t timestamp = 0; 359 uint32_t absolute_send_time = 0; 360 IncomingPacket(kDefaultSsrc, 1000, clock_.TimeInMilliseconds(), timestamp, 361 absolute_send_time); 362 bitrate_estimator_->Process(); 363 EXPECT_FALSE(bitrate_observer_->updated()); // No valid estimate. 364 // Inserting packets for one second to get a valid estimate. 365 for (int i = 0; i < kFramerate; ++i) { 366 IncomingPacket(kDefaultSsrc, kMtu, clock_.TimeInMilliseconds(), timestamp, 367 absolute_send_time); 368 clock_.AdvanceTimeMilliseconds(kFrameIntervalMs); 369 timestamp += 90 * kFrameIntervalMs; 370 absolute_send_time = AddAbsSendTime(absolute_send_time, 371 kFrameIntervalAbsSendTime); 372 } 373 bitrate_estimator_->Process(); 374 EXPECT_TRUE(bitrate_observer_->updated()); 375 EXPECT_EQ(expected_bitrate_bps, bitrate_observer_->latest_bitrate()); 376 for (int i = 0; i < 10; ++i) { 377 clock_.AdvanceTimeMilliseconds(2 * kFrameIntervalMs); 378 timestamp += 2 * 90 * kFrameIntervalMs; 379 absolute_send_time = AddAbsSendTime(absolute_send_time, 380 2 * kFrameIntervalAbsSendTime); 381 IncomingPacket(kDefaultSsrc, 1000, clock_.TimeInMilliseconds(), timestamp, 382 absolute_send_time); 383 IncomingPacket(kDefaultSsrc, 1000, clock_.TimeInMilliseconds(), 384 timestamp - 90 * kFrameIntervalMs, 385 AddAbsSendTime(absolute_send_time, 386 -int(kFrameIntervalAbsSendTime))); 387 } 388 bitrate_estimator_->Process(); 389 EXPECT_TRUE(bitrate_observer_->updated()); 390 EXPECT_EQ(expected_bitrate_bps, bitrate_observer_->latest_bitrate()); 391 } 392 393 // Make sure we initially increase the bitrate as expected. 394 void RemoteBitrateEstimatorTest::RateIncreaseRtpTimestampsTestHelper() { 395 // This threshold corresponds approximately to increasing linearly with 396 // bitrate(i) = 1.04 * bitrate(i-1) + 1000 397 // until bitrate(i) > 500000, with bitrate(1) ~= 30000. 398 const int kExpectedIterations = 1621; 399 unsigned int bitrate_bps = 30000; 400 int iterations = 0; 401 AddDefaultStream(); 402 // Feed the estimator with a stream of packets and verify that it reaches 403 // 500 kbps at the expected time. 404 while (bitrate_bps < 5e5) { 405 bool overuse = GenerateAndProcessFrame(kDefaultSsrc, bitrate_bps); 406 if (overuse) { 407 EXPECT_GT(bitrate_observer_->latest_bitrate(), bitrate_bps); 408 bitrate_bps = bitrate_observer_->latest_bitrate(); 409 bitrate_observer_->Reset(); 410 } else if (bitrate_observer_->updated()) { 411 bitrate_bps = bitrate_observer_->latest_bitrate(); 412 bitrate_observer_->Reset(); 413 } 414 ++iterations; 415 ASSERT_LE(iterations, kExpectedIterations); 416 } 417 ASSERT_EQ(kExpectedIterations, iterations); 418 } 419 420 void RemoteBitrateEstimatorTest::CapacityDropTestHelper( 421 int number_of_streams, 422 bool wrap_time_stamp, 423 unsigned int expected_converge_bitrate, 424 unsigned int expected_bitrate_drop_delta) { 425 const int kFramerate = 30; 426 const int kStartBitrate = 900e3; 427 const int kMinExpectedBitrate = 800e3; 428 const int kMaxExpectedBitrate = 1100e3; 429 const unsigned int kInitialCapacityBps = 1000e3; 430 const unsigned int kReducedCapacityBps = 500e3; 431 432 int steady_state_time = 0; 433 int expected_overuse_start_time = 0; 434 if (number_of_streams <= 1) { 435 steady_state_time = 10; 436 expected_overuse_start_time = 10000; 437 AddDefaultStream(); 438 } else { 439 steady_state_time = 8 * number_of_streams; 440 expected_overuse_start_time = 8000; 441 int bitrate_sum = 0; 442 int kBitrateDenom = number_of_streams * (number_of_streams - 1); 443 for (int i = 0; i < number_of_streams; i++) { 444 // First stream gets half available bitrate, while the rest share the 445 // remaining half i.e.: 1/2 = Sum[n/(N*(N-1))] for n=1..N-1 (rounded up) 446 int bitrate = kStartBitrate / 2; 447 if (i > 0) { 448 bitrate = (kStartBitrate * i + kBitrateDenom / 2) / kBitrateDenom; 449 } 450 stream_generator_->AddStream(new testing::RtpStream( 451 kFramerate, // Frames per second. 452 bitrate, // Bitrate. 453 kDefaultSsrc + i, // SSRC. 454 90000, // RTP frequency. 455 0xFFFFF000 ^ (~0 << (32 - i)), // Timestamp offset. 456 0)); // RTCP receive time. 457 bitrate_sum += bitrate; 458 } 459 ASSERT_EQ(bitrate_sum, kStartBitrate); 460 } 461 if (wrap_time_stamp) { 462 stream_generator_->set_rtp_timestamp_offset(kDefaultSsrc, 463 std::numeric_limits<uint32_t>::max() - steady_state_time * 90000); 464 } 465 466 // Run in steady state to make the estimator converge. 467 stream_generator_->set_capacity_bps(kInitialCapacityBps); 468 unsigned int bitrate_bps = SteadyStateRun(kDefaultSsrc, 469 steady_state_time * kFramerate, 470 kStartBitrate, 471 kMinExpectedBitrate, 472 kMaxExpectedBitrate, 473 kInitialCapacityBps); 474 EXPECT_EQ(expected_converge_bitrate, bitrate_bps); 475 bitrate_observer_->Reset(); 476 477 // Reduce the capacity and verify the decrease time. 478 stream_generator_->set_capacity_bps(kReducedCapacityBps); 479 int64_t overuse_start_time = clock_.TimeInMilliseconds(); 480 EXPECT_EQ(expected_overuse_start_time, overuse_start_time); 481 int64_t bitrate_drop_time = -1; 482 for (int i = 0; i < 100 * number_of_streams; ++i) { 483 GenerateAndProcessFrame(kDefaultSsrc, bitrate_bps); 484 // Check for either increase or decrease. 485 if (bitrate_observer_->updated()) { 486 if (bitrate_drop_time == -1 && 487 bitrate_observer_->latest_bitrate() <= kReducedCapacityBps) { 488 bitrate_drop_time = clock_.TimeInMilliseconds(); 489 } 490 bitrate_bps = bitrate_observer_->latest_bitrate(); 491 bitrate_observer_->Reset(); 492 } 493 } 494 495 EXPECT_EQ(expected_bitrate_drop_delta, 496 bitrate_drop_time - overuse_start_time); 497 498 // Remove stream one by one. 499 unsigned int latest_bps = 0; 500 std::vector<unsigned int> ssrcs; 501 for (int i = 0; i < number_of_streams; i++) { 502 EXPECT_TRUE(bitrate_estimator_->LatestEstimate(&ssrcs, &latest_bps)); 503 EXPECT_EQ(number_of_streams - i, static_cast<int>(ssrcs.size())); 504 EXPECT_EQ(bitrate_bps, latest_bps); 505 for (int j = i; j < number_of_streams; j++) { 506 EXPECT_EQ(kDefaultSsrc + j, ssrcs[j - i]); 507 } 508 bitrate_estimator_->RemoveStream(kDefaultSsrc + i); 509 } 510 EXPECT_TRUE(bitrate_estimator_->LatestEstimate(&ssrcs, &latest_bps)); 511 EXPECT_EQ(0u, ssrcs.size()); 512 EXPECT_EQ(0u, latest_bps); 513 } 514 } // namespace webrtc 515