Browse Prior Art Database

Method for bandwidth-efficient linked list storage for packet data

IP.com Disclosure Number: IPCOM000008929D
Publication Date: 2002-Jul-24
Document File: 5 page(s) / 122K

Publishing Venue

The IP.com Prior Art Database

Abstract

The disclosed is a method for bandwidth-efficient linked list storage for packet data. Benefits include improved performance and improved power performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 41% of the total text.

Method for bandwidth-efficient linked list storage for packet data

The disclosed is a method for bandwidth-efficient linked list storage for packet data. Benefits include improved performance and improved power performance.

Background

              Conventionally, managed memory is used to store packets before being forwarded. Managed memory means that the memory usage is tracked. Space is allocated for received packets. When the packet is forwarded successfully, the allocated space is released so that the memory can be used effectively. This procedure is especially important for devices with internal packet memory, where the memory size is small and must be utilized efficiently.

              To store packets of variable size efficiently, a linked list of memory segments is conventionally used. Each segment could be of the same size or of different sizes. For example, consider a single segment size linked list with a segment size of 128 bytes (see Figure 1). The linked list for a packet consumes three memory segments (see Figure 2). Locations 2, 3, and 9 must be written while receiving the relevant packet chunks. Using the disclosed method, only locations 2 and 3 must be written (see Figure 3).

              The start of packet data is given by the Start of Packet pointer (SOP pointer). A packet that is less than or equal to 128 bytes occupies one segment of memory. It can be addressed by just one link, the SOP pointer for the packet. A packet between 129 and 256 bytes inclusive occupies two segments of memory and can be completely addressed by using two links, the SOP pointer and the NextLink associated with the SOP pointer.

              Although in Figure 1 the next link is shown as being stored adjacent to the packet data, a better practice is to use different memory banks so that the control and data portions of the design are unlinked. Typically, the packet data itself is stored in data memory (internal or external to the device). The control information is stored in control memory (which again could be external or internal to the device). The linked list structure is stored in the control memory. Indexing into the data memory using a link pointer retrieves the data associated with that segment of the packet. Indexing the control memory using a link pointer retrieves the next link and other control information associated with that link. An example of control information is a field indicating that a particular link is the last link of the packet.

              Typical designs of switches involve processing of packet data in small chunks because the same control or data path pipeline would be used to process packets received on several interfaces in a time-multiplexed fashion (see Figure 4). The memory segment sizes could be designed based on the chunk size. A link must be allocated for the chunk unless an already allocated link has enough space to store it. The data must be written into the data memory at the segment pointed to by the newly allocated link. The linked list associated with the packet being...