The Construction And Performance Analysis Of The New Regular Networks

The connecting methods of interconnection network decide its communication ability and efficiency. Excellent network structure should have favourable characteristics such as symmetry, extensibility, recursiveness, universality and smaller communication diameter, besides, when faults occur in the network, it should have acceptable fault-tolerance. The hypercube network has outstanding structure property and evolves numerous variant structures. This paper constructs two new regular network structures by researching the structure and performance deficiency of the hypercube network, and applies profound discussions and analysis on their performance and application value.First, by referring to the structure of the crossed cube (CQn) and the definition of pair-related, in this paper, we analyze the structure character of the twisted-cube connected network (TNn), and prove that TNn is disconnected for n≥5and the number of the disconnected nodes is half of nodes in the network. Besides, by analyzing the problems of the twisted-cube connected network, we obtain a new network structure:the twisted crossed cube (TCQn), prove that the network is all connected, and make some preliminary studies on its basic network properties, such as the regularity, connectivity, fault tolerance, recursiveness, and so on, which indicates that the TCQn has the same excellent network properties as the CQn.Then, by introducing the concept of SN subnet, this paper puts forward an effective routing algorithm Route (u, v), making the communication of any two nodes in the network no more than d(u, v)+l steps, and proves that the diameter of the TCQn is [(n+1)/2]. This paper also studies the hamiltonicity of TCQn, and respectively demonstrates the embedding strategy of the mesh network, the hypercube and the binomial trees into TCQn, which expands the application range of TCQn. Furthermore, combining with TCQn and CQn, a more optimal dynamic network structure-the dynamic crossed cube (DCQn) is put forward. The network has the same network properties as TCQn/CQn, for example, the network diameter is [-(n+1)/2-]as well, what’s more, when the scale of the network is large enough, the connection of DCQn is just half of that of TCQn/CQn, which is favorable for large-scale expansion of the network, and the number of average routing steps in DCQn is much smaller, reducing the communication delay of the network.There exists another excellent new network structure——the exchanged hypercube, which lowers the network connecting complexity. The network reduces the cost of topology connecting when the scale of networks increases and has remarkable cost efficiency. According to the graphic definition of Exchanged Hypercube, this paper obtains its formulized definition, proves that the subgraphs of exchanged hypercube are isomorphic to hypercubes, proposes the concept EHS(s,t) and EHT(s,t), and on the basis of the concept, proves that there are only even circles with length no more than4, and that the vertex connectivity and edge connectivity of exchanged hypercube are min(s+1, t+1}. To enlarge the application range of the exchanged hypercube, this paper puts forwards three strategies embedding hypercubes into exchanged hypercubes as well, and proves that, when n=s+t+l, Qn-1can be embedded into the exchanged hypercube EH(s,t) homeomorphically.