Optimal minimax routing in ATM networks

A model for characterizing the cell loss probabilities of an ATM network is developed. The three types of cell losses considered are losses in the switch fabric, losses due to buffer overflow, and congestion control losses. The problem of determining routing assignments to minimize the maximum link cell loss probability is formulated as an optimization problem. Even though the problem is not a convex program, an algorithm is presented that determines a global optimal solution. The algorithm consists of a one-dimensional search procedure and a procedure for solving a generalized multicommodity flow problem with gains. The algorithm is shown to be reasonably efficient when tested on several networks