网络可用性，扩展性，性能的统计本质-171主机测评

网络是统计的，是不确定的，这话天天说，就不在乎再说一次，就着前文为什么高速网络更怕抖动接着说。从独立随机流叠加定理开始：

我的解释是广义中心极限定理在计数过程上的特例，似乎有点泊松分布随

\\lambda

$λ$ 增加趋向正态分布的意思，要不是泊松分布左边有一堵

x=0

$x = 0$ 的墙，它事实上就是正态分布，增大

\\lambda

$λ$ 只是把整个图形右移，泊松分布左边墙后面的尾巴就露出来了。

本文先说三个同构的流叠加场景，并分析对应结论下的实际行为和启示：

泊松极限，即总均值 $\\lambda λ 恒定的稀疏流叠加，总带宽一定；$
大数定理，广义
经典
上述三大统计律下的实际网络流量行为；

泊松极限说的是，给定有限总到达率，把总流量拆成

$n$ 条独立同分布，稀疏的子流，当流数量

→

∞

n\\to\\infty

$n \to \infty$ ，每条子流到达率

→

\\to 0

$\to 0$ ，聚合后的整体到达过程收敛为泊松过程。

总到达率

total

\\lambda_{\\text{total}}

$λ_{total}$ 恒定，拆为

$n$ 条独立子流，单流到达率

total

\\lambda_n = \\dfrac{\\lambda_{\\text{total}}}{n}

$λ_{n} = \frac{λ _{total}}{n}$ ，当

↑

→

n\\uparrow,\\lambda_n \\to 0

$n ↑, λ_{n} \to 0$ ，每条流平均很久才发一个报文，就是稀疏流。

形象地看，在聚合之前，单条流突发极强，扎堆发送和长时间静默交替，此时其

≫

C_a\\gg1

$C_{a} ≫ 1$ ，拆分后聚合，扎堆被分散，每一条流发包的平均间隔延长，任意小区间，同时有两个及以上子流发包的概率极低，绝大多数情况

$1$ 个或

$0$ 个。这种大量独立且稀有事件叠加的行为，即泊松过程的典型。

抛

$n$ 枚独立硬币，每枚正面概率

→

p\\to0

$p \to 0$ ，总期望

np=\\lambda

$n p = λ$ 固定，正面出现次数趋近泊松分布，网络流叠加和它同一种数学结构。

若用数学描述，也不麻烦。把时间切为极小的时隙

\\Delta t

$Δ t$ ，单个时隙内，总共有报文到达的数量，服从二项分布

(

)

B(n,\\,p_n)

$B (n, p_{n})$ ：

(

)

(

)

(

−

)

−

P(k) = \\binom{n}{k}\\,p_n^k\\,(1-p_n)^{n-k}

$P (k) = (k n) p_{n}^{k} (1 - p_{n})^{n - k}$

总平均到达数固定的约束下：

常数

\\lambda = n\\,p_n =\\text{常数}

$λ = n p_{n} = 常数$

即

p_n = \\dfrac{\\lambda}{n}

$p_{n} = \frac{λ}{n}$ ，满足当 $n\\to\\infty $ 时，

→

p_n\\to0

$p_{n} \to 0$ .

代入二项分布并求极限：

lim

⁡

→

∞

(

)

(

)

(

−

)

−

\\begin{aligned} \\lim_{n\\to\\infty} \\binom{n}{k}\\left(\\dfrac{\\lambda}{n}\\right)^k \\left(1-\\dfrac{\\lambda}{n}\\right)^{n-k} &= \\dfrac{\\lambda^k e^{-\\lambda}}{k!} \\end{aligned}

$n \to \infty lim (k n) (\frac{λ}{n})^{k} (1 - \frac{λ}{n})^{n - k} = \frac{λ ^{k} e ^{- λ}}{k !}$

看，右边正是泊松分布的概率质量函数：

(

)

−

P(N=k) = \\dfrac{\\lambda^k e^{-\\lambda}}{k!}

$P (N = k) = \frac{λ ^{k} e ^{- λ}}{k !}$

这就是独立随机流叠加定理的一般结论，

→

∞

→

常数

n\\to\\infty,\\ p_n\\to0,\\ np_n=\\text{常数}

$n \to \infty, p_{n} \to 0, n p_{n} = 常数$ 条件下，独立稀疏伯努利试验的叠加趋向泊松分布，即大量独立，稀疏的子流叠加，到达计数过程收敛为泊松过程。

泊松过程的到达间隔

$X$ 服从指数分布：

(

)

−

≥

f(x) = \\lambda e^{-\\lambda x},\\quad x\\ge 0

$f (x) = λ e^{- λ x}, x \geq 0$

指数分布矩性质，

[

]

(

)

(

)

\\text{E}[X] = \\dfrac{1}{\\lambda},\\quad \\mathrm{Var}(X) = \\left(\\dfrac{1}{\\lambda}\\right)^2

$E [X] = \frac{1}{λ}, Var (X) = (\frac{1}{λ})^{2}$

代入到达变异系数定义：

(

)

[

]

C_a = \\dfrac{\\sqrt{\\mathrm{Var}(X)}}{\\mathrm E[X]} = \\dfrac{\\dfrac{1}{\\lambda}}{\\dfrac{1}{\\lambda}}=1

$C_{a} = \frac{Var ( X )}{E [ X ]}$

=λ1λ1=1

所以趋向于泊松过程的聚合流，

→

{C_a \\to 1}

$C_{a} \to 1$ 。

这就是骨干网，移动通信基站，小区宽带的设计依据，将大量独立稀疏用户流聚合，流量突发会被自然抹平，最终趋近平稳泊松流。

接入用户数越多，整体流量抖动越稳定，只要

\\rho

$ρ$ 不过大，链路可以跑高利用率仍保持低时延：

⋅

[

]

(

−

)

⋅

(

)

→

≈

⋅

[

]

(

−

)

W_q=\\dfrac{\\rho\\cdot\\text{E}[S]}{2(1-\\rho)}\\cdot(C_a^2+C_s^2)\\to W_q\\approx\\dfrac{\\rho\\cdot\\text{E}[S]}{2(1-\\rho)}

$W_{q} = \frac{ρ \cdot E [ S ]}{2 ( 1 - ρ )} \cdot (C_{a}^{2} + C_{s}^{2}) \to W_{q} \approx \frac{ρ \cdot E [ S ]}{2 ( 1 - ρ )}$

但随着总负载

\\lambda

$λ$ 增加，

\\rho

$ρ$ 增至过大，聚合后越发趋向对称钟形正态分布，钟形被压扁，排队时延

W_q

$W_{q}$ 趋向增加。

另一方面，若在长程依赖场景，存在流的集合同步突发，各流发包便不再是独立稀有事件，就不会收敛到泊松流，这在重大新闻播报，赛事等场景下是常态。

为解决以上两类统计偏离问题，就要触发拥塞控制，既要确保足够的带宽，又要确保公平性，这就

buffer

\\text{buffer}

$buffer$ 的主场了。

本文第二个场景，大数定律下的广义

CLT

\\text{CLT}

$CLT$ 极限，buffer 一定下，

BDP

\\text{BDP}

$BDP$ 总量固定，单流尺度随

\\dfrac{1}{n}

$\frac{1}{n}$ 收缩且不影响

BDP

\\text{BDP}

$BDP$ ，以经典

AIMD

\\text{AIMD}

$AIMD$ 为例，

0.5

\\alpha=1,\\beta=0.5

$α = 1, β = 0.5$ 建模。

设

$n$ 个独立同分布随机变量

∈

{

}

…

X_k \\in \\left\\{\\,\\dfrac{1}{n},\\;\\dfrac{2}{n}\\,\\right\\},\\quad k=1,2,\\dots,n

$X_{k} \in {\frac{1}{n}, \frac{2}{n}}, k = 1, 2, \dots, n$ ，假设两点等概率：

(

)

(

)

P\\left(X_k=\\tfrac1n\\right) =\\dfrac12,\\quad P\\left(X_k=\\tfrac2n\\right) =\\dfrac12

$P (X_{k} = \frac{1}{n}) = \frac{1}{2}, P (X_{k} = \frac{2}{n}) = \frac{1}{2}$

至于

{

}

\\left\\{\\,\\dfrac{1}{n},\\;\\dfrac{2}{n}\\,\\right\\}

${\frac{1}{n}, \frac{2}{n}}$ 区间的保证则来自

AIMD

\\text{AIMD}

$AIMD$ ，或者更普遍的端到端

capacity-seeking

\\text{capacity-seeking}

$capacity-seeking$ 算法。

$n$ 条流的叠加和：

⋯

S_n = X_1 + X_2 + \\dots + X_n

$S_{n} = X_{1} + X_{2} + \dots + X_{n}$

单个变量均值 :

[

]

⋅

\\mu =\\text{E}[X_k]=\\dfrac12\\cdot\\frac1n +\\dfrac12\\cdot\\dfrac2n=\\dfrac{3}{2n}

$μ = E [X_{k}] = \frac{1}{2} \cdot \frac{1}{n} + \frac{1}{2} \cdot \frac{2}{n} = \frac{3}{2 n}$

单个变量方差：

Var

(

)

[

]

−

(

[

]

)

\\text{Var}(X_k)=\\text{E}[X_k^2]-\\big(\\text{E}[X_k]\\big)^2=\\dfrac{1}{4n^2}

$Var (X_{k}) = E [X_{k}^{2}] - (E [X_{k}])^{2} = \frac{1}{4 n ^{2}}$

利用独立变量和性质：

[

]

⋅

Var

(

)

⋅

Var

(

)

\\text{E}[S_n]=n\\cdot\\mu,\\quad\\text{Var}(S_n)=n\\cdot \\text{Var}(X_k)

$E [S_{n}] = n \cdot μ, Var (S_{n}) = n \cdot Var (X_{k})$

故：

[

]

⋅

\\text{E}[S_n]=n\\cdot\\dfrac{3}{2n}={\\dfrac{3}{2}}

$E [S_{n}] = n \cdot \frac{3}{2 n} = \frac{3}{2}$

总均值恒为常数，不随

$n$ 变化，在

BDP

\\text{BDP}

$BDP$ 一定时，总负载真不变。

现在看方差，标准错：

(

)

⋅

\\mathrm{Var}(S_n)=n\\cdot\\dfrac{1}{4n^2}={\\dfrac{1}{4n}}

$Var (S_{n}) = n \cdot \frac{1}{4 n ^{2}} = \frac{1}{4 n}$

(

)

\\sigma_{S_n}=\\sqrt{\\mathrm{Var}(S_n)}=\\dfrac{1}{2\\sqrt{n}}

$σ_{S_{n}} = Var (S_{n})$

=2n

方差趋于

$0$ ，说明

$n$ 越大

\\bar X_n

$\overset{ˉ}{X}_{n}$ 越集中在期望附近，满足大数定律，平均结果随

$n$ 增大越来越稳定，波动消失，这就是我此前论证的，流越多，所需的

buffer

\\text{buffer}

$buffer$ 越少，参见为什么流越多，所需 buffer 越少，主宰 TCP AIMD 的中心极限定理。

OK，我已经展示了

→

C_a\\to 1

$C_{a} \to 1$ 的泊松极限，以及

buffer

→

\\text{buffer}\\to 0

$buffer \to 0$ 的大数定律，它们的承接关系在于，泊松极限确定了由

\\rho

$ρ$ 度量的吞吐和平均时延的固定关系，即

C_a=1

$C_{a} = 1$ 下的

W_q

$W_{q}$ 表达式，保证了资源的利用率和基础性能，而大数定律则以

BDP

\\text{BDP}

$BDP$ 约束了

W_q

$W_{q}$ 的界限，确保了网络的可用性。

一个直观的表示，泊松极限固定了网络最佳效用($\\dfrac{吞吐}{时延} $)时的波动，而大数定律消除了整体的波动，让统计变得确定，可观测。

若撤销泊松极限和

BDP

\\text{BDP}

$BDP$ 大数定律的约束，最后看中心极限定理的规模效应。

设每条子流自身均值，方差固定，与

$n$ 无关：

[

]

(

)

\\text{E}[X_i]=\\mu,\\ \\mathrm{Var}(X_i)=\\sigma_0^2,\\quad\\sigma_{X_i}=\\sigma_0

$E [X_{i}] = μ, Var (X_{i}) = σ_{0}^{2}, σ_{X_{i}} = σ_{0}$

$n$ 条流叠加，总负载随流数线性增大，

→

∞

n\\to\\infty

$n \to \infty$ 时

S_n

$S_{n}$ 依分布收敛为正态分布。叠加总和

S_n

$S_{n}$ :

[

]

(

)

\\text{E}[S_n] = n\\mu ,\\quad \\mathrm{Var}(S_n) = n\\sigma_0^2,\\quad \\sigma_{S_n} = \\sigma_0\\sqrt{n}

$E [S_{n}] = n μ, Var (S_{n}) = n σ_{0}^{2}, σ_{S_{n}} = σ_{0} n$

\\sigma_{S_n}

$σ_{S_{n}}$ 的

\\sqrt{n}

$n$

增长意味着规模效应，将抖动作为成本，则边际成本递减，这便是多路统计复用网络的第一个基础，它决定了网络的可扩展性，资源的扩展能撑得住负载的扩展，同时负载也能吃得下资源的扩展。

而加上泊松极限和大数定律的约束后，这便是一个归一化操作，在中心极限定理下，等效单流

\\displaystyle \\bar X_n=\\frac{S_n}{n}

$\overset{ˉ}{X}_{n} = \frac{S _{n}}{n}$ ，则：

[

]

(

)

\\text{E}[\\bar X_n]=\\mu,\\quad \\mathrm{Var}(\\bar X_n)=\\dfrac{\\sigma_0^2}{n},\\quad \\sigma_{\\bar X_n}=\\dfrac{\\sigma_0}{\\sqrt{n}}

$E [\overset{ˉ}{X}_{n}] = μ, Var (\overset{ˉ}{X}_{n}) = \frac{σ _{0}^{2}}{n}, σ_{\overset{ˉ}{X}_{n}} = n$

σ0

这与大数定律的结论同归，分摊到单流的抖动随

\\dfrac{1}{\\sqrt{n}}

$n$

1 减小。

以上这三大统计律勾勒了所有统计复用网络的基本轮廓，该轮廓下包括几乎所有的单独的网络架构和技术，GPON 广播选收，基站，骨干网，切片，flowlet，固定速率业务，… 以及剩下的让网络变复杂的技术。我们从来没有见过

buffer

\\text{buffer}=0

$buffer = 0$ 的配置，这是为什么。

所以说，它们三个是分组交换网络统计复用的基石，覆盖了流量叠加，突发平滑，

buffer

\\text{buffer}

$buffer$ 的核心。在这三大统计律起作用的理想的，平衡的范围内，运行着并不遵守模型假设的实际流量，正是它们决定着上述提到的让网络变复杂的技术：

网络流量符合随机游走模型；
网络流量呈现重尾分布特征；
网络流量的时间尺度自相似；

首先看随机游走模型描述的网络队列，定义关键统计量，漂移量：

[

单时隙净增量

]

[

到达数

]

−

[

服务数

]

\\delta = \\text{E}[\\text{单时隙净增量}] = \\mathrm{E}[\\text{到达数}]-\\mathrm {E}[\\text{服务数}]

$δ = E [单时隙净增量] = E [到达数] - E [服务数]$

由于拥塞控制(叠加 AQM Policing)会确保

平均到达率

平均服务率

→

\\rho=\\dfrac{平均到达率}{平均服务率}\\lt1\\to\\delta\\lt0

$ρ = \frac{平均到达率}{平均服务率} < 1 \to δ < 0$ ，队列长度是常返状态，高队列只是临时现象，不会无限堆积，拥塞只是暂时的，这和交通拥堵模型一致，可以经常堵，但不会一直堵，这意味着网络是持续可用的。

瞬时突发可以把队列打高，但只要

\\rho<1

$ρ < 1$ ，大数定律会把队列拉回，收敛回归。

再看重尾分布，帕累托分布是其最经典模型，这与取值越大，概率指数级快速衰减的理想建模的指数分布，泊松分布非常不同。

设随机变量

$X$ 描述流长度等特征，标准帕累托重尾分布由两个参数决定：

形状参数 $\\alpha\\gt0 α>0，Pareto 指数，控制尾部厚度；$
尺度参数 $x_m\\gt0 xm>0，随机变量的最小取值；$

其概率密度函数和累积分布函数分别为：

(

;

)

≥

f(x;\\alpha,x_m)=\\dfrac{αx_m^{\\alpha}}{x^{\\alpha+1}},\\quad x\\ge x_m

$f (x; α, x_{m}) = \frac{α x _{m}^{α}}{x ^{α + 1}}, x \geq x_{m}$

(

)

−

(

)

≥

F(x)=1−\\left(\\dfrac{x_m}{x}\\right)^{\\alpha},\\quad x\\ge x_m

$F (x) = 1 - (\frac{x _{m}}{x})^{α}, x \geq x_{m}$

右尾概率为：

(

≥

)

(

)

P(X\\ge x)=\\left(\\dfrac{x_m}{x}\\right)^\\alpha

$P (X \geq x) = (\frac{x _{m}}{x})^{α}$

这就是重尾，右尾衰减慢，其特征在于幂律衰减和尺度不变性，若

∼

Pareto

(

)

X\\sim\\text{Pareto}(\\alpha,x_m)

$X \sim Pareto (α, x_{m})$ ，则对任意

c\\gt0

$c > 0$ ，

∼

Pareto

(

)

cX\\sim\\text{Pareto}(\\alpha,cx_m)

$c X \sim Pareto (α, c x_{m})$ ，即改变度量单位不改变分布的形状，双对数坐标下

log

⁡

(

)

\\log⁡f(x)

$lo g f (x)$ 与

log

⁡

\\log⁡x

$lo g x$ 呈斜率为

−

(

)

−(\\alpha+1)

$- (α + 1)$ 的线性关系。

直观理解，虽然大流量，长流是小概率事件，但概率衰减很慢，极端大值频繁现身。

均值有限，但方差极大，极端突发频发，这似乎违背了理想建模的泊松极限，正如现实中根本见不到理想瘦网一样，现实中的重尾分布极大促进了 CDN，AQM，流量工程的发展演化，网络加入了智能而非理想化的裸哑，此乃原因。

重尾意味着少数热点对象被频繁访问，这就是 CDN 缓存的依据，但尾部对象极多，缓存命中率有上限，这又是 L1/L2 分级缓存的依据，CDN 成了一个复杂的技术。

理想模型下单一简单的 FIFO 将不再适合重尾流量，RED，ECN，CoDel 被设计出来主动管理相对频发的小概率重尾流量，网络转发节点因此变得复杂，不再裸哑。

由于重尾的存在，优先级队列需要更加灵活，可以 hash，识别并隔离频发的小概率重尾流量，以保证公平性，容量规划势必要做得更多，以适应实际均峰比很大的网络。

接下来看流量的自相似性叠加重尾。

理想泊松流量，小时间尺度的波动大于大时间尺度，泊松极限，大数定律让波动变得平滑，但发起流量的是长相关，自相似世界，则流量自相似，在

ms,s,m,h,d

$m s, s, m, h, d$ 等所有时间尺度上，流量的突发，波动基本一致。

Hurst 指数

$H$ 用于判断时间序列是随机游走还是具有长期记忆性，它量化了自相似程度，其核心关系为：

(

)

(

)

∼

⋅

\\dfrac{R(n)}{S(n)}\\sim c\\cdot n^H

$\frac{R ( n )}{S ( n )} \sim c \cdot n^{H}$

其中

(

)

R(n)

$R (n)$ 为极差，

(

)

S(n)

$S (n)$ 为标准差，

$n$ 为观测值个数，

$c$ 为常数。

0.5

H=0.5

$H = 0.5$ 时，时间序列为无记忆随机游走，对应泊松流的独立增量假设，

0.5

0.5\\lt H\\lt1

$0.5 < H < 1$ 时，存在长期正相关性，即过去的增量倾向于影响未来的增量方向，高峰之后更可能还是高峰，低谷之后更可能还是低谷。这正是网络流量自相似性的数学刻画。

网络流量分析实测的

$H$ 值通常在

0.7

～

0.94

0.7～0.94

$0.7 ～ 0.94$ ，远大于

0.5

$0.5$ ，说明流量具有显著的长程依赖，即突发不会在短时间尺度上被平滑掉，而是在多个时间尺度持续。

这直接解释了为什么泊松极限和大数定律在实际网络中失效，它们的前提假设是独立增量，而

0.5

H\\gt0.5

$H > 0.5$ 意味着独立性假设被违背。波动在所有时间尺度都抹不平，拥塞易持续，扩散，流量建模，容量规划难度上升，为适配理想与实际的不一致，网络

buffer

\\text{buffer}

$buffer$ 不得不变大，预留更大的突发余量。

为什么理论上的统计复用网络很确定，但现实里依然有卡顿，抖动，拥塞，这一切都源自于人和社会本身，没人能控制这些，也没有算法能，正如没人能控制人和社会本身一样，其根源就是统计不确定性，而在统计复用网络中，你又必须把确定性交给统计。

浙江温州皮鞋湿，下雨进水不会胖。

网络可用性，扩展性，性能的统计本质

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发