Assessing the efficiency of resource allocations in bandwidth-sharing networks

Resource allocation in bandwidth-sharing networks is inherently complex: the distributed nature of resource allocation management prohibits global coordination for efficiency, i.e., aiming at full resource usage at all times. In addition, it is well recognized that resource efficiency may conflict with other critical performance measures, such as flow delay. Without a notion of optimal (or "near-optimal") behavior, the performance of resource allocation schemes cannot be assessed properly. In previous work, we showed that optimal workload-based (or queue-length based) strategies have certain structural properties (they are characterized by so-called switching curves), but are too complex, in general, to be determined exactly. In addition, numerically determining the optimal strategy often requires excessive computational effort. This raises the need for simpler strategies with "near-optimal" behavior, that can serve as a sensible bench-mark to test resource allocation strategies. 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 a-fair strategies, which are representations of common distributed allocation schemes, and confirm that a-fair strategies perform excellently among non-anticipating policies. In particular, we can approximate the optimal policy with a weighted a-fair strategy