Researches Of Interconneciton Networks Based On Cayley Graphs

The base of information society is interconnection network, communication algorithm is the key of information exchange, seeking network topologies with good properties to realize all kinds of effective communication algorithms and protocols. Performance of the distributed system is significantly determined by the choice of the network topology. Desirable properties of an interconnection network include low degree, low diameter, symmetry, high connectivity and high fault tolerance. there has been active research on a class of graphs called Cayley graphs because these graphs possess many of the above properties. Many well known networks are Cayley graphs, such as Hypercube, CCC, Star Graph, Honeycomb Network, Alternating Group Permutation Network and Hexagonal Torus.The thesis contains five chapters. It centres on the following two important parts of Cayley network:1. Construction of Cayley graph with desirable topological properties.2. Analysis on the topologies of the some Cayley graph interconnection networks.Here are the further descriptions of our research:1. In contrast to the fiexed degree graphs, by the word string with rank, we directly construct a family graphs, namely WG n₂ m. We porve that WG n₂ mis the Cayley graph of wreath product Z2m wr Sn（n≥2 , m≥2）. Afer analyzing its conbinatorial properties, a simple routing algorithm with an upper bound of diameter D（ WGn₂ m）≤52 is offered. Moreover, the embedding properties of the model and maximal fault tolerance are also analyzed. Finally, we compare the proposed networks with some other similar network topologies. It is found that WGn₂ m is superior to other network models because it helps to construct large scale interconnection networks with lower cost.2. Xiao, etc. recently proposed that hexagonal mesh and torus, as well as honeycomb and certain other pruned torus networks, belong to the class of Cayley graphs. However, the optimal routing algorithm for this scheme remain to be established, and the exact value of diameter is still an open problem. In this thesis, we develop a new addressing scheme for the hexagonal torus with the aid of Cayley formulations of this type of network. According to this addressing scheme, we propose two simple algorithms for routing and broadcasting in hexagonal torus. We proved in this thesis that our routing algorithm is optimal, whilst the efficiency of the broadcasting algorithm remains to be seen. By fully use of our addressing scheme, we divide the hexagonal torus into several areas to find a vertex, which has the longest distance to identity vertex, i.e. the exact value of the diameter. In this thesis, we introduce a 3D hexagonal torus based on Cayley graph, and we also discuss its topological properties.3. For the alternating group network AGn, we establish that there exist 2（n?2） parallel paths between any pair of nodes. Furthermore, we demonstrate that these parallel paths are optimal or near optimal, in the sense of their lengths exceeding the internode distance by no more than four.4. In this thesis, we present a general method by using Cayley graph to build deterministic small world networks. We also analyze the cluster topology of the Cayley graph with small world properties by constructing its left Coset graph.