Dissertation > Excellent graduate degree dissertation topics show

On Path and Cycle Embeddings of Fault-tolerant Networks

Author: DuZhengZhong
Tutor: XuJunMing
School: University of Science and Technology of China
Course: Applied Mathematics
Keywords: Hypercube networks University of Science and Technology of China Even cycle Point of failure Interconnection network Network topology Doctoral Dissertation Lemma Sub-networks Part of Fig.
CLC: O175.5
Type: PhD thesis
Year: 2006
Downloads: 124
Quote: 0
Read: Download Dissertation

Abstract


Interconnection networks are usually represented by a graph G=(V, E), where the set of vertices V(G) represents processors, and the set of edges E(G) represents links between processors. Many interconnection network topologies have been proposed in the literature for the purpose of connecting hundreds or thousands of processing elements. Among these topologies the hypercubes, denoted by Qn, is one of the most popular topologies. On the other hand, linear arrays and rings, which are two of the most fundamental networks for parallel and distributed computation, are suitable for developing simple algorithms with low communication costs. The implementation of these algorithms in the hypereubes is an embedding of paths and cycles into the hypercubes. Reliability is the most useful measure of a networks performance. It is useful to consider faulty networks because node faults or link faults may occur in networks. In this dissertation, we discuss the embedding of paths or cycles into the faulty hypercubes or the faulty folded hypercubes. It consists of five chapters, where Chapter Three and Chapter Four are main parts.In the first chapter, we introduce the background of our works.In the second chapter, we introduce graph-theoretical terminology and notation used in our discussion. We also introduce the concepts of fault tolerance and graph embedding. And the definitions of hypercubes and folded hypercubes. Then we list some known results on them.In the third chapter, we study the embedding of paths or cycles into faulty hypercubes. We get four main results as follows.1. For any set Fe of faulty edges of Qn(n≥4) with |Fe|≤n-1, every edge of Qn-Fe lies on a cycle of every even length from 6 to 2n inclusive provided all edges in Fe are not incident with the same vertex.2. For any set Fe of faulty edges of Qn(n≥2) with |Fe|≤n-2 and every pair (u,v) of nodes in Qn-Fe, there exists a uv-path of length (?) with dQn(u, v)+2≤(?)≤2n-1, 2|((?)-dQn(u,v)). If dQn(u,v)≥n-1, there exists a uv-path of length dQn(u, v).3. For any faulty node set Fv of Qn(n≥5) with |Fv|=2n-3, Qn-Fv contains a cycle of even length at least 2n-2|Fv|.4. For any set Fv of faulty nodes and set Fe of faulty edges of Qn(n≥3) with |Fv|=2n-4,|Fe|≤2n-5, Qn-Fv-Fe contains a cycle of even length at least 2n-2|Fv| provided every node of Qn-Fv-Fe incidents with at least two non-faulty edges.In the forth chapter, we study the embedding of paths or cycles into faulty folded hypercubes. We get three results as follows.1. For n≥3, if n is odd, then FQn is (n-1)-edge-fault-tolerant edge-bipancyclic; if n is even and FQn has at most n-1 faulty edges, then every non-faulty edge of FQn lies on a fault-free cycle of every even length from 4 to 2n and every odd length from n+1 to 2n-1.2. For any set Fe of faulty edges of FQn(n≥3) with |Fe|≤2n-3 and every node of FQn-Fe incidents with at least two non-faulty edges, FQn-Fe contains a hamiltonian cycle.3. For any set Fe od faulty edges of FQn(n≥3), if n is even and |Fe|≤n-2, then any two nodes of FQn-Fe are joined by a fault-free hamiltonian path; if n is odd and |Fe|≤n-1, then any two different colored nodes of FQn-Fe are joined by a fault-free hamiltonian path and any two same colored nodes of FQn-Fe are joined by a fault-free path of length 2n-2.Conclusions and some problems to be studied further are in the fifth chapter.

Related Dissertations

  1. Periodic Solutions for Second Order Nonlinear Equations with Singular Vector φ-Laplacian-Like Operators,O175
  2. IGMP packet Internet IP-level topology measurement method study,TP393.02
  3. Existence of Solutions for the p-Laplacian Equations with a Hardy-Sobolev Operator,O175.25
  4. About Borel-Cantelli Lemma Exttetion and Applaction,O211
  5. Hadoop Distributed File System (HDFS) Study Reliability and Optimization,TP316.4
  6. DTN in urban road network modeling and evaluation,TN929.5
  7. The Research and Design of Wireless Position System Based on ZIGBEE,TP212.9
  8. Post-Olympic era Chinese sports newspaper Challenges and Strategies,G219.2-F
  9. Improved algorithms of the network topology tomography,TN915.02
  10. Study on Id-based Signature Scheme Without Trusted Center,TN918.1
  11. Second-order pulse homoclinic solution of differential equations and Boundary Value Problems,O175.8
  12. 0.4kV Low Voltage Distribution Resource Management System,TM769
  13. Research and Application of Work and Operation Tickets in Power System,TM769
  14. Complexity of Public Transport Network in Tianjin,U491.17
  15. Jinan Vocational College campus network transformation,TP393.18
  16. Research on Router Level Network Topology Discovering Technology,TP393.02
  17. Design and Implementation of the SNMP-Based Network Topology Discovery System,TP393.02
  18. Research about Topology Fault-tolerance Scheme in Wireless Multi-hop Networks,TN929.5
  19. Design and Implement on IP Broadband Networking Optimization Support System,TN915.09
  20. The Research of Topology in Network on Chip,TN47
  21. A Solution for Two Elliptic Partial Differential Equations,O175.25

CLC: > Mathematical sciences and chemical > Mathematics > Mathematical Analysis > Differential equations, integral equations > Integral equation
© 2012 www.DissertationTopic.Net  Mobile