Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-02-18
2003-03-11
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S053000, C710S054000, C710S055000, C710S056000, C710S057000
Reexamination Certificate
active
06532503
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a descriptor based memory queuing system for transmitting data packets to one or more transmit ports in a device of a computer network, and in particular to a system where lost buffers can be detected.
BACKGROUND OF THE INVENTION
Many computer network devices, such as bridges, routers, switches and/or hubs, receive data packets and must then forward these packets to one or more transmit ports. The determination of which transmit ports a particular packet is to be sent to, is performed by the higher logic of the network device and is already well known to those skilled in the art. The speed at which each transmit port can send out data packets depends on the speed of the connection, the speed of the receiving port and other factors that can change for each port. Also a data packet can be sent to more than one port at a time, in a process known as multicasting, broadcasting and flooding.
Therefore it is important that the status of the individual transmit ports be closely coordinated with the presence of data packets which are to be sent out on those ports. This can be done using transmit queues for each transmit port and copying a pointer or descriptor into the proper transmit queue which points to the address of a buffer in a main data memory which stores the data packet.
A problem in this descriptor queuing scheme is the loss of buffer descriptors. Generally, these problems result from, logic errors in the buffer descriptor management. Lost buffers is potentially a serious problem preventing full utilization of the main memory. In prior art systems, lost buffers can exist in perpetuity or until a full system reset. Also the number of lost buffers tend to increase with time, causing an increasing under utilization of the device and continual degradation of the network.
SUMMARY AND OBJECTS OF THE INVENTION
It is a primary object of the present invention to rapidly detect lost buffers, and prevent network degradation. It is also an objective to then place the buffers back in service without having to restart the entire network device, particularly when queuing is implemented in hardware and can not be easily corrected if there is a fault in the design.
The present invention accomplishes this object by providing a main data memory in the network device. The main data memory includes a plurality of buffers for storing data packets. A plurality of descriptors, or pointers, point to the individual buffers. A descriptor free pool includes a list of the descriptors in the free state.
When the system receives a data packet, it takes one of the descriptors from the descriptor free pool and stores the data packet in the buffer of the main memory as pointed to by that descriptor.
The system, and more particularly a queue control logic, places a copy of the descriptor in one or more of the plurality of transmit queues of which the queue control logic has previously determined the data packet should be sent out on.
The first embodiment of the invention provides two sets of counters to track buffer descriptors. One set of counters tracks the total number of free and active descriptors. The second set of counters tracks the total number of copies of each active descriptor.
When a descriptor is removed from the free pool, the Free Pool Entry Count is decremented. Similarly, when a descriptor is placed back on the Free Pool, the Free Pool Entry Count is incremented.
There is a one for one correspondence between a Reference Memory Location and each buffer/descriptor. Descriptor Reference Memory stores the status of each descriptor and the number of copies of each descriptor.
When a descriptor is placed on one or more transmit queues, the Reference Memory Entry Count is incremented. The descriptor specific Reference Memory location is updated, state is changed from free to active and the copy count indicates the number of transmit queues which have copies of the descriptor. The copy count is also added to the Transmit Queue Elaborated Count and the Reference Memory Elaborated Count.
When a descriptor is removed from a transmit queue, the Transmit Queue Elaborated Count is decremented. When the data associated with the descriptor has been sent to the destination port, the Reference Memory Elaborated Count is decremented as is the descriptor specific count in Reference Memory. When the descriptor specific count decrements to zero, the descriptor state is changed from active to free, the Reference Memory Entry Count is decremented and the descriptor is returned to the Free Pool.
The second embodiment of the invention provides per port descriptor status as well as overall activity status for each buffer descriptor location in Reference Memory. The status of the descriptors is stored in a descriptor reference memory. The status information includes overall status which includes the states of idle, pending, first poll and lost. The status information also includes port status information for each descriptor. Each port status information includes active and free states for each transmit queue. Also provided is a means for the periodic polling of the overall activity state.
When a packet is received, a descriptor is removed from the Free Pool. When the descriptor is placed on one or more of the transmit queues, the overall activity state in the corresponding Reference Memory location moves from Idle to Pending. Each port that received a copy of the descriptor will have its corresponding per port status set to Active.
When a descriptor is removed from a transmit queue, the corresponding per port status is set to Free. If the per port status of all ports is Free, the overall activity state of the descriptor is set to Idle and the descriptor is returned to the Free Pool.
Lost buffers can occur, and can be detected, in several different parts of the network device.
In the first embodiment, it is possible to detect lost buffers by monitoring the descriptor free pool, and the descriptor reference memory. Since all of the descriptors should either be in the descriptor free pool, or should have an active status in the descriptor reference memory, the sum of the number of descriptors in the free pool with the number of descriptors having an active state in the descriptor reference memory should remain constant and equal to the total number of descriptors. A count of the number of descriptors in the descriptor free pool, and of the active descriptors in the descriptor reference memory is maintained and periodically checked. If the total of these two numbers does not equal the total number of descriptors, an error is indicated.
A transmit queue elaborated counter and a reference memory elaborated counter are also provided to maintain separate accounting of the descriptors in the transmit queues. When a descriptor is placed in one or more transmit queues, both the transmit queue elaborated counter and the reference memory elaborated counter are incremented by the number of queues to which the descriptor is added. When a descriptor is removed from one of the transmit queues, the transmit queue elaborated counter is decremented. When the data packet corresponding to the removed descriptor is transmitted by the port, the reference memory elaborated counter is decremented. Because of the time difference in decrementing the transmit queue elaborated counter and the reference memory elaborated counter, the value of these counters will be different until all of the data packets for the removed descriptors have been transmitted. However at no time, should the difference between the counters be greater than the number of ports. This is because each port should only be holding one data packet before the reference memory elaborated counter is decremented. If the difference between the values of the two counters is greater than the number of ports, a lost buffer is indicated.
When a lost buffer is indicated, the overall healing system can be reinitialized. This involves clearing memory, and resetting counters, which is known to the person of ordinary skill in the art and
Hiscock James Scott
Lindeborg Carl John
Magnan Normand Louis
Ziegler John Ernest
3Com Corporation
Farooq Mohammad O.
Gaffin Jeffrey
McGlew and Tuttle , P.C.
LandOfFree
Method and apparatus to detect lost buffers with 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 Method and apparatus to detect lost buffers with a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to detect lost buffers with a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3073523