System and method for packet storage and retrieval

• US 7,058,789 B2
• Filed: 02/04/2003
• Issued: 06/06/2006
• Est. Priority Date: 02/04/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Croft, Walter E., Henderson, Alex E.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): DILLER, JESSE DAVID
• Application Number:
  US10/358,548
• Publication Number:
  US 20040037276A1
• Time in Patent Office: 1,218 Days
• Field of Search: 370/469, 711/220, 707/230, 710/52, 710/56
• US Class Current: 711/220
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields

Abstract

A network services processor receives, stores, and modifies incoming packets and transmits them to their intended destination. The network services processor stores packets as buffers in main and cache memory for manipulation and retrieval. A memory subsystem stores packets as linked lists of buffers. Each bank of memory includes a separate memory management controller for controlling accesses to the memory bank. The memory management controllers, a cache management unit, and free list manager shift the scheduling of read and write operations to maximize overall system throughput. For each packet, packet context registers are assigned, including a packet handle that points to the location in memory of the packet buffer. The contents of individual packets can be accessed through the use of encapsulation pointer registers that are directed towards particular offsets within a packet, such as the beginning of different protocol layers within the packet.

Claims

1. A method of processing an instruction for data in a packet, the method comprising:

editing protocol layers of the packet;

storing a plurality of encapsulation pointers, the encapsulation pointers associated with protocol layers and indicating offsets between a start point of the packet and start points of the edited version of the protocol layers of the packet;

receiving an instruction, the instruction comprising a protocol layer and an offset relative to a start point of the protocol layer;

indicating whether the instruction is directed towards the edited version of the protocol layers of the packet; and

adding the offset relative to the start point of the protocol layer of the

encapsulation pointer associated with the protocol layer to determine an offset relative to the beginning of the packet.

2. The method of claim 1, wherein the instruction is a read instruction.

3. The method of claim 1, wherein the instruction is a write instruction.

4. The method of claim 1, further comprising:

maintaining a packet handle, the packet handle indicating a location in memory of the start point of the packet; and

adding the offset relative to the beginning of the packet to the value of the location in memory of the start point of the packet to determine a location in memory for the instruction.

5. The method of claim 1, wherein the editing of the protocol layers of the packet comprises adding a Multi Protocol Label Switching (MPLS) field into the packet.

6. An apparatus for processing instructions for a packet, the apparatus comprising:

an editing unit to edit protocol layers of the packet;

a packet context to store a plurality of encapsulation pointers, the encapsulation pointers associated with protocol layers and indicating offsets between a start point of the packet and start points of the edited version of the protocol layers of the packet; and

a packet processing controller to;

receive an instruction, the instruction comprising a protocol layer and an offset relative to a start point of the protocol layer,

indicate whether the instruction is directed towards the edited version of the protocol layers of the packet, and

add the offset relative to the start point of the protocol layer to the encapsulation pointer associated with the protocol layer to determine an offset relative to the beginning of the packet.

7. The apparatus of claim 6, wherein the instruction is a read instruction.

8. The apparatus of claim 6, wherein the instruction is a write instruction.

9. The apparatus of claim 6, wherein:

the packet context stores a packet handle, the packet handle indicating a location in memory of the start point of the packet; and

the packet processing controller to add the offset relative to the beginning of the packet to the value of the location in memory of the start point of the packet to determine a location in memory for the instruction.

10. The apparatus of claim 6, wherein the editing of the protocol layers of the packet comprises adding a Multi Protocol Label Switching (MPLS) field into the packet.

11. The apparatus of claim 6, wherein the packet processing controller includes a table entry processor to process one or more of the following:

comparison tables, action tables, and state tables.

12. The apparatus of claim 6, further comprising a field extraction unit coupled to the packet processing controller, the field extraction unit to

retrieve packet data from a cache,

extract portions of packets referenced by an extract request, and

return the extracted portions of the packets to the packet processing controller.

13. An apparatus for processing packets, the apparatus comprising:

an editing unit to edit protocol layers of the packet;

a packet context to store a plurality of encapsulation pointers, the encapsulation pointers associated with protocol layers and indicating offsets between a start point of the packet and start points of the edited version of the protocol layers of the packet;

a memory storing a packet in a plurality of buffers; and

a packet processing controller to;

store a packet handle for the packet, the packet handle indicating a location in the memory for a first buffer of the packet;

receive an instruction for the packet, the instruction comprising a protocol layer and an offset relative to the start point of the protocol layer;

determine whether a location in memory corresponding to the offset relative to the start point of the protocol layer is stored in the first buffer of the packet;

determine whether the instruction is directed towards the edited version of the protocol layers of the packet; and

add the offset relative to the start point of the protocol layer to the value of the packet handle indicating a location in memory of the start point of the packet to determine a location in memory for the instruction, when the location in memory corresponding to the offset relative to the beginning of the packet is stored in the first buffer of the packet.

14. The apparatus of claim 13, wherein the instruction is a read instruction.

15. The apparatus of claim 13, wherein the instruction is a write instruction.

16. The apparatus of claim 13, wherein the packet processing controller is further to:

determine a size of the first buffer; and

determine that the location in memory corresponding to the offset relative to the start point of the packet is stored in a first buffer of the packet when the magnitude of the offset is smaller than the size of the first buffer.

17. A system comprising:

a packet input unit to process an incoming packet;

an editing unit coupled to the packet input unit, the editing unit to edit protocol layers of the packet;

a packet context to store a plurality of encapsulation pointers, the encapsulation pointers associated with protocol layers and indicating offsets between a start point of the packet and start points of the edited version of the protocol layers of the packet;

a packet processing controller to

receive an instruction, the instruction comprising a protocol layer and an offset relative to a start point of the protocol layer,

indicate whether the instruction is directed towards the edited version of the protocol layers of the packet,

add the offset relative to the start point of the protocol later to the encapsulation pointer associated with the protocol layer to determine an offset relative to the beginning of the packet; and

a packet output unit to output the edited version of the packet.

18. The system of claim 17, further comprising:

a search processor to send search requests for data located in the memory; and

a cache and memory controller to determine whether the request to the location in the memory is stored in a cache.

19. The system of claim 17, wherein the packet context stores a packet handle, the packet handle indicating a location in memory of the start point of the packet and the packet processing controller adds the offset relative to the beginning of the packet to the value of the location in memory of the start point of the packet to determine a location in memory for the instruction.