Patent ID: 7397796

Claim:
A method 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, wherein the method comprises: (a) grouping 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 divided into input subsets, and (b) grouping 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 divided into output subsets, (c) receiving cells into the fabric wherein if a cell is a unicast cell, then the cell is associated with an input subset i and associated with an output subset j based on the input port and the output port of the cell, else if a cell is a multicast cell, then the cell is associated with an input subset i and associated with multiple output subsets {j} based on the input port and the multiple output ports of the cell, (d) assigning each cell to a flow, wherein (i) if the cells are unicast cells, then the 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 the cells are multicast cells, then the 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 (e) 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 through 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 N f is the maximum number of flows whose cells pass any given link, and wherein n, N, N f , h, i, j and l are natural numbers, wherein the flow in the fabric is balanced.