Controller for a non-blocking broadcast network

• US 5,801,641 A
• Filed: 09/18/1995
• Issued: 09/01/1998
• Est. Priority Date: 10/19/1993
• Status: Expired due to Term

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Yang, Yuanyuan, Masson, Gerald M.
• Primary Examiner(s): Zimmerman, Brian
• Assistant Examiner(s): WILSON JR, WILLIAM HALL
• Application Number:
  US08/529,582
• Time in Patent Office: 1,079 Days
• Field of Search: 340/826, 340/827, 340/825.8, 340/825.03, 340/825.79, 370/388, 370/442, 370/357, 370/371, 370/381, 379/220, 379/271, 379/335
• US Class Current: 340/2.22
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

Abstract

A controller for a nonblocking broadcast switching network comprising an input stage, an output stage, and a middle stage. The input stage has N₁ or n₁ r₁ input ports and r₁ switches, where n₁ ≧2 and r₁ ≧1 and are integers. The network also includes an output stage. The output stage has N₂ or n₂ r₂ output ports and r₂ switches, where n₂ ≧2 and r₁ ≧1 and are integers. There is also a middle stage. The middle stage has m switches, where ##EQU1## The m switches are in communication with the r₁ switches and r₂ switches. The middle stage of m switches has L inputs, where L≧r₁ and is an integer, and J outputs, where J≧r₂ and is an integer, corresponding to the n₁ input ports and n₂ output ports, x or fewer of the m switches, where 1≦x≦m, 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. In a preferred embodiment, the controller includes a mechanism for determining which middle stage switches are idle at a given time in the network. The controller also includes a mechanism for choosing middle stage switches from only the idle middle stage switches to form a desired broadcast connection between an idle input port and a plurality of idle output ports. Preferably, the mechanism for choosing chooses the minimum number of idle middle stage switches to form the desired broadcast connection.

Claims

1. A controller for a nonblocking broadcast switching network having N₂ or r₁ input stage switches with N₁ or n₁ r₁ input ports and where each input switch has n₁ input ports and N₁ =n₁ r₁ where r₁ ≧

1 and n₁ ≧

1 and are integers, r₂ output stage switches with n₂ r₂ output ports where each output switch having n₂ output ports and N₂ =n₂ r₂ where r₂ ≧

1 and n₂ ≧

1 and are integers and m middle stage 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 each output switch, where ##EQU9## and where min{n₂ -1,r₂ } equals the smallest of either n₂ -1 or r₂, and min {(n₁ -1)x+(n₂ -1)r_s ^1/x } is the smallest integer solution of {(n₁ -1)x+(n₂ -1)r₂ ^1/x }

said middle stage of m switches having I inputs where I≧

r₁ and is an integer, and J outputs, where J≧

r₂ and is an integer, x or fewer of the m switches, where 1≧

x≧

min{n₂ -1,r₂ } 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 and the m middle stage switches in communication with the input and output stage switches comprising;

means for determining which middle stage switches of the m middle stage switches where ##EQU10## have an idle link to the input switch where a broadcast connection request arises and idle links to the output switches in the broadcast connection at a given time in the network; and

means for choosing middle stage switches from only the middle switches which have an idle link to the input switch where the broadcast connection request arises and idle links to the output switches in the broadcast connection to form the desired broadcast connection between an idle input port and a plurality of idle output ports without any rearrangement of existing connections between an idle input port and a plurality of idle output ports.

2. A controller as described in claim 1 wherein the choosing means chooses the minimum number of middle switches to form the desired broadcast connection.

3. A controller as described in claim 2 wherein there are always enough middle stage switches in the network to form the desired broadcast connection.

4. A controller as described in claim 3 wherein the determining means includes middle switch state registers which store information about a state of middle switch output links.

5. A controller as described in claim 4 wherein the choosing means includes means for picking the middle switches which form the desired broadcast connection.

6. A controller as described in claim 5 wherein the choosing means includes a sequential circuit or a combinational circuit which determines the number of 1'"'"'s in a middle switch state register.

7. A controller as described in claim 6 wherein the choosing means includes a sequential or combinational circuit which takes a group of binary numbers and their addresses as input and outputs the minimum binary number and its address.

8. A controller as described in claim 7 wherein the picking means includes shift registers/counters or adder arrays which identify for each considered middle stage switch the number of output switches with which it connects, said shift register/counter or adder arrays connected to the middle switch stage registers;

a comparator array connected to the shift registers/counters or adder arrays which choose the middle stage switch which connects to the minimum number of output switches.

9. A controller as described in claim 8 wherein the choosing means includes a masking register connected to the shift registers/counters or adder arrays which only provides information about middle stage switches that are connected to desired output switches.

10. A controller as described in claim 9 wherein the choosing means includes a minimum register connected to the masking register and the middle switch state registers for providing the state of the middle switch which is chosen by the comparator array.

11. A controller as described in claim 10 wherein the choosing means includes x selected registers to store the middle switches chosen to form a broadcast connection.

12. A controller as described in claim 11 wherein the choosing means includes a timing control connected to all the registers and arrays for controlling the sequence of their operation.

13. A controller for a nonblocking broadcast switching network having input stage switches with input ports, output stage switches with output ports and middle stage switches in communication with the input and output stage switches comprising:

a mechanism for determining which middle stage switches have an idle link to the input switch where a broadcast connection request arises and idle links to the output switches in the broadcast connection at a given time in the network; and

a mechanism for choosing middle stage switches from only the middle switches which have an idle link to the input switch where the broadcast connection request arises and idle links to the output switches in the broadcast connection to form the desired broadcast connection between an idle input port and a plurality of idle output ports without any rearrangement of existing connections between an idle input port and a plurality of idle output ports without re arrangement of any existing connections.