Some Fault-tolerant Algorithm On Hybercube Graphs

Computer science develops very quickly in current world, because of the highly requirement of data computing in modern industry, including computing speed, veracity, continuity and security. Multi-computers can compute large number of data synchronously, it is steady and safe.Hypercube is one of common models used in interconnection network. During the size of the multi-computers system grow fast, it is obvious that the ratio of fault-happen grow accordingly. So it is very necessary to design a fault-tolerant routing which record optimal routing information to choose the right route and improve the performance of the whole system.At the beginning, the thesis introduces some basic knowledge including research background, research models, hypercube, and faulttolerant algorithm. Then start with a simple model named safety level to analyze the fault-tolerant property of hypercube. But this model cannot apply in networks which include fault-dot. Safety vector model solve this problem. It can use both in fault-link and fault-dot. Safety vector is a vector belongs to every dot that calculates from all of its neighbors in i hamming distance. However, it has limitation that it cannot record all the optimal routing information that actually exists.That because the vector just collect the fault information for neighbors in 1 hamming distance. Extended safety vector optimize the safety vector model that every safety vector calculates from all of its neighbors in 2 hamming distance. This algorithm enhances the veracity of fault-tolerant information for dots.This thesis summarizes the advantage of the 3 former models and presents a new model that transforms all the fault-dots into fault-links, and then treats it as a pure fault-link network. The data of this model is more closely to the really one and it can be used in more conditions.