1 Resilience and Load Balancing in Fog Networks A Multi-Criteria Decision Analysis Approach

2025-04-30 0 0 2.39MB 20 页 10玖币

侵权投诉

Resilience and Load Balancing in Fog Networks:

A Multi-Criteria Decision Analysis Approach

Maad Ebrahim, Abdelhakim Haﬁd, Member, IEEE

Abstract—The advent of Cloud Computing enabled the pro-

liferation of IoT applications for smart environments. However,

the distance of these resources makes them unsuitable for delay-

sensitive applications. Hence, Fog Computing has emerged to

provide such capabilities in proximity to end devices through

distributed resources. These limited resources can collaborate to

serve distributed IoT application workﬂows using the concept

of stateless micro Fog service replicas, which provides resiliency

and maintains service availability in the face of failures. Load

balancing supports this collaboration by optimally assigning

workloads to appropriate services, i.e., distributing the load

among Fog nodes to fairly utilize compute and network re-

sources and minimize execution delays. In this paper, we propose

using ELECTRE, a Multi-Criteria Decision Analysis (MCDA)

approach, to efﬁciently balance the load in Fog environments.

We considered multiple objectives to make service selection

decisions, including compute and network load information.

We evaluate our approach in a realistic unbalanced topological

setup with heterogeneous workload requirements. To the best of

our knowledge, this is the ﬁrst time ELECTRE-based methods

are used to balance the load in Fog environments. Through

simulations, we compared the performance of our proposed

approach with traditional baseline methods that are commonly

used in practice, namely random, Round-Robin, nearest node,

and fastest service selection algorithms. In terms of the overall

system performance, our approach outperforms these methods

with up to 67% improvement.

Index Terms—Internet of Things, Cloud Computing, Fog Com-

puting, Edge Computing, Task Assignment, Service Selection,

Load Balancing, Optimization, MCDA, MCDM, ELECTRE.

I. INTRODUCTION

Fog Computing complements Cloud Computing to support

delay-sensitive IoT applications and to support mobility, geo-

distribution, and location awareness for these applications [1].

It saves the network bandwidth by reducing the trafﬁc between

end devices and the Cloud. In addition, it increases the

security and privacy of IoT applications by pre-processing and

encrypting data closer to its source [2]. Fog resources extend

from the edge of the network to the Cloud, i.e., cloud-to-

thing continuum, while Edge Computing limits these resources

within one-hop distance from those things [3] (see Fig. 1).

Hence, the Fog is more complex than the Edge; indeed, the

Edge can be viewed as a subcategory of the Fog as shown in

Fig. 1. Only modular applications, like workﬂow and bag-of-

tasks [4], allow for distributed Fog deployments as pipelined

workﬂows [5]. In contrast, monolithic applications cannot be

divided into multiple logical modules, and hence each shall

run as a single module in a single computing entity.

The authors are with the NRL, Department of Computer Science and

Operational Research, University of Montreal, Montreal, QC H3T-1J4, Canada

(e-mail: maad.ebrahim@umontreal.ca; ahaﬁd@iro.umontreal.ca).

Corresponding author: Maad Ebrahim (maad.ebrahim@umontreal.ca).

IoT Layer →

Edge Layer →

The Fog Layer

Cloud Layer →

Fig. 1. Cloud, Fog, and Edge Computing for IoT networks.

Many applications beneﬁt from Fog and Edge Computing to

support different types of IoT and mobile applications (see Fig.

2(a)). In Fig. 2(b), we present a Fog-based video surveillance

system, where the overall system performance is increased us-

ing pipelined application workﬂows. The ﬁrst module, i.e., on

the camera, performs simple subtractions between subsequent

frames to prevent sending identical frames of stationary views.

Edge and Fog modules perform object recognition and face

detection, respectively; this allows to only send and process

frames with humans and faces, respectively. Face recognition

will run on the Cloud, where faces are matched against

a privately-owned, or government-owned, database to track

people in restricted areas, suspects, or criminals. Immediate

feedback can be sent from each module in the application

workﬂow to change frame resolution and video Bitrate in the

sensing device when needed. For example, if a face is detected,

the camera is notiﬁed to send higher resolution frames to

increase the face recognition accuracy. However, the camera is

notiﬁed to decrease its resolution and Bitrate to save resources

when no objects are detected.

Estimating the volume of IoT workloads in advanced can

help building Fog environments, from scratch or by extending

existing infrastructures, to support IoT frameworks and their

applications [6]. However, it is almost impossible to accurately

estimate the expected volume of IoT workloads, a problem

that is imposed by the ever-growing number of IoT devices

and their applications. Therefore, optimal resource manage-

ment becomes critical to cope with these increasing demands,

arXiv:2210.13385v1 [cs.DC] 24 Oct 2022

Fog-based IoT Applications

Check for motion using

simple frame subtraction

Object Recognition

Face Detection

Face Recognition

Alarm Feedback

Update resolution & transmission rate

Low-latency applications: online gaming, video

conferencing/streaming, and video surveillance.

Geo-distributed applications: wireless sensor networks

and IoT-based smart farming.

Mobility-based applications: self-driving cars, smart

connected vehicles, and smart transportations.

Large-scale distributed control systems: Smart traffic

lights, smart cities, smart homes, and smart environments.

(a)

Fog-based IoT Applications

Check for motion using

simple frame subtraction

Object Recognition

Face Detection

Face Recognition

Alarm Feedback

Update resolution & transmission rate

Low-latency applications: online gaming, video

conferencing/streaming, and video surveillance.

Geo-distributed applications: wireless sensor networks

and IoT-based smart farming.

Mobility-based applications: self-driving cars, smart

connected vehicles, and smart transportations.

Large-scale distributed control systems: Smart traffic

lights, smart cities, smart homes, and smart environments.

(b)

Fig. 2. The beneﬁts of distributed computing for IoT and mobile applications. (a) Edge and Fog-based IoT applications. (b) Fog-based video surveillance.

which is done through optimal resource provisioning and

resource allocation schemes. In addition, optimally balancing

IoT workload among Fog resources helps achieving optimal

utilization of existing resources without requiring additional

hardware resources. Although, optimal load balancing is not

sufﬁcient when the total available hardware resources can not

provide enough computational power to serve all generated

IoT workloads at a given point in time.

Time-dependent data rate ﬂuctuations, uneven sensor dis-

tribution, and sensor mobility are usually the main reasons

for dynamic workloads in realistic IoT networks. Hence,

efﬁcient management of the network’s scarce resources is

essential to improve the performance of these systems. In

mobile networks, for example, this requires understanding the

behavior of network trafﬁc [7]. These dynamic environment

changes increase the complexity of efﬁcient workload distribu-

tion across Fog nodes [1]. This led researchers to oversimplify

their experiments using many pre-assumptions, which makes

their proposed solutions far from being applicable to realistic

environments [8]. For example, Kashani et al. [9] proposed

to use a three-layer hierarchical architecture, where the Cloud

resides at the top, Fog nodes in the middle, and IoT devices

at the bottom of the hierarchy. However, ﬂat mesh-like archi-

tectures and semi-hierarchical architectures are more realistic,

where Fog nodes can communicate with adjacent Fog nodes

without the concept of layers [8]. This can be achieved by

interconnecting Fog nodes with each other to allow ofﬂoading

workloads and trafﬁc among themselves, if needed, without

necessarily going through the Cloud.

Load balancing becomes critical to achieving resource efﬁ-

ciency by avoiding bottlenecks, underload, and overload situa-

tions [9]. For this to work, the total available resources should

be equal or greater than the requirements of all incoming

requests at a given time [10]. Hence, load balancing methods

try to maximize resource utilization while minimizing the

execution delay to satisfy the deadline requirements for delay-

sensitive tasks. In addition, to distribute workloads among

interconnected Fog nodes without migrating data and services,

these nodes must have redundant service replicas of the

requested modules [11].

Using redundant micro services for Fog-based applications

is essential, especially for resource-hungry real-time IoT appli-

cations that are used globally, such as trending online games,

Internet of Vehicles (IoV), and health monitoring systems.

Balancing the load of such heavy applications is critical, and

avoiding migration while serving the global population can be

only achieved through service replication. These Fog-based

micro services can be deployed globally as background ser-

vices, and only loaded when triggered, i.e., when requested by

an IoT application. Hence, the compute resources of those Fog

nodes will only be consumed while serving these workloads. If

workloads of some applications are less frequent in a speciﬁc

region, their corresponding micro-services that are deployed

in the Fog nodes in that region will be idle most of the time,

hence saving their compute resources.

Considering redundant micro Fog services with resource-

demanding real-time applications saves compute and network

resources from the overhead of service and data migration. Mi-

gration overhead is a heavy burden in Fog networks, especially

the overhead of transmission, allocation, and security of the

migrated services and their associated data [12]. In addition,

redundancy allows performing load balancing through Fog

service selection decisions, where a Fog service in a given

Fog node is selected to serve a given request. Hence, an up-to-

date directory of available services in every available Fog node

must be presented for the node that performs load balancing.

Such directory represents a virtual sub-network, i.e., local view

of the network, for every workload, where multiple Fog nodes

host the required service. Hence, the goal of the load balancing

algorithm is to select one of these Fog nodes to serve this

workload.

Service selection decisions depend on whether Fog modules

need cached data to process IoT requests, a concept referred to

as the state of the ﬂow of requests [13]. For stateless requests,

where cached data is not needed, incoming requests can be

ofﬂoaded to other service replicas without migration [13].

However, migration is needed for stateful, i.e., not stateless,

requests during the ofﬂoading process. Hence, to be able to

use service selection decisions to balance the load between

redundant micro Fog services while avoiding migration, work-

loads/requests must be assumed stateless, i.e., serverless. All

these assumptions are common in Fog environments, in fact,

considering stateless requests with redundant micro services

provides resilience for the system by maintaining service

availability in case of the failure of one or more Fog nodes in

the system [14].

Service selection decisions range from sophisticated load

balancing algorithms to simple random node selection [15].

Round-Robin (RR), nearest node, and fastest service selection

algorithms are other simple service selection methods. Using

the nearest node minimizes communication delay and energy

consumption in the network while using the fastest service

increases resource utilization and minimizes task processing

time. But, smarter algorithms simultaneously include workload

requirements, resource capabilities of computing nodes and

network links, and their current load information. Search-

based optimization algorithms can be used to balance the load

in such fully observable environments, where the network load

information is accessible to the load balancing algorithm.

Even though search-based algorithms may require higher

processing power than simple traditional approaches, they can

provide optimal, or near-optimal, results that can be used as a

baseline for other algorithms. Such algorithms can be deployed

in resource-rich network controllers, like SDN Controllers,

to provide service selection decisions for every generated

workload in the network. Therefore, we propose, in this

paper, a multi-objective search-based optimization approach

using an outranking Multi-Criteria Decision Analysis (MCDA)

algorithm called ELECTRE [16]. Our approach outperformed

traditional service selection algorithms, i.e., random, RR, near-

est node, and fastest service selection algorithms, to improve

the overall system performance. These traditional methods are

widely considered for practical Fog deployments because of

their simplicity while they are wrongly assumed to work well

in arbitrary Fog architectures.

We considered using an MCDA-based approach to balance

the load in Fog networks as it recently showed good perfor-

mances in similar tasks. For instance, these methods achieved

satisfactory performance in Mobile Crowd Computing systems

by making optimal resource selection decisions [17]. They

were also used to solve the service selection problem in Cloud

Computing environments [18]. In addition, these algorithms

were used to solve the service placement problem in Fog

Computing systems [19]. However, this is the ﬁrst time an

MCDA-based method is used to balance the load in Fog

systems to increase the overall Fog system performance.

We also provide in this work a generic network architecture

(see Fig. 3) with heterogeneous and unbalanced resources,

unbalanced load distribution, heterogeneous workload require-

ments, and a semi-hierarchical topology. It demonstrates the

need for load balancing in unbalanced Fog environments with

bottlenecks in computational and communication resources.

31 2

…

The Cloud

Fog Nodes

IoT Devices

Fig. 3. Generic Fog topology that emphasizes the need for load balancing.

Cloud

ActuatorSensor

Fog

Sensor Message Cloud Message

Fog Message

IoT Device

Loop

Fig. 4. A simple distributed IoT application workﬂow for the generic Fog

architecture, with a single application loop.

It is used to evaluate and compare the performance of our

approach with other service selection methods. This archi-

tecture avoids common simpliﬁcations in the literature, like

using hierarchical topologies with homogeneous resource and

workload requirements [8].

We then evaluate our approach in a more realistic experi-

mentation setup, which consists of multiple Fog nodes that are

randomly conﬁgured to simulate unbalanced resource and load

distribution. This larger setup conﬁrms both the performance

of our proposed approach, as well as the effectiveness of our

generic architecture in evaluating load balancing algorithms

in a simpliﬁed setup. In addition, we consider pipelined IoT

application workﬂows with computational modules that span

from the edge of the network to the Cloud (see Fig. 4).

This consideration avoids simplifying Fog problems into Edge

problems, where atomic IoT workloads are assigned to a single

computing entity that then sends feedback to the source IoT

device in response [20].

Hence, our main contributions can be summarized as the:

1) Design and implementation of a generic Fog architecture

that can be used to evaluate load balancing algorithms

away from the common simpliﬁcations in the literature.

2) Design and implementation of ELECTRE MCDA-based

load balancing algorithm that simultaneously considers

ﬁve selection criteria for its decision-making process.

3) Comparison of our proposed approach with traditional

methods that are commonly used in practice, which are

wrongly assumed to behave well in Fog environments.

4) Evaluation of our proposed load balancing solution in a

larger and more realistic setup to conﬁrm our ﬁndings.

The rest of the paper is organized as follows. Section II

presents a comparison between this work and existing work

in the literature. We introduce the ELECTRE algorithm in

Section III. Section IV presents the generic architecture used to

evaluate the proposed solution. Section V discusses the results

and the superior performance of our approach. Finally, Section

VI concludes the paper and presents some future directions for

the work.

II. RELATED WORK

Increasing the performance of IoT applications using Fog

resources can be done in two ways: (1) Constructing Fog

infrastructures that match the expected IoT trafﬁc in a system

[21]. (2) Allocating the resource of existing Fog infrastructures

to run IoT applications, and optimally distributing the load of

these applications to those resources in real-time. The ﬁrst

approach works for geographical regions that do not have

existing Fog infrastructures. The goal here is to ﬁnd the

optimal geographical locations of Fog nodes and to determine

their optimal resource requirements, i.e., CPU, memory, and

storage. In contrast, the second approach is more realistic as

we simply use the resources of existing hardware in the net-

work using optimal resource allocation and load distribution.

Before balancing the load in Fog environments, we need

to allocate Fog resources to distributed application modules.

This problem is also called the Fog placement problem, i.e.,

where to deploy service instances of IoT application modules.

The allocation of resources can be static or dynamic [22].

With static allocation, services do not migrate after their initial

deployments, while they can migrate during their lifetime

when dynamic allocation is used, which is more realistic in

dynamic mobile environments. In this case, efﬁcient mobility-

aware bandwidth reservation schemes are required to support

real-time IoT applications to preserve the valuable and scarce

bandwidth resources [23]. In addition, the overhead of mi-

grating services and their associated data can be unacceptable

in realistic deployments, which is often underestimated in the

literature [24]. It can be ignored only when migration is done

on micro Fog services that are not associated with user data.

Velasquez et al. [25], for example, reduced network latency

in Fog environments by optimizing service placement using

Integer Linear Programming (ILP). The optimization is based

on the popularity of each application, i.e., the number of

requests for each application. Then, they proposed a faster,

but near-optimal, heuristic solution based on the PageRank

algorithm. Their results showed that the heuristic approach was

better in balancing the load between Fog nodes with latency

values close to those of the ILP optimal solution. They used the

YAFS simulator [26] to test their solution and compared their

results with the First Fit (FF) placement algorithm. However,

they only solved the initial placement problem, i.e., static

resource allocation, in Fog environments, which cannot adapt

to dynamic environments with mobile nodes.

The Fog placement problem was also addressed using other

optimization algorithms, including Genetic algorithms [27],

Particle Swarm Optimization (PSO) [28], Gravitational Search

Algorithm (GSA) [29], Monte Carlo simulations [30], and

linear programming [31]. However, solving the Fog place-

ment problem does not necessarily provide resiliency in the

system and it might require service and data migration to

support mobile networks, which introduces a huge overhead

in dynamic systems. Ni et al. [32] compared static allocation

strategies with dynamic resource allocation in the Fog, where

they ﬁltered, classiﬁed, and grouped Fog nodes based on their

computing capabilities and their credibility. They considered

the price and time costs needed to complete the tasks along

with the credibility of end-users and Fog resources. However,

users or resources can have similar credibility, which can

cause sub-optimal behavior when breaking ties. In addition,

the dynamic nature of users’ and resources’ credibility can

cause deviations when calculating these values.

T´

ellez et al. [33] balanced the load between Fog nodes and

the Cloud by ﬁnding the optimal task allocation using an ILP-

based Tabu search method. They transformed multi-objective

optimization into a single-objective problem using the Pareto

Frontier method. They used a Task Scheduling Coordinator to

receive the tasks, schedule them, and assign them to suitable

computing nodes. Puthal et al. [34] used Breadth-First Search

to choose the best computing node in the network to improve

resource utilization and job response time in the system.

Xu et al. [35] balanced the load between Fog nodes based

on CPU, RAM, and bandwidth resources using static resource

allocation and dynamic service migration. Services were parti-

tioned to Fog nodes based on their type and predeﬁned request

generation rates. They compared their approach with FF, Best-

Fit (BF), FF-Decreasing (FFD), and BF-Decreasing (BFD).

Pereira et al. [36] proposed a priority-based load balancing

algorithm with two predeﬁned priority levels. They used a

centralized controller with a global knowledge of system

resources and workload requirements. The controller uses a

search table to select the best available computing node and

can create more nodes if needed. High priority tasks are sent

to the node with the lowest load and latency and the highest

number of cores and available memory. While low priority

tasks wait for nodes with low load or will be sent to the Cloud.

Pinto Neto et al. [11] compared their multi-tenant load

distribution algorithm with a delay-driven load distribution

strategy. They considered homogeneous Fog environments

with redundant services replicas. In their hierarchical archi-

tecture, a management node in the upper layer manages all

Fog nodes in the lower layer. It keeps a table for the resource

utilization in each Fog node as well as the communication

delay between adjacent nodes. When a Fog node receives a

task, it consults the management node to select the best node

to run this task based on its priority and delay requirements.

If all nodes are fully loaded, tasks are kept in a queue in

the management node. When a node becomes available, the

management node sends to it the task with the highest priority.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1ResilienceandLoadBalancinginFogNetworks:AMulti-CriteriaDecisionAnalysisApproachMaadEbrahim,AbdelhakimHad,Member,IEEEAbstractTheadventofCloudComputingenabledthepro-liferationofIoTapplicationsforsmartenvironments.However,thedistanceoftheseresourcesmakesthemunsuitablefordelay-sensitiveapplications.H...

展开>> 收起<<

1 Resilience and Load Balancing in Fog Networks A Multi-Criteria Decision Analysis Approach.pdf

共20页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Resilience and Load Balancing in Fog Networks A Multi-Criteria Decision Analysis Approach

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: