0

这是我的问题:P2P 网络中有 n 个对等点,它们请求相同的数据块;并且有一些限制。1.对等点有自己的上传带宽,平均带宽就是数据块的大小。2. 对等体对这个数据块有不同的期限。如果一个节点在截止日期前没有获得整个区块,它必须搜索服务器帮助。3. 只有拥有整个数据块的对等方才能传输数据(部分或全部)。

目标是最小化服务器的总上传量,我无法弄清楚它是否具有最佳算法或者它是一个 NP 问题。截止时间优先或最大带宽优先可能无法处理某些情况是不是有一些类似这样的NP问题?这就像一个图流问题或一个指令调度,但我发现这很难,因为我必须同时处理截止日期和供应商总带宽的增长。我希望我能得到一些关于解决方案的方向或资源:) 谢谢。

4

1 回答 1

0

考虑到每个对等点在您的情况下都是单独行动的,并不是只有一个自动机在解决您的问题,而是很多。由于在给定延迟内不可用时获取数据块通常是多项式问题,并且由于该工作是由单个对等方完成的,因此您的问题不是本地每个对等方的 NP 问题。

另一方面,如果服务器必须计算备份资源的最小分配来传输“丢失的块”,则必须首先找出对等方丢失块的概率(例如平均值 + 标准偏差)。假设您知道此类事件的统计分布,您可以计算传输那些丢失的块所需的总带宽,并选择带宽中的故障/容限风险。如果您使用多个服务器来满足需求,请确保您的对等方随机联系它们以分配负载。

解决这个统计问题不是 NP 问题。您可以从每个对等点收集故障信息并将其添加到中央/服务器对等点。因此,我的结论是,您的问题不是 NP 问题。

第二部分:

哦,我现在更好地理解了您的情况:多个“服务器”对等点可能会帮助一个对等点获得完整的块。在这种情况下,对于给定的块,系统中服务器对等点的数量呈指数增长。在这种情况下,这个优化问题对我来说具有泛滥问题的所有特征,它们是 NP。

即使你的对等点图和它们之间的潜在连接是静态的(在真正的 P2P 网络中绝不会出现这种情况),在合理的时间内为超过 50 或 100 个节点计算最佳解决方案实际上是不可能的,除非你可以在这张图上做出非常具体的假设(这在一般情况下几乎从来没有,而且并不总是有用的)。

但是您是否绝对需要绝对最优解,或者接近最优解是否足够好?

启发式方法会告诉您,如果您的对等点具有或多或少相同的下载带宽容量,那么首先为具有最高 UPLOAD 带宽的对等点提供服务以最大化雪崩效应并降低对等点寻求帮助的风险是有意义的,一般来说。

如果你的图是相对平衡的(也就是说,大多数对等点可以连接到大多数对等点),那么我敢打赌初始服务器的最小带宽将是图中节点数乘以对等点期望的平均速度的对数函数被送达。这只是我的直觉,应该通过实际测量或对您的案例进行强有力的建模来验证。

于 2011-04-03T16:39:49.090 回答