Genetic algorithm-based congestion control optimisation for mobile data network

With the fast development of mobile devices and network, the mobile data network has become the main way to access Internet. According to CNNIC 47th Inter-Network Development Statistical Report [1], until December 2020, the Chinese netizen scale had reached to 989 million, among which 986 million users were mobile phone netizens, accounting for 99.7%, and three basic intercommunication enterprises had developed cellular IoT end-users of approximately 1.136 billion. At present, the network flow demands of videos, games and live streams are rocketing, and these applications need to interact with many users in real time and maximally improve video and image quality, i.e. providing high-quality services. Compared with the wired network, transmission control protocol (TCP) shows significant performance degradation in the wireless network. In a mobile scene, the state of the cellular network is subject to the impact of location change, i.e. mobility impact, leading to unstable link [2, 3]. Even within a very short time, the state of the cellular network can also change greatly. However, traditional TCP was originally designed for a wired network with stable and reliable link, and it performed well in that environment. When it works in a mobile data network, TCP congestion control algorithm shows poor performance [4]. So, it is particularly important to improve the performance of the TCP congestion control algorithm in the mobile data network.

TCP Vegas [5] is a congestion control algorithm used to measure the network state based on round-trip time (RTT). Through calculating the difference between expected and real transfer rates, this algorithm compares the difference with the lower limit α and upper limit β of two threshold parameters and roughly judges whether the network sending rate is too quick or too slow so as to adjust congestion window (cwnd). If the difference is greater than the upper limit, the congestion control window should be reduced; but if the difference is less than the lower limit, then the congestion control window should be increased to prevent the situations of network congestion, which resulted from excessive data packages in links, and network throughput decline resulted from too less data packages, thereby enhancing bandwidth availability rate of communication links. However, the values of parameters α and β were selected and fixed for the wired network and defaulted as 2 and 4, respectively, which could not be adapted to mobile cellular networks with large bandwidth fluctuation. That is to say, Vegas has a ‘one-size-fits-all’ reaction to all network environments.

NSGA-II [6] was proposed by Srinivas and Deb [7] to analyse and solve the maximised and minimised multi-objective optimisation problem, which was an improvement to the non-dominated sorting genetic algorithm (NSGA). Parent population and progeny population are combined into one population, which is then quickly non-dominantly sorted for Pareto rank sorting, until some individuals of a certain level could not be put into the next generation completely. Then, the individuals of this level that could not be put into the next generation are calculated for congestion degree, ranked from large to small, and put into the next-generation population in sequence, until they satisfy the number of next-generation population. This is actually a cyclic iteration. NSGA-II overcomes the disadvantages of NSGA, such as lacking elitist strategy, having higher computing complexity and needing to manually determine shared parameters. It is a mature multi-objective optimisation algorithm widely used in the multi-objective optimisation field, and the Pareto optimal solution set can be found in the multi-objective optimisation problem.

In view of above analysis, TCP Vegas parameters were studied and discovered that changing Vegas parameters properly can promote QoS for mobile data network; so, the optimisation of TCP Vegas’s QoS under mobile date network was modelled as a multi-variable multi-objective optimisation problem. To find the solution by the NSGA-II algorithm, it was first to build a mathematical model taking throughput and queuing delay as optimisation objectives, various norms and restrictions as dominant punishment and Vegas parameters α and β as decisive variables. Then, the network topology structure of ns-3 was constructed, and Mahimahi mobile data network was used for optimised simulation. Finally, this model was solved to obtain a Pareto solution set, which was further analysed and selected for promoting QoS’s parameter set. The optimal parameters α and β can be found out, making Vegas to show a better QoS performance under mobile data network.

The NSGA-II algorithm adopts fast dominant sorting. Compared with the traditional genetic algorithm, the NSGA-II algorithm has the following three advantages: (1) It uses fast non-dominant sorting method, which reduces computing complexity from O(MN³) to O(MN²) and expands population amount, making it possible to retain more excellent individuals. M is the generation number of a population and N is the individual quantity in each generation of population; (2) The concept of congestion is introduced, avoiding an artificial selection of shared parameters; (3) The elite strategy is introduced to ensure excellent individuals do not miss and guarantee the individual quality of population [11].

The solution by using the NSGA-II algorithm mainly includes the following steps: first, determine the population scale N and immediately generate the initial population P₁, and then, the individuals of P₁ are quickly non-dominantly sorted. Later, such genetic operators as selection, cross-over and mutation are used to produce progeny population S₁. Parent population and progeny population are then mixed to generate a new population R₁, and the individuals of this new population are quickly non-dominantly sorted to obtain a Pareto sequential set sorted from lower to higher levels, i.e. F1,F2,⋯,Fn, . According to the sorting results, individuals are put into the new-generation parent population P₂ in sequence, until F1+F2+⋯+Fj−1<N and F1+F2+⋯+Fj≥N . The individuals of F_j are calculated for congestion degree and sorted from large to small (when equality holds, it is not needed to sort by congestion) and then put in sequence to generate a new-generation parent population P₂, until the size of P₂ increases to N. Repeat this operation of mixing parent population P_i with progeny population S_i to generate a new-generation parent population P_i+1, until i reaches the maximum iteration number max [12]; then, iteration is stopped to obtain the Pareto solution.

Take TCP Vegas parameters α and β as chromosomes, and every one chromosome is a population individual. Set initial population scale as 10, that is to say, generate 10 groups of α and β values within the restraint scope, such as [1, 3]^T, [3, 5]^T, etc. Then, make the crossover operator to randomly select mean value or mean deviation so as to generate new chromosome and randomly endow an individual with new value to generate mutation. Input parameters α and β in the form of chromosome in every iteration obtain the target value of given parameter through ns-3 and represent dots in the target space coordinate system. Finally, calculate the congestion degree of multiple points in target space, complete non-dominant sorting and generate Pareto leading edge. The specific algorithm flow is shown in Figure 1.

Fig. 1

The ns-3 [13] is a discrete event network simulator mainly used for scientific research and education fields. It is written by C++ and can take C++ and Python languages to write a script. As one of the most popular simulators now, ns-3 provides abundant network models, including multiple network protocols (TCP, UDP, etc.) as well as communication technologies. Furthermore, ns-3 can also interact with external systems and actual application and conduct joint simulation with other platforms, which provides great possibility for obtaining truthful data.

The ns-3.30 version is selected in simulation experiment, the installation environment is ubuntu20.04 Linux operating system and the kernel version is 5.8.0-63-generic. In ns-3 software, a point-to-point network topology was built for simulation experiment, and the node0 and node1 were taken as source nodes to bind TCP Vegas source agency. The link queue management mechanism adopts DropTail, and the link bandwidth is mobile network data trace with single-direction dissemination delay of 50 ms and data package of 1500 bytes to simulate the network congestion process under mobile data network. Finally, the average throughput and average queuing delay were obtained [14, 15].

Taking Mahimahi downlink trace to serve as link bandwidth, for example, these traces were collected during driving [16], totalling to 3022 s, under a bandwidth range of 0–20 Mbps and average bandwidth of 8.5 Mbps. These traces represent the time-varying bandwidths of cellular network experienced by mobile users, and each line of the traces gives a timestamp in millisecond and represents that a data package of 1500 bytes exits the queue and crosses over the link. If more than one data packages of 1500 bytes are transmitted in specific millisecond, then multiple lines will repeat the same timestamp. Because the shortest is 120 s in Mahimahi, all traces are cut into 120 s, and 120 s is taken as a trace file. All trace data of <120 s are round off. Every 100 ms, the average bandwidth of 100 ms in trace is updated as link bandwidth.

Pymoo [17] is a Python-based open-source software package supporting multiple optimisation functions, which is used to customise and analyse the optimisation model. Pymoo can be applied to define the symbol problem and create a specific problem instance, such as linear programming and quadratic programming, and uses a standard procedure to resolve these instances. It is an effective framework to solve and analyse multi-objective optimisation problems. We combined Pymoo’s NSGA-II algorithm and ns-3’s network topology and set optimal front-end individual number as 10, population size as 10 and the maximum evolutionary generation number as 4. Then, we wrote multi-thread code with the maximum thread of 16. When it reached to the maximum evolutionary generation number, we quit the calculation and drew the Pareto solution set distribution chart. Because the initial population of algorithm is generated randomly, the results are different in every operation.

In Table 1, the first line shows the result of average throughput and queuing delay under defaulted parameter values, and rest lines show the points of Pareto optimal solution set. It can be seen that as average throughput increases, average queuing delay will also rise. The QoS of Vegas-NSGA-II can be evaluated from two aspects: average throughput f₁ and average queuing delay f₂. The results can be divided into two categories: one can result in high throughput, and the other can lead to low delay. Optimal parameter combination should be selected according to practical QoS requirements. In Pareto solution set, if throughput is >4 Mbps and queuing delay is <60 ms, then we consider it as high throughput, low delay and good QoS performance. Figure 2 shows the Pareto leading edge with horizontal ordinate as a reverse scale, and it is believed simply that the closer a point is to the left bottom, the better its QoS will be. When α = 8, β = 15 and α = 3, β = 4, both of them meet the needs of high throughput and low delay. In Figure 3, the result of red ordinate is a result of defaulted parameter values. Comparing optimised results with defaulted parameter results, the optimised Vegas obtains an average throughput increased by 1.15 Mbps when maintaining a low delay, and throughput can be promoted to a greater extent when insignificantly increasing the delay. This greatly improves the user QoS under mobile data network.

Fig. 2

A simulated experiment was conducted in the mobile data network. The results indicate that (1) NSGA-II can be combined with the TCP Vegas congestion control algorithm effectively to guarantee obtaining an optimal target QoS under changeable network conditions and meeting user demand and (2) ns-3 can be deemed as a black box function. In the mathematical model, the target function is not a specific mathematical expression and does not concretely analyse the internal receiving, sending and missing packages in ns-3 simulation for optimising QoS; (3) this method can be extended and applied to other congestion control algorithms. Since it comprehensively considers multiple variables and targets during optimisation, it provides a new idea and approach for optimising the network congestion control algorithm.