计算拓扑结构中的理论网络带宽

Question

我正在构建离散事件模拟器，并且需要能够计算给定网络拓扑中两个系统之间可用的理论带宽，以便我可以“计时”转移将发生多久，并在预计完成时间创建一个事件。

目前，为了简单起见，我没有考虑交换机的背板或网络中发生冲突/拥塞的可能性。我只是对所有通信系统之间的最大传输速率感兴趣。

例如，请考虑下面的示例网络拓扑：

我们假设以下连接：

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

鉴于这些连接，什么是所有来源的最大有效传输速率？

如果我们把它看成一个图形，我可以通过从源头开始并在每个交换机级别评估进入网络流量与交换机上行链路的最大数量来手动计算。

例如，在这种情况下源＃1具有的有效带宽50 Mbps到DEST 1

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

不过，我很好奇，可以利用什么其他的方法来计算这个，或者如果有是一种更有效的方法，可以用来“预测”网络流量。

任何反馈表示赞赏 - 谢谢。

Answer 1

这本质上是一个最大最小公平问题。

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

逐行填充算法（维基文章中描述）是一个简单的解决这个问题：

如果资源被预先在网络节点分配，最大 - 最小 公平可以通过使用渐进式填充算法来获得。 您从所有费率开始等于0，并以 相同的速度将所有费率一起增长，直到遇到一个或多个链路容量限制为止。使用这些链接的来源的 费率不再增加， 并且您继续增加其他来源的费率。所有已停止的 源都有一个瓶颈链接。这是因为他们 使用饱和链接，并且所有其他来源使用饱和链接 停止在同一时间或之前停止，因此有一个较小或相等的速率。该算法继续，直到它不是 可能增加。最后，当算法终止时，所有 源已在某个时间停止，因此有链接的瓶颈 。这个分配是最大最小公平。