Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
1999-02-04
2004-12-07
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Diagnostic testing
Determination of communication parameters
C370S395210
Reexamination Certificate
active
06829224
ABSTRACT:
1. FIELD OF THE INVENTION
The present invention relates generally to communication systems, and specifically, to a method and apparatus for smoothing the rate of packet discards for random early detection in a communication device.
2. BACKGROUND
Asynchronous Transfer Mode (“ATM”) networks are cell switching networks that transfer fixed length data units called “cells.” Cells are transmitted from a source node to a destination node through ATM (or digital) switches, which are coupled together by way of communication lines. An ATM switch includes a plurality of input ports coupled to input communication lines and a plurality of output ports coupled to output communication lines.
Cells carry voice, video, and data information from the source node to the destination node. Cells are fifty-three bytes in length and include five bytes of header information and forty-eight bytes of payload. The header information includes a virtual path identifier (“VPI”) field and a virtual channel identifier (“VCI”) field, identifying the next destination of a cell as it passes through a series of ATM switches on its way to its destination node. ATM switches asynchronously receive cells on the input ports and switch the cells to the proper output ports based on the VPI and VCI information in the header of the cells.
Each communication line can carry several different connections simultaneously. Queues are typically used within an ATM switch for temporarily storing cells prior to transmission on a communication line. More than one queue may be used to service different types of class of service connections. For example, cells belonging to higher priority connections (e.g., voice connections) may be stored in queues that are marked as higher priority. On the other hand, cells belonging to lower priority connections (e.g., data) may be stored in queues that are marked as lower priority.
These queues, which have a finite size, must be able to store cells for each connection. Thus, in an ATM switch architecture, it is essential to efficiently use buffer resources, while remaining fair to all connections. Moreover, since queues have a finite size, threshold values are assigned to the queues to define a maximum number of cells that can be stored for each connection. Consequently, one function of an ATM switch is to determine whether to accept or reject cells depending on whether the queue that the cell belongs to has reached its maximum threshold.
The ATM Adaptation Layer (“AAL”) is utilized to segment higher layer packets into cells for transporting Transmission Control Protocol/Internet Protocol (“TCP/IP”) traffic over ATM networks. If a cell is discarded by an ATM switch, the entire packet that the cell belongs to is dropped. If TCP/IP packets from several sources are dropped at substantially the same time, a global synchronization problem is likely to occur. Global synchronization occurs when source nodes react to dropped packets synchronously, slowing retransmission of packets. When the source nodes determine that the network is not congested, they begin to retransmit packets at a higher rate, thereby causing congestion again. This type of oscillating behavior reduces throughput.
One technique for solving TCP global synchronization has been proposed by Sally Floyd and Van Jacobson, entitled “Random Early Detection Gateways for Congestion Avoidance”, published in August 1993 by IEEE/ACM Transactions on Networking. According to Floyd/Jacobson, a random early detection (“RED”) algorithm is employed to smooth the distribution of cell discards over time, thereby reducing TCP global synchronization and improving performance.
However, RED is not well suited in high-speed implementations in hardware since it requires multiplication and division operations. Prior art techniques may have performed the multiplication/division smoothing function of RED in software, or used a look-up table in hardware, which is either expensive in terms of chip die area or has limited precision.
SUMMARY OF THE INVENTION
A method for smoothing a rate of cell discards for random early detection in a communication device is described. A cell is detected and an instantaneous discard probability is calculated. The method includes updating a discard probability as a function of the instantaneous discard probability and an accumulated probability, and comparing the discard probability with a random number. If the discard probability is greater than the random number, the cell is discarded, otherwise the cell is accepted.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 5764641 (1998-06-01), Lin
patent: 6282171 (2001-08-01), Adams et al.
patent: 6333917 (2001-12-01), Lyon et al.
patent: 6345037 (2002-02-01), St-Denis et al.
patent: 6434116 (2002-08-01), Ott
patent: 6463068 (2002-10-01), Lin et al.
Random Early Detection Gateways for Congestion Avoidance, Sally Floyd and Van Jacobson, Lawrence Berkeley Laboratory, University of California, Aug. 1993, pp. 1-32.
The ATM Forum, Technical Committee,Utopia Level 2, Version 1.0, af-phy-0039.000, Jun. 1995, pp. 1-66.
Y. Li and S. Elby. “TCP/IP Performance and Behavior Over an ATM Network”. 1996 IEEE. pp. 1-9.
H. Chiou and Z. Tsai. “Performance of ATM Switches with Age Priority Packet Discarding under the On-Off Source Model”. 1998 IEEE. pp. 931-938.
M. Casoni. “Early Packet Discard with Diverse Management Policies for EOM Cells”. 1997 IEEE. pp. 33-37.
Nathan Harwell, “TCP Over ATM”, Internet Web Site, Nov. 5, 1998, 5, http://ils.unc.edu/atm/.
Goldman Gary S.
Nikuie Mohammed
Blakely , Sokoloff, Taylor & Zafman LLP
Cisco Technology Inc.
Hsu Alpus H.
Nguyen Toan D.
LandOfFree
Method and apparatus for smoothing the rate of 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 Method and apparatus for smoothing the rate of packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for smoothing the rate of packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3321120