The Construction for Symmetrical Zone-Balanced Networks

The topology of a switching network can often be represented by a graph by taking switches as vertices and links as edges. By this representation, a multistage (switching) network is a graph the vertex-set of which can be naturally partitioned into s subsets Vi,... ,VS and the edge-set into s -- 1 subsets E,... ,ES-lf for some number s, so that E, connects V, to Vj+i. (We do not allow multiple edges between two vertices.) Vertices in correspond to the input switches of the network and vertices in Vs correspond to the output switches. Let ueV 1 and vtVs. Then the channel graph G{u,u) is the union of all paths connecting u to v in the network. A multistage network is said to be regular if every vertex in Vi has the same number of edges in and the same number of edges in E{. A regular multistage network is balanced if the channel graphs G{u,v) over all ueVi and all ueVs are isomorphic. For many real networks, the input and output switches can often be partitioned into subsets called zones such that switches in the same zone have a certain community of interest and are more likely to request a connection. (In this paper, we are concerned only with connection be2973