これが私の問題です。P2P ネットワークには、同じデータ ブロックを要求する n 個のピアがあります。そして、いくつかの制約があります。1. 独自のアップロード帯域幅を持つピア。平均帯域幅はデータ ブロックのサイズです。2. ピアには、このデータ ブロックに関する異なる期限があります。1 つのピアが期限までにブロック全体を取得できなかった場合、サーバーのヘルプを検索する必要があります。3. ピアは、データ ブロック全体を持っている場合にのみ、データ (部分的または全体的) を転送できます。
目的は、サーバーの総アップロードを最小限に抑えることです。最適なアルゴリズムがあるのか、それとも NP 問題なのかはわかりません。締め切り優先または最大帯域幅優先の状況では対処できない場合があります これに似た NP の問題はありますか? これはグラフ フローの問題や命令スケジューリングのようなものですが、締め切りとサプライヤーの総帯域幅の増加を同時に処理しなければならないため、難しいことがわかりました。解決策についての指示やリソースを入手できることを願っています:)ありがとう。
あなたの場合、各ピアが個別に動作することを考えると、問題を解決するオートマトンは 1 つだけではなく、多くのオートマトンです。特定の遅延内にデータ ブロックが利用できない場合にデータ ブロックを取得することは、通常、多項式の問題であり、ジョブは個々のピアによって実行されるため、問題はローカルの各ピアの NP 問題ではありません。
一方、サーバーが「欠落しているブロック」を転送するためにバックアップ リソースの最小割り当てを計算する必要がある場合は、ピアがブロックを欠落する確率 (平均 + 標準偏差など) を最初に調べる必要があります。そのようなイベントの統計的分布を知っていると仮定すると、帯域幅の障害/許容範囲のリスクを選択して、欠落しているブロックを転送するために必要な合計帯域幅を計算できます。必要に応じて複数のサーバーを使用している場合は、ピアがそれらにランダムに接続して負荷を分散するようにしてください。
この統計問題を解くことは、NP の問題ではありません。各ピアから障害情報を収集し、中央/サーバー ピアに追加できます。したがって、私の結論は、あなたの問題は NP 問題ではないということです。
パート II:
ああ、私はあなたのケースをよりよく理解しています。複数の「サーバー」ピアは、1 つのピアが完全なブロックを取得するのに役立つ可能性があります。この場合、サーバー ピアの数は、特定のブロックに対してシステム内で指数関数的に増加します。この場合、この最適化問題はフラッディング問題のすべての特徴を備えており、NP です。
ピアのグラフとそれらの間の潜在的な接続が静的であったとしても (実際の P2P ネットワークでは決してそうではありません)、50 または 100 を超えるノードに対して合理的な時間で最適解を計算することは事実上不可能です。このグラフで非常に具体的な仮定を立てることができます (これは一般的にはほとんど当てはまらず、常に役立つとは限りません)。
しかし、絶対に最適なソリューションが絶対に必要ですか、それとも最適に近いもので十分でしょうか?
ヒューリスティックスは、ピアが多かれ少なかれ同じダウンロード帯域幅容量を持っている場合、雪崩効果を最大化し、ピアが助けを求めなければならないリスクを減らすために、最初に最大のアップロード帯域幅でピアにサービスを提供することが理にかなっていることを教えてくれます。一般に。
グラフが比較的バランスが取れている場合 (つまり、ほとんどのピアがほとんどのピアに接続できる場合)、最初のサーバーの最小帯域幅は、グラフ内のノード数にピアが期待する平均速度を掛けた対数関数になると思います。提供されます。これは私の直感に過ぎず、実際の測定またはケースの強力なモデリングで検証する必要があります.