2

私は離散イベント シミュレータを構築中ですが、特定のネットワーク トポロジ内の 2 つのシステム間で利用可能な理論上の帯域幅を計算できるようにする必要があります。予想される完了時間にイベントを作成します。

現時点では、簡単にするために、スイッチのバックプレーンや、ネットワーク内で衝突や輻輳が発生する可能性については考慮していません。通信しているすべてのシステム間の最大転送速度に関心があります。

たとえば、次のサンプル ネットワーク トポロジを考えてみましょう。 トポロジーの例

以下の接続を想定しています。

Source 1, Source 2 -> (sending to) Dest 1
Source 3, Source 4 -> (sending to) Dest 2

これらの接続が与えられた場合、すべてのソースの最大実効転送速度は?

これをグラフとして視覚化すると、ソースから開始し、スイッチのアップリンクに対する着信ネットワーク トラフィックの最大量を各スイッチ レベルで評価することで、これを手動で計算できます。

たとえば、このシナリオのソース #1 には、宛先 1 への有効な帯域幅が 50 Mbps あります。

1 Gbps * S1(1/2) * S2(1) * S3(1/10) = 50 Mbps

ただし、これを計算するために他にどのような方法を利用できるか、またはネットワーク トラフィックを「予測」するために利用できるより効果的なアプローチがあるかどうかに興味があります。

フィードバックをお待ちしております -- ありがとうございます。

4

1 に答える 1

1

これは本質的に最大最小公平性の問題です。

https://en.wikipedia.org/wiki/Max-min_fairness

プログレッシブ フィル アルゴリズム (Wiki の記事で説明されています) は、この問題に対する簡単な解決策です。

リソースがネットワークノードに事前に割り当てられている場合、プログレッシブフィリングのアルゴリズムを使用して最大最小公平性を取得できます。すべてのレートを 0 にして開始し、1 つまたは複数のリンク キャパシティ制限に達するまで、すべてのレートを同じペースで増加させます。これらのリンクを使用するソースの料金はこれ以上引き上げられず、他のソースの料金は引き続き引き上げられます。停止されたすべてのソースには、ボトルネック リンクがあります。これは、それらが飽和リンクを使用しており、飽和リンクを使用している他のすべてのソースが同時に停止されているか、以前に停止されていたため、レートが小さいか等しいためです。アルゴリズムは、増加できなくなるまで続行されます。最後に、アルゴリズムが終了すると、すべてのソースがある時点で停止しているため、ボトルネック リンクが存在します。

于 2013-01-20T06:35:16.003 に答える