Previous | Next --- Slide 28 of 45
Back to Lecture Thumbnails

What are some advantages of having direct network (or indirect network)? I assume that the reason we distinguish the two is because one of them has clear advantages over the other (i.e. do direct networks generally cost less when it comes to scaling or vice versa?).


At least in the context of the example given, the advantage to the mesh network is that it has the lowest asymptotic cost. This is because a constant amount of stuff needs to be added for each added node. Contrast this with the crossbar where O(N) things need to be added for a new node, and multi-stage logarithmic where O(lgN) things need to be added for a new node.

The tradeoff of course is that the mesh has the longest average latency. If you only connect the new node to its neighbors (cheap), then the distance in steps to nodes further away gets greater and greater as you add more nodes (slow). If you connect a new node to everything (expensive), then the distance in steps to nodes further away remains the same however many nodes you add (fast).


Another term that we described in the practice exam was bisection bandwidth. Can anyone provide a definition for bisection bandwidth (explaining it in the context of the exam 2 practice problem on interconnection networks would be good).


Slide 12 defines it as the minimum bandwidth out of any partition of the network that includes exactly half the nodes.


Could you potentially make the argument that crossbar is actually direct? Or at least some sort of hybrid direct/indirect?


I'm a little confused by the definition of the cost of the interconnection. In the exam 2 question, we have the cost of a ring and mesh being O(N). If you were to add another row (sqrt(N) nodes), you'd need N more connections. In the ring, if you were to add another sqrt(N) nodes, you need to add sqrt(N) +2 connections. So, the cost isn't relative to the number of connections we add for some given number of nodes?
--- Nvm. I think the cost is defined as the number of wires with respect to the number of nodes in the interconnect not the addition of nodes to the interconnect. So for the mesh, we would have sqrt(N)sqrt(N)+sqrt(N)sqrt(N)= 2N wires making O(N). For the ring, we would have N wires making O(N).

@paluri: I thought that direct was defined where the end points were in the network - they were on the routers/switches directly. Since the packets travel from a start point through a switch to an end point, I don't think that can be defined as direct?


@arjunh bisection bandwidth is the sum bandwidth of links severed when cutting the network in half. For example, the multi-stage logarithmic in this slide, there are 8 links cut into half, if each link is 1 Gbit/s, the bisection bandwidth will be 1 * 8 = 8 Gbit/s.


It is interesting that all the network topologies showed here are in 2-D. I was wondering if there are networks designed in 3-D, like a cube, or hyper-cube.