Research On Topology Properties Of Cubelike Recursive Networks

Interconnection network technology is studied extensively in the field of parallel computer and computer architecture. In many interconnection network topologies, Hy-percube and its variations is a kind of interconnection network model with good topo-logical property and network parameters, and the research and application on them is attractive in the research of interconnection networks. This dissertation defines a kind of special hypercube variations, studies the network parameters and network embedding problems in detail.By analyzing of the topologies of binary recursive networks, we find that a kind of binary recursive networks interesting researchers most, have an identical characteristic: they are all obtained by interconnection with the 3-cube and twisted 3-cube as the basic models. Based on this characteristic, we define this kind of binary recursive netwroks in algebraic form, and name it "cubelike recursive networks" . Cubelike recursive networks is a special subset of binary recursive networks, but it is the most attractive in current researches of binary recursive networks.Since many properties and parameters of the network are directly related to the network topology, whether we can truly understand and correctly describe the network topology plays a vital role in drawing the correct conclusions relevant to network topology and better optimizing the networks. We analyz the topologies of cubelike recursive networks in detail, and described its topology characteristic exactly by using the concept of super-network.Network diameter is an important parameter to measure the network performance, and the size of the diameter determines the communication delay of the network, so the production of any new network is inseparable from the discussion of network diameter. For the diameters of all the cubelike recursive networks, we give their supremum and infimum, and prove the correctness of the conclusion according to the characteristic description of the cubelike recursive networks. Not only this can help people identify the concrete networks with the smallest and largest diameter in such kind of networks, but also guide people to set the maximum and minimum waiting time of message receiving in the actual algorithm.Routing algorithm is one of the most basic and important algorithm among the network algorithms and its goal is to seek the path from source to destination on the network topology graph, and it is the foundation of all other network algorithms. This dissertation provides a routing algorithm applying to all the cubelike recursive networks, and it achieves to be optimal for several very important cubelike recursive networks.Network connectivity is an important parameter to measure the reliability of the interconnection networks. This dissertation proves that all the cubelike recursive networks with the same dimension are of the same connectivity, and it shows that those variations whose diameters are less than the hypercube do not reduce the network reliability under the circumstances of reducing the diameter of hypercube.Network fault diameter is a parameter which is closely related to network connectivity, and it indicates the largest transfer delay when some of the processors in the system break down. The determination of the upper bound and lower bound of the fault diameter of the cubelike recursive networks shows that the maximum fault delay of the cubelike recursive networks will not be higher than that of hypercube.Ring embedding is another important subject of interconnection network research. The embedding of Hamiltonian cycle in the network shows that we can embed a ring having the same number of vertexes as it. Taking advantage of the topology characteristics of cubelike recursive networks, we give a construction algorithm to embed Hamiltonian cycle in it. It breaks the tradition of proving the existence of Hamilton cycle in hypercube and its variations using inductive assumption method and provides a guarantee for practical application. According to the construction algorithm of Hamiltonian cycle, we give a sufficient condition for detecting whether a cubelike recursive network is almost-pancyclicity, meanwhile we give a construction algorithm of constructing a cycle with arbitrary length in the cubelike recursive networks, and this makes it possible to apply the parallel computing algorithms used in rings in hypercube and its variations directly.