Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-12-21
2004-10-05
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
Reexamination Certificate
active
06801991
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the data storage in buffers, and more particularly to a method and apparatus for partitioning an active buffer without loss of data stored in the buffer.
BACKGROUND OF THE INVENTION
Buffer storage is a common element in computer systems and data networks. A computer system buffers data as it awaits service by a resource. For instance, a printer cannot process data at the same rate that it is provided by the processor, so the data is buffered until the printer is ready to process it. A data network requires buffers to hold data as it awaits access to a network processor. For example, network switches typically include an input buffer on each input line and an output buffer on each output line, with the switch fabric interposed between them. The input buffers store packets as they arrive on the input lines while the packets contend for service by the switch. The input buffer size is dependent on the switch capacity and the characteristics of the data network. But once the input buffer size is established, it is not easily modified, especially while the system is operational. Similarly the output buffers store output data traffic from the switch while it contends for access to the output line. Situations may develop where data traffic reaches an unusually high level, at which time it may be necessary for the input or the output buffer to drop one or more packets. This results in network inefficiency as the dropped packets must be resent from the data source.
Typically, buffers associated with network processors are implemented by logically segmenting a single memory space in the network processor. This memory space is partitioned to form multiple logical buffer areas, which are then assigned to serve a required role, such as an input buffer or an output buffer. In certain applications these buffers operate on a first-in-first-out (FIFO) basis and comprise a linear array of memory locations. In a FIFO buffer the next packet or block that is transferred into the network processor is the most recent packet that arrived at the buffer. According to the prior art, FIFO buffers are not resizable while data is present in the buffer. Therefore the data traffic must be halted to resize the buffer.
One common prior art buffer storage technique that allows dynamic buffer repartitioning or resizing uses link lists that identify the memory storage spaces that comprise a logical buffer. The entire memory space is partitioned into equal-size allocation units, and each one is uniquely identified, according to the allocation unit's first and last address within the memory space. An allocation manager assigns allocation units to individual logical buffers. Most logical buffers comprise more than one allocation unit and thus the allocation manager creates a list of the allocation units within each buffer. Further, the lists are linked within the allocation manager to form an ordered chain of allocation units in the logical buffer. Once the linked-lists are created, the allocation manager offers the flexibility to change the logical buffers sizes by adding or deleting allocation units to a logical buffer and correspondingly changing the linked-lists. When a new allocation unit is added to the linked list the previous final linked list entry now has to be linked to the new allocation unit. When data is transmitted from the logical buffer, it is always transmitted from the first buffer location (according to the definition of a FIFO buffer). The allocation unit is removed from the linked list and the new first allocation unit of the buffer is now the allocation unit to which the deleted unit was linked.
One disadvantage of linked lists is the additional storage space required to store the link list itself. Because access to the logical buffer space requires the accessing device to follow the linked list for that buffer, a certain latency time is inherent in reading from or writing to the logical buffer. System performance may be excessively degraded if there are multiple accesses to a logical buffer with a long linked list, as time will be expended chasing the linked list and the desired access speeds may therefore not be attainable. Also, the time required to access the list may make it difficult to timely add and remove entries from the linked list as the buffer allocation units are changed.
Another prior art approach to buffer management is simply using a dedicated storage area for each logical buffer. The storage space is sized to accommodate the expected buffer load and is not expandable nor contractible during operation. This technique can add considerable cost and space requirements to the system architecture. It also does not provide an efficient use of memory storage, as some logical buffers may be considerably and frequently under utilized, and further, the buffers cannot be resized while data is present within the buffer.
BRIEF SUMMARY OF THE INVENTION
The present invention presents a technique for relocating and resizing (also referred to as repartitioning) one or more logical buffers that comprise a memory space. The buffers are generally of different sizes and may be contiguous within the memory space. If there are no empty memory locations between two logical buffers, then one or more of the buffers may be moved so that another buffer can be expanded into the vacated locations. Logical buffer expansion can involve either raising the top memory location in the buffer to a higher memory location, or lowering the base memory location to a lower memory location, both of which require the availability of contiguous vacant memory space. Also, both the top and base memory locations can be raised/lowered. The entire logical buffer can be moved to a different area within the memory space by assigning new top and base locations within the memory space. However, the order of the buffers within the memory space cannot be changed. Essentially, the buffer can be grown to include vacant space at either end or shrunk to release vacant space at either end.
The buffers operate on a first-in-first-out (FIFO) basis, with a read address pointer indicating the next memory location from which data is to be read and a write pointer indicating the next memory location to which data is to be written. The read and write address pointers are incremented by one memory location after their respective operation has been completed. When a pointer reaches the top buffer memory location, it wraps back to the base memory location.
To move or resize a buffer according to the present invention, if certain conditions are satisfied (as discussed below), the base and the top memory addresses are changed to the requested or new base and/or requested or new top addresses to effectuate a move or resizing of the logical buffer. Several possible scenarios can arise. The logical buffer expands upwardly if the top address is modified to include memory space beyond the current top address. As the read and write pointers increment, they will move beyond the former top memory address to the new top memory address, after which they wrap back to the base location. If only the base address is modified by the addition of contiguous memory locations below the base location, the logical buffer will expand downwardly. Once the read and the write pointers reach the top memory address they will wrap back to the new base location. If both the top and base memory locations are modified so that contiguous memory locations are added to the buffer both above and below, then both of the processes as described above are executed. Thus according to the teachings of the present invention, the logical buffer can be expanded or contracted from either the top or base memory location, or from both memory locations. Note that during these move processes, either above, below or both, the data in the buffer is not moved to a different storage location. Only the top and base memory locations, that is, the boundaries of the buffer are expanded (or contracted), to increase the buffer size to a
Koob Christopher
Moller Hanan Z.
Sonnier David P.
Agere Systems Inc.
Ellis Kevin L.
LandOfFree
Method and apparatus for buffer partitioning without loss of... 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 buffer partitioning without loss of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for buffer partitioning without loss of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3312606