response_time_analysis/arrival/
arrival_curve_prefix.rs

1use super::{ArrivalBound, Curve, Propagated};
2use crate::time::Duration;
3use std::iter;
4
5/// Representation of a step of an arrival curve within a finite prefix.
6type Step = (Duration, usize);
7
8/// An alternate representation of an arbitrary arrival curve intended
9/// primarily for input purposes.
10///
11/// Whereas the [Curve] arrival bound is based on a delta-min
12/// representation, this variant expresses the underlying arrival
13/// curve by means of a finite sequence of `steps` and a `horizon`.
14/// This makes this representation easier to use in cases where an
15/// arrival curve is not already given in delta-min representation.
16///
17/// Up to the `horizon`, this representation produces exact results.
18/// Beyond the horizon, it uses a quick, but potentially quite
19/// pessimistic extrapolation. For better extrapolation, convert the
20/// [ArrivalCurvePrefix] to a [Curve] (via [std::convert::From]) and
21/// use its extrapolation facilities (or simply wrap it as an
22/// [ExtrapolatingCurve](super::ExtrapolatingCurve)).
23#[derive(Clone, Debug)]
24pub struct ArrivalCurvePrefix {
25    horizon: Duration,
26    steps: Vec<Step>,
27}
28
29// A step-based implementation of an eta-max curve (i.e., arrival curve).
30impl ArrivalCurvePrefix {
31    /// Construct a new `ArrivalCurvePrefix` from a given `horizon`
32    /// and a sequence of `steps`.
33    ///
34    /// The given sequence of `steps` is a list of tuples of the form
35    /// `(delta, n)`, with the meaning that the arrival curve first assumes
36    /// the value `n` for the interval length `delta`.
37    ///
38    /// The given sequence of `steps` must be contained in the
39    /// horizon and strictly monotonic in `n`.
40    pub fn new(horizon: Duration, steps: Vec<Step>) -> ArrivalCurvePrefix {
41        // make sure the prefix is well-formed
42        let mut last_njobs: usize = 0;
43        for (delta, njobs) in &steps {
44            assert!(*delta <= horizon);
45            assert!(last_njobs < *njobs);
46            last_njobs = *njobs;
47        }
48        ArrivalCurvePrefix { horizon, steps }
49    }
50
51    /// Obtain an arrival-curve prefix by recording all steps of a
52    /// given arbitrary arrival process `T` until a given horizon.
53    ///
54    /// The `steps` vector covers all arrivals until the given `horizon`.
55    pub fn from_arrival_bound_until<T: ArrivalBound>(
56        ab: &T,
57        horizon: Duration,
58    ) -> ArrivalCurvePrefix {
59        Self::new(
60            horizon,
61            ab.steps_iter()
62                .take_while(|delta| *delta <= horizon.max(Duration::epsilon()))
63                .map(|delta| (delta, ab.number_arrivals(delta)))
64                .collect(),
65        )
66    }
67
68    fn max_njobs_in_horizon(&self) -> usize {
69        self.steps.last().map(|(_, njobs)| *njobs).unwrap_or(0)
70    }
71
72    fn lookup(&self, delta: Duration) -> usize {
73        assert!(delta <= self.horizon);
74        if delta.is_zero() {
75            0
76        } else {
77            let step = self
78                .steps
79                .iter()
80                .enumerate()
81                .skip_while(|(_i, (min_distance, _njobs))| *min_distance <= delta)
82                .map(|(i, _)| i)
83                .next();
84            let i = step.unwrap_or(self.steps.len());
85            self.steps[i - 1].1
86        }
87    }
88}
89
90impl ArrivalBound for ArrivalCurvePrefix {
91    fn number_arrivals(&self, delta: Duration) -> usize {
92        let full_horizons = delta / self.horizon;
93        let partial_horizon = delta % self.horizon;
94        self.max_njobs_in_horizon() * (full_horizons as usize) + self.lookup(partial_horizon)
95    }
96
97    fn clone_with_jitter(&self, jitter: Duration) -> Box<dyn ArrivalBound> {
98        Box::new(Propagated::with_jitter(self, jitter))
99    }
100
101    fn steps_iter<'a>(&'a self) -> Box<dyn Iterator<Item = Duration> + 'a> {
102        let horizon = self.horizon;
103        Box::new(
104            iter::once(Duration::zero()).chain((0..).flat_map(move |cycle: u64| {
105                self.steps
106                    .iter()
107                    .map(move |(offset, _njobs)| *offset + horizon * cycle)
108            })),
109        )
110    }
111}
112
113impl From<&ArrivalCurvePrefix> for Curve {
114    fn from(ac: &ArrivalCurvePrefix) -> Self {
115        let njobs = ac.max_njobs_in_horizon();
116        // construct equivalent curve from jobs in horizon
117        let mut curve = Curve::from_arrival_bound(&ac, njobs);
118        // trigger extrapolation to one additional job to account for horizon
119        curve.extrapolate_with_bound((ac.horizon + Duration::epsilon(), njobs + 1));
120        curve
121    }
122}
123
124impl From<ArrivalCurvePrefix> for Curve {
125    fn from(ac: ArrivalCurvePrefix) -> Self {
126        Self::from(&ac)
127    }
128}
response_time_analysis/arrival/arrival_curve_prefix.rs

response_time_analysis/arrival/
arrival_curve_prefix.rs
