تجزیه و تحلیل سیستم خطی RED

The random early detection (RED) algorithm proposed by Floyd and Jacobson [IEEE/ACM Trans. Networking 1 (4) (1993) 397] is a simple and quite effective mechanism for active queue management and as a result has been widely implemented in Internet routers. While RED certainly performs better than drop-tail, its parameters are difficult to tune to give good performance under different congestion scenarios. Also, studies have shown that RED does not stabilize the queue lengths in routers, because its equilibrium queue length strongly depends on the number of active TCP connections. As a result numerous variants of RED have been proposed to work around the performance problems of RED. In this paper, using inferences drawn from a linear systems analysis, we provide an insight into why RED is difficult to tune. The same linear systems analysis is used to show that the DRED algorithm proposed in [Computer 36 (2–3) (2001) 203; Comput. Commun. 24 (12) 2001 1170] overcomes the performance limitations of RED [IEEE/ACM Trans. Network. 1 (4) (1993) 397].

The idea behind active queue management (AQM) is to detect incipient congestion in routers and switches early and convey congestion notification to the end-hosts, allowing them to back off before queue overflow and sustained packet loss occur. One form of AQM recommended by the IETF for deployment in the Internet is RED [1] and [4]. Studies have shown that RED does not stabilize queue lengths in routers, because its equilibrium queue length strongly depends on the number of active TCP connections [5]. The dynamics of TCP changes when the number of active connections changes, and RED exhibits sensitivity to the specific traffic scenario in the network. The performance of RED can be tuned by adjusting its parameters but such a process requires knowledge of network traffic load. Configuring RED's parameters to optimize network performance is an open issue and is still under active research. Using inferences from simple linear system analysis, we explain here why RED is difficult to tune and why RED is not able to stabilize router queues over a wide range of congestion scenarios. The interest in understanding the tuning issues in RED has become very important and stems mainly from the following factors: • Currently, RED is the only algorithm widely implemented in routers, switches, etc. • System and network engineers want to know how to configure/tune RED. • System and network engineers want to know if they should even deploy RED (e.g. see Ref. [6]). • Is there a need to look at the AQM problem from an entirely different perspective? The discussion here is motivated by ideas that are familiar in linear system analysis and control theory. This allows us to make parallels and use insights developed in these fields. We do acknowledge that the models used in the discussions are a rough representation of the AQM process, however, they are adequate enough to help us make the necessary inferences about the behavior of the algorithms under discussion. The linear systems analysis is also used to show that the DRED algorithm proposed in [2] and [3] overcomes the performance limitations of RED [1]. Including a discussion on DRED here is based on the desire to answer the following question: could the linear system approach on which the development of DRED is based also offer an insight into the tuning difficulties of RED? DRED uses a simple feedback control approach to randomly discard packets with a load-dependent probability when a buffer in a router becomes congested. Over a wide range of load levels, DRED is able to stabilize a router queue occupancy at a level independent of the number of active TCP connections. DRED maintains the average queue size close to a predetermined threshold, but allows transient traffic bursts to be queued without unnecessary packet drops. This is done without estimating the number of active TCP connections or flows and also without collecting or analyzing state information on individual flows. A detailed discussion and investigation of RED and DRED including simulations with different network configurations and sources with different round-trip times (RTTs), traffic load, link rates, and sensitivity studies are given in [2] and [3]. A detail comparison of DRED with RED [1] and some recently proposed AQM algorithms (BLUE [7], SRED [8]) for short-lived and long-lived flows is given [9]. Thus, the simulation studies included here serve only to explain/verify the observations made from the linear analysis. We also note here that the previously published papers [2], [3] and [9] focus on the design of DRED as a new alternative to RED [1] and do not present analytic discussions (based on linear system theory) on the tuning difficulties of RED. These analytic discussions are the focus of this paper.

Using inferences from simple linear system analysis, we have explained in this paper why RED is difficult to tune and why RED is not able to stabilize network queues over a wide range of congestion scenarios. The same linear system analysis is used to explain why the DRED algorithm does not exhibit the same tuning/stabilizing difficulties as RED. DRED uses a simple feedback control approach to stabilize a router queue occupancy at a level independent of the number of active connections. We have shown through simulations that DRED is able to keep the buffer occupancy close to a specified control target and away from overflow and underflow. The DRED algorithm controls the average queue size close to the control target, but allows arriving bursts to be accommodated without dropping packets. The benefits of a stabilized queue in a network are high resources utilization, predictable maximum delays, more certain buffer provisioning, and traffic-load-independent network performance in terms of traffic intensity and number of connections.