{-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE NamedFieldPuns #-} {-# LANGUAGE StandaloneDeriving #-} -- | 𝚫Q representation and primitives. -- -- See also <https://www.ofcom.org.uk/__data/assets/pdf_file/0024/71682/traffic-management-detection.pdf> -- appendix A. -- module Ouroboros.Network.DeltaQ ( -- * DeltaQ DeltaQ (..) , deltaqQ99thPercentile , deltaqQ50thPercentile , deltaqProbabilityMassBeforeDeadline -- * GSV , GSV (..) , SizeInBytes , ballisticGSV , gsvLeadingEdgeArrive , gsvTrailingEdgeDepart , gsvTrailingEdgeArrive -- * Distribution -- | Needed to construct a 'DeltaQ' or 'GSV' , Distribution , degenerateDistribution -- * Bi-directional GSV. -- | 'gsvRequestResponseDuration' is provided as an example of the 'GSV' -- and 'DeltaQ' primitives. , PeerGSV (..) , gsvRequestResponseDuration , defaultGSV , fromSample ) where import Control.Monad.Class.MonadTime (DiffTime, Time (..), diffTime) import Data.Word (Word32) -- -- Sketch of API for 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. -- newtype DeltaQ = DeltaQ (Distribution DiffTime) -- | DeltaQ distributions (as independent random variables) are semi-groups -- by convolution. -- deriving instance Semigroup DeltaQ -- | 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. -- deltaqQ99thPercentile :: DeltaQ -> DiffTime deltaqQ99thPercentile :: DeltaQ -> DiffTime deltaqQ99thPercentile (DeltaQ (DegenerateDistribution DiffTime t)) = DiffTime t deltaqQ50thPercentile :: DeltaQ -> DiffTime deltaqQ50thPercentile :: DeltaQ -> DiffTime deltaqQ50thPercentile (DeltaQ (DegenerateDistribution DiffTime t)) = DiffTime t -- | 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. -- deltaqProbabilityMassBeforeDeadline :: DiffTime -> DeltaQ -> Double deltaqProbabilityMassBeforeDeadline :: DiffTime -> DeltaQ -> Double deltaqProbabilityMassBeforeDeadline DiffTime deadline (DeltaQ (DegenerateDistribution DiffTime t)) | DiffTime t DiffTime -> DiffTime -> Bool forall a. Ord a => a -> a -> Bool < DiffTime deadline = Double 1 | Bool otherwise = Double 0 -- -- Sketch of API for Distribution -- -- | 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. -- data Distribution n = DegenerateDistribution n -- | Distributions are semi-groups by convolution. -- instance Num n => Semigroup (Distribution n) where <> :: Distribution n -> Distribution n -> Distribution n (<>) = Distribution n -> Distribution n -> Distribution n forall n. Num n => Distribution n -> Distribution n -> Distribution n convolveDistribution -- | Make a degenerate distribution. -- -- <https://en.wikipedia.org/wiki/Degenerate_distribution> -- degenerateDistribution :: n -> Distribution n degenerateDistribution :: n -> Distribution n degenerateDistribution = n -> Distribution n forall n. n -> Distribution n DegenerateDistribution -- | The convolution of two (improper) probability distributions. -- -- <https://en.wikipedia.org/wiki/Convolution> -- -- For now the implementation only covers degenerate distributions. -- convolveDistribution :: Num n => Distribution n -> Distribution n -> Distribution n convolveDistribution :: Distribution n -> Distribution n -> Distribution n convolveDistribution (DegenerateDistribution n d) (DegenerateDistribution n d') = n -> Distribution n forall n. n -> Distribution n DegenerateDistribution (n dn -> n -> n forall a. Num a => a -> a -> a +n d') -- | Shift a distribution by a constant. This is equivalent to convolution -- with a degenerate distribution. -- -- > shiftDistribution n d = degenerateDistribution n `convolveDistribution` d -- shiftDistribution :: Num n => n -> Distribution n -> Distribution n shiftDistribution :: n -> Distribution n -> Distribution n shiftDistribution n n (DegenerateDistribution n d) = n -> Distribution n forall n. n -> Distribution n DegenerateDistribution (n nn -> n -> n forall a. Num a => a -> a -> a +n d) -- -- Sketch of API for 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 zero-sized 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. -- data GSV = GSV !DiffTime -- G as seconds !(SizeInBytes -> DiffTime) -- S as seconds for size !(Distribution DiffTime) -- V as distribution -- | GSVs are semi-groups by convolution on the three individual components. -- instance Semigroup GSV where GSV DiffTime g1 SizeInBytes -> DiffTime s1 Distribution DiffTime v1 <> :: GSV -> GSV -> GSV <> GSV DiffTime g2 SizeInBytes -> DiffTime s2 Distribution DiffTime v2 = DiffTime -> (SizeInBytes -> DiffTime) -> Distribution DiffTime -> GSV GSV (DiffTime g1DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a +DiffTime g2) (\SizeInBytes sz -> SizeInBytes -> DiffTime s1 SizeInBytes sz DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a + SizeInBytes -> DiffTime s2 SizeInBytes sz) (Distribution DiffTime v1 Distribution DiffTime -> Distribution DiffTime -> Distribution DiffTime forall a. Semigroup a => a -> a -> a <> Distribution DiffTime v2) instance Show GSV where show :: GSV -> String show (GSV DiffTime g SizeInBytes -> DiffTime s (DegenerateDistribution DiffTime v)) = String "GSV g " String -> ShowS forall a. [a] -> [a] -> [a] ++ DiffTime -> String forall a. Show a => a -> String show DiffTime g String -> ShowS forall a. [a] -> [a] -> [a] ++ String " s " String -> ShowS forall a. [a] -> [a] -> [a] ++ DiffTime -> String forall a. Show a => a -> String show (SizeInBytes -> DiffTime s SizeInBytes 1) String -> ShowS forall a. [a] -> [a] -> [a] ++ String " v " String -> ShowS forall a. [a] -> [a] -> [a] ++ DiffTime -> String forall a. Show a => a -> String show DiffTime v -- | The case of ballistic packet transmission where the /S/ is directly -- proportional to the packet size. -- ballisticGSV :: DiffTime -- ^ /G/ -> DiffTime -- ^ /S/ as time per byte. -> Distribution DiffTime -- ^ /V/ distribution -> GSV ballisticGSV :: DiffTime -> DiffTime -> Distribution DiffTime -> GSV ballisticGSV DiffTime g DiffTime s Distribution DiffTime v = DiffTime -> (SizeInBytes -> DiffTime) -> Distribution DiffTime -> GSV GSV DiffTime g (\SizeInBytes sz -> DiffTime s DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a * SizeInBytes -> DiffTime forall a b. (Integral a, Num b) => a -> b fromIntegral SizeInBytes sz) Distribution DiffTime v -- -- Basic calculations based on GSV -- type SizeInBytes = Word32 -- | 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. -- gsvLeadingEdgeArrive :: GSV -> DeltaQ -- | 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. -- gsvTrailingEdgeDepart :: GSV -> SizeInBytes -> DeltaQ -- | 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. -- gsvTrailingEdgeArrive :: GSV -> SizeInBytes -> DeltaQ gsvLeadingEdgeArrive :: GSV -> DeltaQ gsvLeadingEdgeArrive (GSV DiffTime g SizeInBytes -> DiffTime _s Distribution DiffTime v) = Distribution DiffTime -> DeltaQ DeltaQ (DiffTime -> Distribution DiffTime -> Distribution DiffTime forall n. Num n => n -> Distribution n -> Distribution n shiftDistribution DiffTime g Distribution DiffTime v) -- dubious for anything other than ballistic gsvTrailingEdgeDepart :: GSV -> SizeInBytes -> DeltaQ gsvTrailingEdgeDepart (GSV DiffTime _g SizeInBytes -> DiffTime s Distribution DiffTime v) SizeInBytes bytes = Distribution DiffTime -> DeltaQ DeltaQ (DiffTime -> Distribution DiffTime -> Distribution DiffTime forall n. Num n => n -> Distribution n -> Distribution n shiftDistribution (SizeInBytes -> DiffTime s SizeInBytes bytes) Distribution DiffTime v) gsvTrailingEdgeArrive :: GSV -> SizeInBytes -> DeltaQ gsvTrailingEdgeArrive (GSV DiffTime g SizeInBytes -> DiffTime s Distribution DiffTime v) SizeInBytes bytes = Distribution DiffTime -> DeltaQ DeltaQ (DiffTime -> Distribution DiffTime -> Distribution DiffTime forall n. Num n => n -> Distribution n -> Distribution n shiftDistribution (DiffTime g DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a + SizeInBytes -> DiffTime s SizeInBytes bytes) Distribution DiffTime v) -- -- Derived calculations for bi-directional GSV -- -- | The 'GSV' for both directions with a peer, outbound and inbound. -- data PeerGSV = PeerGSV { PeerGSV -> Time sampleTime :: !Time, PeerGSV -> GSV outboundGSV :: !GSV, PeerGSV -> GSV inboundGSV :: !GSV } deriving Int -> PeerGSV -> ShowS [PeerGSV] -> ShowS PeerGSV -> String (Int -> PeerGSV -> ShowS) -> (PeerGSV -> String) -> ([PeerGSV] -> ShowS) -> Show PeerGSV forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [PeerGSV] -> ShowS $cshowList :: [PeerGSV] -> ShowS show :: PeerGSV -> String $cshow :: PeerGSV -> String showsPrec :: Int -> PeerGSV -> ShowS $cshowsPrec :: Int -> PeerGSV -> ShowS Show -- | 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 non-commutative. The new value must come first. instance Semigroup PeerGSV where <> :: PeerGSV -> PeerGSV -> PeerGSV (<>) PeerGSV a PeerGSV b = let timeConstant :: DiffTime timeConstant = DiffTime 1000 :: DiffTime sampleInterval :: DiffTime sampleInterval = PeerGSV -> Time sampleTime PeerGSV a Time -> Time -> DiffTime `diffTime` PeerGSV -> Time sampleTime PeerGSV b alpha :: DiffTime alpha = (DiffTime sampleInterval DiffTime -> DiffTime -> DiffTime forall a. Fractional a => a -> a -> a / DiffTime timeConstant) DiffTime -> DiffTime -> DiffTime forall a. Ord a => a -> a -> a `min` DiffTime 1 updateG :: GSV -> GSV -> GSV updateG (GSV DiffTime g1 SizeInBytes -> DiffTime s Distribution DiffTime v) (GSV DiffTime g0 SizeInBytes -> DiffTime _ Distribution DiffTime _) = DiffTime -> (SizeInBytes -> DiffTime) -> Distribution DiffTime -> GSV GSV (DiffTime g0 DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a + DiffTime alpha DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a * (DiffTime g1 DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a - DiffTime g0)) SizeInBytes -> DiffTime s Distribution DiffTime v in PeerGSV :: Time -> GSV -> GSV -> PeerGSV PeerGSV { sampleTime :: Time sampleTime = PeerGSV -> Time sampleTime PeerGSV a , outboundGSV :: GSV outboundGSV = GSV -> GSV -> GSV updateG (PeerGSV -> GSV outboundGSV PeerGSV a) (PeerGSV -> GSV outboundGSV PeerGSV b) , inboundGSV :: GSV inboundGSV = GSV -> GSV -> GSV updateG (PeerGSV -> GSV inboundGSV PeerGSV a) (PeerGSV -> GSV inboundGSV PeerGSV b) } -- | 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 -- gsvRequestResponseDuration :: PeerGSV -> SizeInBytes -- ^ Request size -> SizeInBytes -- ^ Expected response size -> DiffTime gsvRequestResponseDuration :: PeerGSV -> SizeInBytes -> SizeInBytes -> DiffTime gsvRequestResponseDuration PeerGSV{GSV outboundGSV :: GSV outboundGSV :: PeerGSV -> GSV outboundGSV, GSV inboundGSV :: GSV inboundGSV :: PeerGSV -> GSV inboundGSV} SizeInBytes reqSize SizeInBytes respSize = DeltaQ -> DiffTime deltaqQ99thPercentile (DeltaQ -> DiffTime) -> DeltaQ -> DiffTime forall a b. (a -> b) -> a -> b $ GSV -> SizeInBytes -> DeltaQ gsvTrailingEdgeArrive GSV outboundGSV SizeInBytes reqSize DeltaQ -> DeltaQ -> DeltaQ forall a. Semigroup a => a -> a -> a <> GSV -> SizeInBytes -> DeltaQ gsvTrailingEdgeArrive GSV inboundGSV SizeInBytes respSize defaultGSV :: PeerGSV defaultGSV :: PeerGSV defaultGSV = PeerGSV :: Time -> GSV -> GSV -> PeerGSV PeerGSV {Time sampleTime :: Time sampleTime :: Time sampleTime, GSV outboundGSV :: GSV outboundGSV :: GSV outboundGSV, GSV inboundGSV :: GSV inboundGSV :: GSV inboundGSV } where default_g :: DiffTime default_g = DiffTime 500e-3 -- Old hardcoded default value. Only available value when running without KeepAlive. default_s :: DiffTime default_s = DiffTime 2e-6 -- 4Mbps. inboundGSV :: GSV inboundGSV = DiffTime -> DiffTime -> Distribution DiffTime -> GSV ballisticGSV DiffTime default_g DiffTime default_s (DiffTime -> Distribution DiffTime forall n. n -> Distribution n degenerateDistribution DiffTime 0) outboundGSV :: GSV outboundGSV = GSV inboundGSV sampleTime :: Time sampleTime = DiffTime -> Time Time DiffTime 0 fromSample :: Time -> Time -> SizeInBytes -> PeerGSV fromSample :: Time -> Time -> SizeInBytes -> PeerGSV fromSample t :: Time t@(Time DiffTime start) (Time DiffTime end) SizeInBytes _size = PeerGSV :: Time -> GSV -> GSV -> PeerGSV PeerGSV {Time sampleTime :: Time sampleTime :: Time sampleTime, GSV outboundGSV :: GSV outboundGSV :: GSV outboundGSV, GSV inboundGSV :: GSV inboundGSV :: GSV inboundGSV } where g :: DiffTime g = (DiffTime end DiffTime -> DiffTime -> DiffTime forall a. Num a => a -> a -> a - DiffTime start) DiffTime -> DiffTime -> DiffTime forall a. Fractional a => a -> a -> a / DiffTime 2 sampleTime :: Time sampleTime = Time t inboundGSV :: GSV inboundGSV = DiffTime -> DiffTime -> Distribution DiffTime -> GSV ballisticGSV DiffTime g DiffTime 2e-6 (DiffTime -> Distribution DiffTime forall n. n -> Distribution n degenerateDistribution DiffTime 0) outboundGSV :: GSV outboundGSV = GSV inboundGSV