M.Sc Thesis

M.Sc StudentGolbandi Nadav
SubjectCharacterization and Classification of Butterfly Like
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Ami Litman


A multistage network is a Generalized Butterfly Network (GBN) if there are 2n end-to-end paths, (P0, P1, … , Pn-1 ), that cover all the vertices and are vertex disjoint and for any two consecutive stages k and k + 1 there is an integer l s.t. the k-th vertex of Pi is adjacent to the (k +1)-th vertex of Pj iff the binary presentations of i and j differ at most at the l-th bit. The GBN family contains most of the important interconnection networks including the Butterfly networks, the Beneš networks and the Batcher bitonic sorting networks.

This work establishes several characterizations and properties of the GBN family that were previously unknown even for the special case of the Butterfly. One characterization is based on automorphism as follows: A multistage network G is a GBN iff it is 2-regular and for any two end-to-end paths, P’ and P’’, there is an automorphism of G that swaps p’ and p’’. Another one is based on the existence of paths that shortcut or bypass a certain path and yet anther is based on a certain symmetry of the distance function. These results, and all the other results of this work, are founded on the Layered Cross Product (LCP) introduced by Even and Litman.

It is sometimes useful to assign labels to the vertices or edges of a network. A notable example is the min/max labeling of the edges of a comparator network. To facilitate the study of labeled multistage networks we introduce the Labeled LCP which is an associative and commutative variant of the LCP that operates on vertex-labeled or edge-labeled multistage networks. We show that, under certain conditions, this operator commutes with the concatenation operator. Building on that, we show that the Batcher bitonic sorting network with its min/max labeling is a product of very simple labeled networks - bamboos or rosaries. Moreover, this network, as well as any network which is a product of labeled rosaries under a certain algebra of labels, satisfies a variant of the above path swapping property. Namely, for any two end-to-end paths having identical labels at each stage, there is a label-preserving automorphism that swaps these paths.