In the first round, each leaf chooses a random number k and performs a D-H key exchange with its sibling leaf, which has a random number j, and the resulting value g k× j (mod p) is saved as the random value for the parent node of the above two leaves. Thus the octopus protocol can be used to establish a shared key for a node set containing an arbitrary number of nodes. The octopus protocol removes the assumption and extends the hypercube protocol to work with an arbitrary number of nodes. The hypercube protocol assumes that there are 2 d network nodes. The resulting value g m × n (mod p) is saved as the random value for the parent node of the above two nodes.Īfter d rounds, the root of the complete binary tree contains the established shared secret s. In the ith round, each node at the i − 1 level performs a D-H key exchange with its sibling node using the random numbers m and n, respectively, that they received in the previous round. In the first round, each leaf chooses a random number k and performs a D-H key exchange with its sibling leaf, which has a random number j, and the resulting value g k × j (mod p ) is saved as the random value for the parent node of the above two leaves. D-H key exchanges are performed from the leaves up to the root. All the nodes are put in a complete binary tree as leaves, with leaves at the 0–level and the root at the d-level. This algorithm can be explained using a complete binary tree to make it more comprehensible. The novelty of this architecture has resulted in several experimental and commercial products such as the Cosmic Cube, Intel iPSC, Ametek System/14, NCUBE/10, Caltech/JPL Mark III, and the Connection Machine. Since several common interconnection topologies such as ring, tree, and mesh can be embedded in a hypercube, the architecture is suitable for both scientific and general-purpose parallel computation. However, the structure is not modularly expandable and expansion involves changing the number of ports per node. There are k alternative paths between any two PEs, which is a good situation from the point of view of fault-tolerance. The total number of PEs in a k‐dimensional hypercube is 2 k and the total number of links and the diameter are 0.5 × 2 k k and k, respectively. In general, a k‐cube is defined as the structure resulting from two ( k − 1)-cubes after the corresponding nodes of these two ( k − 1)-cubes are connected by links. Two 0-cubes connected by a line form a 1-cube. There is an elegant recursive definition of hypercube. Since each node is representable by k bits, it has k directly connected neighbors. Two nodes in the hypercube are directly connected if their node addresses differ exactly in one bit position. Ī hypercube is a k‐dimensional cube where each node has k‐bit address and is connected to k other nodes. BASU, in Soft Computing and Intelligent Systems, 2000 Hypercube. The extra nodes of degree 2 have a very small impact on the properties that are of interest to us, and we will therefore restrict ourselves to the case k = n. This will yield a CCC(n, k) network with k2 n nodes. In principle, each cycle may include k nodes with k ≤ n with the additional k – n nodes having a degree of 2. The resulting CCC(n, n) network has n2 n nodes. In general, each node of degree n in the hypercube H n is replaced by a cycle containing n nodes where the degree of every node in the cycle is 3. Each node of degree three in H 3 is replaced by a cycle consisting of three nodes. A CCC network that corresponds to the H 3 hypercube (see Figure 4.9d) is shown in Figure 4.11. An alternative is the Cube-Connected Cycles (CCC) which keeps the degree of a node fixed at three or less. A node must have n ports, which implies that a new node design is required whenever the size of the network increases. However, these are achieved at the price of a high node degree. The hypercube topology has multiple paths between nodes and a low overall diameter of n for a network of 2 n nodes.
0 kommentar(er)
