I know butterfly networks (and benes as well) allow routing a packet from any input to any output node. Congestion is $\sqrt{n}$ but with bene it can be $1$.

Now assume that in a butterfly network, each switch is a selection switch, i.e. the switch has two inputs terminals and two outputs terminal but it "copies" one of the inputs to both of its output terminals( based on control bit).

I am trying to resolve a bit different problem. Let there are $n$ input nodes and $n$ output nodes. Following are the requirements of the problem:

  1. For each input packet $i$, we want $k_i$ output nodes to have $i$.
  2. $\sum_{i=1}^{n}k_i=n$

Note that the problem does not care about the arrangement of output but just the number $k_i$, like any $k_i$ output nodes can have packet $i$. I have tried few examples on the butterfly network and it works fine but I am not sure how can we prove correctness for this network.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy