Tree interconnection network Characteristics, advantages and disadvantages

A tree interconnection network is one in which there exists only one path between any pair of nodes. A tree interconnection network is also called a binary tree network which consists of p = 2^d – 1 processors connected into a complete binary tree at depth d – 1. Each non-root internal processor P_i, 2 < i < 2^{d – 1} – 1, is connected to three processors, P_L(i) [Left processor], P_R(i) [Right processor], and P_F(i) [parent of left and/or right processor], where L(i) = 2i, R(i) = 2i + 1 and F(i) =⌊i/2⌋. The root processor P₁ is connected to P₂ and P₃ as its left and right child respectively. The leaf processors P_i are connected to only their fathers P_F(i), 2^{d- 1} ≤ i ≤ 2^d – 1.

A binary tree interconnection network has a 1-bisector and the diameter of the binary tree is 21og₂[(p+1)/2)] which is the distance from a leaf processor up to the root processor and back down to another leaf processor. Unfortunately, tree networks require linear time to perform permutations. For example, assume it is wished to move each item from the root’s left subtree to the right subtree, and vice versa. The root is then a bottleneck since it is the only bridge between the two subtrees.

The linear arrays and star-connected networks both are special cases of tree networks. There have two different types of representation in tree networking;

Static tree networks: This network model has a processing element at each node of the tree.

Dynamic tree network: Tree networks also have a dynamic counterpart. In this tree network, nodes at intermediate levels are switching nodes and the leaf nodes are processing elements.

Characteristics of Tree interconnection networks:

• In tree networking a node has almost three links i.e. a processor can interact with three processors point-to-point.
• The degree of the tree network is three.
• Every interior node can communicate with its two children and ever node other than the root node communicates with its parents.
• It has low diameter i.e. 2 (d-1); where d is the depth of the tree.
• It has a poor bisection width of 1.
• To route a message in a tree network:
  • The source node/processor sends the message up the tree network until it reaches the node at the root of the smallest subtree containing both the source and destination nodes.
  • Then the mess is routed down the tree towards the destination node
• With a constant node degree, the binary tree is a scalable architecture but with long diameter.

Examples of Binary Tree interconnection networks:

Figure: Binary tree network

Consider the above tree interconnection network:

The depth of the tree d = 5
The total number of nodes in the tree T = 2^d – 1 = 2⁵ – 1 = 31
The degree of root node is = 2
The degree of interior (intermediate) node is = 3
The degree of leaf node is = 1
The diameter is = 2 × (d – 1) = 2 × (5 – 1) = 2 × 4 = 8.

Advantages of Tree interconnection networks:

• A tree network makes it possible to have point-to-point communication between processes.
• All processors have access to their immediate neighbors in the network and also the central processor. This kind of network makes it possible for multiple network devices to be connected to the central processor.

Disadvantages of Tree interconnection networks:

• With the increase in size beyond a point, management becomes difficult.

More Tutorials for you:

• Metrics for interconnection networks
• Automata theory languages and computation tutorial