Browse Prior Art Database

A Fast, Shared, Memory with Multiple Output Queues for Variable Length Packets, Made from Slow Memory Elements

IP.com Disclosure Number: IPCOM000013879D
Original Publication Date: 2001-Apr-15
Included in the Prior Art Database: 2003-Jun-18
Document File: 4 page(s) / 47K

Publishing Venue

IBM

Abstract

Disclosed is a fast, shared, memory with multiple output queues for variable length packets, which memory is made from slow memory elements.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 4

  A Fast, Shared, Memory with Multiple Output Queues for Variable Length Packets, Made from Slow Memory Elements

  Disclosed is a fast, shared, memory with multiple output queues for variable length packets, which memory is made from slow memory elements.

A problem often arises is that a large, fast memory is needed in which the logical organization is that of multiple output queues. The storage elements should be DRAM because of the large size (number of bytes) required. However the random access times of DRAMS are rather long. This is a considerable disadvantage when multiple output queues are to be realized, since writing and reading data to the different queues requires rapid access to any address in the memory.

Data can be transferred in and out of a DRAM most quickly when it is wide. For instance, DRAMS are often organized into wide rows, where each row is subdivided into columns. Addressing a row is a slow process but once it has been addressed then access to the individual columns within that row is much more rapid. So data-transfer is most efficient if an entire row (i.e. all bytes of all columns ) are accessed. If the required speed cannot be met by a single RAM then several RAM's must be connected in parallel and appear as a single RAM element with a multiple of the width of a single RAM. The unit of data accessed by a single row address is called a "container". This container may extend across the width of one or more RAM's.

The method of achieving high speed by using very wide RAMs (with one or more RAM elements) causes problems when data is to be stored which is presented in the form of variable length packets. If each packet is simply split into one or more containers for storage in the memory, there will be unused space in the last container of each packet since it is unlikely that the packet length will be an exact multiple of the container size. This unused space in the container translates into a loss of memory capacity and bandwidth to a degree which is not easy to predict. This makes it difficult to determine the effective size and speed of such a memory.

The dead space can be eliminated by packing the packets together in the containers. However for the case a flow of packets is to be written to memory and where each packet may belong to a different queue this is not so simple, since the data for each queue is found at a different location in the memory.

The main packet memory is implemented as one or more DRAM elements in parallel so that they appear as one very wide RAM with a container width of W bytes. This is illustrated in Figure 1, where only two of the several possible DRAMs are shown. The input data is presented as a sequence of cells of width w bytes. Each cell may contain fragments from one or more packets and each fragment can belongs to one of several queues. The packer packs the fragments contained in stream of cells compactly into a containers which, when they are filled, are written into the packet...