Modeling And Analysis Of Crossed Twisted Cube

After entering into information age, heavy network requirement makes the structure of network change all the time. As to meet this need, it has been proposed the concept of cube network, in which the hypercube is the most popular network structure. Many researchers drew a conclusion about the characters of hypercube though deep study. But with the deep study, it has been exposure that there are several disadvantages of hypercube. Based on the fault, the researchers go on studying and propose a series of variant networks. This paper proposed a new variant based on the crossed cube and twisted cube, which is improved in many aspects. Specific work is as follows:(1) The paper introduces the definition of crossed twisted cube based on the structure of crossed cube and twisted N-cube. Then present the topology network diagram, give the proof of isomorphism between crossed twisted cube and hypercube, and study on the diameter, connectivity and so on. Due to the properties studied above, it has been drawn a conclusion that the performance of crossed twisted cube is better than twisted N-cube.(2) In order to further study on the ability of simulation another network, this paper will study on circle embedding in the crossed twisted cube interconnection network. And then it is proved that the length of any circle is L where the range of L is3<L≤2n can be embedded into the crossed twisted cube with the dilation1in this paper. At the same time, we prove that the crossed twisted cube is Hamilton connected graph. At last, the paper proposed an circle embedding algorithm whose time complexity is O(L) in the crossed twisted cubes.(3) Since graph embedding includes the embedding of cycles and trees, this paper will go on studying characters of tree embedding after the cycles. On one hand this paper introduced the concept of complete binary tree and complete quad tree. On the other hand this paper gave the3Dview of the crossed twisted cubes with dimension of3. At last it has been drawn a conclusion that complete binary tree with the order of N can be embedded in the crossed twisted cube with dimension of N and the dilation of this embedding is2. Then it has been demonstrated the conclusion that complete quad tree of N order can be embedded into the crossed twisted cube of2N-1dimension with dilation2.(4) In order to further study on its routing properties, the paper determines fault tolerance of crossed twisted cube by researching on its local connectivity in the first place, and then proves that even though it is in circumstances of inhomogeneity of the error nodes, the network is still able to keep the whole network functioning. Then based on structural characteristics, a routing algorithm is proposed, which is proved that the path that the algorithm find is very closed to the shortest path between two nodes. After analysis and calculation, time complexity of the algorithm is O(n), which is much better than the routing algorithm in crossed cube that Efe is proposed by comparison.