The Design of Multiple-Line Redundant Networks

One means to assure high reliability in digital electronic equipment is to incorporate multiple-line redundancy in its design. This type of redundancy has been described frequently in the literature. This paper treats the problem of determining the design of a multiple-line redundant network which maximizes the reliability of the network. There is an extremely large number of feasible designs for moderately sized networks, and no computationally practical method exists for determining the optimum design. To provide a practical solution for this problem an algorithm is described which generates a small subset of all feasible designs. A dynamic programming algorithm then selects the best from the reduced set. Computational results show that the design discovered by these techniques, in most instances, has a reliability very close to that of the optimum, and that the time for the computation increases approximately as the fourth power of the number of logical elements in the network.