A Review of Router based Congestion Control Algorithms
Автор: Vandana Kushwaha, Ratneshwer
Журнал: International Journal of Computer Network and Information Security(IJCNIS) @ijcnis
Статья в выпуске: 1 vol.6, 2013 года.
Бесплатный доступ
This paper presents a study of Router based Congestion control approaches in wired network. As network is considered as a distributed system, any problem arises in such a system requires a distributed solution. Thus for good congestion control in the network we also need a solution distributed at source as well as router ends. The purpose of this study is to review the router based Congestion control research for wired network and characterize the different approaches to Congestion control design, by considering their advantages and limitations.
Congestion Control, Router Based Approach, performance metrics
Короткий адрес: https://sciup.org/15011260
IDR: 15011260
Текст научной статьи A Review of Router based Congestion Control Algorithms
Published Online November 2013in MECS DOI: 10.5815/ijcnis.2014.01.01
The Internet is a global infrastructure for information exchange that has revolutionized the social, economic, and political aspects of our lives. One of the most crucial building blocks of the Internet is a mechanism for resource sharing and controlling congestion on the Internet. Congestion can be defined as a network state in which the total demand for resources, e.g. bandwidth, among the competing users, exceeds the available capacity leading to packet or information loss and results in packet retransmissions[1].
It has been agreed upon that the network itself must now participate in congestion control and resource management. The Internet Engineering Task Force (IETF) has advocated the deployment of active queue management mechanisms at routers to detect incipient congestion and to explicitly signal traffic sources before congestion actually occurs.Braden et al [2] (1998) have commented that TCP congestion avoidance mechanisms, while necessary and powerful, are not sufficient to provide good service in all circumstances. There is a limit to how much control can be accomplished from the edges of the network. Some mechanisms are needed in the routers to complement the end point congestion avoidance mechanisms.
The purpose of this study is to reviewthe router based Congestion control approaches for wired network. An attempt has been made to analyzemajor router based congestion control approaches by considering their relative merits and demerits. In this waythis study will trace a better picture of major issues, challenges andpossible solutions of network congestion problem usingrouter based approaches.
The paper is organized as follows: In Section 2, a brief review of previous reviews, conducted on router based Internet congestion control, has been mentioned. The phenomenon of Congestion control is briefly defined in Section 3. In Section 4 we explore the significance of router based Congestion control schemes. Section 5 presents the main observations found during the review. Section 6 discusses the classification, characterization and performance parameter analysis of different approaches. Finally Section 7 concludes the paper.
-
II. RELATED WORKS
In Literature, the problem of Congestion has been studied widely in the context of high speed network, wireless network, satellite network, ad-hoc network etc. Substantial survey works have been reported regarding Congestion control. Some significant survey works related to the topic are as follows. Yang et al [3] (1997) have first proposed a taxonomy of Congestion control approaches in packet switched network, based on control theory. This taxonomy contributesa framework which helps in comparative study of the existing approaches and set a path toward the development of new congestion control approaches.Labrador et al [4] (1999)have given a comprehensive survey of selective packetdropping policies for the best-effort service of ATM and IP networks. They discussedthree router based congestion control schemes for IP networks, namely RED,RED In/Out (RIO) and Flow RED (FRED). They comparedRED and RIO in terms of fairness.Ryu et al [5] (2003) have presented a review of AQM algorithms for congestion control. They also done a survey of control-theoretic analysis anddesign of end-to-end congestion control with a router based scheme. As alternatives to AQM algorithms, they also surveyed architectural approaches such as modification of source or networkalgorithms, and economic approaches including pricing or optimization of allocatedresources.Chatranon et al [6] (2004)have discussed the state-of-the-art in router-basedmechanisms to address the TCP-friendliness problem and presents a description of the most important algorithms, design issues,advantages and disadvantages in their survey. Theyhave done a qualitative comparison of all theexisting AQM schemes and a quantitative
performance evaluationis performed to show the advantages and disadvantagesof only those schemes that don’t require full per-flow stateinformation since they are more likely to be implemented inpractice.Ryu et al [7] (2004) have presenteda review of recently proposed active queue management (AQM) algorithms forsupporting end-to-end transmission controlprotocol (TCP) congestion control with a focus on recentlydevelopedcontroltheoretic design and analysis method for the AQM based TCP congestion control dynamics.Finally, theysurveyed two adaptive and proactiveAQM algorithms, PID-controller and ProActive Queue Management (PAQM), designed using classicalproportional-integral–derivative (PID) feedback control to overcome the reactive congestion control dynamicsof existing AQM algorithms. A comparative study of these AQM algorithms with existing AQMalgorithms is also given by them.An exhaustive survey is madeby Thiruchelvi et al [8] (2008) on the recent advances in the area of AQM techniques. Further they classified the AQM mechanismsaccording to the type of metrics they used as congestionmeasure. From the survey they found that the performancesof rate based AQM schemes are better than that of queuebased schemes and existing rate based schemessuch as AVQ,EAVQ may result in better performance interms of, throughput, packet loss, link utilization by the inclusion of more number ofcongestion measures.Chandra et al [9] (2010) have presented a brief survey of major congestion control approaches, categorization characteristics, elaborates the TCP-friendliness concept and then a state-of-the-art for the congestion control mechanisms designed fornetwork. They pointed out the major pros and cons of the various congestion control approaches and evaluated their characteristics.Adams [10] (2012)has done asurvey that attempts to travel the trajectory of AQM research from 1993 with the first algorithm, Random Early Detection(RED), to thework in 2011. In hersurvey she discussed the general attributes of AQM schemes, and the design approaches taken such as heuristic, control-theoretic and deterministic optimization.
-
III. CONGESTION CONTROL
The Internet is a global infrastructure for information exchange that has revolutionized the social, economic, and political aspects of our lives. One of the most crucial building blocks of the Internet is a mechanism for resource sharing and controlling congestion on the Internet. Congestion can be defined as a network state in which the total demand for resources, e.g. bandwidth, among the competing users, exceeds the available capacity leading to packet or information loss and results in packet retransmissions[1]. At the time of congestion in a computer network there will be a simultaneous increase in queuing delay, packet loss and number of packet retransmissions. In other words Congestion refers to a loss of network performance when a network is heavily loaded. Keshav [11] has defined it as “A network is said to be congested from the perspective of a user if the service quality noticed by the user decreases because of an increase in network load.”
Congestion control refers to techniques and mechanisms that can either prevent congestion, beforeit happen, or remove congestion, after it has happened. Yang et al [3] havedivided congestion control mechanisms into two broad categories: congestion avoidance (open-loop congestion control) and congestion recovery (closed-loop congestion control). The strategy of congestion avoidance is preventive in nature; it is aimed to keep the operation of a networkat or near the point of maximum power, so that congestion will never occur. Whereas, the goal of congestion recovery is to restore the operation of a network to its normal state after congestion has occurred. Without a congestion recovery scheme, a network may crash entirely whenever congestion occurs. Therefore, even if a network adopts a strategy of congestion avoidance, congestion recovery schemes would still be required to retain throughput in the case of abrupt changes in a network that may cause congestion.Congestion control is a (typically distributed) algorithm to sharenetwork resources among competing traffic sources.
-
IV. SIGNIFICANCE OF ROUTER BASED CONGESTION CONTROL
Extensive research works have been done in the area of congestion control by considering the two approaches independently. In this section, we discussed the reasons, to support our view, that why the two approaches should be studied together.
As network is considered as a distributed system, any problem arises in such a system requires a distributed solution. Thus for good congestion control in the networkwe also need a solution distributed at source as well as router ends. Braden et al [2] (1998) have commented that TCP congestion avoidance mechanisms, while necessary and powerful, are not sufficient to provide good service in all circumstances. There is a limit to how much control can be accomplished from the edges of the network. Some mechanisms are needed in the routers to complement the end point congestion avoidance mechanisms.Su et al [12] (2000) found that congestion control is performed mainly by transport protocols at end hosts. However, as continuous media multicast applications (which usually do not deploy TCP for congestion control) become widely deployed on the Internet, it becomes difficult to exclusively rely on end hosts to perform end-to-end congestion control. It has been agreed upon that the network itself must now participate in congestion control and resource management.The Internet Engineering Task Force (IETF) has advocated the Deployment of active queue management mechanisms at routers to detect incipient congestion and to explicitly signal traffic sources before congestion actually occurs.Hollot et al [13] (2002) emphasized that AQM schemes was introduced to allow the router to assist the TCP in network performance management during network congestion. Under TCP, a sender probes the network’s available bandwidth by linearly increasing its rate until data packets are lost. Upon packet loss, the receiver signals the sender to reduce its rate. Rather than waiting for packet loss to occur, AQM acts preemptively by measuring the router’s queue length and throttling the sender’s rate accordingly. Sun et al [14] (2003) commented that AQM schemes complement TCP by signaling congestion. AQM schemes discard or mark packets during congestion which is detected by TCP so that it takes actions to reduce the send rate.Low et al [15] (2003) considered congestion control a distributed algorithm to share network resources (called “links”) among competing sources. It consists of two components: a source algorithm that dynamically adjusts rate (or window size) in response to congestion in its path, and a link algorithm that updates, implicitly or explicitly, a congestion measure and sends it back, implicitly or explicitly, to sources that use that link. On the current Internet, the source algorithm is carried out by TCP, and the link algorithm is carried out by (active) queue management (AQM) schemes such as DropTail or RED.
Ryu et al [5] (2003) found that as the number of users and the size of the network increases, End-to end based congestion control methods are expected to result in unsatisfactory performance like multiple packet losses and low link utilization. Network algorithms such as active queue management (AQM), executed bynetwork components such as routers, detect network congestion, packet losses, or incipient congestion, and inform traffic sources (either implicitly or explicitly). In response, source algorithms adjust the source’s data-sending rate into the network. Paganini et al [16] (2005) emphasized that congestion control mechanisms in the Internet consist of the congestion window algorithms of TCP, running at end-systems, and active queue management (AQM) algorithms at routers. AQM approaches are used in addition to TCP to obtain high network utilization, smallamounts of queuing delay, and some degree of fairness among users.Sonkoly et al [17] (2009) commented that in order to get efficient network operation and to avoid congestion collapse, end-to-end congestion control mechanism is an important component. However, the dynamic behaviour of the network is not exclusively affected by these mechanisms but network routers also play important roles. Active Queue Management schemes were proposed in order to avoid congestion at the routers by means of efficient buffer management.Santi et al [18] (2011) commented that End-to-end based Congestion control mechanism have not been by themselves sufficient to avoid congestion since their sources exert limited control in the aggregate network traffic in the presence of unresponsive flows. Therefore, congestion control must also rely on additional mechanisms, such as Active Queue Management (AQM). Such a mechanism notifies TCP senders of incipient congestion by dropping or marking packets.Xue et al [19] (2012) considered the cooperation of both end-to-end based and router based congestion control mechanisms to provide good congestion solutions in computer networks.Eshete et al [20] (2012) commented that router based mechanisms are designed to make earlier packet drop decisions at congested routers before buffer at routerbecomes full, which allow TCP sources to gracefully slow down their sending rate, thus improving network utilization.
Thus from the above discussion it can be inferred that both the approaches for handling congestion are complementary to each other.
-
V. OBSERVATIONS
We have summarized the observations, during literature review, in the form of tables. The observations are summarized in Table I for router based congestion control approach.
-
VI. DISCUSSION
This section we discuss the significance of router based approach while congestion control. We also summarize the various possible classifications of these approaches, their relative merits and demerits.
Hong et al [21] (2007) commented that TCP congestion control alone is less effective while controlling congestion. Floyd et al [22] (1993) first proposed a router based method for congestionavoidance and emphasized that most effective congestion detection can occur at the router level in cooperation with source level methods. Pan et al [23] (2000) considered aggressive nature of non-TCP (unresponsive) applications as a cause of congestion collapse. Therefore it is required to have router level mechanism to prevent TCP (responsive) flows from aggressiveness of nonresponsive flows.
Aweya et al [24] (2001) commented that buffer overflow is a major issue while using TCP based congestion control with drop-tail routers and for avoiding these overflows router should use some active queue management scheme. Feng et al [25] (2001) considered nonresponsive flow’s aggressiveness as a dangerous situation for TCP flows as it causes congestion collapse. Chang et al [26] (2006) considered network congestion a severe problem as it leads wastage of network resources due to queue overflow at router.Wang et al [27] (2008) commented that Congestion control in communication networks has become increasingly important due to the explosive expansion and the growth of traffic. From the control theory point of view, congestion control problems are complex and challenging due to their highdimensional, nonlinear, and dynamic properties. Jing et al [28] (2008) considered congestion control a major problem because it severely affects quality of service of the network.
-
A. Available methods for Router based Congestion Control
19.
2008
A robust proportional controller for AQM based on optimized second-order system model
AOPC(control theoretic)
Queue length+packet loss ratio
responsiveness, best tradeoff between utilization and delay, convergence rate, queue oscillations,robustness
20.
2009
Effective RED: An algorithm to improve RED's performance by reducing packet loss rate
Effective-RED (heuristic)
Queue length
(both instantaneous + average)
throughput, packet drops, fully compatible with RED, easily upgrade/replace the existing RED
21.
2011
Active Queue Management for Flow Fairness and Stable Queue Length(fairness-enforcing
AQM)
P-AQM
Input rate + loss rate
fairness(intra/inter), stable queue.
22.
2011
Design of optimal Active Queue Management controllers for HSTCP in large bandwidthdelay product networks (HSTCP-H2 controller)
HSTCP-H2(control theoretic)
Queue length input rate
good put , intra protocol fairness
23.
2013
A robust active queue management scheme for networkcongestion control
RC (control theoretic)
robustness, queue stability
Earlier congestion was handled by only source level methods like TCP. But as the network size and network resources increases, source level methods were unable to solve the congestion problem. It was realized that the problem of congestion control is distributed in nature.
Therefore it is not reasonable to rely only on end host forcongestion control; some source level as well as router
TABLE I. List of Router based Congestion Control approaches
S.No. |
Year |
Publication Title |
Method for Congestion Control |
Performance metrics |
|
Approach |
Congestion Measure |
||||
1. |
1993 |
Random Early Detection Gateways for Congestion Avoidance |
RED (heuristic) |
Average Queue length |
global synchronization, global power, Fairness, parameter sensitivity, packet loss and queuing delay |
2. |
1999 |
Random Early Marking : an Optimization Approach to Internet Congestion Control |
REM (optimization) |
Average Queue length+ input rate |
goodput, packet loss, fairness, buffer occupancy, |
3 |
2000 |
CHOKe : a stateless active queue management scheme for approximating fair bandwidth allocation |
CHOKe (heuristic) |
Average Queue length |
stateless,easy to implement, minimum overhead, throughput |
4. |
2001 |
A control theoretic approach to active queue management |
DRED (control theoretic) |
instantaneous Queue length |
link utilization, packet loss rate |
5. |
2001 |
Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management |
AVQ (optimization) |
input rate |
packet Losses, link utilization, responsiveness to changing network conditions, Queue length |
6. |
2001 |
Stochastic fair blue(SFB): A queue management algorithm for enforcing fairness |
SFB (heuristic) |
Packet loss + link utilization |
throughput, delay, queue length |
7. |
2002 |
Analysis and design of controllers for AQM routers supporting TCP flows |
PI (control theoretic) |
instantaneous queue length |
efficient queue utilization, queuing delay, robustness |
8. |
2003 |
AQM based on Capture Recapture Model |
CARE |
throughput, fairness, stability, adaptability, complexity. |
|
9. |
2004 |
Fair adaptive bandwidth allocation : a rate control based active queue management discipline |
FABA |
input rate |
fairness, complexity, scalability, throughput |
10. |
2005 |
The Yellow active queue management algorithm |
Yellow (heuristic) |
input rate |
link utilization, packet loss, robust, stability, queuing delay |
11. |
2005 |
Exponential-RED :a stabilizingAQM scheme for low- and high-speed TCP protocols |
E-RED (heuristic) |
Queue length |
queue length, throughput, stability, queuing delay |
12. |
2005 |
RAQM: A stable rate-based algorithm for active queue management |
RAQM |
input rate |
stability, faster response, good-put, complexity, independent of the number of flows. |
13. |
2005 |
A robust active queue management algorithm in large delay networks |
DC-AQM(control theoretic) |
Queue length((both instantaneous + average) |
Link utilization, queue length, |
14. |
2006 |
A stable queue-based adaptive controller for improving AQM performance |
Q- SAPI(control theoretic) |
Queue length |
packet loss, queuing delay,link utilization |
15. |
2007 |
RaQ : A robust active queue management scheme based on rate and queue length |
RaQ (dual loop feedback control) |
Queue length input rate |
queue length, stability, robustness, convergence |
16. |
2007 |
LRED: A Robust and Responsive AQM Algorithm Using Packet Loss Ratio Measurement |
LRED (proportional controller) |
Instantaneous Queue length+packet loss ratio |
Response time, robustness, flexible system configurations. |
17. |
2007 |
Active queue management algorithm considering queue and load states |
PAQM |
Queue length input rate |
link utilization, low queuing delay, low complexity and easy configuration. |
18. |
2008 |
Design of a stabilizing AQM controller for large-delay networks based on internal model control |
IMC-PID(control theoretic) |
Queue length |
stability, robustness, convergence, link utilization, delay jitter. |
level methods both are needed to solve it [29]. Therefore different academicians and practitioners had proposed two approaches for congestion control. First one is ‘source based’ approach which works as end to end protocol implemented in TCP. Second one is ‘router based’ approach also known as ‘active queue management’ schemes implemented in Router.
Router based congestion control methods are proactive in nature. Router continuously measure the traffic load and if there is any symptoms of traffic overload which causes congestion , it sends a signal to source host to slow down its transmission speed before congestion occurs. Router based methods sends incipient congestion signal by marking packets with a mark probability. Based on the mark probability calculation criteria router based methods are categorized as: Queue length based, Rate based and Hybrid approach. Based on the nature of solution router based approach are classified as: Heuristic approach , Optimization approach and Control Theoretic approach [10].
-
1) Heuristic Approach
Heuristic approach was followed by earlier router based methods like RED proposed by Floyd et al [22] (1993). RED detects incipient congestion by computing the average queue size and control the average queue size before the gateway queue overflows. They considered it an effective mechanism for congestion avoidance at the gateway; in cooperation with network transport protocols because it is unbiased against bursty traffic and avoid global synchronization. Pan et al [23] (2000) stated that earlier methods for congestion control are either easy to implement or able to achieve flow fairness, but not both simultaneously and they proposed an active queue management method, called CHOKe (CHOose and Keep for responsive flows, Choose and Kill for unresponsive flows) that is simple to implement (since it is stateless) and provide fairness by differentially penalizing misbehaving flows by dropping more of their packets. Kunniyur et al [30] (2001) have given a virtual queue based AQM method AVQ (Adaptive Virtual Queue) which uses a rate based marking approach and it can achieve low loss with high link utilization, more robust to the presence of extremely short flow or variability in the
number of long flow in the network. Feng et al [25] (2001) proposed SFB which scalably detects and rate-limits non-responsive flows through the use of a marking probability derived from the BLUE queue management algorithm and a Bloom filter. Chan et al [31] (2003) found that most of the existing AQM schemes cannot provide accurate fair bandwidth sharing while being scalable because of per flow state management. They proposed a novel AQM scheme, called CApture–Recapture (CARE) which requires small bounded number of states but can provide fair bandwidth sharing similar to those that can be provided with per flow mechanisms. Thus CARE can simultaneously achieve high quality-of-service (QoS), high scalability, and robustness which are necessary for high speed implementation.
Kamara et al [32] (2004) stated that with the emergence of new applications with diverse Quality-of-Service requirements over the Internet, the need for mechanisms that provide differentiated services has become increasingly important and they proposed FABA a rate control based AQM discipline that is well suited to network edges or gateways (e.g., the ISPs). Long et al [33] (2005) demonstrated the inherent weakness of current rate-based active queue management algorithms and proposed a new AQM method ‘Yellow’ with key design goals to predict incipient congestion timely and accurately with controlled queuing delays, stability, and robustness to variation in traffic load. Liu et al [34] (2005) introduced and analyzed a decentralized network congestion control algorithm which has dynamic adaptations at both user ends and link ends, a so-called general primal-dual algorithm and introduced an AQM scheme Exponential-RED (E-RED) which outperforms RED with larger throughput and lower queuing delay and is inherently stable when combined with TCP-Reno or its variants for high-speed networks. Wang et al [35] (2005) proposed rate-based algorithm ‘RAQM’ which uses the aggregated traffic input rate to iteratively compute the packet drop probability according to an exponential rule, in order to regulate the input rate to an expected value. RAQM obtains good stability and fast response under diverse network environment and can regulate the queue length to an expected value and achieve a better tradeoff between goodput and queuing delay. Hong et al [36]
(2007) proposed a new AQM algorithm ‘PAQM’ that considers both the average queue length and the estimated packet arrival rate together in order to detect incipient congestion. The proposed algorithm predicts the average queue length and controls it to maintain a certain reference value to achieve high link utilization and low queuing delay and has low complexity and easy configuration. Abbasov et al [37] (2009) proposed effective-RED a refinement to classic RED scheme with aims to reduce packet loss rates in a simple and scalable manner. Kim et al [38] (2011) stated that flow fairness and queue-length stability are the two major goals of queue management however; most prior works dealt with these goals independently. They proposed a new scheme ‘P-AQM’ which consists of a multilevel caching technique to detect high-bandwidth flows accurately with minimal overhead; and a drop policy for achieving both flow fairness and queue-length stability at the same time.
-
2) Optimization Approach
Lapsley et al [39] (1999) first proposed an optimization approach to congestion control method REM which was derived from earlier work on the Optimization Flow Control (OFC). REM uses Proportional Marking and Online measurement techniques for congestion control which results in fairer bandwidth sharing and allows for the provision of differentiated services between users.
-
3) Control Theoretic Approach
Aweya et al [24] (2001) stated that it is difficult to parameterize RED queues to perform well under different congestion scenarios and further considered router queue length stabilization as one of the goal of queue management methods. They commented that traditional RED does not succeed in this goal because the equilibrium queue length strongly depends on the number of active TCP connections and first proposed a simple Control Theoretic Approach, DRED randomly discard packets with a load-dependent probability when a buffer in router gets congested and is able to stabilize a router queue occupancy at a level independent of the number of active TCP connections which results in high resource utilization, bounded delays, more certain buffer provisioning and traffic-load-independent network performance. Hollot et al [13] (2002) analyzed a combined TCP and AQM model from a control engineering standpoint and uncovered limitations of the averaging algorithm in RED. Further they proposed and designed two alternative AQM controllers, first one was ‘proportional controller’ which showed good transient response but suffered steady-state errors in queue regulation, second one was ‘PI controller’ which exhibited better performance under all cases considered. Ren et al [40] (2005) found that almost all the existing AQMs schemes neglected the impact of large delay on their performance and they first showed an unexpected dramatic oscillation appear in the queues controlled by several popular AQM schemes, including RED, PI controller and REM, in large delay networks. With appropriate model approximation, they design a robust AQM controller ‘DC-AQM’ to compensate for the delay
using the principle of ‘internal mode compensation’ in control theory and found that DC-AQM algorithm is superior to other algorithms for large delay and small reference queue length.
Chang et al [26] (2006) proposed a queue-based adaptive PI controller ‘Q-SAPI’ for AQM with a aim to improve the transient performance of the fixed-gain PI controller while maintaining its steady-state performance over a wide range of uncertainties and showed its versatile ability in addressing the tradeo ff between responsiveness and small steady-state error under the dynamic network and tra ffi c conditions. Wang et al [41] (2007) proposed a novel AQM method ‘LRED” which first incorporated packet loss ratio as a complement to queue length for congestion estimation and further they found that the use of packet loss ratio enables LRED to catch network dynamics in time, thus achieving fast control response and better performance in terms of goodput, average queue length, and packet loss ratio.
Wang et al [42] (2008) have focused on the problem of the stability of congestion control for networks with large round-trip communication delays and commented that nearly all the existing AQM schemes neglected the impact large communication delay has on system behavior, such as stability, robustness and convergence which results in low link utilizations and/or high delay jitters. To address the congestion control stability issue they proposed a congestion controller, called ‘IMC-PID’ which was able to restrict the negative impact on queue stability caused by large delay. Wang et al [43] (2008) further proposed a novel AQM based on the ‘optimized-second-order-system’ model, called Adaptive Optimized Proportional Controller(AOPC) which is more responsive to time varying network conditions than other algorithms and achieve the best tradeoff between utilization and delay.
Kim et al [44] (2011) have proposed a novel scheme which consists of a multilevel caching approach which detect high-bandwidth flows accurately with minimal overhead; and a drop policy for achieving both flow fairness and queue-length stability simultaneously. Santi et al [18] (2011) first introduced a novel optimal AQM approach to operate in large bandwidth-delay product networks which uses HSTCP as its transport protocol. Zhou et al [45] (2013) have given a novel robust active queue management scheme based on H-infinity feedback control theory for the Internet TCP flow model.
For the purpose of our study and based on the above discussion, we propose here a revised taxonomy of Router based Congestion control approaches as in Fig.1.
-
B. Relative Comparison of various router based approach
Sun et al [14] have emphasized that heuristic based approach like RED is the most prominent and widely studied AQM. However, it is very difficult to parameterize RED in order to obtain good performance under different congestion scenarios. Ren et al [40] commented that the algorithm design based on theoretical analysis and evaluation should be more reliable than one originated from intuition. Control theoretic efforts are very valuable for understanding the performance of congestion control algorithm comprehensively.Chang et al [26] found that Control theoretic approaches have been widely used to analyze and design mechanisms to improve the performance of various software systems [4]. The main reason is that this kind of approach enables the analysis and design for meeting desired steady-state and transient performance goals [13]. RED follows heuristic approach. The disadvantage of designing in an ad hoc way is that very little is known about why these AQMs work and very little explanation is given when they fail. Wang et al [43] commented that a control theoretic approach gives a framework for network researchers to design an AQM controller to regulate the system. Pi, PID, LRED controllers indeed enhances the performance in wide network scenarios; however, the connatural demerit of these controllers is that the control parameters are configured in particular network scenarios so that they lack of flexibility. The strong correlation between the control parameters and network parameters makes these controllers be prone to be unstable.
Santi et al [18] pointed that while using heuristic approach, efficient parameter setting is a major challenge. When threshold values are not correctly defined, the performance of RED can be even worse than that of the traditional tail drop policy mechanism. To overcome this difficulty, numerous studies based on heuristics have been conducted [46, 47]. Nonetheless, these studies neither assure that an equilibrium point can be reached nor guarantee stability of queue length. Various studies have been conducted in an attempt to derive an adequate configuration of RED parameters in a systematic way [13, 48]. One of these approaches is the use of Control Theory to design AQM policies that ensure stability about an equilibrium point.
Santi et al [18] emphasized that the advantage of the use of control theoretic policies is that they consider the intrinsic nature of feedback in network congestion. In these policies, controllers are responsible for determining the appropriate values of the drop/mark probability so that the queue length will stabilize independent of network conditions.Active Queue Management controllers based on Control Theory are defined to overcome the difficulties in tuning AQM parameters. The design of the controller takes into consideration a detailed description of the system, assuring system stability under various network conditions.
From the above discussion it is clear that control theoretic approach of designing router based congestion control algorithms prove its importance as compare to other approaches and is accepted as a major dimension of research by the academicians and practitioners because of its relative advantages.
-
C. Performance parameters Analysis
Performance parameters considered for router based congestion control techniques are listed in the Table 1.
It can be observed Table-1 that the three performance parameterspacket loss rate, queue length and queuing delay have considered most important parameters while designing end to end based congestion control algorithms. Queuing delay and packet loss rate are the performance metrics which affects the QoS of multimedia traffic. There is a direct relationship between the queue length and packet loss rate as larger the average queue size higher the packet loss rate. Loss rate is defined as the number of dropped packets divided by the total number of packets arrived at the router's input ports. Router output queue length variation is examined over time, in order to measure the average queuing delay and its standard deviation. Minimizing average queuing delay is an important goal for real-time applications. On the other hand, the standard deviation gives a measure of the jitter at the destination hosts which is considered as an important metric for audio/video play back applications.
The metric goodput reflects the best use of the available router resources and can be defined as the bandwidth delivered to all the receivers, excluding duplicate packets.Fairness against nonresponsive flows plays an important role while evaluating a AQM approach. Since an AQM mechanism is a sort of congestion control mechanisms, it needs to have robustness over network failures. Namely, even if a network failure occurs, it is desirable for an AQM mechanism to continue its operation. Generally, it is also desirable for congestion control of an AQM mechanism to be decentralized and distributed. Since, for example, other network devices may break down, control information that an AQM mechanism uses may not arrive on time. Even in such a case, the AQM mechanism should operate without serious trouble.
Queue stability is a desirable feature of an AQM policy since it helps in minimizing the packet loss rate.From the viewpoint of Internet serviceproviders, maintaining queue-length stability is also important for maximizing link utilization with reduced buffer requirements [38].Maintaining stable queue length at a link is critical for improving service quality as well as increasing utilization and decreasing buffer cost. With a stable queue, a flow may exhibit a stable delay with a low jitter as well as a stable loss rate.
Implementation complexity plays an important role while deployment of AQM method in actual network environment.
Following tradeoffs are observed in parameters of router based congestion control algorithms.
TABLE II. List of observed tradeoffs between performance parameters
Parameters having trade off in Router based Approaches |
References |
goodput and queuing delay |
[35], [22] |
link utilization and queue length |
[30] |
link utilization and queuing delay |
[25], [33], [43] |
goodput and queue length |
[41] |
-
VII. CONCLUSION
This work explores the literature review of router based congestion control algorithms in the context of wired networks. We understand that the identified issues and challenges regarding the router based congestion control algorithms may help in future research in this area. This initial proposition of such a review may be purposefully used by the academician/researchers and the corresponding useful feedback may be analyzed.
Список литературы A Review of Router based Congestion Control Algorithms
- D. Papadimitriou, "RFC6077 - Open Research Issues in Internet Congestion Control", RFC, Internet Engineering Task Force, February 2011.
- B. Braden et al., "RFC2309 - Recommendations on Queue Management and Congestion Avoidance in the Internet," IETF RFC, April 1998.
- C. Yang and A. Reddy, "A Taxonomy for Congestion Control Algorithms in Packet Switching Networks," IEEE Network Magazine, vol. 9, no. 4, pp. 34–45,1995.
- [M. Labrador and S. Banerjee, "Packet dropping policies for ATM and IP networks," Communications Surveys & Tutorials, IEEE, vol. 2, no. 3,pp. 2–14, 1999.
- S. Ryu, C. Rump, and C. Qiao, "Advances in Internet congestion control," Communications Surveys & Tutorials, IEEE, vol. 5, no. 1, pp. 28–39, 2003.
- G. Chatranon, M. A. Labrador, and S. Banerjee, "A survey of TCP friendly router-based AQM schemes," Computer Communications, vol. 27, no. 15, pp. 1424–1440, 2004.
- S. Ryu, C. Rump, and C. Qiao, "Advances in active queue management (AQM) based TCP congestion control," Telecommunication Systems - Modeling, Analysis, Design and management, vol. 25, no. 3-4, pp.317–51, 2004.
- G. Thiruchelvi, J. Raja, "A survey on active queue management mechanisms," International Journal of Computer Science and Network Security, VOL.8 No.12, pp. 130–145, 2008.
- E. Chandra and B. Subramani, "A Survey on Congestion Control," Global Journal of Computer Science and Technology Vol. 9 Issue 5, Verion 2.0, January 2010.
- Richelle Adams, "Active Queue Management: A Survey", Communications Surveys & Tutorials,IEEE , vol. PP, no. 99, pp. 1–52, 2012.
- S. Keshav, "What is congestion and what is congestion control", Presentation at IRTF ICCRG Workshop, PFLDnet 2007, Los Angeles (California), USA, February 2007.
- L. Su and J. Hou, "An active queue management scheme for internet congestion control and its application to differentiated services," in Proc. IEEE ICCCN, Oct. 2000.
- C. V. Hollot, V. Misra, D. Towsley, and W. B. Gong, "Analysis and design of controllers for AQM routers supporting TCP flows," IEEE Trans. Automatic. Control, vol. 47, pp. 945–959, June 2002.
- J. Sun, K.T. Ko, G. Chen, S. Chan, and M. Zukerman, "PD-RED: to improve the performance of RED," IEEE Communications Letters, vol. 7, no. 8, pp. 406–8, 2003.
- S. H. Low, "A duality model of TCP and queue management algorithms," IEEE/ACM Trans. Netw. vol. 11, pp. 525–536, Aug. 2003.
- F. Paganini, Z. Wang, J. C. Doyle, and S. H. Low, "Congestion control for high performance, stability and fairness in general networks," IEEE/ACM Trans. Netw., vol. 13, no. 1, pp. 43–56, Feb. 2005.
- B. Sonkoly, B. Simon, T. A. Trinh, and S. Molnar, "A research framework for analyzing high speed transport protocols based on control-theory," International Journal of Network Protocols and Algorithms, vol. 1, no. 2, pp. 1–26, Dec. 2009.
- J. D. Santi, N. L. S. Fonseca. "Design of optimal Active Queue Management controllers for HSTCP in large bandwidth-delay product networks," Computer Networks: the International Journal of Computer and Telecommunications Networking, 55, pp. 2772-2790, 2011.
- L. Xue, C. Cui, S. Kumar, and S.-J.Park, "Experimental evaluation of the effect of queue management schemes on the performance of high speed TCPs in 10Gbps network environment," in Proc. of IEEE ICNC, 2012.
- A. Eshete, Y. Jiang, and L. Landmark, "Fairness among high speed and traditional TCP under different queue management mechanisms," In Proceedings of the ACM Asian Internet Engineering Conference (AINTEC), pp. 39–46.2012.
- J. Hong, C. Joo and S. Bahk, "Active queue management algorithm considering queue and load states," Computer Communications 30 (2007) 886- 892, November 2006.
- S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Transactions on Networking, vol. 1, no. 4, pp. 397–413, 1993.
- R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, a stateless active queue management scheme for approximating fair bandwidth allocation," In Proceedings of IEEE INFOCOM‟00, Tel Aviv, Israel, March 2000.
- . Aweya, M. Ouellette, and D. Y. Montuno, "A Control Theoretic Approach to Active Queue Management," Computer Networks, vol. 36, no. 2–3, 2001, pp. 203–35.
- W. Feng, D. Kandlur, D. Saha, K. Shin, "Stochastic Fair Blue: A Queue Management Algorithm for Enforcing Fairness", in Proc. of INFOCOM 2001, April 2001.
- Chang, J.K. Muppala, "A stable queue-based adaptive controller for improving AQM performance,"Computer Networks, 50 (13), pp. 2204–2224, 2006.
- J. Wang, L. Rong and Y. Liu, "Design of a stabilizing AQM controller for large-delay networks based on internal model control," Computer Communications, 31(10): pp. 1911-1918, 2008.
- Y. Jing, H. Wang, G.M. Dimirovski, X. Liu, "Robust H-infinity control for uncertain time-delay TCP/AQM network system," in Proceedings of the Conference on Decision and Control, pp. 1428–1433, 2004.
- V. Jacobson, "Congestion avoidance and control," ACM SIGCOMM, pp. 314–329, 1988.
- S. Kunniyur and R. Srikant, "Analysis and design of an adaptive virtual queue (AVQ) algorithm for active queue management," Computer Communication Review, vol. 31, no. 4, pp. 123–34, 2001.
- M. Chan, M. Hamdi, "An Active Queue Management Scheme Based on a Capture–Recaptured Model", IEEE J. Select.Areas Commun. 21 (4), May 2003.
- A. Kamra , H. Saran , S. Sen and R. Shorey , "Fair adaptive bandwidth allocation: a rate control based active queue management discipline," Computer Networks, vol. 44, no. 2, pp.135 -152, 2004.
- C. Long, X. Guan, B. Zhao, and J. Yang, "The Yellow active queue management algorithm," Computer Networks, vol. 47, no. 4, pp. 525– 50, 2005.
- S. Liu, T. Bas¸ar, and R. Srikant, "Exponential RED: A stabilizing AQM scheme for low and high speed TCP," Trans. Netw., vol. 13, pp. 1068–1081, 2005.
- C. Wang, B. Li, Y. T. Hou, S.Kazem& K. Long, "A stable rate-based algorithm for active queue management," Computer Communications, 28(15), 1731–1740, 2005.
- J. Hong, C. Joo& S. Bahk, "Active queue management algorithm considering queue and load states," Computer Communications, 30(4), 886–892, 2007.
- B. Abbasov and S. Korukoglu, "Effective RED: An algorithm to improve RED's performance by reducing packet loss rate," Journal of Network and Computer Applications, 32 (3): pp. 703-709, 2009.
- J.Kim, H. Yoon, I. Yeom, "Active Queue Management for Flow Fairness and Stable Queue Length," IEEE Transactions on Parallel and Distributed Systems, vol. 22, No. 4, pp. 571-579, April 2011.
- D. Lapsley and S. Low, "Random Early Marking: an Optimization Approach to Internet Congestion Control," in IEEE ICON, 1999.
- F. Ren, C. Lin, B. Wei, "A robust active queue management algorithm in large delay networks" Comput.Commun., 28, pp. 485–493, 2005.
- C. Wang, J. Liu, B. Li, K. Sohraby and Y. T. Hou, "LRED: A Robust and Responsive AQM Algorithm Using Packet Loss Ratio Measurement," IEEE Trans. Parallel and Distributed Systems, 18(1): pp. 29-43, 2007.
- J. Wang, L. Rong and Y. Liu, "Design of a stabilizing AQM controller for large-delay networks based on internal model control," Computer Communications, 31(10): pp. 1911-1918, 2008.
- J. Wang, L. Rong, Y. Liu, "A robust proportional controller for AQM based on optimized second-order system model," Computer Communications 31, pp. 2468-2477, 2008.
- J. Kim, H. Yoon, I. Yeom, "Active Queue Management for Flow Fairness and Stable Queue Length," IEEE Transactions on Parallel and Distributed Systems, vol. 22, No. 4, pp. 571-579, April 2011.
- C. Zhou, J. He, Q. Chen, "A robust active queue management scheme for network congestion control," Computers & Electrical Engineering, Volume 39, Issue 2, February 2013, Pages 285-294.
- S. Floyd, RED: Discussions of Setting Parameters, 1997. http://www.icir.org/floyd/REDparameters.txt.
- W. Feng, Improving Internet Congestion Control and Queue Management Algorithms, Ph.D. Thesis, University of Michigan, USA, 1999.
- K. Zhou, K.L. Yeung, V.O. Li, Nonlinear RED: a simple yet efficient active queue management scheme, Comput. Networks 50 (18) (2006) 3784–3794.