Widesense nonblocking switching networks
First Claim
1. 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)/p2 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..
3 Assignments
0 Petitions
Accused Products
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)/p2 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.
39 Citations
24 Claims
-
1. 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)/p2 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.. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9)
-
-
10. 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. - View Dependent Claims (11)
-
-
12. 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)/p2 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.- View Dependent Claims (13)
-
14. 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.- View Dependent Claims (15, 16, 17, 18)
-
19. 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. - View Dependent Claims (20, 21, 22, 23, 24)
Specification