Routing doctrines and their implementation in message-switching networks

Three practical constraints on the choice of a deterministic routing doctrine for a connected network are defined, leading to a class of doctrines for which a weighted graph of the network exists so that the specified routes are given uniquely by minimum-cost routes through the graph. A technique for finding such a weighted graph is given. An adaptive routing doctrine is defined, which considers the current delays along links of the network. The implementation of such a doctrine is discussed, and a `distributed¿ solution described which is efficient, decentralised, and resilient under fault conditions. More general adaptive routing doctrines are defined, considering two parameters associated with each link, where the routing of a message may depend on its history as well as its present position and destination. A device called a dynamic route selector is described, which takes routing decisions according to the most general doctrine discussed. It is faster than a digital computer. Finally a method for first introducing deterministic, and then adaptive, routing on a computer-based network is outlined.