Throughput fairness in indirect interconnection networks

Abstract

The performance of an interconnection network is typically measured by two metrics: average latency and peak network throughput. Average network throughput is usually reported in the belief the network is fair and all source nodes are supposedly able to inject at the same rate. However, most systems exhibit significant network unfairness under non-uniform loads. At high loads, if link utilization is uneven, the injection matrix will also become uneven. This unfairness significantly degrades the performance of some nodes, and eventually the whole system. Fairness issues have been previously reported for direct topologies such as mesh and torus, but this work evaluates throughput fairness in indirect networks, specifically the fat-tree topology. We will see fairness is still an issue for indirect networks in the presence of hot-spots. The SAT protocol was initially proposed to provide throughput fairness for ring networks. This paper extends the original protocol to implement a fairness injection mechanism that works for indirect networks. A thorough evaluation will show that for most scenarios it is possible to achieve throughput fairness without a significant lost of peak throughput.