Scalability issues for distributed explicit rate allocation in ATM networks

One of the challenges for rate based congestion management for computer communication networks is that of scalability. This is true especially in the context of ATM, when reducing the amount of state maintained and the computation performed can have significant advantages in making switches fast as well as low-cost. We explore ways of achieving better scalability of explicit rate algorithms for maxmin fair rate allocation in the presence of a large number of flows/virtual connections. We seek ways to reduce the complexity in both the amount of state that individual switches have to maintain, and the computation performed, by introducing the idea of discrete source rates. We develop algorithms with O(k) complexity of the calculation of fair allocation at the switch, where k is the number of distinct rates. We reduce the amount of state information to one bit per flow without performance degradation. We suggest a further approximation requiring only O(k) state information which performs quite well in our simulations, although it is shown to be vulnerable to certain conditions which may lead to somewhat lower link utilization