Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-06-20
2004-04-27
Nguyen, T (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C370S351000, C370S360000, C370S395100, C211S153000, C211S101000, C211S201000, C211S201000
Reexamination Certificate
active
06728857
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to computer systems and more particularly to a method and system for storing data in memory.
BACKGROUND OF THE INVENTION
Telecommunications is becoming increasingly important in today's society. The increased use of the Internet allows people to communicate data between home or business to remote locations. One format for communicating data is asynchronous transfer mode (ATM) format. Many other formats also exist.
Among other criteria, when communicating information according to ATM, cells of data of a specified size are transmitted from one location to another. Often times the cells are stored in memory at an intermediate location before being transferred to the desired destination. An example of such a procedure is the use of an ATM switch at a telecommunications central office for switching data originating from a user's home over the Internet to an appropriate destination over an Internet backbone. Such cells are often stored in a sequential manner such that data that are received first by the memory are distributed first. To effect such sequential transmission, queues are formed that designate which cells are transferred first. In some implementations, a queue exists for each destination.
Linked lists are used in some systems that store queues of ATM cells to facilitate such sequential transmissions. Traditionally, a linked list includes two entries. A first entry in the linked list specifies a corresponding memory location in data memory in which the corresponding data cell is stored. The second entry in the linked list stores the address of the next memory location in the linked list.
A problem with such an approach is that memory is required to store these addresses in the linked list. Additionally, reading and writing the addresses stored in the linked list contribute to switch latency.
SUMMARY OF THE INVENTION
Therefore, a need has arisen for a method and system for storing data. The present invention provides a method and system for storing and retrieving data that addresses disadvantages of prior systems and methods.
According to one embodiment of the invention, a method for retrieving data stored in a plurality of memory locations in data memory includes receiving the address of a first memory location in the data memory storing a first portion of the data and obtaining, from a location in a link memory specified by the address of the first memory location, a second address of a second memory location in the data memory storing a second portion of the data. The method also includes retrieving the first and second portions of the data in the first and second memory locations in the data memory.
According to another embodiment of the invention, a method for storing data in a plurality of memory locations in data memory includes storing a first portion of the data in a memory location in data memory having a first address and storing a second address in a memory location in link memory specified by the first address. The method also includes storing a second portion of the data in a memory location in data memory having the second address.
Some embodiments of the invention provide numerous technical advantages. Other embodiments may realize some, none, or all of these advantages. For example, according to one embodiment, a memory system is provided with reduced memory requirements. Such a system allows storing of data indexed by a linked list that does not require additional memory to designate the address of the location in data memory in which the data is stored. Additionally, in some embodiments, such an approach reduces the amount of logic needed to control the data memory. Furthermore, the number of pins required may be reduced by implementing such a linked list. Because the address in data memory in which a desired portion of data is stored does not need to be read from a linked list, reading and writing data may occur more rapidly. This reduces switch latency.
Other advantages may be readily ascertainable by those skilled in the art and the following FIGURES, description, and claims.
REFERENCES:
patent: 5365519 (1994-11-01), Kozaki et al.
patent: 5535197 (1996-07-01), Cotton
patent: 5557607 (1996-09-01), Holden
patent: 5570348 (1996-10-01), Holden
patent: 5583861 (1996-12-01), Holden
patent: 5893162 (1999-04-01), Lau et al.
patent: 6111880 (2000-08-01), Rusu et al.
patent: 6151301 (2000-11-01), Holden
patent: 6430666 (2002-08-01), Roth
U.S. patent application titled “Method and System for Multicasting”; Filed: Jun. 20, 2001; application Ser. No.: 09/885,905 (25 pages—Figures 1/3).
U.S. patent application titled “Method and System for Testing Linked List Integrity”; Filed: Jun. 31, 2001; application Ser. No.: 09/920,270 (33 pages—Figures 1/6).
Baker & Botts L.L.P.
Cisco Technology Inc.
Nguyen T
LandOfFree
Method and system for storing and retrieving data using... 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 system for storing and retrieving data using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for storing and retrieving data using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220186