A new distributed algorithm is presented for dynamically determining weighted shortest paths used for message routing in computer networks. The major features of the algorithm are that the paths defined do not form transient loops when weights change and the number of steps required to find new shortest paths when network links fail is less than for previous algorithms. Specifically, the worst case recovery time is proportional to the largest number of hopshin any of the weighted shortest paths. For previous loop-free distributed algorithms this recovery time is proportional toh2.

Abstract This paper is concerned with the problem of defining K multiple paths between pairs of nodes in a network. The treatment presented here is on a theoretical level, although the problem is motivated by a practical scheme for message routing in store‐and‐forward packet switched computer networks. Theorems are presented which offer readily testable sufficient conditions on the topology of a network which guarantee the existence of at least one set of paths under consideration. The proof of this theorem provides a generalized systematic method for constructing these paths if the sufficient conditions are met.

This paper analyzes a method for identifying end-to-end connections in computer networks which is designed to provide reductions in the sizes of the packet headers and routing tables stored in the nodes. The method, known as Local Path ID Swapping, uses a shortened connection identifier, called the LPID, in the message headers and routing tables. In general, the LPID field is swapped in the message header from node to node along the path of the route. Some analytical results are presented for evaluating the important tradeoffs involved in LPID swapping. Most notable is the tradeoff between the size of the LPID field and the number of connections which can be defined in the network.