diff --git a/modules/rtp_rtcp/BUILD.gn b/modules/rtp_rtcp/BUILD.gn
index 0424a7a..6c2e09e 100644
--- a/modules/rtp_rtcp/BUILD.gn
+++ b/modules/rtp_rtcp/BUILD.gn
@@ -173,6 +173,8 @@
     "source/rtp_sender_audio.h",
     "source/rtp_sender_video.cc",
     "source/rtp_sender_video.h",
+    "source/rtp_sequence_number_map.cc",
+    "source/rtp_sequence_number_map.h",
     "source/rtp_utility.cc",
     "source/rtp_utility.h",
     "source/time_util.cc",
@@ -423,6 +425,7 @@
       "source/rtp_sender_audio_unittest.cc",
       "source/rtp_sender_unittest.cc",
       "source/rtp_sender_video_unittest.cc",
+      "source/rtp_sequence_number_map_unittest.cc",
       "source/rtp_utility_unittest.cc",
       "source/time_util_unittest.cc",
       "source/ulpfec_generator_unittest.cc",
@@ -456,6 +459,7 @@
       "../../rtc_base:rate_limiter",
       "../../rtc_base:rtc_base_approved",
       "../../rtc_base:rtc_base_tests_utils",
+      "../../rtc_base:rtc_numerics",
       "../../rtc_base:task_queue_for_test",
       "../../system_wrappers",
       "../../test:field_trial",
diff --git a/modules/rtp_rtcp/source/rtp_sequence_number_map.cc b/modules/rtp_rtcp/source/rtp_sequence_number_map.cc
new file mode 100644
index 0000000..95eafce
--- /dev/null
+++ b/modules/rtp_rtcp/source/rtp_sequence_number_map.cc
@@ -0,0 +1,114 @@
+/*
+ *  Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/rtp_rtcp/source/rtp_sequence_number_map.h"
+
+#include <algorithm>
+#include <iterator>
+
+#include "absl/algorithm/container.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/logging.h"
+#include "rtc_base/numerics/sequence_number_util.h"
+
+namespace webrtc {
+
+RtpSequenceNumberMap::RtpSequenceNumberMap(size_t max_entries)
+    : max_entries_(max_entries) {
+  RTC_DCHECK_GT(max_entries_, 4);  // See code paring down to |max_entries_|.
+  RTC_DCHECK_LE(max_entries_, 1 << 15);
+}
+
+RtpSequenceNumberMap::~RtpSequenceNumberMap() = default;
+
+void RtpSequenceNumberMap::Insert(uint16_t sequence_number, Info info) {
+  RTC_DCHECK(associations_.size() < 2 ||
+             AheadOf(associations_.back().sequence_number,
+                     associations_.front().sequence_number));
+
+  if (associations_.empty()) {
+    associations_.emplace_back(sequence_number, info);
+    return;
+  }
+
+  if (AheadOrAt(sequence_number, associations_.front().sequence_number) &&
+      AheadOrAt(associations_.back().sequence_number, sequence_number)) {
+    // The sequence number has wrapped around and is within the range
+    // currently held by |associations_| - we should invalidate all entries.
+    RTC_LOG(LS_WARNING) << "Sequence number wrapped-around unexpectedly.";
+    associations_.clear();
+    associations_.emplace_back(sequence_number, info);
+    return;
+  }
+
+  std::deque<Association>::iterator erase_to = associations_.begin();
+
+  RTC_DCHECK_LE(associations_.size(), max_entries_);
+  if (associations_.size() == max_entries_) {
+    // Pare down the container so that inserting some additional elements
+    // would not exceed the maximum size.
+    const size_t new_size = 3 * max_entries_ / 4;
+    erase_to = std::next(erase_to, max_entries_ - new_size);
+  }
+
+  // It is guaranteed that |associations_| can be split into two partitions,
+  // either partition possibly empty, such that:
+  // * In the first partition, all elements are AheadOf the new element.
+  //   This is the partition of the obsolete elements.
+  // * In the second partition, the new element is AheadOf all the elements.
+  //   The elements of this partition may stay.
+  auto cmp = [](const Association& a, uint16_t sequence_number) {
+    return AheadOf(a.sequence_number, sequence_number);
+  };
+  RTC_DCHECK(erase_to != associations_.end());
+  erase_to =
+      std::lower_bound(erase_to, associations_.end(), sequence_number, cmp);
+  associations_.erase(associations_.begin(), erase_to);
+
+  associations_.emplace_back(sequence_number, info);
+
+  RTC_DCHECK(associations_.size() == 1 ||
+             AheadOf(associations_.back().sequence_number,
+                     associations_.front().sequence_number));
+}
+
+absl::optional<RtpSequenceNumberMap::Info> RtpSequenceNumberMap::Get(
+    uint16_t sequence_number) const {
+  // To make the binary search easier to understand, we use the fact that
+  // adding a constant offset to all elements, as well as to the searched
+  // element, does not change the relative ordering. This way, we can find
+  // an offset that would make all of the elements strictly ascending according
+  // to normal integer comparison.
+  // Finding such an offset is easy - the offset that would map the oldest
+  // element to 0 would serve this purpose.
+
+  if (associations_.empty()) {
+    return absl::nullopt;
+  }
+
+  const uint16_t offset =
+      static_cast<uint16_t>(0) - associations_.front().sequence_number;
+
+  auto cmp = [offset](const Association& a, uint16_t sequence_number) {
+    return static_cast<uint16_t>(a.sequence_number + offset) <
+           static_cast<uint16_t>(sequence_number + offset);
+  };
+  const auto elem = absl::c_lower_bound(associations_, sequence_number, cmp);
+
+  return elem != associations_.end() && elem->sequence_number == sequence_number
+             ? absl::optional<Info>(elem->info)
+             : absl::nullopt;
+}
+
+size_t RtpSequenceNumberMap::AssociationCountForTesting() const {
+  return associations_.size();
+}
+
+}  // namespace webrtc
diff --git a/modules/rtp_rtcp/source/rtp_sequence_number_map.h b/modules/rtp_rtcp/source/rtp_sequence_number_map.h
new file mode 100644
index 0000000..1f6a304
--- /dev/null
+++ b/modules/rtp_rtcp/source/rtp_sequence_number_map.h
@@ -0,0 +1,83 @@
+/*
+ *  Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
+#define MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
+
+#include <cstddef>
+#include <cstdint>
+
+#include <deque>
+
+#include "absl/types/optional.h"
+
+namespace webrtc {
+
+// Records the association of RTP sequence numbers to timestamps and to whether
+// the packet was first and/or last in the frame.
+//
+// 1. Limits number of entries. Whenever |max_entries| is about to be exceeded,
+//    the size is reduced by approximately 25%.
+// 2. RTP sequence numbers wrap around relatively infrequently.
+//    This class therefore only remembers at most the last 2^15 RTP packets,
+//    so that the newest packet's sequence number is still AheadOf the oldest
+//    packet's sequence number.
+// 3. Media frames are sometimes split into several RTP packets.
+//    In such a case, Insert() is expected to be called once for each packet.
+//    The timestamp is not expected to change between those calls.
+class RtpSequenceNumberMap final {
+ public:
+  struct Info final {
+    Info(uint32_t timestamp, bool is_first, bool is_last)
+        : timestamp(timestamp), is_first(is_first), is_last(is_last) {}
+
+    friend bool operator==(const Info& lhs, const Info& rhs) {
+      return lhs.timestamp == rhs.timestamp && lhs.is_first == rhs.is_first &&
+             lhs.is_last == rhs.is_last;
+    }
+
+    uint32_t timestamp;
+    bool is_first;
+    bool is_last;
+  };
+
+  explicit RtpSequenceNumberMap(size_t max_entries);
+  RtpSequenceNumberMap(const RtpSequenceNumberMap& other) = delete;
+  RtpSequenceNumberMap& operator=(const RtpSequenceNumberMap& other) = delete;
+  ~RtpSequenceNumberMap();
+
+  void Insert(uint16_t sequence_number, Info info);
+
+  absl::optional<Info> Get(uint16_t sequence_number) const;
+
+  size_t AssociationCountForTesting() const;
+
+ private:
+  struct Association {
+    explicit Association(uint16_t sequence_number)
+        : Association(sequence_number, Info(0, false, false)) {}
+
+    Association(uint16_t sequence_number, Info info)
+        : sequence_number(sequence_number), info(info) {}
+
+    uint16_t sequence_number;
+    Info info;
+  };
+
+  const size_t max_entries_;
+
+  // The non-transitivity of AheadOf() would be problematic with a map,
+  // so we use a deque instead.
+  std::deque<Association> associations_;
+};
+
+}  // namespace webrtc
+
+#endif  // MODULES_RTP_RTCP_SOURCE_RTP_SEQUENCE_NUMBER_MAP_H_
diff --git a/modules/rtp_rtcp/source/rtp_sequence_number_map_unittest.cc b/modules/rtp_rtcp/source/rtp_sequence_number_map_unittest.cc
new file mode 100644
index 0000000..5cb9d73
--- /dev/null
+++ b/modules/rtp_rtcp/source/rtp_sequence_number_map_unittest.cc
@@ -0,0 +1,457 @@
+/*
+ *  Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/rtp_rtcp/source/rtp_sequence_number_map.h"
+
+#include <algorithm>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <tuple>
+#include <vector>
+
+#include "absl/memory/memory.h"
+#include "absl/types/optional.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/sequence_number_util.h"
+#include "rtc_base/random.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+using Info = RtpSequenceNumberMap::Info;
+
+constexpr uint16_t kUint16Max = std::numeric_limits<uint16_t>::max();
+constexpr size_t kMaxPossibleMaxEntries = 1 << 15;
+
+// Just a named pair.
+struct Association final {
+  Association(uint16_t sequence_number, Info info)
+      : sequence_number(sequence_number), info(info) {}
+
+  uint16_t sequence_number;
+  Info info;
+};
+
+class RtpSequenceNumberMapTest : public ::testing::Test {
+ protected:
+  RtpSequenceNumberMapTest() : random_(1983) {}
+  ~RtpSequenceNumberMapTest() override = default;
+
+  Association CreateAssociation(uint16_t sequence_number, uint32_t timestamp) {
+    return Association(sequence_number,
+                       {timestamp, random_.Rand<bool>(), random_.Rand<bool>()});
+  }
+
+  void VerifyAssociations(const RtpSequenceNumberMap& uut,
+                          const std::vector<Association>& associations) {
+    return VerifyAssociations(uut, associations.begin(), associations.end());
+  }
+
+  void VerifyAssociations(
+      const RtpSequenceNumberMap& uut,
+      std::vector<Association>::const_iterator associations_begin,
+      std::vector<Association>::const_iterator associations_end) {
+    RTC_DCHECK(associations_begin < associations_end);
+    ASSERT_EQ(static_cast<size_t>(associations_end - associations_begin),
+              uut.AssociationCountForTesting());
+    for (auto association = associations_begin; association != associations_end;
+         ++association) {
+      EXPECT_EQ(uut.Get(association->sequence_number), association->info);
+    }
+  }
+
+  // Allows several variations of the same test; definition next to the tests.
+  void GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+      bool with_wrap_around,
+      bool last_element_kept);
+
+  // Allows several variations of the same test; definition next to the tests.
+  void RepeatedSequenceNumberInvalidatesAll(size_t index_of_repeated);
+
+  // Allows several variations of the same test; definition next to the tests.
+  void MaxEntriesReachedAtSameTimeAsObsoletionOfItem(size_t max_entries,
+                                                     size_t obsoleted_count);
+
+  Random random_;
+};
+
+class RtpSequenceNumberMapTestWithParams
+    : public RtpSequenceNumberMapTest,
+      public ::testing::WithParamInterface<std::tuple<size_t, uint16_t>> {
+ protected:
+  RtpSequenceNumberMapTestWithParams() = default;
+  ~RtpSequenceNumberMapTestWithParams() override = default;
+
+  std::vector<Association> ProduceRandomAssociationSequence(
+      size_t association_count,
+      uint16_t first_sequence_number,
+      bool allow_obsoletion) {
+    std::vector<Association> associations;
+    associations.reserve(association_count);
+
+    if (association_count == 0) {
+      return associations;
+    }
+
+    associations.emplace_back(
+        first_sequence_number,
+        Info(0, random_.Rand<bool>(), random_.Rand<bool>()));
+
+    for (size_t i = 1; i < association_count; ++i) {
+      const uint16_t sequence_number =
+          associations[i - 1].sequence_number + random_.Rand(1, 100);
+      RTC_DCHECK(allow_obsoletion ||
+                 AheadOf(sequence_number, associations[0].sequence_number));
+
+      const uint32_t timestamp =
+          associations[i - 1].info.timestamp + random_.Rand(1, 10000);
+
+      associations.emplace_back(
+          sequence_number,
+          Info(timestamp, random_.Rand<bool>(), random_.Rand<bool>()));
+    }
+
+    return associations;
+  }
+};
+
+INSTANTIATE_TEST_SUITE_P(,
+                         RtpSequenceNumberMapTestWithParams,
+                         ::testing::Combine(
+                             // Association count.
+                             ::testing::Values(1, 2, 100),
+                             // First sequence number.
+                             ::testing::Values(0,
+                                               100,
+                                               kUint16Max - 100,
+                                               kUint16Max - 1,
+                                               kUint16Max)));
+
+TEST_F(RtpSequenceNumberMapTest, GetBeforeAssociationsRecordedReturnsNullOpt) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+  constexpr uint16_t kArbitrarySequenceNumber = 321;
+  EXPECT_FALSE(uut.Get(kArbitrarySequenceNumber));
+}
+
+// Version #1 - any old unknown sequence number.
+TEST_F(RtpSequenceNumberMapTest, GetUnknownSequenceNumberReturnsNullOpt1) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  constexpr uint16_t kKnownSequenceNumber = 10;
+  constexpr uint32_t kArbitrary = 987;
+  uut.Insert(kKnownSequenceNumber, {kArbitrary, false, false});
+
+  constexpr uint16_t kUnknownSequenceNumber = kKnownSequenceNumber + 1;
+  EXPECT_FALSE(uut.Get(kUnknownSequenceNumber));
+}
+
+// Version #2 - intentionally pick a value in the range of currently held
+// values, so as to trigger lower_bound / upper_bound.
+TEST_F(RtpSequenceNumberMapTest, GetUnknownSequenceNumberReturnsNullOpt2) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  const std::vector<Association> setup = {CreateAssociation(1000, 500),  //
+                                          CreateAssociation(1020, 501)};
+  for (const Association& association : setup) {
+    uut.Insert(association.sequence_number, association.info);
+  }
+
+  EXPECT_FALSE(uut.Get(1001));
+}
+
+TEST_P(RtpSequenceNumberMapTestWithParams,
+       GetKnownSequenceNumberReturnsCorrectValue) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  const size_t association_count = std::get<0>(GetParam());
+  const uint16_t first_sequence_number = std::get<1>(GetParam());
+
+  const std::vector<Association> associations =
+      ProduceRandomAssociationSequence(association_count, first_sequence_number,
+                                       /*allow_obsoletion=*/false);
+
+  for (const Association& association : associations) {
+    uut.Insert(association.sequence_number, association.info);
+  }
+
+  VerifyAssociations(uut, associations);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       GetObsoleteSequenceNumberReturnsNullOptSingleValueObsoleted) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  const std::vector<Association> associations = {
+      CreateAssociation(0, 10),       //
+      CreateAssociation(0x8000, 20),  //
+      CreateAssociation(0x8001u, 30)};
+
+  uut.Insert(associations[0].sequence_number, associations[0].info);
+
+  // First association not yet obsolete, and therefore remembered.
+  RTC_DCHECK(AheadOf(associations[1].sequence_number,
+                     associations[0].sequence_number));
+  uut.Insert(associations[1].sequence_number, associations[1].info);
+  VerifyAssociations(uut, {associations[0], associations[1]});
+
+  // Test focus - new entry obsoletes first entry.
+  RTC_DCHECK(!AheadOf(associations[2].sequence_number,
+                      associations[0].sequence_number));
+  uut.Insert(associations[2].sequence_number, associations[2].info);
+  VerifyAssociations(uut, {associations[1], associations[2]});
+}
+
+void RtpSequenceNumberMapTest::
+    GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+        bool with_wrap_around,
+        bool last_element_kept) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  std::vector<Association> associations;
+  if (with_wrap_around) {
+    associations = {CreateAssociation(kUint16Max - 1, 10),  //
+                    CreateAssociation(kUint16Max, 20),      //
+                    CreateAssociation(0, 30),               //
+                    CreateAssociation(1, 40),               //
+                    CreateAssociation(2, 50)};
+  } else {
+    associations = {CreateAssociation(1, 10),  //
+                    CreateAssociation(2, 20),  //
+                    CreateAssociation(3, 30),  //
+                    CreateAssociation(4, 40),  //
+                    CreateAssociation(5, 50)};
+  }
+
+  for (auto association : associations) {
+    uut.Insert(association.sequence_number, association.info);
+  }
+  VerifyAssociations(uut, associations);
+
+  // Define a new association that will obsolete either all previous entries,
+  // or all previous entries except for the last one, depending on the
+  // parameter instantiation of this test.
+  RTC_DCHECK_EQ(
+      static_cast<uint16_t>(
+          associations[associations.size() - 1].sequence_number),
+      static_cast<uint16_t>(
+          associations[associations.size() - 2].sequence_number + 1u));
+  uint16_t new_sequence_number;
+  if (last_element_kept) {
+    new_sequence_number =
+        associations[associations.size() - 1].sequence_number + 0x8000;
+    RTC_DCHECK(AheadOf(new_sequence_number,
+                       associations[associations.size() - 1].sequence_number));
+  } else {
+    new_sequence_number =
+        associations[associations.size() - 1].sequence_number + 0x8001;
+    RTC_DCHECK(!AheadOf(new_sequence_number,
+                        associations[associations.size() - 1].sequence_number));
+  }
+  RTC_DCHECK(!AheadOf(new_sequence_number,
+                      associations[associations.size() - 2].sequence_number));
+
+  // Record the new association.
+  const Association new_association =
+      CreateAssociation(new_sequence_number, 60);
+  uut.Insert(new_association.sequence_number, new_association.info);
+
+  // Make sure all obsoleted elements were removed.
+  const size_t obsoleted_count =
+      associations.size() - (last_element_kept ? 1 : 0);
+  for (size_t i = 0; i < obsoleted_count; ++i) {
+    EXPECT_FALSE(uut.Get(associations[i].sequence_number));
+  }
+
+  // Make sure the expected elements were not removed, and return the
+  // expected value.
+  if (last_element_kept) {
+    EXPECT_EQ(uut.Get(associations.back().sequence_number),
+              associations.back().info);
+  }
+  EXPECT_EQ(uut.Get(new_association.sequence_number), new_association.info);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted0) {
+  const bool with_wrap_around = false;
+  const bool last_element_kept = false;
+  GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+      with_wrap_around, last_element_kept);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted1) {
+  const bool with_wrap_around = true;
+  const bool last_element_kept = false;
+  GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+      with_wrap_around, last_element_kept);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted2) {
+  const bool with_wrap_around = false;
+  const bool last_element_kept = true;
+  GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+      with_wrap_around, last_element_kept);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted3) {
+  const bool with_wrap_around = true;
+  const bool last_element_kept = true;
+  GetObsoleteSequenceNumberReturnsNullOptMultipleEntriesObsoleted(
+      with_wrap_around, last_element_kept);
+}
+
+void RtpSequenceNumberMapTest::RepeatedSequenceNumberInvalidatesAll(
+    size_t index_of_repeated) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  const std::vector<Association> setup = {CreateAssociation(100, 500),  //
+                                          CreateAssociation(101, 501),  //
+                                          CreateAssociation(102, 502)};
+  RTC_DCHECK_LT(index_of_repeated, setup.size());
+  for (const Association& association : setup) {
+    uut.Insert(association.sequence_number, association.info);
+  }
+
+  const Association new_association =
+      CreateAssociation(setup[index_of_repeated].sequence_number, 503);
+  uut.Insert(new_association.sequence_number, new_association.info);
+
+  // All entries from setup invalidated.
+  // New entry valid and mapped to new value.
+  for (size_t i = 0; i < setup.size(); ++i) {
+    if (i == index_of_repeated) {
+      EXPECT_EQ(uut.Get(new_association.sequence_number), new_association.info);
+    } else {
+      EXPECT_FALSE(uut.Get(setup[i].sequence_number));
+    }
+  }
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       RepeatedSequenceNumberInvalidatesAllRepeatFirst) {
+  RepeatedSequenceNumberInvalidatesAll(0);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       RepeatedSequenceNumberInvalidatesAllRepeatMiddle) {
+  RepeatedSequenceNumberInvalidatesAll(1);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       RepeatedSequenceNumberInvalidatesAllRepeatLast) {
+  RepeatedSequenceNumberInvalidatesAll(2);
+}
+
+TEST_F(RtpSequenceNumberMapTest,
+       SequenceNumberInsideMemorizedRangeInvalidatesAll) {
+  RtpSequenceNumberMap uut(kMaxPossibleMaxEntries);
+
+  const std::vector<Association> setup = {CreateAssociation(1000, 500),  //
+                                          CreateAssociation(1020, 501),  //
+                                          CreateAssociation(1030, 502)};
+  for (const Association& association : setup) {
+    uut.Insert(association.sequence_number, association.info);
+  }
+
+  const Association new_association = CreateAssociation(1010, 503);
+  uut.Insert(new_association.sequence_number, new_association.info);
+
+  // All entries from setup invalidated.
+  // New entry valid and mapped to new value.
+  for (size_t i = 0; i < setup.size(); ++i) {
+    EXPECT_FALSE(uut.Get(setup[i].sequence_number));
+  }
+  EXPECT_EQ(uut.Get(new_association.sequence_number), new_association.info);
+}
+
+TEST_F(RtpSequenceNumberMapTest, MaxEntriesObserved) {
+  constexpr size_t kMaxEntries = 100;
+  RtpSequenceNumberMap uut(kMaxEntries);
+
+  std::vector<Association> associations;
+  associations.reserve(kMaxEntries);
+  uint32_t timestamp = 789;
+  for (size_t i = 0; i < kMaxEntries; ++i) {
+    associations.push_back(CreateAssociation(i, ++timestamp));
+    uut.Insert(associations[i].sequence_number, associations[i].info);
+  }
+  VerifyAssociations(uut, associations);  // Sanity.
+
+  const Association new_association =
+      CreateAssociation(kMaxEntries, ++timestamp);
+  uut.Insert(new_association.sequence_number, new_association.info);
+  associations.push_back(new_association);
+
+  // The +1 is for |new_association|.
+  const size_t kExpectedAssociationCount = 3 * kMaxEntries / 4 + 1;
+  const auto expected_begin =
+      std::prev(associations.end(), kExpectedAssociationCount);
+  VerifyAssociations(uut, expected_begin, associations.end());
+}
+
+void RtpSequenceNumberMapTest::MaxEntriesReachedAtSameTimeAsObsoletionOfItem(
+    size_t max_entries,
+    size_t obsoleted_count) {
+  RtpSequenceNumberMap uut(max_entries);
+
+  std::vector<Association> associations;
+  associations.reserve(max_entries);
+  uint32_t timestamp = 789;
+  for (size_t i = 0; i < max_entries; ++i) {
+    associations.push_back(CreateAssociation(i, ++timestamp));
+    uut.Insert(associations[i].sequence_number, associations[i].info);
+  }
+  VerifyAssociations(uut, associations);  // Sanity.
+
+  const uint16_t new_association_sequence_number =
+      static_cast<uint16_t>(obsoleted_count) + (1 << 15);
+  const Association new_association =
+      CreateAssociation(new_association_sequence_number, ++timestamp);
+  uut.Insert(new_association.sequence_number, new_association.info);
+  associations.push_back(new_association);
+
+  // The +1 is for |new_association|.
+  const size_t kExpectedAssociationCount =
+      std::min(3 * max_entries / 4, max_entries - obsoleted_count) + 1;
+  const auto expected_begin =
+      std::prev(associations.end(), kExpectedAssociationCount);
+  VerifyAssociations(uut, expected_begin, associations.end());
+}
+
+// Version #1 - #(obsoleted entries) < #(entries after paring down below max).
+TEST_F(RtpSequenceNumberMapTest,
+       MaxEntriesReachedAtSameTimeAsObsoletionOfItem1) {
+  constexpr size_t kMaxEntries = 100;
+  constexpr size_t kObsoletionTarget = (kMaxEntries / 4) - 1;
+  MaxEntriesReachedAtSameTimeAsObsoletionOfItem(kMaxEntries, kObsoletionTarget);
+}
+
+// Version #2 - #(obsoleted entries) == #(entries after paring down below max).
+TEST_F(RtpSequenceNumberMapTest,
+       MaxEntriesReachedAtSameTimeAsObsoletionOfItem2) {
+  constexpr size_t kMaxEntries = 100;
+  constexpr size_t kObsoletionTarget = kMaxEntries / 4;
+  MaxEntriesReachedAtSameTimeAsObsoletionOfItem(kMaxEntries, kObsoletionTarget);
+}
+
+// Version #3 - #(obsoleted entries) > #(entries after paring down below max).
+TEST_F(RtpSequenceNumberMapTest,
+       MaxEntriesReachedAtSameTimeAsObsoletionOfItem3) {
+  constexpr size_t kMaxEntries = 100;
+  constexpr size_t kObsoletionTarget = (kMaxEntries / 4) + 1;
+  MaxEntriesReachedAtSameTimeAsObsoletionOfItem(kMaxEntries, kObsoletionTarget);
+}
+
+}  // namespace
+}  // namespace webrtc