A placement architecture for a container as a service (CaaS) in a cloud environment

A virtual machine is a simulation of physical hardware resources, including processors, memory, and I/O devices. Each VM runs an independent operating system on top of the VMM. Previous studies on the problem of VM-PM placement were mainly intended to optimize the utilization of PMs in IaaS cloud infrastructure and to maintain certain Quality of Service (QoS) requirements of the applications submitted to IaaS clouds. Much of this research was conducted to investigate VM placement and provisioning on PMs, including static and dynamic scheduling, and optimal PM utilization was their main objective [9‐11].

Docker is an operating system-level virtualization mechanism that allows Linux containers to execute independently on any host in an isolated environment. For container placement, algorithms such as Docker Swarm and Google Kubernets [12, 13] have been proposed. The Docker Swarm allocation algorithm simply maps containers to the available resources in round-robin fashion [6]; however, many other scheduling algorithms have been proposed. The main goals of these scheduling algorithms are to either maximize the utilization of PMs or to maximize container performance. For example, in [14], an architecture called OptiCA was proposed in which each component of the distributed application is executed inside a container, and the containers are deployed on PMs. The main goal is to optimize the performance of big-data applications within the constraints of the available cores of the PMs. In [15], an algorithm was proposed to minimize the energy consumption of a data center by placing applications on the PMs efficiently under a certain defined service level agreement constraint while simultaneously minimizing the number of required PMs. A simulation was used to model the workload using a Poisson distribution with a queuing routing strategy to map the workload to the determined PMs.

The placement algorithms of VMs on PMs are mainly intended to optimize PMs utilization. Currently, containerization technology has been used to optimize the utilization of VMs. Application containers are provided by Amazon EC2 in the form of a CaaS cloud service. In the CaaS model, tasks execute inside containers that are allocated to VMs to minimize the application response time and optimize the utilization of the VMs. For example, the proposed queuing algorithm in [15] can be used to map the containers directly onto VMs rather than onto PMs to minimize the required number of VMs and, consequently, to minimize energy consumption. In [16], a placement algorithm for containers on VMs was proposed. The main goal of the proposed placement algorithm was to reduce the number of instantiated VMs to reduce billing costs and power consumption. The proposed model used the constraint satisfaction programming (CSP) approach. In [17], a meta-heuristic placement algorithm was proposed that dynamically schedules containers on VMs based on an objective function that includes the number of PMs, PM utilization, SLA violations, migrations and energy consumption. In [18], the proposed placement algorithm was based on using Constraint Programing (CP) to map containers to VMs with the goal of minimizing the number of required VMs.

The two-tier placement algorithm schedules containers and VMs on PMs. The objectives of such placement algorithms are to (1) maximize the utilization of PMs and VMs, (2) minimize the number of PMs and VMs, and (3) improve the overall performance of the executed applications. This type of placement algorithm is the main concern of this research.

For example, in [19], a two-level placement algorithm is proposed for scheduling tasks and VMs on PMs simultaneously. The main goal of the proposed algorithm is to maximize PMs utilization. The placement algorithm first schedules VMs on the PMs using the Best Fit algorithm and then schedules tasks on the VMs using Best Fit. The results are compared with the those of FCFS scheduler. However, the proposed scheduler focuses on PMs utilization and does not simultaneously consider the utilization of both VMs and active PMs.

In [20], the Best Fit algorithm is used to load-balance the tasks over VMs by first considering the placement of VMs on active PMs using the Best Fit algorithm. This approach aims to ensure moderate PMs utilization. However, the focus of the study involves VM placement on PMs.

In [21], a placement algorithm is proposed based on a fitness function that considers the utilization of both the PMs and the VMs. The Best Fit placement algorithm is used along with the fitness function to evaluate the selections of both PMs and VMs. The experimental results show that the proposed algorithm improved PM utilization compared with the Best Fit algorithm without the fitness function. In this paper, a similar fitness function is proposed based on the remaining available resource percentages of both VMs and PMs. The fitness function is employed in the placement algorithms. Furthermore, in this paper, we explore using different heuristics, such as Best Fit, Max Fit and the meta-heuristic Ant Colony Optimization (ACO) algorithm.

As mentioned above, most existing research has focused on the problem of scheduling containers on either VMs or PMs or on the placement of VMs on PMs. Thus, the existing provision architectures and container-scheduling algorithms for VMs do not consider the VMs and PM attributes together. This leads to major fragmentation of the PM’s resources and poor PMs utilization. For example, consider the placement scenario for container C5 using the configuration shown in Fig. 2. There are several placement options, and each placement decision impacts the utilization of VMs and PMs. The first placement option is the placement of container C5 in either VM1 or VM2. This placement improves the utilization of VM1 or VM2. The second placement option is the placement of container C5 in VM4. This placement option improves the utilization of PM2 as well as the utilizations of VMs on that PM. Finally, the last placement option is the placement of container C5 in VM4. This placement option is the worst option where an unnecessary PM is switched on. Without this placement option, PM3 can be put to sleep to minimize the number of PMs used.

This section presents the proposed placement architecture and scheduling algorithms proposed to improve PM and VM utilization while scheduling containers in a CaaS cloud service model. The architecture aims to minimize the number of instantiated VMs and active PMs and maximize their resource utilization.

In CaaS, tasks execute inside containers that are scheduled on VMs, which, in turn, are hosted on PMs. The objective of the placement architecture is to improve the overall resources utilization of both VMs and PMs, and to minimize the number of instantiated VMs and the number of active PMs. An overall view of the proposed architecture is shown in Fig. 3. The architecture consists of the following components:

The PMC is a daemon that runs on each PM. The PMC collects information such as the utilization of each PM and its resource capacity. The PMC sends the collected data to the container scheduler.

A VMC is a daemon that runs on each instantiated VM. The VMC collects information such as the resource capacity of the VMs and its used resources. The VMC sends the collected data to the container scheduler and to the VM information repository.

The VMIR maintains information about the types of VMs that can be instantiated and information about each instantiated VM.

The VMP schedules the placement of newly instantiated VMs on available PMs using the information available from the VMIR and PMC. Furthermore, the VMP is responsible for VMs provisioning.

The CS determines the placements of containers on the VMs. The placement decisions are based on the information available from the PMC and the VMIR.

In the proposed architecture, each job consists of a number of independent tasks, each of which executes inside a container. The Container Scheduler (CS) contacts the VMIR to obtain the available resource capacity of each VM. The CS applies the placement algorithms that are proposed in the following subsections to find a placement for each container on a VM. When the CS finds a placement, it contacts the VMC to launch the container. When there is no VM available with enough physical resources to host the container, a new VM must be instantiated—either on a new or currently active PM. To accomplish this task, the CS asks the VMP to instantiate a new VM. The VMP finds a placement for the new VM using the information provided by the VMIR and the PMC. The VMP instantiates the new VM and updates the VMIR. Finally, the VMC starts the container on the newly instantiated VM. Figure 4 shows the sequence diagram for container placement in the proposed architecture.

The following subsection presents a mathematical formulation for the problem of container placement on VMs and PMs. The main objective is to improve the overall utilization of VMs and PMs. Based on the proposed formulation, heuristic and meta-heuristic scheduling algorithms will be presented.

This subsection presents the mathematical formulation of the objective function for the proposed architecture, which minimizes the number of active VMs and PMs and maximizes the utilization of both VMs and PMs. Table 1 summarizes the symbols used in this section.

The goal of the objective function is to minimize the number of physical machines:

We consider the following constraints on the scheduling decisions:

Equation (4) ensures that the sum of each resource type allocated by all VMs on each PM is less than or equal to the total amount of that resource available on the PM.

Equation (5) ensures that the sum of each resource requested by the containers on all VMs vm_ij on the physical machine pm_j is less than or equal the total capacity SC_(j, r) of that resource on that physical machine pm_j. This condition applies to computational resources, such as CPU cores, memory, storage, and bandwidth. The placement algorithms should maximize the resource utilization on the VMs and PMs. This can be achieved by minimizing the resource waste on both the VMs and PMs simultaneously. Equation (6) calculates the normalized resource waste on a PM considering only the number of CPU cores and the memory resources.

w₁ and w₂ are weights constants. \( PM\_{available}_j^{CPU\_ cores} \) and \( PM\_{available}_j^{memory} \) represent the available number of cores and the amount of memory on pm_j after assigning the requested physical resources, respectively, and they are calculated using Eqs. (7, 8).

Equation (9) calculates the normalized resource waste of a VM while considering the resource waste of the PM hosting that VM. \( VM\_{available}_{ij}^{CPU\_ cores} \) and \( VM\_{available}_{ij}^{memory} \) represent the number of cores available and the amount of memory on vm_ij after assigning the requested virtual resources, respectively, and they are calculated using Eqs. (10) and (11).

The placement algorithm should make its decisions based on the minimum values of Eqs. (6) and (9). However, this problem is NP-hard and the difficulty increases exponentially as the number of containers increases [9]. The following subsection discusses the heuristic and meta-heuristic scheduling algorithms.

This subsection discusses the proposed scheduling algorithms for scheduling containers on VMs and scheduling VMs on PMs. The problem can be viewed as a multitier bin-backing problem in which the VMs are considered the bins for the containers, while simultaneously, the PMs are considered the bins for the VMs. The goals of the proposed scheduling algorithms are to (1) maximize PMs utilization and (2) maximize VMs utilization. To achieve these goals, we propose three algorithms using the mathematical formulation discussed in Section 3.2. The algorithms are Best Fit, Max Fit, and a meta-heuristic based on Ant Colony Optimization and Best Fit.

The Best Fit algorithm (BF) is a heuristic that is used to optimize the bin packing problem. The BF algorithm is widely used in the literature to find placements for VMs on PMs [22]. In this study, the BF algorithm is used to find a placement for containers on VMs by considering the resource utilizations of both the VMs and the PMs. The BF algorithm presented in Fig. 5 schedules containers onto VMs that have the least available resource capacity that can accommodate the resources required by the new container. This is achieved by scheduling the container to the VM with the minimum resource wastage, using Eq. (9). When no existing VM has sufficient available resources to accommodate the resources required by the new container, a new VM must be instantiated.

The same idea is applied to the placement of VMs onto PMs: a new VM is instantiated on the PM with the least available resource capacity that can accommodate the resources required by the new VM using Eq. (6). Finally, when there is no PM available whose available resource capacity fits the resources required by the new VM, a new PM is activated. The Best Fit algorithm is shown in Fig. 5.

The Max Fit (MF) algorithm is similar to the Best Fit heuristic. However, the main difference is that Max Fit elects to place containers on VMs that have the maximum available resource capacity and can accommodate the resources required by the new container. Thus, in Max Fit, containers are scheduled to VMs that have the maximum resource wastage using Eq. (9). When no VM has sufficient available resources to accommodate the resources required by the new container, a new VM must be instantiated. The new VM is instantiated on the active PM with the maximum available resource capacity that can accommodate the resources required by the new VM using Eq. (6). Finally, when no PM exists whose available resource capacity can accommodate the resources required by the new VM, a new PM is activated. The Max Fit algorithm is shown in Fig. 6.

ACO is a meta-heuristic inspired by real ant colonies and their collective foraging behavior for food sources. ACO is a probabilistic method used to solve discrete optimization problems, such as finding the shortest path in a graph [23]. In the search for food, an ant leaves the nest and travels along a random path to explore the surrounding area for food. During the search, the ant produces pheromone trails along its path. Other ants smell the pheromones and choose the path with a higher pheromone concentration. During the ant’s return trip, it releases a quantity of pheromone trails proportional to the quantity and quality of the food it found. All the remaining ants of the colony will follow paths with higher pheromone concentrations at a higher probability than they follow paths with lower pheromone concentrations. Eventually, all the ants will follow a single optimal path for food. For m ants and n possible paths, each ant determines its path according to the concentration of pheromone trail in each path of the possible paths. Initially, all the ants select a path randomly because of the negligible differences in pheromone quantity among the paths [24, 25].

The ACO algorithm has proven effective as an optimization algorithm for a number of problems, including the traveling salesman and job shop scheduling [26] problems. Furthermore, the ACO algorithm has been used to efficiently schedule VMs on cloud resources with the objective of minimizing total resource wastage and power consumption [27]. The ACO has also been used to schedule tasks on cloud VMs with the goal of load-balancing the tasks on the VMs and reducing the make span of the tasks [28]. A number of schedulers have adopted the ACO algorithm to load balance tasks on cloud resources [29, 30]. The following proposed algorithm uses ACO to find container placements on VMs with the objective of maximizing the utilization of VMs and PMs while minimizing the number of instantiated VMs and active PMs.

In a search for container placement on vm_ij and pm_j with the objective of maximizing the used PMs and VMs utilization, the following equation represents the pheromone trail of that container placement for an ant k in iteration (t + 1).where \( \Delta {\tau}_{ij}^k \) represents the amount of pheromone released by an ant due to the quality of the placement of a container on vm_ij and pm_j. Here, ρ is a constant that represents the rate of pheromone evaporation to simulate the effect of the evaporation of the pheromone at each step, and \( \Delta {\tau}_{ij}^k \) is calculated using the following equation:

VF(i, j) is the fitness of the placement on vm_ij and represents the probability that an ant k will select the placement of a container on vm_ij and pm_j.where η_ij(t) is a heuristic function that represents the quality of a container placement, and η_is(t) is calculated as follows:

The complete algorithm is shown in Fig. 7. The proposed algorithm starts by calculating the total amount of resources available in the instantiated set vm_ij. If the available resources are below the total amount of resources required by the set of containers C, a new subset of VMs is instantiated using the BF algorithm that satisfies Eqs. (6) and (9), which maximize the VMs and PMs utilization. The algorithm starts by calculating the initial pheromone trail matrix τ_ij and the placement cost matrix η_ij using Eqs. (13) and (15), respectively. During each iteration, each ant ant_k finds a placement for the set of containers C_k on vm_ij with a probability calculated using Eq. (14). The selection of vm_ij is performed using the roulette wheel method where a random number ϵ [0, 1] is generated and a cumulative sum of the probabilities is calculated. The cumulative sum probabilities are arranged in ascending order, and the cumulative probability equal to or greater than the generated random number is selected. After each iteration, the ACO algorithm updates the pheromone trail matrix τ_ij. The algorithm iterates until the maximum number of iterations is reached or the best placement of the containers on the subset of VMs is found.

This section presents the experiments conducted to evaluate the proposed placement architecture and scheduling algorithms. A program is designed and developed using MATLAB to simulate the proposed placement algorithms. A simulation-based evaluation is adopted because it allows the environment parameters to be controlled and the experiments to be repeated under different constraints. The experiments are conducted to evaluate the proposed scheduling algorithms in terms of the utilization of VMs and PMs. The following subsections discuss the workload utilized for the simulation, the parameter settings and the evaluation of the proposed algorithms for effective placement of container-based cloud environments.

A workload is a set of jobs submitted for allocation and execution in a cloud environment. The workload dataset used in the evaluation is the Google Cloud trace log, which was published in 2011 [31]. The Google real workload dataset is used because it is widely used in the literature for the purpose of workload placement and scheduling evaluations. In this paper, the workload is used to evaluate the applicability of the proposed placement algorithms in real world scenarios. The workload consists of a number of tables that describe the submitted task requirements, machine configurations, and task resource usage. The Task Event table contains information such as time, job ID, and task ID. Additionally, the table includes normalized data, such as resource requests for CPU cores and RAM. The number of vCores used to denormalize the CPU requests in the task Event table is 64. The amount of memory used to denormalize memory requests in the task Event table is 1024 GB. Figure 8 shows a sample of the vCore and memory requests for 1000 tasks in the Google cloud workload dataset, while Fig. 9 shows the number of tasks received for scheduling during a 1000-s period in the sample Google workload. Each task in the workload, the task Event table, is used to represent a container that requires a placement using the available VMs and PMs configurations described in the following subsections. The required CPU cores and memory request for each task, after denormalization, are considered the required resources for container placement.

The VM type repository includes several types of VMs that can be instantiated. Each VM type has distinct resource characteristics, including the number of vCPUs, the memory size, and the storage size. Each vCPU in a VM is allocated one core of the PM. Table 2 presents the different VM types used in the experiment.

Table 3 shows simulated configurations of the physical machines used in the evaluation experiment.

The simulation was run on a PC with an Intel Core i7–4510 CPU at 2.60 GHz and 8 GB RAM. In the experiments the parameters are set to the values described in Table 4. The parameter settings are obtained by conducting several preliminary experiments.

The goal of the experiments was to evaluate the proposed placement architecture using the Best Fit, Max Fit, and ACO-BF scheduling algorithms. The placement architecture works as a multitier scheduling algorithm in which the placement decision considers the utilization of both PMs and VMs. Each scheduling algorithm is executed 10 times for different number of containers. Initially, all PMs are off with no instantiated VMs. The output of each algorithms is the set of VMs to instantiate with their corresponding PMs to turn on.

Figure 10 shows the number of instantiated VMs for different numbers of containers. It is observed that the ACO-BF scheduler guarantees the lowest number of instantiated VMs compared to the other schedulers. Furthermore, the Max Fit algorithm instantiates a larger number of VMs.

Figures 11 and 12 show the average CPU and memory utilization of the instantiated VMs using the proposed scheduling algorithms for different numbers of containers. It is clear that the proposed ACO-BF algorithm yields the best resource utilization of VMs.

Figure 13 shows the number of PMs turned on for scheduling different number of containers. It is observed that the proposed ACO-BF algorithm turns on a larger number of PMs than the Best Fit and Max Fit algorithms. The Max Fit algorithms activates the lowest number of PMs.

Figures 14 and 15 show the CPU and memory utilization of the activated PMs for different numbers of containers. The proposed ACO-BF placement algorithm achieves the highest resource utilization. It is clear that the Max Fit algorithm guarantees a small number of active PMs but achieves poor resources utilization, as it activates the PMs with largest the physical resources. The proposed ACO-BF placement algorithm activates a large number of PMs because it turns on the PMs with the lowest resource capacities that can accommodate the resources required by the scheduled containers.

Figure 16 shows the time costs of the heuristics, which are computationally lightweight compared to the meta-heuristic ACO-BF, as shown in Fig. 17. Although the ACO requires a substantial amount of time compared to the heuristic algorithms, it guarantees the highest utilization of both VMs and PMs.