The Connectivity And Diagnosability Of Directed Networks

The network of a multiprocessor system has significant impact on the performance of this system.The hyper cubes,a kind of important networks for multiprocessor systems have been applied to both commerce and research fields.With the deepening of research it is found that there are some inherent defects in the system based on the hypercube topological network.For example,the vertex degree and the diameter of the hypercube are both relatively large.In order to preserve as many of the good properties of hypercubes as possible and make up the inherent defects of hyper cubes,k-ary n-cubes were introduced In most hypercube multiprocessor architectures,each link is physically implemented by two opposite unidirectional channels.Based on this observation,bidirectional hypercubes were proposed.To reduce the cost and the complexity in constructing bidirectional networks some unidirectional networks,such as unidirectional hypercubes and unidirectional k-ary n-cubes,were introduced.Fault processors in multiprocessor systems are unavoidable.Therefore,it is very im-portant to diagnose the fault processors of systems.The diagnosability of the system is a parameter to measure the fault diagnosis ability of the system.The connectivity of graphs is an important index of the fault tolerance of networks,which is closely related to the diag-nosability.The g-good-neighbor connectivity and g-good-neighbor diagnosability are more accurate indexes than the classical connectivity and diagnosability.The g-good-neighbor connectivity and g-good-neighbor diagnosability of undirected graphs have received a good deal of attention.However,there were few corresponding results of digraphs.This paper is divided into four chapters to study the performance of the unidirectional hyper cubes,the unidirectional k-ary n-cubes and the bidirectional hypercubes with missing arcs by using the good-neighbor connectivity and good-neighbor diagnosabilityChapter 1 introduces the main concepts and research background of this paperChapter 2 first studies some properties of unidirectional hyper cubes,and then deter-mines the 1-good-neighbor(1-good-in-neighbor,1-good-out-neighbor)connectivity of uni-directional hypercubes and obtains the following:The 1-good-in-neighbor and 1-good-out-neighbor connectivity of the n-dimensional unidirectional hyper cube UQn with n≥3 are both[n/2]and the 1-good-neighbor connectivity of the n-dimensional unidirectional hyper-cube UQn with n≥4 is 2n-4.In addition,the diagnosability t(UQn),the 1-good-neighbor diagnosability t1(UQn),the 1-good-in-neighbor diagnosability t1-(UQn)and the 1-good-out-neighbor diagnosability t1+(UQn)of unidirectional hypercubes under the PM-C model are given as following:t(UQn)=t1+(UQn)=[m/2],t1(UQ3)=t1-(UQ3)=3,t1(UQ5)=t1-(UQ5)=11 and t1(UQn)=t1-(UQn)=2n-1 with n=4 or n≥6.Chapter 3 first studies some properties of unidirectional k-ary n-cubes,and then showes that the 1-good-neighbor connectivity of unidirectional k-ary n-cubes with k≥3 and n≥3 is k1(UQn)=k(n-1).In addition,we show that the diagnosability and the 1-good-neighbor diagnosability of unidirectional k-ary n-cubes under the PMC model are n and kn-1,respectively.A hypercube is a bidirectional hypercube with 0 missing arc,and a unidirectional hypercube is a bidirectional hypercube with exact half of its arcs missing.In Chapter 4,we study the bidirectional hyper cube network D with missing arcs,prove that the diagnosability t(D)of D under the PMC model satisfies t(D)≤δ-(D),and give a necessary and sufficient condition for t(D)=δ-(D).In addition,it is proved that the diagnosability t*(D)of D under the MM*model satisfies δ-(D)≥t*(D)≥δ(D).