US5945922A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Widesense nonblocking switching networks
Assignee: Nokia of America Corp
•
Filing: 1996-09-06
•
Granted: 1999-08-31
•
Expires: 2016-09-06
Abstract
Abstract A multirate network is Wide Sense Non Blocking with a new routing algorithm classifying requests into large, load greater than 1/(1+p), and small groups, where B is the upper load bound of any given request and p=.left brkt-bot.1/B.right brkt-bot.. Where B is less than 31/32-β/4, substantially 2βn(P+1)(B+p-1)/p2 center interconnection units are restricted for carrying large requests only. For all other B, substantially 2βn center interconnection units are restricted. Using this routing algorithm, general multirate WSNB is guaranteed with substantially the lesser of 2f(p)+1+3.75βn and 2nβ(P+1)(Bp+B+p-1)/p 2 interconnection units where n is the number of inlets per input stage switch, β is the ratio of load capacity of external links to the input and output stages, and the load capacity of the internal links connecting the center stage to the input and output stages. Where the network is a three-rate network then the center stage can be further reduced to 5n center interconnection units for β=1. The center stage can be even further reduced to 3n center interconnection units if the network is a two-rate network for β=1.
Inventors
- 👤 Biao Gao
- 👤 Frank Kwangming Hwang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 07:54
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/15; H04L49/1553; H04L49/1569; H04L49/1515; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
210 words
A multirate Wide Sense NonBlocking network comprising: an input stage, said input stage comprising r input switches and n inlet links for each of said r input switches, each of said n inlet links for receiving one or more requests, each of said requests having an associated load with a value between an upper load bound B and a lower load bound b and each of said n inlet links having an external load capacity; an output stage, said output stage comprising r output switches and n outlet links for each of said r output switches, said n outlet links for outputting said received requests and each of said n outlet links having said external load capacity; and a center stage for routing said one or more requests from said input stage via a plurality of first internal links from each of said r input switches, to said output stage via a plurality of second internal links for each of said output switches, each of said first and second internal links having an internal load capacity, said center stage comprising substantially the lesser of 2f(β)+1+3.75βn or 2nβ(p+1)(Bp+B+p-1)/p 2 center interconnection units where β is the ratio of said internal load capacity to said external load capacity and p=.left brkt-bot.1/B.right brkt-bot..
Claim 2
Dependent Claim
210 words
A multirate Wide Sense NonBlocking network comprising: an input stage, said input stage comprising r input switches and n inlet links for each of said r input switches, each of said n inlet links for receiving one or more requests, each of said requests having an associated load with a value between an upper load bound B and a lower load bound b and each of said n inlet links having an external load capacity; an output stage, said output stage comprising r output switches and n outlet links for each of said r output switches, said n outlet links for outputting said received requests and each of said n outlet links having said external load capacity; and a center stage for routing said one or more requests from said input stage via a plurality of first internal links from each of said r input switches, to said output stage via a plurality of second internal links for each of said output switches, each of said first and second internal links having an internal load capacity, said center stage comprising substantially the lesser of 2f(β)+1+3.75βn or 2nβ(p+1)(Bp+B+p-1)/p 2 center interconnection units where β is the ratio of said internal load capacity to said external load capacity and p=.left brkt-bot.1/B.right brkt-bot..
Claim 3
Dependent Claim
25 words
A network according to claim 1 wherein each of said center stage WSNB nonblocking networks comprises an odd number multiple of three stage WSNB networks.
Claim 4
Dependent Claim
18 words
A network according to claim 1 wherein each of said center interconnection units is an r×r interconnection switch.
Claim 5
Dependent Claim
16 words
A network according to claim 3 wherein said r×r interconnection switch is an r×r crossbar switch.
Claim 6
Dependent Claim
36 words
A network according to claim 1 wherein said substantially the lesser of 2f(β)+1+3.75βn or 2nβ(1+p)(Bp+B+p-1)/p 2 center interconnection units comprise a plurality of center interconnection units restricted for routing requests having a load greater than 1/(1+p).
Claim 7
Dependent Claim
28 words
A network according to claim 5 wherein said plurality of restricted center interconnection units is substantially 2βn(p+1)(B+B-1)/p 2 where B is less than approximately 31/32-β/4 and 2βn otherwise.
Claim 8
Dependent Claim
189 words
A three rate Wide Sense NonBlocking network, comprising: an input stage, said input stage comprising r input switches and n inlet links for each of said r input switches, each of said n inlet links for receiving one or more requests, each of said requests having an associated load with a value between an upper load bound B and a lower load bound b and each of said n inlet links having an external load capacity; an output stage, said output stage comprising r output switches and n outlet links for each of said r output switches, said n outlet links for outputting said received requests and each of said n outlet links having said external load capacity; and a center stage for routing said one or more requests from said input stage via a plurality of first internal links from each of said r input switches, to said output stage via a plurality of second internal links for each of said output switches, each of said first and second internal links having an internal load capacity, said center stage comprising substantially between 2n and 5n center interconnection units.
Claim 9
Dependent Claim
189 words
A three rate Wide Sense NonBlocking network, comprising: an input stage, said input stage comprising r input switches and n inlet links for each of said r input switches, each of said n inlet links for receiving one or more requests, each of said requests having an associated load with a value between an upper load bound B and a lower load bound b and each of said n inlet links having an external load capacity; an output stage, said output stage comprising r output switches and n outlet links for each of said r output switches, said n outlet links for outputting said received requests and each of said n outlet links having said external load capacity; and a center stage for routing said one or more requests from said input stage via a plurality of first internal links from each of said r input switches, to said output stage via a plurality of second internal links for each of said output switches, each of said first and second internal links having an internal load capacity, said center stage comprising substantially between 2n and 5n center interconnection units.
Claim 10
Dependent Claim
23 words
A network according to claim 7 wherein each of said center stage interconnection units further comprises an odd number multiple of WSNB networks.
Claim 11
Dependent Claim
44 words
A network according to claim 7 wherein said network is WSNB for small rates, medium rates and large rates, and wherein said large rates have a normalized value less than or equal to 0.5 and said center stage comprises substantially 3.75n center interconnection units.
Claim 12
Dependent Claim
189 words
A two rate Wide Sense NonBlocking Network, comprising: an input stage, said input stage comprising r input switches and n inlet links for each of said r input switches, each of said n inlet links for receiving one or more requests, each of said requests having an associated load with a value between an upper load bound B and a lower load bound b and each of said n inlet links having an external load capacity; an output stage, said output stage comprising r output switches and n outlet links for each of said r output switches, said n outlet links for outputting said received requests and each of said n outlet links having said external load capacity; and a center stage for routing said one or more requests from said input stage via a plurality of first internal links from each of said r input switches, to said output stage via a plurality of second internal links for each of said output switches, each of said first and second internal links having an internal load capacity, said center stage comprising substantially between 2n and 3n center interconnection units.
Claim 13
Dependent Claim
189 words
A two rate Wide Sense NonBlocking Network, comprising: an input stage, said input stage comprising r input switches and n inlet links for each of said r input switches, each of said n inlet links for receiving one or more requests, each of said requests having an associated load with a value between an upper load bound B and a lower load bound b and each of said n inlet links having an external load capacity; an output stage, said output stage comprising r output switches and n outlet links for each of said r output switches, said n outlet links for outputting said received requests and each of said n outlet links having said external load capacity; and a center stage for routing said one or more requests from said input stage via a plurality of first internal links from each of said r input switches, to said output stage via a plurality of second internal links for each of said output switches, each of said first and second internal links having an internal load capacity, said center stage comprising substantially between 2n and 3n center interconnection units.
Claim 14
Dependent Claim
23 words
A network according to claim 10 wherein each of said center stage interconnection units further comprises an odd number multiple of WSNB networks.
Claim 15
Independent Claim
242 words
A method for routing one or more requests having a load between an upper bound B and a lower bound b, between an input stage of switches and an output stage of switches in a multi-rate Wide Sense NonBlocking network, said method comprising the steps of: receiving said requests at one of r input switches of said input stage, through one of n inlet links at each of said r input switches, each of said n inlet links having an external load capacity; outputting said requests at one of r output switches of said output stage, through one of n outlet links at each of said r output switches each of said n outlet links having said external load capacity; and routing said requests from said input stage via a plurality of first internal links from each of said input switches, to said output stage via a plurality of second internal links from each of said output switches, said first and second internal links having an internal link load capacity, through one or more of between 8n and substantially the lesser of 2f(β)+1+3.75nβ and 2βn(1+p)(Bp+B+p-1)/p 2 center interconnection units where β is the ratio of said internal link load capacity to said external link load capacity and p=.left brkt-bot.1/B.right brkt-bot., said center interconnection units being connected to each of said r input switches through r first internal links, and connected to each of said r output switches through r second internal links.
Claim 16
Independent Claim
242 words
A method for routing one or more requests having a load between an upper bound B and a lower bound b, between an input stage of switches and an output stage of switches in a multi-rate Wide Sense NonBlocking network, said method comprising the steps of: receiving said requests at one of r input switches of said input stage, through one of n inlet links at each of said r input switches, each of said n inlet links having an external load capacity; outputting said requests at one of r output switches of said output stage, through one of n outlet links at each of said r output switches each of said n outlet links having said external load capacity; and routing said requests from said input stage via a plurality of first internal links from each of said input switches, to said output stage via a plurality of second internal links from each of said output switches, said first and second internal links having an internal link load capacity, through one or more of between 8n and substantially the lesser of 2f(β)+1+3.75nβ and 2βn(1+p)(Bp+B+p-1)/p 2 center interconnection units where β is the ratio of said internal link load capacity to said external link load capacity and p=.left brkt-bot.1/B.right brkt-bot., said center interconnection units being connected to each of said r input switches through r first internal links, and connected to each of said r output switches through r second internal links.
Claim 17
Dependent Claim
96 words
A method according to claim 12 wherein said routing step further comprises the steps of: grouping said requests having a load greater than 1/(p+1) into a large group, and all other of said requests into a small group; routing said requests of said large group to substantially 2βn(p+1)(B+p-1)/p 2 restricted units of said center interconnection units if B is less than approximately 31/32-β/4, and to substantially 2f(β)+1 restricted units of said center interconnection units for all other B; and routing said requests of said small group to said center interconnection units other than said restricted units.
Claim 18
Independent Claim
232 words
A method for routing one or more requests having a load between an upper bound B and a lower bound b, between an input stage of switches and an output stage of switches in a three-rate Wide Sense NonBlocking network, said method comprising the steps of: receiving said requests at one of r input switches of said input stage, through one of n inlet links at each of said r input switches, each of said n inlet links having an external load capacity; outputting said requests at one of r output switches of said output stage, through one of n outlet links at each of said r output switches each of said n outlet links having said external load capacity; and routing said requests from said input stage via a plurality of first internal links from each of said input switches, to said output stage via a plurality of second internal links from each of said output switches, said first and second internal links having an internal link load capacity, through one or more of substantially between 2n and 5n center interconnection units where β is the ratio of said internal link load capacity to said external link load capacity, said center interconnection units being connected to each of said r input switches through r first internal links, and connected to each of said r output switches through r second internal links.
Claim 19
Independent Claim
232 words
A method for routing one or more requests having a load between an upper bound B and a lower bound b, between an input stage of switches and an output stage of switches in a three-rate Wide Sense NonBlocking network, said method comprising the steps of: receiving said requests at one of r input switches of said input stage, through one of n inlet links at each of said r input switches, each of said n inlet links having an external load capacity; outputting said requests at one of r output switches of said output stage, through one of n outlet links at each of said r output switches each of said n outlet links having said external load capacity; and routing said requests from said input stage via a plurality of first internal links from each of said input switches, to said output stage via a plurality of second internal links from each of said output switches, said first and second internal links having an internal link load capacity, through one or more of substantially between 2n and 5n center interconnection units where β is the ratio of said internal link load capacity to said external link load capacity, said center interconnection units being connected to each of said r input switches through r first internal links, and connected to each of said r output switches through r second internal links.
Claim 20
Dependent Claim
30 words
A method according to claim 14 wherein said lower bound b is greater than 0.5 and wherein said routing step utilizes one or more of substantially 2n center interconnection units.
Claim 21
Dependent Claim
127 words
A method according to claim 14 wherein said three rates comprise a first rate, a second rate and a third rate, said second rate greater than said first rate and said third rate greater than said second rate, and wherein said first rate is not greater than 0.5 and said second rate is greater than 0.5 and wherein said routing step further comprises the steps of: routing all first rate requests through a first set of 2n center interconnection switches of said substantially between 2n and 5n center interconnection units; and routing all secondary and third rate requests through a second set of 2n center interconnection switches of said substantially between 2n and 5n center interconnection units, said second set and said first set being mutually exclusive.
Claim 22
Dependent Claim
257 words
A method according to claim 14 wherein said three rates comprise a first rate, a second rate and a third rate, said second rate greater than said first rate and said third rate greater than said second rate, and wherein said second rate is not greater than 0.5, and said third rate is greater than 0.5 said routing step further comprising the steps of: routing said third rate requests through a first set of 2n center interconnection units of said substantially between 2n and 5n center interconnection units; and routing said first and second rates as follows: grouping said requests having a load greater than 1/(p+1) into a large group and all other of said requests into a small group; routing said requests of said large group and q 2 requests of said small group to x restricted units of said 3n center interconnection units, wherein the value of x substantially depends on q 1 , q 2 and δ, wherein δ is equal to q 0 +q 2 -2q 1 and q 1 , q 2 and q 0 are defined by the following inequalities: q.sub.0 b≦1<(q.sub.0 +1)b B+q.sub.1 b≦1<B+(q.sub.1 +1)b 2B+q.sub.2 b≦1<2B+(q.sub.2 +1)b such that ##EQU12## where δ equals 1; ##EQU13## where δ equals 0 and q 1 is greater than 2q 2 +1; ##EQU14## where δ=0 and q 1 , equals 2q 2 ; and ##EQU15## where δ equals -1; and routing said requests of said small group other than said q 2 requests to said center interconnection units other than said restricted units.
Claim 23
Dependent Claim
152 words
A method according to claim 14 wherein said three rates comprise a first rate, a second rate and a third rate, said second rate greater than said first rate and said third rate greater than said second rate and wherein said third rate is less than 0.5, and wherein said substantially between 2n and 3n center interconnection units comprise 3.75n center interconnection units, said routing step further comprising the steps of: grouping said requests having a load greater than 1/(p+1) into a large group, and all other of said requests into a small group; routing said requests of said large group to substantially 2βn(p+1)(B+p-1)/p 2 restricted units of said center interconnection units if B is less than approximately 31/32-β/4, and to substantially 2f(β)+1 restricted units of said center interconnection units for all other B; and routing said requests of said small group to said center interconnection units other than said restricted units.
Claim 24
Independent Claim
215 words
A method for routing one or more requests having a load between an upper bound B and a lower bound b, between an input stage of switches and an output stage of switches in a two-rate Wide Sense NonBlocking network, said method comprising the steps of: receiving said requests at one of r input switches of said input stage, through one of n inlet links at each of said r input switches, each of said n inlet links having an external load capacity; outputting said requests at one of r output switches of said output stage, through one of n outlet links at each of said r output switches each of said n outlet links having said external load capacity; and routing said requests from said input stage via a plurality of first internal links from each of said input switches, to said output stage via a plurality of second internal links from each of said output switches, said first and second internal links having an internal link load capacity, through one or more of substantially between 2n and 3n center interconnection units, said center interconnection units being connected to each of said r input switches through r first internal links, and connected to each of said r output switches through r second internal links.
Claim 25
Independent Claim
215 words
A method for routing one or more requests having a load between an upper bound B and a lower bound b, between an input stage of switches and an output stage of switches in a two-rate Wide Sense NonBlocking network, said method comprising the steps of: receiving said requests at one of r input switches of said input stage, through one of n inlet links at each of said r input switches, each of said n inlet links having an external load capacity; outputting said requests at one of r output switches of said output stage, through one of n outlet links at each of said r output switches each of said n outlet links having said external load capacity; and routing said requests from said input stage via a plurality of first internal links from each of said input switches, to said output stage via a plurality of second internal links from each of said output switches, said first and second internal links having an internal link load capacity, through one or more of substantially between 2n and 3n center interconnection units, said center interconnection units being connected to each of said r input switches through r first internal links, and connected to each of said r output switches through r second internal links.
Claim 26
Dependent Claim
39 words
A method according to claim 19 wherein said upper bound B is less than 0.5 and said lower bound b is greater than 0.333, said substantially between 2n and 3n center interconnection units comprising substantially 2n center interconnection units.
Claim 27
Dependent Claim
31 words
A method according to claim 19 wherein said lower bound b is not less than 0.5, said substantially between 2n and 3n center interconnection units comprising substantially 2n center interconnection units.
Claim 28
Dependent Claim
122 words
A method according to claim 19 wherein said upper bound B is not greater than 0.333 and wherein said substantially between 2n and 3n center interconnection units comprising substantially 3n center interconnection units, said routing step further comprising the steps of: grouping said requests having a load greater than 1/(p+1) into a large group, and all other of said requests into a small group; routing said requests of said large group to substantially 2βn(p+1)(B+p-1)/p 2 restricted units of said center interconnection units if B is less than approximately 31/32-β/4, and to substantially 2f(β)+1 restricted units of said center interconnection units for all other B; and routing said requests of said small group to said center interconnection units other than said restricted units.
Claim 29
Dependent Claim
210 words
A method according to claim 19 wherein said upper bound B is greater than 0.333 and less than 0.5 and said lower bound b is less than 0.333, said substantially between 2n and 3n center interconnection units comprising substantially 3n center interconnection units, said routing step further comprising the steps of: grouping said requests having a load greater than 1/(p+1) into a large group and all other of said requests into a small group; routing said requests of said large group and q 2 requests of said small group x restricted units of said 3n center interconnection units, wherein the value of x substantially depends on q 1 , q 2 and δ wherein δ is equal to q 0 +q 2 -2q 1 and q 1 , q 2 and q 0 are defined by the following inequalities: q.sub.0 b≦1<(q.sub.0 +1)b B+q.sub.1 b≦1<B+(q.sub.1 +1)b 2B+q.sub.2 b≦1<2B+(q.sub.2 +1)b such that ##EQU16## where δ equals 1; ##EQU17## where δ equals 0 and q 1 is greater than 2q 2 +1; ##EQU18## where δ=0 and q 1 , equals 2q 2 ; and ##EQU19## where δ equals -1; and routing said requests of said small group other than said q 2 requests to said center interconnection units other than said restricted units.
Claim 30
Dependent Claim
218 words
A method according to claim 19 wherein said upper bound B is greater than 0.5 and said lower bound b is less than 0.5, said substantially between 2n and 3n center interconnection units comprising more than ##EQU20## for q 0 ≦2q 1 and ##EQU21## for q 0 ≧+2q 1 +1, said routing step further comprising the steps of: grouping said requests having a load greater than 1(p+1) into a large group and all other of said requests into a small group; routing said requests of said large group and q 1 requests of said small group x restricted units of said 3n center interconnection units, wherein the value of x substantially depends on q 1 , q 2 and δ wherein δ is equal to q 0 +q 2 -2q 1 , and q 1 , q 2 and q 0 are defined by the following inequalities: q.sub.0 b≦1<(q.sub.0 +1)b B+q.sub.1 b≦1<B+(q.sub.1 +1)b 2B+q.sub.2 b≦1<2B+(q.sub.2 +1)b such that ##EQU22## where δ equals 1; ##EQU23## where δ equals 0 and q 1 is greater than 2q 2 +1; ##EQU24## where δ=0 and q 1 , equals 2q 2 ; and ##EQU25## where δ equals -1; and routing said requests of said small group other than said q 1 requests to said center interconnection units other than said restricted units.
References Cited (Backward Citations)
US4696000A
Cited
US4914429A
Cited
US5469154A
Cited
US5450074A
Cited
US5179551A
Cited
US5451936A
Cited
US5801641A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-30 | 2003-03-01 | 2003-08-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-30 | 2007-03-01 | 2007-08-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-30 | 2011-03-01 | 2011-08-31 | $7700.00 | Window Closed / Lapsed |