Local optimization of routing tables for data networks

Data communication networks generally contain routing tables at each of the nodes of the network. We consider the routing tables at a given node to specify the fraction of traffic for each destination that should travel over each of the outgoing links from the given node. An iteration algorithm is presented which, when applied at each node using update information from adjoining nodes, converges to the routing tables that minimize average delay in the network for stationary input statistics. The algorithm has the property that the traffic to each destination is guaranteed to be loop free at each iteration of the algorithm. Several kinds of loop freedom and their implications are discussed.