26
Feb
2015

应用层多播传输最佳播种数量研究



       在调研RMPA时发现以下有趣问题。在我们的设计中,服务端只需要播种几个节点,剩下的结点就会以其为根,组成若干颗树将数据传播开来。如下图所示:

            

       那么我们知道,播种的数量越多,形成的树越多,对应的高度越低,传播就越快,但问题是播种的时间就会越长,这个是反比关系,那么问题是:

       要发送一条大小为N的数据,其接收端有m台,每台网卡速度为s,且与周边r个邻居建立有关系,那么我们需要播撒多少个种子n,才能使总的传输时间最小?

       这里首先我们可以肯定的是,对于每次结点之间的数据传输,其时间为:

    然后是对于播种后的树,其总共的传播时间应为:

    每次发送ack的时间为

    这样以来我们就可以得出一个关于n的时间函数:

    为了求其最小值,我们对其求导(初等函数都是可导的^ ^):



    令其等于0,得:

    由于:


       仅当:

    此时:

    取得极小值。那么此时的n是个什么函数呢?假设我们取 r=4,那么这个函数是这个样:






      可以看出一这函数收敛得很快,也是就说基本上与m无关的,为了一探究竟,我们对上述关于m的函数求极限.

    可以看出这个为常见的  型,可以使用“洛必达”法则,上下一起求导,得:

    如果取r=4,其值为2.88539,取整便为3r越大(意味着越稳定,容灾性越好),其值越大,但极限都是存在的。可见我们这个算法的优越性,开销并不随接收端数量的增加而增加,非常适合用于客户端庞大的情况。





上一篇:Joe Hisaishi Spring 下一篇:2014 北京ArchSummit总结

评论列表:

发表评论: