Safe Haskell  SafeInferred 

Language  Haskell2010 
𝚫Q representation and primitives.
See also https://www.ofcom.org.uk/__data/assets/pdf_file/0024/71682/trafficmanagementdetection.pdf appendix A.
Synopsis
 newtype DeltaQ = DeltaQ (Distribution DiffTime)
 deltaqQ99thPercentile ∷ DeltaQ → DiffTime
 deltaqQ50thPercentile ∷ DeltaQ → DiffTime
 deltaqProbabilityMassBeforeDeadline ∷ DiffTime → DeltaQ → Double
 data GSV = GSV !DiffTime !(SizeInBytes → DiffTime) !(Distribution DiffTime)
 newtype SizeInBytes = SizeInBytes {}
 ballisticGSV ∷ DiffTime → DiffTime → Distribution DiffTime → GSV
 gsvLeadingEdgeArrive ∷ GSV → DeltaQ
 gsvTrailingEdgeDepart ∷ GSV → SizeInBytes → DeltaQ
 gsvTrailingEdgeArrive ∷ GSV → SizeInBytes → DeltaQ
 data Distribution n
 degenerateDistribution ∷ n → Distribution n
 data PeerGSV = PeerGSV {
 sampleTime ∷ !Time
 outboundGSV ∷ !GSV
 inboundGSV ∷ !GSV
 gsvRequestResponseDuration ∷ PeerGSV → SizeInBytes → SizeInBytes → DiffTime
 defaultGSV ∷ PeerGSV
 fromSample ∷ Time → Time → SizeInBytes → PeerGSV
DeltaQ
A "𝚫Q" is a probability distribution on the duration between two events. It is an "improper" probability distribution in that it may not integrate to 1. The "missing" probability mass represents failure. This allows both timing and failure to be represented in one mathematical object.
In the case of networks a 𝚫Q can be used for example distributions such as the time for a leading edge or trailing edge of a packet to traverse a network (or failing to do so), and many others besides.
deltaqQ99thPercentile ∷ DeltaQ → DiffTime Source #
The point in time in the distribution for which 99% of the probability mass is before that time.
This tells us how long we would have to wait to have a 99% chance of the end event having happened. Of course 99% is somewhat arbitrary and other points in the distribution could be of interest.
TODO: this needs to be specified better for improper distributions.
deltaqProbabilityMassBeforeDeadline ∷ DiffTime → DeltaQ → Double Source #
This is another way of looking at a 𝚫Q distribution. Instead of giving a fraction of the probability mass (like 99%) and asking how long we would have to wait, we can say how long we are prepared to wait and ask what fraction of the probability mass is before that time.
So this tells us the chance of the end event happening within the time we are prepared to wait. This is useful for evaluating different options for which has the greatest probability of success within a deadline.
GSV
A "GSV" corresponds to a 𝚫Q that is a function of the size of a data
unit to be transmitted over a network. That is, it gives the 𝚫Q of the
transmission time for different sizes of data in SizeInBytes
.
The 𝚫Q is broken out into three separate 𝚫Q distributions, 𝚫Q∣G, 𝚫Q∣S and 𝚫Q∣V, with the overall 𝚫Q being the convolution of the three components. The G and S components captures the structural aspects of networks, while the V captures the variable aspects:
 G
 the geographical component of network delay. This is the minimum time to transmit a hypothetical zerosized data unit. This component of the distribution does not depend on the data unit size. It is a degenerate distribution, taking only one value.
 S
 the serialisation component of network delay. This is time to serialise a data unit as it is being transmitted. This is of course a function of the data unit size. For each size it is a degenerate distribution, taking only one value.
 V
 the variable aspect of network delay. This captures the variability in network delay due to issues such as congestion. This does not depend on the data unit size, and is not a degenerate disruption.
For ballistic transmission of packets, S is typically directly proportional to the size. Thus the combination of G and S is simply a linear function of the size.
GSV !DiffTime !(SizeInBytes → DiffTime) !(Distribution DiffTime) 
newtype SizeInBytes Source #
Instances
∷ DiffTime  G 
→ DiffTime  S as time per byte. 
→ Distribution DiffTime  V distribution 
→ GSV 
The case of ballistic packet transmission where the S is directly proportional to the packet size.
gsvLeadingEdgeArrive ∷ GSV → DeltaQ Source #
The 𝚫Q for when the leading edge of a transmission unit arrives at the destination. This is just the convolution of the G and V components.
gsvTrailingEdgeDepart ∷ GSV → SizeInBytes → DeltaQ Source #
The 𝚫Q for when the trailing edge of a transmission unit departs the sending end. This is just the convolution of the S and V components.
Since it involves S then it depends on the SizeInBytes
of the
transmission unit.
gsvTrailingEdgeArrive ∷ GSV → SizeInBytes → DeltaQ Source #
The 𝚫Q for when the trailing edge of a transmission unit arrives at the destination. This is the convolution of the G, S and V components.
Since it involves S then it depends on the SizeInBytes
of the
transmission unit.
Distribution
data Distribution n Source #
An improper probability distribution over some underlying type (such as time durations).
The current representation only covers the case of degenerate distributions, that take a single value with probability 1. This is just a proof of concept to illustrate the API.
Instances
Num n ⇒ Semigroup (Distribution n) Source #  Distributions are semigroups by convolution. 
Defined in Ouroboros.Network.DeltaQ (<>) ∷ Distribution n → Distribution n → Distribution n Source # sconcat ∷ NonEmpty (Distribution n) → Distribution n Source # stimes ∷ Integral b ⇒ b → Distribution n → Distribution n Source # 
degenerateDistribution ∷ n → Distribution n Source #
Make a degenerate distribution.
Bidirectional GSV.
gsvRequestResponseDuration
is provided as an example of the GSV
and DeltaQ
primitives.
The GSV
for both directions with a peer, outbound and inbound.
PeerGSV  

Instances
Semigroup PeerGSV Source #  The current tracking model is based on an EWMA (https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average). Typically implementations of EWMA assume a regular update, but EWMA is based on Exponential Smoothing (https://en.wikipedia.org/wiki/Exponential_smoothing). Such smoothing has a time constant, which captures the time for a unit impulse to decay to 1  1/e (~ 63.2%), the 𝛼 (smoothing factor) is a function of relative frequency of the sample interval and this time constant. The approach being taken here is one that does not assume a fixed sample interval (and hence a fixed 𝛼), instead we calculate, given the interval from when the last sample was taken, the 𝛼 needed to ensure that the old value has sufficiently decayed. The exact calcuation involves exponentiation, however where the number of samples within the time constant is sufficiently large a simple ratio of the sample's interval over the time constant will suffice. The relative error of this numerical approximation is, for our use case, small. Eg 1/50 (20s between samples with a 1000s time constant) has a relative error of 1%. The expected typical range of this relative error is between 5% (ratio of 1/10), to 0.5% (1/100). Given the inherent measurement noise in this measurement, the use of the approximation is well justified. We choose (reaonably aribtarily) 1000s as the time constant, it is unclear if this should be a configuration variable or not. Note that this semigroup is is noncommutative. The new value must come first. 
Show PeerGSV Source #  
gsvRequestResponseDuration Source #
∷ PeerGSV  
→ SizeInBytes  Request size 
→ SizeInBytes  Expected response size 
→ DiffTime 
This is an example derived operation using the other GSV
and DeltaQ
primitives.
It calculates the 𝚫Q for the time to send a request of a certain size and receive a reply of an expected size. It then takes the 99% percentile as an approximation of the maximum time we might be prepared to wait.
deltaqQ99thPercentile $ gsvTrailingEdgeArrive outboundGSV reqSize <> gsvTrailingEdgeArrive inboundGSV respSize
This is not realistic in that it omits processing time, but that could be
added as yet another DeltaQ
value, if there's any estimate for it:
deltaqQ99thPercentile $ gsvTrailingEdgeArrive outboundGSV reqSize <> gsvTrailingEdgeArrive inboundGSV respSize <> processingDeltaQ
fromSample ∷ Time → Time → SizeInBytes → PeerGSV Source #