I guess that this is called "blocking" because when a conflict happens one of the messages has to wait for the other one to get off the link?
bwf
I would agree with you that this is blocking. When the messages reach the section labeled conflict, one of them will have to wait for the other to go before it can be sent over the same path.
grose
Would it still be considered blocking if conflicts only happen when we try to connect 3 or more pairs simultaneously? Or does blocking only refer to 2 pairs
bwf
I think it would still be blocking since we defined blocking to be for any permutation of sources and destinations.
grose
@bwf, but wouldn't that mean anything except a crossbar is blocking, if we look at sets of connections involving every node?
bwf
I don't think so. Multistage logarithmic doesn't have to be blocking. It's just that the examples from lecture happen to be blocking.
dumbo_
Professor also mentioned that, there's a class of network which are re-arrangeably non-blocking, meaning that they can always connect any pairing of nodes, but sometimes to do so, if we already have some pairing of connections going on, they need to break down all the connections and re-establish them in a different way to make everybody communicating with each other.
parallelfifths
@bwf I believe you are correct about the definition encompassing the connection of >2 pairs. @grose, I found this definition from MIT course slides helpful (2nd slide on pg. 4):
"A mxn unique routing network is called a nonblocking network
if for any integer k < min(m,n)+1, any k external inputs, any k
external outputs and pairing between these external I/O, there
exist k disjoint routes for the matched pairs"
toutou
So even if there is another path between 3 and 7 having no conflict with that between 1 and 6, it is also "blocking"?
grose
Actually, if the numbers on the left are actually the same nodes as the corresponding numbers on the right, then this counterexample is invalid. You can easily see a route from 6 on the left to 1 on the right.
I also think it may be time to intuitively try to understand the definition of blocking. Assuming each node can only talk to at most one other node at a time, a useful property would be to know that no matter what other nodes are doing, if you're A, you can connect to B, given that B is not busy right now. This seems to imply that the network should support any mapping f, such that f(a) = b => f(b) = a, e.g. a configuration where everyone is connected (which includes as subsets where less than all nodes are connected)
I guess that this is called "blocking" because when a conflict happens one of the messages has to wait for the other one to get off the link?
I would agree with you that this is blocking. When the messages reach the section labeled conflict, one of them will have to wait for the other to go before it can be sent over the same path.
Would it still be considered blocking if conflicts only happen when we try to connect 3 or more pairs simultaneously? Or does blocking only refer to 2 pairs
I think it would still be blocking since we defined blocking to be for any permutation of sources and destinations.
@bwf, but wouldn't that mean anything except a crossbar is blocking, if we look at sets of connections involving every node?
I don't think so. Multistage logarithmic doesn't have to be blocking. It's just that the examples from lecture happen to be blocking.
Professor also mentioned that, there's a class of network which are re-arrangeably non-blocking, meaning that they can always connect any pairing of nodes, but sometimes to do so, if we already have some pairing of connections going on, they need to break down all the connections and re-establish them in a different way to make everybody communicating with each other.
@bwf I believe you are correct about the definition encompassing the connection of >2 pairs. @grose, I found this definition from MIT course slides helpful (2nd slide on pg. 4): "A mxn unique routing network is called a nonblocking network if for any integer k < min(m,n)+1, any k external inputs, any k external outputs and pairing between these external I/O, there exist k disjoint routes for the matched pairs"
So even if there is another path between 3 and 7 having no conflict with that between 1 and 6, it is also "blocking"?
Actually, if the numbers on the left are actually the same nodes as the corresponding numbers on the right, then this counterexample is invalid. You can easily see a route from 6 on the left to 1 on the right.
I also think it may be time to intuitively try to understand the definition of blocking. Assuming each node can only talk to at most one other node at a time, a useful property would be to know that no matter what other nodes are doing, if you're A, you can connect to B, given that B is not busy right now. This seems to imply that the network should support any mapping f, such that f(a) = b => f(b) = a, e.g. a configuration where everyone is connected (which includes as subsets where less than all nodes are connected)