强者越强-效率与公平的幂律视角_效率与幂律

一直以来，人们认为复杂网络的内在是泊松分布，但事实上却是幂律分布。是不是所有基于泊松分布的统计复用需要重新评估呢？比如分组交换网的拥塞控制？但这是后话，本文不谈，本文主要内容是效率和公平。

以无标度网络为例，在平滑连续的时间序列

$t$ 中，每单位时间接入一个节点，它会与既有节点创建

$m$ 个链接，在一个总节点数为

$N$ 的网络中，对于已经接入的节点

$i$ ，设它的度为

K_i

$K_{i}$ ，其被链接的概率为：

(

)

p(i)=m\dfrac{K_i}{\Sigma_{j=1}^NK_j}

$p (i) = m \frac{K _{i}}{Σ _{j = 1}^{N} K _{j}}$

上式即为优先依附，其连续形式为：

(

)

(

)

∫

(

)

(

)

−

(

)

−

≈

(

)

p(i)=m\dfrac{K_i(t)}{\displaystyle\int_1^NK(t)dt}=m\dfrac{K_i(t)}{2mt-m}=\dfrac{K_i(t)}{2t-1}\approx \dfrac{K_i(t)}{2t}

$p (i) = m \frac{K _{i} ( t )}{\int _{1}^{N} K ( t ) d t} = m \frac{K _{i} ( t )}{2 m t - m} = \frac{K _{i} ( t )}{2 t - 1} \approx \frac{K _{i} ( t )}{2 t}$

另一方面，一个节点

$i$ 的度

(

)

K(i)

$K (i)$ 的变化率即为被链接的概率：

(

)

(

)

\dfrac{dK_i(t)}{dt}=\dfrac{K_i(t)}{2t}

$\frac{d K _{i} ( t )}{d t} = \frac{K _{i} ( t )}{2 t}$

两边积分，解微分方程，可得：

(

)

(

)

K_i(t)=(C\times t)^{\frac{1}{2}}

$K_{i} (t) = (C \times t)^{\frac{1}{2}}$

根据初始条件，当节点

$i$ 接入时，它共获得了

$m$ 条连接，即

(

)

K_i(t_i)=m

$K_{i} (t_{i}) = m$ ，代入上式：

C=\dfrac{m^2}{t_i}

$C = \frac{m ^{2}}{t _{i}}$

(

)

(

)

K_i(t)=m(\dfrac{t}{t_i})^{\frac{1}{2}}

$K_{i} (t) = m (\frac{t}{t _{i}})^{\frac{1}{2}}$

对其求导：

′

(

)

(

−

)

−

K_i'(t)=(\dfrac{m}{2}t_i^{-\frac{1}{2}})t^{-\frac{1}{2}}

$K_{i}^{'} (t) = (\frac{m}{2} t_{i}^{- \frac{1}{2}}) t^{- \frac{1}{2}}$

从

(

)

K_i(t)

$K_{i} (t)$ 及其导数可以看出：

看 $K_i(t) Ki(t)分母和分子，越先加入的节点获得的链接越多，此为先发优势。$
看 $K_i'(t) Ki′(t)的负指数，同一个节点受链接的速率逐渐降低，竞争越发激烈。$

这就是无标度网络动力学，越早加入的节点，最终获得越多的链接，那么到底是多少，需要求一下节点的度的概率密度。

概率密度是积累分布的导数，积累分布是一个等于1的积分，对于

(

)

∫

(

)

F_X(x)=\displaystyle\int^x f(x)dx

$F_{X} (x) = \int^{x} f (x) d x$ ，求

(

)

f(x)

$f (x)$ 即可。

对于无标度网络，对于任意度

$k$ ，求度大于

$k$ 的节点比例，即为节点度为

$k$ 的积累分布。

设

(

)

(

)

≥

K_i(t)=m(\dfrac{t}{t_i})^{\frac{1}{2}}\geq k

$K_{i} (t) = m (\frac{t}{t _{i}})^{\frac{1}{2}} \geq k$ 可得：

≤

−

t_i\leq m^2k^{-2}t

$t_{i} \leq m^{2} k^{- 2} t$

在时间

$t$ ，网络中节点总数为

t+m

$t + m$ ，则

≥

K_i\geq k

$K_{i} \geq k$ 的比例为：

≥

−

P_{K_i\geq k}=\dfrac{m^2k^{-2}t}{t+m}

$P_{K_{i} \geq k} = \frac{m ^{2} k ^{- 2} t}{t + m}$

在

$t$ 很大时有：

≥

−

≈

−

P_{K_i\geq k}=\dfrac{m^2k^{-2}t}{t+m}\approx m^2k^{-2}

$P_{K_{i} \geq k} = \frac{m ^{2} k ^{- 2} t}{t + m} \approx m^{2} k^{- 2}$

由于先发优势，对于从

i=1

$i = 1$ 开始的连续的

K_i

$K_{i}$ ，根据积累分布的定义：

−

≥

−

P_{K_i<k}=1-P_{K_i\geq k}=1-m^2k^{-2}

$P_{K_{i} < k} = 1 - P_{K_{i} \geq k} = 1 - m^{2} k^{- 2}$

这就那个积累分布，对其求导：

(

)

(

)

−

(

)

\dfrac{dP(k)}{dk}=(2m^2)k^{-3}=f_X(k)

$\frac{d P ( k )}{d k} = (2 m^{2}) k^{- 3} = f_{X} (k)$

(

)

f_X(k)

$f_{X} (k)$ 就是无标度网络的度分布，这是一个幂律分布。可以看出，前面先加入的节点占据着面积1的巨大的部分：
在这里插入图片描述

这便是马太效应，胜者通吃。

但这是为什么？

这是典型的非独立事件之间的正反馈效应，若没有考虑到这种正反馈效应，则很容易将网络视为随机网络，节点的接入被视为独立事件，但节点接入并非独立事件。

背后的根因是分形，现实中很多动力学并非在1个维度空间起作用，而是在

n>1

$n > 1$ 维空间起作用，典型地

≤

2\leq n\leq 3

$2 \leq n \leq 3$ ，只要

≠

n\neq 1

$n \neq = 1$ ，就必然会出现幂律。

非独立事件必然是关联的，最省力最安全的关联方案就是复制和吸附，背后的根本原因尚无定论，巴拉巴西的《网络科学》一书中也只是提纲挈领。但无论复制还是吸附，或者别的关联方案，都呈现出了某种偏好，即不公平趋势，这种不公平并不仅限于幂律分布的无标度网络，不公平是普遍的。

为解释不公平趋势，以生长为例开始。

设初始资源为1，分配给两个用户U1和U2，其中U1的分配额度为

0.5

0.5+a

$0.5 + a$ ，U2的分配额度为

0.5

−

0.5-a

$0.5 - a$ ，两个用户依赖这些初始资源开始成长。

如果成长仅局限在一维，那么二者在一条长度为1的线段上便是此消彼长的关系，U1获得的资源

′

$a^{'}$ 与U2失去的资源是相等的：

(

0.5

′

)

(

0.5

−

′

)

(0.5+a')+(0.5-a')=1

$(0.5 + a^{'}) + (0.5 - a^{'}) = 1$

当U1生长为

0.5

′

0.5+a'

$0.5 + a^{'}$ 的时候，U2为

0.5

−

′

0.5-a'

$0.5 - a^{'}$ ，U1的生长值比均分资源时大了

0.5

′

−

0.5

0.5+a'-0.5

$0.5 + a^{'} - 0.5$ ，U2的生长值比均分资源时小了

0.5

−

(

0.5

−

′

)

0.5-(0.5-a')

$0.5 - (0.5 - a^{'})$ ，两者相差

$0$ 。如果二者能力相当，那么这种拉锯战将会永远持续下去。

如果可以在二维空间成长，便无法得失相抵了，当U1生长为

(

0.5

′

)

(0.5+a')^2

$(0.5 + a^{'})^{2}$ 的时候，U2为

(

0.5

−

′

)

(0.5-a')^2

$(0.5 - a^{'})^{2}$ ，U1的生长值比均分资源时大了

(

0.5

′

)

−

(0.5+a')^2-0.5^2

$(0.5 + a^{'})^{2} - 0 . 5^{2}$ ，U2的生长值比均分资源时小了

−

(

0.5

−

′

)

0.5^2-(0.5-a')^2

$0 . 5^{2} - (0.5 - a^{'})^{2}$ ，两者相差

′

2a'^2

$2 a^{' 2}$ 。

这将初现不均衡的成长趋势：

更多的资源将会带来差异更大的成长值。
二者的总生长值变大，这是伏笔，请注意。

所以说，当服务员说12寸披萨售罄，要用两个6寸披萨作为替换时，千万别信他的鬼话。

根据柯西不等式的可以证明，当资源分配最公平时，其总效应最小，反之当资源分配最不公平时，其总效应最大，详情可见：
https://blog.csdn.net/dog250/article/details/120889555

那么有意思了：

资源分配最公平时整体上最低效。
资源分配最不公平时整体上最高效。

公平和全局效率是矛盾的吗？如果是矛盾的，那么公平和效率，幂律选择哪个？

举一个例子来辅助思考，假设TCP执行AIMD拥塞控制，将带宽全部分配给一条流传输效率高呢，还是分配给两条流传输效率高呢？

假设链路无噪声丢包，丢包全部由buffer over引发，从cwnd-RTTs坐标图，可得丢包率为：

p=\dfrac{1}{N_{aimd}}

$p = \frac{1}{N _{a i m d}}$

其中

N_{aimd}

$N_{a i m d}$ 为一个AIMD周期的总传输量。如果AIMD参数分别为

0.5

\alpha=1,\beta=0.5

$α = 1, β = 0.5$ ：
在这里插入图片描述
求阴影部分面积，可得：

0.375

N_{aimd}=0.375C^2

$N_{a i m d} = 0.375 C^{2}$

AIMD周期内一个RTT的平均发送量为：

0.5

0.75

N_{avg}=\dfrac{0.5C+C}{2}=0.75C

$N_{a v g} = \frac{0 . 5 C + C}{2} = 0.75 C$

可得吞吐与丢包率的关系为：

0.75

0.375

T=\dfrac{N_{avg}}{RTT}=\dfrac{0.75}{RTT}\sqrt{\dfrac{1}{0.375p}}

$T = \frac{N _{a v g}}{R T T} = \frac{0 . 7 5}{R T T} \frac{1}{0 . 3 7 5 p}$

现在，将带宽资源分给2条流，那么对于每一条流而言，

′

0.5

C'=0.5C

$C^{'} = 0.5 C$ ，带入

N_{avg}

$N_{a v g}$ 和

N_{aimd}

$N_{a i m d}$ ：

′

0.25

0.5

0.375

N_{avg}'=\dfrac{0.25C+0.5C}{2}=0.375C

$N_{a v g}^{'} = \frac{0 . 2 5 C + 0 . 5 C}{2} = 0.375 C$

′

0.375

(

0.5

)

N_{aimd}'=0.375(0.5C)^2

$N_{a i m d}^{'} = 0.375 (0.5 C)^{2}$

计算出

′

$p^{'}$ ：

′

0.375

(

0.5

)

p'=\dfrac{1}{0.375(0.5C)^2}=4p

$p^{'} = \frac{1}{0 . 3 7 5 ( 0 . 5 C ) ^{2}} = 4 p$

排队时延不变，RTT不变，上式带入

$T$ 的公式：

′

0.1875

0.375

T'=\dfrac{0.1875}{RTT}\sqrt{\dfrac{1}{0.375p}}=\dfrac{1}{4}T

$T^{'} = \frac{0 . 1 8 7 5}{R T T} \frac{1}{0 . 3 7 5 p} = \frac{1}{4} T$

结论是，将带宽资源均分给2条流，每条流的有效带宽只获得了

\dfrac{1}{4}

$\frac{1}{4}$ ，有一半带宽被浪费了。如果想获得全局的最佳性能，放弃公平显然更好。

下图可以直观看出上述结论：
在这里插入图片描述
从L1>L2可见，分量越多，每个分量获得的公平资源比例

R_{avg}=\dfrac{\sqrt{n}}{n^2}

$R_{a v g} = \frac{n}{n ^{2}}$ 就越缩水，离

R_{Bavg}=\dfrac{1}{n}

$R_{B a v g} = \frac{1}{n}$ 越远：

在这里插入图片描述

这同样也是柯西不等式揭示的。

但是损失的带宽去哪里了呢？

这提供了思考幂律分布的另一个视角，大自然在不借助外力时是收敛到公平呢，还是收敛到高效(幂律是高效的一种表现形式，我以为)呢？

自然事件发生的世界并非一维的，这些事件在多个维度相互作用，这些作用关系被物理定律主宰，而物理定律趋向于最小约束。

维护公平就是一种强约束，因为事件本身并非均匀发生的，它们的结果便不公平。先开始的事件在某维度的积累要比后发生的事件对应的积累要多，这种积累注定无法公平，除非注入额外的能量。

自然界在时间轴上形成了自相似的分形结构，描述这种结构的就是幂律，所以，幂律选择了效率，请接受幂律。

当需要抚慰公平的时候，换用大自然的方式思考，对幂律

−

y=\alpha x^{-\lambda}

$y = α x^{- λ}$ 两边取对数：

⁡

−

⁡

\ln y=-\lambda\ln +\ln \alpha

$ln y = - λ ln + ln α$

将它画在双对数坐标系，陡峭的幂律曲线就变成了直线。大自然依然是公平的，只是它有自己的公平逻辑，即：

维护尺度不变性，而不是维护量不变性。

大自然兼顾了效率与公平，而我们，要学会基于双对数坐标思考。

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

原文链接: https://blog.csdn.net/dog250/article/details/121007170

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/405665

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

强者越强-效率与公平的幂律视角_效率与幂律

相关推荐