Interconnection Architectures And Routing Algorithms Of Coset Graphs And General Biswapped Networks

Interconnection networks are critical infrastructure for parallel distributed network computing. Different applications require varies of interconnection architectures with different properties and communication capacities, corresponding to different types of network graphs, structural design and evaluation studies. Interconnection network design should make appropriate trade-off among efficiency, robustness and costs.Three common fundamental problems are induced in graph theory from studying on the topological structures of interconnection networks, which are to analyze and evaluate the nature of network topology, network communications, and network mapping or stimulating.In the light of the analysis with insight on the exsisting problems in the interconnection network researches and their applications, in this thesis, we use algebraic graph theory based on group theory, and theory on Cayley graph, coset graph, isomorphism and homomorphism, combined with other tools from network study and graph theory, to investigate theoretical models, topological properties of networks, communication algorithms, and system design & assessment on protocols of P2P network application model, with interconnection architectures based on coset graphs and the General Biswapped Networks (GBSN).The main contributions of the thesis are as follows.1) The coset representation of Sn is established for connected regular digraphs. The necessary and sufficient conditions for the isomorphism between two connected regular digraphs are given and the presentation conditions for the related automorphic groups are mentioned. That provides a systematic rigorous approach to distinguish and to identify their topological equivalence. By using our model with conclusions, the complete coloring problem of regular digraphs is discussed, and so does the arc coloring of the Generized de Bruijn network (LDI network). Our result provides a valuable reference for related research on parallel communication algorithms.2) A unified addressing schema for hexagonal and honeycomb networks is proposed with Cayley graph and coset graph model, which established a concise, elegant and convenient foundation to investigate complex hexagonal and honeycomb related networks. Two open problems on simple distance formulas of honeycomb mesh nodes and diameter measurement of hexagonal torus are solved as application. The shortest-path routing algorithms for hexagonal and honeycomb networks are constructed and a feasible strategy to develop an optimized broadcasting algorithm for hexagonal torus is provided.3) A complex network building approach called General Biswapped Network (GBSN) is proposed and studied, showed its versatility comparing with other related models. The intrinsic connections among GBSN and a series of well-known interconnection network models, including the isomorphic equivalence between GBSN and the generized OTIS, are revealed. The Cayley graph model for BSNs (Biswapped Networks) and the coset graph model for the regular Swapped networks are established and the homomorphism in between is proved. According to the topological properties of the two factor networks, the key parameters on GBSN’s topological properties are calculated, and a common quasi-shortest path routing algorithm is presented. It is proved that if the two factor graphs are vertex-transitive and Hamiltonian, with either a couple even numbers or the same number of nodes, then the composed GBSN is Hamiltonian.4) A novel Cayley graph with small-world features and good static underlying network properties for P2P is defined by group theory and a novel P2P overlay network model called CayleyCCC is introduced with the static underlying network. The P2P DHT related protocols are designed, including routing algorithm, peer joining algorithm and peer exiting mechanism. These embedding algorithms will map peers in dynamic P2P Network onto nodes in the static underlying network. Performance evaluation results quantify the advantages of CayleyCCC in terms of query path length, routing table size, and robustness relative to some recent proposals. CayleyCCC is particularly useful in distributed computing under relatively stable conditions. The evaluation metrics selected with animation process is significant for performance evaluation of other P2P Systems.