Tree-forming reversible routes in communication networks

Abstract

Tree-forming reversible routes are characterized by two constraints. The first, a strong form of route uniqueness, states that there may be no more than one route between any pair of nodes. It is called the tree-forming constraint as it implies that the set of routes to each node form a tree rooted at that node. The other constraint is reversibility: if the route from one node to a second is described as a sequence of nodes or links, the route from the second to the first must be the reverse sequence. The simplicity of these constraints is deceptive, and route definition turns out be non-intuitive and rather difficult. In this paper, a route-definition procedure is considered in which all consequences of a route selection are computed before the next selection is allowed. General properties and problems of tree-forming reversible routing systems are discussed, and an interactive, incremental route definition program is briefly described. © 1989.