Interconnection Networks
Given by Prof. Derek Chiou
There are different properties that define an interconnection network. It includes topology which specifies the way switches are wired. Topology is important and affects many aspects but with commodity switch chips, slowly becoming a non-issue. Routing defines the way the navigation inside the network is done. It usually can be either static, meaning that it is predefined in the design time or adaptive, meaning that it might change based on the dynamic circumstances (like contentions for example). Finally, there are buffering and flow control, defining the intermediate storage abilities of the network and the way it operates.
A packet is networks unit of transfer. A message is clients unit of transfer i.e. the next network layer above the packet level. A flit (flow control digit) is a unit of transfer in the layer of network’s flow control i.e. the layer bellow the packet layer. A channel is a single logical connection between two nodes. Node is a router with-in the network. A router is said to have radix of k or k-ary radix if it has k inputs and k outputs.
The crossbar is among the simplest interconnection networks for discussion. Every unit is connected to every unit and a centralized control required. The main disadvantage of the crossbar is that it scales as N^2.
Butterfly network doesn’t require centralized control. Still the distance between any to end nodes is constant and hence the propagation delay. Therefore we can say that the butterfly interconnect network doesn’t have any locality properties i.e. it doesn’t matter with which end node to communicate, no advantages to close neighbors for example.
Mesh network introducing an interconnection forming a grid are somehow the most intuitive and probably popular as well interconnection networks. That’s probably thanks to the fact that they are relatively easy and straight forward to build mesh interconnection networks relatively to others. It said to be k-ary n-mesh if k is the size of a dimension and n is the number of dimensions.
Torus interconnection network is natural extension of the mesh. Logically it is achieved by connecting all the pairs of edge nodes in all the dimensions. It results cutting the worst amount of required hops by factor of 2. However, implementing a torus interconnection network straight forward would result one link (channel) to be significantly longer (and therefore slower) than all others. Moreover, this ratio would increase relatively to increase in number of nodes. The solution is to build folded rings of torus i.e. each node is connected to the next 2nd (skipping one node). The nodes skipped, form the backward part of the circle. Although this way the length of the channel (link) doubled now, this penalty is not scaling with the increase of nodes. The main advantage of the torus interconnection network over the mesh is its symmetry.
Hypercube interconnection network assumes that the number of nodes is power of two. It is constructed recursively, each time the size of the network is doubled and each node is connected to its clone. Hypercube interconnection network provides a high connectivity resulting short latencies and fault tolerance. The longest path would be of logN hops (like in butterfly interconnection network) and/but there defiantly are locality properties.
Fat tree interconnection network somehow reminds 2 back-to-back butterfly interconnection networks where one is used to go ‘up’ towards the big crossbar and one to go ‘down’ towards the destination node. The up path is chosen randomly and the down path is deterministic. Due to redundancy it introduces fault tolerance.
Clos interconnection network, introduced by Clos while with AT&T in the 50s is structured out of 3 stages. Each side stage is completely connected to the middle stage. Marking m as number of middle switches, n as number of input/output ports, and r as number of input or output switches. Clos network will be strictly non-blocking i.e. in any order of additions of ‘calls’ all inputs can be connected to all outputs if m≥2n-1. If only m≥n, the network is rearrangeably non-blocking, means for any additional call, the existing calls can be rearranged so it can occur.
Due to various reasons, networks are often bellow their 100% efficiency. A speedup (overcapacity) is a method of utilizing channels in higher frequencies. It is often used to meet the requirements of the interconnection network.
Two main switching approaches are circuit and packet switching. In circuit switching the whole path is allocated for a specific transmission and released only when it ends. No one else can use these resources (channels/buffers) during that time. It achieves relatively high bandwidth and low latency, however the set-up time is and expensive overhead. In packet switching, there is no need in allocating/deallocating resources, however, each packet is switched if link/channel is available and can be slower.
Bisection bandwidth is one of the metrics often used to evaluate an interconnection network. It is defined as the minimum number of channels spanning two halves multiplied by a single channel’s bandwidth. For example, in a ring the bisection is 2L (2 channels * bandwidth L of each). Therefore, to remain stable in the worst case it should maintain N/2 ≤2L since in worst case all the nodes on one side would issue traffic to the other side (across the 2 links whom total bandwidth is exactly 2L). For the average/random case stability, only half of the nodes will issue traffic to the other side, therefore, it should hold only N/4 ≤ 2L.
Routing is actually the navigation policy inside the network. Similar to the decision making on choosing the driving path on the road, there are decisions required for choosing paths of the traffic inside the interconnection networks. Different approaches (static/adaptive) are available. Several aspects should be taken into account when designing routing approach. The network might be irregular (for example mesh or hypercube missing some of the links) either intentionally or due to failure (yield). It might be that several paths exist between a source destination pair. Routing should define how a path to be taken will be chosen. Routing decisions can be done in distributed manner (by each node/router) or in centralized manner (as in crossbar).
Interconnection can severely limit routing. For example, in butterfly interconnection network, there exists only a single path between any source and destination. Therefore, in case at least one of the channels/links along that path are in use, the packet will be blocked. Some interconnection networks have very natural forms of routing. For example in hypercube, the SRC XOR DST can be used to determine routing path.
