2.2.7 The DeBrujin network

The topologies regarded so far possess the characteristics specified in table 2.8.

Figure 2.8: Characteristics of topologies

While with ring/torus the number of links is independent from the number of nodes (but the diameter rises), in a tree/hypercube the number of links have to increase with the number of nodes (in ancient times, 10 years ago: problem of manufacturer). The ideal topology would be one with a diameter of order ${\mathcal{O}}(\log_2(P))$ which requires only a constant small number of links per node.
The DeBrujin network is exactly such a topology. First some definitions:

• Left Shuffle [LS] $=$ ISHFTC($b , 1 , d$) (called Link 1)
  

• Right Shuffle [RS] $=$ ISHFTC( $b , -1 , d$) (called Link 2)
  

• Left Shuffle Exchange [LSE] $=$ IOR(ISHFTC($b , 1 , d$),$2^{d-1}$) (Link 3)
  

• Right Shuffle Exchange [RSE] $=$ IOR(ISHFTC( $b , -1 , d$),$2^{d-1}$) (Link 4)
  

• A network of dimension $d$ possesses $2^d$ nodes and $2^{d+1}-2$ (directed) edges.
• Each node, excluding nodes 0 and $2^d-1$, has exactly 4 links. Nodes 0 and $2^d-1$ need only 2 links, the remaining links can be used for communication with the outer world.
• The graph of the networks consists only of even nodes.
  $\Longrightarrow$ Graph can be passed through without overlap.
  $\Longrightarrow$ Ring is embedded.
• Diameter is $d$.

Figure 2.9: DeBrujin network $d=3$ : 8 nodes, 14 edges

The author does not know any commercial or non-commercial realization of the DeBrujin network.


Exercise 5:

For which nodes $i=0,\ldots,2^{d}-1$ in a de Brujin network the following relations hold ?

$$\textrm{RightShuffle} (i) = \textrm{LeftShuffle}(i) \;\;\; \textrm{resp.}$$

$$\textrm{RightShuffleExchange} (i) = \textrm{LeftShuffleExchange}(i)$$

Hint: Differentiate whether $d$ is even or odd.

Exercise 6:

Represent a de Brujin network with $d=4$ !

Exercise 7:

Prove that the diameter in a de Brujin network is equal to the dimension $d$ !