# US 2005/0088970 A1 · Deferred queuing in a buffered switch

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2005/0088970 A1
- Document ID: US20050088970A1
- Status: Published application
- Kind: A1
- Application number: 10/873,430
- Filed: 2004-06-21
- Published: 2005-04-28
- Earliest claimed: 2001-12-19
- Assignees: McData Services Corporation
- Inventors: Steven Schmidt; Anthony Tornetta; Harry Paul; Henry Gonzalez
- Web page: https://patentgrep.com/patent/US20050088970A1

## CPC

- H04L 49/3009: {Header conversion, routing tables or routing tags}
- H04L 49/30: {Peripheral units, e.g. input or output ports}
- H04L 2012/5683: {for avoiding head of line blocking}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method and apparatus is disclosed for temporarily deferring transmission of frames to a destination in a data switch. When a request for transmission of a frame to the destination port is received, the congestion status of that destination is determined. If the destination is congested, the frame is stored in a deferred queue. When the status of a destination changes from congested to non-congested, the deferred queue is examined to see if any deferred frames can now be forwarded to their destination. While examining the deferred queue, incoming frames are placed on a backup queue. When the deferred queue is fully analyzed, the backup queue is emptied by either sending those frames to their destination or storing the frames in the deferred queue. While examining the deferred queue, the congested states of the destinations are not allowed to change from congested to non-congested.

## Claims

### Claim 1

A method for queuing data packets in a switch comprising:
a) storing a beginning of a first data packet in a buffer;
b) determining a switch destination for the first packet;
c) determining a congestion status for the switch destination;
d) forwarding the first packet to the switch destination if the congestion status is non-congested;
e) storing the first packet in a deferred queue if the congestion status is congested;
f) repeating the above steps, such that multiple packets that are routed to a plurality of different congested switch destinations are stored in the same deferred queue.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
g) entering a deferred state wherein the packets in the deferred queue are examined so as to send packets to their switch destination if their switch destination has a non-congested status.

### Claim 3 (depends on 2)

The method of claim 2, further comprising
h) entering the deferred state when a first switch destination changes its congestion status from a congested state to a non-congested state.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
i) when in the deferred state, storing packets received at the switch in a backup queue.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
j) entering a backup state wherein the packets in the backup queue are examined and sent to their destination or to the deferred queue.

### Claim 6 (depends on 5)

The method of claim 5, wherein the step of entering the backup state further comprises:
i) determining a switch destination for a first packet in the backup queue;
ii) determining the congestion status for the switch destination of the first backup queue packet;
iii) forwarding the first backup queue packet to its switch destination if the congestion status of its switch destination is non-congested; and
iv) storing the first backup queue data packet in the deferred queue if the congestion status of its switch destination is congested

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
k) entering a third state after receiving a signal that no data should be sent over a switch fabric of the switch, the third state causing all received data to enter the backup queue.

### Claim 8 (depends on 7)

The method of claim 7, wherein the signal indicates that one of a plurality of ingress memory subsystem to the switch fabric is no longer accepting data, wherein said one ingress memory subsystem accepts packets stored in the buffer for submission over a switch fabric.

### Claim 9 (depends on 3)

The method of claim 3, further comprising the step of:
i) using a congestion status mask to determine the congestion status of the switch destination;

### Claim 10 (depends on 9)

The method of claim 9, further comprising the step of:
j) during the deferred mode, preventing changes in the congestion status mask for the switch destination from a congested status to a non-congested status.

### Claim 11 (depends on 10)

The method of claim 10, further comprising the step of:
k) during the deferred mode, allowing changes in the congestion status mask for the switch destination from a non-congested status to a congested status.

### Claim 12 (depends on 11)

The method of claim 11, wherein, during the deferred mode, changes in the congestion status for the switch destination from a congested status to a non-congested status are recorded in a history register, and further wherein the history register is used to update the congestion status mask after the entire deferred queue is examined.

### Claim 13 (depends on 3)

The method of claim 3, wherein, during the deferred state, packets in the deferred queue are stored back in the deferred queue if their switch destination has a congested status, further wherein such re-storage in the deferred queue maintains a chronological order for packets in the queue.

### Claim 14 (depends on 1)

The method of claim 1, wherein the switch destination is chosen from the set comprising an egress port on the switch and a processor on the switch.

### Claim 15 (depends on 1)

The method of claim 1, wherein the data packet is of a format selected from the set comprising a Fibre Channel frame, an Ethernet frame, and an ATM cell.

### Claim 16

A method for handling data packets within a switch comprising:
a) maintaining a lookup table having multiple entries, each entry containing a congestion status for a different destination in the switch;
b) sending a congestion update to the lookup table, the congestion update containing a destination identifier and an updated congestion status;
c) updating the entry in the lookup table corresponding to the destination identifier using the updated congestion status;
d) using the lookup table to determine the congestion status of a first destination for a data packet entering the switch;
e) storing the data packet in a deferred queue if the congestion status indicates the first destination is not available; and
f) transmitting the data packet to the first destination if the congestion status indicates the first destination is available.

### Claim 17 (depends on 12)

The method of claim 12, further comprising:
g) at a later time, reexamining the congestion status of the first destination, wherein the data packet is transmitted to the first destination if the congestion status indicates the first destination is available, and further wherein the data packet is stored back into the deferred queue if the congestion status indicates the first destination is not available.

### Claim 18

A data switch comprising:
a) an input port that can receive a data packet having a packet destination;
b) a switch destination;
c) a switch fabric for making a switched connection between the input port and the switch destination;
d) a routing module having a routing table routing between the packet destination and the switch destination;
e) an XOFF mask containing a congestion status for the switch destination;
f) a signaling mechanism in communication with the XOFF mask indicating changes in the congestion status;
g) a deferred queue;
h) a queue control module containing logic that places the data packet in the deferred queue if the congestion status is XOFF, and that submits the data packet to the switch fabric if the congestion status is XON.

### Claim 19

A data switch comprising:
a) an input port means for receiving a data packet;
b) a buffer means for temporarily storing and retrieving at least the beginning of the data packet;
c) a destination determination means for determining a switch destination for the data packet;
d) a congestion status determination means for determining a congestion status of the switch destination;
e) a deferred queue means for storing header information relating to the data packet; and
f) a queue controller means for directing the data packet to the deferred queue means if the congestion status is congested and for directing the data packet to the switch destination if the congestion status is non-congested.

### Claim 20 (depends on 19)

The data switch of claim 19, further comprising:
g) a deferred queue state means for analyzing the packet on the deferred queue means and for forwarding the packet to the switch destination if the congestion status has changed to non-congested;
h) a backup queue means for storing additional data packets when the deferred queue state means is analyzing the packet.

### Claim 21

A data switch that switches data packets through the switch from ingress ports to destination ports comprising:
a) a buffer memory at each ingress port for storing a portion of the data packets at known locations;
b) a routing module that determines switch destination addresses and other packet header information for the data packets;
c) a deferred queue and a backup queue for storing packet header information, including their locations in the buffer;
d) a next header logic that selects a next data packet to be sent through the switch, the next data packet being chosen from incoming data packets analyzed by the routing module, the deferred queue, and the backup queue.

### Claim 22 (depends on 21)

The data switch of claim 21, further comprising:
e) a state machine having the following states
i) an initial state in which the header information received from the routing module is analyzed for transmission over the switch;
ii) a deferred state in which the header information in the deferred queue is analyzed for transmission over the switch; and
iii) a backup state in which the header information in the backup queue is analyzed for transmission over the switch.

### Claim 23 (depends on 22)

The data switch of claim 22, wherein data packet header information received from the routing module during the deferred state is stored on the backup queue.

### Claim 24 (depends on 22)

The data switch of claim 22, further comprising
f) a congestion status mask storing a congestion status for each switch destination address, wherein a first data packet is stored on the deferred queue when the switch destination address returned by the routing module for the first data packet has a congestion status of XOFF.

### Claim 25 (depends on 24)

The data switch of claim 24, wherein the congestion status mask receives status updates changing the congestion status for the switch destination addresses.

### Claim 26 (depends on 25)

The data switch of claim 25, wherein the deferred state is entered whenever the congestion status mask receives an XON update changing the congestion status for at least one switch destination address from XOFF to XON.

### Claim 27 (depends on 26)

The data switch of claim 26, wherein data packet header information received from the routing module during the deferred state is stored on the backup queue.

### Claim 28 (depends on 27)

The data switch of claim 27, wherein the backup state is entered after all of the header information in the deferred queue is analyzed in the deferred state.

### Claim 29 (depends on 28)

The data switch of claim 28, wherein the backup state is only entered if the backup queue is not empty.

### Claim 30 (depends on 26)

The data switch of claim 26, wherein the deferred state is exited after all of the header information in the deferred queue is analyzed in the deferred state.

### Claim 31 (depends on 30)

The data switch of claim 30, wherein the congestion status mask does not update the congestion status of any switch destination address from XOFF to XON during the deferred state.

### Claim 32 (depends on 31)

The data switch of claim 31, wherein all status updates from XOFF to XON received during the deferred state are stored in a register.

### Claim 33 (depends on 32)

The data switch of claim 32, wherein the register updates the congestion status mask relating to congestion status changes from XOFF to XON after the deferred state is exited.

### Claim 34 (depends on 33)

The data switch of claim 33, wherein the deferred state is re-entered immediately after the deferred state is exited if the XON history register updates the congestion status of any switch destination addresses.
