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.

Description

[0001]This application claims benefit from U.S. provisional Application Ser. No. 60 / 496,978, filed on Aug. 21, 2003, which application is incorporated herein by reference in its entirety.TECHNICAL FIELD[0002]The invention relates generally to methods, and apparatuses, for balancing data flows through multistage networks.BACKGROUND OF THE INVENTION[0003]Clos circuit switch has been proposed by Clos in 1953 at Bell Labs (C. Clos, “A study of non-blocking switching networks,”Bell Systems Technology Journal 32:406-424 (1953)). FIG. 1 shows the connections between switching elements (SE) in a symmetric Clos three-stage switch. This interconnection rule is: the xth SE in some switching stage is connected to the xth input of each SE in the next stage (C. Clos, 32:406-424 (1953); J. Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Press 1990; F. K. Hwang, The mathematical theory of nonblocking switching networks, World Scientific, 1998). Here, all connect...

AI Technical Summary

Benefits of technology

[0013]The present invention pertains to load balancing algorithms for non-blocking multistage packet switches. These algorithms allow for maximization of fabric utilization while providing a guaranteed delay.

Problems solved by technology

While the complexity of the switching fabric hardware is reduced, the complexity of the algorithm for a circuit setup is increased.

Algorithms for circuit setup in Clos circuit switches cannot be readily applied in Clos packet switches.

Then, an implementation of the algorithm that rearranges connections on a cell-by-cell basis in SEs of a rearrangeable non-blocking Clos switch would be prohibitively complex (J. Hui, Kluwer Academic Press 1990).

However, the delay that packets experience through the Clos switch has not been assessed.

The delay for such load balancing mechanism is too long.

Accordingly, a challenge in the field is providing a minimum required delay guarantee without unacceptably decreasing fabric utilization.

Images