Deadlock recovery for distributed devices

Patent metadata

Field	Value
Publication number	US-9042222-B2
Application number	US-201213720923-A
Country	US
Kind code	B2
Filing date	Dec 19, 2012
Priority date	Nov 28, 2012
Publication date	May 26, 2015
Grant date	May 26, 2015

Abstract

A system for deadlock recovery of distributed devices may include a processor and memory. The processor may transmit packets to a device, receive a pause message indicating that the packet transmission should be paused, and initiate a timer and pause the packet transmission in response to receiving the pause message. The processor may enter a deadlock recovery state if the timer reaches a timeout before a resume message is received that indicates that the packet transmission can resume. The processor may, while in the deadlock recovery state, drop packets that have a packet age that is greater than a threshold, and may exit the deadlock recovery state upon dropping a packet that has a packet age less than the threshold, or upon receiving the resume message. The processor may re-initiate the timer if the resume message has not been received, otherwise the processor may resume the packet transmission.

First claim

What is claimed is:

1. A method for deadlock recovery for distributed devices, the method comprising:
receiving a pause message from a network device that indicates that transmission of packets to the network device should be paused;
initiating a timer and pausing the transmission of the packets to the network device without dropping the packets, in response to the receiving the pause message;
entering a deadlock recovery state if the timer reaches a timeout threshold before receiving a resume message from the network device that indicates that the transmission of the packets to the network device can resume, wherein none of the packets are dropped prior to entering the deadlock recovery state;
dropping the packets that have a packet age that is greater than or equal to an age threshold, when in the deadlock recovery state; and
exiting the deadlock recovery state upon dropping one of the packets that has the packet age that is less than the age threshold, or upon receiving the resume message that indicates that the transmission of packets can resume.

2. The method of claim 1 , further comprising resuming the transmission of the packets to the network device, in response to receiving the resume message.

3. The method of claim 1 , further comprising exiting the deadlock recovery state when a recovery timer that is initiated upon entering the deadlock recovery state reaches an exit deadlock recovery threshold.

4. The method of claim 1 , wherein the packets comprise lossless packets that are queued in one of a plurality of queues, the one of the plurality of queues being associated with a priority value.

5. The method of claim 4 , wherein the pause message comprises a priority flow control message that indicates that the transmission of packets queued in any of the plurality of queues that is associated with the priority value should be paused.

6. The method of claim 4 , wherein the entering the deadlock recovery state if the timer reaches the timeout threshold before the receiving the resume message further comprises ignoring a flow control state of the one of the plurality of queues when the timer reaches the timeout threshold before the receiving the resume message.

7. The method of claim 1 , further comprising:
reinitiating the timer in response to exiting the deadlock recovery state when the resume message has not been received; and
re-entering the deadlock recovery state when the timer reaches the threshold value and the resume message has not been received.

8. The method of claim 1 , wherein the packets are associated with one of a plurality of virtual local area networks (VLANs) and the plurality of VLANs are associated with a plurality of spanning trees.

9. The method of claim 1 , wherein the entering the deadlock recovery state is initiated by software.

10. The method of claim 1 , further comprising:
storing a number of times that the deadlock recovery state is entered and a number of the packets that are dropped.

11. A non-transitory machine-readable medium embodying instructions that, when executed by a machine, allow the machine to perform a method for deadlock recovery for distributed devices, the method comprising:
receiving lossless packets from a first device, queuing the lossless packets in one of a plurality of queues for transmission to a second device, and transmitting the lossless packets to the second device in an order in which the lossless packets are queued, wherein each lossless packet has a packet age that indicates when each lossless packet was received from the first device;
receiving a pause message from the second device that indicates that transmission of lossless packets to the second device should be paused;
pausing the transmission of the lossless packets to the second device without dropping any of the lossless packets and initiating a timer associated with the one of the plurality of queues in response to receiving the pause message;
resuming the transmission of the lossless packets to the second device if a resume message is received from the second device that indicates that the transmission of the lossless packets to the second device can resume, otherwise if the timer reaches a timeout threshold before the resume message is received from the second device without having dropped any of the lossless packets prior to the timer reaching the timeout threshold:
individually processing and dropping the lossless packets in the order which the lossless packets are queued until a lossless packet having the packet age that is less than an age threshold is processed and dropped, or until the resume message is received from the second device; and
if the lossless packet having the packet age that is less than the age threshold is processed and dropped before the resume message is received, repeating the initiating the timer and the processing and the dropping the lossless packets, otherwise receiving the resume message and resuming the transmission of the lossless packets to the second device.

12. The non-transitory machine-readable medium of claim 11 , wherein the transmitting the lossless packets to the second device in the order in which the lossless packets are queued is performed at least in part by a scheduler that schedules packets for transmission to the second device that are queued in each of the plurality of queues.

13. The non-transitory machine-readable medium of claim 12 , wherein each of the plurality of queues is associated with a flow control state that comprises either an on state or an off state, and the scheduler only schedules the packets for transmission that are queued in any of the plurality of queues that are associated with the on state.

14. The non-transitory machine-readable medium of claim 13 , wherein the pausing the transmission of the packets comprises setting the flow control state of the one of the plurality of queues to the off state.

15. The non-transitory machine-readable medium of claim 14 , wherein the scheduler ignores the flow control state of the one of the plurality of queues when the timer reaches the timeout threshold.

16. The non-transitory machine-readable medium of claim 11 , wherein the lossless packets are associated with one of a plurality of virtual local area networks (VLANs) and the plurality of VLANs are associated with a plurality of spanning trees.

17. The non-transitory machine-readable medium of claim 11 , wherein the processing and the dropping the lossless packets is initiated by software.

18. The non-transitory machine-readable medium of claim 11 , the method further comprising:
storing a number of packets that are dropped and a number of times that the timer reaches the threshold.

19. A system for deadlock recovery of distributed devices, the system comprising:
one or more processors; and
a memory including instructions that, when executed by the one or more processors, cause the one or more processors to:
receive lossless packets from a first device, queue the lossless packets in a queue for transmission to a second device, and transmit the lossless packets to the second device in an order which the lossless packets are queued in the queue;
receive a pause message from the second device that indicates that transmission of the lossless packets that are queued in the queue should be paused;
initiate a timer associated with the queue and pause the transmission of the lossless packets that are queued in the queue, in response to the receiving the pause message;
enter a deadlock recovery state for the queue if the timer reaches a timeout th

Assignees

• Broadcom Corp

Inventors

• Kwan Bruce
• Agarwal Puneet

Classifications

• H04L47/12 Primary

  Avoiding congestion; Recovering from congestion · CPC title

• H04L47/32 Primary

  by discarding or delaying data units, e.g. packets or frames · CPC title

• H04L47/283

  in response to processing delays, e.g. caused by jitter or round trip time [RTT] · CPC title

• H04L47/266

  Stopping or restarting the source, e.g. X-on or X-off · CPC title

• H04L47/6215

  Individual queue per QOS, rate or priority · CPC title