{'fraction_non_alphanumeric': 0.028941060349689792, 'fraction_numerical': 0.012055837563451776, 'mean_word_length': 4.849278350515464, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Particle Swarm Optimization Algorithm for Container Deployment

In recent years, with the development of cloud computing, virtualization technology has received widespread attention. As a new representative of virtualization technology, containers have been widely used in software development, operation and maintenance, testing and other aspects, such as microservices and Docker Cloud. In cloud data centers, containers have gradually replaced virtual machines (VMs) as a new carrier for cloud tasks. However, with the increasing number of cloud products, the scale of tasks requested by users in cloud data centers continues to expand. The economic cost of tasks in the process of containerized deployment has become a concern of various cloud service vendors. The container deployment cost usually includes the data exchange cost, the image pull cost and the server energy cost. In order to solve the containerized deployment of application tasks in the container cloud environment with the lowest possible container deployment cost, this paper proposes a new cost calculation model in a container cloud environment, and then presents an improved particles swarm algorithm, namely a particle swarm optimization (PSO) algorithm for container deployment (CD-PSO) to provide the best solution for application task loading. Experimental results show that the proposed algorithm has a lower deployment cost than other scheduling algorithms.


Introduction
Containers are a group of processes running on the host operating system to provide isolated environment technology [1], [2]. It is based on the Linux kernel technology implementation [3], in which Namespce is used to isolate the environment required for program running; Cgroups implements resource control; Rootfs implements file system isolation and some container engines to manage its own life cycle. As an emerging virtualization technology, containers have many advantages in providing a working platform, such as efficient portability, small footprint and startup time of physical nodes, scalable computing resources to a smaller granularity, and simpler management. Nowadays, more and more enterprises are willing to put their business on the cloud. With its unique advantages, containers provide more efficient services for customers in terms of task execution. For large-scale, distributed data processing, however, deployment of a large number of containers on suitable servers to achieve the containerized deployment of user tasks at the lowest possible cost remains a research topic in the scientific community.
The containerized deployment of tasks refers to assigning user tasks to different server hosts in the cluster through a reasonable scheduling algorithm or policy and meeting various constraints. This consists of completing the mapping from tasks to hosts, requiring hosts to complete the pull of image ICSP 2020 Journal of Physics: Conference Series 1544 (2020) 012020 IOP Publishing doi: 10.1088/1742-6596/1544/1/012020 2 files, configuration of requested resources, and to start daemons, etc. to achieve containerization of tasks on the host. In this process, the proper scheduling of tasks is the key step for container deployment. In cloud computing, many research works on task scheduling, including applications of scheduling algorithms on container deployment, have been presented. For example, Ye Tao et al. [4] proposed a dynamic resource scheduling algorithm based on container service computing to provide the best resource allocation for each service scheduling; Kaewkasi et al. [5] proposed improvement of Container Scheduling for Docker using Ant Colony Optimization to balance use of cluster node resources; Bhiman et al. [6] developed a new docker controller for scheduling workload containers of different types of applications to helps speed-up the overall execution of multiple applications on SSDs; Wu et al. [7] proposed a flexible deferrable server scheduler to improve the performance of Docker containerized mixed-criticality real-time system, which might run applications with different criticalities as well as timing constraints; Zhang et al. [8] proposed a dynamic load balancing-based scheduling strategy for container clusters; Cerin et al. [9] proposed a new scheduling strategy based on different Service Level Agreement (SLA) classes. These scheduling algorithms and strategies solve the problems of node load imbalance, low cluster scalability, and low fault tolerance during container deployment. Aiming at reducing the cost of cloud data centers, Canosa et al. [10] proposed a scheduling strategy with energy consumption and quality of service optimization; Cheng et al. [11] used automatic scaling technology to achieve the dynamic allocation of container resources to reduce the cost of container adjustment; Wu et al. [12] proposed a lightweight cloud platform (Rattrap) and developed a new operating environment (Cloud Android Container) for mobile computing offloading, thus replacing the heavyweight virtual machines (VMs) and saving the uninstall cost caused by traditional cloud platforms. Our research also aims to reduce the cost of container cloud data centers. The main contributions of this article are two-fold. Firstly, we build a cluster environment consisting of clients, management host, and execution hosts by combining them with the cloud environment. In addition, we propose a calculation model for container deployment costs on this cluster. Secondly, we present an improved particle swarm optimization algorithm for container deployment (CD-PSO), where the novel cost model is used for performance measurement. Finally, the CD-PSO is applied to the containerized deployment of tasks.
The rest of the paper is organized as follows. Section II introduces the related work and background. Section III presents the objective function and formulation of the container deployment problem. Section IV presents the CD-PSO algorithm. Section V discusses the experiment results. Section VI concludes the work and provides possible future directions.

Related Work And Background
This section introduces the related work of reducing economic costs in the cloud environment and the background of the particle swarm optimization (PSO) algorithms.

Related work
Of long standing it remains a problem as to how to reduce the economic cost of cloud data centers. The study in [13] finds that the biggest economic cost in the data center is caused by the energy consumption of the server, while the energy consumption of the server is related to the allocation of the task carrier. In data centers that use VMs as their primary carrier, Kurpicz et al. [14] introduced a model for Energy-Proportional Accounting in VM-based Environments; Dabbagh et al. [15] proposed an energy-efficient resource allocation framework for overcommitted clouds, which monitors the VM resource usage and reducing the number of active PMs via efficient VM migration and placement; The method proposed by Sonkar et al. [16] not only improves the overall utilization of server resources, achieves the benefit of reducing costs, but also helps to combine various types of workloads; Tian et al. [17] research focuses on the energy-efficient scheduling of VM reservations in a cloud data center. On the other hand, in the cloud environment which is based on the container technology, researchers have conducted the following research to reduce costs. Al-Rakhami et al. [18] proposed a container technology named Raspberry Pi devices, which is applied to the recognition of human activities; Shi et al. [19] proposed a two-stage multi-type particle swarm optimization method (TMPSO) for ICSP 2020 Journal of Physics: Conference Series 1544 (2020) 012020 IOP Publishing doi:10.1088/1742-6596/1544/1/012020 3 energy-aware container consolidation in cloud data centers, This method can save program execution time while optimizing, but the effect of energy consumption optimization is not obvious; Hanafy et al.
[20] proposed a novel container and host selection policies for cloud deployment models, and experimentally demonstrated that the proposed policies could achieve better energy and services level agreement compared to the other competitors; Guan et al. [21] argued that the deployment cost of the same container might be different on different nodes considering image files reusing. They presented a framework for Application Oriented Docker Container (AODC) to reduce deployment costs. This solution starts a tray container for each application to better manage task execution, but it tends to occupy extra resources; Zhang et al. [22] combined container image pulling costs, the cost of node energy consumption and the workload network transition costs between clients and hosts to form an optimization problem. A linear optimization algorithm (LP) was used to find the task allocation scheme with the lowest cost. However, this solution lacks a management host to uniformly handle task scheduling, instead, it allows the client to directly contact the server.
Combining the existing scheduling strategies and the characteristics of the task containerization process, we summarize several types of costs that are easy to incur in the container deployment process: 1) The data exchange costs generated by the large amount of data transfer between hosts in the data center; 2) The image pull cost incurred in the process when a host pulls the image files from the image registry; 3) The energy cost of a host server on which the container runs. In this paper, we refer to the sum of the costs incurred during the task containerization process as the container deployment cost, which is composed of the aforementioned types of costs. This work is to explore the means of achieving the containerization of user-submitted tasks with the lowest container deployment cost. We deal the work as an optimization problem.

Background of PSO
Particle swarm algorithm [23] is a swarm intelligence optimization algorithm proposed by Ebehart and Kennnedy, which is derived from the research of bird swarm predation behavior. For each particle j, which has a position and velocity like a bird, we use vectors Xj = (xj1, xj2, ..., xji) and Vj = (vj1, vj2, ..., vji) to represent them. When the algorithm is initialized, the number of N particles are randomly generated as the effective solution of the problem in search space. With each iterative search, the particles are based on their individual optimal positions Pbestj= (pbj1, pbj2, …, pbji) and the global optimal position of the current group Gbest = (Gb1, Gb2, ..., Gbi) to update their speed and position, and after a certain number of iterations, get the final optimization result of the problem.
The speed and position update of particle j satisfy the following formula:" In the formula (1) and (2), k represents the current number of iterations of the algorithm, and Xj (k) and Vj (k) represent the position and velocity of particle j at the k-th iteration, respectively. W is the inertia weight, which is usually initialized to 0.9, c1 and c2 are the learning factors, which control the particle's tendency to the global optimal solution. Usually, their values are 2, and r1 and r2 are random numbers uniformly distributed between 0 and 1.

Problem Formulation
This section describes a container deployment cost calculation model in a cluster environment, and then the formulation of container deployment problem is discussed.

Deployment cost model
A typical scenario in a container cloud environment is shown in Figure 1. One or more users submit resource requests (Here mainly refers to computing resources) from clients to the management host, and the management host divides the request task into one or more subtasks. After that, it is queued into a queue tq, waiting for the task allocation plan made by the scheduling module, loading the task on the The key issue in the entire process described above is the design of the task scheduler, which dispatches the task load to the execution host, to meet the following criterions.
1) The task loads scheduled to a specific host cannot exceed the host's computing capacity.
2) The total number of scheduled task loads should remain fixed during the containerization process.
To meet criterion 1, denote xi as the task loads on node i, node(i)capacities is the amount of computing resources on node i, then a constraint is set as: This constraint ensures that all the task loads running on host i should not exceed its computing capacity. To meet criterion 2, denote nodenumber as the number of execution hosts in the cluster, another constraint is set as: The value of T is a fixed value. This constraint ensures that the total task load on the cluster server remains the same during the particle optimization process.
Data exchange costs occur between the management host and the execution host. The management host needs to load tasks to the execution host, causing data transfer. In [21], the link cost model in the AODC strategy is used to calculate the cost of data exchange between two hosts. Based on this, the costs of data exchange between the management host and the execution hosts is defined as: distance(i) is defined as the distance between the execution host i and the management host, and trafficost is the cost of traffic through this path.
When the task is started in the container of the execution host, the execution host needs download the image from the image registry, it will generate the image pull cost. The image is composed of multiple layer files and most files are basic files that can be shared [24]. If the image files required for all tasks in the container have been downloaded on the host, there is no need to pull costs, but if the execution host contains only the basic files required for some tasks, it is necessary to pull the missing files, as shown in Figure 2. The image pulling cost is defined as: Because the missing files can only be determined by combining the storage situation of the host image file and the task requirements, we use a random strategy to estimate the percentage of missing files, pcti is defined as: = rand . pull images diagram. In addition, when the container is running on the host (usually a execution node is a server in a container cloud environment), there will also be an energy cost. According to the server energy consumption model proposed by E. Feller et al. [25], we use the utilization of computing resources to estimate the energy cost.
fimin is defined as the lowest working energy consumption value of server i, in our scenario, the lowest working energy consumption means that no container is running in the server, and fimax is defined as the energy consumption value of server i under full load. powercost is defined as the cost of unit energy consumption.
The character u in function (8) means the utilization of computing resources on server i and it can be generated by: For the purpose of global optimization, the energy cost generated by all the hosts, the image pulling costs and the costs of data exchange between the management host and the execution host should be minimized. Take functions (5), (6), and (8) where the weighting factors    、 、 are introduced to balance the three costs.

Problem formulation
Assume that in cluster environment, there is a set of execution nodes Enodes={E1, …, Ei, … Enodenumber}, and the computing resources for execution node i are fixed, defined as Enode(i) capacities.
Each time task scheduling occurs, subtasks in the task queue are loaded from the same management node to multiple execution nodes. Different task loading schemes on the execution nodes in the cluster are considered as different solutions.
The above work aims to dispatch the tasks loads from the management node to execution nodes to achieve the minimal costs of container deployment cost. This is reflected in the objective function (11) y is binary.

CD-PSO Algorithm
In this section we present the improvement of the CD-PSO algorithm on the PSO algorithm and the specific implementation of the CD-PSO algorithm.
The role of the CD-PSO algorithm is to find the lowest cost task loading scheme during the containerized deployment of tasks. In the initialization phase of the algorithm, N kinds of task load distribution schemes X={X1, X2, …, Xj} are randomly generated under constraints. The vector sets of X and V are described as follows. 11 Among X, each line is a vector that represents a loading solution and also represents a particle position in the search space, xji represents the task load of the i-th node in the j-th scheme. For vector set V, each line is a vector that represents a particle velocity, and the element vji of Vj is randomly generated between (-1, 1) at initialization. Then Each particle is updated in an iteration until the maximum number of iterations M is reached. Each time the particle completes the update in the iteration, the update of the optimal position must be considered. The updates of Pbestj and Gbest satisfy the following formulae (19) and (20): Where f is a fitness function, which conforms to the above objective function (11) and the constrains (12), (13), (14), (15), and (16).

Algorithm improvement
In the PSO algorithm, particles are affected by the individual optimal position and the global optimal position during the iterative search process, and they will gather to the same position to different degrees. After reaching a certain number of iterations, a majority of particles will surround a certain space, this phenomenon is called falling into local optimum. Particles trapped in a local optimum will bring a lot of invalid searches. To prevent this, we proposed the CD-PSO algorithm to determine the local optimum in each iteration. If the particles are found to be trapped in the local optimum, an optimal guiding position, called OGP, will be selected to help the particles jump out of the local optimum.

determine the local optimum.
To get rid of the particles from the local optimality is basically to guide the particles to diverge from the vicinity of the aggregation position. In the process of divergence, the particles search for the spatial position that they passed. If the particles do not fall into a local optimum, and thus no guidance necessary, otherwise the particle search will be very uncertain, which will reduce the efficiency of algorithm optimization. Therefore, it is necessary to determine whether the particles are in a local optimum or not in time.
a. Hamming distance: In the information encoding, the alignment elements on the two strings are different, which is called Hamming distance. For example, the strings s1 = [01538], s2 = [04237], the elements in the first and fourth positions of s1 and s2 are the same, and the second, third, and fifth positions are different. The Hamming distance between the two strings is 3. For the same reason, it is stipulated that the absolute value of the difference between the alignment elements of the vectors Xj and Gbest does not exceed 0.5, which is called the same alignment element, and the Hamming distance HDj of each particle position is calculated.
b. Calculate the average Hamming distance HDave of the particle population in the current number of iterations. If formula (21) holds, it means that the current particle population has fallen into a local optimum, where  is the coefficient and its value is set to 1.

Select OGP.
Particles have been updated from the initial initialization to the local optimal position. The global optimal position has undergone a series of updates. We put the updated global optimal position into the set G, G = (G1, G2, ..., Gk), the k represents the number of Gbest updates from initialization to a local optimum. For example, Gk represents the Gbest of the k-th update. The process is simulated, as shown in Figure 3.
We think that in the nearby space where the global optimal position appears multiple times, the spatial position that has not been searched by the particle is limited, while in the space where the distance between adjacent global optimal positions is relatively large, the particle has more spatial positions to search for. We use fen to indicate how much space has not been searched by particles near Gn. It is believed that the larger the fen, the more positions in the space near Gn the particles have not been searched for, and the greater the probability that Gn will be selected.

Restrictions
The following restrictions are made in this algorithm.

Vector element update.
When initialized, xji is a random value within the range 0 to Enode(i)capacities. During the iteration process, it is necessary to frequently update xji. If xji does not meet the formula (12) after updating, determine whether the value that brought the update to xji is positive or negative. If the value is negative, subtract a random number in 0 to xji from xji. When the value is positive, add a random number between 0 and Enode(i)capacities-xji to xji.

T keeps fixed.
At initialization, T is assigned according to a random algorithm. As the algorithm iterates, the vector elements will change. To ensure that the load T remains unchanged after the vector is updated, we use the following steps: formula (12). e. If the formula (12) is satisfied, perform the corresponding operation; if it is not satisfied, it will be substituted into step b until it is satisfied.

Algorithm
Input：N, M , Task queue(tq)。 Output：Task allocation scheme (Gnode) 1 Initialization X = (X1, X2, ... Xj, …XN 10 We found in experiments that the determine local optimum of operating was started when the number of iterations reached 4/3 of the maximum iteration, the execution time of the program was within a reasonable range, and the cost optimization performance was improved. Detailed experimental results are shown in section V.

Experiments
We conduct experiments to evaluate the performance of our proposed algorithm by comparing it with Binpack algorithm employed in the Docker Swarm [26] orchestration framework, Linear optimization algorithm (LP) proposed in reference [22], standard PSO, and TMPSO algorithm proposed by Shi et al [19]. We compare the cost of each algorithm during container deployment.

Experiment setup
For the sake of simplification and to expel other factors, the five scheduling algorithms (CD-PSO, Binpack, LP, PSO, and TMPSO) are implemented via MATLAB in a controlled experimental environment. The data of the test experiment comes from the CPU utilization of a set of tasks monitored by PlanetLab [27].
The experiment is performed in two ways: the first method selects a fixed number of tasks (10, 20, 30) and performs multiple experiments; The second method is to select 40, 60, 80, 100, 120, 140, 160, 180, 200, and 220 tasks for experiments. Each experiment is repeated multiple times, and the experimental result is the average of multiple experimental data. The computing resource capacity of each node is 100,  [25]. The powercost value is set to 1, the trafficost is 1.2, the distance (i) that between the execution host i and the management host is randomly generated between 2 and 6, and the host file pull cost pullcosti is randomly generated within 1 to 3. The number of particles in the CD-PSO algorithm is N = 60, and the maximum number of iterations is M = 300.

Result
In the first method, 6 experiments were performed with 10, 20, and 30 tasks selected and 1 additional hosts. The experimental results are shown in Tables 1, 2, 3, 4, 5, and 6. The data in Tables 1, 3, and 5 show the deployment cost values of the allocation strategies implemented by several scheduling algorithms. The data in Tables 2, 4, and 6 represent the CD-PSO Optimize performance, which is the reduction percentage of the cost value of the CD-PSO algorithm compared with the cost value of other scheduling algorithms. From the experimental data, the cost of the CD-PSO algorithm is lower than other scheduling algorithms. The best experimental results can reach about 26% lower than the cost value of the Binpack algorithm, about 15% lower than the cost value of the LP algorithm, reducing the cost value of the PSO algorithm and the TMPSO algorithm more than 8%.  In the second method, the number of tasks is between 40 and 120, the number of additional hosts is 2, the number of tasks is between 120 and 220, and the number of additional hosts is 3. The experimental results are shown in Figures 4 and 5. In different experimental environments, the optimization performance of the CD-PSO algorithm is basically stable. Among them, the cost value of the CD-PSO algorithm is more than 20% lower than the cost value of the Binpack algorithm, about 14% lower than the cost value of the LP algorithm, about 9% lower than the cost value of the PSO algorithm, and about 7% lower than the cost value of the TMPSO algorithm on average.    Figure 6 indicate the execution time of the PSO algorithm, TMPSO algorithm, and CD-PSO algorithm, which is from task submission to the end of optimization. It can be seen from the figure that the execution time of the TMPSO algorithm is the shortest, because the algorithm reduces the number of calculations and the generation of random numbers when the particle speed is updated. CD-PSO algorithm and PSO algorithm have a small difference in execution time when the number of tasks is 20 to100. When the number of tasks reaches 100 or more, the difference in execution time is obvious. The reason is that the CD-PSO algorithm adds operations to determine the local optimum and select OGP on the basis of the PSO algorithm, which leads to an increase in the calculation amount of the algorithm. We set these operations to occur when the algorithm iteration reaches 4/3 of the maximum iteration. When the number of tasks is small, the amount of computation of the CD-PSO algorithm is only a little more than that of the PSO algorithmthe. Therefore, execution time of the CD-PSO algorithm is almost equal to the execution time of the PSO algorithm. However, As the number of tasks increases, the difference in execution time will become larger and larger. It can be seen that in small-scale task scheduling scenarios, the CD-PSO algorithm achieves the purpose of optimizing performance improvement with less time cost.

Analysis
We study the experimental results in different ways for a brief analysis. Binpack algorithm tends to load tasks onto several main execution hosts, the execution host is easily fully loaded, so the energy cost of the execution host is the highest, as the energy cost is container deployment costs accounting for the largest proportion. The LP algorithm, the PSO algorithm, the TMPSO algorithm, and the CD-PSO algorithm are all optimization algorithms. When scheduling, these algorithms will consider the various constraints of the hosts in the cluster to find the most appropriate task allocation scheme. However, the linear optimization algorithm is not as good as swarm intelligence optimization algorithm in swarm optimization applications. Due to the PSO algorithm often falls into a local optimum and cannot complete a full and efficient search. The CD-PSO algorithm has been improved to address this shortcoming to improve the ability of particles search in the overall solution space, the TMPSO algorithm is designed to focus on finding the optimization results in a short time, so it is difficult to guarantee stability and optimization performance. Therefore, the experimental results show that the cost of the CD-PSO algorithm is lower than other scheduling algorithms, and in a small-scale experimental environment, the time cost of the CD-PSO is also acceptable.

Conclusion
In this paper, we propose a particle swarm optimization algorithm for container deployment (CD-PSO) and implement it on the Matlab simulation platform. Through the data obtained from comparing experiments of CD-PSO algorithm with Binpack algorithm, LP algorithm, PSO algorithm and TMPSO algorithm, it is demonstrated that the CD-PSO algorithm can find the optimal loading solution during the container deployment process to reduce the deployment cost.
In the future, we will consider the diversity of required resources within the scope of our research and apply the CD-PSO algorithm to the Swarm or Apache mesos scheduling module.