Construction Of Independent Spanning Trees On Folded Crossed Cubes

High performance computing is playing an increasingly prominent role in many fields such as computing-intensive applications,data-intensive applications and communicationintensive applications.In high performance computing systems,the way of communication and data exchange between processors is called interconnection network,and the inheritance relationship,topological properties,routing algorithm and construction cost of its topology can affect the overall performance of the system to a certain extent.A reasonable network topology can reduce the communication delay between processors,increase the transmission rate,expand the network bandwidth,and reduce the communication cost.The n-dimensional folded crossed cube FCQn combines the excellent properties of the crossed cube and the folded cube,and is an interconnection network with both high performance and low cost.Compared with the n-dimensional crossed cube and folded cube,FCQn has lower diameter,higher connectivity,lower network construction cost,shorter mean internode distance,and lower message traffic density.The topology of the interconnection network can be described by a graph,and the vertices(edges)in the graph correspond to the nodes(links)in the network.Independent spanning trees are a set of spanning trees that satisfy certain conditions in a graph.It can be divided into vertex-independent spanning trees(VISTs)and edge-independent spanning trees(EISTs).If there are n VISTs(EISTs)rooted at r in the interconnection network G,then there are n vertex(edge)independent paths between the vertex r and any other vertex in G.These n paths contributes to the secure distribution,reliable transmission and fault-tolerant communication of information on network.They can also be applied to the fault link recovery of IP fast rerouting.In addition,based on the definition of edge-independent spanning trees,the conditions are further strengthened to make the directed edges undirected,and the edge-disjoint spanning trees(EDSTs)can be obtained,which can be applied to the research of distributed algorithms against Man-in-the-Middle attacks and efficient collective communication algorithms.This thesis presents the study on the construction algorithms of independent spanning trees on folded crossed cubes for measuring and improving the communication performance and fault diagnosis ability of folded crossed cubes.The specific research contents are as follows:(1)Parallel construction algorithm of edge-independent spanning trees on folded crossed cubesFirstly,Algorithm DS and Algorithm DF are proposed,which are used to obtain the sequence Sx,i and the set Fx,respectively,where x ∈ V(FCQn)\{r} and i ∈ {0,1,…,n-1};then,based on these two algorithms,a parallel algorithm,called Algorithm FC-EIST,with time complexity O(n2)is proposed,which can use N processors to construct n+1 EISTs rooted at r on FCQn,where n≥1 and N=2n;finally,the corresponding theoretical proofs and simulation experiments are given to verify the correctness and time complexity of the construction algorithm.In addition,the results of simulation experiments show that when the number of network vertices does not exceed 220,the average distance-diameter ratio of these EISTs constructed by Algorithm FC-EIST does not exceed 1.4.(2)Recursive construction algorithm of edge-disjoint spanning trees on folded crossed cubesFor the problem of constructing the maximum number of EDSTs on FCQn,firstly,Algorithm EDST_Odd and Algorithm EDST_Even are proposed,which are applicable to the cases when n is odd and h is even,respectively;then,based on the two aforementioned algorithms,Algorithm Gen_EDST with time complexity O(N log N)is proposed to construct[n/2]EDSTs in FCQn,where n≥4 and N=2n;finally,the corresponding theoretical proofs and simulation experiments are given to verify the correctness of the construction algorithm.In addition,the experimental results show that using multiple edge-disjoint paths for simultaneous transmission can lead to a significant reduction in the transmission failure rate.(3)Parallel construction algorithm of vertex-independent spanning trees on folded crossed cubesFirstly,Algorithm CFlag is proposed,which determines the value of the function flag(x,Ti)corresponding to each vertex x in FCQn;then,in combination with the function flag(x,Ti),a parallel algorithm FC-EIST with time complexity O(n)is proposed to obtain the parent vertex of x in the vertex-independent spanning tree Ti,where i ∈ {0,1,…,n}.Finally,the corresponding theoretical proofs and simulation experiments are given to verify the correctness and time complexity of the construction algorithm.In addition,the results of simulation experiments show that the average distance of the n+1 VISTs constructed by Algorithm CFIST is smaller,so that the root vertex can communicate with other vertices along the paths of these n+1 VISTs with lower communication delay and communication cost,while ensuring reliable data transmission to a certain extent.