Multicast routing in self-routing multistage networks

A method for multicasting an inlet data cell, received as part of an original multicast request D, through a self-routing multistage network apparatus to a plurality of desired outlets, the method comprising the steps of

• 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 generating a non-blocking multicast tree based on the intermediate multicast requests and routing the received inlet data cell to the desired outlets, wherein
• the decomposing step and generating step use a copy routing algorithm and wherein
• the decomposing step of the copy routing algorithm includes the steps of
• (a) generating 2.sup.a.sbsp.i copies of the inlet data cell at contiguous outlets, and
• (b) for each of the copies, addressing a desired outlet of D in either a decreasing or increasing order;
• and wherein
• the generating step includes the step of
• repeating steps (a) and (b), for any a.sub.i .noteq.0, where o .ltoreq.i.ltoreq.n-1, where a is an integer, where n=an integer number equal to the number of stages in the network, and where the multicast request is defined as .vertline.D.vertline.=a.sub.n-1, a.sub.n-2. . . a.sub.0, so as to generate a non-blocking multicast tree.

A method for multicasting an inlet data cell, received as part of an original multicast request D, through a self-routing multistage network apparatus to a plurality of desired outlets, the method comprising the steps of

• 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 generating a non-blocking multicast tree based on the intermediate multicast requests and routing the received inlet data cell to the desired outlets, wherein
• the decomposing step and generating step use a combined routing algorithm and wherein
• the decomposing step includes the steps of
• (a) generating 2.sup.j copies of the inlet data cell where
• j=max{.vertline.a.sub.i .noteq.0;0.ltoreq.i.ltoreq.n-1,
• where a is an integer and n=an integer number equal to the number of stages in the network.
• (b) decomposing the original multicast request into a plurality of cubes C=(C.sub.1. . . C.sub.r), each cube C.sub.1. . . C.sub.r being an intermediate multicast request identifying a subset of desired network outlets to which an inlet data cell can be routed in a single pass through the network, and
• (c) generating a non-blocking multicast tree based on the intermediate multicast requests and routing the received inlet data cell to the desired outlets.

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.

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.

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.sup.j copies of the inlet data cell where
• j=max{i.vertline.a.sub.i .noteq.0;0.ltoreq.o.ltoreq.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.