ouroboros-network
Safe HaskellNone
LanguageHaskell2010

Ouroboros.Network.BlockFetch.DeltaQ

Synopsis

Documentation

data GSV Source #

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.

Instances

Instances details
Semigroup GSV Source #

GSVs are semi-groups by convolution on the three individual components.

Instance details

Defined in Ouroboros.Network.DeltaQ

Methods

(<>) :: GSV -> GSV -> GSV #

sconcat :: NonEmpty GSV -> GSV #

stimes :: Integral b => b -> GSV -> GSV #

Show GSV Source # 
Instance details

Defined in Ouroboros.Network.DeltaQ

Methods

showsPrec :: Int -> GSV -> ShowS #

show :: GSV -> String #

showList :: [GSV] -> ShowS #

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

Instances details
Num n => Semigroup (Distribution n) Source #

Distributions are semi-groups by convolution.

Instance details

Defined in Ouroboros.Network.DeltaQ

data DeltaQ Source #

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.

Instances

Instances details
Semigroup DeltaQ Source #

DeltaQ distributions (as independent random variables) are semi-groups by convolution.

Instance details

Defined in Ouroboros.Network.DeltaQ

data PeerGSV Source #

The GSV for both directions with a peer, outbound and inbound.

Constructors

PeerGSV 

Instances

Instances details
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 &#x1D6FC (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 &#x1D6FC), instead we calculate, given the interval from when the last sample was taken, the &#x1D6FC needed to ensure that the old value has sufficiently decayed.

The exact calculation 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 (reasonably arbitrarily) 1000s as the time constant, it is unclear if this should be a configuration variable or not. Note that this semigroup is non-commutative. The new value must come first.

Instance details

Defined in Ouroboros.Network.DeltaQ

Show PeerGSV Source # 
Instance details

Defined in Ouroboros.Network.DeltaQ

data SizeInBytes #

Instances

Instances details
NFData SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Methods

rnf :: SizeInBytes -> () #

Monoid SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Semigroup SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Enum SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Generic SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Associated Types

type Rep SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

type Rep SizeInBytes = D1 ('MetaData "SizeInBytes" "Ouroboros.Network.SizeInBytes" "ouroboros-network-api-0.9.0.1-inplace" 'True) (C1 ('MetaCons "SizeInBytes" 'PrefixI 'True) (S1 ('MetaSel ('Just "getSizeInBytes") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Word32)))
Num SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Integral SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Real SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Show SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Eq SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Ord SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

BoundedMeasure SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

Measure SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

NoThunks SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

type Rep SizeInBytes 
Instance details

Defined in Ouroboros.Network.SizeInBytes

type Rep SizeInBytes = D1 ('MetaData "SizeInBytes" "Ouroboros.Network.SizeInBytes" "ouroboros-network-api-0.9.0.1-inplace" 'True) (C1 ('MetaCons "SizeInBytes" 'PrefixI 'True) (S1 ('MetaSel ('Just "getSizeInBytes") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Word32)))

estimateResponseDeadlineProbability :: PeerGSV -> SizeInBytes -> SizeInBytes -> DiffTime -> Double Source #

Given the PeerGSV, the bytes already in flight and the size of new blocks to download, estimate the probability of the download completing within the deadline.

This is an appropriate estimator to use in a situation where meeting a known deadline is the goal.

estimateExpectedResponseDuration Source #

Arguments

:: PeerGSV 
-> SizeInBytes

Request size

-> SizeInBytes

Expected response size

-> DiffTime 

Given the PeerGSV, the bytes already in flight and the size of new blocks to download, estimate the expected (mean) time to complete the download.

This is an appropriate estimator to use when trying to minimising the expected overall download time case in the long run (rather than optimising for the worst case in the short term).

comparePeerGSV :: (Hashable peer, Ord peer) => Set peer -> Int -> (PeerGSV, peer) -> (PeerGSV, peer) -> Ordering Source #

Order two PeerGSVs based on g. Incase the g values are within +/- 5% of each other peer is used as a tie breaker. The salt is unique per running node, which avoids all nodes prefering the same peer in case of a tie.

comparePeerGSV' :: (Hashable peer, Ord peer) => Int -> (PeerGSV, peer) -> (PeerGSV, peer) -> Ordering Source #

Order two PeerGSVs based on g. Like comparePeerGSV but doesn't take active status into account