(Notes from the lecture by Rajeev Balasubramonian - April 10th, 2002 - associated reading material - Chapter 10 of Culler and Singh) Types of routing: ----------------- There can be multiple independent classifications - Circuit-switched: The first packet of the message sets up the route and all subsequent packets go along that route without any header processing. For example, used in phones....the payload is high. Packet-switched: Each packet is independently routed. Since it doesn't reserve a route, it is more contention-friendly. Store-and-forward: While traversing multiple hops, each intermediate hop receives and stores all packets of the message before forwarding them on. Cut-through: Each packet is forwarded as soon as it is received. Different packets of the same message might reside on different hops....reduces latency because of the pipelining effect. Virtual cut-through: Cut-through routing, but when there is contention, the message gets buffered at the switch (resembles store-and-forward). Wormhole routing: The buffer at each switch is small, so the packets get buffered at the intermediate hops (resembles circuit-switching). Metrics that define a network: ------------------------------ Latency = overhead + routing_delay + channel_occupancy + contention_delay Bandwidth (which influences contention_delay and channel_occupancy) - local bandwidth, bandwidth out of a node - global bandwidth, sum of bandwidths on all channels - bisection bandwidth, the sum of the bandwidths of the minimum set of channels that, if removed, partition the network into two equal unconnected sets of nodes. Hardware cost - number of wires, pin count, length of wires, physical arrangement. Interconnection topologies: --------------------------- Fully Connected Network - A single large switch. Impractical. Linear Arrays and Rings - Linear array of nodes. Routing is trivial. Limited fault tolerance. Easy physical lay-out. Multi-dimensional meshes and tori - Generalization of arrays and rings, respectively. Fault tolerance exists. A d-dimensional k-ary mesh has N=k^d nodes. Bisection bandwidth = k^(d-1). To physically arrange the machine in 3D, multiple logical dimensions are embedded in each physical dimension using longer wires (Fig 10.8 in C&S). Greatly increases wiring complexity. Trees - In a mesh, the diameter and average distance increases with the dth root of N. In a tree, the routing distance grows logarithmically. In a binary tree, the node number is determined by starting from the root and using 0 or 1 depending on whether we go left or right. To route from one node to another, you go up to the lowest common parent (found by XORing the addresses of the two nodes) and then go down. Unique routes, hence no fault tolerance exists. There is a catch - the lengths of the wires increase...exponentially. Layout of O(NlogN)? Actually, only O(N) with an H-tree pattern. In essence, a tree and mesh are similar....the tree only has limited connectivity (hence, unique routes), but longer wires (hence, fewer hops per transfer). Butterflies - The problem with the tree is its lack of fault tolerance and congestion near the root. The butterfly tries to fix this by having a tree for each node, with that node serving as the root. If there is a broken link in the tree for node A, and A wants to send a message to B, but can not, it instead sends the message to C (to which it still has a route), and then uses the tree rooted at C, to send the message to B. You could further improve fault tolerance by adding more levels....that would give you some redundancy and more routes between any two nodes. Since the trees are shared, contention is still an issue. You can increase the number of routing choices by doubling the butterfly network - called a Benes network (figure 10.11 of C&S). To send a message from A to B, the message is first sent to an intermediate column C, and then routed from there. Two messages can be made to not conflict by picking particular intermediate columns for them. This has little practical significance as the communication pattern has to be known well in advance. A Benes network that is folded into itself and has bidirectional links is called a `fat-tree'. Hypercube - It is formed by collapsing all switches in a column. Hence, by traversing a single switch, a node can send a message to any node whose address differs in only a single dimension. Evaluating design trade-offs for a k-ary d-cube: ------------------------------------------------ Number of switches = N = k^d. Number of links = C = Nd. Pins per node = 2wd. Avg routing distance = d(k-1)/2. Diameter = d(k-1). Bisection width = k^(d-1) = N/k links = 2Nw/k wires. Small d ==> array High d ==> hypercube To minimize routing distance, build a hypercube. To minimize hardware cost, build an array. Fig 10.12....latency, 0 hardware cost. Fig 10.14....latency, constant pins per node. Fig 10.15....latency, constant number of wires thru the bisection width. Similar models can also be built by taking load into account. Another important parameter here is the utilization...i.e., the frequency of a message emanating from a node. Routing algorithms: ------------------- Example: Dimension order routing - First route along the lowest dimension, then along the next, and so on. It is important that the routing algorithm be deadlock-free. Each message occupies buffer space in a switch. When a message gets transferred, it writes into the buffer space of the receiver and frees the buffer space in the transmitter. Thus, buffer space in a switch can be freed only if free buffer space exists in the destination switch...that is, there is a resource dependency between channels. If there is a cycle of such resource dependencies, a deadlock can be formed. Example: Fig 10.19. To show that a routing algorithm is deadlock-free, each channel is given a number. If it can be shown that a route always uses monotonically increasing channel numbers, there can be no cycle and hence, no deadlock. Example (Fig 10.20). This is an example of breaking a deadlock by restricting the paths that packets may follow. You can also break a deadlock by restricting how resources are allocated, for example, with virtual channels (Fig 10.22). Turn-model routing abstracts the resource dependency in terms of turns. To break the cycle, only one of the turns has to be disabled. For example, West-first. This is the least restrictive algorithm....allows multiple deadlock-free routes....useful for adaptation/fault tolerance. Note that the above deadlock analysis is done for a single message and its route.