Study Of Several Types Of Network Structure And Parameters

If a vertex represents a node of processor (or a station) and an edge between two vertices a link (or connection) between those two processors, an interconnection network can be modeled as a graph G. Considered the requirement of smaller communication delay and bigger fault tolerant in message transmission, and the requirement of physical limitation and economic factors in the design of a network, we'll study the parameter such as wide diameter, fault tolerant diameter first. Then we'll analyze the properties and structure of some specific networks: n-cube, m-ary n-cube, GHC, n-star etc. Let C_n be the cycle with n vertexes. Let us define C ( n,t)to be the set of the resulting graph by adding t edges to C_n. Define: h ( n,t)= min{d2 (G)G∈C(n,t)}. The computation of h ( n,t)is brought out in [12] as a open problem. In this paper, this problem is studied. As a popular network topology, n-cube has many good properties. The generalized hypercube (GHC) structure not only has the similar properties of n-cube but also break out the limit of the number of vertices N must be the power of 2 in n-cube. In this paper, using the routing algorithm in [9] we calculate the wide diameter and fault diameter of Q ( m_n m_n-1 Λm₁)and Q_n(m). Moreover, the optimal problem of the structure of GHC is discussed here. The connectivity generalization introduced by Esfahanim and Hakimi can be used to model the fault-tolerant analysis of network's with forbidden faulty sets [10], ?v ∈V(G ),A (v)?F, where F is the set of fault vertices. In this issue the connectivity and fault diameter of Q ( m_n m_n-1 Λm₁)andQ_n(m)is computed. The n-star graph as an attractive alternative of n-cube is studied in capture 4, and compared with n-cube in basic parameter, structure, routing etc. Arrangement graph network and (n,k)-star network are introduced in this paper as generalization of n-star. More attention is paid on Cayley graph this years, because of the good topological properties such as regularity, symmetry….When designing a strongly hierarchical network, the Cayley graph will be the first topological model. The Cartesian product of interconnection networks is a good method for combining desirable properties of component networks. We prove some more properties of product graph in this paper and conduct a comparative study between some classic networks.