Reduction of Network States Under Symmetries

Most telephone connecting networks are built in stages of identical units, arranged symmetrically in frames, and joined by symmetric cross-connect fields (Fig. 1). As a result, their structure has so much symmetry that it is possible quickly to identify at least some network states that are "essentially" equivalent in that their combinatorial structure is the same, and that they differ only in point of renaming terminals, switches, links, customers, etc. It has long been known in the informal lore of traffic theory that if the traffic sources at the terminals have the same stochastic behavior, then these symmetries of the network could be used as a basis for lumping together equivalent states and reducing the number of equations to be solved for the state probabilities. Such a line of thought was first pursued in a formal way by S. P. Lloyd1 in unpublished work dated September 19,1955, and we follow it further 111 here. But whereas Lloyd right away considered probability transition rate matrices (for Markov processes) which he assumed admitted symmetry operations, we shall instead first relate the relevant symmetries to the network graph and the semilattice of states, without reference to a probabilistic model, and only later consider a natural traffic model. Our approach remains combinatorial as long as possible, and allows us eventually to include the effects of routing decisions, to connect the reduction ideas with optimal routing, and to find that certain natural transition matrices necessarily admit the network symmetries.