Butterfly network with switches set for two node disjoint paths and method for forming the paths

A storage media encoded with computer instructions for configuring a plurality of switches in a butterfly network to carry traffic, each switch in said plurality having two X ports and two Y ports, each switch having a label <c;

• r>, wherein c indicates a level number in the range 0, . . . i, . . . n, each level having N=2n switches, and r indicates a row number in the range 0, . . . N−1, an X port of each switch labeled <c;
• r> except for c=0 being connected to a Y port of a switch in said plurality labeled <c−1;
• r>, another X port of each switch labeled <c;
• r> except for c=0 being connected to another Y port of a switch in said plurality labeled <c−1;
• s>, with all bits si=ri except for one bit s(c−1)=1−r(c−1), the computer instructions being for:
• identifying a first group of switches of said plurality of switches forming a first path from a first switch in said plurality to a second switch in said plurality, the first switch being designated as a preceding switch wherein said identifying comprises,
• generating a label of a switch in said first group by incrementing by 1 a level number c in a label of said preceding switch, and replacing the c-th bit of row number r in the label of said preceding switch with c-th bit or inverse thereof of the row number in the label of said second switch, wherein each of c, r, and s is a non-negative integer;
• setting at least one switch in said first group of switches;
• identifying a second group of switches of said plurality of switches forming a second path from said first switch to a third switch in said plurality, wherein said first path and said second path are independent of one another;
• and
• setting at least one switch in said second group of switches.

A carrier signal encoded with computer instructions for configuring a plurality of switches in a butterfly network to carry traffic, each switch in said plurality having two X ports and two Y ports, each switch having a label <c;

• r>, wherein c indicates a level number in the range 0, . . . i, . . . n, each level having N=2n switches, and r indicates a row number in the range 0, . . . N−1, an X port of each switch labeled <c;
• r> except for c=0 being connected to a Y port of a switch in said plurality labeled <c−1;
• r>, another X port of each switch labeled <c;
• r> except for c=0 being connected to another Y port of a switch in said plurality labeled <c−1;
• s>, with all bits si=ri except for one bit s(c−1)=1−r(c−1), the computer instructions being for:
• identifying a first group of switches of said plurality of switches forming a first path from a first switch in said plurality to a second switch in said plurality, the first switch being designated as a preceding switch wherein said identifying comprises,
• generating a label of a switch in said first group by incrementing by 1 a level number c in a label of said preceding switch, and replacing the c-th bit of row number r in the label of said preceding switch with c-th bit or inverse thereof of the row number in the label of said second switch, wherein each of c, r, and s is a non-negative integer;
• setting at least one switch in said first group of switches;
• identifying a second group of switches of said plurality of switches forming a second path from said first switch to a third switch in said plurality, wherein said first path and said second path are independent of one another;
• and
• setting at least one switch in said second group of switches.

An apparatus for configuring a plurality of switches in a butterfly network to carry traffic, each switch in said plurality having two X ports and two Y ports, each switch having a label <c;

• r>, wherein c indicates a level number in the range 0, . . . i, . . . n, each level having N=2n switches, and r indicates a row number in the range 0, . . . N−1, an X port of each switch labeled <c;
• r> except for c=0 being connected to a Y port of a switch in said plurality labeled <c−1;
• r>, another X port of each switch labeled <c;
• r> except for c=0 being connected to another Y port of a switch in said plurality labeled <c−1;
• s>, with all bits si=ri except for one bit s(c−1)=1−r(c−1), the apparatus comprising:
• means for identifying a first group of switches of said plurality of switches forming a first path from a first switch in said plurality to a second switch in said plurality, the first switch being designated as a preceding switch wherein said means for identifying comprises,
• means for generating a label of a switch in said first group by incrementing by 1 a level number c in a label of said preceding switch, and replacing the c-th bit of row number r in the label of said preceding switch with c-th bit or inverse thereof of the row number in the label of said second switch, wherein each of c, r, and s is a non-negative integer;
• setting at least one switch in said first group of switches;
• means for identifying a second group of switches of said plurality of switches forming a second path from said first switch to a third switch in said plurality, wherein said first path and said second path are independent of one another;
• and
• setting at least one switch in said second group of switches.