gaussian

README

高斯分布函数

主要用于:
在已知网络延迟的样本下，判定CD延迟欺骗的概率

3σ原则：

1. P（μ-σ<X≤μ+σ）= 68.3%
2. P（μ-2σ<X≤μ+2σ）= 95.4%
3. P（μ-3σ<X≤μ+3σ）= 99.7%

一个极端的例子：

一个来自火星的玩家Mars，和一个来自局域网的玩家Lan。
Mars到达服务器的延迟为1年， Lan到达服务的时间无限接近0. 两者都已经登陆服务器。
两者都执行了一个建造序列，A->B，并且，B的建造，必须要在A建造完成之后进行, A的建造时间是30s.

Mars/Lan分别间隔30s发送了两个数据包[A, B]

理论上，我们只需要检测两者的时间间隔是否是30s就可以判定建造的合理性。 即:

gap(B-A) == 30s

但是网络传输并不一定是一种稳定的延迟， 也许A会晚一秒到达，B早一秒到达。A,B的时间间隔为28s，导致判定失效。
并且，在纯异步的环境下，Mars/Lan的操作，都应该以本地时间为准。

为了解决这样的问题，我们在每个数据包中，都带上一个当前客户端的发送时间戳。好，这样似乎解决问题了，判断:

timestamp(B-A) >= 30s

timestamp差是否是30s以上，就ok.

但是，主角Lan登场。 他发了两个连续(间隔为0)的数据包分别宣称， 我一年之前就把A建造完成了， 我一年-30s之前就把B建造完成了。
OK，无法避免的欺诈发生了，纯粹靠数据包自己的timestamp判断一定是不行的，因为外界是邪恶的。
对，你发现了， 两者混合，既判定两个数据包真正先后到达的时间gap，又判定宣称的timestamp，就能解决问题。

例如:

timestamp(B-A) == gap(B-A)

可是新的问题又来了，怎么判断'=='， 因为latency， gap并不是绝对的啊。我们只能判定约等于，即:

timestamp(B-A) ~= gap(B-A)

方法：

Abs(timestamp(B-A) - gap(B-A)) < N

如何确定N的值呢，最简单方法是，固定值，例如设定N=5, 但是，我更倾向于用概率方法来做，因为 :
高延迟的，必然有高的误差率， 这个误差率，可以用概率分布描述。

我们统计若干个sample，例如32个64个sample。每个sample取值为:

sample := { timestamp(B-A) - gap(B-A),  A,B是两个连续的数据包 }  

高斯分布可以计算出误差的σ，根据高斯分布的3σ原则。误差 > 2σ 的都是小概率事件，对于新的一个观察(observe) 即可判定。

方法：

Abs(Observe - μ) < 2σ

Documentation

Index

• Constants
• type Dist
  • func NewDist(num_samples int) *Dist
  • func (dist *Dist) Add(x int)
  • func (dist *Dist) IsSampleOk() bool
  • func (dist *Dist) P(x int) float64

Constants

const (
	SQRT2PI = float64(2.50662827463100050241576528481)
)

Types

type Dist

type Dist struct {
	Samples []int
	Ptr     int
	N       int
	Sigma   float64
	Mean    float64
}

func NewDist

func NewDist(num_samples int) *Dist

func (*Dist) Add

func (dist *Dist) Add(x int)

func (*Dist) IsSampleOk

func (dist *Dist) IsSampleOk() bool

func (*Dist) P

func (dist *Dist) P(x int) float64