Conditional Embeddings And Fault-tolerance In Interconnection Networks

The invention of electronic computers has pushed the rapid development of in-formation technology. Along with the quick incleasing of the quantity of information and the amount of calculation, there is a pressing need to improve the storage and computing power of computers. However, the computer has a bottle-neck, which is decided by the manufacture process, in its CPU size. To solve this contradiction, scientists have created parallel computers which take some famous interconnection networks as underlying topology. For improving its performance dramaticlly, the parallel computer has its multiple logic or arithmetic units connected to perform parallel operations or parallel processing. Among the many interconnection net-works, linear arrays and rings arc the most fundamental and the most important. The embedding property is an important measurement to determine if a network topology is suitable for a real application where mapping paths and cycles into the network topology is required. Therefore, the problem of edbedding paths and cy-cles into interconnection networks has become an attractive issue and drawn much attention.In real systems, failures of components and communication channels arc in-evitable, which implies that nodes and links in corresponding interconnection net-works arc unavoidable. Therefore, when embedding paths and cycles into the in-terconnection networks, these paths and cycles can not pass through faulty com-ponents. Besides, if some nodes or links of a system arc damaged, the complete interconnection network is not available any more. In this scenario, people hope that the damaged network has as many good propcrities as possible. Thus, fault tolerance of interconnection networks has become an important issue. On the other hand, people hope that the selected paths and cycles pass through some prescribed links, which makes edmedding paths and/or cycles passing through prescribed some edges into interconnection networks more meaningful.The thesis consists of six chapters. In Chapter1, after a brief introduction to the contents and significance of this work, the used basic notation and terminology on graphs and the properities of some famous interconnection networks, we give a survey on research advance of related works and list our main results. The problem of embedding cycles passing through prescribed subgraphs (especially, linear forests and paths) into k-ary n-cubes are studied in Chapters2,3and4. The problem of fault tolerance in bubble-sort networks and star networks is investigated in the last two chapters.On the problem of embedding hamiltonian cycles passing through prescribed linear forests into fault-free k-ary n-cubes, in Chapter2, we prove that for an arbi-trary linear forest L with at most2n-1edges in a k-ary n-cube (n>2, k>3), there is a hamiltonian cycle passing through L. This generalizes some of the results in [97].On the problem of embedding hamiltonian cycles passing through prescribed linear forests into3-ary n-cubes with faulty edges, in Chapter3, we prove that for an arbitrary linear forest L with at most m=2n-1edges in a3-ary n-cube (n≥2), if the number of faulty edges does not exceed n-[m/2]-1, then there is a fault-free hamiltonian cycle passing through L. This extends the main result in [59] to3-ary n-cubes.Pancyclicity is an more refined measure to evaluate an interconnection networks. On the problem of embedding cycles of various length passing through prescribed linear paths into k-ary n-cubes, in Chapter4, we prove that for an arbitrary path P with at most2n-1edges in a k-ary n-cube (n≥2, k≥5odd), there are cycles of length from (k-1)(n-1)/2+k to kn such that they pass through P.The fault tolerance of interconnection networks is usually measured by how much of the original network structure is preserved in the presence of given number of faulty nodes and/or links. On the fault tolerance in bubble-sort networks, we investigate FB(n, k)(resp.fB(n, k)), the minimum number of faulty nodes (resp. links) that make every (n-k)-dimensional sub-bubble-sort graph faulty in Bn under node(resp. link) failure model. For some special k's, we derive the value of FB(n, k) and fB(n, k). By constructing mappings in an elegant way, we obtain an upper bound on FB(n,2) and fB(n,2). Similarly, we obtain an upper bound on FB(n,2) and fB(n,2), too. Connectivity can also evaluate the fault tolefance of interconnection networks to some extent. The presence of node and/or link failures will fail the entire net-work and maybe the network is not connected any more. In this scenario, people hope that every remaining component has undamaged subnetworks (i.e., smaller networks with the same topological properties as the original one). Under this con-sideration, k-embcdding-restricted (edge) connectivity of recursive interconnection networks under embedding restriction is proposed. Furthermore, we determine the k-embedding-restricted (edge) connectivity of Sn for some small k's.