Non-blocking broadcast network

A method for forming a broadcast connection in a nonblocking broadcast switching network having an input stage having n.sub.1 r.sub.1 input ports and r.sub.1 input switches, an output stage having n.sub.2 r.sub.2 output ports and r.sub.2 output switches, and a middle stage having m middle switches, where each middle switch is connected to each input switch and each output switch, where ##EQU11## where min{n.sub.2 -1,r.sub.2 } equals the smallest of either n.sub.2 -1 or r.sub.2,and min {(n.sub.1 -1)x+(n.sub.2 -1)r.sub.2 .sup.1/x } is the smallest integer solution of {(n.sub.1 -1)x+(n.sub.2 -1)r.sub.2 .sup.1/x }, and where n.sub.1, r.sub.1, n.sub.2 and r.sub.2 are all .gtoreq.1, and are integers, comprising the computer generated steps of:

• a. identifying a broadcast connection request;
• b. choosing an input port of the network through which the broadcast connection will be formed;
• c. defining in a memory of the computer a set of all addresses of idle output links of middle switches of the network;
• d. erasing all addresses of idle output links from the set in the memory which do not connect with desired output switches having output ports of the network in the broadcast connection;
• e. choosing an address of a middle switch which has the most idle output links connected to desired output switches from the set in the memory;
• f. saving in the memory of the computer the address of the middle switch chosen in step e.;
• g. removing the address of the middle switch chosen in step e. from the set in memory;
• h. repeating steps e., f., and g. until enough addresses of middle switches are chosen that their idle output links connect to all desired output switches that are needed to form the broadcast connection.
• i. connecting an idle input port with the middle switches whose addresses were chosen in step h., and the chosen middle switches to the desired output switches to form the broadcast connection.

A nonblocking broadcast switching network comprising:

• an input stage, said input stage having N.sub.1 or n.sub.1 r.sub.1 input ports and r.sub.1 input switches, each input switch having n.sub.1 input ports and N.sub.1 =n.sub.1 r.sub.1, where r.sub.1 .gtoreq.1 and n.sub.1 .gtoreq.1 and are integers;
• an output stage, said output stage having N.sub.2 or n.sub.2 r.sub.2 output ports and r.sub.2 output switches, each output switch having n.sub.2 output ports and N.sub.2 =n.sub.2 r.sub.2, where r.sub.2 .gtoreq.1 and n.sub.2 .gtoreq.1 and are integers;
• and ##EQU12## where min{n.sub.2 -1,r.sub.2 } equals the smallest of either n.sub.2 -1 or r.sub.2, and min {(n.sub.1 -1)x+(n.sub.2 -1)r.sub.2 .sup.1/x } is the smallest integer solution of {(n.sub.1 -1)x+(n.sub.2 -1)r.sub.2 .sup.1/x },
• said middle stage of m switches having I inputs where I.gtoreq.r.sub.1 and is an integer, and J outputs, where J.gtoreq.r.sub.2 and is an integer, x or fewer of the m switches, where 1.ltoreq.x.ltoreq.min{n.sub.2 -1,r.sub.2 } and is an integer, always available to form a connection without any rearrangement of existing connections between an idle input port and a plurality of idle output ports, but no output port is connected to more than 1 input port.

A nonblocking broadcast switching network comprising:

• an input stage, said input stage having N.sub.1 or n.sub.1 r.sub.1 input ports and r.sub.1 input switches, each input switch having n.sub.1 input ports and N.sub.1 =n.sub.1 r.sub.1, where r.sub.1 .gtoreq.1 and n.sub.1 .gtoreq.1 and are integers;
• an output stage, said output stage having N.sub.2 or n.sub.2 r.sub.2 output ports and r.sub.2 output switches, each output switch having n.sub.2 output ports and N.sub.2 =n.sub.2 r.sub.2, where r.sub.2 .gtoreq.1 and n.sub.2 .gtoreq.1 and are integers;
• and
• a middle stage, said middle stage having m middle switches, where m is an integer and each middle switch has at least one link connected to each input switch and at least one link connected to at most d output switches, where 1.ltoreq.d.ltoreq.r.sub.2 and where ##EQU13## and where min{n.sub.2 -1,d.sub.2 } equals the smallest of either n.sub.2 -1 or d.sub.2, and min {(n.sub.1 -1)x+(n.sub.2 -1)d.sub.2 .sup.1/x } is the smallest integer solution of {(n.sub.1 -1)x+(n.sub.2 -1)d.sub.2.sup.1/x },
• said middle stage of m switches having I inputs where I.gtoreq.r.sub.1 and is an integer, and J outputs, where J.gtoreq.r.sub.2 and is an integer, x or fewer of the m switches, where 1.ltoreq.x.ltoreq.min{n.sub.2 -1,r.sub.2 } and is an integer, always available to form a connection between an idle input port and a plurality of idle output ports, but no output port is connected to more than 1 input port.