System and method for late-dropping packets in a network switch

• US 7,406,041 B2
• Filed: 07/31/2002
• Issued: 07/29/2008
• Est. Priority Date: 07/31/2001
• Status: Expired due to Fees

• Current Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Mehta, Anil, Oberman, Stuart F., Mullendore, Rodney N., Schakel, Keith, Malik, Kamran
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): Chou; Albert T
• Application Number:
  US10/209,545
• Publication Number:
  US 20030026206A1
• Time in Patent Office: 2,190 Days
• Field of Search: 370/412, 370/230, 370/244, 370/288
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

A system and method for late-dropping packets in a network switch. A network switch may include multiple input ports, multiple output ports, and a shared random access memory coupled to the input ports and output ports by data transport logic. Packets entering the switch may be subject to input thresholding, and may be assigned to a flow within a group. A portion of a packet subject to input thresholding may be accepted into the switch and assigned to a group and flow even if, at the time of arrival of the portion, there are not enough resources available to receive the remainder of the packet. This partial receipt of the packet is allowed because of the possibility of additional resources becoming available between the time of receipt of and resource allocation for the portion of the packet and receipt of subsequent portions of the packet.

Claims

1. A method comprising:

receiving a first portion of a packet at a network switch, wherein the network switch comprises a random access memory, wherein the random access memory comprises a plurality of memory portions configured for use in storing packets in the network switch;

determining that sufficient memo portions are available to store at least the first portion of the packet;

storing the received first portion of the packet in a first one or more of the plurality of memory portions, even if insufficient memory portions are available to store the entire packet;

receiving a second portion of the packet in the network switch;

determining whether sufficient memory portions are available to store the second portion of the packet; and

storing or discarding the second portion of the packet based on the determination of available memory.

2. The method as recited in claim 1, further comprising:

releasing a second one or more of the plurality of memory portions subsequent to said receiving the first portion of the packet, wherein said releasing makes the second one or more memory portions available on the network switch;

receiving the second portion of the packet in the network switch after said releasing; and

storing the received second portion of the packet in a third one or more of the plurality of memory portions, wherein the third one or more of the plurality of memory portions includes at least a portion of the released second one or more of the plurality of memory portions;

wherein, prior to said releasing, the memory portions available are insufficient for storing the second portion of the packet.

3. The method as recited in claim 1, wherein the packet is received by the network switch by a port configured to receive Gigabit Ethernet traffic not using control frame-based flow control.

4. The method as recited in claim 1, further comprising:

receiving the second portion of the packet in the network switch after said receiving the first portion of the packet, wherein, when the second portion of the packet is received, insufficient of the memory portions are available for storing the second portion of the packet; and

marking the packet to indicate the packet is to be dropped by the network switch in response to the memory portions available being insufficient for storing the second portion of the packet.

5. The method as recited in claim 4, further comprising dropping the packet after said marking the packet to be dropped.

6. The method as recited in claim 5, wherein said dropping the packet is performed by an output port of the network switch.

7. The method as recited in claim 4, further comprising providing a packet descriptor for the packet in the network switch, wherein said marking the packet to indicate the packet is to be dropped comprises setting an indicator in the packet descriptor to indicate that the packet is to be dropped.

8. The method as recited in claim 1, wherein the memory portions are clusters, wherein a cluster comprises one or more cells, wherein a cell is a minimum number of bytes that are read from the random access memory in one read operation or written to the random access memory in one write operation.

9. The method as recited in claim 1, further comprising storing the first portion in an input FIFO memory prior to said storing the first portion of the packet in the random access memory.

10. A method comprising:

receiving a first portion of a packet in a network switch, wherein the network switch comprises a random access memory, wherein the random access memory comprises a plurality of memory portions configured for use in storing packets in the network switch;

determining that sufficient memory portions are available to store at least the first portion of the packet;

storing the received first portion of the packet in a first one or more memory portions of the plurality of memory portions even if insufficient memory portions are available to store the entire packet;

a) receiving a second portion of the packet in the network switch;

b) determining if the plurality of memory portions available are sufficient for storing the received second portion of the packet;

c) if the plurality of memory portions available are sufficient, storing the second portion of the packet in a second one or more memory portions of the plurality of memory portions; and

d) if the plurality of memory portions available are not sufficient, marking the packet to indicate the packet is to be dropped by the network switch.

11. The method as recited in claim 10, further comprising, if c) is true, repeating a) through d) for one or more portions of the packet received after the second portion of the packet.

12. The method as recited in claim 10, wherein the packet is received by the network switch by a port configured to receive Gigabit Ethernet traffic not using control frame-based flow control.

13. The method as recited in claim 10, further comprising dropping the packet after said marking the packet to be dropped.

14. The method as recited in claim 13, wherein said dropping the packet is performed by an output port of the network switch.

15. The method as recited in claim 10, further comprising providing a packet descriptor for the packet in the network switch.

16. The method as recited in claim 15, wherein said marking the packet to indicate the packet is to be dropped comprises setting an indicator in the packet descriptor to indicate that the packet is to be dropped.

17. The method as recited in claim 10, wherein, during said receiving the first portion of the packet in the network switch, the plurality of memory portions available are insufficient for storing the second portion of the packet not yet received by the network switch.

18. The method as recited in claim 17, further comprising, prior to said receiving the second portion of the packet, releasing at least enough of the plurality of memory portions to store the second portion of the packet.

19. The method as recited in claim 10, wherein the memory portions are clusters, wherein a cluster comprises one or more cells, wherein a cell is a minimum number of bytes that are read from the random access memory in one read operation or written to the random access memory in one write operation.

20. A network switch comprising:

one or more ports configured to receive packets for the network switch;

a random access memory comprising a plurality of memory portions configured for use in storing the packets in the network switch; and

packet admission logic coupled between the one or more ports and the random access memory, wherein the packet admission logic is configured to;

receive a first portion of a packet at a first port of the one or more ports;

determine that sufficient memory portions are available to store at least the first portion of the packet; and

store the received first portion of the packet in a first one or more of the plurality of memory portions, even if insufficient memory portions are available to store the entire packet;

receive a second portion of the packet in the network switch;

determine whether sufficient memory portions are available to store the second portion of the packet; and

store or discard the second portion of the packet based on the determination of available memory.

21. The network switch as recited in claim 20, wherein the network switch is configured to release a second one or more of the plurality of memory portions after said receiving the first portion of the packet, wherein said releasing makes the second one or more memory portions available to the packet admission logic;

wherein the packet admission logic is further configured to;

receive the second portion of the packet at the first port after said releasing; and

store the received second portion of the packet in a third one or more of the plurality of memory portions, wherein the third one or more of the plurality of memory portions includes at least a portion of the released second one or more of the plurality of memory portions;

wherein, prior to said releasing, the memory portions available are insufficient for storing the second portion of the packet not yet received at the first port.

22. The network switch as recited in claim 20, wherein the first port is a port configured to receive Gigabit Ethernet traffic not using control frame-based flow control.

23. The network switch as recited in claim 20, wherein the packet admission logic is further configured to:

receive the second portion of the packet at the first port after said receiving the first portion of the packet;

determine the memory portions available are insufficient for storing the received second portion of the packet; and

mark the packet to indicate the packet is to be dropped by the network switch in response to said determining the memory portions available are insufficient for storing the received second portion of the packet.

24. The network switch as recited in claim 23, wherein the network switch is configured to drop the packet after said marking the packet to be dropped.

25. The network switch as recited in claim 23, wherein the network switch further comprises an output port configured to convey packets received on the first port out of the network switch, wherein the output port is further configured to drop the packet after said marking the packet to be dropped.

26. The network switch as recited in claim 23, wherein the packet admission logic is further configured to provide a packet descriptor for the packet after said receiving the first portion of the packet, wherein said marking the packet to indicate the packet is to be dropped comprises setting an indicator in the packet descriptor to indicate that the packet is to be dropped.

27. The network switch as recited in claim 20, wherein the plurality of memory portions are clusters, wherein a cluster comprises one or more cells, wherein a cell is a minimum number of bytes that are read from the random access memory in one read operation or written to the random access memory in one write operation.

28. The network switch as recited in claim 20, further comprising an input FIFO memory, wherein the packet admission logic is further configured to store the first portion in the input FIFO memory prior to said storing the first portion of the packet in the random access memory.

29. A network switch comprising:

one or more ports configured to receive input packets for the network switch;

a random access memory comprising a plurality of memory portions configured for use in storing packets in the network switch; and

packet admission logic coupled between the one or more ports and the random access memory, wherein the packet admission logic is configured to;

receive a first portion of a packet at a first port of the one or more ports;

determine that sufficient memo portions are available to store at least the first portion of the packet;

store the received first portion of the packet in a first one or more memory portions of the plurality of memory portions, even if insufficient memory portions are available to store the entire packet;

a) receive a second portion of the packet at the first port;

b) determine if the plurality of memory portions available are sufficient for storing the received second portion of the packet;

c) if the plurality of memory portions available are sufficient, store the received second portion of the packet in a second one or more memory portions of the plurality of memory portions; and

d) if the plurality of memory portions available are not sufficient, mark the packet to indicate the packet is to be dropped by the network switch.

30. The network switch as recited in claim 29, wherein the packet admission logic is further configured to, if c) is true, repeat a) through d) for one or more portions of the packet received after the second portion of the packet.

31. The network switch as recited in claim 29, wherein the first port is configured to receive Gigabit Ethernet traffic not using control frame-based flow control.

32. The network switch as recited in claim 29, wherein the network switch is configured to drop the packet after said marking the packet to be dropped.

33. The network switch as recited in claim 32, wherein the network switch further comprises an output port configured to convey packets received at the first port out of the network switch, wherein the output port is further configured to drop the packet after said marking the packet to be dropped.

34. The network switch as recited in claim 29, wherein the packet admission logic is further configured to provide a packet descriptor for the packet after said receiving the first portion of the packet, wherein said marking the packet to indicate the packet is to be dropped comprises setting an indicator in the packet descriptor to indicate that the packet is to be dropped.

35. The network switch as recited in claim 29,

wherein, during said receiving the first portion of the packet, the plurality of memory portions available are insufficient for storing the second portion of the packet not yet received at the first port;

wherein the network switch is configured to release a third one or more of the plurality of memory portions after said storing the first portion of the packet and prior to said receiving the second portion of the packet, wherein said releasing makes the third one or more memory portions available to the packet admission logic; and

wherein, after said releasing, the plurality of memory portions available are sufficient for storing the second portion of the packet not yet received at the first port.

36. The network switch as recited in claim 29, wherein the plurality of memory portions are clusters, wherein a cluster comprises one or more cells, wherein a cell is a minimum number of bytes that are read from the random access memory in one read operation or written to the random access memory in one write operation.