Previous | Next --- Slide 9 of 34
Back to Lecture Thumbnails

Example of blocking vs. non-blocking: Consider 4 distinct nodes on a network, A, B, C, and D. Suppose that A wants to send a message to B, and C wants to send a message to D. In a non-blocking network, it would be possible for both of these messages to be sent at the same time. In a blocking network, it might not be possible for both of the messages to be sent at the same time. Perhaps both message routes share a switch that can only handle one message at a time.

sjoyner

For bisection bandwidth, if the bandwidth is low, then there are not many links that cross between the two sides of the network, so contention will be high. If the bandwidth is high, there are many links crossing the two sides, so contention will be lower.

kfc9001

For you nerds out there, a network would be blocking if the graph representing the network had a cutvertex.

Worst-case bisection bandwidth is almost k-connectivity.

hh

An example of non-blocking given during the review session is if you have two nodes (A and B) connected to one switch (switch 1) which is connected to another switch (switch 2) which is connected to nodes C and D. If A wants to send a message to C, it will go from A -> switch 1 -> switch 2 -> C. If B wants to send a message to D, it will go from B -> switch 1 -> switch 2 -> C. If there is only one link between switch 1 and switch 2, then it is blocking. However, if you add a second link between switch 1 and switch 2, then even if A is sending a message to C and using up one of the links, B can still send a message to D through the second link, so the network is no longer blocking.

LeeK

Is the crossbar topology the only non-blocking topology?

kayvonf

@Leek: You may be interested in http://en.wikipedia.org/wiki/Nonblocking_minimal_spanning_switch

fangyihua

Bisection Bandwidth is measurement of the total network flow in the network.

abattagl

Higher bisection bandwidth is better than lower, as it (potentially) reduces contention per wire.