LMM: latency-aware micro-service mashup in mobile edge computing environment

Internet of Things (IoT) applications introduce a set of stringent requirements (e.g., low latency, high bandwidth) to network and computing paradigm. 5G networks are faced with great challenges for supporting IoT services. The centralized cloud computing paradigm also becomes inefficient for those stringent requirements. Only extending spectrum resources cannot solve the problem effectively. Mobile edge computing offers an IT service environment at the Radio Access Network edge and presents great opportunities for the development of IoT applications. With the capability to reduce latency and offer an improved user experience, mobile edge computing becomes a key technology toward 5G. To achieve abundant sharing, complex IoT applications have been implemented as a set of lightweight micro-services that are distributed among containers over the mobile edge network. How to produce the optimal collocation of suitable micro-service for an application in mobile edge computing environment is an important issue that should be addressed. To address this issue, we propose a latency-aware micro-service mashup approach in this paper. Firstly, the problem is formulated into an integer nonlinear programming. Then, we prove the NP-hardness of the problem by reducing it into the delay constrained least cost problem. Finally, we propose an approximation latency-aware micro-service mashup approach to solve the problem. Experiment results show that the proposed approach achieves a substantial reduction in network resource consumption while still ensuring the latency constraint.

Keywords: Micro-service; Mobile edge computing; Network resource consumption; Latency; Mashup

Nowadays, IoT is a term that has gained widespread attention from academia, business, and government [[1]]. Many researchers devote to exploiting IoT technologies to make the city more open, efficient, sustainable, productive, and competitive [[3]–[5]]. E.g., citywide crowd flows can be forecasted by mining traffic data send by sensors[[6]–[8]], face recognition, and human identification [[9]] can be performed based on the photos taken by video cameras installed in the street.

With the advancement of software technique, complex IoT applications have been implemented as a set of lightweight and independent micro-services [[10]]. Each micro-service is provided by a lightweight container [[11]]. Different from services in the form of monolithic software, micro-services allow IoT services deployed more easily and flexibly [[12]]. The functional capability of a single micro-service is limited. A collection of loosely coupled micro-services are structured to implement complex business capabilities through lightweight communication protocols. We refer to this process as micro-service mashup.

Where to put the IoT services is an important issue that should be addressed. One efficient way is to deploy the IoT services on the cloud [[13]]. However, the user is at the edge of the mobile network, and clouds are typically far from the network edge. The high latency makes cloud computing not efficient enough for these IoT services [[15]]. The problem cannot be solved only through spectrum extension. In addition, much pressure is added to the network. The current core network bandwidth would be challenged for its capability of transferring large amount of the IoT-created data [[16]].

Mobile edge computing [[17]] has been introduced to the IoT service provision for shorter response time and smaller network pressure [[18]]. As shown in Fig. 1, mobile edge computing offers an IT service environment at the Radio Access Network (RAN) edge. With the capability to reduce latency and offer an improved user experience, mobile edge computing can make a great contribution to satisfy the high throughout and low latency requirements of 5G. The burden of backbone IP networks and cellular core networks can be greatly relieved. We can also exploit the real-time radio network conditions to optimize the network and service. European 5G PPP recognizes mobile edge computing as a key technology toward 5G. The emergency of mobile edge computing presents great opportunities for the development of 5G and IoT applications.

Graph: Fig. 1 Mobile edge computing environment

There are still several issues that should be addressed for provisioning micro-services in the edge. One significant issue is how to produce the optimal collocation of suitable micro-service for a user with the consideration of the network traffic. Because the process capability of a single micro-service is limited, larger amount of micro-services that deliver the same functionality are usually deployed. To avoid ambiguity, we refer to the end-to-end service for a user as an application, refer to all atom component units with the same functionality as micro-service and refer to each candidate as micro-service instance. The micro-service mashup strategy has significant impact on the Quality of Service (QoS) and the network resource utilization. One factor largely contributes to this issue; edge computing is a distributed computing platform. Those micro-service candidates potentially differ in terms of location for deploying over containers on different cloudlets. There is a tremendous difference in latency and network resource utilization when the micro-services from different containers are selected in the service mashup process. Thus, the communication latency and network resource consumption grow when the selected micro-services are deployed far away from each other or from the end user. Little attention has been paid to the problem.

Although service mashup problem has already been studied in the literature, micro-service mashup in mobile edge computing environment is relatively novel in the research community. Many works have addressed service mashup and services composition problems, such as [[19]–[22]]. These works focus on this QoS-aware service mashup/composition problem and give their solutions from different perspectives. However, most of those studies do not account for the network condition, the location of the requestor, and inter-service latency, which may have significant impact on the micro-service mashup in mobile edge computing environment.

In addition, it seems that micro-services mashup is similar to workflow provision [[23]]. Although sharing several characteristics, micro-services provision, and workflow provision are not the same. A workflow task consists of several individual sub-tasks [[24]]. Workflow provision deals with static sub-tasks connection topology where sub-tasks are arranged in a fixed, predetermined order [[25]]. In contrary, component units of micro-services are loosely coupled. Micro-services mashup deals with complex services that are generated based on business capability requirements where the connection topology of the component units is not flexible.

In this paper, we propose a latency-aware micro-service mashup algorithm in mobile edge computing environment. We formulate the problem into an integer nonlinear programming. The aim of the integer nonlinear programming is to reduce the network resource consumption while the overall turnaround time satisfies a specific constraint. The functional requirements, with respect to the latency requirements, the topology of edge network, and the statements of each micro-service instance, are considered in the formulation. We prove that the problem is NP-hard. As we know, a NP-hard problem cannot be solved in polynomial time. To address this issue, an approximation algorithm is designed to make a trade-off between the goodness of the approximation and the running time for micro-service mashup. We conduct experiment on the Shanghai Telecoms base station dataset. The experiment results illustrate that our approach can reduce network resource consumption while still guaranteeing end-to-end latency.

More specifically, the major contributions include:

• In contrast to existing service mashup approaches, we focus not only on efficient service mashup but also on network resource consumption in edge network as another essential consideration. To the best of our knowledge, this is the earliest effort to consider network resource consumption for micro-service mashup in mobile edge computing environment.
• We formulate the problem into an integer nonlinear programming. We prove the NP-hardness of the problem by reducing it into the delay constrained least cost problem. An approximation latency-aware micro-service mashup approach (LMM) is proposed by us to solve the problem.
• To evaluate the performance of our approach, we implement all approaches in a simulation platform. The experimental results show that our approach achieves higher network-resource efficiency as well as end-to-end latency guarantee.

The remainder of this paper is as follows: Sect. 2 provides a review of the mobile edge computing and service mashup-related work. Section 3 describes the system model. We formulate the micro-service mashup problem in mobile edge computing as a optimization problem in Sect. 4. Section 5 presents LMM, an approximation approach to solve micro-service mashup problem. Section 6 compares the performance of LMM with respect to state-of-the-art algorithms. Finally, Sect. 7 concludes our work and presents the future work.

There are plenty of related works in the literature. Due to space limitation, we will only review some notable work here.

The stringent requirements of IoT services have brought great challenges to 5G network and computing paradigm. Traditionally, the IoT service requests are submitted through the mobile edge network and processed by the remote cloud. Although cloud computing has tremendously changed the way we live, cloud computing is not always efficient for IoT service providing. Traditionally, clouds are geographically far away from network edge. The communication latency is always long and unpredictable. The low latency, high bandwidth requirements cannot be satisfied by only extending spectrum resources. Mobile edge computing has been introduced to address this issue. In mobile edge computing, IT service environment and cloud-computing capabilities are provided in the mobile edge network within the RAN. The services are provisioned on cloudlets. A cloudlet is a resource-rich cluster [[27]] and co-located with the base stations (BSs) in a mobile edge network within the RAN. Mobile edge computing promises dramatic increment throughout and reduction in latency, tackling the key challenges for materializing 5G vision. Together with Software-Defined Networking and Network Functions Visualization, mobile edge computing is recognized by the European 5G PPP as key technology toward 5G.

Many studies focus on the cloudlet placement problem in a mobile edge network. A large-scale mobile edge network consists of hundreds and thousands of BSs. Poor cloudlet placement strategy will results in load unbalance and long access latency. The cloudlets that are close to the large stream of people will be overloaded, while other cloudlets that are far away from the stream of people are under-loaded. Considering the topology of mobile edge network, cloudlet placement methods are proposed by [[28]]. The methods presented in [[29]] investigate to offload computation-intensive tasks of mobile users to cloudlets for energy savings. Taking the QoS requirements into consideration, Hoang et al. [[30]] devise a novel linear programming solution for task offloading in mobile edge computing environment. Cardellini et al. [[31]] and Gelenbe et al. [[32]] consider that tasks can be offloaded to both the cloud data center and the local cloudlets at the same time. When all cloudlets have been placed in the mobile edge network, we should determine which cloudlet to process a specific request. The methods proposed in [[33]] deal with the request assignment problem to minimize the average access latency. However, those methods assume that all services are independent from each other, and do not consider the condition that a collection of loosely coupled micro-services should be structured to implement complex business.

A workflow task consists of several individual tasks. Workflow scheduling is to optimize the Task-to-Resource assignment. Malawski et al. [[34]] aim to gain insight into resource allocation for executing scientific workflow on clouds with budget and deadline constraints. Zhu et al. [[35]] study to optimize multiple objectives simultaneously for workflow scheduling in cloud computing environment and work to come up with an evolutionary algorithm to solve the problem. Arabnejad et al. [[36]] design a low-time complexity workflow scheduling algorithm with Quality of Service constrained on heterogeneous resources. There is a lot of wastage for inefficient use of resources. Lee et al. [[37]] proposed a resource-efficient scheduling algorithm for workflow application in clouds

Micro-services mashup and workflow provision are not the same. Sub-tasks of a workflow are arranged in a fixed, predetermined order. The connection topology of a workflow application is flexible. Contrary, component units of micro-services are loosely coupled. A collection of loosely coupled micro-services are structured dynamically based on the business capability requirements.

Service mashup/composition is a hot research field in service computing. We need to composite several atom services to achieve a more complex service when the functional requirements of a user cannot be fulfilled by an individual service. Most of current researches assume that all the QoS values can be predetermined and aim to select the service with optimal QoS value. Achieving a trade-off between adaptation and efficiency in a highly dynamic environment is challenging and necessary. Multi-agent techniques and reinforcement learning are integrated together for adaptive service composition for the method proposed by Wang et al. [[38]]. QoS is an significant criterion in the service selection process for composition. Deng et al. [[39]] exploit the fact that QoS attributes of a service are correlated with other services. QoS correlations are considered in service selection for composition. Chen et al. [[40]] formulate the QoS-aware service composition as a multi-objective optimization problem and present a flexible evolutionary algorithm to solve the problem. Deng et al. [[41]] investigate to study how to select component services from all candidates to create mashups with optimal cost performance. However, the network condition and how to calculate the inter-services latency are ignored in the proposed approach.

Table. 1 summarizes the symbols used in this paper. As shown in Fig. 1, we consider a mobile edge network $N=(V,C,E)$ that is comprised of a set of BSs and cloudlets, where V denotes the set of all BSs in the mobile edge network, C denotes the set of all cloudlets, and E denotes all direct links between two BSs or between a BS and a cloudlet. Suppose |V| and |E| denote

the number of BSs and links in N, respectively. |C| denotes the number of cloudlet in N. $v_i$ denotes the ith BS in N, $c_j$ denotes the jth cloudlet in N. For each BSs pair $(v_i,v_j)$ , let $l(v_i,v_j)$ be the hops of the shortest path between the two BSs and denote by $d(v_i,v_j)$ the average data transmission latency between the two BSs. If a cloudlet $c_j$ is co-located with the BS $v_i$ , there is a link $(v_i,c_j)$ in E. The transmission latency of $(v_i,c_j)$ is 0. Denoted by $v^{c_j}$ the BS that $c_j$ is co-located with.

As shown in Figs. 2 and 3, a collection of loosely coupled micro-services are structured to implements complex business capabilities through lightweight communication protocols. Let K denotes the number of function components required for a specific user. The K number of micro-services is denoted by $\text{MS}=\{{\text{ms}}_1,...,{\text{ms}}_m,...,{\text{ms}}_K\}$ . Because the process capability of a single micro-service is limited, a group of micro-service instances that deliver the same functionality are usually deployed. Suppose ${\text{MS}}_{\gamma }=\{{\text{ms}}_{\gamma }^1,...,{\text{ms}}_{\gamma }^n,...,{\text{ms}}_{\gamma }^{|{\mathrm{ms}}_{\gamma }|}\}$ denotes the set of instance for ${\text{ms}}_{\gamma }$ . ${\text{ms}}_{\gamma }^n$ denotes the nth instance of ${\text{ms}}_{\gamma }$ . The request processing rate of the micro-service instance ${\text{ms}}_{\gamma }^n$ is denoted by ${\mu }_{{\mathrm{ms}}_{\gamma }}^n$ . The current request arrival rate of ${\text{ms}}_{\gamma }^n$ is denoted by ${\lambda }_{{\mathrm{ms}}_{\gamma }}^n$ . Micro-services are provided by the lightweight containers in the cloudlets. $c_{{\mathrm{ms}}_{\gamma }}^n$ denotes the cloudlet that the micro-service instance ${\text{ms}}_{\gamma }^n$ is deployed on.

Notations

Graph: Fig. 2 Intruder detection application developed by micro-service architecture

Graph: Fig. 3 Example of micro-service mashup

The latency-aware micro-service mashup in mobile edge computing environment in a mobile edge network $N=(V,C,E)$ is defined as follows. Given the location of all instance in MS, the functional requirements of a specific mashup request, the access point ap of the requestor, the service request arrival rate ${\lambda }_{\mathrm{in}}$ of the requestor, and the network latency, the problem is to select K micro-service instances such that the network resource consumption is minimized, subject to that the functional requirements and the average service access latency constraint ${\mathrm{\Delta }}_{\mathrm{latency}}$ are satisfied, where the service access latency consists of communication latency, execution, and queuing time.

Note that mashup request is different from service request. We take the intruder detection application as an example. The requestor firstly submits a mashup request. After the mashup request has been received, micro-services are structured based on the functional and non-functional requirements. Then, photos are taken periodically, and each photo is submitted as a service request for processing.

In other words, the problem is to identify K micro-service instances from all candidates such that the average service access latency constraint is satisfied and the network resource consumption is minimized.

An example is shown in Fig. 3. We add a micro-service ${\text{MS}}_0$ as the entrance portal and a micro-service ${\text{MS}}_{K+1}$ as the exit portal. There is only one instance ${\text{MS}}_0^1$ for ${\text{MS}}_0$ , and only one instance ${\text{MS}}_{K+1}^1$ for ${\text{MS}}_{K+1}$ .

We introduce some definitions in the following.

The service access latency consists of the communication latency, the execution time, and the queuing time.

The execution time and queuing time is often analyzed using queuing models. This paper employs M/M/1 queue model which assumes the exponential service time and the Poisson request arrival. According to M/M/1 queue model, the average processing latency (including execution time, and queuing time) of ${\text{ms}}_{\gamma }^n$ is calculated as follows:

Graph

${\mu }_{{\mathrm{ms}}_{\gamma }}^n$ denotes the processing rate, ${\lambda }_{{\mathrm{ms}}_{\gamma }}^n$ denotes the current request arrival rate, and ${\lambda }_{\mathrm{in}}^{\gamma }$ denotes the additional request arrival rate if ${\text{ms}}_{\gamma }^n$ is selected.

We define a binary variable $X_{\gamma }^n$ for micro-service mashup by the following:

2 $$\begin{array}{c}\hfill X_{\gamma }^n=\left\{\begin{array}{cc}1,\hfill & \text{if micro service}{\text{ms}}_{\gamma }^n\text{is selected}\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array},.\right)\end{array}$$

Graph

Therefore, the average execution and queuing time are calculated by the following:

3 $$\begin{array}{c}\hfill t_e=\sum _{n=1}^K\frac{1}{{\mu }_{{\mathrm{ms}}_{\gamma }}^n-\left({\lambda }_{{\mathrm{ms}}_{\gamma }}^n,+,{\lambda }_{\mathrm{in}}^{\gamma }\right)}.\end{array}$$

Graph

The communication latency consists of the latency from the end user to the location of the first micro-service instance, the total latency between micro-service for request processing, the latency from the location of the last micro-service instance to the requestor. Suppose the average data size per service request is ${\text{ds}}_{\mathrm{in}}$ . The data size becomes ${\text{ds}}_{\mathrm{in}}^{\gamma }$ after having been processed by ${\mathrm{ms}}_{\gamma }$ . In real-world, the functional relation between the input data size and the output data size can be obtained through experiments.

The average latency between micro-services for request processing is calculated by the following:

4 $$\begin{array}{c}\hfill t_m=\sum _{\gamma =1}^{K-1}\sum _{m=1}^{|{\mathrm{ms}}_{\gamma }|}\sum _{u=1}^{|{\mathrm{ms}}_{\gamma +1}|}d\left(c_{{\mathrm{ms}}_{\gamma }}^m,,,c_{{\mathrm{ms}}_{\gamma +1}}^u\right){\text{ds}}_{\mathrm{in}}^{\gamma }{X}_{\gamma }^m{X}_{\gamma +1}^u.\end{array}$$

Graph

The average latency from the end user to the location of the first micro-service instance is calculated by the following:

5 $$\begin{array}{c}\hfill t_s=\sum _{m=1}^{|{\mathrm{ms}}_1|}d\left(v_{\mathrm{ap}},,,c_{{\mathrm{ms}}_1}^m\right){\text{ds}}_{\mathrm{in}}{X}_1^m+{\text{ds}}_{\mathrm{in}}/W{log}_2\left(1,+,\frac{\text{TP}\ast H}{{\delta }^2+I}\right).\end{array}$$

Graph

The second part denotes the latency from the user to the serving BS [[42]]. H denotes the channel gain between the user and the BS. TP denotes the transmission power. W denotes the channel bandwidth. ${\delta }^2$ denotes the noise power. I denotes the inter-cell interference power.

The latency from the location of the last micro-service instance to the end user is calculated by the following:

6 $$\begin{array}{c}\hfill t_f=\sum _{m=1}^{|{\mathrm{ms}}_1|}d\left(v_{\mathrm{ap}},,,c_{{\mathrm{ms}}_K}^1\right){\text{ds}}_{\mathrm{in}}^K{X}_K^m+{\text{ds}}_{\mathrm{in}}^K/W{log}_2\left(1,+,\frac{\text{TP}\ast H}{{\delta }^2+I}\right).\end{array}$$

Graph

Therefore, the communication latency is calculated by the following:

7 $$\begin{array}{c}\hfill t_c=t_m+t_s+t_f.\end{array}$$

Graph

Based on the above-mentioned discussion, the average access latency is calculated as follows:

8 $$\begin{array}{c}\hfill t=t_e+t_c.\end{array}$$

Graph

When the source node and the destination node are further from each other, the network packet will be transferred by more links. Thus, more network resource would be consumed. We multiply the hops in application packet transfer by the data size to evaluate the network resource consumption.

The hops in application packet transfer consist of the hops from the end user to the location of the first micro-service instance, the total hops between micro-services for request processing, the hops from the location of the last micro-service instance to the requestor.

The network resource consumption for request processing is calculated by the following:

9 $$\begin{array}{c}\hfill {\text{ns}}_m=\sum _{\gamma =1}^{K-1}\sum _{m=1}^{|{\mathrm{ms}}_{\gamma }|}\sum _{u=1}^{|{\mathrm{ms}}_{\gamma +1}|}l\left(c_{{\mathrm{ms}}_{\gamma }}^m,,,c_{{\mathrm{ms}}_{\gamma +1}}^u\right){\text{ds}}_{\mathrm{in}}^{\gamma }{X}_{\gamma }^m{X}_{\gamma +1}^u.\end{array}$$

Graph

The hops from the end user to the location of the first micro-service instance are calculated by the following:

10 $$\begin{array}{c}\hfill {\text{ns}}_s=\sum _{m=1}{\text{ds}}_{\mathrm{in}}\ast \left(l,\left(v_{\mathrm{ap}},,,{\text{ms}}_{\gamma }^m\right),X_1^m,+,1\right).\end{array}$$

Graph

The hops from the location of the last micro-service instance to the end user are calculated by the following:

11 $$\begin{array}{c}\hfill {\text{ns}}_f=\sum _{m=1}{\text{ds}}_{\mathrm{in}}^K\ast \left(l,\left(v_{\mathit{ap}},,,{\text{ms}}_K^u\right),X_K^m,+,1\right).\end{array}$$

Graph

Based on the above-mentioned discussion, the service access latency is calculated as follows:

12 $$\begin{array}{c}\hfill {\text{ns}}_c={\text{ns}}_m+{\text{ns}}_s+{\text{ns}}_f.\end{array}$$

Graph

By summering all above discussion, we can formulate this latency-aware micro-service mashup in mobile edge computing environment as an integer nonlinear programming as:

13 $$\begin{array}{cc}& min{\text{ns}}_c.\hfill \end{array}$$

Graph

14 $$\begin{array}{cc}& \text{subject to:}t\le {\mathrm{\Delta }}_{\mathrm{latency}},\sum _{n=1}^{|{\mathrm{ms}}_{\gamma }|}{X}_{\gamma }^n=1,\sum _{\gamma =1}^K\sum _{n=1}^{|{\mathrm{ms}}_{\gamma }|}{X}_{\gamma }^n=K.\hfill \end{array}$$

Graph

where the target is to minimize the network resource consumption, the first constraint is to ensure that the latency constraint is satisfied, and the last two constraints are to ensure that the functional requirements are satisfied.

The latency-aware micro-service mashup problem in mobile edge computing environment is NP-Hard.

We reduce the delay constrained least cost (DCLC) problem to the latency-aware micro-service mashup problem in mobile edge computing environment.

The idea is that even if a simpler case of the latency-aware micro-service mashup problem in mobile edge computing environment can be solved, then it can be used to solve the delay constrained least cost problem.

We now construct a new directed graph $\tilde{G}=(\tilde{V},\tilde{E},{\tilde{\nu }}_0^1,{\tilde{\nu }}_{K+1}^1)$ . ${\tilde{\nu }}_0^1$ denotes the application entrance portal, and ${\tilde{\nu }}_{K+1}^1$ denotes the application exit porta. $\tilde{V}$ consists of all related micro-service instances. ${\tilde{\nu }}_{\gamma }^n$ denotes the node for $m{\tilde{s}}_{\gamma }^n$ . There are three types of edges in the graph. Micro-service connection edge connects two micro-service instances. There is a micro-service instance edge from ${\tilde{\nu }}_{\gamma }^n$ to ${\tilde{\nu }}_{\gamma +1}^u$ for $n\in [1,\left|{\text{ms}}_{\gamma }\right|]$ , $u\in [1,\left|{\text{ms}}_{\gamma +1}\right|]$ , and $\gamma \in [1,K-1]$ . The cost and the latency of an micro-service connection edge are defined by the following:

15 $$\begin{array}{cc}\hfill c\left({\tilde{\nu }}_{\gamma }^n,,,{\tilde{\nu }}_{\gamma +1}^u\right)=& {\text{ds}}_{\mathrm{in}}^{\gamma }\ast l\left(c_{{\mathrm{ms}}_{\gamma }}^n,,,c_{{\mathrm{ms}}_{\gamma +1}}^u\right).\hfill \end{array}$$

Graph

16 $$\begin{array}{cc}\hfill d\left({\tilde{\nu }}_{\gamma }^n,,,{\tilde{\nu }}_{\gamma +1}^u\right)=& t_{\gamma }^n+{\text{ds}}_{\mathrm{in}}^{\gamma }\ast d\left(c_{{\mathrm{ms}}_{\gamma }}^n,,,c_{{\mathrm{ms}}_{\gamma +1}}^u\right).\hfill \end{array}$$

Graph

There is an entrance edge from ${\tilde{\nu }}_0^1$ to ${\tilde{\nu }}_1^n$ for $n\in [1,\left|{\text{ms}}_1\right|]$ .The cost of an entrance edge is defined by the following:

17 $$\begin{array}{cc}\hfill c\left({\tilde{\nu }}_0^1,,,{\tilde{\nu }}_1^n\right)=& {\text{ds}}_{\mathrm{in}}^{\gamma }\ast \left(l,\left({\nu }_{\mathrm{ap}},,,c_{{\text{ms}}_1}^n\right),+,1\right).\hfill \end{array}$$

Graph

18 $$\begin{array}{cc}\hfill d\left({\tilde{\nu }}_0^1,,,{\tilde{\nu }}_1^n\right)=& {\text{ds}}_{\mathrm{in}}^{\gamma }\ast \left(d,\left({\nu }_{\mathrm{ap}},,,c_{{\text{ms}}_1}^n\right),+,t_s\right).\hfill \end{array}$$

Graph

There is an entrance edge from ${\tilde{\nu }}_K^n$ to ${\tilde{\nu }}_{K+1}^1$ for $n\in [1,\left|{\text{ms}}_K\right|]$ . The cost of an entrance edge is defined by the following:

19 $$\begin{array}{cc}\hfill c\left({\tilde{\nu }}_K^n,,,{\tilde{\nu }}_{K+1}^1\right)=& {\text{ds}}_{\mathrm{in}}^K\ast \left(l,\left(c_{{\mathrm{ms}}_K}^n,,,{\nu }_{\mathrm{ap}}\right),+,1\right)\hfill \end{array}$$

Graph

20 $$\begin{array}{cc}\hfill d\left({\tilde{\nu }}_K^n,,,{\tilde{\nu }}_{K+1}^1\right)=& t_K^n+{\text{ds}}_{\mathrm{in}}^K\ast \left(d,\left(c_{{\mathrm{ms}}_K}^n,,,{\nu }_{\mathrm{ap}}\right),+,t_f\right)\hfill \end{array}$$

Graph

Now, INLP1 can be transformed to:

21 $$\begin{array}{cc}& \underset{p\in P({\tilde{\nu }}_0^1,{\tilde{\nu }}_{K+1}^1))}{min}\sum _{e\in p}c(e)\hfill \end{array}$$

Graph

22 $$\begin{array}{cc}& \text{subject to}\sum _{e\in p}d(e)\le {\mathrm{\Delta }}_{\mathrm{latency}}\hfill \end{array}$$

Graph

where $P({\tilde{\nu }}_0^1,{\tilde{\nu }}_{K+1}^1)$ is the set of all paths from ${\tilde{\nu }}_0^1$ to ${\tilde{\nu }}_{K+1}^1$ .

It is easy to see that an algorithm for solving the latency-aware micro-service mashup problem in mobile edge computing environment can be used to solve the DCLC problem. The DCLC problem is a well-known NP-Hard problem [[43]]. Hence, it follows that the latency-aware micro-service mashup problem in mobile edge computing environment is NP-Hard. $\square$

For the NP-Hard problem, approximation algorithm [[44]] is a powerful tool to make a trade-off between the goodness of the approximation and the running time. An approach based on the approximation algorithm has been proposed in this paper to attack the NP-Hard problem.

We now devise an approximation approach for this special latency-aware dynamic micro-service mashup problem in mobile edge computing environment.

This approach is developed based upon the algorithm proposed in [41] by exploiting the characteristic of our problem.

$(1+\epsilon )$ -approximation algorithm. Assume $P_{\mathrm{OPT}}$ is the optimal path and OPT is the cost of the optimal path for INLP 2. An algorithm is a $(1+\epsilon )-$ approximation algorithm $(0<\epsilon <1)$ for INLP 2 if the algorithm generates a set of micro-services instances such that ${\sum }_{e\in p}c(e)\le (1+\epsilon )$ OPT and ${\sum }_{e\in p}d(e)\le {\mathrm{\Delta }}_{\mathrm{latency}}$ in a polynomial time.

Let $f_r(c)$ denotes the minimum latency for all paths from ${\tilde{\nu }}_0^1$ to the nodes in $\{{\tilde{\nu }}_{\gamma }^n,n=1\cdots \left|{\text{ms}}_{\gamma }\right|\}$ with the at most cost c. If we know the value of OPT, the process presented in Algorithm 1 can be employed to calculate the optimal path. Algorithm 1 is designed based upon a dynamic programming algorithm. However, OPT cannot be known in priori. The key idea is to obtain a value that is approximate to OPT and employs the value to calculate the optimal path by using Algorithm 1.

Before describing how to obtain a value that is approximate to OPT, we first give an important theorem.

Suppose $P_L$ and $P_R$ are two paths from ${\tilde{\nu }}_0^1$ to ${\tilde{\nu }}_{K+1}^1$ , where $P_L$ denotes the path with the minimum latency among all paths (from ${\tilde{\nu }}_0^1$ to ${\tilde{\nu }}_{K+1}^1$ ) with the at most cost $c(P_L),P_R$ denotes the path with the minimum latency among all paths (from ${\tilde{\nu }}_0^1$ to ${\tilde{\nu }}_{K+1}^1$ ) with the at most cost $c(P_R)$ . $d(P_L)>{\mathrm{\Delta }}_{\mathrm{latency}},d(P_R)\le {\mathrm{\Delta }}_{\mathrm{latency}}$ .

The cost of all micro-service instances in $P_R$ is $(1+ϵ)$ -approximation to OPT if $c(P_R)\le (1+ϵ)c(P_L)$ .

Since $d(P_R)\le {\mathrm{\Delta }}_{\mathrm{latency}}$ , we must have $\text{OPT}<c(P_R)$ . Otherwise, $P_R$ is the optimal solution for the problem. This is in contradiction with the assumption that $P_{\mathrm{OPT}}$ is the optimal solution.

In addition, $P_L$ is the path with the minimum latency among all paths (from ${\tilde{\nu }}_0^1$ to ${\tilde{\nu }}_{K+1}^1$ ) with the at most cost $c(P_L)$ , and $d(P_L)>{\mathrm{\Delta }}_{\mathrm{latency}}$ implies that $\text{OPT}>C(P_L)$ . Otherwise, $P_{\mathrm{OPT}}$ is the path with the minimum latency among all paths.

The above discussion implies that:

23 $$\begin{array}{c}\hfill c(P_L)<\text{OPT}<c(P_R)\end{array}$$

Graph

Based on (23) and the assumption that $c(P_L)<\text{OPT}<c(P_R)$ , we must have:

24 $$\begin{array}{cc}\hfill c(P_R)& \le (1+ϵ)c(P_L)\hfill \end{array}$$

Graph

25 $$\begin{array}{cc}& <(1+ϵ)\text{OPT}\hfill \end{array}$$

Graph

Now, we can prove that the cost of $P_R$ is $(1+\epsilon )-$ approximation to OPT. $\square$

According to Proposition 2, we can start with a range $[c_L,c_R]$ , and narrow down this range until the path $P_L$ with the minimum latency among all paths with the at most cost $c_L$ , and the path $P_R$ with the minimum latency among all paths with the at most cost $c_R$ satisfy $d(P_L)>{\mathrm{\Delta }}_{\mathrm{latency}},d(P_R)\le {\mathrm{\Delta }}_{\mathrm{latency}},c(P_R)\le (1+\epsilon )c(P_L).$

To compute the upper bound and the lower bound, we require an algorithm to decide whether a cost value $C_v$ satisfies $C_v<\text{OPT}$ or $\text{OPT}\le C_v(1+\epsilon )$ .

As we known, if we replace the cost of each edge by:

26 $$\begin{array}{c}\hfill c^{\prime }({\tilde{\nu }}_{\gamma }^n,{\tilde{\nu }}_{\gamma +1}^u)=\text{floor}\left({\displaystyle \frac{c\left({\tilde{\nu }}_{\gamma }^n,,,{\tilde{\nu }}_{\gamma +1}^u\right)}{ϵC_v/(K+1)}}\right)\ast {\displaystyle \frac{ϵC_v}{K+1}}\end{array}$$

Graph

The cost of each edge decreases at most $ϵC_v/(K+1)$ , and the cost of each feasible path decreases at most $ϵC_v$ .

Based on the discussion, we now scale the cost of each edge by the following:

27 $$\begin{array}{c}\hfill c^{\prime }({\tilde{\nu }}_{\gamma }^n,{\tilde{\nu }}_{\gamma +1}^u)=\text{floor}\left({\displaystyle \frac{c\left({\tilde{\nu }}_{\gamma }^n,,,{\tilde{\nu }}_{\gamma +1}^u\right)}{ϵC_v/(K+1)}}\right)\end{array}$$

Graph

Now, we can employ Algorithm 1 to calculate the optimal feasible path after the scaled cost is used. If the scaled cost of the optimal feasible path is smaller than $(K+1)/\epsilon$ , we have that the cost of the path is at most:

28 $$\begin{array}{c}\hfill {\displaystyle \frac{ϵC_v}{K+1}}{c}^{\prime }+ϵC_v<{\displaystyle \frac{ϵC_v}{K+1}}\ast {\displaystyle \frac{K+1}{ϵ}}+ϵC_v=C_v(1+ϵ)\end{array}$$

Graph

We have that $\text{OPT}<C_v(1+ϵ)$ .

If the scaled cost of the optimal feasible path is larger than or equal to, we have that the cost of the path is at most:

29 $$\begin{array}{c}\hfill {\displaystyle \frac{ϵC_v}{K+1}}{c}^{\prime }+ϵC_v>{\displaystyle \frac{ϵC_v}{K+1}}\ast {\displaystyle \frac{K+1}{ϵ}}+ϵC_v=C_v(1+ϵ)>C_v\end{array}$$

Graph

We have that $\text{OPT}>C_v$ . This process is illustrated in Algorithm 2.

Based on Algorithm 1 and Algorithm 2, we propose Algorithm 3 to calculate the optimal mashup strategy. In Algorithm 3, the ceil function returns the smallest integer that is larger than a particular number. The floor function returns the largest integer that is smaller than a particular number. Firstly, Algorithm 3 starts with a range $[c_L,c_R]$ . Then, by using Algorithm 2, Algorithm 3 narrows down this range until the path $P_L$ with the minimum latency among all paths with the at most cost $c_L$ , and the path $P_R$ with the minimum latency among all paths with the at most cost $c_R$ satisfy $d(P_L)>{\mathrm{\Delta }}_{\mathrm{latency}},d(P_R)\le {\mathrm{\Delta }}_{\mathrm{latency}},c(P_R)\le (1+\epsilon )c(P_L).$ Finally, Algorithm 1 is used by Algorithm 3 to find the optimal micro-services instances.

Graph

Graph

Graph

The worst-case time complexity of our proposed mashup approach is $O(({log}_2{log}_2(c_R/c_L)\ast {\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|)\ast (K+1)/ϵ)$ , where $c_L={\sum }_{\gamma =1}^{|K|-1}min\{c\left({\tilde{v}}_{\gamma }^n,,,{\tilde{v}}_{\gamma +1}^u\right),\forall n\forall u\}+min\{c\left({\tilde{v}}_0^1,,,{\tilde{v}}_1^n\right),\forall n\}+min\{c\left({\tilde{v}}_K^n,,,{\tilde{v}}_{K+1}^1\right),\forall n\}$ , and $c_R$ is equal to ${\sum }_{\gamma =1}^{|K|-1}max\{c\left({\tilde{v}}_{\gamma }^n,,,{\tilde{v}}_{\gamma +1}^u\right),\forall n\forall u\}+max\{c\left({\tilde{v}}_0^1,,,{\tilde{v}}_1^n\right),\forall n\}+max\{c\left({\tilde{v}}_K^n,,,{\tilde{v}}_{K+1}^1\right),\forall n\}$ .

The time complexity of Algorithm 1: Lines 3–16 uses O(OPT) iterations to search for the path. It requires ${\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|$ comparisons for calculate $f_{\gamma }$ . Therefore, the total complexity is $O(\text{OPT}\ast {\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|)$ .

The time complexity of Algorithm 2: The time complexity of lines 7–10 requires $O({\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|)$ operations at each iteration. Lines 6–12 uses $O((K+1)/ϵ)$ iterations of Algorithm B. Therefore, the total complexity is $O(({\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|)\ast (K+1)/ϵ)$ .

The time complexity of Algorithm 3:

The min value of $c_L$ is ${\sum }_{\gamma =1}^{|K|-1}min\{c\left({\tilde{v}}_{\gamma }^n,,,{\tilde{v}}_{\gamma +1}^u\right),\forall n\forall u\}+min\{c\left({\tilde{v}}_0^1,,,{\tilde{v}}_1^n\right),\forall n\}+min\{c\left({\tilde{v}}_K^n,,,{\tilde{v}}_{K+1}^1\right),\forall n\}$ , and the max value of $c_R$ is ${\sum }_{\gamma =1}^{|K|-1}max\{c\left({\tilde{v}}_{\gamma }^n,,,{\tilde{v}}_{\gamma +1}^u\right),\forall n\forall u\}+max\{c\left({\tilde{v}}_0^1,,,{\tilde{v}}_1^n\right),\forall n\}+max\{c\left({\tilde{v}}_K^n,,,{\tilde{v}}_{K+1}^1\right),\forall n\}$ .

Suppose the values of $c_L$ and $c_R$ become $c_L^x$ and $c_R^x$ after x iterations. If $\text{OPT}>\sqrt{c_L^x\ast c_R^x}$ , we obtain that:

30 $$\begin{array}{c}\hfill {\displaystyle \frac{c_R^{x+1}}{c_L^{x+1}}}={\left({\displaystyle \frac{c_R^x}{c_L^x}}\right)}^{1/2}.\end{array}$$

Graph

Else, we obtain that:

31 $$\begin{array}{c}\hfill {\displaystyle \frac{c_R^{x+1}}{c_L^{x+1}}}={\left({\displaystyle \frac{c_R^x}{c_L^x}}\right)}^{1/2}(1+ϵ).\end{array}$$

Graph

We can see that:

32 $$\begin{array}{c}\hfill {\left({\displaystyle \frac{c_R^x}{c_L^x}}\right)}^{1/2}\le {\left({\displaystyle \frac{c_R^x}{c_L^x}}\right)}^{1/2}(1+ϵ).\end{array}$$

Graph

Therefore, in the worst condition, CHECK( $C_v$ ) is always false. The value of ratio after x iterations becomes:

33 $$\begin{array}{c}\hfill {\displaystyle \frac{c_R^x}{c_L^x}}={\left({\displaystyle \frac{c_R}{c_L}},)\right)}^{1/2^x}{(1+ϵ)}^{(2^x-1)/2^{x-1}}.\end{array}$$

Graph

We can break the iteration until:

34 $$\begin{array}{cc}& {\left({\displaystyle \frac{c_R}{c_L}}\right)}^{1/2^x}{(1+ϵ)}^{(2^x-1)/2^{x-1}}\le (1+ϵ).\hfill \end{array}$$

Graph

35 $$\begin{array}{cc}& {\left({\displaystyle \frac{c_R}{c_L}}\right)}^{1/2^x}\le {(1+ϵ)}^{(2^{x-1}-1)/2^{x-1}}<2.\hfill \end{array}$$

Graph

36 $$\begin{array}{cc}& {log}_2{\left({\displaystyle \frac{c_R}{c_L}}\right)}^{1/2^x}<{log}_{2}2.\hfill \end{array}$$

Graph

37 $$\begin{array}{cc}& {\displaystyle \frac{1}{2^x}}{log}_2\left({\displaystyle \frac{c_R}{c_L}}\right)<1.\hfill \end{array}$$

Graph

38 $$\begin{array}{cc}& {log}_2\left({\displaystyle \frac{c_R}{c_L}}\right)<2^x.\hfill \end{array}$$

Graph

39 $$\begin{array}{cc}& x>{log}_2{log}_2\left({\displaystyle \frac{c_R}{c_L}}\right).\hfill \end{array}$$

Graph

Inequality (39) implies that the complexity of lines 1–10 is ${log}_2{log}_2((c_R)/(c_L))$ . Each CHECK requires $O(({\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|)\ast (K+1)/ϵ)$ . Therefore, the total complexity is $O({log}_2{log}_2((c_R)/(c_L))\ast ({\sum }_{\gamma }|{\text{ms}}_{\gamma }|\ast |{\text{ms}}_{\gamma +1}|)\ast (K+1)/ϵ),$ where $c_L={\sum }_{\gamma =1}^{|K|-1}min\{c\left({\tilde{v}}_{\gamma }^n,,,{\tilde{v}}_{\gamma +1}^u\right),\forall n\forall u\}+min\{c\left({\tilde{v}}_0^1,,,{\tilde{v}}_1^n\right),\forall n\}+min\{c\left({\tilde{v}}_K^n,,,{\tilde{v}}_{K+1}^1\right),\forall n\}$ , and $c_R$ is equal to ${\sum }_{\gamma =1}^{|K|-1}max\{c\left({\tilde{v}}_{\gamma }^n,,,{\tilde{v}}_{\gamma +1}^u\right),\forall n\forall u\}+max\{c\left({\tilde{v}}_0^1,,,{\tilde{v}}_1^n\right),\forall n\}+max\{c\left({\tilde{v}}_K^n,,,{\tilde{v}}_{K+1}^1\right),\forall n\}$ . $\square$

In order to evaluate the effectiveness of the micro-service mashup approach proposed in this paper, we carry out two sets of experiments. The first set of experiments evaluates the performance improvement by comparing our approach with the approaches that do not account for network topology and inter-service latency. The second set of experiments evaluates the efficiency of our micro-service mashup algorithm in different scale scenarios.

We have realized the approaches using Java language. Experiments are implemented on a computer with Intel (R) i7-5500U CPU 2.40 GHz, 8 GB of RAM and Windows 8.1 operating system professional version. Our experiments are designed based on the Shanghai Telecoms base station dataset. Figure 4 illustrates the BS locations of Shanghai Telecom. There are totally 3233 BSs, and we randomly select 10% among them as the locations of cloudlets. We deploy 40 micro-services on the cloudlets. The number of instance for each micro-service follows uniform distribution with the range [2, 10]. Those instances are uniformly distributed over the cloudlets. Each application requires 5 micro-services. There are 100 mashup requests. $ϵ$ is set to 0.1. The request process rate of each instance follows uniform distribution with the range [10/s, 20/s]. The current request arrival rate of each instance and the request rate of each user follow uniform distribution with the range [2/s, 5/s]. The average data size per request and the data size after processed are 1MB. The average latency of each link follows uniform distribution with the range [2 ms, 5 ms]. We propose the current minimal latency with an additional latency 10 ms as the latency constraint of each micro-service. The wireless channel gain is $H=127+30\ast logd$ and d is 128 m. The channel bandwidth W is 20 MHz, the noise power is $2\ast {10}^{-13}$ W, and the transmit power TP is 0.5 W. The inter-cell interference power I is 0 [[45]].

Graph: Fig. 4 BS locations of Shanghai Telecom

We use latency and network resource consumption as the metrics to measure the performance of our method in comparison with other mash up methods.

To illustrate the effectiveness of our latency-aware micro-service mashup approach (LMM), we compare our approach with the other three common approaches:

• DelayFirst: in this approach, only the service access latency delay is considered, and the algorithm always selects the service with minimum delay and disregards the network resource consumption.
• CostFirst: in this approach, only the network resource consumption is considered and disregards the latency.
• DACS: traditional service mashup approach; both the network resource consumption and latency are considered. However, the approach does not consider the inter-service latency.

We focus on the following three parameters in the experiments:

• Micro-service instance number. The number of instance of a micro-service.
• Latency constraint. The latency constraint of each application.
• Mashup request number. The number of mashup request that has been submitted.

In this section, we study the impact of mashup request number to the performance of our approach. We vary the value of mashup request number from 50 to 300 with a step value of 50. Figures 5 and 6 show the experiment results. Figure 5 illustrates the total cost under different values of mash request number. Figure 6 illustrates the total latency under different values of user number. Observing from Figs. 5 and 6, we draw the conclusion that: (1) The cost of DelayFirst is higher than other approaches. The costs of CostFirst and DACS are lower than LMM; (2) A smaller value of cost does not indicate a better performance. As shown in Fig. 6, CostFirst and DACS cannot ensure that the latency is within the service latency constraint; (3) Our approach has the smallest cost for all approaches that can satisfy the latency constraint. Because the process capability of a single micro-service is limited, a group of micro-service instances that deliver the same functionality are usually deployed. Because edge computing is a distributed computing platform, those micro-service instances are deployed over containers on different cloudlets, and there is a tremendous difference in latency and network resource utilization when the micro-services from different containers are selected in the service mashup process. In contrast to other existing solutions, we focus not only on efficient service mashup but also on the edge network topology in the micro-services instance selection. Therefore, our approach outperforms other approaches under all experimental settings.

Graph: Fig. 5 Total cost under different values of mashup request number

Graph: Fig. 6 Total latency under different values of mashup request number

In the experiments, we vary the additional latency from 5 to 30 with a step value of 5. Results are shown in Figs. 7 and 8. Figure 7 illustrates the cost under different values of latency constraint. Figure 8 illustrates the total latency under different values of latency constraint. Under all experimental settings, CostFirst and DACS obtain smaller cost values consistently. However, the values of total latency of those two approaches are larger than the latency constraint. That is because CostFirst only considers the cost, and DACS ignores the inter-micro-service latency. DelayFirst and LMM can ensure that the latency is always smaller than the latency constraint. LMM obtains smaller cost than DelayFirst. This observation indicates that our approach outperforms other approaches.

Graph: Fig. 7 Total cost under different values of additional latency

Graph: Fig. 8 Total latency under different values of additional latency

To study the impact of the number of micro-service instance to the performance of all approaches, we vary the value of the number of micro-service instance from 4 to 20 with a step value of 4. Figures 9 and 10 show the results. Figure 9 illustrates the cost of all approaches under different values of micro-service instance number. Figure 10 illustrates the total latency of all approaches under different values of micro-service instance number. Observing from Figs. 9 and 10, we draw the conclusion that: (1) the value of micro-service instance number impacts the cost and the total latency significantly. With the given number of micro-service instance increasing from 4 to 20, the cost and the total latency decrease quickly; (2) although the costs of CostFirst and DACS are higher than LMM, CostFirst and DACS cannot ensure that the latency is smaller than the service access latency constraint.

Graph: Fig. 9 Total cost under different values of instance number

Graph: Fig. 10 Total latency under different values of instance number

In this section, we study the impact of parameter $ϵ$ to the performance of our approach. We vary the value of $ϵ$ from 0.1 to 1 with a step value of 0.1. Figures 11, 12, and 13 show the experiment results. Figure 11 illustrates the total cost under different values of $ϵ$ . Figure 12 illustrates the total latency under different values of $ϵ$ . Optimal denotes the cost of the optimal solution. Figure 13 illustrates the total processing time of our approach under different values of $ϵ$ . Observing from Figs. 11, 12, and 13, we draw the conclusion that: (1) the value of $ϵ$ impacts the cost and the total latency significantly. The cost ascends quickly with the increasing of $ϵ$ . The total latency also ascends with the increase in the value of $ϵ$ , indicating that the performance can be improved by given a smaller value of $ϵ$ ; (2) the processing time of our approach decreases with the increasing of the value of $ϵ$ . A smaller value of $ϵ$ will provide better performance. There is negative correlation between the performance and the value of $ϵ$ . Those results indicate that we need to make a trade-off between the performance and the processing time.

Graph: Fig. 11 Total cost under different values of ϵ

Graph: Fig. 12 Total latency under different values of ϵ

Graph: Fig. 13 Total process time under different values of ϵ

With the advancement of software technique, complex IoT applications have been implemented as a set of lightweight and independent micro-services. Mobile edge computing has been introduced to those micro-services provision for shorter response time and smaller network pressure. One significant issue is how to produce the optimal collocation of suitable micro-service with the consideration of the network traffic.

In this paper, we focus on latency-aware micro-service mashup in mobile edge computing environment. To improve the performance of micro-service mashups, we take the inter-service latency and mobile edge network topology into consideration. This problem is formulated as integer nonlinear programming problem. We prove the NP-hardness of the problem by reducing it into a delay constrained least cost problem. An approximation approach is proposed to achieve the objective. The experimental results show that our latency-aware micro-service mashup approach can reduce the network resource consumption without violating the latency constraint. Our future research directions include considering the reliability problem and the user distribution-aware cloudlet placement in mobile edge computing environment.

I would like to express my gratitude to all those who helped me during the writing of this paper. The work presented in this study is supported by NSFC (61602054), NSFC (61571066).

The authors declare that they have no conflict of interest.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.