{'fraction_non_alphanumeric': 0.04513189448441247, 'fraction_numerical': 0.005803357314148681, 'mean_word_length': 4.18552598856006, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Flocking virtual machines in quest for responsive IoT cloud services

We propose Flock; a simple and scalable protocol that enables live migration of Virtual Machines (VMs) across heterogeneous edge and conventional cloud platforms to improve the responsiveness of cloud services. Flock is designed with properties that are suitable for the use cases of the Internet of Things (IoT). We describe the properties of regularized latency measurements that Flock can use for asynchronous and autonomous migration decisions. Such decisions allow communicating VMs to follow a flocking-like behavior that consists of three simple rules: separation, alignment, and cohesion. Using game theory, we derive analytical bounds on Flock's Price of Anarchy (PoA), and prove that flocking VMs converge to a Nash Equilibrium while settling in the best possible cloud platforms. We verify the effectiveness of Flock through simulations and discuss how its generic objective can simply be tweaked to achieve other objectives, such as cloud load balancing and energy consumption minimization.


I. INTRODUCTION
Live Virtual Machine (VM) migration is essential for improving the responsiveness of cloud services. VMs, hosted in Edge Cloud (EC) platforms, install resource-rich cloud services close to data sources and users to realize Internet of Things (IoT) applications. Such VMs provide, for example, real-time video analytics services from cameras to mobile applications. Hosting VMs near the edge can subdue the end-to-end services latency from hundreds to tens of milliseconds compared to hosting VMs in conventional cloud platforms [1], [2]. Existing resource provisioning algorithms migrate VMs from one EC to the other in response to device mobility and service computational capacity requirements. VM migration ensures minimal average latency between mobile devices and the EC [3], [4]. Migration can achieve other goals such as load balancing, efficient service chaining and orchestration, infrastructure cost minimization, efficient content delivery, and energy efficiency, to name a few [5].
However, migrating VMs in response to the mobility of IoT devices is a limited decision given the diverse IoT use cases. Such a mobility-triggered migration assumes a constraining IoT use case in which a cloud service, installed in VMs, communicates with one -and only one -IoT device [2]. Consider EC services for smart glasses as an example. Migrating a VM, which hosts video processing cloud services of a Google glass, minimizes the video processing latency as the glass/user moves, a goal that is reasonable to target only for the Google Glass use case, in which the Google Glass is the singleton client that uses the EC video processing services [2], [3]. However, in general IoT use cases, several VMs, very likely to be deployed in different ECs, are needed to execute distributed algorithms (e.g. computer vision feature extraction, consensus, and aggregation [6]) and require intensive communication among the VMs and/or the devices. Distributed computer vision, for example, enables distributed context-aware applications such as autonomous vehicles and intelligent traffic systems [7]. Predominantly for modern IoT applications, developers implement analytics via large-scale distributed algorithms executed by VMs in geographically distributed and heterogeneous cloud platforms [8], [9].
In this paper, we propose Flock; a simple protocol by which VMs autonomously migrate between heterogeneous cloud platforms to minimize their weighted latency measured with enduser applications, IoT devices, and other peer-VMs. In Flock, a VM uses only local latency measurements, processing latency of its hosting cloud, and local information provided by its hosting cloud about other clouds which the VM can migrate to. A VM greedily migrates to a cloud platform that reduces its regularized weighted latency. We prove, using game-theory, that Flock converges to a Nash Equilibrium (NE) and its Price of Anarchy (PoA) is (1 + ǫ) given the properties of our proposed social value function. We discuss how Flock serves a generic goal that we can redesign using simple tweaks to achieve other objectives such as load balancing and energy minimization. Our design allows VMs to imitate a flocking-like behavior in birds: separation, alignment, and cohesion.

II. SYSTEM MODEL AND OBJECTIVE
We consider a network of VMs modeled as a graph G = (V, P ), where V denotes the set of n VMs and P denotes the set of VM pairs such that p = (i, j) ∈ P if the i-th and j-th VMs communicate with each other. Let d ij ∈ R + denote the traffic demand between VMs i and j and assume that d ij = d ji . We also consider a set, A, of m clouds (i.e. ECs, or conventional clouds) that communicate over the Internet. A VM i autonomously chooses its hosting cloud.
Let x i ∈ A denote the cloud that hosts i and let l(x i , x j ) > 0 be the average latency between i and j if they are hosted at x i and x j respectively (Note: if i and j are hosted at the same cloud x i = x j ). We assume that l is reciprocal and monotonic. Therefore, l(x i , x j ) = l(x j , x i ) and there is an entirely nondecreasing order of A → A ′ such that for any consecutive The reciprocity condition ensures that measured latencies are aligned with peer-VMs and imitates the alignment rule in bird flocking. We model is the average packet latency between x i and x j , and τ (x i , x j ) = τ (x j , x i ). The quantity ρ(x) is the average processing delay of x modeled as: ρ(x) = δ i∈V :xi=x j∈V d ij /(γ(x) − i∈V :xi=x j∈V d ij ), where δ is an arbitrary delay constant and γ(x) denotes the capacity of x to handle all demanded traffic of its hosted VMs. An increased value of ρ(x i ) signals the VM i that it is crowding with other VMs in the same cloud, imitating the separation rule in bird flocking.
A VM i evaluates its weighted latency with its peers if hosted at x as Our objective is to design an autonomous VM migration protocol that converges to an outcome σ = (x 1 , x 2 , . . . , x n ) that minimizes the sum of weighted latency i∈V u i (x i ). That is to say, σ maximizes the responsiveness of all VMs given their peer-to-peer communication pattern (i.e. connectivity and demands).

III. Flock: AUTONOMOUS VM MIGRATION PROTOCOL
We design a simple protocol that allows a VM to autonomously decide its hosting cloud among a set A i ⊆ A of available clouds by relying on only local regularized latency measurements. We call A i the strategy set of i. Every cloud x evaluates its current weight w x = i:xi=x u i (x) and advertises a monotonic non-negative regularization function Since each VM is hosted by a single cloud and all VMs have access to the same strategy set, the VM migration problem is modelled as a singleton symmetric weighted congestion game with the objective of minimizing the social cost C(σ) = is approximately 1, this game model is approximately equivalent to minimizing i∈V u i (x i ). Throughout, we use x i − → y to mean that a VM i migrates from cloud x to cloud y. Letting η ≤ 1 be a design threshold, we propose the following migration protocol: Flock: Autonomous VM migration protocol.
Initialization: Each VM i ∈ V runs at a cloud x ∈ A. Ensure: A Nash equilibrium outcome σ.
1: During round k, do in parallel ∀i ∈ V Greedy migration process imitating cohesion in flocking: We now first begin by proving that Flock converges to a Nash equilibrium, where each VM chooses a single cloud (strategy) and no VM has an incentive (i.e. less average latency) to migrate from its current cloud. Then, we derive an upper bound on Flock's PoA for general regularization functions, f , following a similar approach to [10]. Finally, we propose a regularization function f (w x ) ≈ 1 that achieves a tight PoA of at most 1 + ǫ.

A. Equilibrium
Convergence to a Nash equilibrium in Flock is non-obvious given the inter-dependency of a VM's average weight with its peers.
Theorem 3.1: Flock converges to a Nash equilibrium outcome. Proof Any step of Flock corresponds to choosing a random outcome from a finite number of outcomes. We show that any step of Flock reduces the social value C(σ) and C(σ) is bounded below. We first show that if a VM i migrates from cloud x to cloud y, the increase in y's weight is less than the decease in x's weight. We then use contraction to show that if a subset of i's peers have a total latency that increased after i migrates, the remaining peers must have a total latency that decreased by a greater value. Let σ k and w k x denote the game outcome and the weight of x at round k respectively, and let .
As α < f < 1, we have two extreme cases: , which implies that: Because of the migration: ∆w x < 0 and ∆w y > 0, but |∆w x | ≥ u i (x), and |∆w y | ≤ u i (y). otherwise i would not migrate, then denote the regularized weighted latency and let z t i denote its value at round k. After the migration, i's peers split into two subsets: . Substitute with the weighted latency value from (1) and since the demands (i.e. d ij ) remain unchanged, j∈Vinc l(x j , y) > k∈Vdec l(x k , y). By the reciprocity of l, j∈Vinc l(y, x j ) > k∈Vdec l(y, x k ), and u i (y) ≥ u i (x), which contradicts (2). By this contradiction and from (3), the social value C(σ k+1 ) ≤ C(σ k ). Since n and m are finite, the number of all possible outcomes is finite. An outcome after a VM migration, σ k+1 , corresponds to randomly choosing an outcome from the finite outcome space which reduces the social value. Since C(σ) > 0, then Flock must converge to a Nash equilibrium.

B. Price of Anarchy
We first give a generic upper bound of the PoA, then we propose our regularization function that tightens the PoA.

Theorem 3.3:
The regularization function f (w) = exp(−1/(w+a)) tightens the PoA to 1+ǫ for a sufficiently large constant a and reduces the game to the original VM migration problem, i.e. minimizing i u i (x i ).
Proof For For an infinitesimally small value of ε, we can choose a such that

IV. EXPERIMENTAL RESULTS AND DISCUSSION
We numerically evaluate Flock using several simulation rounds. In each round we model the clouds as a complete graph with inter-cloud latency τ ∼ Uniform(10, 100) and cloud capacity γ ∼ Uniform(50, 100). We simulate the peer-to-peer relations of VMs as a binomial graph with d ∼ Uniform(1, 10). Each simulated VM runs Flock asynchronously. Fig. 1 shows the average rounds, k, required to converge to a Nash equilibrium at 95%-confidence interval with 0.1 error in simulations. Although in the worst case k = O(n log(nf max )), where f max is the maximum value of the regularization function f [11], Fig. 1 suggests that Flock scales better than O(n) on average. The proof of the average convergence time is complex and depends on properties of the social value C(σ) and other parameters. We leave this proof for future work. Fig. 2 shows the PoA statistics of Flock with different η. We implemented the optimal solution as brute-force in simulations that evaluates the minimum social value among all possible VM to cloud assignments. As η ≈ 1, the maximum PoA achieved matched the theoretical value of 1.21. In practice, it is desirable to to keep η < 1 (e.g. η = 0.7) to avoid migrations with insignificant improvements and alternating migrations between clouds. Although the worst case PoA for η = 0.7 approaches 4.5, the average PoA is acceptable in practice.

A. Special Cases: Load-balancing and Energy Efficiency
Flock can be redesigned with simple tweaks to suit other common cloud resource provisioning problems. We consider load-balancing and energy efficiency as special cases.
In load balancing, we seek an outcome σ such that the total load is distributed proportionally to the clouds' capacities. We first force the latency τ = 0 between any cloud pairs x, y ∈ A. This is equivalent to marginalizing the effect of latency on the social value. We also force the VMs to ignore their peer relationships (i.e. P = ∅). The problem transforms immediately to minimizing the sum of cloud utilization. A VM in this setup greedily migrates to the least loaded cloud. Fig. 3 shows the ideal mean utilization for a load-balanced system ('+') and the mean utilization using Flock ('*'). The box-plot also gives a summary statistics of the extreme value and the 75%-percentile samples. Flock performs very well as a load balancing protocol.
The energy-efficiency goal seeks an outcome σ in which the maximum number of clouds are idle (i.e. with ρ = 0). We (virtually) force each VM to be connected to all other VMs (i.e. P = V × V ). We also force τ to be a very large value (i.e. τ → ∞, and d = 1). With this tweak, a VM favors a cloud that hosts the largest number of VMs and with enough capacity ρ. Fig. 4 shows the ideal number of idle clouds that minimizes the energy consumption under a certain load (upper bound) and the number of idle clouds using Flock under the same load.

B. Impact of system dynamics
We now study the impact of various system dynamics on Flock's convergence. If we considered any two Flock steps at discrete times (k − 1) and k, the values of the VM's utilities, u i , evolve randomly. Both external factors and VM migrations can influence this evolution, which introduce difficulty in the convergence analysis of Flock. The simplest approach to deal with such dynamics is to assume that changes in latencies, EC capacities, and any other state are much slower than Flock convergence. This means that changes in u i due to external factors such as link bandwidths or EC failures varies slowly. It also means that Flock steps are very rapid and Flock measures only average values of l or any other system state. Fortunately, we have shown that Flock converges in a finite number of steps. However, we cannot guarantee that this number of steps are taken much faster than changes in any system state. We will follow the approach in [12] to show that despite that Flock may take slow migration decisions, its convergence still holds if we modeled the network dynamics (e.g. l) as a continuoustime Markov process that has values that are generated by the migration steps of Flock.
Consider modeling the utility of a VM as a general discretetime stochastic process such that: ∀k ∈ Z, u i,k+1 = u i,k +b k ω k , where u i,k+1 is the utility value of VM i at the discrete-time k, b k is a design parameter, and ω i,k is a random variable that takes values according to both external factors that impact u and Flock migrations prior to time k. For all k ∈ Z, the values of ω are determined by ω i,k = h(u i,k , Y i,k ) and is a continuous-time Markov process of generator G u i,k and with values in a finite set M, f : M ← R K is an arbitrary mapping, and h : R L ×R K ← R L is a bounded continuous Lipschitz function in u and is uniformly distributed in Y . The Markov process m i (t) is irreducible and ergodic where m i (k) = lim t→k,t<k m i (t). We previously assumed that u i,k is bounded, which is true given the bounded latencies, VM demands, and EC capacities. We also can enforce such bounded values of u by projecting u i,k to a finite subset of R L . Finally, we assume that b k is positive and decreasing in k, such that b k is constant as k → ∞, so that k b k = ∞ and k b 2 k < ∞. By adopting the discrete time factor into the values of u i,k , we transfer Flock into a class of stochastic approximation algorithms with controlled continuous-time Markov noise [13]. As b k is a decreasing step size, the speed of variations in u i,k decreases and vanishes as k increases. This is equivalent to modeling m i (t) as a Markov process with a fixed generator (e.g. when τ values are frozen), and converges to an ergodic behavior. Hence, as k increases, Flock uses averaged values of u i and represents a stable dynamical system (see [13] for formal proofs of the convergence of stochastic approximation algorithms). We call the modified migration protocol, controlled-Flock and is given as: Controlled-Flock: Autonomous VM migration protocol.
Initialization: Each VM i ∈ V runs at a cloud x ∈ A. Ensure: A Nash equilibrium outcome σ.
1: During round k, do in parallel ∀i ∈ V Greedy migration process imitating cohesion in flocking: 2: i solicits its current strategy A i from x. 3: i randomly selects a target cloud y ∈ A i . 4: if u i,k (y)f (w y +u i,k (y)) ≤ ηu i,k (x)f (w x −u i,k (x)) then 5: x i − → y. 6: In the above algorithm, b k is a decreasing step size and is left as a design parameter. For example b k = 1/k satisfies the decreasing condition of b k and that k b k = ∞ and k a 2 k < ∞. If b k is constant, we would obtain weak convergence only. The function f (w x ) serves as the random variable ω i,k for a VM i. In such case f (w where Y i,k = k+1 k j:xj =x,j =i u j,t (x)dt and u j,t (x) is the continuous-time value of u j . The Markov process m i (t) in this case represents the current outcome σ k and that f (m i (t)) = j:xj =x,j =i u j,t (x) is an arbitrary mapping that is bounded and continuous Lipschitz function. We can easily verify that the properties of stochastic approximation algorithms with con-trolled continuous-time Markov noise as described earlier are satisfied and convergence of Controlled-Flock is ensured given the various dynamics.

C. Migration cost
Migration of a VM can be too costly to perform very frequently. Depending on the implementation details of a VM and the workload it serves, migration can involve transferring a large data volume between EC, which introduces a significant network overhead. For some cloud services, frequent migration can cause intolerable service interruption, as the "down-time" due to a migration can range from few milliseconds to seconds [14]. Accounting for the migration cost in Flock can be desired for several applications. We incorporate the migration cost in Flock utility values by two methods.
First, we include the migration cost as an external dynamics in the VMs' utilities and use Controlled-Flock to minimize the utility, which also includes the average migration cost. Let g i (k) ∈ {0, 1} indicate whether i migrated at time k or not. Also let R i (k + 1) = β i R i (k) + (1 − β i )g i (k) denote the average forgetting value of the migrations of VM i, where 0 ≤ β i ≤ 1 is a VM specific parameter that reflects the impact of frequent migrations on service disruptions. The migration cost, C i , is an increasing function of R i (k), C i (R i (k)). To incorporate the migration cost, we redefine u i for the target cloud in Flock as where l ′ (y, x j ) = l(y, x j )+C i (R i (k))++C j (R j (k)) and u i (x) (i.e. utility for current cloud) is memorized. This is equivalent to penalizing the latencies values measured with an additional dynamic that accounts for the estimated average number of migrations. As R i is a function in prior migration, the C i value increases as i migrates more frequently and vanishes over time as i pauses migrations. This tweak perceives the numerical properties of both l and u, hence maintains the convergence and PoA results of Controlled-Flock.
Although the first approach minimizes the average migration cost as k → ∞, it requires exchanging the estimated migration cost between each i, j ∈ E to maintain the reciprocity condition of l. This rapid message exchange introduces a significant communication overhead. Moreover, incorporating the average migration cost in u i only has long term benefit on the system as k grows and it can causes undesirable short term service disruption for some applications. For such interruptionsensitive applications, it may be beneficial to delay the migration decisions using the η parameter instead of incorporating the migration cost into the utility function. In this second approach each VM evaluates its own η i accounting for the estimated number of migration as: η i (k) = 1 exp(R(k)) . As the VM, i, performs less migrations over time, η i (k) → 1 and i migrates for any slight improvement in its utility. Whereas if i performs frequent migrations, η i (k) → 0.36, where i only migrates if the migration decision brings a significant improvement to u i . The drawback of this approach can be seen in Fig. 2, where we sacrifice the tightness of the PoA as η < 1.

V. CONCLUSION
We propose Flock; a simple autonomous VM migration protocol. Flock considers the peer-to-peer interaction of VMs in heterogeneous edge and conventional cloud platforms. We show that Flock converges to a Nash equilibrium with (1 + ǫ) PoA. Flock minimizes the average latency of VMs as a generic goal with diverse use cases and can be easily redesigned to serve other purposes such as load-balancing and energy efficiency.

VI. ACKNOWLEDGMENT
This work was made possible by NPRP grant # NPRP 5-319-2-121 from the Qatar National Research Fund (a member of Qatar Foundation). The statements made herein are solely the responsibility of the authors.