response-time-analysis 0.3.2

Definitions and algorithms for response-time analysis of real-time systems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

use super::{ArrivalBound, Propagated};
use crate::time::{Duration, Time};

/// Model of a [Poisson](https://en.wikipedia.org/wiki/Poisson_distribution) arrival process.
#[derive(Copy, Clone, Debug)]
pub struct Poisson {
    /// Mean arrival rate (lambda).
    pub rate: f64,
}

impl Poisson {
    pub fn arrival_probability(&self, delta: Duration, njobs: usize) -> f64 {
        // quick and dirty naive factorial: k!
        let mut denominator = 1.0;
        for x in 1..(njobs + 1) {
            denominator *= x as f64;
        }
        let mean = Time::from(delta) as f64 * self.rate;
        let mut numerator = (-mean).exp(); // e^(- rate * delta)
        numerator *= mean.powi(njobs as i32); // (rate * delta)**k
        numerator / denominator
    }

    pub fn approximate(&self, epsilon: f64) -> ApproximatedPoisson {
        ApproximatedPoisson {
            poisson: *self,
            epsilon,
        }
    }
}

/// A finite approximation of a Poisson process with bounded
/// probability of under-approximation.
///
/// A Poisson arrival process as modeled by [Poisson] cannot comply
/// with the the [ArrivalBound] interface as there is a diminishing,
/// but non-zero probability for an arbitrary large number of
/// arrivals to occur in any interval. The  [ApproximatedPoisson]
/// process implements the [ArrivalBound] interface with a
/// configurable residual probability of excessive arrivals.
///
/// The bound [number_arrivals][ApproximatedPoisson::number_arrivals]
/// ensures that the claimed number of job arrivals are not exceeded
/// with probability at least `1 - epsilon`.
///
/// Note: the implementation is intended to be simple, but not
/// necessarily fast, so it's best to convert it into an [arrival
/// curve][super::Curve] before use if performance is of interest.
#[derive(Copy, Clone, Debug)]
pub struct ApproximatedPoisson {
    /// The underlying Poisson process.
    poisson: Poisson,
    /// The acceptable probability of under-approximating the number
    /// of arrivals. Must be small but non-zero.
    epsilon: f64,
}

impl ApproximatedPoisson {
    /// Construct a new approximated Poisson arrival process with
    /// mean arrival rate `lambda` and under-approximation bound
    /// `epsilon`.
    pub fn new(lambda: f64, epsilon: f64) -> Self {
        ApproximatedPoisson {
            epsilon,
            poisson: Poisson { rate: lambda },
        }
    }
}

impl ArrivalBound for ApproximatedPoisson {
    /// Bound the number of jobs released in any interval of length `delta` with probability `1 - epsilon`.
    fn number_arrivals(&self, delta: Duration) -> usize {
        if delta.is_non_zero() {
            let mut cumulative_prob = 0.0;
            let mut njobs = 0;
            loop {
                cumulative_prob += self.poisson.arrival_probability(delta, njobs);
                if cumulative_prob + self.epsilon >= 1.0 {
                    break;
                }
                njobs += 1;
            }
            njobs
        } else {
            0
        }
    }

    fn clone_with_jitter(&self, jitter: Duration) -> Box<dyn ArrivalBound> {
        Box::new(Propagated::with_jitter(self, jitter))
    }
}