Skip to content
rachel/esp32-radio
File

Blob: firmware/vendor/str0m/src/bwe/alr_detector/budget.rs

rust282 lines
1//! Interval budget tracker for ALR detection.
2//!
3//! Port of libWebRTC's IntervalBudget class from
4//! `webrtc/modules/pacing/interval_budget.{h,cc}`
5 
6use std::time::Duration;
7 
8use crate::rtp_::{Bitrate, DataSize};
9 
10/// Leaky bucket budget tracker over a fixed time window.
11///
12/// Used by ALR detector to handle bursty traffic (encoders, etc.)
13/// over a 500ms window. Tracks how much "budget" we have left
14/// based on target rate vs. actual send rate.
15///
16/// This implements the same logic as libWebRTC's IntervalBudget class
17/// to ensure ALR detection behaves identically when handling bursty
18/// encoder traffic (keyframes, scene changes, temporal layers, etc.)
19#[derive(Debug, Clone)]
20pub struct IntervalBudget {
21    /// Target bitrate for budget calculation
22    target_rate: Bitrate,
23    /// Maximum bytes that can accumulate in the budget
24    max_bytes_in_budget: DataSize,
25    /// Current bytes remaining in budget (can be negative = debt)
26    bytes_remaining: DataSize,
27    /// Whether underuse can build up credit across intervals
28    can_build_up_underuse: bool,
29}
30 
31impl IntervalBudget {
32    /// Window size for budget tracking
33    const WINDOW: Duration = Duration::from_millis(500);
34 
35    /// Create a new IntervalBudget with the specified target rate.
36    pub fn new(target_rate: Bitrate, can_build_up_underuse: bool) -> Self {
37        let max_bytes_in_budget = Self::calculate_max_bytes(target_rate);
38 
39        Self {
40            target_rate,
41            max_bytes_in_budget,
42            bytes_remaining: DataSize::ZERO,
43            can_build_up_underuse,
44        }
45    }
46 
47    /// Update the target bitrate.
48    ///
49    /// Called when the BWE estimate changes. Clamps existing bytes_remaining
50    /// to the new max_bytes_in_budget range.
51    pub fn set_target_rate(&mut self, target_rate: Bitrate) {
52        self.target_rate = target_rate;
53        self.max_bytes_in_budget = Self::calculate_max_bytes(target_rate);
54 
55        // Clamp bytes_remaining to new budget limits
56        let max = self.max_bytes_in_budget;
57        let neg_max = max * -1i64;
58        self.bytes_remaining = DataSize::bytes(
59            self.bytes_remaining
60                .as_bytes_i64()
61                .clamp(neg_max, max.as_bytes_i64()),
62        );
63    }
64 
65    /// Add budget based on elapsed time.
66    ///
67    /// Increases the budget by `target_rate * delta_time`.
68    /// Behavior depends on `can_build_up_underuse`:
69    /// - If true: underuse accumulates (for ALR detection)
70    /// - If false: budget resets each interval (for pacing)
71    pub fn increase_budget(&mut self, delta_time: Duration) {
72        let bytes = self.target_rate * delta_time;
73 
74        let max = self.max_bytes_in_budget;
75        if self.bytes_remaining.as_bytes_i64() < 0 || self.can_build_up_underuse {
76            // We overused last interval, compensate this interval
77            // OR we allow building up underuse credit
78            self.bytes_remaining = DataSize::bytes(
79                (self.bytes_remaining + bytes)
80                    .as_bytes_i64()
81                    .min(max.as_bytes_i64()),
82            );
83        } else {
84            // If we underused last interval we can't use it this interval
85            self.bytes_remaining = DataSize::bytes(bytes.as_bytes_i64().min(max.as_bytes_i64()));
86        }
87    }
88 
89    /// Consume budget by the specified number of bytes.
90    ///
91    /// This represents sending data. The budget can go negative (debt).
92    pub fn use_budget(&mut self, bytes: DataSize) {
93        let max = self.max_bytes_in_budget;
94        let neg_max = max * -1i64;
95        self.bytes_remaining =
96            DataSize::bytes((self.bytes_remaining - bytes).as_bytes_i64().max(neg_max));
97    }
98 
99    /// Get the current budget ratio.
100    ///
101    /// Returns a value in the range [-1.0, 1.0]:
102    /// - 1.0 = full budget (maximum underuse)
103    /// - 0.0 = neutral (sending exactly at target rate)
104    /// - -1.0 = maximum debt (maximum overuse)
105    ///
106    /// Used by ALR detector for hysteresis thresholds:
107    /// - Enter ALR when ratio > 0.80 (sustained low usage)
108    /// - Exit ALR when ratio < 0.50 (increased usage)
109    pub fn budget_ratio(&self) -> f64 {
110        let max = self.max_bytes_in_budget.as_bytes_i64();
111        if max == 0 {
112            return 0.0;
113        }
114        self.bytes_remaining.as_bytes_i64() as f64 / max as f64
115    }
116 
117    /// Calculate max_bytes_in_budget from target rate
118    fn calculate_max_bytes(target_rate: Bitrate) -> DataSize {
119        target_rate * Self::WINDOW
120    }
121 
122    #[cfg(test)]
123    pub fn target_rate(&self) -> Bitrate {
124        self.target_rate
125    }
126 
127    #[cfg(test)]
128    pub fn bytes_remaining(&self) -> i64 {
129        self.bytes_remaining.as_bytes_i64()
130    }
131}
132 
133#[cfg(test)]
134mod tests {
135    use super::*;
136 
137    #[test]
138    fn test_initial_budget_is_zero() {
139        let budget = IntervalBudget::new(Bitrate::kbps(300), true);
140        assert_eq!(budget.bytes_remaining(), 0);
141        assert_eq!(budget.budget_ratio(), 0.0);
142    }
143 
144    #[test]
145    fn test_increase_budget_accumulates() {
146        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
147 
148        // Add 100ms worth of budget: 300 kbps * 100ms = 3750 bytes
149        budget.increase_budget(Duration::from_millis(100));
150        assert_eq!(budget.bytes_remaining(), 3750);
151 
152        // Budget ratio should be positive (underuse)
153        assert!(budget.budget_ratio() > 0.0);
154    }
155 
156    #[test]
157    fn test_use_budget_creates_debt() {
158        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
159 
160        // Use 5000 bytes
161        budget.use_budget(DataSize::bytes(5000));
162        assert_eq!(budget.bytes_remaining(), -5000);
163 
164        // Budget ratio should be negative (overuse)
165        assert!(budget.budget_ratio() < 0.0);
166    }
167 
168    #[test]
169    fn test_budget_ratio_clamped() {
170        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
171        let max_bytes = (Bitrate::kbps(300) * Duration::from_millis(500)).as_bytes_i64();
172 
173        // Fill to max
174        budget.increase_budget(Duration::from_millis(500));
175        assert_eq!(budget.budget_ratio(), 1.0);
176 
177        // Try to add more - should stay at 1.0
178        budget.increase_budget(Duration::from_millis(100));
179        assert_eq!(budget.budget_ratio(), 1.0);
180 
181        // Use all budget plus create max debt
182        budget.use_budget(DataSize::bytes(max_bytes * 2));
183        assert_eq!(budget.budget_ratio(), -1.0);
184    }
185 
186    #[test]
187    fn test_can_build_up_underuse_false() {
188        let mut budget = IntervalBudget::new(Bitrate::kbps(300), false);
189 
190        // Add budget
191        budget.increase_budget(Duration::from_millis(100));
192        let after_first = budget.bytes_remaining();
193        assert!(after_first > 0);
194 
195        // Add more budget - should reset, not accumulate
196        budget.increase_budget(Duration::from_millis(100));
197        assert_eq!(budget.bytes_remaining(), 3750); // Only the latest 100ms
198 
199        // Not the accumulated 7500
200        assert_ne!(budget.bytes_remaining(), after_first + 3750);
201    }
202 
203    #[test]
204    fn test_can_build_up_underuse_true() {
205        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
206 
207        // Add budget
208        budget.increase_budget(Duration::from_millis(100));
209        let after_first = budget.bytes_remaining();
210 
211        // Add more budget - should accumulate
212        budget.increase_budget(Duration::from_millis(100));
213        assert_eq!(budget.bytes_remaining(), after_first + 3750);
214    }
215 
216    #[test]
217    fn test_debt_recovery() {
218        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
219 
220        // Create debt
221        budget.use_budget(DataSize::bytes(5000));
222        assert_eq!(budget.bytes_remaining(), -5000);
223 
224        // Add budget to recover from debt
225        budget.increase_budget(Duration::from_millis(200));
226        let expected_recovery = 3750 * 2; // 200ms worth
227        assert_eq!(budget.bytes_remaining(), -5000 + expected_recovery);
228    }
229 
230    #[test]
231    fn test_set_target_rate_clamps_budget() {
232        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
233 
234        // Build up budget at 300 kbps
235        budget.increase_budget(Duration::from_millis(500));
236        let old_max = (Bitrate::kbps(300) * Duration::from_millis(500)).as_bytes_i64();
237        assert_eq!(budget.bytes_remaining(), old_max);
238 
239        // Reduce target rate - budget should be clamped to new max
240        budget.set_target_rate(Bitrate::kbps(150));
241        let new_max = (Bitrate::kbps(150) * Duration::from_millis(500)).as_bytes_i64();
242        assert_eq!(budget.bytes_remaining(), new_max);
243        assert!(new_max < old_max);
244    }
245 
246    #[test]
247    fn test_alr_hysteresis_thresholds() {
248        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
249 
250        // Simulate ALR entry threshold (80% budget ratio)
251        let target_bytes =
252            (0.8 * (Bitrate::kbps(300) * Duration::from_millis(500)).as_bytes_i64() as f64) as i64;
253 
254        // Accumulate budget to 80% threshold
255        while budget.bytes_remaining() < target_bytes {
256            budget.increase_budget(Duration::from_millis(50));
257        }
258 
259        assert!(budget.budget_ratio() >= 0.80);
260 
261        // Simulate ALR exit threshold (50% budget ratio)
262        // Use budget to bring ratio down
263        let use_amount =
264            (0.30 * (Bitrate::kbps(300) * Duration::from_millis(500)).as_bytes_i64() as f64) as i64;
265        budget.use_budget(DataSize::bytes(use_amount));
266 
267        assert!(budget.budget_ratio() < 0.80);
268        assert!(budget.budget_ratio() > 0.40); // Should be around 50%
269    }
270 
271    #[test]
272    fn test_target_rate_getter() {
273        let budget = IntervalBudget::new(Bitrate::kbps(500), true);
274        assert_eq!(budget.target_rate(), Bitrate::kbps(500));
275 
276        // After modifying target rate
277        let mut budget = IntervalBudget::new(Bitrate::kbps(300), true);
278        budget.set_target_rate(Bitrate::kbps(600));
279        assert_eq!(budget.target_rate(), Bitrate::kbps(600));
280    }
281}