An algorithm for optimal minimax routing in ATM networks

Asychronous Transfer Mode (ATM) has been adopted by the CCITT as the transport mode in which Broadband ISDN will be based. In this paper, the authors formulate the problem of routing cells in an ATM network as an optimization problem. The objective is to minimize the largest cell loss probability among all links. The constraints correspond to a multicommodity network flow problem with gains. An algorithm to determine a global optimal flow assignment is presented. The minimax routing algorithm was implemented and tested on several sample networks. The computational experiments show that the algorithm is computationally efficient.