Rearrangeably nonblocking multicast multi-stage networks
First Claim
1. A network having a plurality of multicast connections, said network comprising:
- an input stage comprising r1 input ports, and n1 inlet links in each of said r1 input ports;
an output stage comprising r2 output ports, and n2 outlet links for each of said r2 output ports; and
a middle stage comprising a minimum of at least middle switches where m≧
n1+n2, and each said middle switch comprising at least one link (hereinafter “
first internal link”
) connected to each input port for a total of at least r1 first internal links, each middle switch further comprising at least one link (hereinafter “
second internal link”
) connected to each output port for a total of at least r2 second internal links;
said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change one or two middle switches used in one or two said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
.
1 Assignment
0 Petitions
Accused Products
Abstract
A rearrangeably nonblocking multicast network includes an input stage having r1 switches and n1 inlet links for each of r1 switches, an output stage having r2 switches and n2 outlet links for each of r2 switches. The network also has a middle stage of m switches, and each middle switch has at least one link connected to each input switch for a total of at least r1 first internal links and at least one link connected to each output switch for a total of at least r2 second internal links, where m≧n1+n2. The network has all multicast connections set up such that each multicast connection passes through at most two middle switches to be connected to the destination outlet links. When the number of inlet links in each input switch n1 is equal to the number of outlet links in each output switch n2, and n1=n2=n, a three-stage network is operated in rearrangeably nonblocking manner, where m≧2*n. Also a three-stage network having m>n1+n2 is operated in rearrangeably nonblocking manner even if some multicast connections are set up using more than two middle switches as long as each connection has available links into at least two middle switches.
-
Citations
77 Claims
-
1. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports, and n1 inlet links in each of said r1 input ports;
an output stage comprising r2 output ports, and n2 outlet links for each of said r2 output ports; and
a middle stage comprising a minimum of at least middle switches where m≧
n1+n2, and each said middle switch comprising at least one link (hereinafter “
first internal link”
) connected to each input port for a total of at least r1 first internal links, each middle switch further comprising at least one link (hereinafter “
second internal link”
) connected to each output port for a total of at least r2 second internal links;
said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change one or two middle switches used in one or two said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for setting up one or more multicast connections in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, said method comprising;
receiving a multicast connection at said input stage to set up in MIN(n1, n2) time steps;
fanning out said multicast connection in said input stage into at most two middle switches used in one or two said time steps to set up said multicast connection to a plurality of output ports among said r2 output ports, wherein said plurality of output ports are specified as destinations of said multicast connection, wherein first internal links from said input port to said at most two middle switches used in said one or two time steps and second internal links to said destinations from said at most two middles switches used in said one or two time steps are available;
wherein a connection exists through said network and passes through a middle switch used in one said time step and said method further comprises;
if necessary, changing said connection to pass through another middle switch used in another said time step, act hereinafter “
rearranging connection”
. - View Dependent Claims (8)
- d≦
-
9. A method for setting up one or more new multicast connections in MIN(n1, n2) time steps in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, said method comprising;
disconnecting a previously set up multicast connection through the same input port of said new multicast connection and;
setting up said new multicast connection, through at most two middle switches used in one or two said time steps, first and then setting up said previously set up connection, through at most two middle switches used in one or two time steps. - View Dependent Claims (10, 11, 12, 13, 14)
- d≦
-
15. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches where m≧
2×
n1+n2, and each middle switch comprising at least one link connected to each input port for a total of at least r1 first internal links;
each middle switch further comprising at least one link connected to each output port for a total of at least r2 second internal links,said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change at most three middle switches used in at most three said time steps and used by said existing multicast connection, and the network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (16, 17, 18, 19, 20)
-
-
21. A method for setting up one or more multicast connections in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, said method comprising;
receiving a multicast connection at said input stage to set up in MIN(n1, n2) time steps;
fanning out said multicast connection in said input stage into at most three middle switches used in at most three said time steps to set up said multicast connection to a plurality of output ports among said r2 output ports, wherein said plurality of output ports are specified as destinations of said multicast connection, wherein first internal links from said input port to said at most three middle switches used in said at most three time steps and second internal links to said destinations from said at most three middles switches used in said at most three time steps are available, wherein a connection exists through said network and passes through a middle switch used in one said time step and said method further comprises;
if necessary, changing said connection to pass through another middle switch used in another said time step, act hereinafter “
rearranging connection”
. - View Dependent Claims (22)
- d≦
-
23. A method for setting up one or more new multicast connections in MIN(n1, n2) time steps in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, said method comprising;
disconnecting a previously set up multicast connection through the same input port of said new multicast connection and;
setting up said new multicast connection, through at most three middle switches used in at most three said time steps, first and then setting up said previously set up connection, through at most three middle switches used in at most three time steps. - View Dependent Claims (24, 25, 26, 27, 28)
- d≦
-
29. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches where m≧
(x−
1)*n1+n2, 2<
x≦
MIN(n1, n2), and each middle switch comprising at least one link connected to each input port for a total of at least r1 first internal links;
each middle switch further comprising at least one link connected to each output port for a total of at least r2 second internal links,said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change one or two middle switches used in at most x said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (30, 31, 32, 33, 34)
-
-
35. A method for setting up one or more multicast connections in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, for x≧
2, said method comprising;
receiving a multicast connection at said input stage to set up in MIN(n1, n2) time steps;
fanning out said multicast connection in said input stage into at most x middle switches used in at most x said time steps to set up said multicast connection to a plurality of output ports among said r2 output ports, wherein said plurality of output ports are specified as destinations of said multicast connection, wherein first internal links from said input port to said at most x middle switches used in said at most x time steps and second internal links to said destinations from said at most x middles switches used in said at most x time steps are available, wherein a connection exists through said network and passes through a middle switch used in one said time step and said method further comprises;
changing said connection to pass through another middle switch used in another said time step, the act hereinafter “
rearranging connection”
. - View Dependent Claims (36)
- d≦
-
37. A method for setting up one or more new multicast connections in MIN(n1, n2) time steps in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, for x≧
2, said method comprising;
disconnecting a previously set up multicast connection through the same input port of said new multicast connection and;
setting up said new multicast connection, through at most x middle switches used in at most x time steps, first and then setting up said previously set up connection, through at most x middle switches used in at most x time steps. - View Dependent Claims (38, 39, 40, 41, 42)
- d≦
-
43. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches wherein and x1, x2, . . . , xp≧
1;
wherein, for 1≦
i≦
p, multicast connections from ai inlet links of each input port pass through at most xi middles switches, where x1, x2, . . . , xp≧
2,and each middle switch comprising at least one link connected to each input port for a total of at least r1 first internal links;
each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
d≦
r2,said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change at most xi middle switches used in at most xi said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (44, 45, 46, 47)
-
-
48. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches where m≧
n1+n2, and each middle switch comprising at least one link connected to each input port for a total of at least r1 first internal links;
each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
d≦
r2,said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change one or two middle switches used in one or two said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (49, 50, 51, 52, 53)
-
-
54. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches where m≧
2×
n1+n2, and each middle switch comprising at least one link connected to each input port for a total of at least r1 first internal links;
each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
d≦
r2,said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change at most three middle switches used in at most three said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (55, 56, 57, 58, 59)
-
-
60. A network having a plurality of multicast, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches where m≧
(x−
1)*n1+n2, 2<
x≦
MIN(n1, n2), and each middle switch comprising at least one link connected to each input port for a total of at least r1 first internal links;
each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
d≦
r2, for 2≦
x≦
r2,said network further is always capable of setting up said multicast connection in MIN(n1, n2) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change at most x middle switches used in at most x said time steps and used by said existing multicast connection, and said network is hereinafter “
rearrangeably nonblocking network”
. - View Dependent Claims (61, 62, 63, 64, 65)
-
-
66. A network having a plurality of multicast connections, said network comprising:
-
an input stage comprising r1 input ports and n1 inlet links for each of said r1 input ports, and N1=n1*r1;
an output stage comprising r2 output ports and n2 outlet links for each of said r2 output ports, and N2=n2*r2; and
a middle stage comprising a minimum of at least middle switches wherein and k is an integer, and each middle switch comprising at least one link (hereinafter “
first internal link”
) connected to each input port for a total of at least r1 first internal links, each middle switch further comprising at least one link (hereinafter “
second internal link”
) connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
d≦
r2,wherein at most k multicast connections cannot be set up, (hereinafter “
blocked”
) or at most k existing connections are disconnected to set up new multicast connections. - View Dependent Claims (67, 68, 69, 70, 71)
-
-
72. A method for setting up one or more new multicast connections in MIN(n1, n2) time steps in a network having an input stage having n1*r1 inlet links and r1 input ports, an output stage having n2*r2 outlet links and r2 output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r1 input ports through r1 first internal links and each middle switch further comprising at least one link connected to at most d said output ports for a total of at least d second internal links, wherein 1≦
- d≦
r2, for x≧
2, said method comprising;
disconnecting one or more previously set up multicast connections through the same input port of said new multicast connection and;
setting up said new multicast connection, through at most x middle switches used in at most x time steps, first and then setting up said one or more previously set up connections, through at most x middle switches used in at most x time steps, in all possible combinations of sequential order. - View Dependent Claims (73, 74, 75, 76, 77)
- d≦
Specification