Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2001-12-05
2004-09-28
Pham, Chi (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
C370S230100, C370S232000
Reexamination Certificate
active
06798741
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to packet-based computer networks, and more particularly to controlling traffic rates within a packet-based network.
BACKGROUND OF THE INVENTION
Packet-based networks are known to transmit data in bursts. Bursty traffic can cause congestion in the network and can cause packets to be dropped when input buffers are full. In order to improve the performance of a network and to provide guaranteed quality of service (QoS), it is necessary to be able to control the flow of traffic at various locations in the network to a particular desired rate. Two techniques for controlling the flow of traffic are generally referred to as rate shaping and rate limiting. Rate shaping involves buffering packets as they arrive at a location and then controlling the flow of packets leaving the buffers according to a given algorithm to meet a desired rate. Because packets are buffered, bursts of packets can be absorbed and then dispatched in a controlled manner such that incoming packets are not dropped. Rate limiting involves measuring the rate of packets coming into a location and then dropping the packets that arrive in excess of the desired rate.
Some common algorithms that can be used to accomplish rate shaping or rate limiting include the well-known leaky bucket and token bucket algorithms. Using a leaky bucket algorithm to accomplish rate shaping involves buffering incoming packets and then dispatching the packets from the buffer at a constant rate, i.e., the leak rate (measured, for example, in bytes/second). For example, when a packet of size C (i.e., in bytes) is received, it is held in the buffer for a time period of C/leak rate before it is dispatched from the buffer. While the buffer is empty, the transmission capacity, as dictated by the leak rate, goes unused and is not accumulated for subsequent bursts of packets. Therefore, when a new burst of packets arrives in the buffer after a period of no traffic, the new packets are still buffered and dispatched at the leak rate. This technique does not provide flexibility to account for the bursty nature of packet-based network traffic.
Using a token bucket algorithm for rate shaping involves assigning a bit value (i.e., 1,000 bytes, 50 cells, etc.) to a bucket at a constant rate and allowing packets to be dispatched from a buffer only if the requisite number of bits, bytes, or cells have accumulated in the bucket. During periods of no traffic, bits continue to accumulate in the bucket at the constant rate and subsequent bursts of traffic can utilize the accumulated bits. Although this technique does provide flexibility to account for the bursty nature of network traffic, if the bucket accumulates too many bits during periods of no traffic, subsequent packet bursts may not be shaped. The size of an allowable burst can be limited by setting a maximum value for the number of bits that can accumulate in a bucket, however the maximum value for the bucket must be at least as large as the largest expected packet in order to prevent a large packet from being trapped in the buffer. A disadvantage to setting the maximum bucket size to the size of the largest expected packet is that it will allow large bursts of relatively small packets to go out unshaped.
Another algorithm that can be used for rate shaping or rate limiting involves calculating a current traffic rate at a location and comparing the current rate to the desired rate to determine whether or not subsequent packets should be dispatched. According to the algorithm, if the current rate is less than the desired rate, then packets are allowed to flow and if the current rate is greater than the desired rate, then packets are not allowed to flow. One known algorithm such as this that is used for rate shaping is referred to as an exponential weighted moving average (EWMA) algorithm. An example of an EWMA algorithm is expressed as:
Current_Rate
N
=(1−Gain)·Current_Rate
N−1
+Gain·Bytes
N
with,
t
N+1
=t
N
+&Dgr;t
where Current_Rate
N
is the EWMA in the N
th
sampling interval, Current_Rate
N−1
is the EWMA in the N−1 sampling interval, and Bytes
N
is the number of bytes that were dispatched during the N
th
sampling interval, where each sampling interval has a period of &Dgr;t. The Gain controls the time constant (i.e., frequency response) of what is essentially a low-pass filter operation. When used to dispatch packets from a buffer, if the Current_Rate
N
is greater than a pre-defined desired rate (referred to as Desired_Rate), then no packets are dispatched. If the Current_Rate
N
is less than the Desired_Rate, then packets are dispatched. An algorithm for controlling the dispatch of packets from a buffer is expressed in the prior art as:
if (Current_Rate
N
>Desired_Rate)
No packets dispatched else
Packets dispatched
FIG. 1
depicts an example graph of the current rate of traffic
104
versus time (in increments of &Dgr;t) that results from application of the above-described EWMA algorithm in a rate shaping system where the buffer is fully loaded with packets. At an initial time, t
0
, a burst of traffic is dispatched and the current rate, calculated as the EWMA, jumps up above the desired rate, where the desired rate is indicated by horizontal dashed line
106
. As long as the current rate is above the desired rate, no new traffic is dispatched and the current rate steadily declines. Once the current rate declines to below the desired rate (i.e., time t
2
), a new burst of traffic is dispatched and the current rate jumps back up above the desired rate. As depicted in
FIG. 1
, in a fully loaded system, the current rate of traffic is almost entirely above the desired rate because the moment the current rate drops below the desired rate, more packets are dispatched. Because the current rate is almost entirely above the desired rate, the achieved transmission rate over a period of full loading will be greater than the desired rate, where the achieved rate is calculated as the total number of bits dispatched divided by the time period over which the bits were dispatched. For example, in
FIG. 1
the achieved rate
108
over the time period t
0
through t
9
in a fully loaded system is above the desired rate. Ideally, the achieved rate should be equal to the desired rate.
In view of the need to be able to control certain network traffic to desired rates and in view of the disadvantages of prior art rate shaping and rate limiting algorithms, what is needed is an algorithm that can effectively control packet-based traffic rates, that is flexible, and that is easy to implement, especially in hardware.
SUMMARY OF THE INVENTION
A method and system for controlling the flow of packet-based traffic to meet a desired rate involves calculating, as a moving average, a current rate of packet-based traffic on a link, calculating the sum of the error between the calculated current rate and the desired rate, and determining whether or not packets can flow in response to the calculated sum of the error. In an embodiment, when the sum of the error between the current rate and the desired rate is less than or equal to zero, packets are dispatched from a buffer onto a link and when the sum of the error is greater than zero, packets are held in the buffer. Because the flow of packets is controlled in response to the sum of the error between the current rate and the desired rate, the achieved rate of traffic is maintained close to the desired rate even in bursty traffic environments.
In an embodiment of the invention, the sum of the error is compared to a threshold value to determine whether or not packets are allowed to flow. Packets are allowed to flow if the sum of the error is below the threshold and are not allowed to flow if the sum of the error is above the threshold. In an embodiment, the threshold value is zero and packets are allowed to flow if the sum of the error is less than or equal to zero. In another embodiment, packets are allowed to flow when the sum of the error indicates that the achieved rate of traff
Aatresh Deepak J.
Lodha Sandeep
Jones Prenell
Pham Chi
Riverstone Networks, Inc.
Wilson Mark A.
LandOfFree
Method and system for rate shaping in packet-based computer... 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 system for rate shaping in packet-based computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for rate shaping in packet-based computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189225