Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-07-16
2002-05-21
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S414000
Reexamination Certificate
active
06393027
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of The Invention
The present invention relates to packet communication systems. In particular, the invention is directed to the method and device for selective pushout in the packet communication queuing module with shared buffer.
2. Related Prior Art
In the field of packet communication networks, packet processing systems such as switches and multiplexers for ATM and Ethernet are usually implemented in the shared-buffer memory-based architecture. In such an architecture, incoming packets from all input ports to different output ports are buffered in logical output queues within the same shared buffer. As the size of the shared buffer is bounded in practical implementation, a packet processing system always needs a method to decide which packets should be discarded in buffer-full situations. This is usually referred to as the packet discarding control method. A good packet discarding control method should be fair and efficient, i.e. the shared buffer should be fairly used by all output queues, and the discarded packets should be selected to have the least impact on system performance.
Most shared buffer packet communication systems employ the threshold-based method as packet discarding control. Such approach inhibits the buffering of incoming packets when the buffer usage reaches certain threshold level. This can be easily implemented using a counter and a comparator, but it provides a less optimum performance due to space-non-conserving, i.e. packet discarding occurs before the buffer is full.
Selective pushout (hereafter referred to as “Pushout”) packet discarding control was found to achieve fair buffer utilization and optimum cell loss performance for the shared-buffer switching systems. The basic concept of Pushout packet discarding is to discard a packet from the head of the longest queue to accommodate the incoming packet. This helps balancing the buffer occupancy of all queues, and also reducing the average delay by replacing an “old” packet with a “new” one. Inspite of its optimum performance, Pushout is very difficult to implement because it must sort and find out the longest one from all queues in the shared buffer on every packet arrival event. When the number of queues is large and the arrival of packets is frequent, the sorting operation may become the bottleneck for practical implementation.
Therefore, it is necessary to provide a better implementation for the Pushout packet discarding method.
SUMMARY OF THE INVENTION
The main objective of the invention is to provide a packet discarding control method for packet communication systems with shared buffer. The packet communication system has a pointer (Qmax) to point to the quasi-longest queue in the shared buffer and a corresponding queue length counter (QL[Qmax]). The pointer Qmax is updated on every packet arrival and departure events. If the destination queue of an arriving packet becomes longer than QL[Qmax] after the arrival, Qmax is updated to point to this new quasi-longest queue. Similarly, if the output queue of a departing packet is still longer than QL[Qmax] after the departure, Qmax is updated to point to this new quasi-longest queue. As the quasi-longest queue pointer Qmax is updated on every change of queue length, it tracks the real longest queue closely.
When the shared buffer is fill and there are packets arriving at the inputs of the system, the packets at the head of the quasi-longest queue are pushed out and discarded to make room for the newly arrived packets. The method is hence called quasi-pushed (QPO) packet discarding control. Since the quasi-longest queue pointer tracks the-real longest queue closely, QPO is able to provide the fairness and efficiency of the original Pushout packet discarding control method. It is also suitable for practical implementation because the update of the quasi-longest queue pointer, Qmax, involves only one comparison between two queue length counters, and there is no need to sort out the maximum one among all queue length counters.
The present invention will be easily understood by referring to the following embodiment and attached drawings.
REFERENCES:
patent: 5521916 (1996-05-01), Choudhury et al.
patent: 5724358 (1998-03-01), Headrick et al.
patent: 5982771 (1999-11-01), Caldara et al.
patent: 6272143 (2001-08-01), Lin et al.
Accton Technology Corporation
Ho Duc
Hsu Alpus H.
LandOfFree
Quasi-pushout packet discarding method for packet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quasi-pushout packet discarding method for packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasi-pushout packet discarding method for packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858022