Reduction of Network States Under Symmetries
Vladimír Beneš · Bell System Technical Journal · 1978
It is a folk-theorem of traffic theory that if all sources have the same stochastic behavior, then symmetries of a telephone connecting network can be used to lump together equivalent states and to reduce the number of equations to be solved for the state probabilities. The structural and algebraic bases of this idea, and its connections to stochastic models, are studied here by means of concepts from lattice theory, group theory, and combinatorics generally. It is shown that when offered traffic is homogeneous and routing is structurally consistent, the state equations for certain natural Markov processes (representing operating telephone networks) can be substantially simplified by restricting attention to “macrostates,” defined as the structural equivalence classes of states, of which there are typically many fewer than of states. Reduced state equations are then obtained for general networks under simple Markovian traffic assumptions.