Load balancing algorithms in non-blocking multistage packet switches

An article of manufacture for balancing unicast or multicast flows in a multistage non-blocking fabric, wherein the fabric comprises at least one internal switching element (SE) stage, wherein the stage has 1 internal switching elements, wherein each internal switching element is associated with a unique numerical identifier, and wherein the fabric comprises an input SE stage and an output SE stage, wherein the article comprises:

• a computer readable medium containing one or more programs which when executed implement the steps of:
• (a) dividing input ports into input sets whereby each input set consists of input ports that transmit through the same input SE, and wherein the input sets are further divided into input subsets, and
• (b) dividing output ports into output sets whereby each output set consists of output ports that receive cells through the same output SE, and wherein the output sets are further divided into output subsets,
• (c) assigning each cell received into the fabric to a flow comprising:
• (i) if a cell is a unicast cell, then associating the cell received into the fabric with an input subset and with an output subset based on the input port i and the output port j of the cell, wherein cells which are associated with the same input subset and associated with the same output subset are assigned to the same flow, else
• (ii) if a cell is a multicast cell, then the cell is associated with an input subset and associated with multiple output subsets based on the input port i and the multiple output ports {j} of the cell, wherein cells which are associated with the same input subset and associated with the output subsets of the same output sets are assigned to the same flow, and
• (d) transmitting flows through the internal SE stage wherein cells of a particular flow are distributed among the internal switching elements, wherein the quantity of the cells of each particular flow transmitted at each internal SE differs by at most h, wherein h is positive,
• wherein the number of subsets of at least one input set or at least one output set is less than n, wherein n is the number of ports of that input SE or of that output SE, and wherein N is the total number of input ports and output ports, and wherein Nf, is the maximum number of flows whose cells pass any given link, and wherein n, N, Nf, h, i, j and l are natural numbers.

An apparatus for balancing unicast or multicast flows in a multistage non-blocking fabric, wherein the fabric comprises at least one internal switching element (SE) stage, wherein the stage has l internal switching elements, wherein each internal switching element is associated with a unique numerical identifier, and wherein the fabric comprises an input SE stage and an output SE stage, the apparatus comprises:

• a flow control device configured to:
• (a) divide input ports into input sets whereby each input set consists of input ports that transmit through the same input SE, and wherein the input sets are further divided into input subsets, and
• (b) divide output ports into output sets whereby each output set consists of output ports that receive cells through the same output SE, and wherein the output sets are further divided into output subsets,
• (c) assign each cell received into the fabric to a flow comprising:
• (i) if a cell is a unicast cell, then associate the cell received into the fabric with an input subset and with an output subset based on the input port i and the multiple output ports {j} of the cell, wherein cells which are associated with the same input subset and associated with the same output subsets are assigned to the same flow, else
• (ii) if a cell is a multicast cell, then the cell is associate with an input subset and associated with multiple output subsets based on the input port i and the multiple output ports {j} of the cell, wherein cells which are associated with the same input subset and associated with the output subsets of the same output sets are assigned to the same flow, and
• (d) transmit flows through the internal SE stage wherein cells of a particular flow are distributed among the internal switching elements, wherein the quantity of the cells of each particular flow transmitted at each internal SE differs by at most h, wherein h is positive,
• wherein the number of subsets of at least one input set or at least one output set is less than n, wherein n is the number of ports of that input SE or of that output SE, and wherein N is the total number of input ports and output ports, and wherein Nf is the maximum number of flows whose cells pass any given link, and wherein n, N, Nf, h, i, j and l are natural numbers.

A multistage non-blocking switch comprising:

• (a) at least one internal switching element (SE) stage, wherein the stage has l internal switching elements, wherein each internal switching element is associated with a unique numerical identifier,
• (b) an input SE stage,
• (c) an output SE stage,
• (d) input ports which are divided into input sets wherein each input set consists of input ports that transmit through the same input SE, and wherein the input sets are further divided into input subsets, and
• (e) output ports which are divided into output sets wherein each output set consists of output ports that receive cells through the same output SE, and wherein the output sets are further divided into output subsets, and
• (f) a flow assignment module wherein the module assigns cells which are received into the fabric to a flow, wherein the assignment comprises
• (i) if a cell is a unicast cell, then the cell is associated with an input subset and associated with an output subset based on the input port i and the output port j of the cell, wherein cells which are associated with the same input subset and associated with the same output subset are assigned to the same flow, else
• (ii) if a flow is a multicast flow, then each cell is associated with an input subset and associated with multiple output subsets based on the input port i and the multiple output ports {j} of the cell, wherein cells which are associated with the same input subset and associated with the output subsets of the same output sets are assigned to the same flow,
• whereby flows are transmitted through the internal SE stage wherein cells of a particular flow are distributed among the internal switching elements, wherein the quantity of the cells of each particular flow transmitted at each internal SE differs by at most h, wherein h is positive,
• wherein the number of subsets of at least one input set or at least one output set is less than n, wherein n is the number of ports of that input SE or of that output SE, and wherein N is the total number of input ports and output ports, and wherein Nf, is the maximum number of flows whose cells pass any given link, and wherein n, N, Nf, h, i, j and l are natural numbers.