US5451936A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-blocking broadcast network
Assignee: Johns Hopkins University
•
Filing: 1993-10-19
•
Granted: 1995-09-19
•
Expires: 2013-10-19
Abstract
Abstract The present invention pertains to a nonblocking broadcast switching network. The network comprises an input stage. The input stage has N1 or n1r1 input ports and r1 switches, where n1>/=2 and r1>/=1 and are integers. The network is also comprised of an output stage. The output stage has N2 or n2r2 output ports and r2 switches, where n2>/=2 and r1>/=1 and are integers. There is also a middle stage. The middle stage has m switches where m is an integer and, where <IMAGE> The m switches are in communication with the r1 switches and r2 switches. The middle stage of m switches has L inputs, where L>/=r1 and is an integer, and J outputs, where J>/=r2 and is an integer, x or fewer of the m switches, where 1>/=x>/=min{n2-1, r2} 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. In a preferred embodiment, the controller is comprised of means for determining which middle stage switches are idle at a given time in the network. The controller is also comprised of means 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 choosing means chooses the minimum number of idle middle stage switches to form the desired broadcast connection.
Inventors
- 👤 Yuanyuan Yang
- 👤 Gerald M. Masson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 21:18
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/64; H04Q3/68
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
261 words
A nonblocking broadcast switching network comprising: an input stage, said input stage having N 1 or n 1 r 1 input ports and r 1 input switches, each input switch having n 1 input ports and N 1 =n 1 r 1 , where r 1 ≧1 and n 1 ≧1 and are integers; an output stage, said output stage having N 2 or n 2 r 2 output ports and r 2 output switches, each output switch having n 2 output ports and N 2 =n 2 r 2 , where r 2 ≧1 and n 2 ≧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 each output switch, where ##EQU10## and where min{n 2 -1,r 2 } equals the smallest of either n 2 -1 or r 2 , and min {(n 1 -1)x+(n 2 -1)r 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)r 2 1/x }. said middle stage of m switches having I inputs where I≧r 1 and is an integer, and J outputs, where J≧r 2 and is an integer, x or fewer of the m switches, where 1≦x≦ min{n 2 -1,r 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.
Claim 2
Dependent Claim
261 words
A nonblocking broadcast switching network comprising: an input stage, said input stage having N 1 or n 1 r 1 input ports and r 1 input switches, each input switch having n 1 input ports and N 1 =n 1 r 1 , where r 1 ≧1 and n 1 ≧1 and are integers; an output stage, said output stage having N 2 or n 2 r 2 output ports and r 2 output switches, each output switch having n 2 output ports and N 2 =n 2 r 2 , where r 2 ≧1 and n 2 ≧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 each output switch, where ##EQU10## and where min{n 2 -1,r 2 } equals the smallest of either n 2 -1 or r 2 , and min {(n 1 -1)x+(n 2 -1)r 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)r 2 1/x }. said middle stage of m switches having I inputs where I≧r 1 and is an integer, and J outputs, where J≧r 2 and is an integer, x or fewer of the m switches, where 1≦x≦ min{n 2 -1,r 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.
Claim 3
Dependent Claim
37 words
A network as described in claim 1 including a controller in communication with each of the input, output and middle stages to form the connection between an idle input port and a plurality of idle output ports.
Claim 4
Dependent Claim
46 words
A network as described in claim 2 wherein the controller includes means for forming the connection by choosing x or fewer middle switches which have an idle link to a input switch where a connection request arises and idle links to output switches in the connection.
Claim 5
Independent Claim
338 words
A method for forming a broadcast connection in a nonblocking broadcast switching network having an input stage having n 1 r 1 input ports and r 1 input switches, an output stage having n 2 r 2 output ports and r 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 2 -1,r 2 } equals the smallest of either n 2 -1 or r 2 ,and min {(n 1 -1)x+(n 2 -1)r 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)r 2 1/x }, and where n 1 , r 1 , n 2 and r 2 are all ≧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.
Claim 6
Independent Claim
338 words
A method for forming a broadcast connection in a nonblocking broadcast switching network having an input stage having n 1 r 1 input ports and r 1 input switches, an output stage having n 2 r 2 output ports and r 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 2 -1,r 2 } equals the smallest of either n 2 -1 or r 2 ,and min {(n 1 -1)x+(n 2 -1)r 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)r 2 1/x }, and where n 1 , r 1 , n 2 and r 2 are all ≧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.
Claim 7
Dependent Claim
225 words
A nonblocking broadcast switching network comprising: an input stage, said input stage having N 1 or n 1 r 1 input ports and r 1 input switches, each input switch having n 1 input ports and N 1 =n 1 r 1 , where r 1 ≧1 and n 1 ≧1 and are integers; an output stage, said output stage having N 2 or n 2 r 2 output ports and r 2 output switches, each output switch having n 2 output ports and N 2 =n 2 r 2 , where r 2 ≧1 and n 2 ≧1 and are integers; and ##EQU12## where min{n 2 -1,r 2 } equals the smallest of either n 2 -1 or r 2 , and min {(n 1 -1)x+(n 2 -1)r 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)r 2 1/x }, said middle stage of m switches having I inputs where I≧r 1 and is an integer, and J outputs, where J≧r 2 and is an integer, x or fewer of the m switches, where 1≦x≦min{n 2 -1,r 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.
Claim 8
Dependent Claim
225 words
A nonblocking broadcast switching network comprising: an input stage, said input stage having N 1 or n 1 r 1 input ports and r 1 input switches, each input switch having n 1 input ports and N 1 =n 1 r 1 , where r 1 ≧1 and n 1 ≧1 and are integers; an output stage, said output stage having N 2 or n 2 r 2 output ports and r 2 output switches, each output switch having n 2 output ports and N 2 =n 2 r 2 , where r 2 ≧1 and n 2 ≧1 and are integers; and ##EQU12## where min{n 2 -1,r 2 } equals the smallest of either n 2 -1 or r 2 , and min {(n 1 -1)x+(n 2 -1)r 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)r 2 1/x }, said middle stage of m switches having I inputs where I≧r 1 and is an integer, and J outputs, where J≧r 2 and is an integer, x or fewer of the m switches, where 1≦x≦min{n 2 -1,r 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.
Claim 9
Dependent Claim
266 words
A nonblocking broadcast switching network comprising: an input stage, said input stage having N 1 or n 1 r 1 input ports and r 1 input switches, each input switch having n 1 input ports and N 1 =n 1 r 1 , where r 1 ≧1 and n 1 ≧1 and are integers; an output stage, said output stage having N 2 or n 2 r 2 output ports and r 2 output switches, each output switch having n 2 output ports and N 2 =n 2 r 2 , where r 2 ≧1 and n 2 ≧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≦d≦r 2 and where ##EQU13## and where min{n 2 -1,d 2 } equals the smallest of either n 2 -1 or d 2 , and min {(n 1 -1)x+(n 2 -1)d 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)d 2 1/x }, said middle stage of m switches having I inputs where I≧r 1 and is an integer, and J outputs, where J≧r 2 and is an integer, x or fewer of the m switches, where 1≦x≦min{n 2 -1,r 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.
Claim 10
Dependent Claim
266 words
A nonblocking broadcast switching network comprising: an input stage, said input stage having N 1 or n 1 r 1 input ports and r 1 input switches, each input switch having n 1 input ports and N 1 =n 1 r 1 , where r 1 ≧1 and n 1 ≧1 and are integers; an output stage, said output stage having N 2 or n 2 r 2 output ports and r 2 output switches, each output switch having n 2 output ports and N 2 =n 2 r 2 , where r 2 ≧1 and n 2 ≧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≦d≦r 2 and where ##EQU13## and where min{n 2 -1,d 2 } equals the smallest of either n 2 -1 or d 2 , and min {(n 1 -1)x+(n 2 -1)d 2 1/x } is the smallest integer solution of {(n 1 -1)x+(n 2 -1)d 2 1/x }, said middle stage of m switches having I inputs where I≧r 1 and is an integer, and J outputs, where J≧r 2 and is an integer, x or fewer of the m switches, where 1≦x≦min{n 2 -1,r 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.
References Cited (Backward Citations)
US3582560A
Cited
US4394541A
Cited
US4400627A
Cited
US4417245A
Cited
US4696000A
Cited
US4845736A
Cited
US4907253A
Cited
US4975909A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-18 | 1999-03-20 | 1999-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-18 | 2003-03-20 | 2003-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-18 | 2007-03-20 | 2007-09-19 | $7700.00 | Window Closed / Lapsed |