WO2019045584A1

WO2019045584A1 - Method of migrating virtual resources in data processing centers

Info

Publication number: WO2019045584A1
Application number: PCT/RU2017/000451
Authority: WO
Inventors: Евгений Викторович ЧЕМЕРИЦКИЙ; Александр Владиславович ШАЛИМОВ; Руслан Леонидович СМЕЛЯНСКИЙ; Виталий Александрович АНТОНЕНКО
Original assignee: Некоммерческое Партнерство "Центр Прикладных Исследований Компьютерных Сетей"
Priority date: 2017-08-30
Filing date: 2017-08-30
Publication date: 2019-03-07

Abstract

The technical solution relates to the field of systems for processing and storing data, and is a method of migrating virtual resources in data processing centers, in which a plan is made for migrating virtual resources in data processing centers, taking into account a predefined migration time limit. In the claimed method for migrating virtual resources in data processing centers, a migration plan is made for a given plurality of transferable virtual resources that satisfies a given time limit for completion. As a result of making the migration plan, a shortest path is made in a communication medium for each virtual resource, along which a transfer of said virtual resource will occur.

Description

THE METHOD OF MIGRATION OF VIRTUAL RESOURCES IN CENTERS

DATA PROCESSING

TECHNICAL FIELD

The technical solution relates to the field of data processing and storage systems and is a way to migrate virtual resources in data centers, in which they plan to migrate virtual resources in data centers, taking into account the predetermined limit on the migration time. The technical solution, in particular, can be used in the cloud platform scheduler, which manages resources in the data center.

BACKGROUND

The migration of virtual resources, in particular the migration of virtual machines, can be viewed from two points of view:

1. Study of factors affecting the migration of virtual resources. 2. Study the overhead associated with the migration of virtual resources.

Article [1] identifies some factors affecting the migration of virtual machines.

The overhead costs associated with the migration of virtual machines: disk boot, energy costs, the duration of the migration, the capture of network and computing resources - were investigated in the article [2]. One of the main factors affecting the migration time is the loading of the virtual machine, its activity, for example, the intensity of writing to the RAM, the network loading is also an important factor - [3]. Various technological approaches, how to conduct migration, are discussed in article [4]. There are works that consider the migration of only one machine at a specific point in time [5]. In papers [3, 6], the migration of several machines at the same time point is considered. In [7], the issue of virtual machine migration time was investigated depending on the mutual influence of virtual machines, network topology, and the state of communication channels. In all the articles reviewed above, the technological problems of migration are mainly discussed. But none of the articles proposed an algorithm for constructing a migration plan. Under the migration plan, we will understand the sequence of movements of virtual resources. Each move 5 is associated with a certain virtual resource and is characterized by the initial and resulting location of this resource, as well as the start time of the move and the duration of the move.

Migration time is very important to be able to estimate, since the data center resources are used during the migration. The longer the migration takes, the longer the data center resources are misused, i.e. not to handle user requests.

Migration of a virtual machine that works intensively with memory can take quite a long period of time due to two factors:

15 1. Intensive work with memory implies an increase in the transferred data during the migration of a virtual machine. This in turn affects the migration time of the virtual machine.

2. Migration uses data center network resources.

If there are too many 20 migrations in the same time interval, then the migration time of each virtual resource may increase due to the lack of bandwidth.

The analogue of the developed algorithm is the heuristic algorithm presented in [8]. This algorithm builds a migration plan, but this work does not take into account the time spent on migration. Algorithm

25 builds a sequence of movements to be made.

A move is represented as a triple <v, s, d>, where v is a moving virtual resource, s is the original destination of the virtual resource, d is the new destination of the virtual resource. The task: to find the optimal sequence of displacements of the form <v, s, d>. This paper shows that the task of building such a migration plan is a ΝΡ-difficult task. The task of building a migration plan comes down to the task of planning — the Sequence Planning Problem [9]. In [8], two algorithms are given for solving the problem of constructing a migration plan. The first algorithm is a reboot algorithm, which considers all possible permutations of movements that must be made. The second algorithm has quadratic complexity based on the number of displacements and is briefly described as follows: first, an arbitrary sequence of displacements is created, then all triples <v, s, d> are scanned, the number of possible migrations that can be performed after moving the virtual resource v is calculated for each triples. After all such triples are sorted by decreasing this number. The resulting sorted sequence will be the migration plan. This article presented the results of comparing the quality of the obtained solutions of the following algorithms: a random algorithm (an arbitrary sequence of displacements), a heuristic algorithm proposed in the article, and an optimal solution. It was noted in the experiments that the optimal solution and the solution obtained by the heuristic algorithm described in the article are always close to each other, which speaks in favor of the heuristic algorithm.

However, the algorithm presented in article [8] does not estimate the time of migration and does not build a path in the communication environment of the data center in which the virtual machine will be moved. The developed algorithm builds a plan for the migration of virtual resources.

The migration plan satisfies the specified limit on execution time. Also, for each virtual resource, as a result of the algorithm execution, a path will be built in the communication environment, which will need to be migrated. ESSENCE OF TECHNICAL SOLUTION

The problem to which the claimed technical solution is directed is as follows.

Build a migration plan for a given set of roaming virtual resources that satisfies the specified constraint on execution time. For each virtual resource, as a result of building a migration plan, the shortest path in the communication environment through which the virtual resource will travel will be built. s The claimed technical solution provides a technical result aimed at reducing the time to complete the migration plan for a given set of virtual resources being moved.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows an example of a resource planner in a data center, illustrating how to integrate the process of building a migration plan into a data center planner.

Figure 2 shows the block diagram of the algorithm for constructing a plan for the migration of virtual resources of the data center. DETAILED DESCRIPTION

For the most complete understanding of the essence of the claimed technical solution, we will give a mathematical formulation of the problem of resource allocation in the data center [1] and expand it for the task by building a plan for migration of virtual resources in the data processing center. The model of the physical resources of the data center will be given by the graph ^H = (named UK, L) where P is the set of compute nodes, M is the set of data storages, K is the set of switching elements of the data center exchange network, L is the set of physical data transfer channels. On the sets P, M, K, and L, the vector functions of the scalar argument are defined, specifying, respectively, the characteristics of the computational nodes, data storages, switching elements and data transmission channels:

(mh ^ mh.,, ..., mh ^) = fmh ("g)

(kh _ls kh ₂ , ..., kh _n3 ) = fkh (A:)

(lh _{1 5} lh ₂ , ..., lh _n4 ) = flh <? )

In this paper, it is assumed that the same characteristics are set for switching elements and data transmission channels.

The resource request will be defined by the graph ^{G =} ( ^w ^ Ε), where W is the set of virtual machines used by applications, S is the set of virtual data storages (storage-elements), E - a set of virtual data transfer channels between virtual machines and storage-request elements. The vector functions of the scalar argument defining the characteristics of the requested virtual element (SLA) are defined on the sets W, S and E: (wg,, wg ₂ , ..., wg _nl ) = fwg (w)

(sg,, sg ₂ , ... ^ g ^^ fsg ^) ^

(eg,, eg ₂ , ..., eg _n4 ) = feg (e)

The characteristics of the SLA element of the request coincide with the characteristics of the corresponding physical resource. The purpose of the request is mapping B

B: G—> H U {0} = {W ^ P U {0}, S -> M U {0}, E -> {K, L} U {0}} (3)

Request G is called fully assigned if

Vg G: B (g)! = 0 (4)

The request G is called partially assigned if

5 g1 e G: B (g1)! = 0 and 3 g2 e G: B (g2) = 0 (5)

The set of all requests is denoted by G = U {Gi} (assigned, partially assigned, and pending assignments).

The set of requests assignments will be denoted by A.

We distinguish three types of relationships between the characteristics of requests and the corresponding characteristics of physical resources. We denote by x the characteristic of the request and by y the corresponding characteristic of the physical resource. Then these relationships can be written as follows:

1. Inadmissibility of overloading the capacity of a physical resource:

Σ ^x ^ y

, here Rj is the set of queries assigned to be executed on the physical resource j.

2. The type conformity of the requested resource and the physical resource x = y 3. The presence of the required characteristics of the physical resource: x <y

The mapping ^{A: G_> H =,} {? ^ - * ^p ' ^{S _} * HE - "- i, L]) _we call it correct if for all physical resources and all their characteristics relations 1-3 are fulfilled.

The residual graph of available resources is the Hres graph, obtained from the graph of physical resources H, for which the values of functions are redefined by characteristics, which must satisfy the validity relation 1: fPkes (p) = JP P) - fsgis)

flb ® = fiKQ - Σ ^ ⁾ flKes (= AW) - Σ few

eeE _/ ^ esE _k ^

Here Wp is the set of virtual machines assigned for execution on the computing node p, EI is the set of virtual channels mapped onto the physical channel I, Ek is the set of virtual channels passing through the switching element k, Sm is the set of storage elements hosted in the data storage t.

To build a migration plan in the data center, it is necessary to expand the mathematical model of the planning problem presented above. The constructed plan must satisfy the previously mentioned correctness requirements (all resources involved in the migration of the query element must satisfy the correctness relationship). This means that during the migration of virtual elements, SLA requests are not violated.

Let us expand the data center model given in [1] by introducing the following concepts: the task of moving and moving virtual elements in the data center.

The motion task is a triple T = (e, s, d), where ee G; s, de H, i.e. e is a virtual element: VM or storage element; s and d are physical resources that correspond to the old and new purpose of the virtual database. element e; s! = d. The task for moving T shows that the virtual element e needs to be moved from the physical resource s to the physical resource d.

Moving we will call the five TR = (T, ts, tp = t (T, H), {Li}, tun), where T is the task for moving, ts is the time to start moving, tp is time 5 for performing the moving task, depending from the task T and the current state of the N data center resources, tun is a virtual migration channel whose capacity depends on the intensity of migration to the data center, {Li} is the set of physical channels through which the virtual migration channel passes. The migration plan is a sequence of movements that satisfies the following correctness conditions: a) all movements fit into a given directive interval Tdir b) when moving virtual SLA elements are not violated

As the initial data of the task of constructing a plan for the migration of virtual 15 elements: a) A set of tasks for moving {Τί}

b) Activity of relocatable virtual elements. Virtual machine activity is the intensity of data change in memory, measured in Mb / s.

20 c) Migration plan time limit — Tdir

Required:

Build a migration plan for a set of tasks for movements {Ti}, which is built for a set of virtual elements previously assigned in the data center, but having changed their purpose in a new display. 25 The execution time of this migration plan should not go beyond the directive interval — [0, Tdir]

The given formulation of the task of building a migration plan allows you to take into account the time of the migration of virtual resources, in contrast to the formulation presented in Chapter 11.2. Also, this formulation assumes that for each virtual resource a migration path will be built. Below is a detailed description of the algorithm for constructing a migration plan. The input data of the algorithm are:

1. Graph of residual physical resources -Hres

2. The set of virtual elements U, for which you need to migrate.

3. Old - Aold and new - Anew display of migrating virtual elements.

4. The size of the directory interval Tdir, within which the migration should be performed. The output is a constructed migration plan that satisfies the conditions for correctness: the SLA should not be violated, all movements must fit within the directive interval. If such a migration plan failed to build, then failure returns.

To explain the operation of the algorithm, the following notation is introduced: { ^~ P} is the set of tasks for moving. | {Ti} | = k (k assignment tasks of the form T = <ei, si, di>).

T is an arbitrary task of displacement of the form <e, s, d>.

V (or Vi) is the size of the virtual element. For a storage element, V is determined by its size in some conditional units (Mb, Gb), for a virtual machine, by the amount of RAM and disk memory.

A = activity (or Ai) - the intensity of the virtual element; shows how much data in arbitrary units (МЬ, Gb) changes per unit of time (second, minute, hour). Activity is directly proportional to the intensity of writing to the storage storage element or VM. The higher the intensity of the element, the more data will need to be transferred at the time of its migration. Suppose that some of the data has already moved from the physical resource s to the resource d, but if the intensity of the work is non-zero, a situation may arise when this same part of the data changes and needs to be moved again. Therefore, the intensity of the virtual element during migration is an important characteristic and it must be taken into account in order to estimate the time that will be spent on the movement.

{TRi} is a move plan. | {TRi} | = k. TRi = <Ti, tsi, tpi, {Li}, tun>. TRi - move the virtual element - ei. tc is the end time of the migration. The value of tc lies in the half-interval [0, Tdir). tfi = tsi + tpi. The end time of the virtual element ei migration

Q— ordered queue of tasks for moving.

Hres (t), where t is time.

The residual resource graph Hres (t) is calculated for a specific point in time in the following way: a) Before starting the construction of the migration plan, we have the residual resource graph Hres (0), which is taken as input.

b) Next, for any moment of time t, to determine Hres (t), we scan all movements - {TRi} (in this set at time t <tc there can be only part of the movements) and capture in Hres (0) those physical channels Li, for which: tsi <= t && t <tfi, i.e. capture those channels that are busy at time t. You also need to capture temporary replicas of relocatable elements in Hres (t), i.e. for TRi, running at time t, capture resources under the element ei on both the physical element s and element d.

Movements can be performed in parallel, therefore network resources are not fully allocated for the migration of a virtual element, but are divided in proportion to their intensity. To find the bandwidth of the virtual migration channel tun for the virtual element ei, the following procedure is performed: in the set {Li} there is a channel with the smallest bandwidth - throughput, after the bandwidth of the tun channel is calculated by the formula: tun. throughput = throughput

The bandwidth of the migration channel can be calculated as follows tun. throughput ^ throughput

The effect of these two options on the result of the algorithm was studied in an experimental study. The use of option 1 is more preferable, since with parallel migration the time spent on migration may be less than when using option 2, in which the migration of virtual resources takes place sequentially.

Estimating the migration time of a virtual element is not an easy task, therefore, in this course migration time, it is considered to be directly proportional to the ratio of the data being moved to the data transmission channel bandwidth: tp = ^V - _:

tun. throughput — Activity ^

If the Activity is larger than the tun.throughput migration channel bandwidth allocated, the corresponding movement will be prohibited.

It is not known in advance how much time will be required for each movement, therefore, the task of building a plan for migrating virtual elements is not a classic task of building a schedule. Therefore, to solve this problem, the algorithm described below was proposed: A) Using the set U = {ei}, 1 <= i <= k, we form a set of tasks for moving {Ti}.

B) Arrange the set {Ti} to reduce the product Vi * (Ai + 1) and form a queue Q from it. This is done in order to first try to move the most "difficult" elements. If the element has a high intensity, therefore, there will be a lot of transmitted data, so that even with a small element along V, but with very high intensity, difficulties may arise when moving.

C) We retrieve the next item from the Q queue.

Yu D) We initiate the zero variable observeTime, which is responsible for the point in the schedule currently under consideration.

E) If the current time is tc, go to step (F). Otherwise we try to put the movement in the current time - observeTime: a) We form Hres (observeTime). b) We are looking for the minimum path at a given cost in the Hres (observeTime) graph from the vertex si to the vertex di. The search is performed using the Dijkstra algorithm [1]. The cost of the edge (physical channel) in the graph is the occupied bandwidth. If it was not possible to find the path, go to subparagraph (iv). c) We check if we have exceeded the time of migration: if we have exceeded, then go to step (iv), otherwise we check if we interfere with any movements. If we do not interfere with any movements, then to item (H), otherwise we proceed to sub-item (iv). d) Update observeTime — we skip the move closest to the current time. Go to subparagraph (i).

F) We attempt to move the element ei. We are looking for a path from si to di in the Hres (0) graph. If failure, then put processed Ti at the end of the queue and go to paragraph (I).

G) We check if we have exceeded the time of migration: if we have exceeded, then we put the processed Ti at the end of the queue and go to step (I).

H) Put the formed movement TRi into the set of already processed movements {TRj}. Update tc time.

I) If the Q queue is looping, then the algorithm returns a failure.

J) If Q's queue is empty, therefore, the migration plan is built - return success.

K) Return to paragraph (C).

Based on the above described algorithm, we describe the procedure for building a migration plan. Suppose there is already a migration plan S - it may be empty. Items that are located in the data center before the start of the resource allocation algorithm and for which migration is allowed are OLDm. After the processing of the next request, let the data center planner decide to change the assignment of the elements of the OLDm ^* subset of the OLD set. If there are no displacements of elements from the OLDm ^* set in S, then an attempt is made to supplement the migration plan S according to the algorithm described above - steps А-К for the OLDm ^{* set} . If the migration plan S contains the movement of elements from OLDm *, then a new migration plan is constructed for the virtual elements from S and OLDm ^* . If when adding a migration plan or when constructing a new plan, the directive period is violated, then a return to the previous correct migration plan or to an empty migration plan is made, and the procedure for building a migration plan returns FAILED.

The claimed method of migration of virtual resources in data centers is industrially applicable, since its implementation uses known and proven methods and components.

Although this technical solution is described by a specific example of its implementation, this description is not limiting, but is given only for illustration and a better understanding of the essence of the technical solution, the scope of which is determined by the attached formula.

Bibliography

1. Jiangtao Zhang, Hejiao Huang, XuanWang. Cloud computing: A survey. // Journal of Network and Computer Applications — 2016, V.64 Issue C, —P. 23-42

2. A. Sallam, K. Li .A multi-objective virtual machine migration policy in cloud

systems. // Comput Journal— 2014; 57 (2), —P. 195-204. [Electronic resource]. URL:

http://comjnl.oxfordjournals.org/content/early/2013/02/28/comjnl.bxt018 (appeal date: 13.04.2016).

3. Sotomayor In, Keahey K, Fosterl. Combining batch execution and leasing using virtual machines. // HPDC'08, Boston, Massachusetts, USA, - June 2008, - p.87-96. [Electronic resource]. URL: http://www.nimbusproject.org/files/hpdc242s-sotomayor.pdf (access date: 13.04.2016).

4. Zhao M.Figueiredo RJ. Experimental study of virtual machine migration in

support of reservation of cluster resources. / VTDC'07, 2nd international

Workshop on Virtualization technology in distributed computing.— 2007, - p. 5. [Electronic resource]. URL: http: //dl.acm. org / citation.cfm? id = 1408659 (appeal date: 13.04.2016).

5. Han P, Gong Q. Optimized live vm migration with eviction-free memory

approach.// In: Proceedings of the 9th international symposium linear drives for industry applications, vol.1.Springer; 2014. — P.185-191.

6. Ye K, Jiang X, Ma R, Yan F. Vc-migration: live cloud computing and GRAC; 2012. - P; 209-218. [Electronic resource]. URL:

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6319172

& filter% 3DAND% 28p_IS_Number% 3A6319148% 29% 26pageNumber% 3D2 (reference date: 13.04.2016).

7. Sarker TK, Tang M. Performance-driven live migration of multiple virtual

machines in datacenters.// IEEE international conference on granular computing (GrC) .IEEE; 2013. — P.253-258.

8. Walk the Line: Consistent Network Updates with Bandwidth Guarantees //

HotSDN'12, - Helsinki, Finland, 2012, p.6. [Electronic resource]. URL:

http://web.engr.iHinois.edu/~caesar/papers/hot18-ghorbani.pdf (date

references: 04/13/2016).

9. B. G. Jozsa and M. Makai. On the solution of reroute sequence planning (RSP) problem in mpls networks. // Computer Networks, 42 (2), 2003 — P.199 - 210. [Electronic resource]. URL: http://www.cs.elte.hu/~marci/papers/reroute.pdf (access date: 13.04.2016).

J. Thomas X. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Chapter 24 The shortest paths from one vertex. In: Algorithms: construction and analysis., 3rd ed. : Trans. From English - M.: LLC “I. D. Williams, 2013. - 1328 p. : il. - Paral. Titus English

11. Zotov I. A., Kostenko V. A. Algorithm of resource allocation in data processing centers with a single scheduler for various types of resources // News of the Russian Academy of Sciences. Theory and management systems.—

Claims

CLAIM

1. The method of migration of virtual resources in data centers in which, using the set U = {ei}, 1 <= i <= k, form a set of tasks for moving {Ti}; order the set {Ti} by reducing the product Vi * (Ai + 1) and form a queue Q from it; remove the next item from the queue Q; zero is initiated by the observeTime variable, which is responsible for the point in the schedule currently being considered; if the current time is tc, go to the next step, otherwise try to put the movement at the current time - observeTime: a) form Hres (observeTime); b) looking for the minimum path at a given cost in the Hres (observeTime) graph from the vertex si to the vertex di. The search is performed using the Dijkstra algorithm [1]. The cost of the edge (physical channel) in the graph is the occupied bandwidth. If it was not possible to find the way, go to subparagraph (iv); c) check if we have exceeded the migration time: if we have exceeded, then proceed to the next step, otherwise check if any movement is disturbed and if we do not interfere with any movement, put the formed movement TRi into the set of already processed movements {TRj} and update tc time, otherwise go to the next step; d) pass the movement nearest to the current time; make an attempt to move the element ei, while looking for a path from si to di in the Hres (0) column and if unsuccessful, then put the processed Ti at the end of the queue and the algorithm returns a failure; check whether the migration time is exceeded and, if exceeded, put the processed Ti at the end of the queue and the algorithm returns a failure; put the formed movement TRi into the set of already processed movements {TRj} and update the time tc; if the queue Q is looping, then the algorithm returns a failure, if the queue Q is empty returns success.