The Hypercube Structure Of A Multi-dimensional Interval Routing Algorithm And Its Fault-tolerant Algorithms And Adhoc Network Routing Algorithm

Distributed computing is very important in today's computer science and technology development. With the advance of computer networking and communication,more and more computer systems are connected to meet the need of information communicating and source sharing,which constitute distributed computer systems. The programming of distributed systems must be based on the use of distributed algorithms,so that the research on distributed algorithm naturally becomes an active field.Routing is an important technique in distributed computing system. When the network becomes large,it is impractical to maintain a complete routing table at each node. Interval Routing Scheme was introduced to reduce the size of routing tables,multi-dimensional routing scheme is the extension of interval routing scheme and it can represent all shortest paths between each pair of nodes,which turns out to be convenient when problems related to flow control aspects such as fault tolerance and traffic load balancing are considered. In multicomputer system,the efficient communication between computers is very important to improve the system's performance. Recently,hypercubes multicomputers have been drawing considerable attention from many researchers. With the development of VLSI and hardware technology,the size of the multicomputer systems is becoming larger,and the probability of processor failure also increases.With the rapid development of the information technology,people increase their need of network communication. Wireless networking is one of the essential technologies to implement the mobile computer network. There are currently two variations of mobile wireless networks. The first is known as the infrastructured network,i.e.,a network with fixed and wired gateways. The second type of mobile wireless network is the infrastructureless mobile network,commonly known as an ADHOC network. Among all proposed wireless mobile ADHOC routing protocols,ADHOC On-demand Distance Vector Routing (AODV) and Dynamic Source Routing (DSR) are the most prominent.We do research on distributed algorithms,mainly the multi-dimensional interval routing scheme on hypercube and the routing algorithms on ADHOC network. The paper is divided into the following four chapters:Chapter One is the summarization. We give the definitions of Distributed System and Distributed Algorithm,and show their development and the problems they face.In Chapter Two we give a multi-dimensional interval routing scheme on hypercube and a routing algorithm based on the compact routing table. We discuss the complexity of the algorithm. In addition,a fault-tolerant algorithm on hypercube is put forward.We briefly describe ADHOC On-demand Vector Routing algorithm and Distance Source Routing algorithm in Chapter Three and compare the two algorithms. Depending on the difference between them,we make some modification on them respectively.Chapter Four is the concluding remark. It summarizes the work of our paper,and then gives some ideas of further improvement.