Question $3$

Consider a $4\backslash$times $4$ Hypercube network, as shown in Figure $1$ below. The

dimensions of this $4\backslash$times $4$ hypercube are depicted in the figure. Utilizing

the tag routing technique $($E$-$cube routing algorithm$),$ illustrate the

sequence of steps to route messages from node $(0100)$ to node $(1001).$

Provide a comprehensive account of the routing process, indicating all

intermediate nodes along the path between the source and the

destination. $[$Word Limit not Applicable$]$

Note:

The address bits in the hypercube signify its four dimensions in the

following manner: the leftmost bit represents dimension $0,$ followed by

dimension $2($the second bit from the left$),$ then dimension $1($the third bit

from the left$),$ and lastly, dimension $0($the rightmost bit$).$Figure $1$: $44$ Hypercube

Note:

The address bits in the hypercube signify its four dimensions in the

following manner: the leftmost bit represents dimension $0,$ followed by

dimension $2($the second bit from the left$),$ then dimension $1($the third bit

from the left$),$ and lastly, dimension $0($the rightmost bit$).$

The following figure illustrates how the dimensions are numbered within

the hypercube.

Figure $2$: Dimensions of the Hypercube