在调研RMPA时发现以下有趣问题。在我们的设计中,服务端只需要播种几个节点,剩下的结点就会以其为根,组成若干颗树将数据传播开来。如下图所示:
那么我们知道,播种的数量越多,形成的树越多,对应的高度越低,传播就越快,但问题是播种的时间就会越长,这个是反比关系,那么问题是:
要发送一条大小为N的数据,其接收端有m台,每台网卡速度为s,且与周边r个邻居建立有关系,那么我们需要播撒多少个种子n,才能使总的传输时间最小?
这里首先我们可以肯定的是,对于每次结点之间的数据传输,其时间为:
然后是对于播种后的树,其总共的传播时间应为:
每次发送ack的时间为
这样以来我们就可以得出一个关于n的时间函数:
为了求其最小值,我们对其求导(初等函数都是可导的^ ^):
令其等于0,得:
由于:
仅当:
此时:
取得极小值。那么此时的n是个什么函数呢?假设我们取 r=4,那么这个函数是这个样:
可以看出一这函数收敛得很快,也是就说基本上与m无关的,为了一探究竟,我们对上述关于m的函数求极限.
可以看出这个为常见的 型,可以使用“洛必达”法则,上下一起求导,得:
如果取r=4,其值为2.88539,取整便为3,r越大(意味着越稳定,容灾性越好),其值越大,但极限都是存在的。可见我们这个算法的优越性,开销并不随接收端数量的增加而增加,非常适合用于客户端庞大的情况。
评论列表: