Assessing the efficiency of resource allocations in bandwidth-sharing networks

We focus on flows traversing the network, sharing the resources on their common path with (independently generated) cross-traffic. Assuming exponentially distributed flow sizes, we show that in many scenarios optimizing under a fluid scaling gives a simple linear switching strategy, that accurately approximates the optimal strategy. When two nodes on the flow path are equally congested, however, fluid scaling is not appropriate, and the corresponding strategy may not even ensure stability. In such cases, we show that the appropriate scaling for efficient workload-based allocations follows a square-root law. Armed with these, we then assess the potential gain that any sophisticated strategy can achieve over standard α-fair strategies, which are representations of common distributed allocation schemes, and confirm that α-fair strategies perform excellently among non-anticipating policies. In particular, we can approximate the optimal policy with a weighted α-fair strategy.