netem_trace/
mahimahi.rs

1//! This module can generate traces in mahimahi format for struct implementing [`BwTrace`] and
2//! load traces in mahimahi format to [`RepeatedBwPatternConfig`].
3//!
4//! Enable `mahimahi` feature to use this module.
5//!
6//! ## Examples
7//!
8//! ```
9//! # use netem_trace::{Mahimahi, MahimahiExt};
10//! # use netem_trace::model::StaticBwConfig;
11//! # use netem_trace::{Bandwidth, Duration};
12//! let mut static_bw = StaticBwConfig::new()
13//!     .bw(Bandwidth::from_mbps(24))
14//!     .duration(Duration::from_secs(1))
15//!     .build();
16//! assert_eq!(static_bw.mahimahi(&Duration::from_millis(5)), [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]);
17//! let mut static_bw = StaticBwConfig::new()
18//!     .bw(Bandwidth::from_mbps(12))
19//!     .duration(Duration::from_secs(1))
20//!     .build();
21//! assert_eq!(static_bw.mahimahi_to_string(&Duration::from_millis(5)), "1\n2\n3\n4\n5");
22//! ```
23
24#[cfg(feature = "pdo-model")]
25use crate::model::{HeavyPdoTraceConfig, RepeatedHeavyPdoPatternConfig, TraceHeavyPdoConfig};
26use crate::{
27    model::{BwTraceConfig, RepeatedBwPatternConfig, StaticBwConfig},
28    Bandwidth, BwTrace, Duration,
29};
30
31const MTU_IN_BYTES: u64 = 1500;
32const MTU_IN_BITS: u64 = MTU_IN_BYTES * 8;
33const MTU_PER_MILLIS: Bandwidth = Bandwidth::from_kbps(MTU_IN_BITS);
34const MAHIMAHI_TS_BIN: Duration = Duration::from_millis(1);
35
36macro_rules! saturating_duration_as_millis_u64 {
37    ($duration:expr) => {
38        $duration
39            .as_secs()
40            .saturating_mul(1_000)
41            .saturating_add($duration.subsec_millis() as u64)
42    };
43}
44
45/// The `Mahimahi` trait provides a method to generate a trace in mahimahi format.
46///
47/// The trace is a sequence of timestamps, each timestamp represents an opportunity
48/// of sending a packet at that timestamp.
49///
50/// This trait is automatically implemented for all types that implement `BwTrace`.
51///
52/// This trait is often used with [`MahimahiExt`] trait. [`MahimahiExt`] provides
53/// methods that generates trace and writes it to a string or a file.
54pub trait Mahimahi: BwTrace {
55    /// Generate a timestamp sequence in mahimahi format.
56    ///
57    /// Each timestamp represents an opportunity of sending a packet at that timestamp (in milliseconds).
58    ///
59    /// For example, if the bandwidth is 12Mbps (one packet per millisecond), then the sequence can be:
60    /// \[1, 2, 3, 4, 5\]
61    fn mahimahi(&mut self, total_dur: &Duration) -> Vec<u64> {
62        let mut timestamp = MAHIMAHI_TS_BIN;
63        let mut v = Vec::new();
64        let mut transfer = Bandwidth::from_bps(0);
65        let mut bin_rem = MAHIMAHI_TS_BIN;
66        while let Some((bw, mut dur)) = self.next_bw() {
67            if timestamp > *total_dur {
68                break;
69            }
70            while (timestamp <= *total_dur) && !dur.is_zero() {
71                let bin = bin_rem.min(dur);
72                bin_rem -= bin;
73                dur -= bin;
74                let bin_factor = bin.as_secs_f64() / MAHIMAHI_TS_BIN.as_secs_f64();
75                transfer += bw.mul_f64(bin_factor);
76                while transfer >= MTU_PER_MILLIS {
77                    v.push(saturating_duration_as_millis_u64!(timestamp));
78                    transfer -= MTU_PER_MILLIS;
79                }
80                if bin_rem.is_zero() {
81                    bin_rem = MAHIMAHI_TS_BIN;
82                    timestamp += MAHIMAHI_TS_BIN;
83                }
84            }
85        }
86        v
87    }
88}
89
90impl<T: BwTrace + ?Sized> Mahimahi for T {}
91
92/// The `MahimahiExt` trait provides some convenient methods to generate a trace in mahimahi format.
93pub trait MahimahiExt: Mahimahi {
94    /// Join the mahimahi timestamp sequence to a string.
95    fn mahimahi_to_string(&mut self, total_dur: &Duration) -> String {
96        let ts = self.mahimahi(total_dur);
97        itertools::join(ts, "\n")
98    }
99
100    /// Write the mahimahi timestamp sequence to a file.
101    fn mahimahi_to_file<P: AsRef<std::path::Path>>(&mut self, total_dur: &Duration, path: P) {
102        let content = self.mahimahi_to_string(total_dur);
103        std::fs::write(path, content).unwrap();
104    }
105}
106
107impl<T: Mahimahi + ?Sized> MahimahiExt for T {}
108
109/// Load a mahimahi trace to a [`RepeatedBwPatternConfig`].
110///
111/// The `trace` is a sequence of timestamps, each timestamp represents an opportunity
112/// of sending a packet at that timestamp.
113///
114/// The `count` is the number of times the trace repeats. If `count` is `None` or `Some(0)`,
115/// then the trace will repeat forever.
116///
117/// Each timestamp will be converted into a 12Mbps bandwidth lasting for 1 millisecond,
118/// and then accumulated. For example, if the trace is \[1, 1, 5, 6\] and count is `Some(1)`,
119/// then the bandwidth pattern will be \[24Mbps for 1ms, 0Mbps for 3ms, 12Mbps for 2ms\].
120///
121/// **Warning:** In some cases, this trace may slightly deviate from the behavior of mahimahi.
122///
123/// Returns `Err` string if the mahimahi trace is invalid.
124pub fn load_mahimahi_trace(
125    trace: Vec<u64>,
126    count: Option<usize>,
127) -> Result<RepeatedBwPatternConfig, &'static str> {
128    let mut pattern: Vec<StaticBwConfig> = vec![];
129    // The closure inserts a bandwidth config into the pattern.
130    let mut insert_into_pattern = |config| {
131        if pattern.is_empty() {
132            pattern.push(config);
133        } else {
134            let last_config = pattern.last_mut().unwrap();
135            if last_config.bw.unwrap() == config.bw.unwrap() {
136                last_config.duration =
137                    Some(last_config.duration.unwrap() + config.duration.unwrap());
138            } else {
139                pattern.push(config);
140            }
141        }
142    };
143
144    let mut zeor_ts_cnt = 0; // count of zero timestamps
145    let mut last_ts = 0; // last non-zero timestamp
146    let mut last_cnt = 0; // count of last non-zero timestamp
147    for ts in trace {
148        // count zero timestamps
149        if ts == 0 {
150            zeor_ts_cnt += 1;
151            continue;
152        }
153        // non-zero timestamps
154        match ts.cmp(&last_ts) {
155            std::cmp::Ordering::Less => {
156                return Err("timestamps must be monotonically nondecreasing");
157            }
158            std::cmp::Ordering::Equal => {
159                last_cnt += 1;
160            }
161            std::cmp::Ordering::Greater => {
162                if last_ts > 0 {
163                    // insert new bandwidth config
164                    insert_into_pattern(
165                        StaticBwConfig::new()
166                            .bw(MTU_PER_MILLIS * last_cnt)
167                            .duration(MAHIMAHI_TS_BIN),
168                    );
169                }
170                if ts - last_ts > 1 {
171                    // insert zero bandwidth
172                    insert_into_pattern(
173                        StaticBwConfig::new()
174                            .bw(Bandwidth::ZERO)
175                            .duration(MAHIMAHI_TS_BIN * ((ts - last_ts - 1) as u32)),
176                    );
177                }
178                last_cnt = 1;
179                last_ts = ts;
180            }
181        }
182    }
183    if last_cnt == 0 {
184        // no non-zero timestamps
185        return Err("trace must last for a nonzero amount of time");
186    } else {
187        // merge final timestamps and zero timestamps
188        insert_into_pattern(
189            StaticBwConfig::new()
190                .bw(MTU_PER_MILLIS * (last_cnt + zeor_ts_cnt))
191                .duration(MAHIMAHI_TS_BIN),
192        );
193    }
194    Ok(RepeatedBwPatternConfig::new()
195        .count(count.unwrap_or(0))
196        .pattern(
197            pattern
198                .drain(..)
199                .map(|config| Box::new(config) as Box<dyn BwTraceConfig>)
200                .collect(),
201        ))
202}
203
204/// How many bytes one line of a mahimahi trace can deliver in mahimahi (`PACKET_SIZE` in mahimahi).
205pub const MAHIMAHI_PDO_BYTES: u64 = 1504;
206
207/// Load a mahimahi trace to a heavy PDO trace ([`RepeatedHeavyPdoPatternConfig`]).
208///
209/// The `trace` is a sequence of timestamps (in milliseconds), each timestamp represents an opportunity
210/// of sending `pdo_bytes` bytes at that timestamp. Use [`MAHIMAHI_PDO_BYTES`] to follow mahimahi,
211/// or [`CELLREPLAY_PDO_SIZE`](crate::model::CELLREPLAY_PDO_SIZE) to follow the heavy PDO trace of CellReplay.
212///
213/// Timestamps with the same value are merged into one PDO. For example, if the trace is \[1, 1, 5, 6\]
214/// and `pdo_bytes` is 1504, the heavy PDO trace will be \[(1ms, 3008), (4ms, 1504), (1ms, 1504)\].
215///
216/// The `count` is the number of times the trace repeats. If `count` is `None` or `Some(0)`,
217/// then the trace will repeat forever. Like mahimahi, the next cycle starts at the last timestamp,
218/// so leading zero timestamps go out together with the last timestamp of the previous cycle.
219///
220/// Unlike [`load_mahimahi_trace`], there is no bandwidth here, so the timing is exactly the same as in mahimahi.
221///
222/// Returns `Err` string if the mahimahi trace is invalid.
223#[cfg(feature = "pdo-model")]
224pub fn load_mahimahi_heavy_pdo_trace(
225    trace: Vec<u64>,
226    count: Option<usize>,
227    pdo_bytes: u64,
228) -> Result<RepeatedHeavyPdoPatternConfig, &'static str> {
229    let mut pattern: Vec<(Duration, u64)> = vec![];
230    let mut last_ts = 0;
231    for ts in trace {
232        match ts.cmp(&last_ts) {
233            std::cmp::Ordering::Less => {
234                return Err("timestamps must be monotonically nondecreasing");
235            }
236            std::cmp::Ordering::Equal if !pattern.is_empty() => {
237                pattern.last_mut().unwrap().1 += pdo_bytes;
238            }
239            _ => {
240                pattern.push((Duration::from_millis(ts - last_ts), pdo_bytes));
241                last_ts = ts;
242            }
243        }
244    }
245    if last_ts == 0 {
246        return Err("trace must last for a nonzero amount of time");
247    }
248    Ok(RepeatedHeavyPdoPatternConfig::new()
249        .count(count.unwrap_or(0))
250        .pattern(vec![
251            Box::new(TraceHeavyPdoConfig::new().pattern(pattern)) as Box<dyn HeavyPdoTraceConfig>
252        ]))
253}
254
255#[cfg(test)]
256mod test {
257    use super::*;
258    use crate::model::StaticBwConfig;
259    use crate::Bandwidth;
260
261    #[test]
262    #[cfg(feature = "pdo-model")]
263    fn test_load_heavy_pdo() {
264        use crate::HeavyPdoTrace;
265
266        assert!(matches!(
267            load_mahimahi_heavy_pdo_trace(vec![0, 2, 4, 3], None, MAHIMAHI_PDO_BYTES),
268            Err("timestamps must be monotonically nondecreasing")
269        ));
270        assert!(matches!(
271            load_mahimahi_heavy_pdo_trace(vec![0, 0, 0], None, MAHIMAHI_PDO_BYTES),
272            Err("trace must last for a nonzero amount of time")
273        ));
274        assert!(matches!(
275            load_mahimahi_heavy_pdo_trace(vec![], None, MAHIMAHI_PDO_BYTES),
276            Err("trace must last for a nonzero amount of time")
277        ));
278
279        let mut pdo = load_mahimahi_heavy_pdo_trace(vec![1, 1, 5, 6], Some(2), 1504)
280            .unwrap()
281            .build();
282        for _ in 0..2 {
283            assert_eq!(pdo.next_heavy_pdo(), Some((Duration::from_millis(1), 3008)));
284            assert_eq!(pdo.next_heavy_pdo(), Some((Duration::from_millis(4), 1504)));
285            assert_eq!(pdo.next_heavy_pdo(), Some((Duration::from_millis(1), 1504)));
286        }
287        assert_eq!(pdo.next_heavy_pdo(), None);
288
289        // leading zeros: in the second cycle they go out at the same time as the last PDO
290        let mut pdo = load_mahimahi_heavy_pdo_trace(vec![0, 0, 2, 2, 3], None, 1400)
291            .unwrap()
292            .build();
293        for _ in 0..3 {
294            assert_eq!(pdo.next_heavy_pdo(), Some((Duration::ZERO, 2800)));
295            assert_eq!(pdo.next_heavy_pdo(), Some((Duration::from_millis(2), 2800)));
296            assert_eq!(pdo.next_heavy_pdo(), Some((Duration::from_millis(1), 1400)));
297        }
298    }
299
300    #[test]
301    #[cfg(feature = "pdo-model")]
302    fn test_heavy_pdo_matches_timestamps() {
303        use crate::HeavyPdoTrace;
304
305        // replaying the PDOs gives back the same timestamps as mahimahi, also across cycles
306        let trace = vec![2, 2, 3, 3, 4, 4, 5, 5, 8, 9];
307        let mut pdo = load_mahimahi_heavy_pdo_trace(trace.clone(), Some(2), 1)
308            .unwrap()
309            .build();
310        let mut now = 0;
311        let mut replayed = vec![];
312        while let Some((interval, bytes)) = pdo.next_heavy_pdo() {
313            now += interval.as_millis() as u64;
314            replayed.extend(std::iter::repeat_n(now, bytes as usize));
315        }
316        let expected: Vec<u64> = trace
317            .iter()
318            .copied()
319            .chain(trace.iter().map(|ts| ts + 9))
320            .collect();
321        assert_eq!(replayed, expected);
322    }
323
324    #[test]
325    fn test_trait() {
326        let mut static_bw = StaticBwConfig::new()
327            .bw(Bandwidth::from_mbps(24))
328            .duration(Duration::from_secs(1))
329            .build();
330        assert_eq!(
331            static_bw.mahimahi(&Duration::from_millis(5)),
332            [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
333        );
334        let mut static_bw = StaticBwConfig::new()
335            .bw(Bandwidth::from_mbps(12))
336            .duration(Duration::from_secs(1))
337            .build();
338        assert_eq!(
339            static_bw.mahimahi_to_string(&Duration::from_millis(5)),
340            "1\n2\n3\n4\n5"
341        );
342        let a = vec![
343            Box::new(
344                StaticBwConfig::new()
345                    .bw(Bandwidth::from_mbps(12))
346                    .duration(Duration::from_millis(2)),
347            ) as Box<dyn BwTraceConfig>,
348            Box::new(
349                StaticBwConfig::new()
350                    .bw(Bandwidth::from_mbps(24))
351                    .duration(Duration::from_millis(2)),
352            ) as Box<dyn BwTraceConfig>,
353        ];
354        let mut c = Box::new(RepeatedBwPatternConfig::new().pattern(a).count(2)).into_model();
355        assert_eq!(
356            c.mahimahi(&Duration::MAX),
357            [1, 2, 3, 3, 4, 4, 5, 6, 7, 7, 8, 8]
358        );
359    }
360
361    #[test]
362    fn test_load() {
363        assert!(matches!(
364            load_mahimahi_trace(vec![0, 2, 4, 3], None),
365            Err("timestamps must be monotonically nondecreasing")
366        ));
367        assert!(matches!(
368            load_mahimahi_trace(vec![0, 0, 0], None),
369            Err("trace must last for a nonzero amount of time")
370        ));
371
372        let trace = vec![1, 1, 5, 6];
373        let mut bw = load_mahimahi_trace(trace, None).unwrap().build();
374        // first cycle
375        assert_eq!(
376            bw.next_bw(),
377            Some((Bandwidth::from_mbps(24), Duration::from_millis(1)))
378        );
379        assert_eq!(
380            bw.next_bw(),
381            Some((Bandwidth::from_mbps(0), Duration::from_millis(3)))
382        );
383        assert_eq!(
384            bw.next_bw(),
385            Some((Bandwidth::from_mbps(12), Duration::from_millis(2)))
386        );
387        // second cycle
388        assert_eq!(
389            bw.next_bw(),
390            Some((Bandwidth::from_mbps(24), Duration::from_millis(1)))
391        );
392
393        let trace = vec![0, 0, 2, 2, 3, 3, 6, 6];
394        let mut bw = load_mahimahi_trace(trace, Some(0)).unwrap().build();
395        // first cycle
396        assert_eq!(
397            bw.next_bw(),
398            Some((Bandwidth::from_mbps(0), Duration::from_millis(1)))
399        );
400        assert_eq!(
401            bw.next_bw(),
402            Some((Bandwidth::from_mbps(24), Duration::from_millis(2)))
403        );
404        assert_eq!(
405            bw.next_bw(),
406            Some((Bandwidth::from_mbps(0), Duration::from_millis(2)))
407        );
408        assert_eq!(
409            bw.next_bw(),
410            Some((Bandwidth::from_mbps(48), Duration::from_millis(1)))
411        );
412        // second cycle
413        assert_eq!(
414            bw.next_bw(),
415            Some((Bandwidth::from_mbps(0), Duration::from_millis(1)))
416        );
417        assert_eq!(
418            bw.next_bw(),
419            Some((Bandwidth::from_mbps(24), Duration::from_millis(2)))
420        );
421
422        let mut bw = RepeatedBwPatternConfig::new()
423            .count(2)
424            .pattern(vec![
425                Box::new(load_mahimahi_trace(vec![1, 1, 2, 2, 3, 3], Some(1)).unwrap())
426                    as Box<dyn BwTraceConfig>,
427                Box::new(load_mahimahi_trace(vec![1, 2], Some(2)).unwrap())
428                    as Box<dyn BwTraceConfig>,
429            ])
430            .build();
431        assert_eq!(
432            bw.next_bw(),
433            Some((Bandwidth::from_mbps(24), Duration::from_millis(3)))
434        );
435        assert_eq!(
436            bw.next_bw(),
437            Some((Bandwidth::from_mbps(12), Duration::from_millis(2)))
438        );
439        assert_eq!(
440            bw.next_bw(),
441            Some((Bandwidth::from_mbps(12), Duration::from_millis(2)))
442        );
443        assert_eq!(
444            bw.next_bw(),
445            Some((Bandwidth::from_mbps(24), Duration::from_millis(3)))
446        );
447        assert_eq!(
448            bw.next_bw(),
449            Some((Bandwidth::from_mbps(12), Duration::from_millis(2)))
450        );
451        assert_eq!(
452            bw.next_bw(),
453            Some((Bandwidth::from_mbps(12), Duration::from_millis(2)))
454        );
455        assert_eq!(bw.next_bw(), None);
456    }
457
458    #[test]
459    fn test_interoperability() {
460        // this check only works on non-zero timestamps trace, which has full interoperability
461        let check = |trace: Vec<u64>| {
462            let mut bw = load_mahimahi_trace(trace.clone(), None).unwrap().build();
463            assert_eq!(
464                bw.mahimahi(&Duration::from_millis(*trace.last().unwrap())),
465                trace
466            );
467        };
468        check(vec![1, 1, 5, 6]);
469        check(vec![2, 2, 3, 3, 4, 4, 5, 5, 8, 9]);
470
471        let mut bw = load_mahimahi_trace(vec![0, 0, 2, 2, 3, 3, 6, 6], None)
472            .unwrap()
473            .build();
474        assert_eq!(
475            bw.mahimahi(&Duration::from_millis(12)),
476            vec![2, 2, 3, 3, 6, 6, 6, 6, 8, 8, 9, 9, 12, 12, 12, 12]
477        );
478
479        let mut bw = RepeatedBwPatternConfig::new()
480            .count(2)
481            .pattern(vec![
482                Box::new(load_mahimahi_trace(vec![1, 1, 2, 2, 3, 3], Some(1)).unwrap())
483                    as Box<dyn BwTraceConfig>,
484                Box::new(load_mahimahi_trace(vec![1, 2], Some(2)).unwrap())
485                    as Box<dyn BwTraceConfig>,
486            ])
487            .build();
488        assert_eq!(
489            bw.mahimahi(&Duration::MAX),
490            vec![1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 12, 13, 14]
491        );
492    }
493}
netem_trace/mahimahi.rs

netem_trace/
mahimahi.rs
