Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-07-31
2001-08-07
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S414000
Reexamination Certificate
active
06272143
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to packet communication systems. In particular, the present invention is directed to the method and system for selective pushout in packet communication queuing modules with shared buffer. More particularly, the present invention relates to the method and system for selective pushout with upper-layer discarding control in packet communication queuing modules with shared buffer.
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 as those mentioned in “Dimensioning of an ATM switch with shared buffer and threshold priority,” Computer Networks and ISDN systems, no. 26, pp. 95-108, 1993 and “Dynamic queue length threshold in a shared memory ATM switch,” in Proc. Of INFOCOM, 1996, pp. 679-687. Such approach inhibits the buffering of incoming packets when the buffer usage reaches certain threshold level. This can be easily implemented with a usage counter and a comparator, but it provides a sub-optimum performance due to space-non-conserving, i.e., packet discarding occurs before the buffer is full.
Selective pushout (referred as “Pushout” hereafter) packet discarding control was found to achieve fair buffer utilization and optimal packet loss performance for the shared-buffer switching systems (see I. Cidon, et. al. “Optimal buffer sharing,” IEEE Journal on selected areas in communications, vol. 13, no. 7, pp. 1229-1239, September 1995 and L. Tassiulas, et. al. “Optimal buffer control during congestion in an ATM network node,” IEEE/ACM Trans. On Networking, vol. 2, no. 4, pp. 374-386, August 1994). The basic concept of Pushout packet discarding is to discard 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 “young” one. In spite of its optimum performance, Pushout is very difficult to implement because it must sort out the longest of all queues in the shared buffer on every packet arrival events. When the number of queues is large and the arrival of packets is frequent, the sorting operation may become the bottleneck for practical implementation.
Most communication protocols are layered, i.e., an upper-layer packet is segmented into several small lower-layer packets. For each upper-layer packet, if one or more lower-layer packets of it have been discarded, its integrity is damaged and the whole upper-layer packet should be retransmitted. Therefore, if a to-be-discarded lower-layer packet is selected from a damaged upper-layer packet, the upper-layer packet loss performance will not be affected. Such discarding control associated with the status of upper-layer packets shall reduce the damage to upper-layer packets and thus provide better upper-layer packet loss performance.
Therefore, it is necessary to provide a better implementation of Pushout packet discarding method. Besides, the upper-layer packets status should also be considered to achieve better upper-layer packet loss performance.
SUMMARY OF THE INVENTION
The main objective of this 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 indicate the quasi-longest queue in the shared buffer and a corresponding queue length counter (QL[Qmax]) thereof. The pointer Qmax is updated on every packet arrival and/or departure events. If the length of the destination queue of an arriving packet grows longer than QL[Qmax] after the arrival, Qmax is updated to point to this new quasi-longest queue. Similarly, if the length of the output queue of a departing packet is found 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 packet arrival and/or departure events (queue length change events), it tracks the real longest queue closely.
In one embodiment of the present invention, when the shared buffer is full and there are packets arriving at the inputs of the system, some packets must be discarded to make space for the arriving ones. The to-be-discarded packet is selected from the head of the quasi-longest queue. Since the quasi-longest queue pointer tracks the real longest queue closely, quasi-pushout (QPO) is able to provide the fairness and efficiency of the conventional 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, instead of sorting out the maximum among all queue length counters.
In addition, a damage flag and a damaged-queue pointer can be employed to identify the presence of a damaged upper-layer packet and to point to the queue which stores the damaged upper-layer packet respectively. And in another embodiment of the present invention, when the shared buffer is full and an incoming packet arriving at the input of the system, the packet to be discarded to make space for the arriving one is first selected from the damaged upper-layer packet, and then, from the head of the quasi-longest queue. The associated upper-layer packet status control will improve the upper-layer packet loss performance by accumulating discarded lower-layer packets in damaged upper-layer packets.
The present invention will be easily understood by referring to the following embodiments and attached drawings.
REFERENCES:
patent: 5475682 (1995-12-01), Choudhury et al.
patent: 5521916 (1996-05-01), Choudhury et al.
patent: 5561663 (1996-10-01), Klausmeier
patent: 0715436 (1996-06-01), None
Y. Lin et al, Quasi-Pushout Cell Discarding, Sep. 5, 1997, IEEE Communications Letters vol. 1, No. 5., pp. 146-148.
J.F. Meyer et al, Dimensioning of an ATM Switch with Shared Buffer and Threshold Priority, 1993, pp. 96-108.
A. Choudhury et al, Dynamic Queue Length Thresholds in a Shared Memory ATM Switch, 1996 IEEE, pp. 679, 687.
I. Cidon, Optimal Buffer Sharing, Sep. 7, 1995, IEEE Journal, vol. 13, No. 7, pp. 1229-1240.
L. Tassiulas, Optimal Buffer Control During Congestion in an ATM Network Node, IEE/ACM Transactions on Networking, vol. 2, No. 4, Aug. 4, 1994, pp. 374-386.
Lin Yu-Sheng
Shung C. Bernard
Accton Technology Corporation
Cangialosi Salvatore
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Quasi-pushout method associated with upper-layer 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 method associated with upper-layer packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasi-pushout method associated with upper-layer packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447785