Multicast routing in self-routing multistage networks

Claim 3

The method of claim 1 wherein the decomposing step and generating step use a Cube routing algorithm to decompose the original multicast request into a plurality of cubes, each cube being an intermediate multicast request identifying a subset of the desired outlets to which an inlet data cell can be routed in a single pass through the network.

Claim 4

The method of claim 2 wherein the decomposing step includes the step of decomposing the original multicast request received by the network into a plurality of cubes, each cube being an intermediate multicast request identifying a subset of the desired outlets to which the inlet data cell is routed in a single pass through the network.

Claim 5

The method of claim 1 wherein the decomposing step uses a Boolean logic minimization procedure to decompose the original multicast request D, defining a set of desired outlets, received by the network into a plurality of intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network.

Claim 6

The method of claim 1 wherein the network includes switching elements of degree larger than 2 and wherein the decomposing step uses a multi-value logic minimization procedure to identify cubes of the original multicast request D, each cube defining an intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request of said network of degree larger than 2.

Claim 9

The method of claim 6 wherein the plurality of cubes are partitioned using a Greedy partitioning algorithm to select the largest possible cubes C=(C 1 . . . C r ) in descending order of their size to obtain the set P=(P 1 . . . P m ), where each P is a cube with |P|≦|P 1+1 |, and where m is an integer.

Claim 10

The method of claim 7 wherein the greedy partitioning algorithm is characterized by the following steps: (a) choosing and removing the largest cube from the plurality of cubes C (b) choosing and removing the next largest cube from the remaining plurality of cubes that does not contain any of the outlets previously identified, (c) repeating step (b) until all the desired outlets are identified, and wherein the cubes selected in steps (a) and (b) are the set P which is the partition of D where P={P 1 P 2 , . . . , P m }, where each P is a cube with |P 1 |≧|P 1+1 | and where m is an integer.

Claim 11

The method of claim 2 wherein said generating step includes the steps of (a) selecting and removing a largest cube from an outlet set P where P={P 1 , P 2 , . . . , P m }, where each P is a cube with |P 1 |≧|P 1+1 | and where m is an integer, (b) using the outlets of the largest cube as inlets for a second stage of a build-up of a multicast tree, (c) for each inlet, selecting and removing a next largest cube from the set P that does not cause blocking with existing cubes in a current stage, (d) using the outlets of the identified cubes as the inlets of a next stage, and (e) repeating steps (c) and (d) until all the cubes in the set P have been identified.

Claim 12

The method of claim 9 wherein a non-blocking condition is determined by the following steps (a) computing the distance between two inlets s 1 , s 2 of the network, the distance being a least significant bit position in which s 1 and s 2 , in binary representation, disagree, (b) computing the distance between two cubes C 1 , C 2 at the output of the network as a most significant bit position, excluding `don't care x` positions, in which C 1 and C 2 in binary representation disagree, and (c) identifying multicast connections as non-blocking when two selected inlets of the network which are at a distance d in and which are connected to two disjoint cubes at a distance d out satisfy the equation d.sub.out -d.sub.in ≧0.

Claim 13

The method of claim 1 wherein the decomposing step and generating step use a copy routing algorithm which performs the following steps recursively (A) generate 2 a i copies at contiguous outlets, for any a i =0, where |D|=a n-1 , a n-2 , . . . , a 0 , where a and n are integer numbers and (B) each of these copies reach a desired outlet selected from D in either a decreasing or an increasing order.

Claim 16

The method of claim 1 wherein the decomposing step and generating step use a combined routing algorithm which includes a copy routing algorithm for stage one of the network and a cube routing algorithm for other stages of the network, wherein the copy routing algorithm performs the following steps recursively (A) generate 2 a i copies at contiguous outlets, for any a i =0, where |D|=a n-1 , a n-2 , . . . a 0 , where a and n are integer numbers and (B) each of these copies reach a desired outlet selected from D in either a decreasing or an increasing order, and and wherein the cube routing algorithm performs the partition P of the multicast request D to form a multicast tree, each node of the multicast tree corresponding to a cube in P, where P={P 1 , P 2 , . . . , P m }, where each P is a cube with |P|≧|P 1+1 |, and m is an integer.

Claim 19

The method of claim 14 wherein the decomposing step uses a Boolean logic minimization procedure to decompose the original multicast request D, defining a set of desired outlets, received by the network into a plurality of intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network.

Claim 20

The method of claim 1 wherein the decomposing step uses the Quine-McCluskey method to identify thereby a plurality of cubes C=(C 1 . . . C r ), each cube C 1 . . . C r being an intermediate multicast request identifying a unique subset of desired outlets to cast request which identifies desired outlets to which the inlet data cell is routed in a single pass through the network.

Claim 21

The method of claim 6 wherein the plurality of cubes are partitioned using a Greedy partitioning algorithm to select the largest possible cubes C=(C 1 . . . C r ) in descending order of their size to obtain the set P=(P 1 . . .P m ), where each P is a cube with |P 1 |≧|P 1+1 |, and where m is an integer.

Claim 22

The method of claim 17 wherein the greedy partitioning algorithm is characterized by the following steps: (a) choosing and removing the largest cube from the plurality of cubes C, (b) choosing and removing the next largest cube from the remaining plurality of cubes that does not contain any of the outlets previously identified, (c) repeating step (b) until all the desired outlets are identified, and wherein the cubes selected in steps (a) and (b) are the set P which is the partition of D, where P=(P 1 . . . P m ), where each P is a cube with |P 1 |≧|P 1+1 |, and where m is an integer.

Claim 23

The method of claim 14 wherein said generating step includes the steps of (a) using outlets of the generating step (a) of claim 13 as the inlets for a second stage of a build-up of a multicast tree, (b) for each inlet, selecting and removing the next largest cube from an output set P that does not cause blocking with existing cubes in the current stage, where P=(P 1 . . . P m ), where each P is a cube with |P 1 |≧|P 1+1 |, and where m is an integer. (c) using the outlets of the identified cubes as the inlets of a next stage, and (d) repeating steps (b) and (c) until all the cubes in the set P have been identified.

Claim 24

The method of claim 19 wherein a non-blocking condition is determined by the following steps: (a) computing the distance between two inlets s 1 , s 2 of the network, the distance being a least significant bit position in which s 1 and s 2 in binary representation disagree, (b) computing the distance between two cubes C 1 , C 2 at the output of a network as the most significant bit position, excluding `don't care x` positions, in which C 1 and C 2 in binary representation disagree, and (c) identifying multicast connections as non-blocking when two selected inlets of the network which are at a distance d in and which are connected to two disjoint cubes at a distance d out satisfy the equation d.sub.out -d.sub.out ≧0.

Claim 25

A self-routing multistage network apparatus, having n=log N stages, where N is the number of inlets/outlets of the network, for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into a plurality of intermediate multicast requests, each intermediate multicast request including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets by recirculation of at least one intermediate multicast request through the network.

Claim 26

A self-routing multistage network apparatus, having n=log N stages, where N is the number of inlets/outlets of the network, for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into a plurality of intermediate multicast requests, each intermediate multicast request including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets by recirculation of at least one intermediate multicast request through the network.

Claim 27

A self-routing multistage network apparatus for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets wherein said decomposing means utilizes a cube routing algorithm to decompose the original multicast request into a plurality of cubes, each cube being an intermediate multicast request identifying a subset of the desired outlets to which an inlet data cell can be routed in a single pass through the apparatus and said generating means utilizes a cube routing algorithm to generate a non-blocking multicast tree based on the plurality of cubes.

Claim 28

A self-routing multistage network apparatus for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets wherein said decomposing means utilizes a cube routing algorithm to decompose the original multicast request into a plurality of cubes, each cube being an intermediate multicast request identifying a subset of the desired outlets to which an inlet data cell can be routed in a single pass through the apparatus and said generating means utilizes a cube routing algorithm to generate a non-blocking multicast tree based on the plurality of cubes.

Claim 29

The apparatus of claim 22 including two or more switching apparatuses to pipeline the routing of sequential data cells through the network apparatus to reduce transit time of each data cell.

Claim 30

A self-routing multistage network apparatus for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets wherein said decomposing means and said generating means utilize a copy routing algorithm and wherein said apparatus further comprises a first switching apparatus including said decomposing means and a second switching apparatus, connected to said first switching apparatus, which together with said first switching apparatus includes said generating means.

Claim 31

A self-routing multistage network apparatus for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets wherein said decomposing means and said generating means utilize a copy routing algorithm and wherein said apparatus further comprises a first switching apparatus including said decomposing means and a second switching apparatus, connected to said first switching apparatus, which together with said first switching apparatus includes said generating means.

Claim 32

A self-routing multistage network apparatus for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets wherein said decomposing means and said generating means utilize a combined routing algorithm and wherein said apparatus further comprises a first switching apparatus including means for generating 2 j copies of the inlet data cell where j=max{i|a.sub.i ≠0;0≦o≦n-1, where a is an integer, where n=an integer number equal to the number of stages in the network a second switching apparatus including decomposing means for decomposing the original multicast request into a plurality of cubes, each cube being an intermediate multicast request identifying a subset of desired outlets to which an inlet data cell can be routed in a single pass through the apparatus, and generating means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets.

Claim 33

A self-routing multistage network apparatus for multicasting an inlet data cell, received as part of an original multicast request D, to a plurality of desired outlets, the apparatus comprising means for decomposing the original multicast request D, defining a set of desired outlets, received by a single self-routing multistage network into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request and including a routing tag which enables a non-blocking, self-routing distribution to a subset of the desired outlets of the original multicast request in one or two passes through the network, and means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets wherein said decomposing means and said generating means utilize a combined routing algorithm and wherein said apparatus further comprises a first switching apparatus including means for generating 2 j copies of the inlet data cell where j=max{i|a.sub.i ≠0;0≦o≦n-1, where a is an integer, where n=an integer number equal to the number of stages in the network a second switching apparatus including decomposing means for decomposing the original multicast request into a plurality of cubes, each cube being an intermediate multicast request identifying a subset of desired outlets to which an inlet data cell can be routed in a single pass through the apparatus, and generating means for generating a non-blocking multicast tree based on the intermediate multicast requests and for routing the received inlet data cell to the desired outlets.

Claim 34

The method of claim 1 wherein the decomposing step uses the Quine-McCluskey method to identify the plurality of cubes C=(C 1 . . . C r ), each cube C 1 . . . C r being an intermediate multicast request identifying a unique subset of the original multicast request which identifies desired outlets to which the inlet data cell is routed in a single pass through the network.