A Minimum Delay Routing Algorithm Using Distributed Computation

An algorithm is defined for establishing routing tables in the individual nodes of a data network. The routing table at a node i specifies, for each other node j , what fraction of the traffic destined for node j should leave node i on each of the links emanating from node i . The algorithm is applied independently at each node and successively updates the routing table at that node based on information communicated between adjacent nodes about the marginal delay to each destination. For stationary input traffic statistics, the average delay per message through the network converges, with successive updates of the routing tables, to the minimum average delay over all routing assignments. The algorithm has the additional property that the traffic to each destination is guaranteed to be loop free at each iteration of the algorithm. In addition, a new global convergence theorem for noncontinuous iteration algorithms is developed.