The skyline operator for selection of virtual machines in mobile computing

Published Online November 2018 in MECS DOI: 10.5815/ijmecs.2018.11.01

Mobile computing services have been widely used by mobile users recently. The article considers more efficient use of cloud computing resources benefiting from the latest Mobile Cloud Computing technologies. Rapid expansion of mobile devices (notebooks, tablets, smartphones, etc.) worldwide and Internet connection via telecommunication technologies (GPS, 3G, 3G, Wi-Fi, etc.) gave impetus to the emergence of the new technology - Mobile Cloud Computing. Obviously, although the capabilities of any mobile device (computing and memory resources) are limited, the users are widely using them for the solution of the tasks requiring great computing and memory resources. In this regard, cloud computing is extensively applied. Thus, the lack of computing and memory resources of mobile devices can be eliminated through cloud technologies [1]. Mobile cloud computing is a new platform that combines mobile computing and cloud computing, allowing solution of the complex tasks in cloud and storing large volumes of data. Mobile users can solve any task by using cloud computing services. Recently reduced prices of cloud servers enable mobile users to widely use cloud computing services [2]. In mobile cloud computing environment, the limitations of the technical capabilities mobile devices, wireless communication quality, and variety of application software are the key factors affecting the assessment of cloud computing. Various stages of building a mobile network infrastructure should be reviewed to eliminate network overload and communication channel delays for the effective use of mobile applications. In mobile cloud computing, devices connect to clouds over the Internet through the base stations (GPS, 3G, 4G, Wi-Fi, etc.) and use the necessary services. Currently, users are widely using three types of cloud services (IaaS, PaaS and SaaS services). Numerous research studies are devoted to the analysis of the separate features of these services [3,4,5]. Using the services of providers, millions of users benefit from mobile applications (mobile commerce, mobile education, mobile health, mobile games) [6,7,8]. Developed mobile applications do not depend on operating systems and types of mobile devices. Therefore, the number of mobile users using cloud services is growing day by day.

Users prefer the following criteria when using cloud technologies [9]:

• •    Minimum cost required for solving the problem;

• •    Minimum time for the problem solution;

• •    Reliable communication channels;

• •     Ensuring the security of users' data;

• •    Fast and reliable delivery of data and results to users;

• •    And so forth.

The key factors affecting the efficient use of cloud services in mobile cloud computing are [10]:

• •    remote location of data centers of the cloud computing systems from users;

• •    Internet overloading;

• •    network delays;

• •    breakages in communication channels;

• •    late delivery of data and results to users;

• •    use of cloudlets with different technical

• c apabilities on the network;

• •    non-optimal deployment of the user issues on cloudlets,

• •    And so forth.

The following strategies are projected to be used to ensure the timely processing of the users’ issues taking into account the above-mentioned problems:

• •    Creating a hierarchical network infrastructure based on cloudlets;

• •    Ensuring cloudlets’ deployment at the appropriate locations on the network;

• •    Deploying the applications in the nearest cloudlets to a user to reduce delays;

• •    Defining the capabilities of computing and memory resources of cloudlets;

• •    Selecting virtual machines in cloudlets complying with users' requirements;

• •    Using minimal communication channel between users and cloudlets;

• •    Deploying software applications with high usage

frequency in the cloudlet network in advance;

• •    And so forth.

The article proposes the development of a hierarchical network infrastructure to eliminate delays in communication channels that affect the prompt processing of user tasks. At the same time, the problem of selection of VM satisfying the user requirements (execution time and cost) are considered. In this paper, a new algorithm to create skyline is proposed. It is known that when the number of VMs in a skyline is large, then the choice of a subset of VMs that meets the user requirements becomes very hard. To this end, this article proposes a strategy for choosing a subset of VMs from the skyline.

The paper is organized as follows. Section 2 introduces the overview of related work. Section 3 reviews the issue of developing a cloudlet-based hierarchical architecture. Section 4 presents an algorithm selection of VMs based on the skyline operator, which meets the user requirements. Experiments are presented in Section 5.

Finally, Section 6 concludes the paper and suggests future work.

• II.    Related Work

This section reviews the studies devoted to the development of virtual machines meeting users’ requirements. Optimal deployment of wide range of tasks with a large number of mobile users on cloud-based virtual machines is of great importance. Most research on mobile cloud computing technologies are dedicated to the effective organization of the processing of the user requests on a remote cloud server [12, 13]. Providing solution of the users’ tasks on the nearest cloudlets and reducing the number of communication channels to the number of links between cloudlets and users, the delays can be eliminated and reliable network performance can be ensured. Power consumption, delays and breakages can be reduced by properly deploying the user interface and key parts of the software applications used by users in mobile devices and cloud servers respectively [14]. Some researchers point out the extensive delays in data sharing between the user and the remote cloud because due to the physical distance between the cloud servers and users [15]. Close deployment of cloud servers significantly reduces delays in data sharing [16].

The article [17] addresses the issue of selecting virtual machines that can provide faster solution of the task on the user’s demand by utilizing the technical capabilities of cloudlets and the virtual machines built in them. The article [18] investigates the balanced optimal distribution of mobile applications across the cloud servers of the mobile networks.

Some studies [9, 12] focus on the creation of network infrastructure of cloudlets located near the access points of the WMAN. It is recommended to build cloudlets near all access points of the mentioned network. However, it is not cost-effective and raises the price of the network. On the other hand, cloudlets placed near any access point can be less used or unused at all. Therefore, it is suggested to located cloudlets in the vicinity of more mobile users (shopping malls, libraries, schools, universities, stadiums, stations, airports, etc.). Some research studies [19] explore conditions requiring the creation of cloudlets in mobile computing clouds and predict which base stations are better to locate cloudlets near. In [20], reduction of energy consumption through optimal distribution of tasks between the cloudlets and the remote cloud server is considered. Some researchers review faster solution of the task by distributing software attachments across multiple cloudlets [21]. While others suggest that the small number of communication channels between the user and the cloudlet can provide high quality performance of software tools implemented in cloud with less delays and minimal fractures [22].

Rapid development of cloud computing and the use of multiple technical and software tools by many users may cause network security risks and network attacks. Researches show that some users using the same virtual machine can deal with hazardous activities. Therefore, some authors offer flexible protection systems to guard virtual machines from internal users [23]. Some authors consider migrating mobile cloud services (placing services closer to users in cloudlets) and show some advantages of this method. To implement this process, a simple algorithm can be created by taking into account the access frequency of applications. When higher-priority software maintenance is needed, relatively less-used software, which is stored in the memory, can be deleted from the cloud memory resources [24]. The article [25] examines the problem of building initial computing resources (virtual machines) using a hierarchical analysis method for the efficient use of cloud computing environments.

Skyline operator is very important in real life and has wide-ranging applications in various fields (for example, tourism, retail industry etc.) that involve multi-criteria decision making (MCDM). The Skyline operator is used for reducing the decision space. The skyline operator filters out a set of interesting points based on a set of evaluation criteria from a potentially large dataset of points. The skyline of a set of multi-dimensional data points is the set of points, called skyline points, each of which is not dominated by any other point in the set. Given two points x and y, x dominates y means that the values of x are not worse than those of y in any dimension, and better at least in one dimension. In general, the skyline of a data point set X is the set of best points in X, and different skyline points represent various trade-offs between the dimensions [26-30].

At the present time, TripAdvisor platform is one of the most crowdsourcing sites, where travelers write reviews about hotels through an evaluation form. Then, collected reviews are used later to answer users’ queries about the best hotels regarding some criteria (for example, the cheapest and closest hotel to the beach). Since, the TripAdvisor cannot answer to a multi-criteria query of users, [31] proposed a new evidential skyline operator to meet the multi-criteria filtering objective of the users. The proposed skyline operator is based on belief functions theory. In the proposed skyline operator, first, reviews are modeled as basic belief assignments. And then, the belief functions are used to combine reviews considering the travelers’ reliabilities. For extracting possibilistic RDF data, in [32], the skyline operator is used to find out a small set of resources that satisfy predefined user preferences. For computing the skyline with a reasonable performance, [33] proposes an efficient algorithm. For grouping the skyline set into k clusters [34] applied US-ELM (Unsupervised Extreme Learning Machine). At next step, to select a point as the representative point in each cluster, they proposed a method.

The paper [27] proposes a visual analytic system SkyLens, which helps users in organizing, interpreting, and comparing skyline points from different perspectives and at different scales. The paper [28] proposed a hybrid approach to rank-order Skyline Web services, which mixes several methods borrowed from MCDM field.

Although in recent years, the skyline has attracted a lot of attention due to its wide application, computation of the skyline is a challenging issue as there is a high probability that today’s applications deal with large and high-dimensional data. The paper [33] proposes a novel data space partitioning method for parallel and distributed skyline computation that consists of two-phases: diagonal and entropy score curve based partitioning. For efficiently processing skyline queries for large data in parallel, [34] proposes a novel two-phase approach in MapReduce framework. In the first phase, they start by dividing the input dataset into a number of subsets and then they compute local skylines only for the qualified subsets. Note that another efficient parallel algorithm SKY-MR+ for processing skyline queries using MapReduce has recently been offered in [35]. For continuous skyline computation, the paper [36] proposes a balanced joint rooted tree algorithm and a nondominated relation cache.

• III.    Building Hierarchicallly Structured Network Infrastructure Based On Cloudlets

The core concept of mobile cloud computing is the cloud service providing computing and memory resources to mobile users. Although cloud servers have high computing and memory resources in centralized mobile computing systems used by users, they are not capable to provide high speed data delivery to users. Rapid increase in the number of mobile cloud computing users leads to network (communication channels) overload causing great delays in delivery of the processed data to the user. To eliminate this shortage, cloud computing resources are located closer to the user. Hierarchically (two-level) structured mobile cloud computing is used to solve the problem (figure 1).

MCC typically consists of three parts: mobile devices, wireless networks and clouds. Cloud servers of cloud computing system are deployed in Level 1, and cloudlets are located close to base stations in Level 2. Cloudlets (minor cloud computing) are the devices (servers) placed near the base stations of the wireless network ensuring faster solution of the user problem.

A hierarchically structured architecture built using Resource Manager (RM) is proposed for efficient use of cloudlet resources [37]. RM center of the hierarchical network contains information about the technical capabilities of virtual machines built in cloudlets. At the same time, virtual machines in RM are grouped (low, medium, high) by their technical capabilities (performance, number of cores, capacity of memory, etc.). This classification is determined by the frequency of processor’s performance used to build virtual machines and the number of cores. When a user sends a request to the RM center to solve the task, the center sends the user information about the technical capabilities of currently vacant virtual machines. The user chooses a virtual machine based on this information, and then solves the problem. Here, when mobile users access the cloud, they first connect to the proposed RM, which then connects the user to the corresponding cloud server as soon as

Fig.1. MCC structural scheme based on cloud computing

possible, and the mobile user can easily use the cloud services. Mobile devices are connected to mobile networks through base stations (e.g., 3G / 4G, access point - Wi-Fi, etc.) that establish and manage connections (air connection) between the network and mobile devices. Mobile users’ requests and information (e.g., ID and location) are transferred to RM center (central processor connected to the server), which provides mobile network services. Here, mobile network operators provide services such as home agent (HA) stored in database and AAA (authentication, authorization, and accounting) based on subscriber data. Subsequently subscribers’ requests are sent to the server that provides the Internet connection of RM of the proposed model, and the contact with the relevant cloud is established via the Internet. RM contains information about computer equipment (server, desktop, notebook, etc.) used for building cloudlets. Moreover, RM includes information about the technical capabilities of the cloudlets (processor's operation frequency, number of processor cores, number of virtual machines, their technical specifications, amount of memory, etc.), while the mobile network includes the information about how near the mobile user is located to the cloudlet. Therefore, based on an incoming query, the question of which cloudlets and virtual machine the software applications called from the cloud servers are located in is of great importance.

In many cases, users do not properly choose the type of virtual machine in accordance with the resource required to solve the task in it. Software applications to be supported by certain mobile cloud infrastructure or not are identified based on requirements (computing intensity, network coverage and network delays) of the cloud infrastructure features as mobile device, network coverage and delay vectors. When users use social network they do not specify certain requirements for large-bandwidth resources (low), network transmission capabilities (medium), and network delays (high). However, if the user is using biometric recognition, HD video data, online games, translation and navigation software, then requirements to above-mentioned cloud infrastructure attributes are high. High resolution and content applications, such as real time recognition, require the use of high-bandwidth and low-latency networks such as LTE. This, in turn, ensures fast and seamless delivery of face recognition algorithms and large data launched in the cloudlets to the users’ devices. A high- bandwidth and low latency environment for high-transmission software applications can be achieved through the use of cloudlets’ VM located near the user

• [23] . Mentioned delays can be eliminated through the cloudlet networks built close to users.

• IV.    Algorithm For Selection Of Virtual Machines

This section deals with the selection of VM, which meets the users’ requirements (time and cost).

Assume that it is required to solve any task Z in the VM of cloudlet. For this purpose, there are n number of VMs ( vm ₁ ,…, vm_n ) with different computing performance. Note that, depending on the computing performance of VMs, their pricing policies differ. In other words, the costs of the solution of the same task in different VMs vary.

Assume that the task Z is to be solved in the VM so that both required time and cost will be minimum. The problem statement shows that this is a matter of multicriterion optimization. That is, two criteria are required to be optimized (minimized) simultaneously. Unfortunately, these two objectives balance each other. Thus, VMs with high computing performance are often more expensive. But what is the best VM in this case? VMs can be selected only according to the decision of the decision maker. In this case, any VMs that are not worse than other VMs for both indicators (time and cost) are taken into account. Two-dimensional Skyline operator is used to select VMs that are of interest [38]. The decision maker can make the final decision on the time and cost spent by using this operator.

In literature, Skyline operator is known as a task of finding the maximum vector [39]. In this method, the name Skyline is taken from its graphic description. More formally, Skyline is a set of multiple points, any other point beyond of which has no advantage over this set of points. This advantage means that if a point (i.e., VM) is better or much better than other point (VM) for both indicators (in our case, time and cost), or if it is better at least for one indicator, then, this point (VM) has the advantage over other points (VM). For example, a VM with time = 5 hours and cost = 800 USD has the advantage over other VMs with time = 10 hours and cost = 1000 USD. In other words, the first VM is better than the second VM for both indicators. Another example, VM with time= 4 hours and cost = 600 USD, has the advantage over other VMs with time = 4 hours and cost = 650 USD, because the first VM has the advantage over the second VM for the second indicator (600 USD).

Before solving the problem, assume that required time and cost spent to solve the task Z on each vm are known. The time spent to solve the task Z on the i th VM ( vm ) is denoted by t , and the cost by c . Then each VM can be described as a two-dimensional vector:

^vm, = vm i ⁽ t i .'c i ), i = 1,-, n . (1)

Obviously, the time spent on the task solution depends directly on VM’s computing performance. The more the computing performance increases, the more the time spent decreases. On the other hand, the cost of solving the problem also depends on VM’s computing performance. The more the computing performance increases, or the less the time spent, the more the cost required to solve the task increases.

Skyline is built with the following algorithm:

Step 1. The times spent for solving the task on different VMs are presented in the increasing order: t, < t2 <... < tk , k < n . The case k < n means that there are several VMs with the same execution time, but different required costs. Or vice versa: there are several VMs with different execution time, but the same required costs. In other words, t„ = t„ and c„ * c„, or t„ * t„ and pq  pq  pq cp = cq may be for two different vmp = vmp (tp;cp) and vmq = vmq (tq;Cq ), ( P * Q )•

Step 2. VM, which requires the least costs for each specified time t , is selected:

vm, (t^c ™^m) = argmin_c vm ,. ( t^c ), i = 1,..., n .  (2)

Step 3. If the cost ( c ^min) required by the selected VM in accordance with the time t_i+ , >  t_t is greater than c m ⁱⁿ, then that VM is not selected for Skyline . In other words, if t ,₊,> t, and c min >  c ^min , i.e., if the following vm _{+ 1}( t i _{+ 1} , c min ) defeated by the previous vm i ( t i , c ™^m)for its time and cost, then it will not be selected for Skyline .

Once the Skyline is established, the next step is to select a VM that meets the requirements of the decision maker. The following appro ac h is applied for this:

• 1)    The center O    ( t,c )  of the set of points

Skyline = {vm(t; cxmin),vm(t2; cmmin),...,vms(ts; cmin)}    included into Skyline is calculated:

SS t = 1 ^t and c = 1 ^cmm,         (3)

SI^i i          S15

where S is the number of points (VMs) in Skyline .

Since nature and range of variables of the indicators (time and cost) characterizing the VM differ, then vm ( t , c ^min) are normalized. For normalization the min-max strategy is used, which linearly transforms the variable x to the variable y :

x - хшш

У =-----^ ,               (4)

max min where x and x are the minimum and maximum min        max values of the variable x .

Thus, the interval [x   , x ] of the variable x is transformed to the interval [0,1] .

• 2)    Using the Euclidean distance, the distance from each point of Skyline set to the center of this set is calculated:

dist( vm , O skyline ) = V ( b - t )² + (c m ⁱⁿ - c)² , i = 1,2,..., 5 . (5)

The points are ordered according to the distance from the center. The center is a reference point for a decision making.

• 3)    The closest point to the center is taken as the best solution. If this solution does not meet the decision of the decision maker, the next point is selected and the process is continued until the decision maker is satisfied.

• V.    Experiment

Assume that there are 31 VMs. The execution time and required cost for solving task on different VMs are given in Table 1.

Table 1. Time and required cost for solving task on different VMs

VMs	Time ( ti )	Cost ( ci )	VMs	Time ( t i )	Cost ( c i )
vm	10	70	vm 16	50	25
vm	10	60	vm	60	31
vm	20	55	vm 18	60	26
vm 4	20	46	vm 19	70	25
vm	20	35	vm 20	70	22
vm 6	25	37	vm	80	26
vm	30	52	vm	80	20
vm 8	30	46	vm 23	90	28
vm 9	30	40	vm 24	90	25
vm 10	30	30	vm 25	90	16
vm 11	40	37	vm 26	100	24
vm	40	33	vm	100	20
vm	40	28	vm 28	100	17
vm 14	50	31	vm 29	100	15
vm 15	50	27	vm 30	100	12
			vm 31	100	9

Each VM is described as a point on the coordinate plane (Figure 2). Using Eq.(2) the best (in other words, the least expensive) VM at each time tx = 10 ; t2 = 20 ; t3 = 25 ; t4 = 30 ; t5 = 40 ; t6 = 50 ; t7 = 60 ; t8 = 70 ; t, = 80 ; t0 = 90 ; t11 = 100 is selected. Thus, the following VMs will be selected: vm (10;60) , vm (20; 35) ; vm (25; 37) ; vm (30; 30) ; vm (40; 28) ;

vm ₁₆(50; 25) ; vm ₂₀(70; 22) ; vm ₂₂(80; 20) ; vm ₂₅ (90;16) and vm (100; 9) .

According to the procedure given above (Step 3), vm (25; 37) does not have any advantage over previous VM ( vm (20;35) ) for both indicators (time and cost), consequently this VM cannot be selected for Skyline . Each subsequent (in terms of time) VM has the advantage over the previous VM (in terms of cost). Thus, the following points (VMs) will be selected for Skyline : vm ₂ (10; 60) , vm (20; 35) ; vm (30; 30) ; vm (40; 28) ; vm (50; 25) ; vm (70; 22) ; vm ₂₂(80; 20) ; vm (90;16) and vm (100; 9) . These points are highlighted in red in Figure 1.

The points selected for Skyline and their coordinates after subsequent normalization are given in Table 2. Table 2 shows the Euclidean distance of each Skyline point (i.e. VM) in the last column from the center, and VMs are ranked in according with these distances. The ranks are shown in square brackets.

Thus, the decision maker is offered the following ordered list:

vm ₆ (50; 25) >  vm ₃(40; 28) >  vm ₂₀ (70; 22) >

* vm ₀ (30; 30) >  vm ₂ (80; 20) >  vm ₅ (20; 35) >  ^   (6)

vm ₂₅(90;16) >  vm _x(100;9) >  vm^ (10; 60)

The a ^ b means that a is better than b .

The decision maker can start choosing consistently from the first VM ( vm ). Note that if the decision maker previously limits the time and cost, the selection process will be easier. For example, decision-maker specifies conditions 30 <  t <  100 and 20 <  c <  60 on the predefined time and cost of the given example, then the choice will take place only among vm , vm and vm . In fact, there will be set of VMs vm ₃₀ < _t < ₁₀₀ = { vm₁₃,vm₁₆, vm ₂₀ , vm ₂₂ , vm ₂₅} that meets the condition 30 <  t <  100 and set of VMs vm 20 < _c < ₆₀ = { vm₅,vm₁₀, vm₁₃, vm₁₆, vm ₂₀} that meets the condition 20 <  c <  60 . Then, the VMs that meet both conditions will be the intersection of these two sets: ^vm 30 < t < 100 A ^vm 20 < c < 60 { vm ₁₃ ,vm ₁₆ , vm ₂₀} .

In the offered method both indicators (time and cost) are considered to have the same degree of importance. In this case, undeniably, the question arises: if these indicators have different degree of importance, then how the selection will be made? In this case, the problem solution requires a new approach, which will be investigated in the following studies.

Fig.2. Time and required cost for solving task on VMs

Table 2. Time and required cost for solving task on different VMs

	Before normalization		After normalization		Euclidean distance from Skyline center
	Time ( t )	Cost ( c )	Time ( t )	Cost ( c )
vm	10	60	0.00	1.00	0.81	[9]
vm	20	35	0.11	0.51	0.41	[6]
vm 10	30	30	0.22	0.41	0.28	[4]
vm 13	40	28	0.33	0.37	0.16	[2]
vm 16	50	25	0.44	0.31	0.07	[1]
vm 20	70	22	0.67	0.25	0.21	[3]
vm 22	80	20	0.78	0.22	0.32	[5]
vm 25	90	16	0.89	0.14	0.45	[7]
vm 31	100	9	1.00	0.00	0.62	[8]
O skyline ( t,c )	54.44	27.22	0.49	0.36

Fig.3. Skyline of VMs

• VI.    Conclusion

The article provided a solution to the problem of placing the mobile users' tasks on virtual machines built in the cloudlets placed near the base stations of WMAN, considering the technical capabilities of virtual machines. It explored the problems that arise in mobile cloud computing and their solutions, as well as the characteristics of the user tasks and virtual machines in the course of problem solving. The article presented an expression of resource indicators of the virtual machines in the form of a normalized value. Hierarchically structured architecture and algorithm based on cloudlets were proposed for the selection of virtual machine that meets the time and cost requirements set by the user to solve the task. An algorithm based on skyline operator was offered. An approach to the optimal VM selection out of VM set based on Skyline operator was proposed for the solution of the two-criterion selection task. Approaches to the optimal VM selection out of VM set based on the Skyline operator in accordance to the multicriterion request (execution time, cost, reliability

Acknowledgment

This work was supported by the Science Development Foundation under the President of the Republic of Azerbaijan – Grant № EIF-2014-9(24)-KETPL-14/02/1.