Credit loop deadlock detection and recovery in arbitrary topology networks

1. A method of communication, comprising the steps of:

in a packet network of switches, the switches having ingress ports, egress ports and switch buffers, at least a portion of the switches being interlinked in a credit loop comprising loop-participating switches;

making a determination that at least a portion of the loop-participating switches are deadlock-suspected switches based, respectively, on an existence in a deadlock-suspected egress port thereof of a non-zero queue length for a predetermined time interval and an absence of throughput for the predetermined time interval;

responsively to the determination performing first traversals of the credit loop by periodically transmitting respective credit loop control messages (CLCMs) from the deadlock-suspected switches via the deadlock-suspected egress port to respective next-hop loop-participating switches of the credit loop, the CLCMs each having a switch port-unique identifier (SPUID);

in deadlock-suspected next-hop loop-participating switches forwarding the CLCMs to subsequent next-hop loop-participating switches via the deadlock-suspected egress port thereof;

establishing that a deadlock exists in the credit loop by determining that all the switch buffers in links to the loop-participating switches are full, and that no packets are propagating through the links;

thereafter selecting a master switch from the loop-participating switches, wherein the SPUID of a received CLCM equals the SPUID of a previously transmitted CLCM; and

in a release phase of operation resolving the deadlock in the credit loop with the master switch by:

transmitting new CLCMs to perform second traversals of the credit loop along a path that extends through a selected deadlocked egress port of each of the loop-participating switches, the second traversals comprising:

(a) recording in the new CLCMs the SPUID and the selected deadlocked egress port of respective loop-participating switches in the path; and:

(b) in respective loop-participating switches identifying the ingress port using the recording in the new CLCMs; and

(c) performing by the respective loop-participating switches a reconfiguration thereof for a predefined time interval to affect packet traffic that flows via the identified ingress port through the selected deadlocked egress port thereof.

2. The method according to claim 1 , further comprising:

determining that that the SPUID of a currently received CLCM exceeds the SPUID of the previously transmitted CLCM; and

thereafter continuing to periodically transmit CLCMs.

3. The method according to claim 1 , further comprising:

determining that that the SPUID of a currently received CLCM exceeds the SPUID of the previously transmitted CLCM; and

thereafter transmitting another new CLCM having the SPUID of the currently received CLCM.

4. The method according to claim 1 , wherein in the reconfiguration the selected deadlocked egress port accepts therethrough only packets that pass through the identified ingress port.

5. The method according to claim 1 , wherein resolving the deadlock comprises the steps of:

identifying flows of packets that traverse pairs of ingress ports and deadlock-suspected egress ports in the master switch; and

rerouting the identified flows via respective alternate paths to destinations thereof, the alternate paths having minimum cost metrics.

6. The method according to claim 5 , wherein rerouting the identified flows comprises changing routing rules in the loop-participating switches.

7. The method according to claim 1 , wherein the reconfiguration comprises the step of releasing a buffer space on the master switch by forcing transmission of packets via the selected deadlocked egress port of the master switch.

8. The method according to claim 7 , wherein forcing transmission is performed by overriding a credit flow control.

9. The method according to claim 1 , wherein the reconfiguration comprises increasing an available buffer size in the identified ingress port.

10. The method according to claim 1 , wherein the new CLCMs contain switch data that identify each of the loop-participating switches that is traversed.

11. A system, comprising:

a packet network; and

a plurality of switches in the network, the switches having ingress ports, egress ports and switch buffers, at least a portion of the switches being interlinked in a credit loop in the network, the credit loop comprising loop-participating switches that are configured to cooperatively perform the steps of:

making a determination that at least a portion of the loop-participating switches are deadlock-suspected switches based, respectively, on an existence in a deadlock-suspected egress port thereof of a non-zero queue length for a predetermined time interval and an absence of throughput for the predetermined time interval;

responsively to the determination performing first traversals of the credit loop by periodically transmitting respective credit loop control messages (CLCMs) from the deadlock-suspected switches via the deadlock-suspected egress port to respective next-hop loop-participating switches of the credit loop, the CLCMs each having a switch port-unique identifier (SPUID);

in deadlock-suspected next-hop loop-participating switches forwarding the CLCMs to subsequent next-hop loop-participating switches via the deadlock-suspected egress port thereof;

establishing that a deadlock exists in the credit loop by determining that all the switch buffers in links to the loop-participating switches are full, and that no packets are propagating through the links;

thereafter selecting a master switch from the loop-participating switches, wherein the SPUID of a received CLCM equals the SPUID of a previously transmitted CLCM; and

in a release phase of operation resolving the deadlock in the credit loop with the master switch, by:

transmitting new CLCMs to perform second traversals of the credit loop along a path that extends through a selected deadlocked egress port of each of the loop-participating switches, the second traversals comprising:

(a) recording in the new CLCMs the SPUID and the selected deadlocked egress port of respective loop-participating switches in the path; and

(b) in respective loop-participating switches identifying the ingress port using the recording in the new CLCMs; and

(c) performing by the respective loop-participating switches a reconfiguration thereof for a predefined time interval to affect packet traffic that flows via the identified ingress port through the selected deadlocked egress port thereof.

12. The system according to claim 11 , wherein the switches are further configured for performing the steps of:

determining that that the SPUID of a currently received CLCM exceeds the SPUID of the previously transmitted CLCM; and

thereafter continuing to periodically transmit CLCMs.

13. The system according to claim 11 , wherein the switches are further configured for performing the steps of:

determining that that the SPUID of a currently received CLCM exceeds the SPUID of the previously transmitted CLCM; and

thereafter transmitting another new CLCM having the SPUID of the currently received CLCM.

14. The system according to claim 11 , wherein in the reconfiguration the selected deadlocked egress port accepts therethrough only packets that pass through the identified ingress port.

15. The system according to claim 11 , wherein the switches are further configured for resolving the deadlock by performing the steps of:

identifying flows of packets that traverse pairs of ingress ports and the deadlock-suspected egress port in the master switch; and

rerouting the identified flows via respective alternate paths to destinations thereof, the alternate paths having minimum cost metrics.

16. The system according to claim 15 , wherein the switches are further configured for resolving a deadlock by releasing a buffer space on the master switch by forcing transmission of packets via the deadlock-suspected egress port of the master switch.

17. The system according to claim 16 , wherein forcing transmission is performed by overriding a credit flow control.

18. The system according to claim 11 , wherein the switches are further configured for increasing an available buffer size in the identified ingress port.

19. A method of communication, comprising the steps of:

in a network of switches that are interconnected for packet traffic flows therethrough, the switches being interlinked in a credit loop comprising loop-participating switches:

making a determination that at least a portion of the loop-participating switches are deadlock-suspected switches based, respectively, on an existence in a deadlock-suspected egress port thereof of a non-zero queue length for a predetermined time interval and an absence of throughput for the predetermined time interval;

responsively to the determination periodically transmitting respective credit loop control messages (CLCMs) from the deadlock-suspected switches via the deadlock-suspected egress port to respective next-hop loop-participating switches of the credit loop, the CLCMs each having a switch port-unique identifier (SPUID);

in deadlock-suspected next-hop loop-participating switches forwarding the CLCMs to subsequent next-hop loop-participating switches via the deadlock-suspected egress port thereof;

selecting a master switch from the loop-participating switches, wherein the SPUID of a received CLCM equals the SPUID of a previously transmitted CLCM;

determining that ports of the loop-participating switches are stalled; and

thereafter resolving a deadlock in the credit loop with the master switch, wherein resolving a deadlock comprises the steps of:

after selecting a master switch repeating the step of periodically transmitting respective CLCMs through the credit loop, using new CLCMs as the CLCMs;

determining in one of the loop-participating switches that the SPUID of a current new CLCM matches the SPUID of a previously received new CLCM and that the deadlock-suspected egress port thereof is deadlocked;

in a release phase of operation retransmitting the current new CLCM via the deadlock-suspected egress port through the loop-participating switches of the credit loop; and

in the loop-participating switches performing the steps of:

respectively identifying an ingress port and a previously traversed egress port of the current new CLCM; and

permitting only packets from the identified ingress port to be transmitted through the previously traversed egress port,

wherein the CLCMs further comprise:

phase data that identify the release phase of operation; and

a SPUID array identifying the SPUID of each of the loop-participating switches that is traversed in the release phase of operation;

an egress port array identifying the egress port of each of the loop-participating switches that is traversed in the release phase of operation; and

an index into the SPUID array and the egress port array, wherein identifying an ingress port and a previously traversed egress port are performed by updating the SPUID array, the egress port array and the index when the loop-participating switches are traversed in the release phase of operation.