Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-03-30
2004-06-29
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S167000, C711S005000, C370S412000, C370S413000, C710S054000
Reexamination Certificate
active
06757791
ABSTRACT:
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.
REFERENCES:
patent: 4131767 (1978-12-01), Weinstein
patent: 4161719 (1979-07-01), Parikh et al.
patent: 4316284 (1982-02-01), Howson
patent: 4397020 (1983-08-01), Howson
patent: 4419728 (1983-12-01), Larson
patent: 4424565 (1984-01-01), Larson
patent: 4437087 (1984-03-01), Petr
patent: 4438511 (1984-03-01), Baran
patent: 4439763 (1984-03-01), Limb
patent: 4445213 (1984-04-01), Baugh et al.
patent: 4446555 (1984-05-01), Devault et al.
patent: 4456957 (1984-06-01), Schieltz
patent: 4464658 (1984-08-01), Thelen
patent: 4499576 (1985-02-01), Fraser
patent: 4506358 (1985-03-01), Montgomery
patent: 4507760 (1985-03-01), Fraser
patent: 4532626 (1985-07-01), Flores et al.
patent: 4644532 (1987-02-01), George et al.
patent: 4646287 (1987-02-01), Larson et al.
patent: 4677423 (1987-06-01), Benvenuto et al.
patent: 4679189 (1987-07-01), Olson et al.
patent: 4679227 (1987-07-01), Hughes-Hartogs
patent: 4723267 (1988-02-01), Jones et al.
patent: 4731816 (1988-03-01), Hughes-Hartogs
patent: 4750136 (1988-06-01), Arpin et al.
patent: 4757495 (1988-07-01), Decker et al.
patent: 4763191 (1988-08-01), Gordon et al.
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckberg, Jr. et al.
patent: 4771425 (1988-09-01), Baran et al.
patent: 4819228 (1989-04-01), Baran et al.
patent: 4827411 (1989-05-01), Arrowood et al.
patent: 4833706 (1989-05-01), Hughes-Hartogs
patent: 4835737 (1989-05-01), Herrig et al.
patent: 4879551 (1989-11-01), Georgiou et al.
patent: 4893306 (1990-01-01), Chao et al.
patent: 4903261 (1990-02-01), Baran et al.
patent: 4922486 (1990-05-01), Lidinsky et al.
patent: 4933937 (1990-06-01), Konishi
patent: 4960310 (1990-10-01), Cushing
patent: 4962497 (1990-10-01), Ferenc et al.
patent: 4962532 (1990-10-01), Kasirai et al.
patent: 4965772 (1990-10-01), Daniel et al.
patent: 4970678 (1990-11-01), Sladowski et al.
patent: 4979118 (1990-12-01), Kheradpir
patent: 4980897 (1990-12-01), Decker et al.
patent: 4991169 (1991-02-01), Davis et al.
patent: 5003595 (1991-03-01), Collins et al.
patent: 5006982 (1991-04-01), Ebersole et al.
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5020058 (1991-05-01), Holden et al.
patent: 5033076 (1991-07-01), Jones et al.
patent: 5054034 (1991-10-01), Hughes-Hartogs
patent: 5059925 (1991-10-01), Weisbloom
patent: 5072449 (1991-12-01), Enns et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5095480 (1992-03-01), Fenner
patent: RE33900 (1992-04-01), Howson
patent: 5115431 (1992-05-01), Williams et al.
patent: 5128945 (1992-07-01), Enns et al.
patent: 5136580 (1992-08-01), Videlock et al.
patent: 5166930 (1992-11-01), Braff et al.
patent: 5199049 (1993-03-01), Wilson
patent: 5206886 (1993-04-01), Bingham
patent: 5208811 (1993-05-01), Kashio et al.
patent: 5212686 (1993-05-01), Joy et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5226120 (1993-07-01), Brown et al.
patent: 5229994 (1993-07-01), Balzano et al.
patent: 5237564 (1993-08-01), Lespagnol et al.
patent: 5241682 (1993-08-01), Bryant et al.
patent: 5243342 (1993-09-01), Kattemalalavadi et al.
patent: 5243596 (199
Dan Yie-Fong
O'Grady Robert
Tran Sonny N.
Wilford Bruce
Cisco Technology Inc.
Gossage Glenn
Hickman Palermo & Truong & Becker LLP
LandOfFree
Method and apparatus for reordering packet data units in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reordering packet data units in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reordering packet data units in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3347893