Evaluation of communication structures in large-scale multicomputer networks.

Abstract

Computer network design is a difficult and multifaceted problem. The designer must select a combination of architecture and protocols to meet a specific need. To do this task properly many potential networks need to be evaluated and compared in terms of performance and reliability criteria. This evaluation can be done most effectively and efficiently via modeling. Unfortunately, current modeling techniques are tied closely to specific architectures, and so do not readily permit meaningful comparisons across broad classes of networks. Moreover, architecture specific models become intractable when faults are introduced, making evaluation of degradable performance impossible. To address this problem, we develop a means of describing and modeling multicomputer systems that facilitate the comparison of the performability of a wide range of architectures. A network architecture taxonomy is used to increase the understanding of the relationships between various networks. Guided by this, a network description system is developed which focuses on the logical rather than the physical structure of network architectures. A model construction technique for multicomputer systems based on this logical structure is outlined. A group theoretic algorithm is used to manipulate the physical symmetries of a network architecture in order to generate the logical structure states necessary for modeling. This permits a significant reduction in the number of states of the model leading to savings in both time and memory necessary for the solution of the model, as well as increasing the size of systems that can be modeled. A generalization of reward models is developed to permit solution of the type of models that result from this construction method. The generalization uses a stochastic reward structure and under appropriate conditions equivalent generalized and ordinary models can be constructed. The use of this methodology is demonstrated for several network architectures, including a new class based on balanced incomplete block designs. This new class is a multibus network which limits the number of connections required at each node as well as the number of nodes connected to a bus.