FIFO buffer with multiple stream packet segmentation

• US 8,804,751 B1
• Filed: 10/02/2006
• Issued: 08/12/2014
• Est. Priority Date: 10/04/2005
• Status: Active Grant

• Current Assignee: Dell Marketing Corporation (Dell Technologies Inc.)
• Original Assignee: Force10 Networks, Inc. (Dell Technologies Inc.)
• Inventors: Poole, Glenn, Gui, Ann, Chung, Heeloo, Lin, Joanna, Danofsky, Brad, Haddad, David
• Primary Examiner(s): Hamza, Faruk
• Assistant Examiner(s): GUADALUPE CRUZ, AIXA AMYR
• Application Number:
  US11/537,958
• Time in Patent Office: 2,871 Days
• Field of Search: None
• US Class Current: 370/412
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 47/365 Dynamic adaptation of the packet size
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9021 Plurality of buffers per packet
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing

Abstract

An epoch-based network processor internally segments packets for processing and aggregation in epoch payloads. FIFO buffers interact with a memory management unit to efficiently manage the segmentation and aggregation process.

Claims

1. A network processing device packet buffering subsystem comprising:

a first-in first out (FIFO) memory comprising a plurality of FIFO buffers, each associated with a source index, to receive multiplexed packet data marked with source indices and sort the multiplexed packet data to the FIFO buffers according to source index;

a plurality of counters, associated respectively with the plurality of FIFO buffers, to track a size of each packet as it is received into each FIFO buffer from the multiplexed packet data; and

segmentation logic to output from the FIFO memory a segment of a packet being received into a given one of the FIFO buffers when the packet data accumulated in that given FIFO buffer for the received packet exceeds a selected data length, the selected data length being less than an amount of data than can be transmitted through a switch fabric associated with the buffering subsystem during a single epoch of time;

wherein the segmentation logic allows the packet data accumulated for a given segment to exceed the selected data length by up to a selected overflow amount when lengthening the given segment will allow the given segment to be a last segment for its corresponding packet;

wherein the segmentation logic delays outputting the given segment until it determines whether the given segment can be made the last segment by extending the given segment up to the selected overflow amount.

2. The packet buffering subsystem of claim 1, wherein the segmentation logic repeats the segmentation of the received packet each time the packet data accumulated in the given FIFO buffer for the received packet exceeds the selected data length.

3. The packet buffering subsystem of claim 1, further comprising header logic to place a header on each segment output from the FIFO memory.

4. The packet buffering subsystem of claim 3, wherein the header logic sets flags in the header of each segment, the flags designating each segment as a first and/or a last segment or a middle segment.

5. The packet buffering subsystem of claim 4, wherein the header logic sets the flags to mark a single segment as both a first and a last segment when the single segment can hold the entire packet.

6. The packet buffering subsystem of claim 3, wherein the header logic sets a length field in the header of each segment.

7. The packet buffering subsystem of claim 6, wherein a length field is initially set by the header logic to indicate a length of a corresponding segment.

8. The packet buffering subsystem of claim 7, wherein the length field on a first segment of each multi-segment packet is eventually overwritten to indicate a total length of all segments of a corresponding multi-segment packet.

9. The packet buffering subsystem of claim 3, wherein the header logic places the header on a current segment that is not a first segment of a packet by saving the header from a preceding segment into a head of the FIFO buffer containing the current segment as the preceding segment is output from the FIFO memory, and modifying the saved header as necessary for the current segment.

10. The packet buffering subsystem of claim 1, further comprising a packet processing unit to examine packet segments output from the FIFO memory and make drop decisions for each packet based on the examination of the packet segments.

11. The packet buffering subsystem of claim 10, the packet processing unit comprising a state table to save a state for each packet until that packet is fully segmented and examined by the packet processing unit.

12. The packet buffering subsystem of claim 10, wherein the packet processing unit can at least drop the received packet for having an improper length and to enforce a traffic management profile.

13. The packet buffering subsystem of claim 10, wherein the packet processing unit has a capability to drop the received packet prior to receiving the last segment of the received packet, the packet processing unit consequently signaling the FIFO memory to drop the remainder of the received packet without segmenting it and sending it to the packet processing unit.

14. The packet buffering subsystem of claim 10, wherein the packet processing unit has a capability to drop the received packet after forwarding at least a first segment of the received packet through to a downstream memory management unit, the packet processing unit consequently signaling the memory management unit to drop segments of the received packet already forwarded to the memory management unit.

15. The packet buffering subsystem of claim 1, further comprising:

a buffer memory to store segments output from the FIFO memory; and

a memory manager to control storing of the segments to and reading of the segments from the buffer memory, the memory manager comprising;

a destination queue state table to maintain a state for each of a plurality of virtual queues associated with different packet destinations, the virtual queues sharing the buffer memory, the state for each virtual queue comprising a linked list of segments stored in the buffer memory and destined for a corresponding destination, and

a temporary queue state table to maintain a state for each packet for which not all segments have yet been received from the FIFO memory, the state for each such packet comprising a linked list of the segments stored for that packet.

16. The packet buffering subsystem of claim 15, further comprising a queue manager to transfer, upon receipt of the last segment for a respective packet that has its state maintained in the temporary queue state table, segments stored for the respective packet included in the linked list corresponding to the respective packet.

17. The packet buffering subsystem of claim 15, wherein the memory manager replaces the source index of each segment with a first source index indicative of the position of the packet buffering subsystem in the network processing device.

18. The packet buffering subsystem of claim 17, wherein the source index is replaced prior to writing a respective segment to the buffer memory.

19. The packet buffering subsystem of claim 15, wherein the memory manager replaces a segment length of a first segment of the received packet with a total length of the received packet.

20. The packet buffering subsystem of claim 19, wherein the segment length of the first segment of the received packet is replaced prior to writing the first segment of the received packet to the buffer memory.

21. The packet buffering subsystem of claim 15, wherein the plurality of virtual queues maintained by the memory manager comprise multiple queues for at least one destination, the multiple queues serving different traffic classes.

22. The packet buffering subsystem of claim 1, implemented on an egress section of a line card.

23. The packet buffering subsystem of claim 1, implemented on an ingress section of a line card.

24. A network processing device comprising:

an epoch-based switch fabric;

a backplane supporting multiple ingress port pipes and egress port pipes to the switch fabric;

an epoch scheduler to schedule connection of ingress port pipes to egress port pipes through the switch fabric for each epoch; and

a plurality of line cards, each connected to the epoch-based switch fabric by at least one ingress port pipe, each line card connected to a given ingress port pipe that is scheduled for a given epoch, and each line card constructing epoch data for the given epoch by concatenating multiple packet segments having a destination reachable through a given egress port pipe paired with the given ingress port pipe for the given epoch;

wherein;

packet segments corresponding to a first one of one or more packets include one or more first packet segments and one or more second packet segments;

packets are segmented each time the first packet exceeds a selected data length;

the one or more first packet segments are transmitted in a first epoch;

the one or more second packet segments are transmitted in a second epoch different from the first epoch;

packet data accumulated for a given segment may exceed the selected data length by up to a selected overflow amount when lengthening the given segment will allow the given segment to be a last segment for its corresponding packet; and

transmission of the given segment is delayed until it is determined whether the given segment can be made the last segment by extending the given segment up to the selected overflow amount.

25. A method of operating a network processing device comprising:

receiving multiplexed packet data marked with source indices;

sorting the multiplexed packet data to a plurality of FIFO buffers according to source index;

tracking the size of each packet as it is received into each FIFO buffer from the multiplexed packet data using a plurality of counters, associated respectively with the plurality of FIFO buffers;

performing packet segmentation on a packet being received into a given one of the FIFO buffers; and

outputting a segment of the received packet when packet data accumulated in that given FIFO buffer for the received packet exceeds a selected data length, the selected data length being less than the amount of data that can be transmitted through a switch fabric associated with the buffering subsystem during a single epoch of time;

allowing the packet data accumulated for a given segment to exceed the selected data length by up to a selected overflow amount when lengthening the given segment will allow the given segment to be a last segment for its corresponding packet;

delaying outputting the given segment until it is determined whether the given segment can be made the last segment by extending the given segment up to the selected overflow amount.

26. The method of claim 25, wherein the segmentation logic repeats the segmentation of the received packet each time the packet data accumulated in the given FIFO buffer for the received packet exceeds the selected data length.

27. The method of claim 25, further comprising placing a header on each segment output from the FIFO buffers.

28. The method of claim 27, further comprising initially setting a length field in each segment to indicate a length of a respective segment.

29. The method of claim 28, further comprising eventually overwriting a length field on the first segment of each multi-segment packet to indicate a total length of all segments of a corresponding multi-segment packet.

30. The method of claim 27, wherein placing a header on each segment comprises, for each segment that is not a first segment of a packet, saving the header from a preceding segment into a head of the FIFO buffer containing the segment as the preceding segment is output from the FIFO buffer, and modifying the saved header as necessary for the current segment.

31. A network processing device comprising:

an epoch-based switch fabric;

a backplane supporting multiple ingress port pipes and egress port pipes to the switch fabric;

an epoch scheduler to schedule connection of ingress port pipes to egress port pipes through the switch fabric for each epoch;

a plurality of ingress traffic managers, each coupled to the switch fabric by at least one corresponding ingress port pipe, each ingress traffic manager buffering packets, prior to transmission through the switch fabric, as a collection of buffered packet segments, and concatenating multiple buffered packet segments from one or more packets with a common egress port pipe destination to create epoch data for transmission through the switch fabric during each epoch for which the corresponding ingress port pipe is scheduled for connection to a corresponding egress port pipe; and

a plurality of egress traffic managers, each connected to the switch fabric by at least one the egress port pipe, each egress traffic manager parsing packet segments received from the ingress traffic managers during epochs in order to buffer the packet segments, and recombining the buffered packet segments for a given packet after all segments of the given packet are received, wherein each of the buffered packets is segmented into one or more packet segments included in the collection of buffered packet segments, and wherein;

the epoch data includes a plurality of the packet segments;

one of the buffered packets includes one or more first packet segments and one or more second packet segments;

the buffered packets are segmented each time the buffered packets exceed a selected data length;

the one or more first packet segments are transmitted in a first epoch;

the one or more second packet segments are transmitted in a second epoch different from the first epoch;

packet data accumulated for a given segment may exceed the selected data length by up to a selected overflow amount when lengthening the given segment will allow the given segment to be a last segment for its corresponding packet; and

transmission of the given segment is delayed until it is determined whether the given segment can be made the last segment by extending the given segment up to the selected overflow amount.

32. The network processing device of claim 31, wherein an epoch length is at least ten times a maximum segment length.

33. The network processing device of claim 32, wherein the epoch length is sufficient to allow transmission of a packet of a maximum allowable length without segmentation.

34. The network processing device of claim 32, wherein each ingress traffic manager segments packets according to a source index indicative of a source port, and changes the source index of the given segment to an index assigned to the ingress traffic manager prior to transmitting the given segment as epoch data.

35. The network processing device of claim 32, wherein each ingress traffic manager and egress traffic manager saves state information such that the first packet segments can be transmitted from a given ingress traffic manager to a given egress traffic manager during the first epoch, with the second packet segments being transmitted during the second epoch that corresponds to the same given ingress traffic manager/egress traffic manager pairing as the first epoch.

36. The network processing device of claim 35, wherein the given egress traffic manager stores packet segments as the packet segments are received, the given egress traffic manager comprising a temporary queue state table to save state information for packets that have not had all packet segments received, the state information for each such packet comprising a linked list of the packet segments stored for that packet.

37. The network processing device of claim 36, wherein each egress traffic manager further comprises:

a destination queue state table to maintain a state for each of a plurality of virtual queues associated with different packet destinations, the state for each virtual queue comprising a linked list of packet segments stored and destined for a corresponding destination; and

a queue manager to transfer, upon receipt of the last segment for a respective packet that has its state maintained in the temporary queue state table, packet segments stored for the respective packet included in the linked list corresponding to the respective packet.

38. The network processing device of claim 36, wherein each ingress traffic manager further comprises a destination queue state table to maintain a state for each of a plurality of virtual queues associated with different packet destinations, the state for each virtual queue comprising a linked list of segments stored and destined for a corresponding destination, and wherein the segments for a first packet are stored in consecutive order in the linked list of segments stored for a given destination.

39. The network processing device of claim 38, wherein the destination queue state table maintains multiple virtual queues associated with a common packet destination, each virtual queue being associated with at least one packet class, and wherein each egress traffic manager uses a source index associated with a corresponding ingress traffic manager and a traffic class to maintain a state for each packet until all segments for that packet are received.

40. The network processing device of claim 32, wherein each ingress traffic manager comprises segmentation logic to segment packets to create the buffered packet segments, wherein the segmentation logic creates multiple packet segments once the given packet exceeds the selected data length.

41. The network processing device of claim 31, wherein each ingress traffic manager, when concatenating multiple buffered packet segments to create epoch data for a given epoch, concatenates packet segments until a next segment awaiting transmission to the common egress port pipe destination is longer than a space remaining for data transmission during the given epoch.

42. A method of operating a network processing device, the method comprising:

switching packet data during a series of epochs through a switch fabric having multiple ingress port pipes and egress port pipes, each epoch corresponding to a switch fabric configuration that connects given ingress port pipes with given egress port pipes;

for packets received by the network processing device, segmenting each packet exceeding a selected data length prior to switching packet data corresponding to that packet through the switch fabric;

concatenating multiple packet segments from one or more packets with a common egress port pipe destination to create epoch data for transmission through the switch fabric during each epoch from each ingress port pipe scheduled for connection to a corresponding egress port pipe, wherein;

packet segments corresponding to one of the one or more packets include one or more first packet segments and one or more second packet segments;

the one or more first packet segments are transmitted in a first epoch;

the one or more second packet segments are transmitted in a second epoch different from the first epoch;

packet data accumulated for a given segment may exceed a selected data length by up to a selected overflow amount when lengthening the given segment will allow the given segment to be a last segment for its corresponding packet; and

transmission of the given segment is delayed until it is determined whether the given segment can be made the last segment by extending the given segment up to the selected overflow amount;

parsing packet segments received from egress port pipes during epochs in order to buffer the packet segments; and

recombining the buffered packet segments for the given packet after all segments of the given packet are received from a respective egress port pipe.

43. The method of claim 42, wherein an epoch length is at least ten times a maximum segment length.

44. The method of claim 43, wherein the epoch length is sufficient to allow transmission of a packet of a maximum allowable length without segmentation.

45. The method of claim 43, wherein segmenting each packet exceeding the selected data length comprises marking packet segments according to a source index indicative of a source port, the method further comprising changing the source index of a first packet segment to an index associated with an ingress port pipe over which epoch data containing the first packet segment will be transmitted, prior to transmitting the first packet segment as epoch data.

46. The method of claim 43, further comprising saving state information in the device prior to each ingress port pipe and after each egress port pipe, such that the first packet segments can be transmitted from a first ingress port pipe to a first egress port pipe during the first epoch, with the second packet segments being transmitted during the second epoch that corresponds to the same ingress port pipe/egress port pipe pairing as the first epoch.

47. The method of claim 46, further comprising storing packet segments at a receiving end of each egress port pipe as the packet segments are received, and concurrently saving state information for packets that have not had all packet segments received, the state information for each such packet comprising a linked list of the packet segments stored for that packet.

48. The method of claim 47, further comprising:

maintaining a state at the receiving end of each egress port pipe for each of a plurality of virtual queues associated with different packet destinations, the state for each virtual queue comprising a linked list of packet segments stored and destined for a corresponding destination; and

transferring, upon receipt of the last segment for a respective packet that has its state information saved at the receiving end of a given egress port pipe, packet segments stored for the respective packet included in the linked list corresponding to the respective packet at the given egress port pipe.

49. The method of claim 47, further comprising maintaining a state at a sending end of each ingress port pipe for each of a plurality of virtual queues associated with different packet destinations, the state for each virtual queue comprising a linked list of packet segments stored and destined for a corresponding destination, and wherein the packet segments for a corresponding packet are stored in consecutive order in the linked list of packet segments stored for the corresponding destination.

50. The method of claim 49, wherein maintaining the state at the sending end of each ingress port pipe comprises maintaining multiple virtual queues associated with a common packet destination, each virtual queue being associated with at least one packet class, and wherein maintaining the state at the sending end of each egress port pipe comprises associating a packet segment state with a source index associated with an ingress port pipe and a traffic class to maintain the state for each packet until all segments for that packet are received.

51. The method of claim 42, wherein concatenating multiple buffered packet segments to create epoch data for a given epoch comprises concatenating segments until a next packet segment awaiting transmission to the common egress port pipe destination is longer than a space remaining for data transmission during the given epoch.