The Complete Interconnection Network Model: The most general static or fixed interconnection scheme is the complete interconnection network in which every processor is directly connected to every other processor therefore routing of message between processors becomes a straightforward task. Since the diameter of complete interconnection network is only one (D = 1), so it can perform any permutation in one cycle. However, it is physically unrealistic for several reasons. An arbitrarily large number of communication links can’t enter a processor because of physical fan-in limitations, so only very small machines would be constructible. Moreover, the degree of complete interconnection network is ‘p-1’ having ‘p’ processor and the number of its communication links is ‘P(P-1)/2’, the space it would occupy and the length of the longest communication link increases very rapidly as the number of processor ‘p’ increases. The complete network is interesting as a theoretical model since algorithmic lower bounds for this model are automatically lower bounds for all fixed interconnection networks.
Characteristics of Complete Interconnection Network (CIN):
- CINs guarantee fast delivery of information from any source node to any destination node in the network. Only one link has to be traversed.
- The number of communication links or connecting wires in a CINs network is given by N(N-1)/2.
- The delay complexity of CINs, measured in terms of the number of links traversed as messages are routed from any source to any destination is constant, i.e. O(1).
Example of Complete Interconnection Network:
1.
Example (1) of Interconnection network
The above complete interconnection network having N=6 nodes and/or processor.
A total of communication links required by the network are = N(N-1)/2
= 6 × (6-1) /2
= 6 × 5 / 2
= 15
Total 15 links are required in order to satisfy the complete inter connectivity of the network.
2.
Example (2) of Interconnection network
Example 2 of complete interconnection network having N=8 nodes and/or processor.
A total of communication links required by the network are = N(N-1)/2
= 8 × (8-1) /2
= 8 × 7 / 2
= 28
Total 28 links are required in order to satisfy the complete inter connectivity of the network.
Advantages of Complete Interconnection Network:
- The diameter of CINs = 1
- Bandwidth scales with processor p.
- Non-blocking
- It is difficult to partition network.
Disadvantages of Complete Interconnection Network:
- Number of communication links grows O(p2).
- Fan-in (and out) at each node grows lineally with p.
Also Read:
