Method and apparatus for using meta-packets in a packet processing system

• US 7,965,708 B2
• Filed: 06/07/2005
• Issued: 06/21/2011
• Est. Priority Date: 06/07/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Williams, John Jr., Evans, Adrian, Markevitch, James, Cohen, Earl T.
• Primary Examiner(s): Ferris; Derrick W
• Assistant Examiner(s): ONAMUTI, GBEMILEKE J
• Application Number:
  US11/147,755
• Publication Number:
  US 20060274773A1
• Time in Patent Office: 2,205 Days
• Field of Search: 370/394, 370/412, 370/398, 370/389, 370/413, 709/250, 712/201, 345/501
• US Class Current: 370/389
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9042 Separate storage for different parts of the packet, e.g. header and payload
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

Meta-packets are used to more efficiently reassemble packets and to more efficiently conduct other packet processing operations. The meta-packets are special types of packets which are interpreted by hardware in a queuing system. Instead of directly containing data, the meta-packet packets contain instructions for building a desired packet from various identifiable storage locations in the packet processor system. Because the reassembled packet replaces the meta-packet, packet ordering is preserved.

Claims

1. A packet processing system, comprising:

a first storage buffer configured to store data packets containing headers with address or control fields used for directing transport of the data packets over a packet switched network;

a second storage buffer configured to store packet fragments, wherein two or more of the packet fragments are combinable as a reassembled data packet that is capable of being transported over the packet switched network;

a first packet queue configured to store the data packets or packet handles that identify where the data packets are located in the first storage buffer;

a second packet queue configured to store meta-packets containing embedded sequences of meta-commands that are executable independently of the address and control fields contained in the packet headers and that comprise instructions for reassembling the packet fragments;

a packet scheduler configured to output the data packets stored in the first packet queue together with the meta-packets stored in the second packet queue in a first sequential order corresponding with a same order that the data packets and the meta-packets are each separately stored in the first and second packet queues;

a queuing system configured to process the data packets or packet handles and the meta-packets in the first sequential order received from the packet scheduler, wherein the queuing system is further configured, during processing of the meta-packets, to process the packet fragments stored in the second storage buffer to create the reassembled data packet, wherein the packet fragments are reassembled in a second sequential order identified by the embedded sequences of meta-commands contained in the meta-packets, and wherein the reassembled data packet replaces the meta-packets in the first sequential order; and

an output port configured to output the data packets and the reassembled data packet in the first sequential order.

2. The packet processing system according to claim 1 wherein at least some of the packet handles contained in the packet queues point to meta-packets that are then processed next in the first sequential order by the queuing system.

3. The packet processing system according to claim 1 wherein the queuing system processes the meta-commands serially in an order contained in the meta-packets.

4. The packet processing system according to claim 1 wherein one or more of the meta-commands cause the queuing system to identify a length for the reassembled data packet and then include the identified length in the reassembled data packet.

5. The packet processing system according to claim 1 wherein one or more of the meta-commands include a memory insert instruction configured to cause the queuing system to load another meta-packet from memory into the packet queues.

6. The packet processing system according to claim 1 wherein one or more of the meta-commands include copy instructions that copy portions of a first meta-packet into a second different meta-packet.

7. The packet processing system according to claim 1 wherein one or more of the meta-commands cause the queuing system to drop one or more of the packet fragments in the first packet queue.

8. The packet processing system according to claim 7 wherein the one or more of the meta-commands cause the queuing system to generate a report identifying an amount of data dropped in the one or more dropped packet fragments.

9. The packet processing system according to claim 8 wherein the report is returned to a processing or control element as part of the reassembled data packet.

10. The packet processing system according to claim 1 wherein:

the first packet queue is located in the packet scheduler and a feedback path couples an output of the queuing system back to the first packet queue; and

one or more of the meta-commands comprise programmable re-queue commands that, when executed, cause the queuing system to re-enqueue the meta-packets back through the feedback path to the first packet queue.

11. The packet processing system according to claim 10 wherein the re-enqueued meta-packets are output through the feedback path separately from the meta-packets or reassembled data packet output from the output port.

12. The packet processing system according to claim 1 wherein one or more of the meta-commands cause the queuing system to generate multiple packets from the same meta-packet.

13. The packet processing system according to claim 1 wherein one or more of the meta-commands cause the queuing system to copy a portion of one or more of the meta-packets into the reassembled data packet or another meta-packet.

14. The packet processing system according to claim 1 wherein the meta-packets are distinguished from the data packets or packet handles by indicating the meta-packets using out-of-band signaling.

15. The packet processing system according to claim 1 wherein the meta-packets are consumed in the queuing system without being output to the output port.

16. A method, comprising:

receiving a first set of data packets and a second set of data packets in one or more buffers;

queuing the first set of data packets comprising data or control packets (regular packets) in a first packet queue;

creating meta-packets responsive to receiving the second set of data packets, wherein the meta-packets include a packet header and meta-commands for assembling the second set of data packets;

queuing the meta-packets in a second packet queue;

de-queuing the first set of data packets and the meta-packets in a first sequential order corresponding with a same order that the first set of data packets and the meta-packets are each separately stored in the first and second packet queues;

distinguishing the meta-packets from the first set of data packets by a bit in the packet header;

executing the meta-commands in the meta-packets to retrieve the second set of data packets in a second sequential order identified by the meta-commands in the meta-packets;

replacing the meta-packets with the second set of data packets in the first sequential order; and

transferring the first set of data packets and the second set of data packets to an output port in the first sequential order.

17. The method according to claim 16 including processing the first set of data packets and the meta-packets in the first sequential order, wherein the processing comprises transferring the first set of data packets and executing the meta-commands.

18. The method according to claim 17 including:

reassembling the second set of data packets read from memory or from a buffer separate from the first and second packet queues.

19. The method according to claim 16 including:

locating one or more of the meta-packets in the second packet queue, wherein the meta-commands provide a notice indicating all packets in front of the one or more meta-packets in the second packet queue have been flushed.

20. The method according to claim 16 including executing a meta-command in one of the meta-packets that issues a command to a packet processing element of a packet processor.

21. The method according to claim 16 including executing one or more of the meta-commands that re-enqueue results from the meta-commands back to the first or second packet queues.

22. The method according to claim 16 including executing one or more of the meta-commands in the meta-packets that generate one or more regular packets or additional meta-packets.

23. The method according to claim 16 including executing one or more of the meta-commands that copy a portion of one or more of the meta-packets into another packet or meta-packet.

24. The method according to claim 16 including executing one or more of the meta-commands that cause one or more of the data packets to be dropped from the first packet queue.

25. The method according to claim 24 including one or more additional meta-commands that generate a report identifying an amount of data dropped in the one or more data packets.

26. The method according to claim 25 including returning the report to a processing or control element as part of an assembled packet.

27. The method according to claim 16 including:

identifying different portions of different packets received in the one or more buffers;

generating additional meta-packets containing meta-commands that identify which of the one or more buffers contain the different portions and that also identify what order the different portions are stored in the one or more buffers; and

sending the additional meta-packets to a queuing system that then reassembles the different portions into the different packets.

28. The method according to claim 27 including queuing the reassembled packets in the first sequential order previously held by the additional meta-packets.

29. The method according to claim 16 including executing the meta-commands in a same meta-packet that cause multiple different regular packets or meta-packets to be created and output or re-enqueued.

30. A packet processing system, comprising:

one or more packet memory devices configured to receive incoming network packets and packet fragments from a packet switched network, wherein the network packets comprise a packet payload;

one or more packet processing elements configured to generate meta-packets containing meta-instructions for reassembling the packet fragments, wherein the meta-packets do not contain packet payloads; and

a queuing system configured to execute the meta-instructions in the meta-packets, wherein execution of the meta-instructions cause the packet processing system to perform operations comprising;

arranging the network packets together with the meta-packets in a first sequential order;

assembling the packet fragments into reassembled network packets in a second sequential order identified in the meta-instructions; and

replacing the meta-packets with the reassembled network packets in the first sequential order.

31. The packet processing system according to claim 30 including a recirculation path between the queuing system and the one or more packet memory devices used by the queuing system under control of the meta-instructions to send the packets back to the one or more packet memory devices.

32. The packet processing system according to claim 30 wherein the queuing system includes:

queues for storing the network packets and the meta-packets; and

a scheduler for scheduling the queuing of the network packets and the meta-packets, wherein the network packets are transferred according to associated packet handles output by the scheduler.

33. The packet processing system according to claim 32 wherein the meta-packets cause the output packet module to re-enqueue the network packets or the meta-packets in the queuing system.

34. The packet processing system according to claim 30 wherein the network packets and the meta-packets are de-queued sequentially in the queuing system and then processed in a same sequential order.

35. The packet processing system according to claim 30 wherein the operations further comprise outputting the network packets and the reassembled network packets in the first sequential order.

36. The packet processing system according to claim 30 wherein the operations further comprise:

identifying a length of the reassembled network packets; and

inserting the identified length in the reassembled network packets.

37. The packet processing system according to claim 36 wherein the identified length indicates how much data should be read in retrieving the plurality of packet fragments, starting at an identified address location in the one or more packet memory devices.

38. A system, comprising:

means for receiving data packets and packet fragments in one or more buffers;

means for queuing the data packets comprising data or control packets (regular packets) in a first queue;

means for generating meta-packets associated with the packet fragments, wherein the meta-packets comprise a packet header and meta-commands comprising instructions for reassembling the packet fragments into a reassembled packet;

means for queuing the meta-packets in a second queue;

means for de-queuing the data packets and the meta-packets in a first sequential order corresponding with a same order that the data packets and the meta-packets are each separately queued in the first and second queues;

means for distinguishing the meta-packets from the data packets;

means for executing the meta-commands in the meta-packets to retrieve the packet fragments in a second sequential order identified by the meta-commands in the meta-packets;

means for reassembling the packet fragments in the second sequential order to create the reassembled packet;

means for replacing the meta-packets with the reassembled packet in the first sequential order; and

means for transferring the data packets and the reassembled packet in the first sequential order.

39. The system according to claim 38 including means for processing the data packets and the meta-packets in the first sequential order, wherein the processing comprises transferring the data packets and executing the meta-commands.

40. The system according to claim 39, wherein the reassembled packet is transferred in a same position in the first sequential order previously held by the meta-packets.

41. A non-transitory storage media having stored thereon computer executable instructions, wherein the instructions are executable by a system that cause the system to perform operations comprising:

receiving a plurality of data packets and a plurality of packet fragments;

storing the plurality of data packets and the plurality of packet fragments;

creating meta-packets that identify a location of the stored packet fragments;

queuing the plurality of data packets and the meta-packets in one or more packet queues of a packet scheduler in a first sequential order, wherein the meta-packets comprise a packet header and meta-commands for reassembling the plurality of packet fragments into a reassembled packet;

de-queuing the data packets and the meta-packets in the first sequential order;

transferring the de-queued data packets while executing the meta-commands in the meta-packets;

retrieving the plurality of packet fragments;

reassembling the plurality of packet fragments into the reassembled packet in a second sequential order according to the meta-commands; and

transferring the reassembled packet and the data packets to an output port in the first sequential order.

42. The non-transitory storage media according to claim 41 wherein the operations further comprise distinguishing the meta-packets from the data packets by a field in the packet header.

43. The non-transitory storage media according to claim 41 wherein the operations further comprise copying instructions into a first meta-packet for generating a second meta-packet identical to the first meta-packet.

44. The non-transitory storage media according to claim 43 wherein copying the instructions comprises repeatedly generating multiple timing packets that operate as a time stamp reference.