Rearrangeably nonblocking multicast multi-stage networks

• US 20060165085A1
• Filed: 12/27/2005
• Published: 07/27/2006
• Est. Priority Date: 09/27/2001
• Status: Abandoned Application

• Current Assignee: TEAK Technologies Incorporated
• Original Assignee: TEAK Technologies Incorporated
• Inventors: Konda, Venkat
• Application Number:
  US11/321,287
• Publication Number:
  US 20060165085A1
• Time in Patent Office: Days
• US Class Current: 370/395.100
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04Q 1/00 Details of selecting apparatus or arrangements
• CPC Class Codes: H04Q 2213/1302 Relay switches
• CPC Class Codes: H04Q 2213/1304 Coordinate switches, crossbar, 4/2 with relays, coupling field
• CPC Class Codes: H04Q 2213/13146 Rerouting upon blocking/overload, rearrangement
• CPC Class Codes: H04Q 2213/13242 Broadcast, diffusion, multicast, point-to-multipoint (1 : N)
• CPC Class Codes: H04Q 2213/1334 Configuration within the switch
• CPC Class Codes: H04Q 2213/13341 Connections within the switch
• CPC Class Codes: H04Q 3/00 Selecting arrangements H04Q5/00 - H04Q11/00 take precedence
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

Abstract

A rearrangeably nonblocking multicast network includes an input stage having r₁ switches and n₁ inlet links for each of r₁ switches, an output stage having r₂ switches and n₂ outlet links for each of r₂ 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 r₁ first internal links and at least one link connected to each output switch for a total of at least r₂ second internal links, where m≧n₁+n₂. 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 n₁ is equal to the number of outlet links in each output switch n₂, and n₁=n₂=n, a three-stage network is operated in rearrangeably nonblocking manner, where m≧2*n. Also a three-stage network having m>n₁+n₂ 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.

Claims

1. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports, and n₁ inlet links in each of said r₁ input ports;

an output stage comprising r₂ output ports, and n₂ outlet links for each of said r₂ output ports; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches where m≧

n₁+n₂, 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 r₁ 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 r₂ second internal links;

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) 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”

.

2. The network of claim 1 wherein each multicast connection from an inlet link passes through at most two middle switches used in one or two said time steps, and said multicast connection further passes to a plurality of outlet links from said at most two middle switches used in said one or two time steps.

3. The network of claim 1 further comprising a controller coupled to each of said input, output and middle stages to set up said multicast connection.

4. The network of claim 1 wherein said r₁ input ports and r₂ output ports are the same number of ports.

5. The network of claim 1 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least 2.

6. The network of claim 1,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

7. A method for setting up one or more multicast connections in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, said method comprising;

receiving a multicast connection at said input stage to set up in MIN(n₁, n₂) 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 r₂ 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”

.

8. The method of claim 7,

wherein any of said acts of fanning out and rearranging are performed recursively.

9. A method for setting up one or more new multicast connections in MIN(n₁, n₂) time steps in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, 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.

10. The method of claim 9 further comprising:

when any one of said two setting up acts fail, disconnecting said new multicast connection if it succeeded to get set up, and setting up said previously set up connection if it failed to get set up.

11. The method of claim 9 further comprising:

repeating said acts of disconnecting a previously set up connection and setting up after said new multicast connection for all the remaining previously set up connections in the same input port.

12. The method of claim 9 further comprising:

by setting up said new multicast connection through two middle switches used in one or two time steps having available first internal links so that only one of said two middle switches used in one of said two time steps use second internal links which are already in use by one or more existing multicast connections from other input ports (hereinafter called “

incompatible existing connections”

); and

disconnecting said incompatible existing connections.

13. The method of claim 9 further comprising:

for all said incompatible existing connections recursively repeating said acts of disconnecting and setting up connections in their respective first ports, until all said incompatible existing connections are set up.

14. The method of claim 9 wherein any of said acts of checking, setting up and disconnecting are performed recursively.

15. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches where m≧

2×

n₁+n₂, and each middle switch comprising at least one link connected to each input port for a total of at least r₁ first internal links;

each middle switch further comprising at least one link connected to each output port for a total of at least r₂ second internal links,

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) 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”

.

16. The network of claim 15 wherein each multicast connection from an inlet link passes through at most three middles switches used in at most three said time steps, and said multicast connection further passes to a plurality of outlet links from said at most three middle switches used in said at most three time steps.

17. The network of claim 15 comprising a controller in communication with said input, output and middle stages to set up said multicast connection.

18. The network of claim 15 wherein said r₁ input ports and r₂ output ports are the same number of ports.

19. The network of claim 15 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least 3.

20. The network of claim 15,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

21. A method for setting up one or more multicast connections in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, said method comprising;

receiving a multicast connection at said input stage to set up in MIN(n₁, n₂) 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 r₂ 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”

.

22. The method of claim 21,

wherein any of said acts of fanning out and rearranging are performed recursively.

23. A method for setting up one or more new multicast connections in MIN(n₁, n₂) time steps in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, 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.

24. The method of claim 23 further comprising:

when any one of said two setting up acts fail, disconnecting said new multicast connection if it succeeded to get set up, and setting up said previously set up connection if it failed to get set up.

25. The method of claim 23 further comprising:

repeating said acts of disconnecting a previously set up connection and setting up after said new multicast connection for all the remaining previously set up connections in the same input port.

26. The method of claim 23 further comprising:

by setting up said new connection through three middle switches used in at most three time steps having available first internal links so that only one of said three middle switches used in one of said three time steps use second internal links which are already in use by one or more existing multicast connections from other input ports (hereinafter called “

incompatible existing connections”

); and

disconnecting said incompatible existing connections.

27. The method of claim 23 further comprising:

for all said incompatible existing connections recursively repeating said acts of disconnecting and setting up connections in their respective first ports, until all said incompatible existing connections are set up.

28. The method of claim 23 wherein any of said acts of checking, and setting up are performed recursively.

29. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches where m≧

(x−

1)*n₁+n₂, 2<

x≦

MIN(n₁, n₂), and each middle switch comprising at least one link connected to each input port for a total of at least r₁ first internal links;

each middle switch further comprising at least one link connected to each output port for a total of at least r₂ second internal links,

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) 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”

.

30. The network of claim 29 wherein each multicast connection from an inlet link passes through at most x middle switches, and said multicast connection further passes to a plurality of outlet links from said at most x middle switches used in at most x said time steps.

31. The network of claim 29 comprising a controller in communication with said input, output and middle stages to set up said multicast connection.

32. The network of claim 29 wherein said r₁ input ports and r₂ output ports are the same number of ports.

33. The network of claim 29 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least x.

34. The network of claim 29,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

35. A method for setting up one or more multicast connections in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, for x≧

2, said method comprising;

receiving a multicast connection at said input stage to set up in MIN(n₁, n₂) 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 r₂ 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”

.

36. The method of claim 35 wherein any of said acts of fanning out and rearranging is performed recursively.

37. A method for setting up one or more new multicast connections in MIN(n₁, n₂) time steps in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, 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.

38. The method of claim 37 further comprising:

when any one of said two setting up acts fail, disconnecting said new multicast connection if it succeeded to get set up, and setting up said previously set up connection if it failed to get set up.

39. The method of claim 37 further comprising:

repeating said acts of disconnecting a previously set up connection and setting up after said new multicast connection for all the remaining previously set up connections in the same input port.

40. The method of claim 37 further comprising:

by setting up said new connection through x middle switches used in at most x time steps having available first internal links so that only one of said x middle switches used in one of said x time steps use second internal links which are already in use by one or more existing multicast connections from other input ports (hereinafter called “

incompatible existing connections”

); and

disconnecting said incompatible existing connections.

41. The method of claim 37 further comprising:

for all said incompatible existing connections recursively repeating said acts of disconnecting and setting up connections in their respective first ports, until all said incompatible existing connections are set up.

42. The method of claim 37 wherein any of said acts of checking, and setting up are performed recursively.

43. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches wherein

$m\ge <br><br>\underset{i=1}{\overset{p}{\sum <br><br>}}<br><br>x_i*a_i,\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i=1}{\overset{p}{\sum <br><br>}}<br><br>a_i=n_1+n_2$

and x₁, x₂, . . . , x_p≧

1;

wherein, for 1≦

i≦

p, multicast connections from a_i inlet links of each input port pass through at most x_i middles switches, where x₁, x₂, . . . , x_p≧

2,

and each middle switch comprising at least one link connected to each input port for a total of at least r₁ 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≦

r₂,

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) time steps by changing the path, defined by passage of an existing multicast connection, thereby to change at most x_i middle switches used in at most x_i said time steps and used by said existing multicast connection, and said network is hereinafter “

rearrangeably nonblocking network”

.

44. The network of claim 43 comprising a controller in communication with said input, output and middle stages to set up said multicast connection used in at most x_i said time steps.

45. The network of claim 43 wherein said r₁ input ports and r₂ output ports are the same number of ports.

46. The network of claim 43 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least x.

47. The network of claim 43,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

48. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches where m≧

n₁+n₂, and each middle switch comprising at least one link connected to each input port for a total of at least r₁ 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≦

r₂,

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) 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”

.

49. The network of claim 48 wherein each multicast connection from an inlet link passes through at most two middle switches used in one or two said time steps, and said multicast connection further passes to a plurality of outlet links from said at most two middle switches used in said one or two time steps.

50. The network of claim 48 comprising a controller in communication with said input, output and middle stages to set up said multicast connection.

51. The network of claim 48 wherein said r₁ input ports and r₂ output ports are the same number of ports.

52. The network of claim 48 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least 2.

53. The network of claim 48,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

54. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches where m≧

2×

n₁+n₂, and each middle switch comprising at least one link connected to each input port for a total of at least r₁ 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≦

r₂,

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) 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”

.

55. The network of claim 54 wherein each multicast connection from an inlet link passes through at most three middle switches used in at most three said time steps, and said multicast connection further passes to a plurality of outlet links from said at most three middle switches used in said at most three time steps.

56. The network of claim 54 comprising a controller in communication with said input, output and middle stages to set up said multicast connection.

57. The network of claim 54 wherein said r₁ input ports and r₂ output ports are the same number of ports.

58. The network of claim 54 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least 3.

59. The network of claim 54,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

60. A network having a plurality of multicast, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches where m≧

(x−

1)*n₁+n₂, 2<

x≦

MIN(n₁, n₂), and each middle switch comprising at least one link connected to each input port for a total of at least r₁ 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≦

r₂, for 2≦

x≦

r₂,

said network further is always capable of setting up said multicast connection in MIN(n₁, n₂) 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”

.

61. The network of claim 60 wherein each multicast connection from an inlet link passes through at most x middle switches, and said multicast connection further passes to a plurality of outlet links from said at most x middle switches used in at most x said time steps.

62. The network of claim 60 comprising a controller in communication with said input, output and middle stages to set up said multicast connection.

63. The network of claim 60 wherein said r₁ input ports and r₂ output ports are the same number of ports.

64. The network of claim 60 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least x.

65. The network of claim 60,

wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

66. A network having a plurality of multicast connections, said network comprising:

an input stage comprising r₁ input ports and n₁ inlet links for each of said r₁ input ports, and N₁=n₁*r₁;

an output stage comprising r₂ output ports and n₂ outlet links for each of said r₂ output ports, and N₂=n₂*r₂; and

a middle stage comprising a minimum of at least

$s=\frac{m}{\mathrm{MIN}<br><br>\left(n_1,n_2\right)}$

middle switches wherein

$m=n_1+n_2-2*k,\mathrm{for}<br><br>\text{\hspace{1em}<br><br>}<br><br>1\le <br><br>k\le <br><br>\lceil <br><br>\frac{\left(n_1+n_2\right)}{2}\rceil <br><br>$

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 r₁ 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≦

r₂,

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.

67. The network of claim 66 wherein each multicast connection from an inlet link passes through at most two middle switches used in one or two said time steps, and said multicast connection further passes to a plurality of outlet links from said at most two middle switches used in said one or two time steps.

68. The network of claim 66 further comprising a controller coupled to each of said input, output and middle stages to set up said multicast connection.

69. The network of claim 66 wherein said r₁ input ports and r₂ output ports are the same number of ports.

70. The network of claim 66 wherein said n₁ inlet links and n₂ outlet links are the same number of queues and n₁=n₂=n, then s is a minimum of at least

$2-\frac{2⨯}{}$

k n ,

for 1≦

k<

n.

71. The network of claim 66, wherein each of said input ports, or each of said output ports, or each of said middle switches further recursively comprise one or more networks.

72. A method for setting up one or more new multicast connections in MIN(n₁, n₂) time steps in a network having an input stage having n₁*r₁ inlet links and r₁ input ports, an output stage having n₂*r₂ outlet links and r₂ output ports, and a middle stage having s middle switches, where each middle switch is connected to each of said r₁ input ports through r₁ 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≦

r₂, 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.

73. The method of claim 72 further comprising:

when any one of said setting up acts fail, disconnecting said new multicast connection if it succeeded to get set up, and setting up one or more said previously set up connections if they failed to get set up.

74. The method of claim 72 further comprising:

repeating said acts of disconnecting a previously set up connection and setting up after said new multicast connection for all the other one or more groups of previously set up connections in the same input port.

75. The method of claim 72 further comprising:

by setting up said new connection through x middle switches used in at most x time steps having available first internal links so that only one of said x middle switches used in at most x time steps use second internal links which are already in use by one or more existing multicast connections from other input ports (hereinafter called “

incompatible existing connections”

); and

disconnecting said incompatible existing connections.

76. The method of claim 72 further comprising:

for all said incompatible existing connections recursively repeating said acts of disconnecting and setting up connections in their respective first ports, until all said incompatible existing connections are set up.

77. The method of claim 72 wherein any of said acts of checking, and setting up are performed recursively.