METHOD AND SYSTEM FOR REMOTE EXECUTION OF SERVICES REQUESTED BY A MOBILE DEVICE VIA A CELLULAR COMMUNICATION NETWORK

Abstract

The invention relates to a method and system for remote execution services requested by at least one mobile device via a cellular communications network according to a communication protocol which is at least fourth-generation, a service being executed by a virtual machine of a current host server. The method comprises, for a given service request, a) calculating (52) a probabilities vector containing K components, each component being associated with a given moment in time from a set of K moments in time, b) selecting (54) a migration moment in time based on the calculated probabilities vector, c) determining (56) a number of replications of the virtual machine to be carried out at the selected migration moment in time in order to minimize a replication energy cost while providing a level of service continuity and calculating (56) a predicted gain for the migration.

Claims

1. A method of remote execution of services required by at least one mobile device, in particular on board a vehicle, via a cellular communication network according to a communication protocol of at least fourth generation, a service being executed by a virtual machine of a computing server, referred to as the current host server, the mobile device sending a service request having a position belonging to a geographical area of current cellular communication coverage, said current host server being associated with the geographical area of current coverage, the method being implemented by a processor of said current host server (MEH.sub.c), for a given service request, received during a current time interval and comprising: a) for the current time interval, calculating a probability vector with K components, each component being associated with a given moment of time of a predetermined set of K moments of time, each component of the probability vector corresponding to a probability of migration at the associated moment of time, the migration consisting of at least one replication of the virtual machine executing said service on a chosen host server belonging to a geographical area of coverage contiguous to said current geographical area of coverage, the calculation of the components of the probability vector implementing a set of K weights, each weight being associated with a migration moment of time and representative of a gain predicted for a migration at said associated migration moment of time, b) selecting from said set of K moments of time of a moment of time, referred to as the selected migration moment of time, according to the calculated probability vector, the selected migration moment of time having a maximum corresponding probability of migration in the calculated probability vector, and c) determining, for the migration at the selected migration moment of time, of a number of replications of the virtual machine to be performed at the selected migration moment of time so as to minimize a cost in terms of replication energy while ensuring a level of continuity of service, and calculation of a predicted gain for said migration at the selected migration moment of time.

2. The method according to claim 1, further comprising storing, in a storage, the selected migration moment of time and the number of replications of the virtual machine to be performed for said given service request.

3. The method according to claim 1, implemented by said current host server for a plurality of service requests over a succession of time intervals, the method further comprising: d) updating of the weight associated with the selected migration moment of time, for a following time interval, the update depending on said predicted gain, and repeating of steps a) to d) for the following time interval.

4. The method according to claim 3, wherein the update of the weight implements an exponential function of said predicted gain, and the probability associated with the selected migration moment of time for the current time interval.

5. The method according to claim 4, wherein the weight associated with the selected moment of time for the following time interval is obtained by the formula: ${?}_{k*}\left(t+1\right)={?}_{k*}\left(t\right)e^{\frac{?x_{k^{*}}\left(t\right)}{K{p}_{k^{*}}\left(t\right)}}$ where k* is the index of the selected migration moment of time, ?.sub.k*(t) is the weight associated with the selected moment of time for the current time interval (t), ?.sub.k* (t+1) is the weight associated with the selected moment of time for the next time interval, ? is a weighting parameter, p.sub.k*(t) and is the probability associated with the selected migration moment of time.

6. The method according to claim 5, wherein, for the current time interval, the probability associated with the moment of time T.sub.k of index k is calculated by the formula: $p_k\left(t\right)=\left(1-?\right)\frac{{?}_k\left(t\right)}{{.Math.}_{j=1}^K{?}_j\left(t\right)}+\frac{?}{K}\mathrm{for}\mathrm{any}k?\left\{1,2,.Math.,K\right\}$

7. The method according to claim 5, wherein the weighting parameter is calculated dynamically based on a calculation of cumulative global gain for each moment of time, the cumulative global gain being incremented, for each moment of time, for each service request processed, by the predicted gain for migration when said moment of time is selected as the migration moment of time.

8. The method according to claim 7, wherein the weighting parameter value is changed when the maximum cumulative overall gain among said calculated overall gains exceeds a threshold dependent on the number of moments of time.

9. The method according to claim 1, wherein determining, for a migration at the selected migration moment of time, for each service request, a number of replications of the virtual machine to be performed at the selected migration moment of time, each replication being performed on a selected host server, implements a minimization of an target function depending on an energy consumed for said number of replications, under the constraint of a risk metric associated with the accessibility of the host server(s) chosen for the replication and of an availability metric, for each replication, of the virtual machine triggered after the replication triggered at the selected migration moment of time.

10. The method of claim 9, wherein the risk metric uses a probability representative of a prediction of mobility associated with each selected host server, representative of the probability that the mobile device sending said service request enters a geographical coverage area associated with said chosen host server.

11. The method according to claim 10, wherein for a selected migration moment of time, and for a given request r(t), said risk metric is defined by: $\mathrm{Risk}\left(r\left(t\right)k^{*},{M_r^{k^{*}}\left(t\right)}^{*}\right)=1-\underset{i=1}{\overset{{M_r^{k^{*}}\left(t\right)}^{*}}{.Math.}}{p}_{r,k^{*},i}^s\left(t\right)$ where k* is the index of the selected migration moment of time, M.sub.r.sup.k*(t)* is the number of replications of the optimal virtual machine calculated, and p.sub.r,k*,i.sup.s(t) is the probability representative of a prediction of mobility associated with a host server of index i.

12. The method according to claim 9, wherein the availability metric uses, for each replication of virtual machine, a comparison of a migration moment of time of the virtual machine and of a time remaining before a change of host server for the mobile device sending said service request.

13. The method according to claim 9, wherein said consumed energy is calculated based on the number of replications and a size of the virtual machine to be migrated.

14. The method according to claim 9, wherein said determination, for the migration at the selected migration moment of time, for each service request, of a number of replications of the virtual machine to be performed at the selected migration moment of time implements, for a plurality of service requests received over a current time interval, a mean risk calculation and a mean availability calculation availability over said plurality of requests.

15. The method according to claim 14, wherein said calculated mean risk for the current time interval is used to construct a first virtual queue, for a subsequent time interval, according to an associated first control parameter, and said mean availability is used to construct a second virtual queue, for a subsequent time interval, depending on an associated second control parameter, the objective function to be minimized being dependent on said first and second virtual queues.

16. The method according to claim 9, wherein, for a given service request, and for a selected migration moment of time, the predicted gain is equal to the value of said objective function for the determined number of replications of the virtual machine.

17. The method according to claim 1, wherein a maximum number of candidate host servers is associated with each moment of time, the maximum number of candidate host servers associated with each moment of time decreasing in the ascending order of moments of time.

18. A computer program including software instructions which, when executed by a programmable electronic system, implement a method of remote execution of services required by at least one mobile device according to claim 1.

19. A method of remote execution of services required by at least one mobile device, in particular on board a vehicle, the system including a cellular communication network according to a communication protocol at least of fourth generation, and a plurality of computing servers, a service being executed by a virtual machine of a computing server, known as the current host server, the vehicle sending a service request having a position belonging to a current geographical area of cellular communication coverage, said current host server being associated with the current geographical area of coverage, said current host server including a processor configured to implement, for a given service request received during a current time interval belonging to a succession of time intervals: a module for calculating, for the current time interval, calculation of a probability vector with K components, each component being associated with a given moment of time of a set of K predetermined instants, each component of the probability vector corresponding to a probability of migration at the associated moment of time, the migration consisting of at least one replication of the virtual machine executing said service on a chosen host server belonging to a geographical area of coverage contiguous to said geographical area of current coverage, the calculation of the components of the probability vector implementing a set of K weights, each weight being associated with a migration moment of time and representative of a gain predicted for a migration at said associated migration moment of time, a module for selecting, from said set of K moments of time, a moment of time, referred to as the selected migration moment of time, according to the calculated probability vector, the selected migration moment of time having a maximum corresponding probability of migration in the calculated probability vector, a module for determining, for the migration at the selected migration moment of time, a number of replications of the virtual machine to be performed at the selected migration moment of time so as to minimize a cost in terms of replication energy while ensuring a level of continuity of service, and calculation of a predicted gain for said migration at the selected migration moment of time.

20. The system according to claim 19, further including a module for updating the weight associated with the selected migration moment of time for a subsequent time interval, the update depending on said predicted gain.

Description

[0046] Other features and advantages of the invention will be clear from the description thereof which is given below as a non-limiting example, with reference to the enclosed figures, among which:

[0047] FIG. 1 schematically illustrates a cellular communication network wherein the invention is applied;

[0048] FIG. 2 is a block diagram of a system for remote execution of services;

[0049] FIG. 3 is a flow chart of the main steps of method of remote execution of services according to a first embodiment;

[0050] FIG. 4 schematically illustrates a time axis of application of a method of remote execution of services according to one embodiment;

[0051] FIG. 5 is a flow chart of the main steps implemented for determining a number of replications of the virtual machine to be performed at a selected moment of time and calculating an associated gain according to one embodiment;

[0052] FIG. 6 is a flow chart of the main steps of path generation method according to a second embodiment.

[0053] The invention applies to a mobile device, e.g. a device on board a moving vehicle or a vehicle equipped with the ability to connect to a communication network, and it is the latter case of application which is described in detail hereinafter.

[0054] FIG. 1 schematically illustrates a set of geographical coverage areas of a cellular communication network 2.

[0055] The geographical areas 4.sub.1, 4.sub.2, . . . , 4.sub.j are represented schematically.

[0056] The communication network 2 is a communication network according to a radio communication protocol of at least fourth generation, 4G, or fifth generation, 5G.

[0057] Each geographical area corresponds to a cell of the communication network and comprises communication equipment (not shown) (access points, base stations, etc.).

[0058] In addition, each cell comprises or is associated with a calculation server 6), or host server called MEH, (standing for Mobile Edge Host), which is a physical server with a calculation capacity. In an MEC, a plurality of MEH servers are connected, via an either wired or wireless link, for managing remote services (e.g. execute the virtual machines). A MEH can be placed either in a base station (colocated) or associated with a plurality of base stations.

[0059] The set of computing servers 6.sub.j, suitable for communicating with each other, forms a cloud of computing devices 15.

[0060] FIG. 1 diagrammatically shows a vehicle 8, e.g. a motor vehicle, which has the ability to move and which is equipped with a communication interface (not shown in FIG. 1) according to the 4G or 5G communication protocol.

[0061] The invention applies more generally to any mobile device, equipped with a 4G or 5G, and beyond, communication interface, which can move between geographical areas, e.g. a terminal, a mobile telephone, a tablet, vehicles, etc.

[0062] More generally, the invention applies in any system that uses wireless communication between a node and one or more host servers that run services for said node and is of particular interest to any mobile node for which there is a position uncertainty at the time of handover.

[0063] Of course, the invention applies to any type of land vehicle, and also to other types of vehicles such as e.g. drones.

[0064] At a current moment of time, the vehicle 8 is located at a given spatial position, belonging to a current geographical coverage zone, which is the zone 4.sub.1 in the example shown in FIG. 1. The vehicle 8 is then apt to exchange data and to request the execution of one or a plurality of services from the host server 6.sub.1 associated with the zone 4.sub.1, which is the host server MEH.sub.1, also called the current host server MEH.sub.c.

[0065] The execution of a service is performed by a virtual machine or VM 10.

[0066] A virtual machine refers herein to a computing software unit that virtualizes (or emulates) a computing system, in various known types of implementations, in the form of a container or other, e.g. Docker (open source software for launching applications in software containers), Solaris Containers, OpenVZ, Linux-VServer, LXC, AIX Workload Partitions, Parallels Virtuozzo Containers, iCore Virtual Accounts.

[0067] The term service refers herein to any software application implementing exchanges of data, e.g., in the case of connected vehicles, services include driving assistance services, road traffic management and the provision of infotainment.

[0068] A plurality of predefined classes of service can be distinguished.

[0069] The service or software application implemented is a stateful app. Replication of a virtual machine for executing a service consists of the complete copying of a runtime instance of the service, and an execution context (variables, parameters), or status of the runtime instance.

[0070] When the vehicle 8 is moving, same may leave the geographical zone 4.sub.1, for one of the adjacent zones. By hypothesis, the future geographical area of coverage of the vehicle in question is not known.

[0071] For continuity in the execution of the services, provision is made to replicate the virtual machine VM 10 to one or a plurality of the host servers 6, associated with the geographical coverage zones 4, adjacent (or contiguous) to the current zone.

[0072] The current host server MEHc initiates a migration consisting in replicating the VM 10 on one or a plurality of host servers 6, which is represented schematically by arrows in FIG. 1.

[0073] To this end, the host server implements a method which will be described in greater detail hereinafter, which makes it possible to determine, for each service request coming from a vehicle, when (i.e. at what moment of time), how many replications to make and to which host server(s), based on a gain dependent on replication energy, and based on a chosen level of continuity of service, taking into account a risk metric associated with the accessibility of the chosen host server(s) (risk associated with a probability that the moving vehicle will enter a coverage area associated with each chosen host server) and a VM replication availability metric.

[0074] For example, a level of continuity of service is defined by a value of the risk metric and a value of the availability metric, which ensures that these metrics are met within such framework.

[0075] FIG. 1 diagrammatically shows two migrations by arrows starting from the host server MEH.sub.c: a first set of arrows 12 (in dotted lines) representative of a first migration, at a moment of time T.sub.1, corresponding to five replications in the present example; a second set of arrows 14 (in solid lines) representative of a second migration, at a moment of time T.sub.2, subsequent to T.sub.1, corresponding to three replications in the present example. The moments of time T.sub.1, T.sub.2 are both future moments with respect to the current moment when the vehicle is in the position shown. It should be understood that between the moment of time T.sub.1 and the moment of time T.sub.2, the vehicle will have moved, and the number of available host servers will be smaller.

[0076] Advantageously, the proposed method makes it possible to ensure a level of continuity of service when the vehicle 8 changes geographical area of network coverage, in particular in the case of rapid mobility of the vehicle 8, for services sensitive to transmission delays (delay sensitive applications).

[0077] FIG. 2 is a flow diagram of the functional blocks of a system of remote execution of services according to the invention.

[0078] The system 20 comprises a vehicle 8 and a plurality of host servers MEH.sub.c, MED.sub.d, suitable for communicating with each other, and forming an MEC.

[0079] It is understood that the system represented in FIG. 2 is simplified, the number of host servers being any number. Moreover, in practice, a current host server is suitable for receiving service requests from a plurality of vehicles.

[0080] The functional blocks of a host server 6 (MEH.sub.c) are represented in detail, the host server being a current host server MEH.sub.c configured to implement the method of remote execution of services.

[0081] The vehicle 8 comprises an on-board electronic control unit (ECU) 22 and a communication interface 24 according to the chosen cellular communication protocol, e.g. the 5G protocol.

[0082] The ECU 22 is an electronic computing device, e.g. an on-board computer, including in particular a computing processor and an electronic memory.

[0083] The ECU 22 is suitable for communicating with the communication interface 24 via a two-way communication bus, for the exchange of data, commands, requests, responses. In particular, the ECU 22 is suitable for sending service requests to a host server MEH.sub.c, e.g. a request r(t) sent during a time interval t.

[0084] Each host server MEH 6 further includes a communication interface 26, according to the cellular communication protocol chosen, e.g. the 5G protocol.

[0085] The host server 6 is a programmable electronic device, which further comprises a calculation unit 28 comprising one or a plurality of calculation processors and an electronic memory unit 30. The communication interface 26, the calculation unit 28 and the electronic memory unit 30 are suitable for communicating via a communication bus.

[0086] The calculation unit 28 implements a VM 10 for the execution of the request r(t), sent by a vehicle for the execution of a service.

[0087] Furthermore, the calculation unit 28 is configured to implement, for each request and for successive time intervals: [0088] a module 32 for calculating a probability vector with K components, each component being associated with a given moment of time of a set of K predetermined moments of time, each component of the probability vector corresponding to a probability of migration at the associated moment of time, the migration consisting of at least one replication of the virtual machine executing the service on a host computing server belonging to a geographical area of coverage contiguous to said current geographical area of coverage, the probability being calculated as function a weight depending on the associated moment of time; [0089] a module 34 for selecting a moment of time, called the selected migration moment of time, based on the calculated probability vector, [0090] a module 36 for determining, for the migration at the selected migration moment of time, a number of replications of the virtual machine to be performed at the selected moment of time so as to minimize a cost in terms of replication energy while ensuring a level of continuity of service, and calculation of gain associated to said migration at the selected migration moment of time, and [0091] a module 38 for updating the weight associated with the selected moment of time according to the calculated gain.

[0092] In one embodiment, the modules 32, 34, 36, 38 are each implemented in the form of a software program or a software brick executable by the calculation unit 28 and stored in the memory 30. The modules then form a computer program including software instructions which, when executed by a programmable electronic system, implement a method of remote execution of services required by a mobile device. This computer program can be recorded on any computer-readable non-volatile recording medium, e.g. any type of non-volatile memory (EPROM, EEPROM, FLASH, NVRAM), a magnetic card or an optical card.

[0093] In a variant (not shown), the modules 32, 34, 36, 38 are each embodied in the form of a programmable logic component, such as an FPGA (Field Programmable Gate Array), GPU (graphic processor) or a GPGPU (General-purpose processing on graphics processing), or further in the form of a dedicated integrated circuit, such as an ASIC (Application Specific Integrated Circuit).

[0094] FIG. 3 is a flow chart of the main steps of a method for executing remote services according to a first embodiment, implemented by a calculation unit of a current host server.

[0095] The method is described below in the case of reception of a service execution request from a vehicle but applies in a similar manner to each request received by the current host server, coming from the same vehicle or from a plurality of vehicles.

[0096] The method starts in a first time interval t=1 (t represents herein a time interval number in a succession of time intervals), and is executed over a plurality of successive time intervals, as illustrated schematically in FIG. 4, e.g. Q time intervals, Q being a given integer.

[0097] The duration of each time interval is chosen, e.g. it is fixed or is variable according to a number of requests to accumulate before starting the execution. The number of requests is greater than or equal to 1, and e.g. comprised between 2 and 100. Such requests are received by the current host server from one or a plurality of vehicles.

[0098] In one embodiment, the processed requests are requests for services likely to be migrated, e.g. from vehicles located at a distance less than a threshold distance from an edge of the coverage area.

[0099] The method comprises a step of reception of a service request r(t) and of initialization of the parameters for the current time interval t, which is the interval t=1.

[0100] The purpose of the method is to determine a migration trigger moment of time, simply referred to thereafter as the migration moment of time, for executing the or each service request received, from among a set of K predetermined moments of time: {T.sub.1, . . . , T.sub.i, . . . T.sub.K}.

[0101] In the following, the method shown in FIG. 3 is described for processing a service request coming from a vehicle.

[0102] An example of moments of time T.sub.1, . . . , T.sub.i, . . . T.sub.K is illustrated on the time axis represented in FIG. 4: the moments of time are ordered in the ascending order of the indices, the instant T.sub.i+1 being subsequent to the instant T.sub.i.

[0103] In one embodiment, the set of K moments of time is determined as a function of a number of neighboring host servers (i.e. associated with geographical coverage areas contiguous to the current geographical area in which the requesting vehicle is located) candidates for the migration at each moment of time T.sub.k.

[0104] Thereby, N.sub.MEH.sup.k represents the number of candidate neighbor MEH servers when the migration is initiated at the moment of time T.sub.k. The moments of time are chosen so that the numbers of associated candidate host servers are different, e.g. decreasing, in the order of increasing indices N.sub.MEH.sup.1>N.sub.MEH.sup.2> . . . >N.sub.MEH.sup.K, up to N.sub.MEH.sup.K=1.

[0105] The number K is any integer, depending on the topology of the communication network, e.g. an integer greater than or equal to 2.

[0106] At each moment of time T.sub.k is associated an option ?.sub.k(t) representative of the selection or non selection, at the time interval t, of the migration of the VM at the moment of time T.sub.k. In other words:

[0107] ?.sub.k(t)=1 if the moment of time T.sub.k is selected as the migration initiation moment during the execution of the method at the time interval t; and ?.sub.k (t)=0 otherwise.

[0108] The method implements a probabilistic optimization algorithm such as exploit or explore, over a succession of time intervals.

[0109] Initial values of weight associated with the moments of time, ?.sub.k(t), as well as an initial value of the weighting parameter ?, comprised between 0 and 1 and representative of a weighting between the options exploit or explore, are obtained in the initialization step 50. Such initial values are e.g. supplied by an operator, or read from a memory, or else are set by default.

[0110] For example, in one embodiment, the weighting parameter ? takes a value provided by the formula:

[00004]$\begin{array}{cc}?=\min \left\{1,\sqrt{\frac{\mathrm{Kln}\left(K\right)}{\left(e-1\right)g_b}}\right\}& \left[\mathrm{MATH}1\right]\end{array}$

[0111] Where g.sub.b is a given value, representative of an upper bound of the total gain, defined by the following formula as a function of a gain x.sub.x(t) defined below:

[00005]$g_b=\underset{1?k?K}{\max }\underset{t=1}{\stackrel{T}{.Math.}}{x}_k\left(t\right)$

[0112] Each weight ?.sub.k (t), associated with the moment of time T.sub.k, is calculated as a function of a gain predicted for a migration at said associated moment of time T.sub.k.

[0113] The method comprises a step 52 of calculating a first probability vector P(t) with K components, each component p.sub.k (t) being a probability value of migration of the VM at the moment of time T.sub.k calculated for the time interval t:

[00006]$\begin{array}{cc}{p}_k\left(t\right)=\left(1-?\right)\frac{{?}_k\left(t\right)}{{.Math.}_{j=1}^K{?}_j\left(t\right)}+\frac{?}{K}\mathrm{for}\mathrm{any}k?\left\{1,2,.Math.,K\right\}& \left[\mathrm{MATH}2\right]\end{array}$

[0114] Thereby, for each moment of time T.sub.k, the calculated probability of migration is a sum between a first term depending on the weight values associated with each moment of time, representative of an empirically predicted gain, and a second term of uniform distribution.

[0115] The method then comprises a step 54 of selecting a moment of time T.sub.k*, referred to as the selected migration moment of time, as a function of the first calculated probability vector. The selected moment of time is the moment that maximizes the probability p.sub.k(t):

[00007]$\begin{array}{cc}{k}^{*}={\mathrm{Argmax}}_{j=1.Math.K}\left(p_j\left(t\right)\right)& \left[\mathrm{MATH}3\right]\end{array}$

[0116] The option ?.sub.k*(t) is enabled, i.e. set to 1, the other values of ?.sub.j (t) being 0.

[0117] In the particular case where a plurality of migration moments have the same probability equal to the maximum value among the probabilities p.sub.k(t), it is possible to use any metric to finalize the selection of a moment of time, e.g. a drawing of lots between scenarios with the same probability of migration, or the selection of the first result obtained with the maximum probability.

[0118] The method then comprises a determination step 56, for the migration at the selected migration moment of time T.sub.k*, a number of replications of the virtual machine to be performed from the selected moment of time so as to minimize a cost in terms of replication energy while ensuring a level of continuity of service, and to calculate a predicted gain for said migration at the selected migration moment of time. In addition to the number of replications, the host servers to use for the replications are also determined.

[0119] An implementation of the determination step 56 will be discussed in detail hereinafter with reference to FIG. 5. Advantageously, an algorithm based on a Lyapunov optimization is implemented.

[0120] The predicted gain at the time interval t for the migration at the moment of time T.sub.k* of all the requests received at t is denoted by x.sub.k*(t)

[0121] The method further comprises a step 58 for updating the weight associated with the moment of time .sub.k* for the following time interval t+1.

[00008]$\begin{array}{cc}{?}_{k*}\left(t+1\right)={?}_{k*}\left(t\right)e^{\frac{?x_k*\left(t\right)}{{\mathrm{Kp}}_{k*}\left(t\right)}}& \left[\mathrm{MATH}4\right]\end{array}$

[0122] For index values k different from k*, the weight values are unchanged:

[00009]$\begin{array}{cc}{?}_k\left(t+1\right)={?}_k\left(t\right),?k?k^{*}& \left[\mathrm{MATH}5\right]\end{array}$

[0123] In one embodiment, the updating of the weights is performed for all the requests received during the current time interval, and which belong to the same service class, the service classes being predefined.

[0124] Step 58 is followed by a step 62 for storing, for the or each request considered, the decision of migration ?.sub.k*(t), specifying the instant T.sub.k* selected for the migration, as well as the number M.sub.r.sup.k*(t) of replications to be performed, as determined in step 56. The host servers of the replications are M.sub.r.sup.k*(t) host servers selected during step 56, based on a probability representative of an associated prediction of mobility, representative of the probability that the vehicle will move into a coverage area with which a selected host server is associated.

[0125] An effective triggering of the migration by replication(s) of the VM at the moment of time T.sub.k* will be carried out later according to the stored information (number of replications, replication host servers).

[0126] Steps 50 to 58 are iterated for the next time interval t+1 for one or a plurality of new requests, coming from the same vehicles or from other vehicles.

[0127] The algorithm described above with reference to FIG. 3 is a decision algorithm based on the algorithm known as EXP3 (Exponential weight algorithm for Exploration and Exploitation), which advantageously implements a determination of gain associated with the triggering of the migration at the moment of time T.sub.k*. The calculation of the gain will be discussed in detail hereinafter. The calculation is based on a minimization of the replication energy for a number M.sub.r.sup.k*(t) of replications to be performed during the migration at the moment of time T.sub.k*, and compliance with a risk constraint (risk of loss of continuity of service) and a VM availability constraint (full replication at the moment when the vehicle changes the geographical coverage area thereof).

[0128] FIG. 5 is a flow chart of the main steps implemented for determining a number of replications of the virtual machine to be performed at a selected moment of time, for one or each request, and the calculation of an associated gain according to one embodiment.

[0129] In such embodiment, a Lyapunov optimization is implemented.

[0130] The method for determining a number of replications is implemented for a time interval t, and for a plurality of execution requests r, coming from one or a plurality of vehicles, received during the time interval t.

[0131] The method applies similarly to the processing of each request.

[0132] The method comprises a step 70 of calculation of the energy consumed for the migration, for all the requests considered during the time interval t.

[0133] The energy consumed during the migration of the VM which processes a request, for a number M.sub.r.sup.k (t) of replications, is calculated, in one embodiment, by the following formula:

[00010]$\begin{array}{cc}{E}_r\left(t\right)=M_r^k\left(t\right){?}_r& \left[\mathrm{MATH}6\right]\end{array}$

[0134] Where M.sub.r.sup.k (t) is the number of replications performed when the migration is triggered at the moment T.sub.k, and ?.sub.r or the energy consumed for a replication of the VM which processes the request r.

[0135] For example, in one embodiment, the energy consumed by replication of a VM is calculated according to the formula:

[00011]$\begin{array}{cc}{?}_r=3600?\left(0.512W+20.165\right)\left[\mathrm{Joules}\right]& \left[\mathrm{MATH}7\right]\end{array}$

[0136] Where W: The size of the VM to be migrated in megabytes.

[0137] Thereby, in such embodiment, the energy consumed by replication of the VM depends on the size of the VM to be migrated.

[0138] Of course, variants of calculation of the energy consumed by replication of a VM are conceivable. For example, in one variant, the calculated consumed energy depends on the migration moment of time as well.

[0139] For a set of requests A(t), the total energy consumed for the migration is, for all the moments of time T.sub.k considered:

[00012]$\begin{array}{cc}\underset{r?A\left(t\right)}{.Math.}\underset{k=1}{\stackrel{K}{.Math.}}{M}_r^k\left(t\right){?}_r{?}_k\left(t\right)& \left[\mathrm{MATH}8\right]\end{array}$

[0140] The set of request A(t) comprises N(t) requests.

[0141] Then, a mean risk is calculated during a step of calculating a mean risk 72, according to a risk metric.

[0142] The risk metric is associated with the probability, called spatial probability, for each host server, that the vehicle sending a request enters the coverage area with which the host server is associated, after leaving the current coverage area. In other words, the risk metric is associated with the accessibility of the host servers for the requesting vehicle while the vehicle is moving.

[0143] A prediction of mobility vector, which is a second spatial probability vector, is associated with each request r?A (t), denoted by P.sub.r,k.sup.s (t)=(P.sub.r,k,1.sup.s (t), p.sub.r,k,2.sup.S (t), . . . , p.sub.r,k,N.sub.MEH.sup.S (t)). The vector includes N.sub.MEH components, each component p.sub.r,k,i.sup.S(t) representing the probability that the vehicle sending the request r(t) connects to the host server MEH.sub.i following a migration at the moment of time T.sub.k. The components of the vector are organized in descending order of probability: p.sub.r,k,1.sup.S (t)?p.sub.r,k,2.sup.S(t)? . . . ?p.sub.r,k,N.sub.MEH.sup.S (t)

[0144] For a chosen migration moment of time T.sub.k*, the risk metric is written:

[00013]$\begin{array}{cc}\mathrm{Risk}\left(r\left(t\right),k^{*},M_r^{k^{*}}\left(t\right)\right)=1-\underset{i=1}{\stackrel{M_r^{k^{*}}\left(t\right)}{.Math.}}{p}_{r,k^{*},i}^s\left(t\right)& \left[\mathrm{MATH}9\right]\end{array}$

[0145] The mean risk is then calculated according to the formula:

[00014]$\begin{array}{cc}\stackrel{\_}{?\left(t\right)}=\frac{1}{N\left(t\right)}\underset{r?A\left(t\right)}{.Math.}\underset{k=1}{\stackrel{K}{.Math.}}\left(1-\underset{i=1}{\stackrel{M_r^k\left(t\right)}{.Math.}}{p}_{r,k,i}^s\left(t\right)\right){?}_k\left(t\right)& \left[\mathrm{MATH}10\right]\end{array}$

[0146] The mean risk is calculated for all requests processed in the time interval t.

[0147] Step 72 of calculating a mean risk is followed by a step 74 of calculating a mean availability according to an availability metric, representative of the availability of the VM following a replication, in other words, the ability to perform a complete migration of the VM before a change of host server.

[0148] For a given request, and for a migration moment of time, the duration of replication of the VM T.sub.r.sup.Mig to a host server MEH.sub.i is calculated.

[0149] In one embodiment, the duration of replication depends on a class of service, e.g. among the following classes of services: game server, high RAM app, video streaming, face detection. Of course, the list is not exhaustive. For example, for such types of services, the estimated replication time varies between 2 seconds and 15.5 seconds in the case where the VM is a container.

[0150] The time remaining before the host server change T.sub.r,k.sup.Rem is estimated, based on context data (estimation of the speed of the vehicle, network topology).

[0151] For a chosen migration moment of time T.sub.k*, the availability metric is e.g. the indicator function denoted by Ind ({T.sub.r,k*.sup.Rem? T.sub.r.sup.Mig}), which is equal to 1 if the inequality is verified, and equal to 0 otherwise.

[0152] The mean availability for all requests processed during the time interval t is then written:

[00015]$\begin{array}{cc}\stackrel{\_}{?\left(t\right)}=\frac{1}{N\left(t\right)}\underset{r?A\left(t\right)}{.Math.}\underset{k=1}{\stackrel{K}{.Math.}}\mathrm{Ind}\left(\left\{T_{r,k}^{\mathrm{Rem}}?T_r^{\mathrm{Mig}}\right\}\right){?}_k\left(t\right)& \left[\mathrm{MATH}11\right]\end{array}$

[0153] Of course, the steps 72 of calculating the mean risk and 74 of calculating the mean availability can be performed in a different order or in parallel.

[0154] A step 76 of constructing Lyapunov virtual queues implements the mean risk and mean availability values calculated beforehand, according to the following formulas:

[00016]$\begin{array}{cc}Z\left(t+1\right)=\max \left\{0,Z\left(t\right)+\stackrel{\_}{?\left(t\right)}-?\right\}& \left[\mathrm{MATH}12\right]\end{array}$$\mathrm{And}$$\begin{array}{cc}Y\left(t+1\right)=\max \left\{0,Y\left(t\right)+?-\stackrel{\_}{?\left(t\right)}\right\}& \left[\mathrm{MATH}13\right]\end{array}$

[0155] The respective parameters ? and ? are control parameters related to the desired level of continuity of service, or in other words, to the desired quality of service.

[0156] Indeed, the first virtual queue (Z(t)) associated with the risk is incremented when the calculated mean risk exceeds the associated control parameter ?.

[0157] Similarly, the second virtual queue (Y(t)) associated with the availability is incremented if the calculated mean availability is less than the associated control parameter ?.

[0158] A drift plus penalty optimization is applied (step 78) according to the Lyapunov optimization method, known in the field of stochastic systems.

[0159] For the migration moment of time T.sub.k*, ?.sub.k*(t) is known.

[0160] During such step, the optimal number M.sub.r.sup.k*(t) for each request is determined from the objective function x.sub.k(t) (given that T.sub.k* has been chosen as the optimal instant for triggering the migration).

[0161] The objective function for the moment T.sub.k* is given by the following formula:

[00017]$\begin{array}{cc}{x}_{k^{*}}\left(t\right)=\underset{r?A\left(t\right)}{.Math.}V{M}_r^{k^{*}}\left(t\right){?}_r+\frac{Z\left(t\right)}{N\left(t\right)}\left(1-\underset{i=1}{\overset{M_r^{k^{*}}\left(t\right)}{.Math.}}{p}_{r,k,i}^s\left(t\right)\right)-\frac{y\left(t\right)}{N\left(t\right)}ind\left\{T_{r,k}^{Rem}\left(t\right)?T_r^{\mathrm{Mig}}\right\}& \left[\mathrm{MATH}14\right]\end{array}$

[0162] x.sub.k*(t) naturally decomposes along r.

[0163] In order to determine the optimal value of M.sub.r.sup.k*(t) for each query r, each term

[00018]$V{M}_r^{k^{*}}\left(t\right){?}_r+\frac{Z\left(t\right)}{N\left(t\right)}\left(1-{.Math.}_{i=1}^{M_r^{k^{*}}\left(t\right)}{p}_{r,k,i}^s\left(t\right)\right)-\frac{Y\left(t\right)}{N\left(t\right)}ind\left\{T_{r,k}^{Rem}\left(i\right)?T_r^{\mathrm{Mig}}\right\}$

is minimized individually.

[0164] Thereby:

[00019]$$\begin{gathered} {M_r^{k^{*}}\left(t\right)}^{*}=\underset{M_r^{k^{*}}\left(t\right)?N_{MEH}^{k^{*}}}{\arg \min }\left[{\mathrm{VM}}_r^{k^{*}}\left(t\right){?}_r+\frac{Z\left(t\right)}{N\left(t\right)}\left(1-{.Math.}_{i=1}^{M_r^{k^{*}}\left(t\right)}{p}_{r,k^{*},i}^s\left(t\right)\right)-\frac{Y\left(t\right)}{N\left(t\right)}\mathrm{Ind}\left(\left\{T_{r,k^{*}}^{Rem}? \\ {T}_r^{\mathrm{Mig}}\right\}\right)\right] \end{gathered}$$

[0165] Where the V value is a factor for taking into account the energy consumed.

[0166] Then, in the general case, Lyapunov optimization consists in determining a number M.sub.r.sup.k*(t) of replication to be performed, the number M.sub.r.sup.k*(t) being less than or equal to the number N.sub.MEH.sup.K* of candidate host servers associated with the moment T.sub.k*.

[0167] In one embodiment, an exhaustive search is applied, all values of M.sub.r.sup.k*(t) comprised between 1 and N.sub.MEH.sup.k are tested, and the value M.sub.r.sup.k*(t)* that minimizes

[00020]$V{M}_r^{k^{*}}\left(t\right){?}_r+\frac{Z\left(t\right)}{N\left(t\right)}\left(1-{.Math.}_{i=1}^{M_r^{k^{*}}\left(t\right)}{p}_{r,k^{*},i}^s\left(t\right)\right)-\frac{Y\left(t\right)}{N\left(t\right)}\mathrm{Ind}\left(\left\{T_{r,k^{*}}^{Rem}?T_r^{\mathrm{Mig}}\right\}\right)$

is retained, x.sub.k*(t) is obtained by summing the terms

[00021]$V{M_r^{k^{*}}\left(t\right)}^{*}{?}_r+\frac{Z\left(t\right)}{N\left(t\right)}\left(1-\underset{i=1}{\overset{{M_r^{k^{*}}\left(t\right)}^{*}}{.Math.}}{p}_{r,k^{*}i}^s\left(t\right)\right)-\frac{Y\left(t\right)}{N\left(t\right)}\mathrm{Ind}\left(\left\{T_{r,k^{*}}^{Rem}?T_r^{\mathrm{Mig}}\right\}\right)$

[0168] After having determined the M.sub.r.sup.k*(t)* which minimizes the objective function, the predicted gain is calculated in the gain calculation step 80, the gain being equal to the value of the objective function x.sub.k*(t). for T.sub.k* and for the determined number of replications.

[0169] The predicted gain minimizes the replication energy for performing the number of replications M.sub.r.sup.k*(t) under the constraint of meeting the level of quality of service with regard to the risk of migration to a host server that will not be sought and the availability of the VM after replication.

[0170] In practice, M.sub.r.sup.k*(t)* replications will be triggered at the chosen migration moment T.sub.K*, towards the M.sub.r.sup.k*(t)* host servers having the highest representative probabilities of prediction of associated mobilities in the prediction of mobility vector P.sub.r,k*.sup.s(t).

[0171] FIG. 6 is a flow chart of the main steps of a method of remote execution of services according to a second embodiment, implemented by a calculation unit of a current host server. In the second embodiment, the weighting parameter ? used in the formula [MATH 2] for calculating the first probability vector is determined by the algorithm known as doubling trick.

[0172] Unlike the first embodiment, in said embodiment, the weighting parameter ? has a value that changes dynamically, so as to ensure convergence of the implemented algorithm.

[0173] The method comprises an initialization step 90, during which a parameter C is initialized to the value:

[00022]$\begin{array}{cc}C=\frac{Kln\left(K\right)}{e-1}& \left[\mathrm{MATH}16\right]\end{array}$

[0174] A variable l is set to zero, l referring to an index of a period during which the value of the weighting parameter ? is constant.

[0175] In addition, the time interval index is initialized to 1, and a set of cumulative global gain values for each moment of time index T.sub.k is set to 0:

[00023]$\begin{array}{cc}{G}_k\left(t=1\right)=0,?k& \left[\mathrm{MATH}17\right]\end{array}$

[0176] The method comprises a step 92 of calculating a value g.sub.l of gain limit for the period of index l:

[00024]$\begin{array}{cc}{g}_l=C?4^l& \left[\mathrm{MATH}18\right]\end{array}$

[0177] At initialization, l=0 as indicated hereinabove.

[0178] The method further comprises a step 94 of calculation of the value of the weighting parameter ? as a function of the index l:

[00025]$\begin{array}{cc}?=2^{-l}& \left[\mathrm{MATH}19\right]\end{array}$

[0179] The algorithm EXP3 is then implemented (step 45, comprising steps 52 to 58 described above with reference to FIG. 3) for the time interval t, with the value of the weighting parameter ? calculated during step 94. A migration moment of time T.sub.k* is then obtained, and an associated predicted gain x.sub.k*(t).

[0180] During an update step 96, the cumulative overall gain is incremented for the index k* corresponding to the selected migration moment of time T.sub.k*:

[00026]$\begin{array}{cc}{G}_{k^{*}}\left(t+1\right)=G_{k^{*}}\left(t\right)+x_{k^{*}}\left(t\right)& \left[\mathrm{MATH}20\right]\end{array}$

[0181] Where x.sub.k*(t) is the calculated predicted gain.

[0182] For the other values of k, the cumulative overall gain is unchanged: G.sub.k(t+1)=G.sub.k(t)

[0183] Then, during verification step 98, it is checked whether the maximum cumulative global gain value for the time interval t satisfies the following condition:

[00027]$\begin{array}{cc}{\max }_k{G}_k\left(t\right)?g_l-\frac{K}{?}& \left[\mathrm{MATH}21\right]\end{array}$

[0184] The maximum cumulative overall gain is compared with a threshold that depends on the number K of moments of time, as well as on the current weighting value ?.

[0185] If the cumulative overall gain is less than the threshold, the time interval index is incremented during the incrementation step 100 (t?t+1), and step 45 of implementing the EXP3 algorithm for interval t+1 is executed, with the same weighting parameter value ? as before.

[0186] If the condition verified in the verification step 98 is not satisfied, i.e. if the cumulative overall gain is greater than the threshold

[00028]$\left({\max }_k{G}_k\left(t\right)>g_l-\frac{K}{?}\right),$

then step 98 is followed by a step 104 of incrementing the index l referring to the period during which the value of the weighting parameter ? is constant l+l+1, and by an update of the values of the weighting parameter and the gain terminal g.sub.l.

[0187] Similarly to step 100, the time interval index is incremented during step 106.

[0188] Step 106 is followed by step 92 of calculation of a gain limit value g.sub.l for the index period l (for the new index value l), then step 94 of calculating a value of the weighting parameter ? as a function of the index l. The step 45 of implementation of the EXP3 algorithm for the interval t+1 is executed, with the calculated value of the weighting parameter ?.

[0189] According to alternative embodiments, in the method of the invention, the energy consumed for the migration depends on other parameters, e.g. on the migration moment of time.

[0190] Advantageously, the choice of the migration moment of time for each request is optimized as a function of a sum of gains associated with migrations of previous requests over a succession of moments of time.

[0191] Advantageously, the predicted gain for each request, for the selected migration moment of time and the determined number of replications, depends on the energy consumed for performing the replications, the risk metric and an availability metric, and of control parameters associated with a desired level of continuity of service. Thereby, the invention makes it possible to define a plurality of levels of continuity of service and to determine a migration moment of time for a chosen level of continuity of service.

[0192] Advantageously, for each level of continuity of service, the replication energy is minimized.

[0193] Advantageously, the proposed method is executable on a plurality of requests, coming from one or a plurality of mobile devices, over successive time intervals, and for each request, the weights used in the calculation of the components of the probability vector associated with the migration moments of time are updated according to the predicted gains.