Method and apparatus for reordering packet data units in storage queues for reading and writing memory

DETAILED DESCRIPTION The invention is directed to a method and system for reordering data units that are to be written to, or read from, selected locations in a memory.
The data units are re-ordered so that an order of accessing memory (or portions thereof) is optimal for speed of reading or writing memory, not necessarily an order in which data units were received or requested.
The invention is applicable to a packet memory, and a method for operating that packet memory, so as to use as much memory speed as possible.
Packets that are received at input interfaces are divided into cells, with the cells being allocated to independent memory banks.
Many such memory banks are kept busy concurrently, so the cells (and thus the packets) are read into the memory as rapidly as possible.
A set of first-in-first-out (FIFO) queues includes one queue for each such memory bank, and is disposed in a sequence of rows (herein called "stripes") so as to have one queue element for each time slot to write to the memory.
The FIFO queues can include cells in each stripe from more than one complete packet, so as to reduce the number of memory operations for multiple packets.
In a preferred embodiment, as packets are received, their packet information is disassembled into cells of a uniform size.
The individual cells are mapped to sequential memory addresses, in response to the order in which they appear in packets, and in response to the packet queue(s) the packet is to be written to.
When the memory is ready to read cells into the memory, a stripe of cells from those queues is read into the memory.
Similarly, for packets that are to be sent to output interfaces, cells can be located in the independent memory banks and read therefrom, so the cells (and thus the packets) are read out of the memory as rapidly as possible.
Cells from the memory can be placed in individual queues for each memory bank.
When the memory is ready to read cells out of the memory, one stripe of cells from those queues can be read out of the memory, and packets can be reassembled from those cells