Service Migration Algorithm Based on Markov Decision Process with Multiple Service Types and Multiple System Factors

I.   Introduction

The conventional centralized network architecture lacks flexibility for modern mobile applications. For example, a terminal has moved far away from the position where it initiates the service, if continuing to communicate with the original server will lead to high latency and causes waste of system resources in the core network. In order to solve this problem, 5G network uses software defined network (SDN) technology. SDN technology separates the software and hardware of network equipment, so that the functions of network equipment are no longer bound to specific hardware, which can meet the requirements of new advanced services more flexibly.

Specifically, SDN adopts the network architecture that contains the application layer, control layer and forwarding layer. The application layer realizes various network functions such as making service migration decisions discussed in this paper, and it communicates with the control layer with the northbound interface. The control layer is responsible for generating routes and internal switching paths on demand, handling network status changes, and controlling the devices in forwarding layer through the southbound interface. The forwarding layer performs packet forwarding and other actions according to the instructions from the control layer. Based on this structure, the data centers and services are deployed in distribution. When the terminal’s position changes, the services can be migrated to the nearest server to improve service quality.

Service migration can improve service experience of the users in terms of increasing the resource efficiency and reducing the latency, which is important in latency-sensitive scenario such as Internet of vehicles. There have been many studies on service migration, they mainly focus on the following aspects: 1) how to improve service quality [1]-[6], 2) how to reduce system resource consumption [7]-[10], and 3) both improving service quality and reducing system resource consumption [11]-[15].

However, the existing studies have the following problems: 1) None of these studies considers multiple system factors and multiple service types. In a system, there are many factors affecting quality of service (QoS), such as latency, jitter and bandwidth, which need to be fully considered. And different service types have different requirements on QoS, this also needs to be considered. 2) Most of the above studies use fixed threshold or instant revenue at the decision moment for migration decisions, we defined and used overall revenue to make migration decisions, considering not only the instant revenue but also the sum of the revenues in the whole connection time of the services.

Since only the current state and the related migration revenue are known at the current decision moment, the states and revenues in future are not known. To obtain the overall revenue, there must be a method to establish the relationship between the states at different decision moments, so that the future states and revenues can be predicted from the current state and revenue. Obviously, the current state is only related to the state of the last decision moment and the action performed, so it’s appropriate to use the Markov decision process to describe the relationship between the states at different decision moments during service migration process.

Motivated by these two problems, this paper proposes a service type distinguished (STD) service migration decision scheme, which comprehensively considers multiple system factors and make migration decisions to maximize the overall revenue. We use the Markov decision process to predict the mean value of the sum of the revenues in the whole connection time of the services. Services were divided into two types according to their different requirements on QoS, one is real-time services that are sensitive to latency, and the other is non-real-time services that are not sensitive to latency. To distinguish the two types of services, we set different values for the weight coefficients of each QoS parameter in the revenue and cost functions. Therefore, real-time services always tend to be migrated to reduce latency, while non-real-time services tend not to be migrated to reduce migration overhead.

The contributions of this paper are as follows:

1) Propose a service migration decision scheme that considers multiple system factors and distinguishes different service types by assigning different values for the parameters of different services. In this way, more latency revenue can be obtained through frequent migrations for real-time services, and system overhead can be reduced for non-real-time services through less frequent migrations.

2) The scheme makes migration decisions by maximizing the overall revenue, rather than according to instant revenue which is used in existing works.

3) We proved that the Markov chain can be used for estimating the overall revenue and presented the corresponding iterative algorithm. We also gave out the analyses of convergence and complexity of the algorithm.

The rest of this paper is structured as follows: Section II is the analysis of existing studies. Section III introduces the system model. Section IV is the simulation and discussion. And Section V is the summary and the future plan.

II.   Related Work

There are many studies focusing on the service migration problem, and some studied the models and frameworks of service migration. The authors of [16] proposed a dynamic service migration mechanism based on edge cognitive computing (ECC), and studied how cognitive computing can be combined with edge computing to provide service migration. In [17], the authors proposed a general framework for optimizing edge service migration based on reinforcement learning, which could learn different service migration strategies according to different optimization goals.

Some researchers focused on how to improve QoS through service migration. In [1], the authors studied around a specific service type of streaming media, focused on improving the cache hit rate of edge servers for low latency. The authors of [2] focused on the latency problem with the goal of minimizing the weighting and latency of all devices, proposed a scheme for computing resource evaluation, and used convex optimization theory for computing resource allocation. Based on the Internet of vehicles scenario, with latency and available bandwidth as the optimization goals, the authors of [3] focused on the routing transfer problem in the process of service migration. The authors of [4] researched on the latency in the service migration process, focused on reducing the interruption time of the service migration process using Docker, and proposed two migration solutions. In [5], the authors used the Markov decision process to train the migration model to improve service quality, but the model takes only one parameter of the distance between the user and the service location to define the state space. The authors of [6] used a reinforcement learning-based model to solve the service migration problem to reduce service discontinuity, but the training model is only for pre-set single user.

There are also some researchers focused on how to reduce system overhead or reduce system energy consumption. The authors of [7] used the Lyapunov function to calculate the balance point of the system to make service migration without predicting user trajectories, and minimized system energy consumption on the premise of ensuring latency. The authors of [8] payed attention to the cost of service migration and divided users into high-mobility users and ordinary users, and the algorithm focuses on speeding up the recovery speed when services are blocked. In [9], the authors analyzed the vehicle edge network scenarios, and proposed an algorithm that integrates network performance, edge server processing capabilities and terminal movements to make migration decisions, which pays more attention to the server, but does not pay attention to the QoS. The authors of [10] proposed a brownout-based approximate Markov decision process approach to improve system performance and reduce energy consumption through deactivating non-mandatory components of applications.

A few researchers combined the previous two studies, and focused not only on improving the service quality, but also on reducing the consumption of system resources. The authors of [11] focused on the cost and latency of service migration, and coordinated service migration by predicting vehicle movement routes. The authors of [12] proposed a migration algorithm that perceives the service quality of the existing handover procedure for the scenario of the Internet of Vehicles, and payed attention to the latency, reliability and service migration cost. In [13], the authors researched in the Internet of vehicles scenario, the model considers the speed of the vehicle. In [14], the authors also studied the Internet of vehicles scenario, focused on latency and service migration cost, and used Markov process for model optimization to minimize the total service delay and migration cost. The authors of [15] proposed a probabilistic service migration approach for delay-aware and mobility-aware mobile edge computing, which guarantees latency for terminals while reducing energy consumption in the cloud by optimizing service deployment.

Some of the studies use fixed threshold to make migration decisions, some based on instant revenue, but none of them distinguishes the different requirements on QoS of different service types. The comparison of related work is as Table 1.

Table  1.  Comparison of related work

Scheme	Research emphasis		Scenario		Decision method		Algorithm complexity
	QoS	Resource consumption	Specific	General	Threshold	Action revenue	Low	High
[1]	$\checkmark$		$\checkmark$			$\checkmark$		$\checkmark$
[2]	$\checkmark$			$\checkmark$		$\checkmark$		$\checkmark$
[3]	$\checkmark$		$\checkmark$		$\checkmark$		$\checkmark$
[4]	$\checkmark$			$\checkmark$	$\checkmark$		$\checkmark$
[7]		$\checkmark$		$\checkmark$	$\checkmark$			$\checkmark$
[8]		$\checkmark$		$\checkmark$	$\checkmark$		$\checkmark$
[9]		$\checkmark$	$\checkmark$			$\checkmark$		$\checkmark$
[10]		$\checkmark$		$\checkmark$		$\checkmark$	$\checkmark$
[11]	$\checkmark$	$\checkmark$	$\checkmark$			$\checkmark$		$\checkmark$
[12]	$\checkmark$	$\checkmark$	$\checkmark$		$\checkmark$		$\checkmark$
[13]	$\checkmark$	$\checkmark$	$\checkmark$			$\checkmark$		$\checkmark$
[14]	$\checkmark$	$\checkmark$	$\checkmark$			$\checkmark$		$\checkmark$
[15]	$\checkmark$	$\checkmark$		$\checkmark$	$\checkmark$		$\checkmark$
Ours	$\checkmark$	$\checkmark$		$\checkmark$		$\checkmark$	$\checkmark$

 | Show Table

DownLoad: CSV

III.   System Model

In this section, we introduce the system model used in this paper, including the network architecture, terminal movement model, Markov state space, revenue function and service migration decision scheme.

1   Application scenario

We consider a wireless cellular network, each cell corresponds to a service area with edge servers. As illustrated in Figure 1, when the terminal moves from service area 1 to service area 2, the system will gather information from the network and the terminal, and make migration decision based on the multiple system factors and QoS requirements. If the result is making migration, then the services will be migrated from the original server to the new server. Otherwise, the services will not be migrated.

Figure  1.  Heterogeneous service migration with multiple attributes.

DownLoad: Full-Size Img PowerPoint

2   Markov decision model

1   Define the state space

In the Markov model, the changes of different Markov states lead to different instant revenues, so the state is associated with the revenue, it should reflect instant information of the terminal. In the scenario considered in this paper, the terminal is moving continuously, the distance between the terminal’s current cell and the original cell is changing in real-time, and the services running on the terminal are also changing in real-time. So we take these two main factors as the state space of the decision model as follows:

where $D\in\{0,1,2\ldots,{\mathrm{thr}}\}$ represents the distance between the terminal’s current cell and the original cell in terms of circles, and $\mathrm{thr}$ represents the maximum circle distance allowed, when exceeding this distance, service migration will be performed by default. $s_r \in \{0, 1\}$ represents real-time services that have high requirements on latency, such as video call or autopilot in the car, where 1 represents the terminal is running this type of services, and 0 represents the terminal is not running this type of services. $s_n\)\($ represents non-real-time services such as file download or application upgrade, where 0 and 1 have the same meanings as those for real-time services.

2   Define the action

The action is the decision made according to the revenue function under the current condition, and the state transfers from $s$ to $s{'}$ through action $a$.

When action $a$ is equal to $a0$, the services will not be migrated. When action $a$ is equal to $a1$, the services will be migrated. In this paper, considering the complexity of technical implementation, we assume that when performing service migration, all services on the same terminal will be migrated together.

3   State transition probability

In order to calculate the overall revenue by summing instant revenues of state space, we need to know the probability of each state. Since the next state is associated with the current one, if the current state is already known, then we can calculate the probability of next state through state space transition probability matrix. As described above, the state space is divided by the distance and service types running on the terminal.

We evaluate the transition probabilities among the states of service types first. Divide according to whether there is such type of services running on the terminal, there are four states of service types, they are respectively $\{s_r,s_n\}=[\{0,0\},\{0,1\},\{1,0\},\{1,1\}]$, with transform to the state transition process, the state transition diagram is shown in Figure 2.

Figure  2.  State transition diagram of service types.

DownLoad: Full-Size Img PowerPoint

Assume that the arrival and departure of services follow the Poisson distribution. We use $r+$ to represent arrival of real-time services, use $r-$ to represent departure of real-time services, use $r0$ to represent unchanged to real-time services, and $n+$, $n-$, and $n0$ to represent arrival, departure and unchanged of non-real-time services respectively, then the service state transition matrix is

In the state transition probability matrix ${\boldsymbol{P}}^1$, ${\boldsymbol{P}}^1_{i,j}$ represents the probability of transferring from state $i$ to state $j$, where $i,j=1,2,3,4$ correspond to the four states of $\{0,0\},\{0,1\},\{1,0\},\{1,1\}$ in $\{s_r,s_n\}$.

Let the arrival and departure rates of real-time services are $\lambda_1\mathrm{e}^{-\lambda_1}$ and $\mu_1\mathrm{e}^{-\mu_1}$ respectively, the probability of keeping the same state is $1-\lambda_1\mathrm{e}^{-\lambda_1}-\mu_1\mathrm{e}^{-\mu_1}$. Similarly, the arrival and departure rates of non-real-time services are $\lambda_2\mathrm{e}^{-\lambda_2}$ and $\mu_2\mathrm{e}^{-\mu_2}$ respectively, the probability of keeping the same state is $1-\lambda_2\mathrm{e}^{-\lambda_2}- \mu_2\mathrm{e}^{-\mu_2}$. Then the transition probability matrix of real-time and non-real-time services of the terminal is as ${\boldsymbol{P}}^1$ below.

From transition probability matrix ${\boldsymbol{P}}^1$ we can see that ${\boldsymbol{P}}^1_{1,1}$ represents the probability of the service state transfers from {0,0} to {0,0}, which is the probability that real-time and non-real-time service status remains the same with the probability of $(1-\lambda_1\mathrm{e}^{-\lambda_1}-\mu_1\mathrm{e}^{-\mu_1})\times (1-\lambda_2\mathrm{e}^{-\lambda_2}-\mu_2\mathrm{e}^{-\mu_2})$. Another example like ${\boldsymbol{P}}^1_{1,2}$ represents the probability of the service state transferring from {0,0} to {0,1}, which means the terminal starts a new non-real-time service while real-time service status remaining the same with the probability of $(1-\lambda_1\mathrm{e}^{-\lambda_1}- \mu_1\mathrm{e}^{-\mu_1})\lambda_2\mathrm{e}^{-\lambda_2}$.

The above state transition probability only considers the state space of service types, the complete state space also includes the state of the distance between the terminal’s current cell and the original cell, we use $D$ to represent the circle distance between the terminal’s current cell and the original cell where the server that the terminal is communicating with locates. Figure 3 shows the state transition diagram of circle distance $D$.

Figure  3.  State transition diagram of circle distance.

DownLoad: Full-Size Img PowerPoint

In Figure 3, 0 represents the terminal is in the original cell, the terminal is communicating with the edge server in the cell, 1, 2 and other values represent the circle distances between the current cell and the original cell, $\mathrm{thr}$ is the maximum distance allowed, when exceeding this distance, service migration will be performed. When taking action $a0$, the services will not be migrated, and when taking action $a1$, the system will perform service migration. After service migration, the $D$ in state space will return to 0.

According to the network architecture in the scenario we considered and the moving model of the terminal in cellular network researched in [18], we can obtain the following terminal movement probabilities in the cellular network.

where $p_m$ represents the probability of the terminal moving from the current cell to a neighboring cell.

From the state transition diagram and (1), we can get the transition probability matrix ${\boldsymbol{P}}^2$ of the circle distance:

where ${\boldsymbol{P}}^2_{i,j}$ represents the probability of transferring from state $i$ to state $j$, $i$ and $j$ represent the circle distance $D$. For example, ${\boldsymbol{P}}^2_{0,0}$ represents the probability of circle distance changing from 0 to 0, which is $p1=1-p_m$ in the transition diagram. And the probabilities, such as ${\boldsymbol{P}}^2_{0,1}$, which have not been defined in the distance state transition diagram, will be set to 0 uniformly.

Combining the state transition probability matrices ${\boldsymbol{P}}^1$ and ${\boldsymbol{P}}^2$, we can get the global state transition probability matrix ${\boldsymbol{P}}$ as

The size of ${\boldsymbol{P}}$ is $\big(4\times({\mathrm{thr}}+1)\big)\times \big(4\times({\mathrm{thr}}+1) \big)$, where $4\times({\rm{thr}}+1)$ is the whole number of the state space, and the elements in the matrix are the probabilities that a terminal transfers from state $s$ to state $s{'}$ through action a, which is $P[s{'}|s,a]$.

4   Instant revenue

The instant revenue function depends on the current state and the action taken, and a revenue function can be generated from a given state $s$. The instant revenue is the net revenue obtained from service quality of the migration decision after removing system overhead each time a terminal moves. The instant revenue function we defined includes the following parts.

a) Revenue of latency and jitter

Latency and jitter are two attributes that affect service experience. Through the researches on latency in [2], [15] and [19], we know that the latency of the terminal is related to the distance between the terminal and the server that provides services for it. And jitter is randomly caused by the network environment or the servers, the larger the distance is, the more network devices and servers a data link passes through, the larger the probability and the range of jitter. When performing service migration, the processing time is also counted.

The total latency in the whole process includes the wireless part and the wired part. In the model studied in this paper, the wireless part is not related to the distance between the terminal and the server, and only the wired part is related to the distance. When the terminal is in the original cell, the distance $D$ is 0, and the terminal has the minimum latency of $t_0$. We set $t_0$ as the base latency, which represents the latency when the terminal and the server are in the same cell.

The jitter in the data link is a random value and increases roughly with the increase of distance, here we take the mean value of jitter and consider it linear with the change of distance. We use $\rho t_0$ to represent the jitter, $\rho$ is the proportional coefficient of jitter and $t_0$.

We put the latency brought by service migration into consideration at the migration cost, and the revenue loss during migration process will also be considered in migration cost. We simplify the relationship between latency and distance to be linear here when designing the revenue function, and define the latency and jitter revenue function $t(s,a)$ through comprehensive consideration of both real-time services and non-real-time services as

where $\alpha_1$ and $\alpha_2$ represent the influence coefficients of latency on real-time services and non-real-time services respectively. $\beta_1$ and $\beta_2$ represent the influence coefficients of jitter on real-time and non-real-time services respectively. For real-time services with high requirement on latency and sensitive to jitter, $\alpha_1$ and $\beta_1$ have bigger values, and for non-real-time services with low requirement on latency and non-sensitive to jitter, $\alpha_2$ and $\beta_2$ have smaller values on the contrary. The total latency is the sum of base latency $t_0$ and additive latency $k_{t}D$. Different migrations through different actions $a$ lead to different $D$, hence the value of $D$ is associated with the current state $s$ and action $a$. $k_{t}$ represents the proportional coefficient of the latency varying with the distance, it’s a positive number. When the distance increases, the latency and jitter revenue decrease.

b) Revenue of available bandwidth

The available bandwidth is another attribute that influences the QoS, it also reflects the load condition of the system.

According to the relevant model in [20], we define the available bandwidth revenue function $b(s,a)$ as

where $\delta_{1}$ and $\delta_{2}$ represent the influences of available bandwidth on real-time services and non-real-time services respectively, $x$ represents the bandwidth provided by the system, $\sigma_1$ and $\sigma_2$ represent the bandwidths required by real-time services and non-real-time services respectively, different services have their separate requirements on transmission bandwidth. When the bandwidth provided by the system meets the requirements of services, the revenue is maximized, when the provided bandwidth is lower than requirements, the service experience is reduced. The function $\exp{\left[-\frac{[\min(0,x-\sigma_{1})]^2}{2\sigma_{1}^{2}}\right]}$ is used to adjust the revenue according to above description.

c) Migration cost of multiple system factors

The migration cost consists of resource consumption during service migration in the core network and the corresponding service termination during this process. When performing service migration, the system needs to transfer the service data used by terminal from current server to another new one, and runs the corresponding programs on the new server to provide services for the terminal, this will consume system bandwidth and resource on servers. During this process, the service will also be suspended, which represents an increase in the latency of terminal. The bigger the user data, the more bandwidth and resource consumption in the network and servers, and the longer suspending time. As the suspending time is directly related to the data transmission and program processing in the system, here we do not deal with it individually.

Due to the differences between the different service types, real-time services require small latency and jitter to improve service experience, while non-real-time services do not have this requirement. Therefore, when the position of the terminal changes, real-time services always tend to perform service migration to obtain smaller latency, but from the aspect of the system, frequent service migrations will consume too much system resource, thereby reducing the overall performance.

As described above, the migration cost is associated with network bandwidth and server resource consumption and correspinding suspending time. The transmission bandwidth in core network is assumed to be sufficient here, and the cost function $c(s,a)$ is defined as

The cost function is the product of state vector $[s_r,s_n]$ with action variable $a$ and cost vector $\boldsymbol m$. When no migration is performed, the action variable $a$ is 0, and there is no migration cost, and the action variable $a$ is 1 if migration is performed. The cost vector is $\boldsymbol m$. $C_b^r, C_b^n$ and $C_s^r, C_s^n$ are the bandwidth consumption and server resource consumption of real-time and non-real-time services respectively, the consumptions of real-time and non real-time services are different. $p$ and $q$ are the influence coefficients of network bandwidth and server resource consumption on the system during migration, the more powerful the performance of the server, the smaller the values of $p$ and $q$, which means the influence of migration cost on the overall revenue is smaller. The bigger the migration cost, the greater the negative influence on the overall revenue of the whole system. $k=p/q$ is the ratio between the network transmission capacity and the data processing capacity of the system, which reflects the capability characteristic of the system, such as transmission system or computing system.

d) Revenue function of multiple system factors

Different latency, jitter and available bandwidth have different affects on different service types, resulting in different revenues. We can adjust the influence of each QoS factor on revenue of different service types through the weight coefficients according to the requirements on service quality of the divided service types. According to (2), (3) and (4), we can obtain the following revenue function that combined latency and jitter and available bandwidth after removing the migration cost:

5   Optimization model

The goal of the model is to maximize the overall revenue, that is to maximize the sum of instant revenues of all actions. The overall revenue here refers to the total net revenues from all migration decisions in the whole connection time of all services on all terminals.

The overall revenue function is

where $\pi$ is a service migration decision strategy consists of a set of actions performed at each specific state, the initial state is $s^0$, $\gamma\in{[0,1]}$ represents the reduction factor which means the importance of long-term revenues relative to instant revenues. Specially, $\gamma=0$ represents we only consider instant revenues without considering long-term revenues, while $\gamma=1$ represents we consider long-term revenues as important as instant revenues. $E_{\pi}\left\{\sum\limits_{t=0}^{\infty}\gamma^{t}r(s^t,a^t)\right\}$ represents the overall revenue function through calculating the expectation of the sum of instant revenues.

Our goal is to find out a maximum overall revenue function $v^{\pi^{*}}(s^0)$ as follows:

Theorem 1 The over all revenue function $v^{\pi}(s^0)$ can be expressed as

Proof For each state is associated with the previous one, so the overall revenue is related with the initial state and the actions taken at each state. We extract the first term from the expectation of (6), and obtain (8) as follows:

then we expand the first half of (8), it follows:

and then transform the last half of (8) into (10):

Replace $E_{\pi}\left\{\sum\limits_{t=0}^{\infty}\gamma^{t}r(s^{t+1},a^{t+1})\right\}$ in (10) with $v^{\pi}(s{'})$, and add (9) and (10), it follows:

With Theorem 1, (7) can be expressed as

Different $\pi$ leads to different values of overall revenue function by adopting different strategies. Our goal is to find out a strategy $\pi^{*}$ to maximize the sum of all revenues at all states, and that is the migration scheme we get last to make the service experience and system overhead optimized.

3   Model solving

According to the expression above, the optimization algorithm of the model is as Algorithm 1.

The iterative method is used to optimize the model, first, the overall revenue is set to 0, then calculate the revenue of each state step by step according to (5), and calculate the overall revenue until the stopping condition we set is met. Then repeat the steps with other strategies, finally the set $\pi$ of actions corresponding to the maximum value is the optimal migration strategy $\pi^{*}$ that we want to find. The parameter $\varepsilon$ is used to adjust the number of iterations, a smaller $\varepsilon$ can improve the accuracy of the algorithm, and a larger $\varepsilon$ can reduce the amount of computation.

4   Convergence analysis of the algorithm

In this paper, the incremental gain ratio is used to control the iterative process of the algorithm. At each time a migration decision is made, different revenues can be obtained according to different actions, the revenues vary randomly within a certain range. To simplify the analysis, it is assumed that the revenues of each migration decision are the same, which is r0, then the overall revenue after $\frac{1}{\varepsilon}+1$ times of iterations is $r0*(\frac{1}{\varepsilon}+1)$, and it is $r0*(\frac{1}{\varepsilon}+2)$ after $\frac{1}{\varepsilon}+2$ times of iterations.

And now

which meets the stopping condition we set, then the calculation will stop after $\frac{1}{\varepsilon}+2$ times of iterations. In actual, since the revenue of each migration decision is different, the number of iterations will increase or decrease, but their statistical average tends to be $\frac{1}{\varepsilon}+2$. Therefore, the proposed algorithm is convergent.

5   Complexity analysis of the algorithm

There are two service types and four combinations of service types defined in this paper, and there are a total of $\mathrm{thr}+1$ kinds of distance in the proposed algorithm. The size of the state space is $4\times({\mathrm{thr}}+1)$, that is, there are a total of $4\times({\mathrm{thr}}+1)$ states that the Markov decision process may experience. Two actions can be taken at each state: migrate or not. Then the number of actions may be experienced in one iteration is $O\left(2^{4\times({\mathrm{thr}}+1)}\right)$, together with the iterative times analyzed above, the total complexity of the algorithm is $O\left(2^{4\times({\mathrm{thr}}+1)}\times(\frac{1}{\varepsilon}+2)\right)$, $\mathrm{thr}$ and $\varepsilon$ are fixed parameters, they are limited numbers, compared with [15], the complexity of the proposed algorithm is in the same order of magnitude.

IV.   Simulation and Discussions

Based on the network model proposed in Section III, we used a set of synthetic parameters to perform the simulation.

Assume that the real-time services and non-real-time services are running on the terminal at the same time, we took video call as the reference for real-time services, the requirement on transmission bandwidth $\sigma_1$ is 5 Mbps, and the declared requirement on latency is not exceeding 100 ms, the arrival rate and departure rate of it are 0.1 and 0.05 respectively. For non-real-time services, the HD video streaming media caching was used as the reference, the requirement on transmission bandwidth $\sigma_2$ is 10 Mbps, with no requirement on latency, the arrival rate and departure rate of it are 0.15 and 0.1 respectively.

The available bandwidth $x$ provided by the server was changing randomly between 3 Mbps and 20 Mbps. The base latency $t_0$ was set to 30 ms. The proportional coefficient $k_t\)\($ was set to $0.02+{\mathrm{ random}}(-0.01,0.01)$, which indicates that every time the distance increases by 1, the latency increases by 20 ms and changes randomly within 10 ms. The weight coefficients of cost consumption $p$ and $q$ were both set to 0.5.

Due to the latency and jitter have more influence on experience of real-time services and less influence on non-real-time services, $\alpha_1$ and $\beta_1$ were set to 0.04 and 0.02 respectively, and $\alpha_2$ and $\beta_2$ were both set to 0.01. While available bandwidth has more influence on experience of non-real-time services than that of real-time services, $\delta_1$ was set to 0.2 and $\delta_2$ was set to 0.4. Real-time services are often computing services, only the service data of the user needs to be transferred to the new server while performing service migration. Non-real-time services are often resource-based services, and a large number of files need to be transferred during migration. Therefore, the migration costs $C_b^r, C_b^n$ and $C_s^r, C_s^n$ in this paper were set to 0.2, 0.7 and 0.3, 0.5 respectively.

The probability that the terminal moves from the current cell to a neighboring one was set to 0.75. The maximum circle distance $\mathrm{thr}$ was set to 5. The reduction factor $\gamma$ that adjusts the importance of long-term revenues relative to instant revenues varied between 0 and 1, when not specified, the value was 1 by default. The iteration control parameter $\varepsilon$ was set to 0.001.

The following algorithms were selected as comparison:

1) Never migrate (NM): The service is always provided by the initial server, and there is no migration cost in the network.

2) QoS first (QF): The service will always be migrated as the terminal moves to ensure the best service quality.

3) Considering both QoS and cost (PDMA proposed in [15]), the algorithm minimizes migration cost while ensuring service quality.

Figures 4–6 are the simulation results of the scenario where both real-time services and non-real-time services exist.

Figure  4.  Changes of latency at different decision moments.

DownLoad: Full-Size Img PowerPoint

Figure  5.  Changes of migration cost with different reduction factors.

DownLoad: Full-Size Img PowerPoint

Figure  6.  Changes of overall revenue with different reduction factors.

DownLoad: Full-Size Img PowerPoint

It can be seen from Figure 4 that every time the latency falls from the peak to about 30 ms means that a service migration is performed. Compared with PDMA, more frequent migration operations are performed, and the latency is controlled to meet that required by service declaration. Accordingly, the migration cost of proposed scheme is also larger than PDMA in Figure 5. However, as can be seen from Figure 6 that the proposed algorithm has the best overall revenue, this is because the proposed algorithm does not make migrations rely on a fixed threshold, but maximizes the overall revenue. At each decision moment, it calculates the instant revenue of migrating or not in the current state, and calculates the long-term revenue that could be obtained corresponding to different actions according to the state transition probability matrix, and takes the action corresponding to the maximum total revenue as the decision. It can also be seen that the overall revenue increases as the reduction factor gets larger and reaches maximum when the reduction factor is 0.9.

Next are the simulation results for two special cases with only real-time services or only non-real-time services exist.

From Figures 7 and 8, it can be seen that the proposed algorithm exhibits different decision-making behaviors in the two cases. When there are only real-time services, the algorithm performs frequent migration operations, which is close to the QF algorithm. When there are only non-real-time services, the migration frequency is very low, which is close to the NM algorithm. From Figure 7, it can be seen that the latency guarantee rate of real-time services is 100% by frequent migrations. Because we distinguish the different requirements of the two types of services, the high migration costs caused by real-time services can be balanced by non-real-time services which seldom migrate, which ensures the latency requirements of real-time services while keeping migration cost acceptable. The migration costs in Figures 9 and 10 also show the different behaviors of the proposed algorithm. This reflects that the proposed scheme can adapt to the latency requirements of different services, and also considers reducing the migration cost. It’s because that the proposed algorithm assigns different weights to the migration revenues and costs of the two types of services, when there is only one type of services exists, the algorithm will calculate the revenue according to the parameters set for this type of services. Comparing with algorithms that do not distinguish service types, it can reflect the differences in requirements on QoS of different services more accurately, so as to make migration decisions more suitable for the differentiated requirements. The overall revenues obtained by the proposed algorithm in Figures 11 and 12 are the largest compared to others, the reason is the same as that in Figure 6. The QF and NM algorithms achieved opposite overall revenue in these two cases. When there are only real-time services, compared with the NM algorithm, the QF algorithm is closer to meet the requirements of the services, and the NM algorithm has the largest difference from the requirements. Therefore, the QF algorithm obtained larger revenue, and the NM algorithm obtained the smallest revenue. When there are only non-real-time services, the NM algorithm is closer to meet the requirements of the services, while the QF algorithm is the most different from the requirements, so the performances of the two are opposite to that when there are only real-time services.

Figure  7.  Changes of latency with only real-time services.

DownLoad: Full-Size Img PowerPoint

Figure  8.  Changes of migration cost with only real-time services.

DownLoad: Full-Size Img PowerPoint

Figure  9.  Changes of overall revenue with only real-time services.

DownLoad: Full-Size Img PowerPoint

Figure  10.  Changes of latency with only non-real-time services.

DownLoad: Full-Size Img PowerPoint

Figure  11.  Changes of migration cost with only non-real-time services.

DownLoad: Full-Size Img PowerPoint

Figure  12.  Changes of overall revenue with non-real-time services.

DownLoad: Full-Size Img PowerPoint

V.   Conclusion

This paper proposes a service migration algorithm to satisfy QoS requirements when the terminal moves. The algorithm distinguishes the different requirements on service quality such that the revenue and cost can be balanced. The proposed algorithm makes migration decisions based on overall revenue rather than fixed threshold or instant revenue, and Markov decision process was used to maximize the overall revenue of the system. Simulation results show that the largest revenue in whole process of service connection was obtained by the proposed algorithm.

In the next step, we will increase the analysis of energy consumption of servers, and research how to reduce energy consumption of the system while guaranteeing service quality to cope with the trend of increasingly energy efficiency.