Communication networks based on the product graph

Abstract

A large switched network has a complex pattern of interconnections which in practice is normally based on tandem connection of relatively simple units. It is shown that an alternative basis is possible, in which a large structure is built up as a Cartesian product of simple units. The resulting structure has some interesting topological properties, notably an overall homogeneity and a high connectivity for a given number of links and switches. The high connectivity implies that low blocking and high reliability should be attainable. The traffic capacity depends on the path-selection strategy used. A general theory is given for products of arbitrary dimension, assuming uniformly distributed traffic, and either of two simple strategies. A more efficient strategy is described and analysed for two-dimensional products only. The requirements of a trunking scheme for terminal and transit exchanges are summarised, and it is shown that the product network is in principle adaptable to them. The network may need to be partitioned into subsets of varied size, and it is shown that this can be done in a uniform manner. Finally, the use of a product network as a concentrator is described.