SYSTEMS AND METHODS FOR PROGRAMMING CONNECTIONS THROUGH A MULTI-STAGE SWITCH FABRIC WITH BLOCKING RECOVERY, BACKGROUND REBALANCING, AND ROLLBACK

• US 20080285449A1
• Filed: 05/17/2007
• Published: 11/20/2008
• Est. Priority Date: 05/17/2007
• Status: Active Grant

• Current Assignee: Ciena Corporation
• Original Assignee: Ciena Corporation
• Inventors: Aluri, Neena, Bjelcevic, Goran, Gopalakrishna, Satish Mysore, Larsson, Gustav Karl
• Granted Patent: US 8,649,370 B2
• Time in Patent Office: Days
• US Class Current: 370/232
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

The present invention provides systems and methods for programming connections through a multi-stage switch fabric. The present invention utilizes load-balancing, blocking recovery, background rebalancing, and rollback algorithms to select and manage connection balance on center stage switches in the multi-stage switch fabric for new and modified connections. The load-balancing algorithm attempts to spread the multi-connection slices across center stage switches as evenly as possible, to increase the probability that future multi-connection slices can be added without needing to rearrange existing slices. Advantageously, the present invention is efficient by making the best possible local decision for one multi-connection slice at a time, without considering other multi-connection slices that may also need center switch assignments. Additionally blocking recovery, rollback and background rebalancing features are also supported.

Claims

1. A method for programming a multi-connection slice through a multi-stage switch fabric comprising a plurality of ingress switches interconnected to a plurality of center stage switches interconnected to a plurality of egress switches, comprising:

receiving a multi-connection slice request, wherein the multi-connection slice comprises the flow in a single direction across the multi-stage switch fabric from one of the plurality of ingress switches to one of the plurality of egress switches, and wherein the request comprises the number of channels;

computing an imbalance for all links from the one of the plurality of ingress switches to each of the plurality of center stage switches and from the one of the plurality of egress switches to each of the plurality of center stage switches; and

selecting a center stage switch of the plurality of center stage switches responsive to the lowest imbalance from the computing step.

2. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 1, further comprising:

performing blocking recovery if the selecting step fails due to blocking on one or more links, wherein blocking recovery rearranges multi-connection slices on the one or more links so that the multi-connection slice request can be added.

3. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 2, wherein blocking recovery comprises:

randomly selecting one or more channels on the one or more links;

finding multi-connection slices for each of the randomly selected one or more channels; and

reallocating each of the multi-connection slices for each of the randomly selected one or more channels to a new center stage switch of the plurality of center stage switches.

4. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 3, wherein the blocking recovery is repeated if one or more links are still blocked.

5. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 3, further comprising:

storing rollback data for each of multi-connection slices for each of the randomly selected one or more channels;

performing a chain pull operation, wherein the chain pull operation comprises a hitless update achieved by writing a new configuration to a standby bank of the plurality of ingress, egress, and center stage switches and then doing a global active/standby bank swap between an active and the standby bank of the plurality of ingress, egress, and center stage switches; and

implementing a rollback utilizing the rollback data responsive to a failure of the chain pull operation.

6. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 5, wherein the rollback comprises:

removing all of the multi-connection slices reallocated to the new center stage switch in the reallocating each of the multi-connection slices step;

reallocating channels to a prior multi-connection slice; and

reassigning time slots to the channels.

7. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 1, further comprising performing background rebalancing responsive to the multi-stage switch fabric being idle for a time period, wherein background rebalancing is configured as a proactive measure to reduce imbalances in the plurality of center stage switches.

8. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 7, wherein background rebalancing comprises:

setting an imbalance threshold;

finding all links between the plurality of ingress switches, the plurality of center stage switches, and the plurality of egress switches above the set imbalance threshold;

randomly selecting multi-connection slices for each of the found links; and

utilizing a chain pull operation to rearrange each of the randomly selected multi-connection slices to a new center stage switch of the plurality of center stage switches.

9. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 8, wherein the background rebalancing is repeated with one of a new imbalance threshold and the same imbalance threshold.

10. The method for programming a multi-connection slice through a multi-stage switch fabric of claim 8, further comprising:

storing rollback data for each of multi-connection slices; and

implementing a rollback utilizing the rollback data responsive to a failure of the chain pull operation.

11. A multi-stage switch fabric with a load-balancing algorithm for provisioning multi-connection slices through center stages of the switch fabric, comprising:

a plurality of ingress switches interconnected to a plurality of center stage switches interconnected to a plurality of egress switches;

a controller in communication with the plurality of ingress switches, the plurality of center stage switches, and the plurality of egress switches, wherein the controller is configured to;

receive a multi-connection slice request, wherein the multi-connection slice comprises the flow in a single direction across the multi-stage switch fabric from one of the plurality of ingress switches to one of the plurality of egress switches; and

select one of the center stage switch of the plurality of center stage switches responsive to computed imbalances of all links the one of the plurality of ingress switches to each of the plurality of center stage switches and from the one of the plurality of egress switches to each of the plurality of center stage switches.

12. The multi-stage switch fabric with a load-balancing algorithm of claim 11, wherein the controller is further configured to perform blocking recovery responsive to blocking on one or more links, wherein blocking recovery rearranges multi-connection slices on the one or more links so that the multi-connection slice request can be added.

13. The multi-stage switch fabric with a load-balancing algorithm of claim 11, wherein the controller is further configured to perform background rebalancing responsive to the multi-stage switch fabric being idle for a time period, wherein background rebalancing is configured as a proactive measure to reduce imbalances in the plurality of center stage switches.

14. The multi-stage switch fabric with a load-balancing algorithm of claim 12, further comprising a data store configured to store rollback data utilized to roll back the multi-connection slices on the one or more links if the blocking recovery fails.

15. The multi-stage switch fabric with a load-balancing algorithm of claim 13, further comprising a data store configured to store rollback data utilized to roll back the rebalancing if the background rebalancing fails.

16. A three-stage optical switch with a load-balancing algorithm for provisioning connections through center stages of the switch fabric, comprising:

a plurality of line modules each line module comprising a plurality of ingress switches and a plurality of egress switches;

a plurality of switch modules each switch module comprising a plurality of center stage switches;

a backplane connected to the plurality of line modules and the plurality of switch modules, wherein the plurality of ingress switches, the plurality of egress switches, and the plurality of center stage switches are interconnected through the backplane; and

means for selecting a center stage switch of the plurality of center stage switches responsive to one of a new and modified connection from one of the plurality of ingress switches to one of the plurality of egress switches.

17. The three-stage optical switch with a load-balancing algorithm of claim 16, further comprising means for blocking recovery, wherein blocking recovery rearranges connections between the of the plurality of ingress switches, the plurality of center stage switches, and the plurality of egress switches so that one of the new and modified connection can be added.

18. The three-stage optical switch with a load-balancing algorithm of claim 16, further comprising means for background rebalancing of the plurality of center stage switches, wherein background rebalancing is configured as a proactive measure to reduce imbalances in the plurality of center stage switches.

19. The three-stage optical switch with a load-balancing algorithm of claim 17, further comprising means for rollback responsive to a failure in blocking recovery.

20. The three-stage optical switch with a load-balancing algorithm of claim 18, further comprising means for rollback responsive to a failure in background rebalancing.