response_time_analysis/arrival/
poisson.rs

1use super::{ArrivalBound, Propagated};
2use crate::time::{Duration, Time};
3
4/// Model of a [Poisson](https://en.wikipedia.org/wiki/Poisson_distribution) arrival process.
5#[derive(Copy, Clone, Debug)]
6pub struct Poisson {
7    /// Mean arrival rate (lambda).
8    pub rate: f64,
9}
10
11impl Poisson {
12    pub fn arrival_probability(&self, delta: Duration, njobs: usize) -> f64 {
13        // quick and dirty naive factorial: k!
14        let mut denominator = 1.0;
15        for x in 1..(njobs + 1) {
16            denominator *= x as f64;
17        }
18        let mean = Time::from(delta) as f64 * self.rate;
19        let mut numerator = (-mean).exp(); // e^(- rate * delta)
20        numerator *= mean.powi(njobs as i32); // (rate * delta)**k
21        numerator / denominator
22    }
23
24    pub fn approximate(&self, epsilon: f64) -> ApproximatedPoisson {
25        ApproximatedPoisson {
26            poisson: *self,
27            epsilon,
28        }
29    }
30}
31
32/// A finite approximation of a Poisson process with bounded
33/// probability of under-approximation.
34///
35/// A Poisson arrival process as modeled by [Poisson] cannot comply
36/// with the the [ArrivalBound] interface as there is a diminishing,
37/// but non-zero probability for an arbitrary large number of
38/// arrivals to occur in any interval. The  [ApproximatedPoisson]
39/// process implements the [ArrivalBound] interface with a
40/// configurable residual probability of excessive arrivals.
41///
42/// The bound [number_arrivals][ApproximatedPoisson::number_arrivals]
43/// ensures that the claimed number of job arrivals are not exceeded
44/// with probability at least `1 - epsilon`.
45///
46/// Note: the implementation is intended to be simple, but not
47/// necessarily fast, so it's best to convert it into an [arrival
48/// curve][super::Curve] before use if performance is of interest.
49#[derive(Copy, Clone, Debug)]
50pub struct ApproximatedPoisson {
51    /// The underlying Poisson process.
52    poisson: Poisson,
53    /// The acceptable probability of under-approximating the number
54    /// of arrivals. Must be small but non-zero.
55    epsilon: f64,
56}
57
58impl ApproximatedPoisson {
59    /// Construct a new approximated Poisson arrival process with
60    /// mean arrival rate `lambda` and under-approximation bound
61    /// `epsilon`.
62    pub fn new(lambda: f64, epsilon: f64) -> Self {
63        ApproximatedPoisson {
64            epsilon,
65            poisson: Poisson { rate: lambda },
66        }
67    }
68}
69
70impl ArrivalBound for ApproximatedPoisson {
71    /// Bound the number of jobs released in any interval of length `delta` with probability `1 - epsilon`.
72    fn number_arrivals(&self, delta: Duration) -> usize {
73        if delta.is_non_zero() {
74            let mut cumulative_prob = 0.0;
75            let mut njobs = 0;
76            loop {
77                cumulative_prob += self.poisson.arrival_probability(delta, njobs);
78                if cumulative_prob + self.epsilon >= 1.0 {
79                    break;
80                }
81                njobs += 1;
82            }
83            njobs
84        } else {
85            0
86        }
87    }
88
89    fn clone_with_jitter(&self, jitter: Duration) -> Box<dyn ArrivalBound> {
90        Box::new(Propagated::with_jitter(self, jitter))
91    }
92}
response_time_analysis/arrival/poisson.rs

response_time_analysis/arrival/
poisson.rs
