Efficient load balancing for UBR traffic in ATM networks

A method is presented to find routes for UBR (unspecified bit rate) circuits in ATM networks to make UBR traffic well-balanced. It selects an optimal path for each UBR circuit, while avoiding the potential problem of selecting the same optimal path or subpath repeatedly for different circuits. This is achieved by choosing an optimal path uniformly at random from the set of all optimal paths, according to any user-selected metric. Since the set of potential paths is exponentially large and has a complex structure, a new tool is needed to select a path uniformly at random from the set of all optimal paths efficiently. We propose a solution whose complexity is only that of shortest path selection, and we prove that it selects any optimal path with equal probability, thus providing good load balancing among candidate routes. Given the efficiency of the proposed solution and the above properties of the resulting paths selection, we believe the solution can be a practical approach to load balancing of UBR circuits in ATM networks