The bit representation of the destination node encode the path to this node. This is true for every source node. And this also explained the O(lgN) latency, because the path length is the number of bits in the node bit representation.
rootB
Each stage has N/2 switches, and between stages switches are 2x2 crossbar connected. The port id does a perfect shuffle at each stage: the next stage's port id is obtained by left rotating shift of the current id. For example, 001 goes to 010 (the second switch in the first stage), then 100 (the third switch in the second stage), then back to 001 (the first switch in the third stage). There are log2(N) stages, which is the number of bit that can represents the nodes as mentioned by @chenh1, hence the O(lg(N)) latency. Number of switches is N/2 * log2(N) = O(Nlg(N)).
What properties define a multi-stage logarithmic network?
kshitizdange
I didn't understand how the path to node 3 from any other node will always be '011'?
kshitizdange
Ohh got it! Every right link corresponds to '1' and every left link corresponds to '0', from a switch. So, to reach node 3 from any other node, 0-1-1 needs to be followed on the switches.
The bit representation of the destination node encode the path to this node. This is true for every source node. And this also explained the O(lgN) latency, because the path length is the number of bits in the node bit representation.
Each stage has N/2 switches, and between stages switches are 2x2 crossbar connected. The port id does a perfect shuffle at each stage: the next stage's port id is obtained by left rotating shift of the current id. For example, 001 goes to 010 (the second switch in the first stage), then 100 (the third switch in the second stage), then back to 001 (the first switch in the third stage). There are log2(N) stages, which is the number of bit that can represents the nodes as mentioned by @chenh1, hence the O(lg(N)) latency. Number of switches is N/2 * log2(N) = O(Nlg(N)).
Related papers for reference:
Omega: Access and Alignment of Data in an Array Processor
Butterfly: Flattened butterfly: a cost-efficient topology for high-radix networks
Clos networks: A study of non-blocking switching networks
What properties define a multi-stage logarithmic network?
I didn't understand how the path to node 3 from any other node will always be '011'?
Ohh got it! Every right link corresponds to '1' and every left link corresponds to '0', from a switch. So, to reach node 3 from any other node, 0-1-1 needs to be followed on the switches.