Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-21
2003-09-09
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S413000, C370S414000, C370S415000, C370S395700, C370S395710, C370S395720, C710S052000, C710S056000, C711S104000, C711S105000, C711S149000, C711S170000
Reexamination Certificate
active
06618390
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 maintaining free buffer information.
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 switch makes forwarding decisions upon receipt of data frames based on information contained in a header of each 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.
Data frames must comply with certain transmission standards that allow transparent interpretation by various networks such as, for example, the Ethernet (IEEE 802.3) network. The network standard outlines the parameters and requirements (e.g., media type, data structures, etc.) that must be used to ensure a level of reliability and quality of service. During normal operation, a large quantity of data must be exchanged though a network. When data is received by a network switch, it is forwarded to a network station specified by a header contained in the data frame.
Depending on the specific implementation and/or characteristic of the networking system (i.e., data transfer rate, traffic intensity), buffers must normally be provided for temporary storage of the data frames received by the switch, until forwarding decisions can be made. Without the use of buffers, there is a great likelihood that data frames will be lost, hence requiring retransmission and reducing the overall efficiency of the system.
The buffers used by the switch to store the data frames are usually accessed using pointers that address the location of specific buffers in a storage location such as a Random Access Memory (RAM) located external of the network switch. The switch then stores the pointers in a queue structure that can be accessed anytime a data frame must be stored in memory. One method of accessing the buffers in the external memory requires that the pointers be decodable into unique address locations for corresponding buffers. For example, each pointer can be divided into two portions that address specific locations in the external memory where the buffer is located.
When data frames arrive 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 are 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. It is therefore imperative that sufficient buffer pointers are available to address buffers for storing received data frames.
The queues used to store buffer pointers are typically maintained on the chip itself (i.e., referring to the chip on which the switch is implemented) in order to minimize latency. The expense associated with on-chip real estate may be addressed by providing a storage area external of the chip (i.e., external memory). An external storage area, however, introduces new problems because access to the “on-chip” memory may be considerably faster than access to the external memory. Consequently, latency may be significantly increased when information must be stored in, or retrieved from, an external memory. Furthermore, providing an external storage area requires complex logic to provide high-priority access to the external memory, and increases the bandwidth for accessing the external memory from the chip.
Accordingly, a problem associated with communication systems, such as computer networks, is the amount of on-chip real estate required on a network switch to maintain an adequate quantity of buffer pointers for addressing buffers that are available to store received data frames. Another problem associated with such communication systems is the complexity of the logic that must be incorporated to provide priority access to the external memory when there is insufficient on-chip storage. Still another problem is the increased latency and bandwidth that results when access to the external memory is required.
DISCLOSURE OF THE INVENTION
There exists a need for an arrangement that is capable of efficiently maintaining information for accessing buffers to store data frames within a communication system such as a computer network.
These and other needs are addressed by the present invention wherein a random access memory is provided on the network switch for storing values that indicate the available buffers for storing received data frames.
In accordance with one aspect of the present invention, an arrangement is provided for maintaining free buffer information for a network switch. The arrangement includes a first random access memory (RAM), an input logic, and an output logic. The first RAM is located on the network switch and functions to store values that indicate whether or not free buffers, located in a second RAM, are available for storing received data frames. The input logic places values in the first RAM to indicate which free buffers are available for storing the data frames. The output logic searches the first RAM and locates values that indicate available free buffers in the second RAM. The output logic then generates buffer pointers that address the locations of the free buffers in the second RAM. The present arrangement advantageously reduces the amount of storage space required to store buffer pointers by utilizing a RAM that stores only an indication of whether free buffers are available for use. Buffer pointers are then created only when necessary to address buffers for storing data frames. Hence, the overall amount of storage space required to maintain free buffer information on the switch is reduced. Furthermore, latency is reduced because a prescribed number of buffer pointers can be stored on the switch, rather than providing a large capacity storage area located in an external memory.
According to another aspect of the invention, a method of maintaining free buffer information for a network switch comprises the steps: placing values, in a first RAM located on the network switch, that indicate the availability of free buffers located in a second RAM, the free buffers being usable by the network switch to store received data frames; searching the first RAM to locate values that indicate available free buffers in the second RAM; and generating buffer pointers that address the locations of the free buffers in the second RAM, the buffer pointers being available for use by the network switch to locate free buffers for storing received data frames. The present method advantageously reduces latency by storing values that indicate availability of free buffers and generating buffer pointers when necessary, rather than providing a large capacity st
Erimli Bahadir
Nandakumar Vallath
Advanced Micro Devices , Inc.
Nguyen Van Kim T.
Vanderpuye Kenneth
LandOfFree
Method and apparatus for maintaining randomly accessible... 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 maintaining randomly accessible..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maintaining randomly accessible... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3014598