Local and congestion-driven fairness algorithm in arbitrary topology networks

Typically, bandwidth reservation is not made for data applications. Therefo re, the only way to provide minimum bandwidth guarantees to such an applica tion is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The c ontext of this work is fairness in an arbitrary topology network, the MetaN et, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarante e combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications. While developing the mechanisms, we also present performance measures to as sess the new access- and now-control algorithm: i) Locality and congestion-driven-only the subnetwork containing conflictin g traffic streams becomes involved in the fairness regulation, Furthermore, the fairness regulation is activated only when congestion occurs, This imp lies that when there is no congestion, nodes can access the network immedia tely and freely, which is a key requirement for distributed computing. ii) Scalability-the data-structure sizes used in the algorithm are a functi on of the switching node degree, and use constant space control signals of two bits only (the ATR I standard, for example, dedicates four bits in the header of each cell to generic flow-control). iii) Linear access time in the congested subnetwork-measured by "the maxima l clique in what we call the conflict graph to which a node belongs," and a frequency which is inverse linear in this parameter (when the traffic patt ern stabilizes).