Research On Fault Tolerance And Diagnosis Of The Data Center Network BCube

The Data Center Network(DCN)is a network that connects servers in a data center through links and switches,which has a decisive impact on the performance of the data center to a large extent and can provide online cloud services.With the increasing amount of data,the scale of the data center network is also expanding,which leads to a higher and higher probability of server failure in the network.Therefore,it becomes crucial to study the reliability of the DCN.BCube is a data center network with superior properties,such as good fault tolerance,load balancing capability and small diameter.This thesis makes the switch of BCube transparent and get its logical graph BCn,k(k≥ 0 and n≥ 2).The servers in BCube constitute the vertex set of BCn,k,and the links between servers constitute the edge set of BCn,k.Then this thesis studies the reliability of BCn,k from two aspects of fault tolerance and diagnosis,including restricted connectivity and fault-tolerant unicast path algorithm,extra connectivity,extra conditional diagnosability and diagnosis algorithm in BCn,k.The research results of this thesis include the following aspects:(1)Restricted connectivity:The connectivity is an important criterion for measuring the fault tolerance of a network.In the definition of connectivity,any vertex in the graph can fail,but the probability of such a situation(For example,all neighbors of a vertex fail at the same time)is often relatively small.Thus,the traditional connectivity greatly underestimates the fault tolerance of the network.To solve the deficiency,the concept of restricted connectivity has been proposed in the literature,which adds constraints on the condition of traditional connectivity to better reflect the fault tolerance of the network.The increase of this condition indicates that the network can accommodate more faulty vertices under the premise of ensuring normal communication.This thesis proves that the 2-restricted connectivity of BCn,k is 3(k+1)(n-1)-2n,where n≥ 3 and k≥ 3.The result shows that when n is constant and k is sufficiently large,the 2-restricted connectivity of BCn,k is about three times of the traditional connectivity.(2)Fault-tolerant unicast path:When there is a vertex failure in the network,how to find a fault-free path(That is,the fault-tolerant unicast paths)from the source vertex to the destination vertex in a shorter time is an important topic to study the fault tolerance of the network.This thesis proposes a fault-tolerant unicast path construction algorithm of BCn,k under 2-restricted connectivity and the algorithm time complexity is O(κ(BCn,k)3),whereκ(BCn,k)=(k+1)(n-1)is the connectivity of BCn,k.Further the simulation experiment verifies that the algorithm has good performance in the time and length of the path construction.(3)Extra connectivity:Similar to restricted connectivity,the concept of extra connectivity has been proposed in the literature,which adds constraints on the condition of traditional connectivity to better reflect the fault tolerance of the network.This thesis proves that the 3-extra connectivity of BCn,k is 4(k+1)(n-1)-4n,where n≥ 4 and k≥ 4.The result shows that when n is constant and k is sufficiently large,the 3-extra connectivity of BCn,k is about four times of the traditional connectivity.(4)Diagnosing faulty vertices:In order to ensure the normal communication of the vertex fault network,it is necessary to diagnose and then repair or replace the faulty vertices.Therefore,it is also an important research topic to study the network diagnosis ability.This thesis proves that the 3-extra conditional diagnosability of BCn,k under the PMC model is 4(k+1)(n-1)-4n+3,where n≥ 4 and k≥4.This thesis obtains that the 3-extra conditional diagnosability of BCn,k is about four times of traditional diagnosability,when n is constant and k is sufficiently large,which can better reflect the real diagnosis ability of the network.Simultaneously,this thesis gives a fault diagnosis algorithm with a time complexity of O(M*κ(BCn,k)),where M=nk+1 is the number of vertices of BCn,k and K(BCn,k)=(k+1)(n-1)is the connectivity of BCn,k.And the correctness of the algorithm is verified by simulation experiments.