Zoltán Ádám Mann
Fog / edge computing arises through the increasing convergence and integration of several – traditionally distinct – disciplines: cloud computing on one hand, mobile computing and the Internet of Things (IoT) on the other hand, and advanced networking technologies as a glue between them. The main idea is to combine the strengths of these technologies to provide the necessary compute power to end‐user applications in a cost‐effective and secure way, with low latencies. Thus, fog / edge computing brings significant benefits to all of the underlying fields.
The notions of fog computing and edge computing are somewhat vaguely defined in the literature and have largely overlapping meaning [1]. In this chapter, we use the terms “fog computing” and “edge computing” interchangeably to refer to an architecture combining cloud computing with resources on the network edge and end‐user devices.
In cloud computing, there has been an evolution for several years from centralized architectures (one or few large data centers) toward increasing decentralization (several smaller data centers), which is still continuing, and fog / edge computing is a natural next step on this evolution trajectory [2]. Geographically distributed data centers lead to decreased latency for applications involving distributed data sources and sinks (e.g., users or sensors / actuators), since each data source / sink can be served by a nearby data center. Other benefits include improved fault tolerance as well as access to green energy sources of limited capacity [3].
From the point of view of mobile computing and IoT, the devices' limited computational capacity and limited battery life span are major challenges [4]. By offloading resource‐intensive compute tasks to more powerful nodes – such as servers in a data center or compute resources at the network edge – the range of possible applications can be widened significantly [5].
Optimization plays a crucial role in fog computing. For example, minimizing latency and energy consumption are just as important as maximizing security and reliability. Because of the high complexity of typical fog deployments (many different types of devices, with many different types of interactions) and their dynamic nature (mobile devices coming and going, devices or network connections failing permanently or temporarily etc.), it has become virtually impossible to ensure the best solution by design. Rather, the best solution should be determined using appropriate optimization techniques.
For this purpose, it is vital to define the relevant optimization problem(s) carefully and precisely. Indeed, the used problem formulation can have dramatic consequences on the practical applicability of the approach (e.g., omitting an important constraint may lead to solutions that cannot be applied in practice), as well as on its computational complexity.
Research on fog computing is still in its infancy. Some specific optimization problems have been defined, but in an ad hoc manner, independently from each other. As a result, it is difficult to compare or combine different approaches, because they usually address different variants or facets of the same problem and such subtle differences are often not apparent. (Earlier, we have witnessed a similar situation in cloud computing research as well [6, 7]). In addition, the quality and level of detail of existing problem formulations is quite heterogeneous.
Therefore, the aim of this chapter is to propose a generic conceptual framework for optimization problems in fog computing, based on consistent, well‐defined, and formalized notation for constraints and optimization objectives. Using a taxonomy of problem formulations, their relationships will become clear, also highlighting the gaps that necessitate further research. With this standard reference, we hope to contribute significantly to the maturation of this field of research.
The concept of fog computing was introduced by Cisco in 2012 as a means to extend cloud computing capabilities to the network edge, thus enabling more advanced applications [8]. Since then, an increasing number of research papers have been published on fog computing. This is exemplified by Figure 5.1, which shows the development of the number of papers and number of citations in fog computing, available in the Scopus database 1 on 7th December 2017. The used search query was “TITLE‐ABS‐KEY (“fog computing”)”, meaning that the phrase “fog computing” must occur in the title, the abstract, or the keywords of the paper.
Several of those papers describe technologies, architectures, and applications in a fog computing setting. However, the number of papers that deal with optimization in fog computing is also quickly rising. This is demonstrated by Figure 5.2, which shows the number of papers and number of citations obtained from the Scopus database on 7th December 2017, with the search query “TITLE‐ABS‐KEY (“fog computing”) AND TITLE‐ABS‐KEY (optim*)”, meaning that both the phrase “fog computing” and a word starting with “optim” (like optimal, optimized, or optimization) must occur in the title, the abstract, or the keywords of the paper.
Later in Section 5.9, when the essential characteristics of optimization problems in fog computing have already been defined, we will show how existing literature on optimization in fog computing can be classified.
Before delving into optimization problems and optimization approaches in fog computing, we describe some essential properties and notions of optimization in general.
An optimization problem is generally defined by the following [9]:
The problem then consists of finding appropriate values v 1, …, v n for the variables, such that all of the following holds:
A tuple (v 1, …, v n ) that satisfies (1) and (2) is called a solution of the problem. Thus, the goal is to find the solution with highest f value. At least, this is the case for maximization problems (as defined above). For a minimization problem, the goal is to find the solution with lowest f value, which is equivalent to finding the solution that maximizes the objective function f′= − f. In case of minimization problems, the objective function is often called cost function because it represents some – real or fictive – cost that needs to be minimized.
It is important to differentiate between a practical problem in engineering – e.g., minimization of power consumption in fog computing – and a formally defined optimization problem as outlined above. Deriving a formalized optimization problem from a practical problem is a nontrivial process, in which the variables, their domains, the constraints, and the objective function must be defined. In particular, there are usually many different ways to formalize a practical problem, leading to different formal optimization problems. Formalizing the problem is also a process of abstraction, in which some nonessential details are suppressed or some simplifying assumptions are made. Different formalizations of the same practical problem may exhibit different characteristics – for example, in terms of computational complexity. Therefore, the decisions made during problem formalization have a high impact. Problem formalization implies finding the most appropriate trade‐off between the generality and applicability of the formalized problem on one hand and its simplicity, clarity, and computational tractability on the other hand. This requires expertise and an iterative approach in which different ways of formalizing the problem are evaluated.
It should be mentioned that some papers jump from an informal problem description directly to devising some algorithm, without formally defining the problem first. This, however, has the disadvantage of prohibiting precise reasoning about the problem itself, e.g., about its computational complexity or its similarity with known other problems that could lead to the adoption of existing algorithms.
In the above definition of a general optimization problem, it was assumed that there is a single real‐valued objective function. However, in several practical problems, there are multiple objectives and the difficulty of the problem often lies in balancing between conflicting objectives. Let the objective functions be f 1, …, f q , where the aim is to maximize all of them. Since there is generally no solution that maximizes all of the objective functions simultaneously, some modification is necessary to obtain a well‐defined optimization problem. The most common approaches for that are the following [10]:
The fundamental motivation for the developments leading to fog computing are strongly related to some important quality attributes that should be improved. As explained earlier, fog computing can be seen as an extension of cloud computing towards the network edge, with the aim of providing lower latencies for latency‐critical applications within end devices. In other words, the optimization objective of minimizing latency is a major driving force behind fog computing [11].
On the other hand, from the point of view of end devices, fog computing promises significantly increased compute capabilities, enabling the execution of compute‐intensive tasks quickly and without major impact on energy consumption of the device. Therefore, optimization relating to execution time and energy consumption are also fundamental aspects of fog computing.
As we will see shortly in Section 5.6, several other optimization objectives are relevant to fog computing as well. Moreover, there are nontrivial interactions, sometimes also conflicts, among the different objectives. Hence, it is important to systematically study the different aspects of optimization in fog computing.
Before discussing individual optimization objectives, it is useful to define a generic framework for modeling different variants of the problem.
As shown in Figure 5.3, fog computing can be represented by a hierarchical three‐layer model [12]. Higher layers represent higher computational capacity, but at the same time also higher distance – and thus higher latency – from the end devices. On the highest layer is the cloud with its virtually unlimited, high‐performance, and cost‐ and energy‐efficient resources. The middle layer consists of a set of edge resources: machines offering compute services near the network edge, e.g. in base stations, routers, or small, geographically distributed data centers of telecommunication providers. The edge resources are all connected to the cloud. Finally, the lowest layer contains the end devices like mobile phones or IoT devices. Each end device is connected to one of the edge resources.
More formally, let c denote the cloud, E the set of edge resources, D e the set of end devices connected to edge resource e ∈ E , and the set of all end devices. The set of all resources is R={c} ∪ E ∪ D . Each resource r ∈ R is associated with a compute capacity a(r) ∈ ℝ + and a compute speed s(r) ∈ ℝ + . Moreover, each resource has some power consumption, which depends on its computational load. Specifically, the power consumption of resource r increases by w(r) ∈ ℝ + for every instruction to be carried out by r .
The set of links between resources is L={ce:e∈E}∪{ed:e∈E, d∈D e }. Each link l ∈ L is associated with a latency t(l) ∈ ℝ + and a bandwidth b(l) ∈ ℝ + . Moreover, transmitting one more byte of data over link l increases power consumption by w(l) ∈ ℝ + . Table 5.1 gives an overview of the used notation.
Table 5.1 Notation overview.
Notation | Explanation |
c | cloud |
E | set of edge resources |
D e | set of end devices connected to edge resource e ∈ E |
R | set of all resources |
a(r) | compute capacity of resource r ∈ R |
s(r) | compute speed of resource r ∈ R |
w(r) | marginal energy consumption of resource r ∈ R |
L | set of all links between resources |
t(l) | latency of link l ∈ L |
b(l) | bandwidth of link l ∈ L |
w(l) | marginal energy consumption of link l ∈ L |
As already mentioned, there are several metrics that need to be optimized in a fog computing system. Depending on the specific optimization problem variant, these metrics may indeed be optimization objectives, but they can also be used as constraints. For example, one problem variant may look at a real‐time application, in which overall execution time needs to be constrained by an upper bound, while energy consumption should be minimized. In another application, the finite battery capacity of a mobile device may be the bottleneck, so that energy consumption should be constrained by an upper bound, while execution time should be minimized.
Independently from the specific application – and hence, problem variant–some metrics play an important role in fog computing. These metrics are reviewed next.
There are several performance‐related metrics, like execution time, latency, and throughput. Generally, performance is related to the amount of time needed to accomplish a certain task. In a fog computing setting it is important to note that accomplishing a task usually involves multiple resources, often on different levels of the reference model of Figure 5.3. Hence, the completion time of the task may depend on the computation time of multiple resources, plus the time for data transfer between the resources. Some of these steps might be made in parallel (e.g., multiple devices can perform computations in parallel), whereas others must be made one after the other (e.g., the results of a computation can only be transferred once they have been computed). The total execution time depends on the critical path of compute and transfer steps. For instance, if a computation is partly done in an end device and partly offloaded from the end device to an edge resource, this may lead to a situation such as the one depicted in Figure 5.4, in which the total execution time is determined by the sum of multiple computation and data transfer steps.
Especially in the lower layers of the reference model of Figure 5.3, the economical use of the scarce resources is vital. This particularly applies to end devices, which typically have very limited CPU and memory capacity. Edge resources typically offer higher capacities, but also those capacities can be limited, given that edge resources may include machines like routers that do not offer exhaustive computational capabilities.
To some extent, CPU usage can be traded off with execution time, i.e., overbooking the CPU may lead to a situation where the application is still running, but more slowly. This may be acceptable for some applications, but not for time‐critical ones. Moreover, memory poses a harder constraint on resource consumption, since overbooking the memory may lead to more serious problems like application failure.
Beyond CPU and memory, also network bandwidth can be a scarce resource, both between end devices and edge resources and between edge resources and the cloud. Hence, also the use of network bandwidth may have to be either minimized or constrained by an upper bound.
It is important to note that, in contrast to performance, which is a global metric spanning multiple resources, resource consumption needs to be considered at each network node and link separately.
Energy can also be seen as a scarce resource, but it is quite different from the other resource types already considered. Energy is consumed by all resources as well as the network. Even idle resources and unused network elements consume energy, but their energy consumption increases with usage. Generally, assuming that the power consumption of a resource depends linearly on its CPU load is a good approximation [13]. It is important, though, to highlight the difference between power consumption and energy consumption, since energy consumption also depends on the amount of time during which power is consumed. Thus, it is, for instance, beneficial in terms of overall energy consumption to move a compute task from one resource to a significantly faster one, even if the faster machine has slightly higher power consumption.
Energy consumption is important on each layer of the fog, but in different ways. For end devices, battery power is often a bottleneck, and thus preserving it as much as possible is a primary concern. Edge resources are typically not battery‐powered; hence, their energy consumption is less important. For the cloud, energy consumption is again very important, but because of its financial implications: electric power is a major cost driver in cloud data centers. Finally, also the overall energy consumption of the whole fog system is important because of its environmental impact.
As already mentioned, energy consumption has implications on financial costs. But also other aspects influence costs. For example, the use of the cloud or edge infrastructure may incur costs. These costs can be fixed or usage‐based, or some combination thereof. Similarly, the use of the network for transferring data may incur costs.
All aspects covered so far are easily quantifiable. However, they are not sufficient to guarantee a high quality of experience for users. For this, quality attributes like reliability [14], security [12], and privacy [16] also need to be taken into account, which are harder to quantify.
Traditionally, such quality attributes are not captured by optimization problems, but, rather, addressed with appropriate architectural or technical solutions. For instance, reliability may be achieved by creating redundancy in the architecture, security may be achieved by using appropriate cryptographic techniques for encryption, while privacy may be achieved by applying anonymization of personal data. Nevertheless, there are several ways to address quality attributes during optimization of a fog system, as shown by the following representative examples:
It is important to note that the above optimization objectives relating to quality attributes typically conflict with other optimization objectives relating to costs, performance, etc. For example, increasing redundancy may be beneficial for improving reliability but at the same time it can lead to higher costs. Similarly, preferring service providers with high reputation is advantageous from the point of view of security, but may also lead to higher costs. Constraining co‐location options may improve privacy, but may lead to worse performance or higher energy consumption, and so on. This is one of the main reasons why it is beneficial to include also quality attributes in optimization problems, because this enables explicit reasoning about the optimal trade‐off between the conflicting objectives.
Optimization problems in fog computing can be classified according to which layer(s) of the three‐layer fog model (cf. Figure 5.3) is/are involved.
In principle, it is possible that only one layer is involved. This, however, is typically not regarded as fog computing. For example, if only the cloud layer is involved, then we have a pure cloud optimization problem. Likewise, if only end devices are involved, then the problem would not be in the realm of fog computing, but rather – depending on the kinds of devices and their interconnections – in mobile computing, IoT, wireless sensor networks etc.
Therefore, real fog computing problems involve at least two layers. This consideration leads to the following classification of optimization problems in fog computing:
In each of the fog layers, optimization may target the distribution of data, code, tasks, or a combination of these. In data‐related optimization, decisions have to be made about which pieces of data are stored and processed where in the fog architecture. In code‐related optimization, program code can be deployed on multiple resources and the goal is to find the optimal placement of the program code. Finally, in task‐related optimization, the aim is to find the optimal split of tasks among multiple resources.
Finally, it should be noted that the distributed nature of fog computing systems may make it necessary to perform optimization in a distributed fashion. Ideally, the locally optimal decisions of the participating autonomous resources should lead to a globally optimal behavior [20].
Just like cloud computing, fog computing is characterized by the provision and consumption of services. By looking at the different optimization opportunities at the different stages of the service life cycle, one can differentiate between the following options:
As can be seen, run‐time optimization plays a very important role in the optimization of fog computing systems. This has some important consequences. First, the time available for executing an optimization algorithm during run time is seriously limited, thus the adopted optimization algorithms have to be fast. Second, run‐time optimization is usually not about laying out a system from scratch, but rather, about adapting an existing setup. This implies, in particular, that the costs associated with changes to the system have to be taken into account.
The different aspects of optimization covered so far can form the basis to devise a taxonomy of optimization problems in fog computing. In the following, we illustrate this by means of classifying some representative publications taken from the literature along the presented dimensions.
As a first example, Table 5.2 shows the classification of the work of Do et al. [21]. This paper considers a video streaming service, consisting of a central cloud data center and a huge number of geographically distributed edge resources (called fog computing nodes or FCNs in the paper), which are to provide end devices with streaming video. The aim is to determine the data rate of video streaming for each edge resource, taking into account the different utility provided by different data rates at different edge resources, data center energy consumption, and the workload capacity of the data center. The paper proposes a distributed iterative improvement algorithm inspired by the ADMM (Alternating Direction Method of Multipliers) method.
Table 5.2 Classification of the work of Do et al. [21] according to the presented dimensions.
Paper: | Do et al.: A proximal algorithm for joint resource allocation and minimizing carbon footprint in geo‐distributed fog computing [21] |
Context / domain: | Video‐streaming service with a central cloud serving distributed edge resources which, in turn, serve end devices |
Considered metrics: |
|
Considered layer / resources: |
|
Phase in life cycle: | Design / deployment time |
Optimization algorithm: | Distributed iterative improvement |
As another example, Table 5.3 shows the classification of the work of Sardellitti et al. [22] according to the presented dimensions. That paper considers the computation offloading problem in a mobile edge computing (MEC) setting, where some mobile end devices offload some compute tasks to a nearby edge resource. For each compute task of each end device, it can be decided whether or not it should be offloaded, and in case of offloading, which radio channel should be used for the communication. The optimization problem is formed in terms of energy consumption and latency. The paper first formulates the problem for a single end device, which can be solved explicitly in closed form. However, for several end devices with potentially interfering communication, the problem becomes much tougher (in particular, nonconvex), which the authors solved by means of an appropriate heuristic.
Table 5.3 Classification of the work of Sardellitti et al. [22] according to the presented dimensions.
Paper: | Sardellitti et al.: Joint optimization of radio and computational resources for multicell mobile‐edge computing [22] |
Context / domain: | Computation offloading from mobile end devices to an edge resource |
Considered metrics: |
|
Considered layer / resources: |
|
Phase in life cycle: | Run time |
Optimization algorithm: | Iterative heuristic using successive convex approximation |
Finally, Table 5.4 describes the work of Mushunuri et al. [23], which addresses the problem of finding the optimal work distribution among cooperating robots. The robots (end devices) offload their compute tasks to a server (edge resource), which distributes it among the end devices and itself. It is assumed that compute tasks can be split arbitrarily. The optimization, carried out at run time by the edge resource, takes into account the communication costs, battery status, and compute capacities of the devices, and uses an off‐the‐shelf nonlinear optimization package.
Table 5.4 Classification of the work of Mushunuri et al. [23] according to the presented dimensions.
Paper: | Mushunuri et al.: Resource optimization in fog enabled IoT deployments [23] |
Context / domain: | Cooperating mobile robots sharing compute tasks |
Considered metrics: |
|
Considered layer / resources: |
|
Phase in life cycle: | Run time |
Optimization algorithm: | Nonlinear optimization with the COBYLA (Constrained Optimization by Linear Approximations) algorithm within the NLOpt library |
As can be seen from these three examples that cover different optimization problems within fog computing, the presented aspects can be applied successfully to classify the approaches from the literature and capture the characteristics that are relevant for optimization.
The three examples presented in Section 5.9 show that the optimization techniques adopted in fog computing optimization problems are quite heterogeneous. The following characteristics seem to be quite common, though:
In the future, with the maturation of the field, a consolidation of the used methods may take place. However, since the considered problem variants are also manifold, we expect the field to continue to require several different types of algorithmic techniques, including exact algorithms, heuristics, as well as hybrid approaches [24].
Fog computing is still in its early days, with optimization taking an ever more important role in it. Accordingly, there are several areas where significant future research is needed:
In this chapter, we have presented a review of optimization problems in fog computing. In particular, we have explained why optimization plays a vital role in fog computing and why it is important to define optimization problems unambiguously, preferably using a formal problem model. The most important aspects of optimization in fog computing have been reviewed according to multiple dimensions: the metrics that serve as optimization objectives or as constraints, the considered layers within the fog architecture, and the relevant phase in the service life cycle. These dimensions also lend themselves to form a taxonomy, which can be used to classify existing or future problem variants.
We have also argued that there are several important directions for future research, including the improved handling of multiple optimization objectives, the co‐optimization of multiple technical aspects, better understanding of which algorithmic techniques work best for which problem variant, and devising disciplined evaluation methodologies.
The work of Z. Á. Mann has been supported by the Hungarian Scientific Research Fund (Grant Nr. OTKA 108947) and the European Union's Horizon 2020 research and innovation program under grant 731678 (RestAssured).