Research On Reliable Communication Performance Of The Data Center Network HSDC

With the advent of the era of information explosion and expansion of data center networks,server failures have become an inevitable event.Therefore,it is important to ensure reliable communication between servers in a data center network.The data center network HSDC is based on the well-known network hypercube,which retains many superior properties of the hypercube,such as regularity and node symmetry.In addition,the data center network HSDC also has advantages that the hypercube network does not have,for example,HSDC has excellent performance in incremental scalability.As a data center network with high scalability,it is of great theoretical and practical importance to study the reliable communication performance of HSDC.In this thesis,the logical graph Hn is obtained by making the switches in HSDC transparent,where the servers in HSDC and the links between them constitute the set of nodes and the set of edges of Hn and n≥2,respectively.Then,the connectivity,fault-tolerant unicast path,disjoint paths,Hamiltonian properties,and fault-tolerant Hamiltonian properties of Hn are studied for the first time to measure the reliable communication performance of HSDC in this thesis.Connectivity is an important indicator to measure the reliable communication performance of a network.The greater the connectivity of a network,the more fault-tolerant it is,and the more reliable communication capability of the network.In addition,the connectivity is the basis for subsequent researches in this thesis.When the number of faulty nodes in the network is less than the connectivity,there exists at least one fault-free path,i.e.,fault-tolerant unicast path,between any two distinct fault-free nodes in the network,which can ensure that reliable data transmission can still take place between any two fault-free nodes in the network.Disjoint paths can reduce packet loss rate during data transmission by parallel transmission,thereby ensuring reliable communication in the network.Hamiltonian paths are often used to design wormhole multicast routing algorithms in networks to reduce congestion and deadlocks caused by tree-based multicast routing algorithms in networks.The details of the research in this thesis are as follows:(1)This thesis studies the connectivity of Hn.It is proved that the connectivity of Hn is n when n ≥ 2.Since Hn is an n-regular graph,its connectivity is equal to the degree of nodes in Hn,so Hn has maximum connectivity.(2)This thesis studies the fault-tolerant unicast path when n≥ 3 and there are no more than n-1 faulty nodes in Hn.First,a fault-tolerant unicast path construction algorithm HFPath with linear time complexity is proposed.The maximum length of the path constructed by this algorithm is obtained by analysis as 4[log n/d]+2d+1,where d denotes the Hamming distance between the nodes at both ends of the path.In addition,the performance of algorithm HFPath and breadth-first algorithm BFS are compared by simulation experiments,and the experimental results show that as the dimension of Hn increases,algorithm HFPath performs well in terms of average running rate and constructed path length.(3)This thesis studies the disjoint paths in Hn when n≥ 3.In this thesis,the disjoint path algorithm is designed from the perspective of multi-objective optimization.Firstly,three disjoint paths construction algorithms are given respectively according to the relative positions of any two distinct nodes in Hn,and the algorithm for constructing disjoint paths between any two distinct nodes in Hn is given.Then the process of constructing disjoint paths in H4 by the disjoint path algorithm is simulated experimentally.In addition,it is verified through simulation experiments that the maximum length of the path obtained by the disjoint path construction algorithm proposed in this thesis is only 3 longer than the diameter of Hn of the same dimension.This indicates that the communication delay between any two nodes in Hn is smaller in the worst case.(4)This thesis studies the Hamiltonian and fault-tolerant Hamiltonian properties of Hn.It is first proved that Hn is Hamiltonian-connected when n≥ 3.Further,an algorithm is given to construct a Hamiltonian path between any two distinct nodes in Hn,whose time complexity is O(NlogN),where N=|V(Hn)| and n≥ 3.Finally,the fault-tolerant Hamiltonian properties of Hn with faulty elements(faulty nodes or faulty edges)is studied,and it is proved that Hn is(n-3)-fault-tolerant Hamiltonian-connected and(n-2)-fault-tolerant Hamiltonian,which shows that Hn still has good communication performance with no more than n-2 fault elements.In summary,this thesis demonstrates that HSDC has good reliable communication performance in terms of connectivity,fault-tolerant unicast path,disjoint paths,Hamiltonian properties,and fault-tolerant Hamiltonian properties.In addition,this thesis also provides methods to study the reliable communication performance of other data center networks.