Research On The Construction Of Independent Spanning Trees On The Augmented Cube And Its Extended Network

The data center is an integral part of the "new infrastructure",and also an important infrastructure supporting social development.As the connection bridge of massive servers in the data center,the data center network largely determines the computing and storage capacity of the data center,which has become a research hotspot in the academic and industrial circles.In recent years,many kinds of data center networks are designed based on interconnection network.More and more research work is carried out around interconnection network and data center network,in which the research on independent spanning trees occupies an important position.Independent spanning trees are important criteria for evaluating the quality of a network.They cannot only be used to improve the reliability and communication performance of a network,but also have important applications in the diagnosis of fault nodes.The augmented cube is an important variant of the hypercube(a common interconnection network),which has the properties of low diameter,regularity,and scalability.As an extended network of the augmented cube,the AQDN is a server-centric data center network,which not only retains many superior properties of the augmented cube,but also has large network capacity and good routing performance.In this thesis,we deeply study the construction method of independent spanning trees on the augmented cube and its extended network.The main work is as follows.1.Parallel construction of edge-independent spannning trees on the augmented cube.(1)We interpret the relationship between the augmented cube and hypercube from another perspective,and propose a decomposition method,which can decompose the ndimensional augmented cube into three structures with disjoint edges,one of which is an n-dimensional hypercube,and the other two are both isomorphic to an(n-1)-dimensional hypercube.(2)We introduce the Hamming distance Latin square matrix into the construction of edge-independent spanning trees on the augmented cube,and construct 2n-2 edgeindependent spanning trees on the augmented cube.(3)We design a parallel construction algorithm with the time complexity of O(log2N),where N is the number of vertices in the n-dimensional augmented cube.2.Research on the construction of completely independent spanning trees on the AQDN network.(1)We propose a construction method of n-1 edge-disjoint Hamiltonian paths on the n-dimensional augmented cube,and prove that the number of Hamiltonian paths constructed is optimal.(2)We propose a method to construct n-1 completely independent spanning trees on the n-dimensional AQDN networks.This is the first time that the relationship between the number of completely independent spanning trees and the dimension of data center network is established,and it is proved that the number of completely independent spanning trees constructed is optimal.The decomposition method of the augmented cube proposed by us is an important foundation of the research content in this thesis.Furthermore,this method can be used to study other properties of the augmented cube and its extended network.In addition,the construction method of completely independent spanning trees on the AQDN network proposed in this thesis has important reference significance for the research of completely independent spanning trees on other data center networks.