Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1999-05-24
2002-06-04
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S014000, C710S054000, C710S055000
Reexamination Certificate
active
06401147
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 performing diagnostic procedures on queue structures used for storing received data in communication systems.
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. Depending on the specific implementation and/or characteristic of the networking system (i.e., data transfer rate, traffic intensity), buffers must 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 often implemented as queue structures. There are many types of electronic data systems in which queues are used. These include microprocessors, memory transfer systems, airline telephone reservation systems, and packet switched networks. An example of a queue from everyday life is a customer line, at a bank or an airport ticket counter. In most systems, it is desirable that the queues have low latencies so that processing of an entry is not delayed very long due to delays caused by the queues themselves. A low queue latency means that an entry will flow from the entrance to the queue to the exit of the queue quickly, in comparison to queues with higher latencies. One factor that has a significant impact on the latency of a queue is the length, or capacity, of the queue. The greater the capacity of the queue to store entries, the higher the latency of the queue.
In certain systems, a compromise is typically made between the competing factors of latency and capacity in designing the queue size. For example, the network switch typically receives data frames from multiple ports, and cannot process all of the data frames instantaneously to thereby determine where each should be sent. Hence, a queuing arrangement that queues the received data frames provides the network switch enough time to process the received data frames.
It is often difficult to balance the competing factors of latency and capacity in multiport network switches because of the desire to quickly process received data frames with minimal delay that may be introduced by the queue structure. Regardless of the processing speed of the network switch, it is also important that there is sufficient storage capacity to accommodate large numbers of received data frames. A high storage capacity ensures that received data frames will not be discarded, hence avoiding loss of information even during times of high throughput at the switch.
Further complications arise as a result of the ever-increasing pressure to reduce the size of the chips that embody the device that implements the queue structure, or provide extended functionality in the device. Consequently, the amount of real estate, on the chip, that can be dedicated to the queuing function becomes considerably more expensive. This expense is further increased in devices such as multiport network switches, where each port may be required to have its own queue.
The expense associated with on-chip real estate has traditionally been addressed by providing additional storage area external of the chip (i.e., external memory). The external storage area, however, introduces new problems because access to the “on-chip” memory is considerably faster than access to the external memory. Consequently, latency is significantly increased.
Accordingly, a principal problem associated with implementing queue structures is the need to efficiently balance competing factors such as latency and storage capacity.
Another problem associated with implementing queue structures is the inability to effectively minimize latency when a large storage capacity is available.
DISCLOSURE OF THE INVENTION
There is a need to provide a queue structure and a method of queuing that will satisfy both competing interests of low latency and high capacity, that queues entries to a system with low latency, yet still retains the capacity to handle relatively large amounts of entries when necessary.
There is also a need for a queue structure that is capable of minimizing latency regardless of the amount of external storage capacity available to store entries.
These and other needs are addressed by the present invention wherein a queue structure includes a queue overflow engine that minimizes latency by selectively utilizing an external memory area, based on a prescribed threshold value.
In accordance with one aspect of the present invention, a queue structure comprises a first queue area for receiving entries, a second queue area for outputting entries input to the first queue area, a queue overflow engine logically coupled to the first queue area and the second queue area, and an overflow storage area operatively coupled to the queue overflow engine. The first queue area and the second queue areas each include an input portion and an output portion. The queue overflow engine functions to transfer entries from the first queue area to the second queue area using either a trickle mode or an overflow mode, based on a prescribed threshold value. Depending on the specific system, the threshold value used by the queue overflow engine may correspond to the number of entries stored in the first queue area, the number of entries stored in the second queue area, or both.
According to one implementation of the present invention, the overflow mode requires that the queue overflow engine perform a first transfer of entries from the output portion of the first queue area to the overflow storage area. Next, the queue overflow engine performs a second transfer wherein the entries currently stored in the overflow storage area are transferred to the second queue area. Furthermore, the trickle mode requires that the queue overflow engine transfer entries directly from the output portion of the of the first queue area into the input portion of the second queue area.
According to another implementation, the queue overflow engine attempts to transfer entries into the second queue area using only the trickle mode, in order to minimize latency resulting from access to the external memory area. The queue overflow engine thus monitors the number of entries currently stored in the first and second queue areas. If the first queue area is empty, then the queue overflow engine refrains from transferring entries from the overflow storage area until a minimum threshold value is reached in the second queue area. If additional entries are input to the first queue area before the minimum threshold value is reached, then entries are transferred t
Erimli Bahadir
Sang Jinqlih
Yang Edward
Advanced Micro Devices , Inc.
Gaffin Jeffrey
Mai Rijue
LandOfFree
Split-queue architecture with a first queue area and a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Split-queue architecture with a first queue area and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split-queue architecture with a first queue area and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925068