2.2.5 The Tree

The tree is a quite flexible topology with good communication properties.

Optimal tree :
An optimal tree is a tree with maximal depth and maximal number of branches at a node not larger than $d = \log_{2} P$.

In the remaining lecture we will use the notation tree always in the sense of an optimal tree.
Thus, for those trees the following statements are valid :

• $2^{d-1} < P \le 2^d$
• Max. $d$ links per node.
• Diameter: $2d - 1 = 2 \log_2 P -1$

Figure 2.5: Optimal tree in binary representation

The numbering of nodes in the binary tree bases on the Gray code.
Gray code :
The binary representations of the numbers of neighboring nodes differ in exactly one bit ( $[0,\ldots,d]$) !


Construction of a binary tree

Each node in a tree with node $000$ as root possesses as much branches as 0-bits follow the last $L$-bit in its binary representation.

Hardware: Convex-MPP with the concept of ''Fat Trees'', i.e., if a link is located closer to the root, then its bandwidth will be higher.