To clarify, is a network blocking when multiple paths overlap? To have a truly non-blocking network, do you need to have separate paths to each end node for every input node? For this example, would you need n-squared paths to have a non-blocking network?
For this example, in order to resolve the conflict issue, would each node need to have some sort of queue abstraction?
adilets
For your first question yes if the paths overlap then it is blocking since the connection can relay only one message at a time.
cloudhary
@anamdev it's interesting you mention n-squared paths to have a non-blocking network, because that very clearly brings home the need for something like this - to reduce the amount of connections for large n. I'm not sure, but I think you can implement a connection from every one node to another in nlogn in a graph like the above? I guess it's a tradeoff that designers have tested to figure that they'd rather increase the latency with blocking messages than ensure non blocking constantly
yeezus98
One way to perhaps deal with this problem is to probabilistically determine paths. This way even if there is a conflict, we can minimize the potential conflicts. as @adamdev mentioned, presenting a truly non conflicting network requires n^2 paths and no one wants that
yey1
It is a crossbar interconnect, which costs O(N^2) switches.
To clarify, is a network blocking when multiple paths overlap? To have a truly non-blocking network, do you need to have separate paths to each end node for every input node? For this example, would you need n-squared paths to have a non-blocking network?
For this example, in order to resolve the conflict issue, would each node need to have some sort of queue abstraction?
For your first question yes if the paths overlap then it is blocking since the connection can relay only one message at a time.
@anamdev it's interesting you mention n-squared paths to have a non-blocking network, because that very clearly brings home the need for something like this - to reduce the amount of connections for large n. I'm not sure, but I think you can implement a connection from every one node to another in nlogn in a graph like the above? I guess it's a tradeoff that designers have tested to figure that they'd rather increase the latency with blocking messages than ensure non blocking constantly
One way to perhaps deal with this problem is to probabilistically determine paths. This way even if there is a conflict, we can minimize the potential conflicts. as @adamdev mentioned, presenting a truly non conflicting network requires n^2 paths and no one wants that
It is a crossbar interconnect, which costs O(N^2) switches.