Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1999-03-22
2001-06-26
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
C714S026000
Reexamination Certificate
active
06252848
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to the design of a data network and more particularly to a method for optimizing system performance in a data network through ingress rate monitoring.
2. Description of Related Art
A flow of data entering a network is routed to a designated queue while other flows are simultaneously routed to their designated queues. A queue can build up (i.e., congest) when the egress rate is less than the ingress rate for that queue. This congestion can lead to poor performance for the underlying tasks. Therefore, the efficient management of congestion is an important goal in the design of a data network.
As illustrated in
FIG. 6
, a representative data network includes data channels C
1
′-C
3
′, which take as inputs data from the Flows F
1
′-F
9
′. The channels pass data to a switch S′, which in turn passes the data to Queues Q
1
′-Q
3
′.
The data in each of flows F
1
′·F
9
′ consists of a sequence of packets (i.e., units of data). The packets corresponding to a given flow (i.e., one of F
1
′-F
9
′) pass through a designated channel (i.e., one of C
1
′-C
3
′) and are routed by Switch S′ to a designated queue (i.e., one of Q
1
′-Q
3
-).
When the network becomes congested, packets can be dropped due to a lack of resources. Dropped packets must then be resent. This places an additional load on the system that can lead to further congestion.
A packet is dropped according to the RED algorithm (Random Early Detection) in the packet's corresponding queue (i.e., one of Q
1
′-Q
3
′). As illustrated by the drop probability curve in
FIG. 7
, the probability of dropping a packet is set to zero for values of the average queue size less than a lower RED threshold value and is set to one for values greater than an upper RED threshold value. For values of the average queue size in between the two thresholds, the drop probability depends linearly on the average queue size. Once the drop probability of a packet is determined, then the packet may or may not be dropped according to a random test; otherwise, the packet is enqueued. Details of the RED Algorithm are given in “Random Early Detection Gateways for Congestion Avoidance”(Sally Floyd and Van Jacobson, 1993 IEEE/ACM Transactions on Networking), incorporated herein by reference.
The dropping of packets effectively signals congestion in a data network to a higher-level protocol such as TCP, and the higher-level protocol then responds by slowing down the rate of the corresponding flow. When there is no congestion (i.e., no dropping of packets), the higher-level protocol naturally increases the overall traffic in the network until congestion occurs. While the use of RED to signal congestion has some advantages, this approach still can lead to limitations in system performance, which can be characterized by measures such as throughput (i.e., the total amount of data transferred) and goodput (i.e., the amount of data transferred completed tasks).
Because the RED algorithm allows the dropping of packets without regard to the characteristics of a flow, packets may be dropped in a flow that is critical for system performance but is not responsible for congestion in the system. Thus, for example, the RED algorithm does not distinguish between a high-bandwidth flow related to a file transfer and a low-bandwidth flow related to a control signal. In a qualitative sense, the overall performance of the system will benefit by increasing drop probabilities for flows that are causing the congestion.
Attempts to modify the RED algorithm have generally focussed on additional inputs other than ingress measurements and performance criteria other than and system performance.
For example, the FRED algorithm (Flow Random Early Drop) modifies the drop probability according to the RED algorithm by incorporating information on buffer use (i.e., queue usage) so that packets of a flow with high buffer use are more likely to be dropped. The FRED algorithm makes this modification by maintaining per-active-flow buffer counts for each flow that currently has packets buffered. Details of the FRED algorithm are discussed in “Dynamics of Random Early Detection” (Dong Lin and Robert Morris, Proceedings of SIGCOMM'97).
The Adaptive RED algorithm employs a drop probability curve according to the RED algorithm, where the curve can be modified according to some system performance goal; however, flow characteristics and measurements are not used. Details of the Adaptive RED algorithm are discussed in “A Self-Configuring RED Gateway” (Feng et al.).
The WRED algorithm (Weighted Random Early Detection) uses the IP precedence of a packet to modify the drop probability without regard to the flow. That is, a different drop probability curve as in
FIG. 7
is used for each IP precedence (from 1 to 8). As a result, one cannot expect improved system performance. A variant of the WRED algorithm also employs different drop probability curves at each queue.
Other approaches have focussed on preferences for certain users. That is, a flow owned by a preferred user can have a drop probability curve with lower values as compared with a curve associated with a non-preferred user. As a result, flows belonging to a preferred user may be benefited, but system performance is not likely to be enhanced. For example, the two-bit scheme allocates a higher-priority queue to a preferred user. Similarly the USD scheme allocates higher bandwidth to a preferred user. The RIO scheme includes two drop probability curves, one for flows “in profile” and one for flows “out of profile” with respect to some flow characterization based in part on the user. The “in profile” curve uses a higher value for the lower RED threshold as compared with the “out of profile” curve. As a result, packets may be dropped for flows that are “out of profile” while the congestion in the system is being caused by flows that are “in profile.” Preferences based primarily on user identification cannot be expected to enhance system performance. Details of the two-bit scheme, the USD scheme and the RIO scheme are discussed in “A Comparative Study of Schemes for Differentiated Services” (Anindya Basu and Zheng Wang, IETF Website).
Other non-probabilistic approaches to dropping packets have also been developed. Examples include U.S. Pat. No. 4,769,810 and U.S. Pat. No. 4,769,811. However, for some applications these approaches appear to be less successful in signaling congestion in a data network.
SUMMARY OF THE INVENTION
Accordingly, it is an object of this invention to provide a method for optimizing performance in a data network.
It is a further object of this invention to provide a method for optimizing performance in a data network using ingress flow measurements.
It is a further object of this invention to provide a method for optimizing performance in a data network where the optimization criterion is based on system performance.
It is a further object of this invention to provide a method for marking packets of flows according to a comparison of ingress flow measurements and flow profiles.
It is a further object of the invention to provide a method for selecting drop probability functions according to the marking of a packet.
It is a further object of the invention to provide a method for selecting the drop probability of a packet according to the average queue size of the queue and the marking of a packet.
The above and related objects of the present invention are realized by a method for optimizing performance in a data network including a plurality of ingress ports and output queues. Ingress rates of a plurality of flows are monitored, each flow including a plurality of packets passing from an ingress port to an output queue, each flow having a profile related to flow characteristics. Each packet is marked with one of a plurality of flow markings based on criteria including the ingress rate and the flow profile. A drop probability of each packet is adjusted
Chin Wellington
Jones Prenell
Pillsbury Winthrop LLP.
Pluris, Inc.
LandOfFree
System performance in a data network through queue... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System performance in a data network through queue..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System performance in a data network through queue... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2477520