Project Proposal in cloud computing - Research Methods

Enhancing Kubernetes Scheduler by assimilating Hammersley Sequence Sampling technique in Ant Colony Optimization

Anandteerth Onkar x18141439

MSc in Cloud Computing

29th July 2019

Abstract Google’s Kubernetes has eventually become a de-facto standard tool for container orches-

tration due to it’s wide use in enterprise cloud for automated deployment and management of containers. After studying the default scheduling policy used in Kubernetes, it was observed that the scheduler selects the latest Node with high priority score without considering the monetory cost associated with the resources allocated. The following research work proposes to use an efficient ant colony optimization (EACO) algorithm for scheduling, to improve the performance efficiency of Kubernetes scheduler by replacing the default scheduling policy al- gorithm. The performance of proposed model will be evaluated considering utilization ratio, response time and turn around time. Using these parameters the model will be compared against default scheduling algorithm (greedy approach) of Kubernetes and some existing container orchestration model.

Keywords: Cloud, Container Orchestration, Kubernetes, Task Scheduling, Docker, Efficient Ant Colony Optimization (EACO).

Contents

1 Introduction 2

2 Literature Review 3 2.1 Containers over virtual machines (VMs) in cloud environment . . . . . . . . . . . 3 2.2 Task scheduling in cloud environment . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2.1 Task scheduling - Virtual machines . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 Task Scheduling - Containers . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Efficient Ant Colony Optimization (EACO) : Proof of concept . . . . . . . . . . . 7

3 Research Methods & Specification 8 3.1 Kubernetes Scheduler : Default Algorithm . . . . . . . . . . . . . . . . . . . . . . 8

3.1.1 POD scheduling in Kubernetes cluster . . . . . . . . . . . . . . . . . . . . 8 3.1.2 POD scheduling theoretical model and algorithm . . . . . . . . . . . . . . 9

3.2 Proposed Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.1 Proposed Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.2 EACO algorithm for Kubernetes scheduler . . . . . . . . . . . . . . . . . . 11 3.2.3 Scheduling using EACO algorithm . . . . . . . . . . . . . . . . . . . . . . 13

3.3 Proposed Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Proposed Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1

4 Research Timeline 15

5 Conclusion 16

References 16

1 Introduction

In recent years microservices-based applications hosted on containers has become a new architec- tural prototype for designing webservices. These applications are set of unconstrained, modular and compact services which communicate by passing messages and appear to function as single entity to achieve desired task. The application requirements are estimated by constituting set of heterogeneous microservices [1]. Microservice based applications have benefited in terms of in- tegration, deployment, shipping and periodical updation of applications. It has helped to bridge the gap between development and operations by empowering continuous integration / continuous development release cycles. These fundamental features have simplified application management and coordination over heterogeneous cloud [2]. Companies like Amazon, Netflix, IBM, Google etc. have migrated their applications adopting the microservices development achetype [3]. In cloud infrastructure the virtual machines are swiftly being replaced by the containers as a new light weight virtualization technology. The time required to launch or terminate a container instance is much faster than that of VMs. Additionally, containers contribute towards efficient utilization of computational resources [4].

Containers are formed by virtualizing the operating system layer, this allows individualistic environments for environments for execution and secluded filesystems. The container images are incremental in nature and consists of a layered file system. Container images are encapsulated with binaries, libraries and supporting environmental files that are not available in the under- neath operating system. This results in creation of light-weight instances (container) thereby reducing the virtualization overhead [5]. Due to these features Containers are rapidly becoming a key element of microservices architecture contributing towards its popularity. Thus container happens to be the most prominent technology for encapsulation and scaling of microservices. An experimental study was conducted [1], wherein the backend services of a commercial mo- bile application was migrated to microservices-based architecture that made use of containers. Linux Container (LXC) were the first to provide standard distribution for Linux container vir- tualization. Docker is the most widely used open source Linux container for deployment of microservices application [6].

Initially containers were used to deploy microservices application in homogeneous single cloud environment. Despite the success of containerization, it was facing a major drawback in managing multiple containers in enterprise level multi cloud environments. However this issue was resolved with emergence of container management tools such as Kubernetes, Docker Swarm, HarshiCorp etc. The tools efficiently manage the scheduling of containers and deployment of microservice based application in heterogeneous multi-cloud environments [6]. A framework was proposed by [7], wherein the deployment of microservices was automated in multi-cloud environ- ments using containers. An eCommerce application was developed to validate this architecture. The requirements of microservices are accomplished using resource management techniques, in which any given tasks are mapped to the computational resources.

The resource management is a challenging task in enterprise cloud composed of several heterogeneous components and unpredictable workloads. The challenges related to optimization and resource management in cloud using containers have been researched to certain extent, to the best of our knowledge. For example [8] optimized the scheduling of docker swarm using

2

ACO. Despite its success, there are lot opportunities to enhance the performance factor of default schedulers. Furthermore, the default scheduling policies in Kubernetes, Docker Swarm follow the basic algorithm without using any optimization techniques [9]. Therefore, lot of research opportunities are available to improve the scheduling policies used in these container management tools by implementing optimization techniques. Kubernetes scheduling policy maps the POD jobs to the computational resources by favouring the contemporary node without considering the monetory cost of resources allocated [10].

The aforementioned limitations motivates the following research work, by defining the re- search question as below:

Research Question: Can the performance efficiency of Kubernetes scheduler be optimized by using Efficient Ant Colony Optimization (EACO) algorithm?

The following research work addresses the drawback associated with Kubernetes scheduler, by optimizing its default scheduling policy with an objective to improve the performance and reduce the monetary cost associated with deployment of microservice application.

2 Literature Review

In recent years, studies based on resource management and container orchestration in cloud have gained a huge momentum [11]. There are several open issues related to container scheduling for deployment of microservices, that are to be addressed in cloud [2]. The research study presented in different sections is summarized below:

• Containers over virtual machines (VMs) in cloud environment :- Highlights the significance of containers in cloud.

• Task Scheduling in cloud environment:- Highlights studies related to task scheduling in virtual machines and containers.

• Efficient Ant Colony Optimization (EACO): Proof of concept :- Highlights im- portance of implementing EACO algorithm for optimization problem.

2.1 Containers over virtual machines (VMs) in cloud environment

Virtual machines are replicas of hardware (Ex. server) formed by simulating system instructions sequentially. On the other hand containers are formed by virtualizing operating system, in which the OS kernel is shared among all containers. Containers are capable of packaging more number of applications on a single host compared to that of VMs. Due to which containers are replacing VM technology in cloud data center [6].

Various studies have been conducted to evaluate the performance of VMs and Linux contain- ers [4], [12], [13]. The QoS, network performance and security evaluation factors of containers are marginally higher compared to that of VMs. VM have performance overhead which impact the overall performance, on other side the containers don’t have performance overhead but they face performance challenges due to high packet flow rate. However, from security and isolation perspective VMs rule over containers because of minimal security and isolation present in con- tainers [12]. Therefore choosing between VM and container is a distinct decision, that is based on the cloud infrastructure requirements.

3

2.2 Task scheduling in cloud environment

Efficient scheduling of tasks is an important factor in resource management. This section dis- cusses different studies related scheduling of tasks on virtual machines and containers in cloud environment.

2.2.1 Task scheduling - Virtual machines

The studies discussed in following section have benefited in deciding the scheduling approach of containers. They have formed a strong baseline to support container technology. Table 1 summarizes the key aspects of these studies related to task scheduling on virtual machines.

H.Fard et al. proposed a pricing model using dynamic scheduling mechanism with an ob- jective to reduce the monetory cost and achieve faster completion time. They used Vickrey- Clarke-Groves(VCG) mechanism for cost and introduced a scheduling heuristic from Bi-objective Scheduling Strategy (BOSS) based on an extension of game theory for dynamic scheduling. The evaluation of results showed improvement in cost and time compared to the two multi-objective evolutionary algorithms (MOEAs) i.e. SPEA2 and NSGA-II [14]. Bermejo et al. surveyed the use of elite multi-objective genetic algorithm (NSGA-II) to address the pitfalls in cloud inter- operability for cloud brokers, in order to efficiently schedule tasks for optimizing the availability, time, reliability and cost [15].

Panda and Jana, proposed Minimum Completion Cloud (MCC) algorithm with single phase scheduling, Median Max (MEMAX) with two phase scheduling and Cloud Min-Max Normal- ization (CMMN) with two phase scheduling for workload scheduling in multi-cloud in order to maximize the average utilization rate of cloud resources. These three algorithms viz. MCC, MEMAX and CMMN were evaluated on multiple commercial Platform as a Service(PaaS) envir- onments using synthetic data-set to draw the efficiency of proposed algorithm [16]. The authors further extended their work of scheduling in multi-cloud by introducing two task scheduling algorithms based on SLA viz. SLA-Mean Time Completion (SLA-MCT) with single phase scheduling and SLA-Min-Min with two phase scheduling. Results of SLA-MCT were contrasted with Profit-MCT, CLS and Execution-MCT algorithms, and on the other hand results of SLA- Min-Min were evaluated against Profit-Min-Min and Execution-Min-Min algorithms based on different performance metrics i.e cloud utilization rate, makespan, penalty cost and profit. Eval- uation of results show an equilibrium between cost gained and makespan of services compared to algorithms in test [17].

For deploying services across cloud a modular broker archetype capable of supporting mul- tiple scheduling strategies was proposed by Lucas et al. that optimized cost and performance considering budget, types of instances, performance, reallocation, load balancing and placement factors for both static and dynamic environments. The proposed architecture was tested by de- ploying it on web server and HPC clusters, the results showed a trade-off between these cluster types with respect to financial profit analysis [18]. The scheduling problem in multi-cloud was addressed by using an enhanced genetic algorithm using biased random-key to deploy user ap- plication in Iaas cloud with an objective reduce the execution time and monetory cost associated with deployment. The results outperformed compared to the models from related work with respect to time and quality [19]. To efficiently strategize the failures of deployment, resource load, run-time cost and application availability multi-cloud, a modified multi-objective schedul- ing algorithm Genetic was used by M. E. Frincu and C. Ciprian. The aim was to accomplish high availability of application, fault tolerance in resources and reducing usage cost by increasing resource utilisation rate through optimization of task allocations in physical machines. The res- ults obtained using genetic algorithm were compared to the round-robin, to prove the efficiency of proposed system [20].

F. Legillon at al. improvised genetic algorithm to deploy application services on VMs as-

4

signed with divergent Infrastructure as a Service (IaaS) providers. The advancement of the approach was experimented by using simulation of real-time instance using two bench-marking data sets generated from low-load web-server and high-load web-server. The results were evalu- ated against Mixed-Integer Programming (MIP) solver that concluded genetic algorithm to be an optimal solution to solve small and medium problems within given time compared to MIP [21].

Refs Resource

Management Workload Type

Resources Managed

Algorithms Optimization

Factor

[14] Scheduling Task VM (Cloud) Vickrey- Clarke-Groves (VCG)

Monetary cost and makespan

[15] Scheduling Task VM (Cloud) NSGA-II Availability, cost, time and reliability

[16] Scheduling Task VM (Cloud) MCC, MEMAX and CMMN

Makespan

[17] Scheduling Task VM (Cloud) Stochastic (SLA-MCT, SLA-Min-Min)

Service Level Agreement

[18] Scheduling Service VM (Cloud) Cost functions Monetory Cost and performance

[19] Scheduling Task VM Biased random-key Resource usage, execution time and monetory cost

[20] Scheduling Task VM Genetic algorithm Availability, cost and resource usage

[21] Scheduling Service VM Genetic algorithm Monetory Cost

Table 1: Summary of related work: task scheduling strategy for virtual machines

2.2.2 Task Scheduling - Containers

Container scheduling is relatively a new research domain with limited literature addressing the open issues present in scheduling of containers. Most of the studies discussed in this section have base-lined their approach considering scheduling techniques implemented in virtual machines.

Most of research conducted in task scheduling were focused on virtual machines, applying these methods and techniques to containers won’t be feasible as the architecture of containers is different from that of virtual machines (VM). In addition and these existing methods don’t take into account the dependencies linked with containers, therefore applying the VM schedul- ing methods won’t be completely feasible in case of containers. Highlighting the importance

5

of scheduling methods and its impact on overall performance of system a container schedul- ing strategy based on neighbour division of micro-services called CSBND was designed. The objective was to optimize the the system performance by considering response time and load balancing parameters. The capability of local search particle swarm optimization algorithm is implemented. The model was simulated using CloudSim and the experimental results were compared with Multi-objective Particle Swarm Optimization (MOPSO) algorithm, CSBND not only guaranteed load balancing of cluster but also improved the system performance by 20% - 25% [22].

D. Zhang et al. have evaluated container scheduling considering three major factors: energy conservation associated with the container host, the cost of extracting the container image from the image registry and assigning it to the container host and finally the cost associated with network transition for transmitting the workload from client-side to the container host. The scheduling problem was defined in terms of an integer linear programming (ILP) problem, which was solved using an effective and adaptive scheduling algorithm. The performance of container deployment was enhanced and the model can be easily accumulated in any of the container orchestration framework. Experiments were conducted by prototyping the scheduler using MATLAB. The results were compared to Random method and Bin-packing algorithms that are shipped with Docker Swarm-Kit. The results prove that the transition cost and energy consumption rate was comparatively depleted with use of linear programming [23].

C. Cerin et al. proposed a scheduling strategy by defining three Service Level Agreement (SLA) classes: Long service for applications that have consistent high load of resources (class SLA 1), Short services for application affecting in overloading of resources or waiting in a for any remote service (class SLA 2) and Micro service class for services whose lifespan is for few milli- seconds (class SLA 3). The objective is to optimize the consumption rate of resources utilized which reduces wastage of resources, create invoice based on resource consumption and developing a sustainable market for containers. Experiments were conducted using Swarm scheduler and to test the model the ’testing’ package shipped with ’Go’ language was used as a data set. The results showed improvement when compared to default scheduling strategies (random, spread and bin-packing) of Docker-Swarm [24].

C. Kaewkasi and K. Chuenmuneewong, argues about the scheduling policy of Docker Swarm is sub-optimal, in case when there is non-uniformity of resources. Therefore they propose a scheduling strategy for Swarm using Ant Colony Optimization (ACO) which is a meta-heuristic algorithm. They state that use of ACO will be workable to optimally enhance the schedulers’ performance. Experiments were conducted by simulating the Swarm-kit using ACO and the workload under test was taken from NGINX application server along with Apache bench-marking tool. The results of ACO were compared to Greedy algorithm and proved that ACO was 15% more faster than Greedy algorithm [8].

Discussion: Advantages and Limitations

The studies presented in following section are aimed towards improvising the container scheduling. The latency factor between containers communication has been improved using the Neighborhood division in micro service, which resulted in overall performance of application. Though performance was improved, the system wasn’t able to address the scheduling through- put and scaling at peak loads [22]. Linear programming was used for efficient task scheduling of containers with focus on cost of downloading the container image from repository (registry) and energy consumption rate. There was an overall improvement in mechanism for container creation, but the proposed model did not consider resource allocation and container placement factors [23]. The SLA class based container scheduling architecture model allocated resources considering predefined users’ SLA. However the SLA’s defined in the strategy for scheduling are unclear and contradicting. In addition, the proposed algorithm was not quantitatively eval- uated against algorithms shipped with Swarm-kit [24]. A container scheduling strategy using

6

ACO aimed at improving the performance container scheduling for non-uniform distribution resources, apparently it did not consider the performance when resource distribution is uniform [8].

Ref Objective Algorithm Platform Optimization

Factor Limitations

[22] Network latency between containers

Neighborhood division in micro service

Docker Swarm-kit

Performance Throughput & Scaling

[23]

Energy consumption rate & cost of downloading image

Linear programming

Docker Swarm-kit

Container Creation

Container Placement & Resource allocation

[24] Resource allocation

Service Level Agreement Class

Docker Swarm-kit

Container Allocation

Vague & Contradictory

[8] Container Scheduling

Ant Colony Optimization

Docker Swarm-kit

Container Scheduling

Non-uniform resources

Proposed Work

Container Scheduling

Efficient Ant Colony Optimization

Kubernetes Performance & Resource usage

TBD

Table 2: Summary of containers scheduling strategy

The container scheduling strategies discussed have been implemented only with Docker Swarm-kit. No authenticated studies have been published that uses above mentioned algorithms and techniques to address the scheduling limitations of Google Kubernetes. This research is fo- cused on studying the implementation of Efficient Ant Colony Optimization (EACO) [25] in Kubernetes scheduler with an objective to optimize the performance of container scheduling. Table 2 summarizes different container scheduling, by showcasing the similarities and differ- ences between the previous studies versus our approach.

2.3 Efficient Ant Colony Optimization (EACO) : Proof of concept

Ant Colony Optimization (ACO) is a meta-heuristic optimization algorithm which was first de- veloped by Dorigo [26], to find an optimal solution to combinatorial problems. Recently over a decade ACO is being widely used by researchers because of its successful implementation in various disciplines such as machine learning, scheduling, design problems, routing and different engineering domains [27]. In recent years, after successful implementation of ACO algorithm to find solutions to combinatorial optimization problems, researchers have been improving ACO al- gorithm for finding solutions to mixed variable and continuous non-linear programming problems [25].

ACO is inspired by from the behavioral characteristics of real ants to hunt for food. The real ant fortuitously hunt for food nearby their nest vicinity. After an ant discovers the source of food, on its way back to nest it deposits a chemical substance called Pheromone, that marks a path from food source to the nest. This pheromone trail laid by the ant will be indirectly be communicated to other ants in the colony, who will get attracted towards following the trail laid by the ant. The pheromone is volatile in nature, it evaporates after certain period of time reducing the attractiveness related to the under-laid path. Frequently used paths have

7

higher level of pheromone concentration that attracts other ants to follow. Therefore the level of pheromone concentration is more on shorter path compared to the longer path between food source and nest, leading towards shorter cycle time. This way the real ants discover the shortest path [26].

In case of ACO algorithm, artificial ants are variables that follow a procedure to build a probabilistic solution by utilizing pheromone model of real ants and perhaps the heuristic data from the mathematical representations. Numerical values represents the artificial pheromone trails, that is used to communicate between unnatural (artificial) ants. To inculcate the evap- oration property of real ants, pheromone decay technique is applied. This technique empowers the artificial ants to concentrate on new and efficient directional searches. Similar to real ants, the artificial ants updates the trail values based on information gathered from previous itera- tions. These procedures involved in ACO algorithm helps to find an optimal solution to larger problems [27].

U. Diwekar and B. Gebreslassie developed a new strategy for conventional ACO algorithm using a quasi-random sampling technique called Hammersley Sequence Sampling (HSS) [28]. The HSS technique improved computational performance of ACO by expanding the diversity in the initial solution set and by yielding consistency in the random operations performed. The competency of the EACO algorithm was evaluated using 9 benchmark problems that were initially solved using ACO. The experimental results of EACO were compared to ACO, EACO proved to improve computational efficiency in the range of 3% to 71% over ACO. Based on the results it was concluded, the probability of discovering an optimal solution for wider range and large scale optimization problems is higher using EACO compared to the conventional ACO [25].

3 Research Methods & Specification

This section specifies working of the default scheduling algorithm used in Kubernetes, the pro- posed method to improve the scheduling using EACO and the implementation steps.

3.1 Kubernetes Scheduler : Default Algorithm

This section explain, how the default algorithm of Kubernetes scheduler works. As shown in Figure 1, Kubernetes follows a master-slave architecture, wherein it can have one or more master called Control Panel and multiple slaves called Worker nodes. The scheduler is part of master node responsible for scheduling of Nodes. The scheduler consists of a scheduling policy to decide on which Node these microservices will be deployed. This scheduling policy can be modified or replaced with new algorithm to improve resource allocation in cloud [29].

3.1.1 POD scheduling in Kubernetes cluster

The primary responsibility of the Kubernetes scheduler is acknowledging the newly created POD by API server by arranging a host (VM) for the new POD and finally writing the metadata information of POD to etcd.

From the scheduling perspective, PODs can be categorized as:

• Long-running services: In this type, the Replication Controller creates the POD. Ex. nginx, mongoDB, MySQL etc.

• One-time task: In this type, the Job creates the POD. Ex. Unit testing, data calculation etc.

8

Figure 1: Kubernetes cluster architecture [30]

The long-running service and one-time task requires to be scheduled to execute on cluster of nodes. The unoccupied resources, that remain idle after one-time task are executed are always occupied by the long-running service. The scheduler bifurcates the unoccupied nodes in the cluster and reallocates them based on their node score. The node with the highest score is chosen in this allocation process, based on scoring strategy. The following research focuses on optimizing this allocation method of the scheduler.

The scheduling of POD is considered as a Task and the node on which it will be deployed is performed using virtual machine. The node with the highest score is selected to bind the POD to node, based on default selection and scheduling methods. The major drawback of this greedy deployment approach is that, not all the requested resources by the all PODs from the entire cluster are considered. Additionally the cost of resources is not taken into account while calculating the score. To overcome this limitation, this research work proposes to use an Efficient Ant Colony Optimization algorithm to optimize the scheduling.

3.1.2 POD scheduling theoretical model and algorithm

The theoretical model for scheduling in POD [29], is devised by considering below parameters:

n = number of PODs to scheduled. m= nodes to deploy. Q = {q0,q1,q2, ....qn} , where Q represents number of PODs in the queue to be scheduled. V = {vm0,vm1,vm2, ....vmm} , where V represents the number of nodes in the queue that are to be deployed.

Assuming that every POD can be scheduled only on a single node. The relation between POD and Node is represented in equation 1 as below: :

P = {p0,p1,p2, ....,pi, ....pn} 0 ≤ i ≤ n and 0 ≤ pi ≤ m (1)

9

Where, pi represents a task (t) to be deployed on a node vmpi for which P represents a practical solution for POD allocation. If pi is equal to -1, in that case task allocation is failed.

Algorithm: The Kubernetes scheduling algorithm consists of two phases [29]:

i. Applying filtering criteria.

ii. Prioritized ranking. In first step, the scheduler filters the node based on defined requirement criteria. If the available node’s memory and CPU satisfies the requirement of POD request or the requested port conflicts with the node’s port. If either of the criteria is not met, then it won’t consider the node in ranking phase. After filtering, the nodes (host) that met the requirement are scored using a priority function (Priorityfun) on a scale of 1 - 10, where 10 being most preferred and 1 least preferred. A weight-age (W) is summed into the priority score to calculate the final score for a node. The final score (Nodefinal−score) is represented in equation 2 as below:

Nodefinal−score = (W1 ∗ Priorityfun1) + (W2 ∗ Priorityfun2) (2)

3.2 Proposed Methodology

In this section, the proposed architecture and the EACO algorithm to be used for scheduling in Kubernetes is described.

3.2.1 Proposed Architecture

The scheduling policy in Kubernetes scheduler can be extended by configuring the scheduler configuration using either of the pre-defined policies or by applying a customized policy. The scheduler configuration are defined in a JSON file called Scheduler.json. This file contains the baseline criteria and priorities that the scheduler would be utilizing. The default scheduling policy is defined in a file called Scheduler.go. The scheduling policies in Scheduler.go and the configuration settings in Scheduler.json can be overridden by executing a command line utility flag called "policy-config-file".

As shown in figure 2, EACO algorithm will be implemented in Kubernetes scheduler by over- riding the Scheduler.go and Scheduler.json files. The EACO algorithm to be used is explained in section 3.2.2.

10

Figure 2: Proposed architecture of Kubernetes scheduler

3.2.2 EACO algorithm for Kubernetes scheduler

In ACO, the elements of the solution archive are chosen by the decision policy considering the negotiation factor between intensity level of pheromone on a particular edge and the attract- iveness of the chosen edge w.r.t it’s benefaction for an objective function. Taking into account these edge properties, the algorithm efficiently makes use of pheromone potency established con- sidering the information acquired from previous solution and edge attractiveness. The decision policy is expressed using the transition probability function as expressed in equation 3

Probu,v(Itr) = ταuv (Itr) . η

β uv (Itr)∑

i∈allowed u τ α uv (Itr) . η

β uv (Itr)

(3)

Where,

• Probu,v(Itr) is probability of selecting an edge uv as an element in solution set, for an ant positioned at node u for Itr iteration.

• τuv (Itr) represents the pheromone value for edge uv for iteration Itr.

• ηuv (Itr) represents the attractiveness of edge uv.

• α & β represents the control for pheromone intensity and attractiveness respectively.

If α � β, the algorithm will function based on information gathered from pheromone.

If α � β, the algorithm will follow a greedy heuristic approach by choosing low cost edges without considering the pheromone data.

The core component of ACO is to assess the pheromone value τuv (Itr) after every iteration (i.e. solution construction). Considering the assessment results the values at every edge uv is updated. The aim of this process is to refine the solution construction following certain rules. The rules to update the pheromone values on edge uv involves two steps:-

11

• The present pheromone level is declined by introducing pheromone evaporation technique.

• Pheromone attractiveness operation is directly proportional to the quality of constructed solution after every iteration.

These rules are represented in equation 4

τuv(Itr + 1) = ρ.τuv(Itr) + ∆τuv(Itr) (4)

Where,

ρ = Evaporation factor of pheromone.

∆τuv(Itr) = Updation of pheromone value at edge uv.

The performance of ACO is affected by:-

• The initial solution set derived by considering a small portion of space from a potentially available solution space.

• Algorithm consists of many functions based on random probability.

The diversity of initial solution archive is crucial for performance of ACO. To overcome this limitation a Hammersley Sequence Sampling (HSS) technique is introduced at the solution archiving stage. HSS has multi-dimensional uniformity property, which fully utilizes the poten- tial solution space to randomly chose values [25]. Algorithm 1 represents how HSS technique is used in ACO to develop an Efficient Ant Colony Optimization (EACO).

Algorithm 1 Efficient Ant Colony Optimization 1: Begin Program 2: Set MAXItr,�, K, Nants, NC, NO, NCG, NOpt and ND. 3: Initialize solution archive using HSS technique: S(K, NC, NO) 4: Initialize solution archive by randomly considering potential options: S(K,NCG). 5: Devise objective function from solution set S of size K: T(K,ND). 6: Rank solutions based on objective function: T = rank(R1, ....,Rk). 7: To deal with categorical problems, inculcate random number generated using HSS: 8: (MAXItr ∗Nants ∗ND,NOpt). 9: While termination criteria is unsatisfied

10: Develop a solution set equal to no. of ants Nants 11: For all Nants 12: Construction of solution is incremented. 13: For all ND 14: Construct continuous variables NC 15: Construct ordinal variables NO 16: Construct categorical variables NCG 17: End for ND 18: Calculate new objective function 19: End for Nants 20: Amalgamate and rank best solutions of size K. 21: S = Best(rank(R1, ....,RK, ..,RK+Nant,K) 22: Solution to be updated 23: End While 24: End Program

12

The parameter used in EACO algorithm are described below:

• MAXItr = a criteria for terminating the solution construction step, when it reaches a maximum threshold value.

• � = a tolerance factor between two sequential iterations.

• S = a solution archive of size K.

• Nants = number of ants.

• NC = number of continuous variables.

• NO = number of ordinal variables.

• NCG = number of categorical variables.

• NOpt = number of options available in categorical variables.

• ND = total number of decision variables.

3.2.3 Scheduling using EACO algorithm

The scheduling in Kubernetes cluster using EACO algorithm is represented in figure 3 with the help of a flow chart. The steps involved in scheduling are described below:

Step 1: The values of all the nodes will be initialized. Also the solution set will be initialized.

Step 2: Then the ants will be randomly placed on Nodes and they will be processed.

Step 3: If the termination criteria is met, the processing stops. Else it will start updating the solution set with the values of selected nodes.

Step 4: The solution set will be constructed incrementally using HSS technique.

Step 5: Step 4 will be executed until all the ants have been processed.

Step 6: After completing the construction of solution set, the values of selected Nodes are stored and further processed using objective function.

Step 7: The nodes are ranked based on their values using objective function.

Step 8: The best nodes is selected based on ranking and finally the solution set is updated.

13

Figure 3: Flowchart for Kubernetes scheduling using EACO

3.3 Proposed Implementation

The experiment will be conducted using CloudSim 3.0.3, a cloud simulation platform used to simulate the resource scheduling in cloud [31]. Kubernetes is an open-source framework, available on GitHub [32]. Python 3.7.3, an object oriented programming language will be used to develop code for EACO algorithm [33]. The Docker community edition 19.03.0 will be used to create containers [34].

The steps involved in experiment are given below:

Step 1: Setting up cloud environment using CloudSim simulation tool.

Step 2: Replacing existing scheduling algorithm with EACO.

Step 3: A sample application will be deployed on container.

14

Step 4: The experimental execution results will be captured and stored in a text file (logs.txt).

3.4 Proposed Evaluation

The performance of the EACO algorithm will be measured with respect to utilization ratio, response time and turn around time. The results of these parameters will be referred from the text file (logs.txt), in which the simulation execution results are stored. Based on these parameters the performance of EACO algorithm will be compared with the default scheduling algorithm used in Kubernetes. Going further, using the performance parameters of the proposed model will be compared against the Docker Swarm model implemented using ACO algorithm [8].

4 Research Timeline

The different tasks involved in implementation of the proposed model has been listed in figure 4 along with the time period to accomplish each of those task. The timeline associated each of those tasks is graphically presented using a Gantt chart in figure 5.

Figure 4: Implementation tasks for research project

15

Figure 5: Gantt Chart : Project Timeline

5 Conclusion

This research work explored the working of scheduling algorithm in Kubernetes framework, identifying its potential benefits and limitations, and then researching on algorithms which would help to overcome the limitations. The literature survey discussed about different task scheduling algorithms for placement of task on virtual machines and containers, and then the importance of EACO algorithm for solving optimization problem at enterprise scale. Considerable amount of research work has been accomplished for virtual machines, apparently container orchestration is a new technology, so there are very research work that has been conducted. Most of the work for task scheduling in container used Docker Swarm platform, so this research project focused on improving Kubernetes scheduling using EACO algorithm. The research project is quite challenging and hope to achieve the expected results by implementing the proposed model.

References

[1] A. Balalaie, P. Jamshidi, and A. Heydarnoori, “Microservices architecture enables devops: Migration to a cloud-native architecture,” IEEE Software, vol. 33, no. 3, pp. 42–52, 2016.

[2] M. Fazio, A. Celesti, R. Ranjan, C. Liu, L. Chen, and M. Villari, “Open issues in scheduling microservices in the cloud,” IEEE Cloud Computing, vol. 3, no. 5, pp. 81–88, 2016.

[3] A. Sampaio, H. Kadiyala, B. Hu, J. Steinbacher, T. Erwin, N. Rosa, I. Beschastnikh, and J. Rubin., “Supporting microservice evolution,” IEEE International Conference on Software Maintenance and Evolution (ICSME), pp. 539–543, 2017.

16

[4] W. Felter, A. Ferreira, R. Rajamony, and J. Rubio, “An updated performance comparison of virtual machines and linux containers,” IEEE International Symposium on Performance Analysis of Systems and Software, pp. 171–172, 2015.

[5] D. Merkel, “Docker: lightweight linux containers for consistent development and deploy- ment,” Linux Journal, 2014.

[6] D. Bernstein, “Containers and cloud: From lxc to docker to kubernetes,” IEEE Cloud Computing, vol. 1, no. 3, pp. 81–84, 2014.

[7] D. L. Sousa G, Rudametkin W, “Automated setup of multi-cloud environments for mi- croservices applications,” 9th International Conference on Cloud Computing, pp. 327–334, 2016.

[8] C. Kaewkasi and K. Chuenmuneewong, “Improvement of container scheduling for docker using ant colony optimization,” 9th International Conference on Knowledge and Smart Technology, pp. 254–259, 2017.

[9] E. Casalicchio, “Autonomic orchestration of containers: problem definition and research challenges,” ACM 10th EAI International Conference on Performance Evaluation Method- ologies and Tools, 2017.

[10] M. Z.Wei and Z.Jin, “Research on kubernetes’ resource scheduling scheme,” ACM, Proceed- ings of the 8th International Conference on Communication and Network Security, pp. 144– 148, 2018.

[11] R. Buyya et al., “A manifesto for future generation cloud computing: Research directions for the next decade,” ACM Computing Surveys (CSUR), vol. 51, no. 5, 2019.

[12] R. K. Barik, R. K. Lenka, K. R. Rao, and D. Ghose, “Performance analysis of virtual ma- chines and containers in cloud computing,” in 2016 International Conference on Computing, Communication and Automation (ICCCA), pp. 1204–1210, 2016.

[13] K.-T. Seo, H.-S. Hwang, I.-Y. Moon, O.-Y. Kwon, and B.-J. Kim, “Performance comparison analysis of linux container and virtual machine for building cloud,” Advanced Science and Technology Letters, vol. 66, no. 105-111, p. 2, 2014.

[14] H. M. Fard, R. Prodan, and T. Fahringer, “A truthful dynamic workflow scheduling mech- anism for commercial multicloud environments,” IEEE Transactions on Parallel and Dis- tributed Systems, vol. 24, no. 6, pp. 1203–1212, 2013.

[15] A. Amato, B. D. Martino, and S. Venticinque, “Multi-objective genetic algorithm for multi- cloud brokering,” Euro-Par 2013: Parallel Processing Workshops., vol. 8374, pp. 55–64, 2014.

[16] S. K. Panda and P. K. Jana, “Efficient task scheduling algorithms for heterogeneous multi- cloud environment,” J Supercomput, vol. 71, no. 4, p. 1505–1533, 2015.

[17] S. K. Panda and P. K. Jana, “Sla-based task scheduling algorithms for heterogeneous multi- cloud environment.,” J Supercomput, vol. 73, no. 6, p. 2730–2762, 2017.

[18] J. L. Lucas-Simarro, R. Moreno-Vozmediano, R. S. Montero, and I. M. Llorente, “Schedul- ing strategies for optimal service deployment across multiple clouds,” Future Generation Computer Systems, vol. 29, no. 6, pp. 1431–1441, 2013.

[19] L. Heilig, E. Lalla-Ruiz, and S. Vo, “A cloud brokerage approach for solving the resource management problem in multi-cloud environments,” Computers Industrial Engineering, vol. 95, no. C, pp. 16–26, 2016.

17

[20] M. E. Frincu and C. Craciun, “Multi-objective meta-heuristics for scheduling applica- tions with high availability requirements and cost constraints in multi-cloud environments,” Fourth IEEE International Conference on Utility and Cloud Computing, pp. 267–274, 2011.

[21] F. Legillon, N. Melab, D. Renard, and E.-G. Talbi, “Cost minimization of service deployment in a multicloud environment,” IEEE Congress on Evolutionary Computation, p. 2580–2587, 2013.

[22] Y. Guo and W. Yao, “A container scheduling strategy based on neighborhood division in micro service,” NOMS 2018 - 2018 IEEE/IFIP Network Operations and Management Symposium, pp. 1–6, 2018.

[23] D. Zhang, B. Yan, Z. Feng, C. Zhang, and Y. Wang, “Container oriented job scheduling us- ing linear programming model,” 3rd International Conference on Information Management (ICIM), pp. 174–180, 2017.

[24] C. Cérin, T. Menouer, W. Saad, and W. B. Abdallah, “A new docker swarm schedul- ing strategy,” IEEE 7th International Symposium on Cloud and Service Computing (SC2), pp. 112–1172017.

[25] U. M. Diwekar and B. H. Gebreslassie, “Efficient ant colony optimization (eaco) algorithm for deterministic optimization,” International Journal of Swarm Intelligence and Evolution- ary Computation, 2016.

[26] M. Dorigo and G. Di Caro, “Ant colony optimization: a new meta-heuristic,” Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), vol. 2, pp. 1470–1477, 1999.

[27] M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theoretical computer science, vol. 344, no. 2-3, pp. 243–278, 2005.

[28] K.-J. Kim and U. M. Diwekar, “Efficient combinatorial optimization under uncertainty. 1. algorithmic development,” Industrial & Engineering Chemistry Research, vol. 41, no. 5, pp. 1276–1284, 2002.

[29] “Creating a cluster | kubernetes engine documentation,” Google Cloud [online] Available at: https://cloud.google.com/kubernetes-engine/docs/how-to/creating-a-cluster, 2019.

[30] H. V. Netto, L. C. Lung, M. Correia, A. F. Luiz, and L. M. S. de Souza, “State machine replication in containers managed by kubernetes,” Journal of Systems Architecture, vol. 73, pp. 53–59, 2017.

[31] “Cloudslab/cloudsim,” [online] Available at: https://github.com/Cloudslab/cloudsim/releases/tag/cloudsim- 3.0.3, 2019.

[32] “Kubernetes,” [online]Available at: https://github.com/kubernetes/kubernetes, 2019.

[33] “Python release python 3.7.3,” [online] Available at: https://www.python.org/downloads/release/python-373/, 2019.

[34] Docker-Documentation, “Docker engine release notes,” [online] Available at: https://docs.docker.com/engine/release-notes/, 2019.

18