Researches Of Interconnection Networks Based On Cayley Graphs

It is now well known that Cayley graphs play a very important role in the design and analysis of interconnection networks for parallel processing and of local area communication networks. The graphs such as hypercubes, double loop networks, star graphs are examples of Cayley graphs. The paper contains five chapters. It centres on the following two important parts of Cayley networks:1. The design and optimal routing algorithm for double loop networks;2. The routing algorithm for alternating group networks and shuffle-exchange permutation networks.Here are some of main results in this paper:1. We give a method to construct k-tight optimal infinite families. By using this method, we obtain four 3-tight optimal infinite families, three 4-tight optimal infinite families, three 5-tight optimal infinite families, and two 6-tight optimal infinite families. By the aid of computer, we also find 27 new 0-tight optimal infinite families, 26 new 1-tight optimal infinite families, 8 new 2-tight optimal infinite families, and 2 3-tight optimal infinite families.2. We give a method to construct singular 1-tight optimal infinite families. By using this method, we obtain three singular 1-tight optimal infinite families and one singular 2-tight optimal infinite families.3. For a given directed double loop network G(n; s1, s2), by computing four parameters of the .L-shape tile and a solution of s1x + s2y = 1 (mod n) in advance, we give an optimal routing algorithm for G(n; s1,s2) which requires constant processing time to find a shortest path between any two nodes.4. For a given positive integer n, we give an O(k2.5n0.25 log n) algrithm to find a fc-tight optimal double loop network G(n; 1,s).5. For a given undirected double loop network G(n;眘1,盨2), by computing four parameters of the L-shape tile and a solution of s1x + s2y = 1 (mod n) in advance, weIIgive an optimal routing algorithm for G(n;s1 s2) which requires constant processing time to find a shortest path between any two nodes.6. We give a diameter formula for an undirected double loop network G(n; 眘1, 眘2), which can be represented by four parameters of the L-shape tile.7. An optimal routing algorithm is presented for the new alternating group network ANn.8. A new routing algorithm is proposed for the shuffle-exchange permutation network SEPn and a lower bound diameter estimation is given for this network.