Route scheduling of packet streams to achieve bounded delay in a packet switching system

A method for scheduling sending packets over an interconnection network, the interconnection network including a plurality of first stage switch elements, one or more intermediate stages of switch elements, and a final stage switch element, the interconnection network including a plurality of links connecting the plurality of first stage switch elements with each switch element of a next stage of said one or more intermediate stages of switch elements and connecting the final stage switch element with each switch element of a last stare of said one or more intermediate stages of switch elements, the interconnection network including a plurality of non-conflicting paths between the plurality of first stage switch elements over the plurality of links and through said one or more intermediate stages of switch elements to the final stage switch element, the method comprising:

• for each particular first stage switch element of the plurality of first stage switch elements:
• identifying a corresponding portion of a total bandwidth of packets being sent from the plurality of first stage switch elements to the final stage switch element;
• and
• identifying a particular window of said paths corresponding to the corresponding portion of the total bandwidth of packets, the particular window of said paths not including a same path included in a window of paths corresponding to a different one of the plurality of first stage switch elements,
• sending successive packets from one of the first stage switch elements over different paths within the particular window of said paths corresponding to said one of the first stage switch elements;
• wherein the particular window of said each particular first stage switch element is identified by an offset value corresponding to said each particular first stage switch element and a window shift value common to all of the plurality of first stage switch elements;
• and
• wherein the particular one of said paths is identified for each particular first stage switch based on a clock value, the clock value including a first subset of bits and a second set bits, and the window shift value is determined using the first subset of bits and the position within the window is determined based on the second subset of bits.

A packet switch comprising:

• an interconnection network including:
• a of first stage switch element;
• one or more intermediate stages of switch elements;
• a final stage switch element;
• and
• a plurality of links, the interconnection network including a plurality of paths between the first stage switch element over at least some of the plurality of links and through at least some of said one or more intermediate stages of switch elements to the final stage switch element;
• and
• a clock including a first subset of bits and a second set bits;
• wherein the packet switch is configured to send packets over the interconnection network between the first stage switch element to the final stage switch element;
• wherein a particular one of said plurality of paths is identified for the first stage switch clement based on a window shift value and a position within a particular window, the window shift value being determined using the first subset of bits and the position within the window being determined based on the second subset of bits.

A packet switch comprising:

• an interconnection network including:
• a plurality of first stare switch elements;
• one or more intermediate stages of switch elements, a final stage switch element;
• and
• a plurality of links connecting the plurality of first stare switch elements with each switch element of a next stage of said one or more intermediate stages of switch elements and connecting the final stare switch element with each switch element of a last stage of said one or more intermediate stages of switch elements, the interconnection network including a plurality of non-conflicting paths between the plurality of first stage switch elements over the plurality of links and through said one or more intermediate stages of switch elements to the final stage switch element;
• wherein the packet switch is configured to schedule sending packets over the interconnection network, said scheduling for each particular first stage switch element of the plurality of first stage switch elements including;
• identifying a corresponding portion of a total bandwidth of packets being sent from the plurality of first stage switch elements to the final stage switch element;
• and
• identifying a particular window of said paths corresponding to the corresponding portion of the total bandwidth of packets, the Particular widow of said paths not including a same path included in a window of paths corresponding to a different one of the plurality of first stage switch elements;
• wherein the packet switch is configured to schedule sending successive packets from one of the first stage switch elements over different paths within the particular window of said paths corresponding to said one of the first stage switch elements, the particular window of said each particular first stage switch element is identified by an offset value corresponding to said each particular first stage switch element and a window shift value common to all of the plurality of first stage switch elements;
• and
• wherein the particular one of said paths is identified for each particular first stage switch based on a clock value, the clock value includes a first subset of bits and a second set bits, and the window shift value is determined using the first subset of bits and the position within the window is determined based on the second subset of bits.