A minimax utilization routing algorithm in networks with single-path routing

We consider the routing problem in networks with single-path routing and multicasting services. In such networks, all the single-destination traffic is transmitted over exactly one path between the origin and the destination and the multiple-destination traffic (if applicable) is transmitted over exactly one tree rooted at the origin. Examples of such networks are the conventional circuit-switched telephone networks, virtual-circuit based packet networks such as the X.25 networks, networks supporting Switched Multi-megabit Data Service (SMDS), networks supporting frame relay service (FRS), and the recently proposed B-ISDNs based on asynchronous transfer mode (ATM). We consider the problem of choosing a route/tree between every origin and its single/multiple destination(s) in a network so as to minimize the maximum link utilization. We consider the formulation of this problem as a linear integer programming problem. The emphasis of this paper is (i) to consider routing for single-destination and multiple-destination (multicast) traffic in a uniform way, (ii) to develop a near-optimal quasi-static algorithm to solve the problem, and (iii) to evaluate the efficiency and effectiveness of using the minimax criterion as a surrogate objective of other performance measures, e.g. the average packet delay. The basic approach to the algorithm development is Lagrangean relaxation. We also show that the routing decisions made by the minimax utilization routing (MUR) algorithm are within 2% of an optimal solution where the objective is to minimize the average packet delay. We also discuss issues of implementing the MUR algorithm