Designing optimal rate allocation algorithms based on utility function in data networks

Faculty of Electricity and Computers

Doctoral Dissertation in Electrical Engineering

Abstract:

The purpose of this thesis is to improve the performance of optimal rate allocation algorithms based on the utility function in data networks. The optimal rate allocation algorithm based on the utility function was first proposed by Dr. Golestani. Then Kelly showed that it is possible to convert the optimal rate allocation problem into two simpler sub-problems, one of which is solved by the network and the other by the users, and he showed that the network problem is actually a rate allocation problem with a proportional justice criterion and has many advantages, including the similarity with the congestion control algorithm in TCP/IP (AIMD method) and also the stability and convergence of the algorithm Math showed. But at the same time, Kelly's algorithm has some limitations, including the problem of scalability, low convergence speed, and high computational overheads. In this treatise, we will introduce two hierarchical algorithms, a fuzzy algorithm and a hybrid fuzzy-hierarchical algorithm with the aim of solving the above-mentioned defects in order to achieve rate allocation methods with higher convergence speeds while maintaining proportional justice. In addition, the mathematical analysis of the stability of the proposed algorithms, the analysis of the behavior of hierarchical algorithms in the presence of background traffic with a variable rate, and the analysis of the phenomenon of users entering and exiting the system are among the other things that will be examined in this treatise.

Introduction

In general, quality of service 1 is the ability that the network has in distinguishing between different types of services and traffic classes in such a way that users who are in a Traffic classes are placed, depending on their needs, they can observe different performance of the network compared to other types. Among the ways to support the quality of service, we can refer to various methods of rate control and congestion control2.

Rate control and congestion control methods are used in computer networks in order to control traffic in the networks and divide the bandwidth, taking into account the assumed fairness criteria.

Rate control is a set of methods used by the network to control the input rate to the network, while congestion control is the application of some controls on the input. which have caused network buffers to be filled.

In a general classification, congestion control in data telecommunication networks is done in two ways. Window-based methods in which the number of packets in the network is set to a certain limit by intelligently controlling a window called the congestion window4 [6,5,4,3,2,1] and rate-based methods in which the traffic in the network is looked at as a liquid flow and with specific algorithms, an attempt is made to allocate rates to network users in such a way that justice is observed in allocating rates to users. [11,10,9,8,7].

Several criteria have been introduced to implement this justice, the most prominent of which are maximum-minimum1, proportional2, and minimum potential delay3 criteria [14,13,12].

Mo and Walrand in [13] have investigated the justice criterion (W,a) and have shown that all the mentioned justice criteria can be considered as special cases of the general justice criterion. (W,a) obtained.

With the research conducted in the field of congestion control and rate allocation algorithms, it has been concluded that any algorithm that is used for congestion control or rate allocation should be implemented in a distributed manner at the network level as much as possible, because otherwise, if the algorithm is implemented centrally, as the network dimensions increase, a significant computational load will be applied to the central processor, and in addition, in the event of a malfunction in this processor, the behavior of the entire system will be disturbed. And it becomes a mess, while in a distributed algorithm, the responsibility of rate allocation and congestion control is placed on all network nodes and end users, and the creation of an error or defect in a part of this distributed system will not have a great impact on the behavior of the entire algorithm.. For this reason, researchers such as Bertsekas [15] and Gallager [16] have tried to push rate allocation algorithms towards distributed and widespread algorithms at the network level.

The initial idea of ??implementing the rate control problem as a general optimization problem has been proposed by S.J. Golestani [17] and after him, many researchers have tried to develop existing methods to allow users on the network level to access optimal rates with distributed methods.

The main work of these researchers can be generally divided into two main categories. In the first category, researchers such as S. Low in [18,19] have tried to turn the optimization problem into a widespread problem at the network level by using duality theory [15] in which end users and network links are able to solve the general optimization problem by exchanging some information with each other and even these researchers in [18] have tried to prove the stability of their distributed algorithms with the help of mathematical methods and in practice how to implement such algorithms in the ATM 5 network. [21,20] and for the ABR service available in it, it has been investigated and analyzed using the facilities provided by this service.

Researchers who are in the second category of the above division try to solve the problem of optimal rate allocation with the general optimization theory by using methods based on the penalty function [15], which includes the research done in [24,23,22,10,8,7] pointed out.

Of course, it is necessary to explain, there are also researchers who have tried to solve the problem of general optimization of rate allocation by using methods different from the above two general methods. For example, Ba?ar et al. T. in [25] and R. Srikant et al. In [8], they have tried to analyze the rate allocation optimization problem with the help of game theory.

Among the most important methods of the second category, we can refer to the research results in [7]. Kelly et al. In [7], in addition to implementing an extensive algorithm at the network level, they have tried to achieve the criterion of proportional justice. Among the most important features of this criterion, its proximity to the well-known congestion control method in the Internet by Jacobson et al. It is presented in [26]. Among other outstanding features of this algorithm, checking and proving its stability by selecting suitable Lyapunov functions.

Since the time delay in the Kelly algorithm has received less attention, R.Johari and D.Tan have done extensive research in [11] to prove the stability of the Kelly algorithm in the presence of delay and under certain conditions, and have achieved significant results, and finally, the stability of the algorithm for a general network topology and arbitrary but limited delays by L. Massoulié in [27] and S.Deb and R.Srikant is presented in [28].

The issue of user entry and exit in the Kelly algorithm is investigated in [10].

One of the most effective methods applied to avoid congestion or control it is the use of costing methods2 on network links in exchange for the traffic passing through them [31,30,29] which in this Methods Each link imposes a fee on passing users for the cumulative traffic that passes through it, and this fee increases with the increase of passing cumulative traffic, and for example, in [7], such costing methods have been used in order to achieve fair and optimal rates for elastic users [32] in the network. Recently, due to the ever-increasing growth of applications on the Internet and the need for services that have specific limits for delay (or delay changes4), special attention has been paid to applying methods based on optimization and costing algorithms on real-time traffic5, and since

one of the best ways to achieve service quality in the current Internet is the use of segregated services [33], applying costing methods to segregated services [34] and costing based on priority and real-time traffic costing using the concept of effective bandwidth 2 [35] are important current research fields and many researchers around the world are engaged in research in this field. It is based on utility function 3 in data networks.