Research On Fault-Tolerant Path-Embedding And Fault-Tolerant Cycle-Embedding Of Interconnection Networks

The development of big data is closely related to Internet of Things(IOT)and Cloud Computing.How to use a good network topology to interconnect thousands of servers,memories,routers,switching devices and computer systems of data center of IOT and Cloud Computing(called interconnection network)to make the system work efficiently and stably is one of the core problems to be solved at present.Interconnection network will inevitably have some malfunctions during the running time,such as malfunctions in routers,switches,and communication links and so on.For a given interconnection network,how many nodes and links can be tolerated to fail at the same time,while communication between any two nodes in the remaining sub-networks can still be maintained,which is called fault tolerance of networks.High reliability of interconnection network has always been one of the important goals of network designers.The graph embedding is an important feature to measure the performance of an interconnection network,which determines whether some basic networks such as paths,cycles,grids,and trees can operate efficiently on this network.The fault-tolerant Pancyclicity and fault-tolerant Panconnectivity of networks are widely used in practical problems to measure whether a network can still embed cycles of any length and paths of any length in cases of networks failure.This dissertation mainly studies fault tolerant Hamiltonian-Connectivity,fault tolerant Panconnectivity and fault tolerant Edge-Pancyclicity of several hypercube variant networks.The main studies are as follows:Firstly,we study the fault-tolerant Hamiltonian connectivity and fault-tolerant Panconnectivity of n-dimensional twisted hypercube-like networks THLNs,two results are proved as follows.Let F(?)V(THLNs)UE(THLNs)with |F|?n.-2.Then for any fault-free vertices-pair(u,v)in THLNs,there is a fault-free Hamiltonian path Puv joining u and v excepting(u,v)being a weak vertices-pair(for any given F,there is at most one weak vertices-pair).Let F(?)V(THLNs)U E(THLNs)with |F|?n-2.Then for any fault-free vertices-pair(u,v)in THLNs and length l(2n-1-1 ?l?|V(THLNs-F)|-?-1),there is a fault-free path Puv of length l joining uLand v,where ?=1 for(u,v)being a weak vertices-pair;?=0 for(u,v)being a normal vertices-pair.The two results show that the number of fault tolerant Hamiltonian-Connectivity and fault tolerant Panconnectivity of the twisted hypercube-like networks THLNs can be increased from n-3 to n-2,and without adding restrictions to each vertex,the fault tolerant upper bound of Hamiltonian-Connectivity and Panconnectivity of THLNs is sharp.Secondly,we study the fault tolerant Hamiltonian-Connectivity and fault tolerant Panconnectivity of n-dimensional augmented cubes AQn.two results are proved as follows.Let F(?)V(AQn)UE(AQn)with |F| ?2n-3.Then for any fault-free vertices-pair(u,v)in AQn,there is a fault-free Hamiltonian path Puv joining u and v excepting(u,v)being a weak vertices-pair(for any given F,there is at most one weak vertices-pair).The result shows that the number of fault tolerant Hamiltonian-Connectivity of AQn can be increased from 2n-4 to 2n-3,and without adding restrictions to each vertex,the fault tolerant upper bound of HamiltonianConnectivity of AQn is sharp.Let F C V(AQn)? E(AQn)with |F|?2n-4.Then for any fault-free vertices-pair(u,v)with distance d in AQn and length l(max {d+2,4} ?l?V(AQn-F)|-1),there is a fault-free path Puv of length l joining u and v.The result shows that the number of fault tolerant Panconnectivity of AQn can be increased from 2n-5 to 2n-4,and the fault tolerant upper bound of Panconnectivity of AQn is relatively better so far.Finally,we study the fault tolerant Edge-Pancyclicity of n-dimensional mobius cubes MQn,two results are proved as follows.Let F(?)V(MQn)U E(MQn)with |FI?n-3.Then for any fault-free edge e and ll(6?l?|V(MQn-F)|),there is a fault-free cycle with length l containing edge e in MQn-F.Let F(?)V(MQn)U E(MQn)with |F|? n-2.Then for any fault-free edge e and l(7-i?l?|V(MQn-F)|),there is a fault-free cycle with length l containing edge e in MQni-F(i=0,1).The two results show that,when |FI?n-3,the cycle length of Edge-Pancyclicity of MQn can be improved from 2n-2?L?V(MQn-F)| to 6<l?|V(MQn-F)|.When|F|?n-2,the cycle length of Edge-Pancyclicity of MQn can be improved from 2n-1?l?|V(MQni-F)|to 7-i?l?|V(MQni-F)|(i?0,1).And the lower bound of cycle length is sharp when the number of faulty elements is n-3 and n-2 respectively,.The results of the dissertation show that when twisted hypercube-like networks THLNs,augmented cubes AQn,and mobius cubes MQn are used as the data center network topologies,they have better reliability and robustness.They will provide important theoretical guidance for the design of interconnection networks,the quantitative analysis and evaluation of network performance,and will provide further theoretical basis for the network topology design of high efficiency,stable and energy saving new data center and the design of the interconnection networks for next generation super-large-scale supercomputer systems.