Abstract:
A method and system for reordering data units that are to be written to, or read from, selected locations in a memory are described herein. The data units are reordered so that an order of accessing memory is optimal for speed of reading or writing memory, not necessarily an order in which data units were received or requested. Packets that are received at input interfaces are divided into cells, with cells being allocated to independent memory banks. Many such memory banks are kept busy concurrently, so cells (and thus the packets) are read into the memory as rapidly as possible. The system may include an input queue for receiving data units in a first sequence and a set of storage queues coupled to the input queue for receiving data units from the input queue. The data units may be written from the storage queues to the memory in an order other than the first sequence. The system may also include a disassembly element for generating data units from a packet and a reassembling element for reassembling a packet from the data units.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to reordering data units for reading and writing memory, such as for example used in packet buffering in a packet router. 
     In a computer network, routing devices receive messages at one of a set of input interfaces, and forward them on to one of a set of output interfaces. It is advantageous for such routing devices to operate as quickly as possible so as to keep up with the rate of incoming messages. As they are received at an input interface, packets are read from the input interface into a memory, a decision is made by the router regarding to which output interface the packet is to be sent, and the packet is read from the memory to the output interface. 
     One problem in the known art is that packets are often of differing lengths, so that storing the packet in memory can use multiple cells of that memory. This complicates the decision of where in the memory to record the packet, and, depending on the nature of the memory, can slow the operations of reading packets into memory or reading packets from memory. 
     This problem in the known art is exacerbated by the relative speed with which memory can read and write. As memory becomes ever faster, the desirability of using the relative speed of that memory becomes ever greater. This problem is particularly acute when the memory itself has a plurality of memory banks capable of operating concurrently. Moreover, this problem is exacerbated when memory transfers use a relatively wide data transfer width; transfers that require just one or a few bytes more than the maximum transfer width waste relatively more memory read and write bandwidth as the data transfer width becomes relatively larger. 
     Accordingly, it would be advantageous to provide a packet buffer memory that uses as much of the speed of the memory as possible, particularly when that memory has banks which are capable of operating concurrently. This advantage is achieved in an embodiment of the invention in which packets are divided into cells, cells are allocated to memory banks capable of operating concurrently, and packets are reconstructed from the cells that were recorded in memory. Writing cells into the memory and reading cells from the memory need not occur in the same order in which those cells are received. 
     SUMMARY OF THE INVENTION 
     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. 
     In a preferred embodiment, each stripe of cells to be read into or read out of the memory is filled, as much as possible, before the next memory cycle, so as to make most efficient use of the parallel capacity of the memory. Similarly, stripes of cells to be read into or read out of the memory are also filled, as much as possible, in advance, so that memory cycles can be performed rapidly without waiting for filling any individual memory bank queue. Either of these might involve advancing cells of one or more packets out of order from the rest of their packet, so as to maintain one or more memory banks busy. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a block diagram of an improved system for packet buffer memory use. 
     FIG. 2 shows a block diagram of the memory controllers in an improved system for packet buffer memory use. 
     FIG. 3 shows a process flow diagram of a method for using an improved system for packet buffer memory use. 
     FIG. 4 shows a timing diagram that illustrates the timing of activities occurring in an improved system for packet buffer memory use. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. Those skilled in the art would recognize after perusal of this application that embodiments of the invention can be implemented using processors or circuits adapted to particular process steps and data structures described herein, and that implementation of the process steps and data structures described herein would not require undue experimentation or further invention. 
     System Elements 
     FIG. 1 shows a block diagram of an improved system for packet buffer memory use. 
     A system  100  includes a set of line cards  110  and a switching crossbar fabric  120 . 
     Each line card  110  includes a set of input interfaces  111 , a set of output interfaces  112 , and a set of (i.e., plural) control elements  130 . 
     Each control element  130  is disposed for receiving packets  113  at the input interfaces  111  and for transmitting those packets  113  to the switching fabric  120  for processing by the same or another control element  130 . 
     Each control element  130  includes a receive element  140 , a first memory controller  150 , a first memory  160 , a second memory controller  150 , a second memory  160 , a fabric interface element  170 , a transmit element  180 , and control circuits  190 . 
     The receive element  140  includes circuits disposed for receiving a sequence of packets  113  from a set of associated input interfaces  111 , and for sending those packets  113  to the first memory controller  150 . In a preferred embodiment, the receive element  140  is also disposed for performing relatively simple processing functions on the packets  113 , such as computing and checking consistency for packet headers or Internet Protocol (IP) header check-sum values. 
     The first memory controller  150  includes circuits disposed for the following functions: 
     receiving packets  113  from the receive element  140 ; 
     disassembling packets  113  into sequences of cells  151 ; and 
     storing (and scheduling for storing) cells  151  in the first memory  160 . 
     Although referred to herein as a single physical memory, the first memory  160  can include more than one SDRAM operating concurrently under the control of the first memory controller  150 . In a preferred embodiment, the first memory  160  includes two physical memories, each of which can operate concurrently or in parallel; however, there is no particular requirement for using more than one physical memory for operation of the invention. 
     Similar to the first memory controller  150 , the second memory controller  150  includes circuits disposed for the following functions: 
     retrieving (and scheduling for retrieving) cells  151  from the second memory  160 ; 
     reassembling packets  113  from sequences of cells  151 ; and 
     sending packets  113  to the transmit element  180 . 
     Similar to the first memory  160 , although referred to herein as a single physical memory, the second memory  160  can include more than one SDRAM operating concurrently under the control of the second memory controller  150 . In a preferred embodiment, the second memory  160  includes two physical memories, each of which can operate concurrently or in parallel; however, there is no particular requirement for using more than one physical memory for operation of the invention. 
     The fabric interface element  170  includes circuits disposed for sending packets  113  to the switching fabric  120 , and disposed for receiving packets  113  from the switching fabric  120 . 
     The transmit element  180  includes circuits disposed for sending packets  113  to output interfaces  112 . 
     The control circuits  190  provide for control of the control element  130  in accordance with techniques described herein. 
     Memory Controllers 
     FIG. 2 shows a block diagram of the memory controllers in an improved system for packet buffer memory use. 
     The first memory controller  150  and the second memory controller  150  have similar design; accordingly, the description below is made with reference to a single memory controller and a single memory. The single memory controller could be either the first memory controller  150  or the second memory controller  150 , while the single memory could be either the first memory  160  or the second memory  160 , as appropriate. 
     Write Controller 
     The memory controller  150  includes a set of input queues  210 , each disposed for receiving and storing packets  113 . 
     The memory controller  150  includes, for each input queue  210 , a disassembly element  220  disposed for disassembling packets  113  into sequences of cells  151 . In a preferred embodiment, each cell  151  is a uniform length (preferably 64 bytes). Thus, each packet  113  can consist of one or more cells  151 . 
     The memory controller  150  includes a memory queuing element  230 , disposed for queuing cells  151  for storage in the memory  160 . 
     The memory  160  (or if there is more than one physical memory, each physical memory) includes a plurality of memory banks  161 , each of which includes a segment of memory which is addressable by the memory  160  and separately usable by the memory  160 . 
     For example, SDRAM memories having a plurality of memory banks are known in the art. One property of known memories having a plurality of banks is that the time during which the entire memory is busy (herein called “busy time”) in storing an element in one bank is less than the time during which the individual bank is busy (herein called “latency time”). 
     The memory queuing element  230  uses the difference between busy time and latency time for the memory  160  to access separate memory banks  161  of the memory  160 . The memory queuing element  230  arranges the cells  151  so they can be stored into separate memory banks  161  in order, so that it can store cells  151  into separate memory banks  161  faster than if those cells  151  were stored into separate memory banks  161  at random. 
     The memory queuing element  230  includes a plurality of storage queues  231 , one for each memory bank  161 . Each storage queue  231  includes a set of cell locations  232 , each of which holds a single cell  151 , a storage queue head pointer  233 , and a storage queue tail pointer  234 . 
     In sequence, at a speed consistent with the busy time of the memory  160 , the memory queuing element  230  commands memory banks  161  to store single cells  151  from the cell location  232  denoted by the storage queue head pointer  233 . 
     Memory banks  161  are therefore used to store single cells  151  at a speed consistent with the busy time, rather than the latency time, of the memory  160 . Where there are two or more physical memories, the memory queuing element  230  commands those two or more physical memories to operate concurrently or in parallel, so that storage bandwidth into each physical memory can be as fully utilized as possible. 
     The memory controller  150  includes a dequeuing element  240 , disposed for dequeuing cells  151  from the storage queues  231  for storage in the memory  160 . 
     The dequeuing element  240  stores one cell  151  in sequence from one cell location  232  at the head of each storage queue  231  into its designated location in the memory  160 . The dequeuing element  240  updates for each storage queue  231 , the storage queue head pointer  233  and the storage queue tail pointer  234 . 
     In a preferred embodiment, the dequeuing element  240  stores the cells  151  in the memory  160  in the sequence in which they were entered into each storage queue  231  (that is, the dequeuing element  240  does not reorder cells  151  within any of the storage queues  231 ). In alternative embodiments, the dequeuing element  240  may reorder cells  151  within the storage queues  231  to achieve greater speed at writing to the memory  160 . 
     Read Memory Controller 
     The memory controller  150  includes a memory reading element  250 , disposed for reading cells  151  from the memory  160  for transmission. 
     The following description is similar to operation of the memory queuing element  230 . 
     The memory reading element  250  may identify packets  113  that are to be sent to output interfaces in response to their location in the memory  160  (that is, in selected areas of the memory  160  designated for associated output interfaces). 
     The memory reading element  250  may read the cells  151  for those packets  113  in sequence from their locations in the memory  160  into a set of reassembly queues  251 , similar to the storage queues  231 . The memory reading element  250  may reassemble the packets  113  from the cells  151  located in the reassembly queues  251 , similar to disassembly of the packets  113  into cells  151  for placement in the storage queues  231 . 
     Once packets  113  are reassembled, they are sent to a set of output queues  252 , each of which is associated with a selected output interface  112 . From each selected output interface  112 , packets  113  are sent to the associated fabric interface element  170  or transmit element  180 . 
     Timing Diagram 
     FIG. 4 shows a timing diagram that illustrates the timing of activities occurring in an improved system for packet buffer memory use. 
     A timing diagram  400  includes an X axis  401  showing progressive time, and a Y axis  402  showing individual memory banks  161  in the memory  160 . 
     A first trace  410  shows a busy time  411  during which the entire memory  160  is busy for writing to a first memory bank  161 , and a latency time  412  during which the first memory bank  161  is busy but the rest of the memory  160  is not necessarily busy. 
     Similarly, a second trace  420  shows a similar busy time  421  and latency time  422  for writing to a second memory bank  161 . 
     Similarly, a third trace  430  shows a similar busy time  431  and latency time  432  for writing to a third memory bank  161 . 
     Similarly, a fourth trace  440  shows a similar busy time  441  and latency time  442  for writing to a fourth memory bank  161 . 
     The timing diagram  400  shows that operation of the memory  160  proceeds at an effective rate equal to L/B times the ordinary storage speed of the memory  160 , where L=latency time, and B=busy time. 
     Writing Stripes 
     The memory queuing element  230  arranges cells  151  in the storage queues  231  so that an entire set of cell locations  232 , one for each memory bank  161  (herein called a “stripe”) can be stored into the memory  160  concurrently. 
     The memory queuing element  230  arranges sequential cells  151  from packets  113  in sequential storage queues  231 , so that when those sequential cells  151  are stored into the memory  160 , they are stored into sequential locations therein. However, those sequential cells  151  are written into the memory  160  in stripe order, thus not necessarily in the order in which they arrived in packets  113 . 
     Although sequential cells  151  are written into the memory  160  in stripe order, they are not necessarily written into the memory  160  in sequential locations in those memory  160 . Thus, a single stripe can include cells  151  to be written into different areas of the memory  160 , in particular in a preferred embodiment where those different areas of the memory  160  are associated with different packet queues. 
     Method of Operation 
     FIG. 3 shows a process flow diagram of a method for using an improved system for packet buffer memory use. 
     A method  300  is performed by the system  100 , including the plural line cards  110 , each having plural control elements  130 , and switching (crossbar) fabric  120 . Each control element  130  includes the receive element  140 , the first memory controller  150 , the first memory  160 , the second memory controller  150 , the second memory  160 , the fabric interface element  170 , the transmit element  180 , and control circuits  190 . 
     Receiving Packets 
     At a flow point  310 , the system  100  is ready to receive a packet  113 . 
     At a step  311 , the receive element  140  receives the packet  113  and stores the packet  113  in an input queue  210 . 
     At a step  312 , the disassembly element  220  disassembles the packet  113  into one or more cells  151 . Each cell  151  has a uniform length, preferably 64 bytes. If the packet  113  is not an exact multiple of the cell length, the last cell  151  in that packet  113  can contain undetermined data which had been stored in the cell  151  at an earlier time. 
     At a step  313 , the memory queuing element  230  places the sequence of cells  151  for the packet  113  in a related sequence of storage queues  231 . As each cell  151  is placed in its related storage queue  231 , the memory queuing element  230  updates the tail pointer for that storage queue  231 . 
     Storing Cells into Memory 
     At a flow point  320 , the system  100  is ready to store cells  151  in the memory  160 . The method  300  performs those steps following this flow point in parallel with those steps following other flow points. 
     At a step  321 , the dequeuing element  240  writes cells  151  in sequence from the head of each storage queue  231  to its designated location in the memory  160 . 
     At a step  322 , the dequeuing element  240  updates, for each storage queue  231 , the storage queue head pointer  233  and the storage queue tail pointer  234 . 
     Reading Cells from Memory 
     At a flow point  330 , the system  100  is ready to read cells  151  from the memory  160 . The method  300  performs those steps following this flow point in parallel with those steps following other flow points. 
     The following description is similar to operation following the flow point  320 . 
     At a step  331 , the memory reading element  250  identifies, in response to their location in the memory  160 , packets  113  that are to be sent to output interfaces  112 . 
     At a step  332 , the memory reading element  250  reads the cells  151  for those packets  113  in sequence from their locations in the memory  160  into the reassembly queues  251 . 
     At a step  333 , the memory reading element  250  reassembles packets  113  from those cells  151 . 
     Transmitting Packets 
     At a flow point  340 , the system  100  is ready to transmit packets  113 . The method  300  performs those steps following this flow point in parallel with those steps following other flow points. 
     At a step  341 , reassembled packets  113  are sent to a set of output queues  252 , each of which is associated with a selected output interface  112 . 
     At a step  342 , from each selected output interface  112 , packets  113  are sent to the associated fabric interface element  170  (for the first memory controller  150 ) or to the transmit element  180  (for the second memory controller  150 ). 
     Generality of the Invention 
     The invention has substantial generality of application to various fields in which data is reordered for writing into or reading from a storage device. These various fields include, one or more of, or a combination of, any of the following (or any related fields): 
     Routing packets, frames or cells in a datagram routing network, in a virtual circuit network, or in another type of network. This application could include packet routing systems, frame relay systems, aynchronous transfer mode (ATM) systems, satellite uplink and downlink systems, voice and data systems, and related systems. 
     Queueing packets, frames or cells in a scheme in which different queues correspond to differing quality of service or allocation of bandwidth for transmission. This application could include broadcast, narrowcast, multicast, simulcast, or other systems in which information is sent to multiple recipients concurrently. 
     Operating in parallel using multiple memory banks or related storage devices, or using memory banks or related storage devices that have the capability to perform true parallel operation. 
     Reordering data for processing by multiple components, including either hardware processor components or software components. This application could include reordering of data that is not necessarily fixed length, such as the cells used in the preferred embodiment. 
     Alternative Embodiments 
     Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.