Load Balancing Algorithms in Non-Blocking Multistage Packet Switches

Abstract

The present invention provides 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, an input SE stage and an output SE stage. The method comprises: (a) receiving cells into the fabric wherein each cell is associated with an input subset and associated with an output subset according to the source and destination address of the cell, (b) assigning each cell to a flow, wherein cells sourced from the same input subset, and bound for the same output subset, or multiple output subsets, are assigned to the same flow, and (c) transmitting flows through the internal SE stage wherein cells of a particular flow are distributed among the internal switching elements, wherein the cells of each particular flow transmitted at each internal SE differs by at most h, wherein h is positive, whereby the flow in the fabric is balanced.

1 . 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, an input SE stage and an output SE stage, wherein the method comprises:
 (a) receiving cells into the fabric wherein each cell is associated with an input subset and associated with an output subset according to the source and destination address of the cell,   (b) assigning each cell to a flow, wherein cells sourced from the same input subset, and bound for the same output subset, or multiple output subsets, are assigned to the same flow, and   (c) transmitting flows through the internal SE stage wherein cells of a particular flow are distributed among the internal switching elements, wherein the cells of each particular flow transmitted at each internal SE differs by at most h, wherein h is positive,   
     whereby the flow in the fabric is balanced.