Congested network笔记(4)

第二个谬误的思考方式是在估计和进度安排中使用的工作量单位: 人月。成本的确随开发产品的人数和时间的不同有着很大的变化, 进度却不是如此。因此我认为用人月作为衡量一项工作的规模是一个危险和带有欺骗性的神话。 它暗示着人员数量和时间是可以相互替换的。……从而,添加更多的人手,实际上是延长了而不是缩短了时间。

——人月神话

在网络中有一个著名的理论——The Braess Paradox,布雷斯悖论。

布雷斯悖论是指,在特定情况下,当某一网络上增加一条路段时,反而使得每个单位流量的花费增加,最终导致网络整体的花费增加,情况恶化。在开始具体讨论布雷斯悖论之前,先来看看如何计算一个网络的效率,以及这个网络中特定组成部分的重要性。

A network efficiency measure for congested networks这篇paper中,提出了一种新的计算congested network的效率/性能的方法。

$$\varepsilon=\varepsilon(\mathcal{G},d)=\frac{\sum_{w\in \mathcal{W}}\frac{d_w}{\lambda_w}}{n_{\mathcal{W}}}$$

在这个公式里,$\mathcal{G}$是一个网络拓扑。
$\mathcal{W}$是具有$n_{\mathcal{W}}$个元素的源点/终点对(O/D Pair)的集合。
$d_w$是源点/终点对\(w\)的需求。
$\lambda_w$则是源点/终点对$w$在网络平衡时的最小花费。

那么$\frac{d_w}{\lambda_w}$则是给定源点/终点对$w$中,单位花费能够完成的需求。若花费的计量方式是时间的话,$\frac{d_w}{\lambda_w}$可以看作是源点/终点对\(w\)的吞吐量(thoughput)。

\(\frac{\sum_{w\in \mathcal{W}}\frac{d_w}{\lambda_w}}{n_{\mathcal{W}}}\)便是将所有源点/终点对\(w\)的吞吐量加起来,然后平均到每一个源点/终点对\(w\)。

这个应该是比较自然的,比如家里有两台计算机,其中一台需要下载 16 GB 的内容,使用的时间是 1.6 小时,另一台需要下载 64 GB 的内容,使用了 3.2 小时,那么我们有

$$\begin{align}\varepsilon&=\frac{\frac{16}{1.6}+\frac{64}{3.2}}{2}\\
&=\frac{10+20}{2}\\
&=15\,\text{GB/h}\\
&=34.13\,\text{Mbps}\end{align}$$

即平均到每台电脑的吞吐量(thoughput)是 34.13 Mbps,或者说网络的效率是 34.13 Mbps。

在有了网络效率之后,paper 中提出了一种衡量网络组成部分(比如节点、链接)\(g\in \mathcal{G}\)的重要性的方法

$$\begin{align}\mathcal{I}(g)&=\frac{\Delta \varepsilon}{\varepsilon}\\
&=\frac{\varepsilon(\mathcal{G},d)-\varepsilon(\mathcal{G}-g,d)}{\varepsilon(\mathcal{G},d)}\end{align}$$

这个公式的计算思想很简单(simple, not trivial),\(\mathcal{G}-g\)是去掉\(g\)之后的网络拓扑,然后重新计算网络的效率,和原来的差值记为\(\Delta \varepsilon\),最后比上原由网络的效率便得到了\(g\)的重要性\(\mathcal{I}(g)\)。因为分式中都是以同一种单位计量的网络效率,那么\(\mathcal{I}(g)\)便是无单位的一个量,并且\(\mathcal{I}(g)\)的值域上界为1。

在定义这个公式,paper中同时也定义了:如果在去掉\(g\)之后,源点/终点对\(w\)之间没有任何路径的话,则为这个源点/终点对\(w\)定义一个抽象的路径,且这条路径的花费为\(\infty\)。

在有了网络效率及网络中组成部分\(g\)重要性的计算方法之后,让我们回到布雷斯悖论的话题上来。假设有如下网络

transport-3

现在有一个源点/终点对\(w=(1,4)\),需求\(d=6\),给出线段上的花费函数

$$\left\{\begin{align}c_a(f_a)&=10f_a\\
c_b(f_b)&=f_b+50\\
c_c(f_c)&=f_c+50\\
c_d(f_d)&=10f_d\end{align}\right.$$

显然,我们有两条路径\(\mathcal{P}_{1=(a,c)},\mathcal{P}_{2=(b,d)}\),那么线段上的流量为

$$\left\{\begin{align}f_a&=\mathcal{P}_1\\
f_b&=\mathcal{P}_2\\
f_c&=\mathcal{P}_1\\
f_d&=\mathcal{P}_2\end{align}\right.$$

于是路径上的花费函数为

$$\left\{\begin{align}\mathcal{C}_{p_1}&=c_a+c_c\\
&=10\mathcal{P}_1+\mathcal{P}_1+50\\
&=11\mathcal{P}_1+50\\
\mathcal{C}_{p_2}&=c_b+c_d\\
&=10\mathcal{P}_2+\mathcal{P}_2+50\\
&=11\mathcal{P}_2+50\end{align}\right.$$

求得均衡解\(\mathcal{P}^*\)为

$$\left\{\begin{align}\mathcal{P}^*_1&=3\\
\mathcal{P}^*_2&=3\end{align}\right.$$

此时的花费\(\mathcal{C}_{p^*_1}=\mathcal{C}_{p^*_2}=83\)

看起来非常符合直觉,两条路径的花费本质上是相同的,于是聪明的人们就分别走两条路径了。如果再在节点 2 和节点 3 之间加一条路的话,会不会更好呢?于是我们得到了下图

transport-3

并且知道了线段 e (也就是我们新增加的那条)的花费函数是

$$c_e=f_e+10$$

此时我们就有三条路可以走了

$$\left\{\begin{align}&\mathcal{P}_{1=(a,c)}\\
&\mathcal{P}_{2=(a,e,d)}\\
&\mathcal{P}_{3=(b,d)}\end{align}\right.$$

此时各线段上的流量为

$$\left\{\begin{align}f_a&=\mathcal{P}_1+\mathcal{P}_2\\
f_b&=\mathcal{P}_3\\
f_c&=\mathcal{P}_1\\
f_d&=\mathcal{P}_2+\mathcal{P}_3\\
f_e&=\mathcal{P}_2\end{align}\right.$$

以及路径上的花费函数为

$\left\{\begin{align}\mathcal{C}_{p_1}&=c_a+c_c\\
&=10(\mathcal{P}_1+\mathcal{P}_2)+(\mathcal{P}_1+50)\\
&=11\mathcal{P}_1+10\mathcal{P}_2+50\\
\mathcal{C}_{p_2}&=c_a+c_e+c_d\\
&=10(\mathcal{P}_1+\mathcal{P}_2)+(\mathcal{P}_2+10)+10(\mathcal{P}_2+\mathcal{P}_3)\\
&=10\mathcal{P}_1+21\mathcal{P}_2+10\mathcal{P}_3+10\\
\mathcal{C}_{p_3}&=c_b+c_d\\
&=(\mathcal{P}_3+50)+10(\mathcal{P}_2+\mathcal{P}_3)\\
&=11\mathcal{P}_3+\mathcal{P}_2+50\end{align}\right.$

这个时候求均衡解\(\mathcal{P}^*\)的方程是

$$\left\{\begin{align}11\mathcal{P}^*_1+10\mathcal{P}^*_2+50&=\lambda\\
10\mathcal{P}^*_1+21\mathcal{P}^*_2+10\mathcal{P}_3+10&=\lambda\\
11\mathcal{P}^*_3+\mathcal{P}^*_2+50&=\lambda\\
\mathcal{P}^*_1+\mathcal{P}^*_2+\mathcal{P}^*_3&=6\\
\mathcal{P}^*_1,\mathcal{P}^*_2,\mathcal{P}^*_3&\ge 0\end{align}\right.$$

求解可得

$$\left\{\begin{align}\mathcal{P}^*_1&=2\\
\mathcal{P}^*_2&=2\\
\mathcal{P}^*_3&=2\\
\lambda&=92\end{align}\right.$$

\(\lambda=92\)!这意味着我们多修了一条路实际上使得每个用户的花费增加了,而不是减少了。而这就是布雷斯悖论。

如果我们计算此时各线段的重要性\(\mathcal{I}\)的话,会有

$$\left\{\begin{align}\mathcal{I}(a)&=\frac{6}{29}&=0.206\\
\mathcal{I}(b)&=\frac{121}{673}&=0.179\\
\mathcal{I}(c)&=\frac{121}{673}&=0.179\\
\mathcal{I}(d)&=\frac{6}{29}&=0.206\\
\mathcal{I}(e)&=\frac{-9}{83}&=-0.108\end{align}\right.$$

可以看到线段\(e\)的重要性\(\mathcal{I}(e)\)是个负值!这说明线段\(e\)在这种情况下根本就不该参与到这个系统中来。

于是这在实际的应用中的话,可以作为是否要修建新的公路的参考,或者计算机中是否要添加新的通信线路的参考。当然也可以作为部分我们总是觉得现实中越修路反而越堵的原因。

最后,对于刚才使用到的例子,实际上在需求\(d\)取不同的值的时候,布雷斯悖论不一定出现。在原paper中给出的范围如下(均衡状态时)

当\(d\in[0, 2\frac{18}{31})\)时,只有\(\mathcal{P}_{2=(a,e,d)}\)会被使用,此时布雷斯悖论没有出现。

当\(d\in[2\frac{18}{31}, 3\frac{7}{11}]\)时,也只有\(\mathcal{P}_{2=(a,e,d)}\)会被使用,但此时出现了布雷斯悖论。

当\(d\in(3\frac{7}{11}, 8\frac{8}{9}]\)时,三条线路都有被使用,同时也存在出现了布雷斯悖论,我们计算的\(d=6\)就是这种情况。

当\(d\in(8\frac{8}{9}, +\infty)\)时,只有\(\mathcal{P}_{1=(a,c)}, \mathcal{P}_{2=(b,d)}\)会被使用,布雷斯悖论消失了。

其实布雷斯悖论应用在计算机中可能更好理解,或者会是一件自然而然的事,比如我有一个超算节点,我的作业可以在 1 分钟内完成,当我增加一个节点协同计算时,对于某些类型的作业可能反而增加了运行时间。例如那些数据量比较大的作业,在节点间传输也有着不小的开销。但是当数据量达到一定程度之后,就又会增加整体的效率。

Leave a Reply

Your email address will not be published. Required fields are marked *

18 − three =