Queueing systems with different types of renovation mechanism and thresholds as the mathematical models of active queue management mechanism

Full Text

Introduction In modern communication networks the problem of congestion avoidance does not have a satisfying solution [1] and the development of active queue management (AQM) algorithms appears to be the actual task for researches and practitioners. A numerous number of AQM schemes have been proposed [2], some of them were investigated and standardised by IETF working group on “Active Queue Management and Packet Scheduling” [3]. For the most AQM algorithms models the performance analysis is performed by simulation (for example, [2]) and that is why the bridges between the available use-case results and the available analytic results are very few (see, for example, [4]-[7]). In this paper the mathematical models of RED-like ( in contrast to standard RED algorithm, when a possible reset occurs at the time of the next packet arrival and the control parameter is an exponentially weighted average queue length [8]-[10], in our models the decision about a possible packet drop is made at the momemnts of service completions) algorithms with renovation and one or several thresholds (which determine not only the place in the buffer from which the packets are dropped, but also the place to which the reset of packets occurs). The structure of the article is following. The section 2 gives the brief description active queue algorithms, especially of the classic RED algorithm. The section 3 consists of foyr subsections: in 3.1 the definitions of different types of renovation are given as well as a brief overview of queueing systems with renovation; in 3.2 the models with renovation and a single thresholds are described; the subsectionn 3.3 is devoted to models with renovation and two thresholds (for one of these models some analitycal results are presented); the last subsection 3.3 describes renovation models with three thresholds. In section 4 the comparison of results for RED algorithm and some renovation models is presented, based on experimental results from [11]-[13]. These results confirm assumptions that the use of the renovation mechanism in the single server queues under heavy overload conditions and some other constraints allows one to achieve at least the same performance level as by the classical random early detection algorithm. The last section 5 concludes the paper with the short discussion. Active queue management algorithms. The brief description of RED algorithm module According to RFC 7567 [1] active queue management (AQM) is considered as a best practice of network congestion avoidance (reducing) in Internet routers. The active queue management is the policy of dropping packets inside a buffer associated with a network interface controller (NIC) before that buffer becomes full (or gets close to becoming full) and this policy is based on some rules (algorithms ) such as: Random Early Detection (random early discard or random early drop) (RED) [8]-[10], [14] - is a queuing discipline for a network scheduler suited for congestion avoidance by pre-emptively dropping packets before the buffer becomes completely full based on predictive models to decide which packets to drop; Explicit Congestion Notification (ECN) [9], [15] and its modifications [16]- [19] - allows end-to-end notification of network congestion without dropping packets (opposed to RED); controlled delay (CoDel) [20] and its modifications [21], [22] - a schedul- ing algorithm for the network scheduler, designed to overcome bufferbloat in networking hardware by setting limits on the delay network packets experience as they pass through buffers in this equipment; BLUE [23] and its modifications [24]-[26] - operates by randomly dropping or marking packet with explicit congestion notification mark before the transmit buffer of the network interface controller overflows and it requires little or no tuning to be performed by the network administrator; CAKE (Common Applications Kept Enhanced)[27], [28] - is a shaping- capable queue discipline which uses both AQM and FQ, itcombines COBALT, which is an AQM algorithm combining Codel and BLUE Early AQM disciplines (notably RED and SRED) require careful tuning of their parameters in order to provide good performance, but modern AQM disciplines (Blue, CoDel, CAKE and new modifications of RED - the overview may be seen in [29], [30]) are self-tuning, so they can be run with their default parameters. The classic RED [8] is an active queue management algorithm with two thresholds (

About the authors

Hilquias Viana Carvalho Cravid

Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: hilvianamat1@gmail.com

post-graduate student of Department of Applied Probability and Informatics

6, Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Ivan S. Zaryadov

Peoples’ Friendship University of Russia (RUDN University); Institute of Informatics Problems, FRC CSC RAS

Email: zaryadov-is@rudn.ru

Candidate of Physical and Mathematical Sciences, assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

6, Miklukho-Maklaya St., Moscow, 117198, Russian Federation; 44-2, Vavilova St., Moscow 119333, Russian Federation

Tatiana A. Milovanova

Peoples’ Friendship University of Russia (RUDN University)

Email: milovanova-ta@rudn.ru

Candidate of Physical and Mathematical Sciences, lecturer of Department of Applied Probability and Informatics

6, Miklukho-Maklaya St., Moscow, 117198, Russian Federation

References