Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-11-29
2004-03-30
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S118000, C711S165000, C713S502000
Reexamination Certificate
active
06715046
ABSTRACT:
FIELD OF THE INVENTION
This invention especially relates to writing to and reading from storage, such as that used in communications and computer systems; and more particularly, the invention relates to reading from and writing to storage, including, but not limited to memory devices, using acknowledged phases of sets of data.
BACKGROUND OF THE INVENTION
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet. For example, a enqueuing component of such a device receives a stream of various sized packets which are accumulated in an input buffer. Each packet is analyzed, and an appropriate amount of memory space is allocated to store the packet. The packet is stored in memory, while certain attributes (e.g., destination information and other information typically derived from a packet header or other source) are maintained in separate memory. A memory interface typically dictates the amount of information written into memory each clock cycle, and typically a packet, especially a large packet, is written to memory over multiple clock cycles. Once the entire packet is written into memory, the packet becomes eligible for processing, and an indicator of the packet is typically placed in an appropriate destination queue for being serviced according to some scheduling algorithm.
The dequeue machine operates in parallel, running an scheduling algorithm to determine which packet should be read from the memory into an output buffer. Once the entire data is read into the output buffer, the packet can be forwarded to a next component or system, and the buffer space it occupied is freed for other packets.
As packets are received at higher rates, then these operations must also be performed at higher rates. The nature of the system and of the large fast memories, which exist in today's market, introduces a problem of ordering in memory accessing. The order of the actual memory accesses is very hard to predict due to various reasons, including the varying nature of traffic and the burstiness behavior of both read and write side, especially as the number of read and write accesses varies.
The characteristics of the external memories imply that for achieving maximum efficiency, most of the memory accesses have to be reordered to avoid conflicts. This means that the order in which they were issued by the enqueue machine to the memory interface is not necessarily the order in which they are actually written to the memory. Switches from read to write and vice versa, should be as infrequent as possible, because switching also causes a penalty in the number of memory accesses. This means that the memory interface should attempt executing as many writes as it can before switching to read and vice versa, and this fact further weakens the correlation between the order of issuing a memory access, and the order of execution. As a result of these and other factors, complex processing must be performed to determine when an entire packet data is actually written to memory and is thus eligible for being enqueued to the appropriate target queue. Similar processing must be performed to determine when the entire packet's data is read, and the memory space can be freed.
New methods and apparatus are needed for efficiently determining when the data of an entire packet is read from or written to storage.
SUMMARY OF THE INVENTION
Methods and apparatus are disclosed for reading from and writing to storage, including, but not limited to memory devices, using acknowledged phases of sets of data. In one embodiment, a phase indication is maintained. A first value of the phase indication is associated with a first plurality of storage requests, and a second value of the phase indication is associated with a second plurality of storage requests. The first and second pluralities of storage requests are forwarded to a storage control component. A first acknowledgement that the first plurality of storage requests have been manipulated is received. In one embodiment, the plurality of storage requests include a write request. In one embodiment, the plurality of storage requests include a read request.
REFERENCES:
patent: 5530851 (1996-06-01), Fortier
patent: 5630075 (1997-05-01), Joshi et al.
patent: 6088734 (2000-07-01), Marin et al.
patent: 6122715 (2000-09-01), Palanca et al.
patent: 6134217 (2000-10-01), Stiliadis et al.
patent: 6230243 (2001-05-01), Elko et al.
patent: 6330645 (2001-12-01), Harriman
patent: 6334171 (2001-12-01), Hill et al.
patent: 6408005 (2002-06-01), Fan et al.
patent: 6466939 (2002-10-01), Lai et al.
patent: 6483841 (2002-11-01), Chang et al.
patent: 6510531 (2003-01-01), Gibbons
patent: 2002/0039370 (2002-04-01), Elliot
Scott Rixner et al., “Memory Access Scheduling,” Proceedings of the 27th Annual International Symposium on Computer Architecture, ACM Press, New York, NY, 2000, pp. 128-138.
Listman Shimon
Shoham Doron
Chace Christian P.
Cisco Technology Inc.
Sparks Donald
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for reading from and writing to storage... 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 reading from and writing to storage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reading from and writing to storage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219384