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

Browse other questions tagged or ask your own question.