DonNTU   Masters' portal

Abstract

Table of contents

Introduction

Uneven growth data channels rate inevitably leads to the emergence of "narrow" places in the telecommunication network and therefore to the appearance of overload, particularly when access networks connected to the transport network. It is the directly connected router to the data link has information about the occurrence of congestion in the channel or condition which may lead to its presence. The router evaluates the current level of congestion of the output queue and the current growth or decline in the intensity of the load, and reports TCP transmitters on the need to reduce congestion window. To explicit congestion notification by marking passing packets passing protocol ECN (Explicit Congestion Notification) is used, described in the document RFC-3168. If there is no support for ECN, then at the threat of congestion instead of marking packets can be dropped at random. Otherwise, the queue will overflow to multiple packet losses and subsequent periodic alternation of moments of overflow and router's buffer underrun.

At the moment there are a number of implementations of methods of router's queue management in networks TCP/IP, with different levels of complexity and implementation approach, the main measured parameters (size of the queue, the level of the incoming packet traffic, the loss rate, etc.), the main purpose and how it will be achieved (stabilization of the queue length at the minimum level or to ensure equality of service flows). The task of the queue management mechanisms is to encourage transfer data sources with intensity lower than that may cause congestion, i.e. coordination of dynamics of the queue, as well as reducing latency and packet drop rate effect of preventing the occurrence of lock-out.

1. Theme urgency

At this point, despite the large number of developments in this area, it is difficult to say which algorithm is used in real data networks. In fact, all they see end of this packet loss or marking ECN. The reason for this is the first, the lack of universality of algorithms, i.e., to identical performance in all types of networks and traffic patterns, for example, the dependence on the size of the buffer router delay of waiting in line, traffic load or power consumption. Second, parameter tuning algorithms that would work well for all possible situations. To effectively use the bandwidth you need to choose the queue management algorithm that will maximize use of resources and the most efficient operation of the network. Therefore there is a need to study the process of data transfer protocol such as TCP based flow control process with status queue management algorithms and analysis of the effectiveness of the algorithms under various conditions.

Because of this master thesis is devoted to the current category by developing a method for evaluating the performance router queue management algorithms. For research methods will be applied simulation with ns-2 simulator, and the methods of the theory of stochastic differential equations presented in [1]. Simulation will be conducted in a large number of nodes in the network with the use of parallel programming tools based on the technology NVIDIA CUDA [2].

2. Goal and tasks of the research

The goal of the research is to model and develop the methodology for assessing the effectiveness of the router queue management algorithms in network TCP/IP.

The main tasks of the research:

  1. Analysis of the main existing queue management algorithms, implemented in modern routers.
  2. Synthesis of the network topology and selection of the parameters of its components for modeling.
  3. The development of the mathematical hydrodynamic model for the selected queue management algorithms with constant and variable load.
  4. Simulation of the synthesized network at the selected queue management algorithms with ns-2 simulator.
  5. Simulation of the synthesized network based on the hydrodynamic model developed for the selected queue management algorithms by means of parallel programming of technology NVIDIA CUDA.
  6. Analysis of the correlation of the created models and comparative analysis of the effectiveness of the selected queue management algorithms in the synthesized network.

The object of the research: multiservice network.

The subject of the research: queue management algorithms in TCP/IP network routers.

Within the master's work are plans to achieve the actual scientific result: it will be the technique of complex evaluation of the performance of router queue management algorithms in TCP/IP networks.

3. The analysis of existing research and publications

Quite a lot of the work is devoted to the problem of modeling the process of functioning of TCP in a variety of queue management algorithms. Simplified models are presented in [3-5]. More recent and accurate (in terms of assumptions about the process of packet loss) models of functioning of TCP in the steady state are, for example, in [6-8].

At [9] it is analyzed a model for short-duration TCP-sessions, which is reflected in the strong dependence of the phase model of the connection and phase of a slow start, the average waiting time of the beginning of the packet transmission into the channel is approximated and the average packet transmission time. Model, focused on long-TCP-session study characterized the stationary characteristics in the main data transmission on stage to control congestion [10-12]. In these models, the analysis of the average capacity and the impact of the regulatory process flow status on the evolution of the size of TCP-window. In [12] analyzed a simplified model of TCP-traffic, taking into account the level of packet loss and RTT.

In many works in the construction and analysis of the models take into account the interaction of the transfer of data over TCP and control process flow status in the event of overload. As a control process algorithm is often considered RED [13] and its modifications. The most well-known classical algorithm modifications RED are following: Gentle RED (GRED) [14], Stabilized RED (SRED) [15], Adaptive RED (ARED) [16-18], Refined Adaptive RED (RARED) [18], State Dependent RED (SDRED) [19].

Various changes in classical RED, and as a result, the appearance of a large number of modifications related to the problem selection algorithm parameters (threshold values??, maximum discharge parameter, etc.) for which the system would be operated stably and efficiently. Analysis of the efficiency of the algorithm RED and trying to solve the problem by selecting its parameters are studied in [20-23].

In [24] it is shown that there is no single set of parameters RED, that works well for all possible scenarios. In this paper, an algorithm for ARED, adjusts system parameters according to the state of flow. Development of the idea of adaptive algorithms extended in [18-19].

The capacity of the system implemented in the RED algorithm was investigated in [25], in which it was shown that at high system load when the RED has a significant influence on the flow behavior, the bandwidth is inversely proportional to the parameter download.

It is shown that, the RED algorithm inefficiently allocates bandwidth in the case of different types of traffic, such as voice, video, data, etc., with different quality of service requirements. To solve this problem, [26] proposed an algorithm Fair Buffering RED (FB-RED), which is the basic idea – to use the work capacity of the delay of service to determine the reset packet. The main drawback of this algorithm is poor scalability. In [27-28], the authors demonstrate the ineffectiveness of RED algorithm for streams such as UDP provide an alternative stream-oriented version of the algorithm RED (Flow RED, FRED). The decision to drop the packet is received on the basis of statistics collected for each flow.

To solve the problem of scalability of algorithms FB-RED and FRED in the work in [15] proposed an algorithm Stabilized RED (SRED). Like the RED, algorithm discards packets depending on the load on the system, but additionally evaluates the number of active connections.

For the design and analysis of process models with data control with queue management algorithms flow rate different approaches and methods applies. For example, the model of [29] is an iterative dynamic model of the first-order discrete-time and determined by a set of difference equations. The model describes the dynamics of the system on a large range of parameter values ??RED and provides information about the occupancy of the buffer at a time. However, this model neglects the dynamics of TCP.

In [1] for a review of the interaction of multiple TCP-flow c RED was developed nonlinear dynamic model of the second order, built using the apparatus of stochastic differential equations. As the state variables were used TCP-window size and queue. In [1] as an extension of the model of [29], the authors examined the evolution of the average queue length, the equation for which is described in terms of ordinary differential equations. Qualitative analysis of the system of differential equations by the authors was not carried out to verify the simulation model was compared with the implementation on ns-2.

On the review of the researches can be made the following conclusions:

1) The interes is the investigation of the process of data transfer protocol, such as TCP, taking into account the state of the regulatory process flow using queue management algorithms such as RED, for which there are difficulties in selecting the parameters;

2) methods used for the study are simulation and/or build mathematical models for both discrete and continuous time, their analysis used different approaches and methods, such as methods of the theory of stochastic differential equations, numerical methods, the methods of the theory of stochastic processes, etc.;

3) RED algorithm modifications are quite a lot and each with its own characteristics; interest is the problem of identifying common features in these algorithms, as well as the possible causes of choosing parameters.

4. Modeling and performance evaluation of a queue management algorithms Drop Tail, RED и ARED

4.1 Analysis of the logic of the algorithms Drop Tail, RED, ARED

а) DT

The simplest scheme of the router queue management. Incoming packets are rejected only after filling the buffer, i.e. when exceeded the maximum size of the queue qmax. The probability of failure in service – two positions, its value can be 0 or 1. Therefore, the reset function for DT is described as follows:

Function for DT

where q – instantaneous queue length.

Since the algorithm only signals that the queue is full, it can be quite a long time to stay in this state and the level of network congestion can grow. Thus, due to the large size of the queue time of delivery of the package will increase. With on-off nature of the mechanism of DT leads to hesitation and unable to adapt quickly to sudden changes in the pulsating nature of the traffic. Queues have a tendency to flow maldistribution, which causes the effect of global synchronization.

b) RED

RED randomly drops or marks incoming packets when the average queue length avg exceeds the minimum threshold minth. The probability of failure increases with the average queue length up to the maximum probability of reset packet maxp. When the average queue length reaches the maximum threshold maxth, the packages are dropped. Since avg varies from minth to maxth, the probability of dropping/marking changes linearly from 0 to maxp:

Probability for RED

Final dropping probability pa slowly increases with the number of packets count, which came after the dropping of the last packet:

Probability fot RED

The average queue length, which is calculated each time you receive a new packet, is defined as follows:

Average queue size RED

where wq – weighting queue coefficient , avg – the previous value of the average queue length, q – instantaneous queue length.

Thus, the function of the droping package probability takes the form:

Probability for RED

Fig. 1 shows the described above dropping functions of algorithms:

Probability for RED

а)                                                                 б)

Figure 1 – а) dropping function for RED, б) dropping function for Drop Tail

Obviously, if wq is too large, then the averaging procedure does not consider short-term overload on the router. If you set it too low, then avg is too slow to react to changes in the current length of the queue and not be able to quickly identify the initial stage of the overload.

Parameter minth should be large enough to allow the channel to maintain the level of use at a high level, if traffic is typical pulsating. Parameter maxth is partly dependent on the maximum average delay that could allow the router. On the setting of minimum and maximum thresholds operates the following recommendation:

Рекомендация для максимального порога

Parameter maxp must be small enough, because one of the principles of the RED is not a large number of packets dropped when the average queue length exceeds the value of the minimum threshold, but only from time to time to deny some packages to get sources to reduce their transmission intensity. It is recommended to set this value as 0.1. In general, establishing the optimum set of parameter values ??RED algorithm is sufficiently complex and depends on the transmission medium used and the nature of the traffic.

According to RFC 2309, the main purpose RED algorithm is:

• reducing queuing delay and packet drop;

• maintaining a high level of utilization of the channel;

• better adaptation to the bursty traffic;

• software environment with low latency for interactive services by supporting small queue.

c) ARED

To adjust the parameters of the adaptive mechanism has been proposed ARED, which by minor changes in the original algorithm solves this problem by dynamically changing the maxp in the range of 1-50% depending on the average workload of the queue on the principle of AIMD:

Maxp for ARED

where

target for ARED
Коэффициенты для ARED

To reduce the need to adjust other parameters RED, they are also calculated automatically. Determined by the following procedures to maxth and wq:

Thresh for ARED
Weight for ARED

4.2 The mathematical description of the hydrodynamic flow model for algorithms DT and RED

To construct mathematical models of the selected queue management algorithms we use a somewhat simplified, compared to the original, the system of equations:

The equation of the sliding window
The equation of the queue
Delay

where W – the size of the sliding window TCP (packets), q – queue size (packets), R – RTT (seconds), С – channel throughput (packets/s), N – the number of TCP-sessions, Tp – propagation delay (seconds), p(t) – dropping/marking probability function.

The first equation describes the dynamics of the size of the sliding window Wi(t). It simulates the behavior of TCP type AIMD (additive-increase-multiplicative-decrease). The second equation is the behavior of the queue q(t).

Submitted hydrodynamic equations can be represented as a circuit that demonstrates the link between them two:

Communication scheme of differential equations

Figure 2 – Block-diagram of TCP's congestion-avoidance flow-control mode

In these differential equations as a function of the probability of dropping/marking perform the functions described above for the algorithms Drop Tail, RED, ARED.

4.3 Simulation of algorithms Drop Tail, RED, ARED and analysis of the results

The modeling process based on the hydrodynamic model is listed in the article published in the Library section, the results can be found on the following link.

Simulation modeling was performed using ns-2. To assess the effect of queue management algorithms, namely Drop Tail, RED, ARED, the transmission performance of the network was used to simulate the congestion in the channel between two routers, which are transmitted through multi-service traffic of 3 types: TCP-session created 20 FTP applications; CBR-and Pareto-traffic based on UDP (sources 10 and 20 respectively). Speed channel between routers is limited 0.7 Mbit/s. We used the implementation of the protocol TCP Reno. The start time for applications distributed over a uniform law. Simulation time – 50 seconds. The network topology for the simulation shown in Fig. 3.

Topology modeling

Figure 3 - The bottleneck network topology

(Animation: 6 frames, the delay between shots with the 0.8, the number of repetition cycles - 5, size 145 KB, created by mp_gif_animator.exe)

The simulation results's shown in Fig. 4 – 7.

Очередь DT

Figure 4 – Queue size for the algorithm Drop Tail

Очередь RED

Figure 5 – Queue size for the algorithm RED

Очередь ARED

Figure 6 – Queue size for the algorithm ARED

Окна TCP

Figure 7 – TCP-window size (packet/s) of the investigated algorithms

Obviously DT provides the highest level of congestion of the link, as it only sends a congestion notification (as dropped packets), while continuing to overflow buffer. All the above methods use the ECN, which causes the sources to reduce the level of the transfer, even if the loss is not observed, thus reducing the possible useful bandwidth. Since DT reset packets to a buffer overflow, it will be equal to the sum of all the maximum amount of buffer, whereas the RED/ARED already received the notifications to achieve minth. However, provide minimal, compared with DT, the delay time, as support the length of the queue at the same level to prevent buffer overruns. DT is more sensitive to pulsations of traffic, bringing more instability in the network and providing less than the fair bandwidth allocation between threads.

Conclusions

Experiments were performed in ns-2 to determine the effect of the method the queue management on network performance parameters and QoS. Implementation of ARED showed greater efficiency compared with RED and DT, eliminating their disadvantages. The complexity of the dynamic adjustment of parameters RED does not provide a strong win over the more simple DT. And there is a question of compromise between performance and delay that as long as one does not solve any of the methods.

Note

In writing this essay master's work is not yet complete. Final completion: December 2013. Full text and materials on the topic can be obtained from the author or his scientific advisor after that date.

References

  1. Misra V., Gong W., Towsley D. Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED / Vishal Misra, Wei-bo Gong, Don Towsley. – Proceedings of ACM Sigcomm, Stockholm, Sweden. – August, 2000.
  2. Сандерс Дж. Технология CUDA в примерах. Введение в программирование графических процессоров. / Дж. Cандерс, Э. Кэндрот. – М.:ДМК Пресс, 2011. – 232 c.
  3. Kosten L. Stochastic Theory of Data Handling Systems, with Groups of Multiple Sources / L. Kosten // Performance of Computer-Communication Systems, Elsevier Science Publishers B.V. – 1984. – pp. 321-331.
  4. Van Doom E.A., Jagers A.A., De Wit J. A Fluid Reservoir Regulated by a Birth-Death Process / E.A. Van Doom, A.A. Jagers, J. De Wit // Stochastic Models. – 1988. – Vol. 4(3). – pp. 457-472.
  5. Mitra D. Stochastic Theory of a Fluid Model of Producers and Consumers Coupled by a Buffer / D. Mitra // Adv. Appl. Prob. – 1988. – Vol. 20. – pp. 646-676.
  6. Misra A., Baras J., Ott T. Generalized TCP Congestion Avoidance and its Effect on Bandwidth Sharing and Variability / A. Misra, J. Baras, T. Ott // Proc. IEEE GLOBECOM. – Vol. 1. – San Francisco, CA, USA. – 2000. – pp. 329-337.
  7. Padhye J., Firoiu V., Towsley D. Modeling TCP Reno Performance: a Simple Model and its Empirical Validation / J. Padhye, V. Firoiu, D. Towsley // IEEE/ACM Trans. Networking. – 2000. – Vol. 8. – pp. 133-145.
  8. Roy R., Mudumbai R.C., Panwar S.S. Analysis of TCP Congestion Control using a Fluid Model / R. Roy, R.C. Mudumbai, S.S. Panwar // Proc. IEEE ICC, Helsinki, Finland. – 2001. – Vol. 8. – p. 2396-2403.
  9. Mellia M., Stoica I., Zhang H. TCP Model for Short Lived Flows / M. Mellia, I. Stoica, H. Zhang // IEEE Communications Letters. – 2002. – Vol. 6. – p. 85-87.
  10. Mathis M., Semke J., Mahdavi J., Ott T. The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm / M. Mathis, J. Semke, J. Mahdavi, T. Ott // SIGCOMM Corn-put. Commun. Rev. – 1997. – Vol. 27, No 3. – pp. 67-82.
  11. Misra A., Ott T.J. The Window Distribution of Idealized TCP Congestion Avoidance with Variable Packet Loss / A. Misra, T.J. Ott // INFOCOM. – 1999. – pp. 1564-1572.
  12. Altman E., Avrachenkov K., Barakat Ch. A Stochastic Model of TCP/IP with Stationary Random Losses / E. Altman, K. Avrachenkov, Ch. Barakat // SIGCOMM Comput. Commun. Rev. – 2000. – Vol. 30, No 4. – pp. 231-242.
  13. Floyd S., Jacobson V. Random Early Detection Gateways for Congestion Avoidance / S. Floyd, V. Jacobson // IEEE/ACM Transactions on Networking. – 1993. – No 1(4). – pp. 397-413.
  14. Recommandations on using the Gentle Variant of RED. [Электронный ресурс] / S. Floyd. – 2001. – Режим доступа: http://www.aciri.org/floyd/red/gentle.html.
  15. Ott Т., Lakshman Т., Wong L. SRED: Stabilized RED / T. Ott, T. Lakshman, L. Wong // Proceedings of INFOCOM'99. – 1999. – pp. 1346-1355.
  16. Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management [Электронный ресурс] / S. Floyd, R. Gummadi, S. Shenker. – 2001. – Режим доступа: http://www.icir.org/floyd/papers/adaptiveRed.pdf.
  17. Ng B.K., Ud-din M.S., Abusin A.A.Y.M., Chieng D. POWARED for Non-Linear Adaptive RED / В.K. Ng, M.S. Ud-din, A.A.Y.M. Abusin, D. Chieng // Asia-Pacific Conference on Communications, Perth, Western Australia. – 3-5 October 2005.
  18. Kim T.-H., Lee K.-H. Refined Adaptive RED in TCP/IP Networks / T.H. Kim, K.H. Lee // SICE-ICASE International Joint Conference, Bexco, Busan, Korea. – 2006.
  19. Ryoo I., Yang M. A State Dependent RED: An Enhanced Active Queue Management Scheme for Real-Time Internet Services / I. Ryoo, M. Yang // IEICE Trans. Commun. – 2006. – Vol. E89-B, No 2. – pp. 614-617.
  20. Que D., Chen Z., Chen B. An Improvement Algorithm Based on RED and Its Performance Analysis / D. Que, Z. Chen, B. Chen // IEEE. – 2008. – pp. 2005-2008.
  21. RED: Discussions of Setting Parameters. [Электронный ресурс] / S. Floyd. – 1997. – Режим доступа: http: //www.aciri.org/floyd/REDparameters.txt.
  22. Lin D., Morris R. Dynamics of Random Early Detection / D. Lin, R. Morris // Proceedings of ACM SIGCOMM, Sophia Antipolis, France. – 1997. – pp. 127-137.
  23. Estimating Arrival Rates from the RED Packet Drop History. [Электронный ресурс] / S. Floyd, K. Fall, K. Tieu. – 1998. – Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8252
  24. May M., Bolot J., Diiot C., Lyles B. Reasons not to Deploy RED / M. May, J. Bolot, C. Diot, B. Lyles // Proceedings of IWQoS'99. – 1999. – pp. 260-262.
  25. Anjurn F., Tassiulas L. Fair Bandwidth Sharing among Adaptive and Non-Adaptive Flows in the Internet / F. Anjurn, L. Tassiulas // INFOCOM. – 1999. – pp. 1412-1420.
  26. Kim W.-J., Lee B.G. The FB-RED algorithm for TCP over ATM / W.-J. Kim, B.G. Lee // IEEE GLOBECOM, Sydney, Australia.   1998.   pp. 551-555.
  27. Suter B., Lakshman T.V., Stiliadis D., Choudhury A.K. Buffer Management Schemes for Supporting TCP in Gigabit Routers with Per-Flow Queuing / B. Suter, Т.V. Lakshman, D. Stiliadis, A.K. Choudhury // IEEE J. Sel. Areas Commun. – 1999. – Vol. 17. – p. 1159-1169.
  28. Ranjan P., La R.J., Abed E.H. Bifurcations of TCP and UDP traffic under RED / P. Ranjan, R.J. La, E.H. Abed // Proc. 10th Mediterranean Conference on Control and Automation (MED), Lisbon, Portugal. – 2002.
  29. Misra V., Gong W.-B., Towsley D. Stochastic Differential Equation Modeling and Analysis of TCP-Windowsize Behavior / V. Misra, W-B. Gong, D. Towsley // Proceedings of IFIP WG 7.3 Performance – November, 1999.