Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-12-18
2001-05-15
Marcelo, Melvin (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C711S173000
Reexamination Certificate
active
06233244
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data storage, and more particularly, to method and apparatus for reclaiming buffers used to store data to allow the buffers to be re-used to store different data.
BACKGROUND ART
In many systems in which is received and forwarded, such as packet switched networks (e.g., Ethernet networks), memory buffers are used to temporarily store data prior to forwarding of the data. For example, in a packet switched network, a frame of data may be received at a network switch, which will forward the frame to an appropriate port, and is loaded into individual buffers as the data is received at the switch. It is common for the size of the frame to be larger than the capacity of an individual buffer, so that multiple buffers to be used to store a single frame of data.
Buffering the data as it is received allows robust error checking on the frame to be performed, and also permits rate matching between transmitting and receiving ports, among other features. When a frame of data arrives at a switch, only buffers that are currently available (or “free”) are used to store the data, so that data is not overwritten before the data is transmitted. Once the data has been transmitted, or is otherwise no longer needed, the buffers storing the data may be reused to store data of a new frame. Also, it is possible for buffers to be set aside for storing data of an incoming frame, but error checking or an insufficient amount of data received may cause the frame to be discarded. In circumstance as well, the buffers should be returned for reuse.
For purposes of efficiency, and to assure that buffers are available for storage of incoming frames to the extent possible, the return of the buffers for reuse should be performed as quickly as possible after they are no longer needed. In systems allowing for multiple buffers to store a single frame, after the entire frame is transmitted, the switch will recognize the transmission of the frame and begin the process of reclaiming the individual buffers that store the chain. If multiple copies of the same frame are transmitted, then the switch waits until all of the copies of the frame are transmitted before beginning the process of reclaiming the buffers that stored the frame. Hence, the same reclaiming procedure would be used whether a single copy of the frame is transmitted, or multiple copies of the frame are transmitted.
Another concern in systems using buffers to store data in a memory is the generation of the pointers to store those buffers. The buffer pointers, which point to the locations in memory where the buffers are located, may be generated upon startup of the system and loaded into a buffer pool, from where they are retrieved when the buffers are used to store data. After reclaiming the buffers following their use, the buffer pointers are returned to the buffer pool. Where the system employs a large number of buffers, this initial generation and loading of buffer pointers into the buffer pool upon startup of the system is a relatively time-consuming process.
SUMMARY OF THE INVENTION
There is a need for an arrangement and a method of reclaiming buffers in a fast manner upon the transmission of data from buffers in a memory so that the buffers can be available for reuse to store other data.
This and other needs are met by the present invention which provides an arrangement for reclaiming buffers that store frames for a network switch in a packet switched network. The arrangement comprises a reclaim queue configured to queue frame pointers that point to a location in a buffer memory of a first buffer in which a frame is stored. A searchable first memory stores a count of the number of copies of a frame to be transmitted from the network switch. A free buffer pool is configured to queue buffer pointers that point to locations of buffers in a buffer memory. A buffer manager receives a frame pointer of a frame for transmission of a copy of that frame and searches the first memory to determine if transmission of this copy would be the last copy of that frame to be transmitted. If this transmission would be the last copy, the buffer manager causes the transmission of that last copy of that frame from the network switch and places the buffer pointer of each buffer that stores the frame into the free buffer pool after the transmission of the contents of that buffer.
One of the advantages of the present invention is that, when it is possible to determine that the next copy to be transmitted of a frame is the last copy that is to be transmitted, the buffers which store the frame are reclaimed after the contents of each buffer are transmitted. This returns the buffers much faster for reuse than waiting until an entire frame has been transmitted, then determining that no more copies of that frame are to be sent, and only then begin reclaiming the buffers that stored the frame.
The earlier stated need and others are met by another embodiment of the present invention which provides a method of reclaiming buffers, which store a frame, following transmission of the frame from a network switch. In the method of the invention, an attempt is made to determine if a copy of the frame to be transmitted is the last copy of the frame to be transmitted. If it is determined that the copy of the frame to be transmitted is the last copy of the frame to be transmitted, the buffers that store the frame are reclaimed after the contents of each buffer is transmitted from the network switch. However, if it is determined that the copy of the frame to be transmitted is not the last copy of the frame to be transmitted, an indication of the transmission of the copy of the frame is queued after the frame is transmitted from the network switch. Also, if it is not determinable whether the copy of the frame to be transmitted is the last copy of the frame to be transmitted, an indication of the transmission of the copy of the frame is queued after the frame is transmitted from the network switch.
One advantage of this embodiment of the present invention is that an attempt is made to determine the status of a transmission of a frame, i.e., whether it is the last copy. If it can be determined, then a speeding up of the reclaiming process is achieved by reclaiming the buffers immediately after the contents of each buffer are transmitted. This is allowed since it is known that the data in the buffers will not be needed to send another copy of that frame. However, when it is not the last copy, or if it cannot be determined that it is the last copy, then an indication of the transmission is queued. This indication can be used later in keeping a count of the number of copies that have been transmitted. Hence, under certain circumstances, present invention speeds up the reclaiming process.
In certain embodiments of the invention, it is also determined whether the only a single copy of the frame is to be sent, or multiple copies. With such embodiments, a speeding up process for reclaiming buffers when during the transmission of the single copy is possible, since it is known that the contents of the buffers will not be needed for transmission of other copies of that frame. Hence, the reclaiming of the buffers of a single copy of a frame may be performed in the same manner as the last copy of a multiple copy frame (when it is known to be the last copy of the multiple copy frame).
There is also a need for an arrangement and method of generating buffer pointers upon system startup that is less time-consuming upon startup.
This and other needs are met by the present invention which provides an arrangement for making buffers available in a memory for storing data. This arrangement includes a free buffer pool configured to store a plurality of buffer pointers. Each buffer pointer points to a different location in memory at which an associated free buffer, which is a buffer currently available for storing data, is located. Reclaim circuitry is provided that returns buffer pointers of buffers that have become available for storing data to the free
Egbert Chandan
Erimli Bahadir
Runaldue Thomas J.
Advanced Micro Devices , Inc.
Kwoh Jasper
Marcelo Melvin
LandOfFree
Method and apparatus for reclaiming buffers 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 reclaiming buffers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reclaiming buffers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539903