The Deadlock-free Routing Restrictions And Deadlock-free Routing Algorithms On Star Graph

Star Graph and Hypercube networks have been paid great attention by researchers, and are one of the most important and attractive interconnection networks hitherto, for their excellent characteristics such as regularity, symmetry, good fault-tolerance, parallelism, extensibility, and embeddable ability. Since Star Graph and Hypercube networks are of lots of similarities in their topologies, but are not the same, and in addition, novel interconnection networks with some special natures can be constructed through the combination of their special good characteristics, then the topologies and routing algorithms of Star Graph and Hypercube networks are researched synthetically and comparatively in this paper.On the researches about topologies and routing algorithms of Star Graph interconnection networks, this paper studies deadlock-free behavioral routing algorithms on star graph. First, two minimum deadlock-free routing restrictions on star graph are presented. Then the deadlock-free behavioral routing algorithm based on these two restrictions is presented. Furthermore, two classes of buffer-based deadlock-free routing restrictions on star graph are presented. Then the deadlock-free behavioral routing algorithm based on these two restrictions is presented.On the researches about topologies and routing algorithms of Hypercube interconnection networks, an overview of the current major works on this field are presented in this paper at first, and then, on the basis of these current researching outcomes, one kind of new fault-tolerant Hypercube interconnection network such as Safety Path Vectors based fault-tolerant model (SPV) is proposed. And it is proved that the new fault-tolerant model is of better fault-tolerant performances than the previous fault-tolerant models such as Optimal Path Matrix based fault-tolerant model (OPM) and Extended Optimal Path Matrix based fault-tolerant model (EOPM) separately. Finally, efficient fault-tolerant routing algorithm based on the above new fault-tolerant models is designed separately, and it is proved that the fault-tolerant ability of the fault-tolerant routing algorithm is better than that of those fault-tolerant routing algorithms based on OPM, and EOPM.