Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-05-12
2003-07-08
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S004000, C710S033000, C710S054000, C710S055000, C710S056000
Reexamination Certificate
active
06591317
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data communications networks and more particularly relates to a queue incorporating a duplicate counter per entry.
BACKGROUND OF THE INVENTION
Currently, the number of data networks and the volume of traffic carried by these networks is expanding at an ever increasing rate. The network devices used to construct these networks generally consist of specialized hardware designed to move data at very high speeds. Typical networks, such as Ethernet based networks, are mainly comprised of end stations, Ethernet hubs, switches, routers, bridges and gateways. ATM networks are constructed with similar network devices adapted to carry ATM traffic, e.g., ATM capable end stations, edge devices and ATM switches.
With the ever increasing user demand for faster and faster data communications, network devices have had to perform at higher and higher speeds. A primary function of many network devices is to receive frames (packets, cells, etc.) at one or more ingress ports, and forward the frame to an appropriate egress port. Accomplishing this requires that the network device make a forwarding decision about the received frame. This requires processing resources and memory resources to store the frame until the forwarding decision is complete and the packet is placed onto the appropriate one or more output ports.
In particular, when a frame (note that the same applies to cells and packets as well), arrives at a switch, for example, typically only its header is examined and a forwarding decision is made therefrom. The application of the decision to the frame requires that the entire frame be queued to an output port. In some implementations, the frame is not scheduled for transmission until the complete frame is successively received.
In prior art store and forward schemes, the frame is not queued into the output port until the entire frame is received. The forwarding decision is made in an input server after receipt of the header portion. The frame, however, is not queued to an output port until the entire frame is received. Thus, the frame header and the forwarding result must be stored until the complete frame is received.
In such devices, it is common to place entries in a queue whose entries are processed asynchronously at a later time. The entries may comprise the entire received frame or may comprise portions of a frame such as the frame header. For example, a network device may have a learning queue for storing information from received frames such as the header or the MAC source address that is unknown so that the software will read it at a later time and update the internal forwarding tables. In operation, a frame enters the device and the source address is used as a lookup index to the forwarding table. An entry is placed in the learn queue when the MAC source address extracted from the frame does not appear in the hardware tables or does appear but with the wrong information. A software process asynchronously processes the entries placed in the queue whereby the MAC source address is thus learned.
Consider the case wherein a frame is received that does not have an associated forwarding decision. In prior art systems, once it is determined that a MAC source address is to be learned, it is pushed into the learning queue even if the same entry is already present in the queue but has not yet been processed. If, however, many frames with the same source address are received before the software processes the learning queue, then the frame will be entered over and over again into the learning queue. Additional frames received before the first entry is processed are written into the queue. This effects the utilization of the queue, lowering it considerably. It also causes processing time to be spent unnecessarily on all the similar entries in the queue.
Moreover, in the event a station sends a burst of traffic incorporating many frames having the same MAC source address, the MAC source address may be pushed numerous times onto the learning queue before the software has an opportunity to process it.
SUMMARY OF THE INVENTION
The present invention solves the problems associated with the prior art by providing a queue having a ‘duplicate’ counter associated with each entry. Data to be written to the queue is not automatically stored. Rather, before data is placed in the queue, the queue is searched for an entry matching the data to be written. If a match is found, the duplicate counter associated with the entry is incremented. Further, if a match is found and the data stored therein is inconsistent with the current data, the contents of the queue are updated and the duplicate counter associated with the entry is reset to one.
If a match is not found, the data is written to the queue and the duplicate counter associated with the entry is initialized to one. In accordance with the present invention, duplicate entries are not entered into the queue in the event an identical entry already exists. In this manner, the utilization of the queue is greatly increased and the queue size required is reduced significantly.
Optionally, the duplicate entry counter may be read periodically and alternative processing performed on the entry in the event the duplicate counter value exceeds a predetermined threshold. In addition, the value of the duplicate counter may optionally be used to determine priority among the entries in the queue.
It is appreciated that the present invention is particularly suitable in cases where the number of required entries is relatively small, i.e. 1 to 100 entries. This permits an easier implementation of the compare operation whereby a new entry to be entered into the queue is compared with all the existing entries in the queue. Note, however, that queues with a larger number of entries may be constructed in accordance with the present invention using standard Content Addressable Memory (CAM) devices.
There is thus provided in accordance with the present invention a queue comprising a plurality of storage locations, each storage location adapted to store an entry, a plurality of duplicate counters, each duplicate counter associated with a different storage location and processing means operative to search, for each entry to be written to the queue, the plurality of storage locations for a matching entry previously written to the queue, and if a match is found, increment the duplicate counter associated with the matching entry, and if a match is not found, store the entry to be added in an unused storage location and initializing to one a duplicate counter associated with the entry to be added.
There is also provided in accordance with the present invention a learning queue for use by software means in a network device in learning the associations between Media Access Control (MAC) source addresses and corresponding ports in the device comprising a plurality of storage locations, each storage location adapted to store an entry including a MAC source address and corresponding port, a plurality of duplicate counters, each duplicate counter associated with a different storage location and a queue control circuit operative to search the plurality of storage locations for an entry having the same MAC source address as the MAC source address to be learned, and if a match is found, increment the duplicate counter associated with the matching entry, and if a match is not found, store the entry to be learned in an unused storage location and initializing to one a duplicate counter associated with the entry to be learned.
REFERENCES:
patent: 5525982 (1996-06-01), Cheng et al.
patent: 6026505 (2000-02-01), Hedberg et al.
patent: 6170034 (2001-01-01), Weston-Lewis et al.
patent: 6252877 (2001-06-01), Kozaki et al.
ATM Practical Implementations Here and Now, 3COM Corporation, 1996.
Bronstein Zvika
Schzukin Golan
Shimony Ilan
3Com Corporation
Farooq Mohammad O.
Gaffin Jeffrey
Sutton Paul J.
Zaretsky Howard
LandOfFree
Queue incorporating a duplicate counter per entry does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Queue incorporating a duplicate counter per entry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue incorporating a duplicate counter per entry will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3090111