There are log(N) rows (stages according to wikipedia) and each row has N/2 nodes. So total cost is O(N lg N).
In the picture, N=8, there are 3 rows and 4 nodes per row.
This comment was marked helpful 1 times.
rutwikparikh
Bisection bandwidth is O(N) as can be noted due to (in this case) n wires between switches.
This comment was marked helpful 0 times.
edwardzh
Many variations of multi-stage logarithmic networks, such as the Omega and butterfly networks, are isomorphic (topologically equivalent). These networks (delta networks), are "digit controlled" networks. In other words, the reason why there are $\log_2(n)$ rows (columns, in this picture) is because, starting from the left, each node is connected to exactly one 2x2 switch. Routing is entirely determined by the packet ("digit controlled"), which has $\log_2(n)$ bits. Each bit determines whether the packet is routed to the high connection or the low connection. Because each origin must be capable of reaching $n$ destinations, there must be exactly $\log_2(n)$ bits to account for the full $n$ outcomes.
Question: Why is the cost O(N lg N) here?
This comment was marked helpful 0 times.
There are log(N) rows (stages according to wikipedia) and each row has N/2 nodes. So total cost is O(N lg N). In the picture, N=8, there are 3 rows and 4 nodes per row.
This comment was marked helpful 1 times.
Bisection bandwidth is O(N) as can be noted due to (in this case) n wires between switches.
This comment was marked helpful 0 times.
Many variations of multi-stage logarithmic networks, such as the Omega and butterfly networks, are isomorphic (topologically equivalent). These networks (delta networks), are "digit controlled" networks. In other words, the reason why there are $\log_2(n)$ rows (columns, in this picture) is because, starting from the left, each node is connected to exactly one 2x2 switch. Routing is entirely determined by the packet ("digit controlled"), which has $\log_2(n)$ bits. Each bit determines whether the packet is routed to the high connection or the low connection. Because each origin must be capable of reaching $n$ destinations, there must be exactly $\log_2(n)$ bits to account for the full $n$ outcomes.
This comment was marked helpful 0 times.