Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-21
2003-01-07
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395700
Reexamination Certificate
active
06504846
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to communication systems, and more particularly, to a method and apparatus for reclaiming memory buffers used for temporary storage of received data in a communication system.
2. Description of the Related Art
Modern communication systems, such as computer networking systems or communication networks, provide constant transmission of data between end stations and/or intermediate stations such as routers and signal amplifiers. Computer networking systems, such as packet switched networks (e.g., Ethernet networks), often require transmission of data to a single end station or to multiple end stations within the network. The data originates from a user program and is segmented into multiple data frames, and subsequently transmitted in order to simplify processing and minimize the retransmission time required for error recovery. For example, in a conventional e-mail system, a user may desire to send the same e-mail message to four different users that are connected to the e-mail system. Accordingly, the identical data would be directed to multiple end stations.
Packet switched computer networks typically employ a network switch that receives and forwards data frames to individual and/or multiple end stations. The network switch makes forwarding decisions upon receipt of data frames based on information contained in a header of the data frame. For example, if a received data frame is to be transmitted to a number of end stations, the switch must make the forwarding decision to forward the data frame to the ports of the correct end stations. Depending on the specific implementation and/or characteristic of the networking system (i.e., data transfer rate, traffic intensity, etc.), buffers must be provided for temporary storage of the data frames, received by the switch, until forwarding decisions can be made. The buffers used to store the data frames are often implemented as first in, first out (FIFO) queues.
In packet switched networks that utilize buffers to temporarily store data frames prior to transmission to the appropriate end station, it is common for the size of an individual data frame to be larger than the capacity of an individual buffer. Buffers are typically allocated a static amount of memory, hence requiring that multiple buffers be used to store a single frame of data that exceeds the buffer's capacity. Buffering the data as it is received allows, for example, robust error checking to be performed on the data frames, and also permits rate matching between transmitting and receiving ports. When data frames arrives at a network switch, only buffers that are currently available (i.e., “free”) may be used to store the data frames, in order to prevent overwriting of a first data frame by a second data frame prior to transmission. Once the data frames have been transmitted, or is otherwise determined to be no longer necessary, the buffers storing the data frames may be reused to store newly received data frames. In addition, it is possible for buffers to be set aside for storing incoming data frames, but because of error checking or an insufficient amount of data received, the data frames must be discarded. In such circumstances, the buffers must be returned for reuse in order to avoid a potential situation wherein all of the system buffers are improperly set aside to receive data frames that have been discarded.
For purposes of efficiency and continued operation of the network system, it is imperative that buffers be available to store incoming data frames to the extent possible. In addition, the return of the buffers for reuse should be performed as quickly as possible after the buffers are no longer needed.
In systems that employ multiple buffers to store a single data frame, the network switch monitors the transmission of the data frame, and begins the process of reclaiming the individual buffers that store the data frame after the entire data frame has been transmitted. If multiple copies of the same data frame must be transmitted, then the network switch waits until all copies of the data frame have been transmitted before beginning the process of reclaiming the buffers used to store the data frame. Hence, different reclaiming procedures would be more efficient depending on whether a single copy of the frame is transmitted, or multiple copies of the frame are transmitted, and whether the data frame is stored in a single frame buffer or multiple frame buffers.
Accordingly, a primary disadvantage associated with current methods of transmitting data in communication systems, such as a packet switched computer networking system, is the amount of time required to free the buffers that are used to store incoming data frames, once the data frames have been transmitted.
Another disadvantage associated with current methods of transmitting data in communication systems is the inefficiency associated with utilizing the same circuitry (or method) to reclaim buffers regardless of whether a data frame is stored in a single frame buffer or multiple frame buffers.
DISCLOSURE OF THE INVENTION
There is a need for an arrangement and a method for quickly reclaiming buffers that store data frames upon transmission of the data frames so that the buffers can be available to store newly received data frames.
There is also a need for an arrangement and method that distinguishes between single and multiple buffer data frames, and efficiently reclaims buffers depending on whether a data frame is stored in one buffer or multiple buffers.
These and other needs are addressed by the present invention, wherein a multiport switch determines whether a particular data frame is stored in one frame buffer or multiple frame buffers, and places the corresponding frame pointer into either a reclaim queue or a free buffer queue based on such a determination.
In accordance with one aspect of the present invention, an apparatus for reclaiming frame buffers used to store data frames received by a network switch comprises a multicopy queue, a free buffer queue, and a multicopy circuit. The multicopy queue stores entries corresponding to received data frames which must be transmitted to multiple output ports of the network switch. Each entry queued by the multicopy queue includes a frame pointer that addresses a location in memory where frame buffers for storing the received data frames are located. The free buffer queue stores frame pointers that identify locations in the memory where reclaimed frame buffers are located. Each reclaimed frame buffer is available for storing newly received data frames. The multicopy circuit retrieves entries from an output portion of the multicopy queue, and determines if all copies of a received data frame have been transmitted by the multiple output ports. If all copies of the received data frame have been transmitted, then the multicopy circuit reclaims one or more frame buffers based on the size of the received data frame.
The present apparatus efficiently reclaims frame buffers by determining whether a received data frame is stored in one frame buffer or multiple frame buffers. If it is determined that only one frame buffer is used to store the data frame, then the multicopy circuit may place the frame pointer directly into the free buffer queue. If, however, multiple frame buffers are used to store the data frame, then the multicopy queue places the frame pointer in the reclaim queue so that the reclaim queue may use the frame pointer to access the first frame buffer, and walks a linked list of frame buffers in order to free all of the frame buffers used to store the data frame.
According to one specific implementation of the present invention, the multicopy circuit includes a searchable memory area for storing values corresponding to the number of copies of each received data frame that must be transmitted, and a search engine for searching the searchable memory area and updating the values stored therein to reflect the current number of copies of each received data frame that remain
Erimli Bahadir
Yu Ching
Zhuang Xiaohua
Advanced Micro Devices , Inc.
Kizou Hassan
Odland David
LandOfFree
Method and apparatus for reclaiming buffers using a single... 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 using a single..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reclaiming buffers using a single... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3021855