+// A class to estimate the future jitter. Used in QueueLengthPolicy (see below).
+//
+// There are many ways to estimate jitter; I've tested a few ones (and also
+// some algorithms that don't explicitly model jitter) with different
+// parameters on some real-life data in experiments/queue_drop_policy.cpp.
+// This is one based on simple order statistics where I've added some margin in
+// the number of starvation events; I believe that about one every hour would
+// probably be acceptable, but this one typically goes lower than that, at the
+// cost of 2–3 ms extra latency. (If the queue is hard-limited to one frame, it's
+// possible to get ~10 ms further down, but this would mean framedrops every
+// second or so.) The general strategy is: Take the 99.9-percentile jitter over
+// last 5000 frames, multiply by two, and that's our worst-case jitter
+// estimate. The fact that we're not using the max value means that we could
+// actually even throw away very late frames immediately, which means we only
+// get one user-visible event instead of seeing something both when the frame
+// arrives late (duplicate frame) and then again when we drop.
+class JitterHistory {
+private:
+ static constexpr size_t history_length = 5000;
+ static constexpr double percentile = 0.999;
+ static constexpr double multiplier = 2.0;
+
+public:
+ void register_metrics(const std::vector<std::pair<std::string, std::string>> &labels);
+ void unregister_metrics(const std::vector<std::pair<std::string, std::string>> &labels);
+
+ void clear() {
+ history.clear();
+ orders.clear();
+ }
+ void frame_arrived(std::chrono::steady_clock::time_point now, int64_t frame_duration, size_t dropped_frames);
+ std::chrono::steady_clock::time_point get_expected_next_frame() const { return expected_timestamp; }
+ double estimate_max_jitter() const;
+
+private:
+ // A simple O(k) based algorithm for getting the k-th largest or
+ // smallest element from our window; we simply keep the multiset
+ // ordered (insertions and deletions are O(n) as always) and then
+ // iterate from one of the sides. If we had larger values of k,
+ // we could go for a more complicated setup with two sets or heaps
+ // (one increasing and one decreasing) that we keep balanced around
+ // the point, or it is possible to reimplement std::set with
+ // counts in each node. However, since k=5, we don't need this.
+ std::multiset<double> orders;
+ std::deque<std::multiset<double>::iterator> history;
+
+ std::chrono::steady_clock::time_point expected_timestamp = std::chrono::steady_clock::time_point::min();
+
+ // Metrics. There are no direct summaries for jitter, since we already have latency summaries.
+ std::atomic<int64_t> metric_input_underestimated_jitter_frames{0};
+ std::atomic<double> metric_input_estimated_max_jitter_seconds{0.0 / 0.0};
+};
+