Adaptive alternate-routing in telephone networks: Optimal and equilibrium solutions

In this paper, the authors consider the problem of adapting the alternate routing tables in telephone networks to the varying traffic conditions. Two types of solutions of this problem, which is treated under quasi-static conditions, are discussed. First, the authors consider optimal solutions in the sense of minimum traffic losses. This problem of optimal routing is shown to be NP-complete in the strong sense, which is an indication of computational intractability even for near-optimal solutions. Then, equilibrium solutions are proposed as a natural and more tractable alternative. A relaxation type algorithm is suggested and shown to obtain the equilibrium strategies for networks having multiple sources directing traffic to a common destination. The decentralization of the algorithm in large scale networks is also discussed.