Researches Of Network Topology Construction Based On Cayley Graph And Small-world Phenomena

Performance of the network is determined by the topology of interconnection network inparallel distributed system. Many models of interconnection networks based on Cayley graphhave been proposed, such as hypercube, torus, butterfly, de Bruijn and Kautz networks.Most researches focused on a specific structure of the network intuitively. Some samenetwork structures are repeatedly proposed for different symbols. So it is necessary to use themethods based on Cayley graph to unify interconnection network topology.Small-world network interests a lot of researcher for high clustering coefficient andsmall network diameter. Network Topology based on Cayley Graph can be constructed withdeterministic small-world characteristics. The algorithms are simple and efficient if thenetwork topology base on Cayley graph has small-world phenomenon.The main contents and innovations include the following aspects:1. First, some interconnection network topologies are studied and classified by directproduct or semidirect method. Second, OTIS is extended to SN. The relationship of SN andBSN is analyzed. The relationship of BSN and basis network is proved.Finally, more generalinterconnection structure—MSN is proposed by generalizing BSN. Many researches of MSNare in progress, such as topological properties, routing and broadcasting algorithms,embedding, node-disjoint paths, etc.2. All-coupling model is designed for the subway network. Data were calculated andanalyzed by the network topology metrics, such as the number of shortest paths, node degreedistribution, clustering coefficient, robustness and so on. Research shows that theAll-coupling network topology of the subway has small-world phenomenon. Analysinghigh-density nodes and remote nodes, some advices can be provided to the subway company.3. The Cayley graph with small-world characteristics can be static P2P overlay networktopology. CHC is proposed that its static topology model is Cayley graph. CHC has manyadvantages, such as good symmetry, high clustering coefficient and small average distance.4. Cayley graph can be used as a virtual topology static model. Many good properties are found for good symmetry, such as simpler routing algorithm, higher reliability andfault-tolerant. In WDM optical networks and wireless mesh networks, Cayley graph can beused to simplify some constraints of topology design and some good law can be obtained.