Question

E-Cube algorithm:

1. for source A and destination B, result = A XOR B

2. for each non-zero bit in the result starting from the least significant (right most) travel along that dimension

Using the above algorithm give the sequence of hops, node by node, for the following source and destinations on this hypercube:

AQ3 ю. AQ r000 1001 0010 101p.. 001 1011 1100, 1101 0110 Ц10

1.0000→1111

2.1111→0000

3. 0101→1010

4. 1100→1000

5. 0001→1000

6. 0010→1111

Answer 1

ANS:

Consider the hypercube shown in Figure , let Ps = 0000 and Pd = 1111 represent the source and destination nodes for a message. Node Ps computes 0000 XOR 1111 = 1111. In the first step, Ps forwards the message along the dimension corresponding to the least significant bit to node 0001. Node 0001 sends the message along the dimension corresponding to the most significant bit (0001 XOR 1111 = 1110). The message reaches node 0011.Node 1100 sends the message along the dimension corresponding to the most significant bit (1100 XOR 1111 = 1100).The message reaches node 0111. Node 0111 sends the message along the dimension corresponding to the most significant bit (0111 XOR 1111 = 1000).The message reaches the node 1111. which is the destination of the message.