Interconnection network

A connection network describes a technical device that has the task of establishing a static or dynamic connection between a transmitter and a receiver via an appropriate line medium in order to enable information to be transmitted .

Transmitters and receivers are transmitting and receiving stations in the broader sense, that is, they are nodes that operate communication, for example processors , workstation computers, telecommunication units, coupled computer networks , etc.

parameter

Connection networks have numerous parameters which, on the one hand, reflect their performance or central properties and, on the other hand, serve to subdivide or classify the networks.

topology

The topology is the most important parameter of a connection network. It is essentially responsible for the fundamental characteristics and limitations of the connection network. For more information, see topology (computer network) .

Connection type

The connection type is the primary characteristic used to subdivide the connection networks. Connections are either static or dynamic.

Static interconnection networks

Static interconnection networks are hard-wired. Each node has a fixed number of neighbors and corresponding direct connections (links) to them. The network itself consists only of the lines and therefore has no switching function. This is carried out indirectly via the nodes involved. Networks of this type cannot be reconfigured once they have been set up. Examples of static connection networks are grids or rings, trees and hypercubes (see topology (computer network) )

Dynamic interconnection networks

Dynamic connection networks are characterized by the fact that the connections between the nodes are implemented via coupling elements belonging to the network. These coupling elements can be arranged one behind the other in several stages, which is why this type of connection network is again divided into single-stage and multi-stage networks. A stage contains a certain number of coupling elements. More precisely, the network ensures that sender nodes are switched to receiver nodes using a permutation function. Either all n! Permutations are switched, or just a few.

Single-level dynamic interconnection networks

These connection networks consist of only one level of switching cells or just the switching cell itself. The cells are usually a more or less complex form of a crossbar , which itself is a single-stage dynamic connection network. The simplest form is the so-called beta cell, a 2 × 2 crossbar that can handle the switch positions "straight" and "crossed". Single-stage dynamic connection networks are strictly non-blocking because they can switch any permutation.

Multi-level dynamic interconnection networks

These connection networks are characterized by the fact that several stages of switching cells are connected in series. There is fixed wiring between the stages, which mostly - but not always - corresponds to one of the basic permutations. These are mainly the Perfect Shuffle Permutation and the Butterfly Permutation.

Perfect Shuffle: Sender identification (binary): i _n , i _n-1 , ..., i ₁ → Receiver identification (binary): i _n-1 , ..., i ₁ , i _n (cyclic left shift)
Butterfly: Sender identification (binary): i _n , i _n-1 , ..., i ₁ → Receiver identification (binary): i ₁ , i _n-1 , ..., i _n (interchange of LSB and MSB)

Furthermore, these networks are divided into so-called networks and NOT networks. With N nodes, networks have levels and N / 2 switching elements per level. They are relatively minimal compared to their performance data, but are usually not free of blocks. Examples of this are the Omega network , the Banyan network or the flip network. Non-log-N networks do not have these properties (above all, they are not minimal), but are often non-blocking, such as the Clos network. ${\ displaystyle \ log N}$ ${\ displaystyle \ log N}$ ${\ displaystyle \ log N}$ ${\ displaystyle \ operatorname {ld} N}$

Data stream type

According to the way in which data flows in the network, a distinction is made between circuit-switched and packet-switched connection networks. Circuit-switched networks first establish the connection when communication begins. All data then flow over the established connection, i.e. take the same route, which is why no routing algorithm is used here . Packet-switched networks divide the data to be transmitted into several packets, which then find their way through the network to their destination independently of one another. A routing algorithm is necessary for this.

Blocking and deadlock behavior

Here one considers whether and how blockages (nodes can temporarily no longer forward data because they are already transmitting other data) and deadlocks can occur and whether and how these can be resolved. The routing algorithm used plays a decisive role here. It decides whether detours are to be taken in the event of blockages or how to route around the blockage at all. Detecting and resolving deadlocks can be difficult or even impossible, depending on the topology and routing, which is why you usually try to avoid them.

Transfer rate

see transfer rate

Fault tolerance

The fault tolerance describes whether and how a connection network reacts to faults such as link or node failures or how critical the failure of some or specific nodes or links is. The topology and the routing algorithm of the network are decisive here.

Expandability

The expandability or scalability describes whether and to what extent an interconnection network can be expanded, that is to say can be expanded by additional nodes without significant characteristics of the interconnection network being lost. This mainly depends on the topology used. When it comes to expandability, it is not only the basic feasibility that is important, but also the costs involved.

costs

The costs quantify the (not just monetary) effort that has to be made to set up and operate a connection network. Here things like the degree of topology, the transmission medium used, transmission rate, routing algorithm, necessary intelligence of the hardware and the protocols used play a role.

Significance in parallel computer systems

The connection network is mainly - but not exclusively - mainly responsible for the achievable overall performance in parallel computer systems, since the work processes are divided into autonomous parallel phases and communication phases, whereby the connection network can become the bottleneck of communication here if it is several orders of magnitude slower than the networked computing nodes.

literature

W. Giloi: Computer architecture. Springer, Berlin 2001, ISBN 3540624368

Th. Ungerer: Innovative computer architectures. McGraw-Hill, Hamburg 1989, ISBN 3890281508

Th. Schwederski, M. Jurczy: Connection Networks . Teubner, Stuttgart 1996, ISBN 351902134X

H. Richter: Connection networks for parallel and distributed systems. Spectrum, Heidelberg 1997, ISBN 3827401879

AS Tanenbaum: Computer architecture. Structures - Concepts - Basics. 5th revised edition. Pearson Studium, Munich 2005, ISBN 3827371511

Th. Warschko: Efficient communication in parallel computer architectures . In: VDI reports. Row 10, No. 525

M. Sampels: Algebraic Construction of Efficient Connection Networks . Dissertation Uni Oldenburg, 1998, ISBN 3897220512

Andrew S. Tanenbaum : Computer Networks. 5th, updated edition, Pearson Studium, Munich 2012, ISBN 978-3-8689-4137-1

R. Buyya (Ed.): High Performance Cluster Computing. Volumes 1 and 2. Prentice Hall, Upper Saddle River / NJ 1999, ISBN 0-13-013785-5