Optimum and suboptimum tree computation for interconnected multiple-access networks [LAN interconnection]

A method of computing optimum trees is presented along with a suboptimum approach that is computationally efficient. The optimum spanning tree is defined to be the one which, for a given network and traffic requirements, minimizes the average frame transfer delay, which for simplicity is referred to as delay. A procedure is described for finding a suboptimum tree by examining a small subset of trees likely to have good delay characteristics. The tradeoff between the degree of optimization and the computational effort is examined. Results show that the computational effort was reduced by over 90% while yielding near-optimum results