Hernan Humberto

Alvarez Valera

MENAUD Jean Marc

Professeur, Rapporteur Imt Atlantique

Olivier Barais

Patricia Stolf

Comodin Comodin

Marc Dalmau

Philippe Roose

Ruth Valera Calderón

Sara Calderón

Tania Barrientos

A Dennis Barrios

Raquel Patinio

A Karito Machaca

José Manuel Negrete

Patrick Etcheverry

An energy saving perspective for distributed environments: Deployment, scheduling and simulation with multidimensional entities for Software and Hardware

Keywords:

Nowadays, strong economic growth and extreme weather conditions increased global electricity demand by more than 6% in 2021 after the COVID pandemic. The fast recovery regarding this demand rapidly increased electricity consumption. Even though renewable sources present a significant growth, electricity production from both coal and gas sources has reached a historical level.

On the other hand, the consumption of energy by the digital technology sector depends on its growth and its degree of energy efficiency. On this matter, although devices at all deployment levels are energy efficient today, their massive use means that global energy consumption continues to grow.

All these data show the need to use the energy of these devices wisely. For that reason, this thesis work addresses the dynamic (re)deployment of software components (containers or virtual machines) and their data to save energy. To this extent, we designed and developed intelligent distributed scheduling algorithms to decrease global power consumption while preserving the applications' quality of service.

Such algorithms execute migrations and duplications procedures considering the natural relation between hardware components' load/features and power consumption. For that, they implement a novel manner of decentralized negotiations based on a distributed middleware we created (Kaligreen) and multidimensional data structures.

To operate and assess the algorithms above, appropriate tools regarding hardware and software solutions are essential. Here, our choice was to develop our own simulation tool called: PISCO.

PISCO is a versatile and straightforward simulator that allows users to concentrate only on their scheduling strategies. It enables network topologies to be abstracted as data structures whose elements are devices indexed by one or more criteria. Additionally, it mimics the execution of microservices by allocating resources according to various scheduling heuristics.

We have used PISCO to implement, run and test our scheduling algorithms.

Nowadays, strong economic growth and extreme weather conditions increased global electricity demand by more than 6% in 2021 after the COVID pandemic [START_REF]IEA. Global changes in electricity generation[END_REF].

The fast recovery regarding this demand rapidly increased electricity consumption.

Even though renewable sources present a significant growth, electricity production from both coal and gas sources has reached historic level [START_REF]Electricity Market Report[END_REF]. Some difficulties concerning this subject have been pointed out. For instance, MD Staff argued that the emissions from electricity need to decline by 55% by 2030 to meet Zero-Emissions by 2050. However, in the absence of major policy action, those emissions are set to remain around the same level for the next three years(2022-2025). Among these significant changes, the world needs massive transformations for the electricity sector to fulfill its critical role in decarbonizing the broader energy system [165].

On the other hand, the consumption of energy by the digital technology sector depends on its growth and its degree of energy efficiency. On this matter, a division regarding three categories is highlighted [START_REF] Strempel | EIT Digital presents report on Digital Technologies and the Green Economy[END_REF]. First, personal devices (phones, computers, tablets) correspond to the primary source of energy use, with approximate calculations between 38% [START_REF] Van Heddeghem | Trends in worldwide ICT electricity consumption from 2007 to 2012[END_REF] and 50% [START_REF] Andrae | Projecting the chiaroscuro of the electricity use of communication and computing from 2018 to 2030[END_REF]. Next are data centers (servers, data, computing units) with consumption values of 1.1-1.4% [START_REF]IEA. Data Centres and Data Transmission Networks[END_REF]. Finally, communication networks (wireless, data transport).

The afore-mentioned subdivisions had an annual increase surpassing the growth of worldwide electricity consumption during the period comprehending from 2007 to 2012: Personal devices 10%, data centers 5%, and communication networks 4% [START_REF] Van Heddeghem | Trends in worldwide ICT electricity consumption from 2007 to 2012[END_REF].

All these data show the need to use the energy of these devices wisely. For that reason, this thesis work addresses the dynamic (re)deployment of software components (containers or virtual machines) and their data to save energy. To this extent, we designed and developed intelligent distributed scheduling algorithms to decrease global power consumption while preserving the applications' quality of service.

Such algorithms execute migrations and duplications procedures considering the natural relation between hardware components' load/features and power consumption. For that, they implement a novel manner of decentralized negotiations Chapter 1

Introduction

based on a distributed middleware we created (Kaligreen) and multidimensional data structures.

In order to operate and assess the algorithms above, appropriate tools regarding hardware and software solutions are essential. For example, infrastructures customized with specially designed middlewares (Kalimucho [START_REF] Da | Kalimucho: Middleware for Mobile Applications[END_REF], Kubernetes[136], etc.), measurement devices (wattmeters or uninterruptible power supply (UPS)), among others.

Because these technologies were unavailable to us and the proven effectiveness of power formulas (explanation in chapter 2), we introduced our own simulation tool called: PISCO.

Regarding the formulas, we have studied, adapted existing approaches, and proposed (if concerned) our own mathematical models to describe the energy consumption of essential hardware components (CPU, RAM, NIC, and storage device). For the CPU and the RAM, we have selected and adapted already tested formulas to detail their workload, power state, and power consumption. Then, we have proposed and tested our own energy consumption models for the storage device and the NIC. It is relevant to indicate that each model's parameters' values can be collected from different GNU/Linux interfaces (such as APIs, specialized programs, and others).

PISCO allows the (re)deployment of software components (executing processes) as well as their connections in the network's nodes. Additionally, it calculates hardware components' energy consumption based on their workload over time extent. This load can be evaluated taking into account as many hardware components as defined.

The strength of our simulator consists of its versatility and simplicity. It enables network topologies to be abstracted as data structures whose elements are devices indexed by one or more criteria. Additionally, it mimics the execution of microservices by allocating resources according to various scheduling heuristics. For that reason, we have used our simulator to implement, run and test our scheduling algorithms.

Thesis Methodology

This thesis work seeks to create and execute distributed tools and algorithms to save energy while maintaining the notion of QoS. For this, its chapters describe our proposal of a way forward toward intelligent distributed scheduling.

The first step on this path is to have energy information usable by any distributed middleware and simulation tools. Chapter 2 studies this problem. In it, we provide Thesis Methodology Section 1.1 energy formulas for four important hardware components (CPU, RAM, NIC, and storage) to describe the consumption of running applications in heterogeneous devices.

Our next step is to understand how distributed approaches work. For this, Chapter 3 shows a different way of categorizing research works based on an algorithmic procedure. The strategy considers 1) important input variables such as hardware components load and devices positions, 2) scheduling operations as migrations or duplications, and 3) optimized variables such as QoS and energy consumption. Moreover, we study this flow in (de)centralized environments at different deployment levels, such as cloud, grid, or edge. That makes it easy to understand the scope of new scheduling proposals.

Then, having explored state of the art in distributed environments, Chapter 4 describes our scheduling strategies. We have designed a distributed middleware called Kaligreen. It is aware of the software and hardware components of the devices on which it runs. Furthermore, it implements special communication methods that enable centralized and decentralized strategies in any network topology. Kaligreen includes a default algorithm that performs neighborhood microservices exchanges after negotiation and microservices-filtering processes.

Using kaligreen, we have designed, implemented, and tested a fully decentralized algorithm inspired by multidimensional data structures, representing one of this thesis's major contributions. That considers the devices as nodes in a space with as many edges as the characteristics of said nodes. In this space, each device can find peers to negotiate microservice migrations or duplications at an optimal computational cost.

Next, Chapter 5 shows the design and implementation of PISCO, the simulator we created and use to deploy and evaluate our scheduling algorithms. The importance of our tool is to allow its users to focus solely on their scheduling heuristics. For this, PISCO implements an overlay as any data structure (graphs, trees, etc.), devices and software as dynamic objects, and middlewares as threads to execute any scheduling policies.

Finally, the thesis finishes by showing our methods' experiments and results in chapter 6, and its conclussions and future work in section 7.

Regarding the structure of each chapter, each begins by defining its introduction and context, next explaining the methodology that follows, showing its content, and finally arguing its conclusions and contributions.

CHAPTER 2 PROFILING APPS' POWER CONSUMPTION

Profiling applications' power consumption

Introduction

This research work studies how to dynamically (re)deploy software components (containers or virtual machines) and their data to save energy. To do this, we designed and developed intelligent distributed scheduling algorithms that reduce global power consumption, maintaining the applications' quality of service.

They operate (migrations and duplications procedures) considering the natural relation between hardware components' load/features and power consumption.

In order to execute and evaluate these algorithms, we needed to use special hardware and software tools. For example, infrastructures configured with specialized middlewares (Kalimucho [START_REF] Da | Kalimucho: Middleware for Mobile Applications[END_REF], Kubernetes [START_REF]How the Kubernetes scheduler works[END_REF], etc.), measurement devices (wattmeters or uninterruptible power supply (UPS)), among others.

However, since we did not have these technologies available and the effectiveness of power formulas has already been demonstrated [START_REF] David | RAPL: Memory Power Estimation and Capping[END_REF] [START_REF] Colmant | The next 700 CPU power models[END_REF] (even taking into account the hardware heterogeneity), we decided to implement and use our own simulation tool.

PISCO is a highly dynamic simulator (explained in detail in chapter 4) for distributed scheduling. First, it allowed us to deploy heterogeneous nodes in any network topology. Secondly, it served us to define different hardware components for each physical node. Next, it found the component's power/energy consumption from their load and energy mathematical models. Finally, our tool executed and evaluated our distributed scheduling approaches.

From the software point of view, PISCO allows the (re)deployment of software components (for us, running processes) and their connections in the network's nodes. It also calculates said components' energy consumption based on their workload over time. This load can be analyzed considering as many hardware components as defined.

In this research work, we have chosen four components to energetically profile any running process (application, microservice, virtual machine, etc.): The CPU (Central Processing Unit), the RAM (Random access memory), the network card, and the storage device. We based this decision mainly 1) on the fact that for these components, it is possible to obtain the necessary profile values from OS (operating system) interfaces and 2) on the existence of works that analyze these components Chapter 2

Profiling applications' power consumption to outline the energy consumption of a distributed system node. For example, while some works understand that the most important devices to analyze global power consumption are the CPU and RAM [START_REF] Jaiantilal | Modeling CPU Energy Consumption for Energy Efficient Scheduling[END_REF] [START_REF] Nour | Adaptive Power Panel of Cloud Computing Controlling Cloud Power Consumption[END_REF][155] [START_REF] Bellosa | The Benefits of Event: Driven Energy Accounting in Power-Sensitive Systems[END_REF] [START_REF] Acar | Beyond CPU: Considering memory power consumption of software[END_REF], others also take into account other components such as the hard drive, the ethernet card, or even the video card [START_REF] Bellosa | The Benefits of Event: Driven Energy Accounting in Power-Sensitive Systems[END_REF] [153][238].

This chapter describes our distributed scheduling algorithms' input criteria. In the following paragraphs, we study each of these four components' importance, operation, and features. Moreover, we explain the mathematical models that relate the workload produced by a process identifiable by a PID to the respective power consumption.

Methodology

This chapter contains four main sections explaining the four components we study: CPU, RAM, Network Card, and Storage device. Each section explains first the technical hardware details regarding how the component uses power according to a given workload. Then, it describes how several authors study and optimize the components' power consumption. Here we have grouped the approaches into four levels: 1) low-level configuration, 2) software design and development, 3) launching applications, and 4) applications already running. This categorization allows us to identify the techniques and mathematical models compatible with distributed energy savings strategies. If a proposal is possible with the values obtained from OS interfaces, we use them for our algorithm implementation. Otherwise, we develop and use our own formulas.

It is important to say that we have made the differentiation of points 3 and 4 for two reasons. On the one hand, the applications usually contain different startup and post-start execution routines. On the other hand, many profiling tools need to launch the application to analyze it. This fact creates an undesirable dependency relation for production environments but interesting results for building a preexecution profile.

We present the summary section at the end of the chapter, highlighting our contributions and procedures.

The CPU's energy consumption

The CPU (Central Processing Unit) is the hardware component that executes the instructions described in a program through logical/arithmetic operations (among The CPU's energy consumption Section 2.3 others). Depending on the CPU's structural characteristics, these instructions can be executed at different frequencies, using different parallelism and prediction criteria, and finally, using different amounts of energy.

Compared to the other components studied in this chapter, the CPU has the greatest structural variations (even within the same brand) due to technological advancement and the plurality of existing devices. Furthermore, each processor could operate at different voltages or activate different power-related capabilities for energy-saving purposes.

In order to understand how these mechanisms consume energy, it is necessary to study some basic aspects of the processor's operation, which we will describe in the following section.

Background

From an electronics point of view, the CPU comprises millions of silicon transistors that act as switches useful for generating bits from electricity. With these transistors, each processor can execute the instructions described in its ISA (Instruction Set Architecture) using several cores. On the one hand, each core has processing units such as a set of ALUs (Arithmetic Logic Unit) and FPUs (Float Point Unit). Moreover, they have other internal units such as one MMU (memory management unit), one RS (Register Set), a CU (Control Unit), and a set of cache memories. These last usually have three categories: 1) L1, which is the closest (and therefore more quickly accessible) to each core. 2) L2, which each pair of cores share, and 3) L3, which all cores can access [START_REF]How many Transistors in a CPU?[END_REF][231] [START_REF] Gayde | Anatomy of a CPU[END_REF].

Each time a compiler processes an application source code, it generates a set of instructions specific to the CPU's ISA. Then, employing internal or external (operating system ones) selection algorithms, one or more CPU's cores process these instructions. If the CPU implements hyperthreading technology (two data and instruction streams per core), the selection algorithms will also use the core's threads to improve parallel execution.

When executing an application, each core performs the concerning operations using its CU to synchronously utilize its necessary internal units. This work is performed at a frequency determined by the clock's speed, which is dependent on the core's voltage. Therefore, the more frequency, the more operations in a given time a core can process, and the more energy it uses [START_REF]How to Overclock Your Unlocked Intel Core Processor[END_REF].

However, the frequency and voltage are also directly related to the heat produced, which can damage the chip's internals. For this reason, each CPU has a TDP (Thermal Design Power) expressed in Watts, which defines the maximum power with which a processor can work safely for an indeterminate time [START_REF]Potencia de diseño térmico (TDP) en procesadores Intel[END_REF].

Chapter 2

Profiling applications' power consumption

It is important to mention that the TDP may be exceeded for a short amount of time to increase processing capacity in certain circumstances. That is known as Overclocking [START_REF]How to Overclock Your Unlocked Intel Core Processor[END_REF].

On the other hand, executing a program's instructions requires correct memory handling. To be executed, each of them must first be retrieved from RAM or the CPU's caches in order to be placed into the CPU's instruction registers. This process is known as "fetch." Then, through the "decode" process, the CPU discovers each instruction type. Finally, in a process called "execute," the instruction's data is placed in the registers of the corresponding execution unit, such as the ALU for arithmetic, logical, and branch operations or the MMU for memory retrieval operations.

Depending on the type of instruction, there are very complex operations and strategies to be carried out. For instance, if the required instruction's data is not in the core's registers, more clock cycles are required to query the RAM [START_REF] Tanenbaum | Modern Operating Systems. 4th[END_REF].

To face that, the cache controller will try to predict (using special predictive algorithms) and fetch additional to-request data. On the other hand, statements such as "for" or "if" may involve executing a sequence of instructions different from the current one. These instructions are known as branch operations. As the mentioned statements' immediate results are unknown, branch operations can involve unnecessary processing instructions that use indeterminately different core processing units. This phenomenon makes parallelism difficult and the execution efficiency of an application not optimal. To address this, using complex structures called branch predictors, the CPU tries to predict whether a branch should be taken or not with about 95% accuracy on modern processors [START_REF] Gayde | Anatomy of a CPU[END_REF] [START_REF] Both | The central processing unit (CPU): Its components and functionality[END_REF].

As it is easy to see, studying the CPU's power consumption, including parallelism and prediction criteria particular to each model, is an extremely complex task (more than for other components [START_REF] David | RAPL: Memory Power Estimation and Capping[END_REF]). Each CPU model could also implement different forms of energy saving, such as voltage reduction or turning off certain parts of a particular core. However, several studies have managed to relate workloads with the energy consumption they produce in the CPU.

The next section describes these approaches.

Finding and optimizing the CPU's energy consumption

From the point of view of hardware evolution, CPU manufacturers have made processors work at high processing frequencies, using power more and more efficiently. For that, they have implemented two main techniques that seek to adapt the amount of energy invested with the workload type and the chip's temperature.

The CPU's energy consumption Section 2.3

• The DVFS (Dynamic Voltage Frequency Scaling) enables the operating system to reach a certain P-State (Performance State). It lowers the CPU's frequency and voltage under certain circumstances to save energy at the cost of processing capacity [START_REF]CPU frequency scaling[END_REF][145] [233][114].

• The C-States allow each CPU's core to turn off some of its parts as requested by the OSPM (Operating System Directed Power Management). These states establish the core's idle state-level defining the following relation: The deeper the C-state is, the more energy is saved, but the higher is the exit latency to the active state [START_REF]C-State[END_REF]. In figure 2.1, Intel shows the C-states of some of its processors [START_REF]White paper:Energy-Efficient PlatformsConsiderations for Application Software and Services[END_REF] and the relation just mentioned. It is important to note that in order to obtain the best energy-saving results, all (v)cores that share resources such as caches should be affected by the same C-state.

Other works propose improvements in the design of the processing units to save energy. For example, some approaches take better advantage of the turbo boost in order to avoid cache misses and branch mispredictions [START_REF] Kondguli | A Case for a More Effective, Power-Efficient Turbo Boosting[END_REF]. For their part, other scientists intelligently use the power gates to turn off certain processor parts according to the workloads' characteristics [START_REF] Leverich | Power Management of Datacenter Workloads Using Per-Core Power Gating[END_REF] [START_REF] Madan | Guarded Power Gating in a Multi-core Setting[END_REF].

We can use physical sensors, mathematical models, or system-level and processor simulators to discover the effectiveness of these approaches [START_REF] Binkert | The Gem5 Simulator[END_REF]. Although there are several creations of this type, we do not mention them as they are beyond the scope of this work. Some other approaches seek to save energy from a higher level of abstraction by tuning the operating system scheduler. They propose techniques such as 1) modifying the run-queues to halt the CPU when power consumption reaches a certain threshold [START_REF] Bellosa | The Benefits of Event: Driven Energy Accounting in Power-Sensitive Systems[END_REF], 2) grouping tasks of the same type (characteristics, number of cycles in the CPU internals, etc.) for their execution to trigger the DVFS (using, for example, GNU/LINUX ACPI/CPUFREQ) or the C-States [START_REF] Jaiantilal | Modeling CPU Energy Consumption for Energy Efficient Scheduling[END_REF][41] [START_REF] Chen | The Balance Mechanism of Power and Performance in the Virtualization[END_REF], 3) enabling the scheduler to predict the energy-impact of its decisions[130], or 4) enabling CPU and GPU to work as a single unit [START_REF] Kang | Exploration of CPU/GPU Co-execution: From the Perspective of Performance, Energy, and Temperature[END_REF] [START_REF] Tang | Elastic Multiresource Fairness: Balancing Fairness and Efficiency in Coupled CPU-GPU Architectures[END_REF].

For these approaches, the power/energy consumption can be estimated eighter from 1) mathematical models that can, among others, take into account the number of events/cycles that a thread produces in the CPU's internals (ALU, FPU, or caches) [START_REF] Bellosa | The Benefits of Event: Driven Energy Accounting in Power-Sensitive Systems[END_REF][120], 2) from the battery usage in a certain period [START_REF] Corral | Energy-aware Performance Evaluation of Android Custom Kernels[END_REF], or 3) from chip-specific measurement tools [START_REF] Kang | Exploration of CPU/GPU Co-execution: From the Perspective of Performance, Energy, and Temperature[END_REF].

At the next level of abstraction, from the point of view of applications development and execution, some papers relate power consumption to source code procedures. This relation enable developers to perform different energy-aware coding strategies [91][42][172] [START_REF] Acar | The Impact of Source Code in Software on Power Consumption[END_REF]. As in the other approaches, we can use APIs, physical Chapter 2

Profiling applications' power consumption sensors, or measurement applications (e.g., powertutor [186]) to corroborate the results of these techniques.

Once the application has been developed, there are tools that can execute it by counting the number of events/operations that it generates in each of the CPU's internals [START_REF]Intel. Intel VTune Profiler[END_REF][180] [START_REF] Willhalm | Intel® Performance Counter Monitor -A Better Way to Measure CPU Utilization[END_REF][53] (i.e., integer, float point operations, etc.). These tools then infer energy consumption using mathematical models and physical measurement devices [START_REF] Jaiantilal | Modeling CPU Energy Consumption for Energy Efficient Scheduling[END_REF].

On the other hand, when the application is already running and identified by its PID, it is possible to relate the frequency, voltage, or operations type that it needs/performs from/in the CPU with the corresponding energy amount [START_REF]Enhanced Intel SpeedStep Technology for the Intel Pentium M Processor[END_REF][202] [START_REF] Noureddine | Monitoring Energy Hotspots in Software[END_REF].

We summarize all the methods described so far in the table 2.1.

Since we optimize the distributed-applications scheduling in this thesis, the next section deeply describes the approaches mentioned in the last two paragraphs.

Proposal to measure the CPU's power consumption from the perspective of distributed algorithms

As Table 2.1 shows, most approaches analyze and improve the CPU's energy consumption using hardware and operating system features. Nevertheless, as we study software components' distributed scheduling, the next section describes the Profiling applications' power consumption best methods for analyzing the CPU considering two moments: When a component is executed and when it is already running and identifiable by its PID.

Analyzing a process from the moment it is executed and when it is already running

Currently, there are several tools (programs and APIs) compatible with certain OSs that allow estimating the energy consumption of running applications [START_REF] Petit | Scaphandre v0.1.1: measuring the energy consumption of the tech industry (backstages)[END_REF][112] [START_REF] David | RAPL: Memory Power Estimation and Capping[END_REF].

The problem with some of them is that either they do not offer all the models they use openly (at least in their documentation), or their results have been discussed by other scientific works [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF][172] [START_REF] Colmant | The next 700 CPU power models[END_REF].

For these two reasons, we use the model offered by PowerAPI, but also consider the fan's power consumption. In one of its versions presented by Adel Noureddine et al. [START_REF] Noureddine | Monitoring Energy Hotspots in Software[END_REF], the model relates the total current CPU power consumption to the percentage of its capacity an application uses in a given time.

𝑛𝐶𝑜𝑟𝑒𝑠 ∑ 𝑖=0 𝐸 𝑃𝐼 𝐷 𝐶𝑃𝑈 𝑖 (𝑡) = 0.7 × 𝑇 𝐷𝑃 𝑓 𝑇 𝐷𝑃 × 𝑉 2 𝑇 𝐷𝑃 × 𝑓 𝑖 × 𝑉 2 𝑖 × 𝑈 𝑃𝐼 𝐷 𝐶𝑃𝑈 𝑖 𝑈 𝐶𝑃𝑈 𝑖 (𝑡) + 𝑓 𝑎𝑛𝑠 𝑠 (𝑡), 𝑤ℎ𝑒𝑟𝑒 𝑓 𝑎𝑛𝑠 𝑠 = 𝐽 ∀𝐾 (𝑓 𝑖 > 𝑓 𝑥 > 𝑓 𝑗 ) (2.1)
In the formula 2.1, the first factor refers to the CPU's capacitance, which is not always found in datasheets, nor is it easy to obtain through operating system interfaces. For that reasons, the authors deduce it from the processor's TDP and its respective voltage and frequency (the same model, but in terms of the capacitance and TDP's corresponding values). They do that also considering an already proven surplus proportional to 0.7. Then, the second and third factors refer to the current frequency (𝑓 ) and the current voltage (𝑉 ), respectively. The last factor represents the ratio between the CPU time for a process represented by its PID (𝑈 𝑃𝐼 𝐷 𝐶𝑃𝑈 𝑖 ), and the time the CPU is active for all the processes (𝑈 𝐶𝑃𝑈 𝑖 ). Finally, we added the 𝑓 𝑎𝑛𝑠 variable which represents the CPU's fan energy consumption. That assumes a certain speed (𝑠) when a core's frequency 𝑓 𝑥 reaches a value between 𝑓 𝑖 and 𝑓 𝑗 .

In the context of our algorithms, we use this formula for each core 𝑖, considering multithreading situations. We can obtain its values using GNU/Linux interfaces (applications) such as turbostat [START_REF] Brown | turbostat -Report processor frequency and idle statistics[END_REF] for the TDP (MSR_PKG_POWER_INFO interface) and idle statistics, msr-tools [START_REF]Intel. Intel -msrTools[END_REF] (rdmsr 0x198 -u -bitfield 47:32)/8192)

The RAM's energy consumption Section 2.4

for core voltage1 , perf[180](perf stat -per-core -pid) or ps[181](ps -p PID/PSR) for processes' per-core CPU usage, and lm-sensors [START_REF] Wiki | Lm_sensors -Linux hardware monitoring[END_REF] for the CPU's fan information.

It is important to mention that CPU undervolting or C-states can formally be triggered from the OS internal calls (mwait, htl, IA*_PERF_CTL, etc.). However, some unofficial tools allow manual procedures [147].

In the context of our work, we indirectly consider the DFVS and C-States from the non-linear nature of the formula 2.1.

Important considerations and future work

Although the model we use is quite accurate to measure the applications' energy consumption, we know that new processors are more complicated to study. We will consider C-states and P-States more deeply in future works, modeling them per level and residency.

In addition, we also know that we must evaluate special widely-used CPU characteristics such as overclocking. To do that, in future works, we may improve the model we described in the previous section. However, we can also use other approaches, such as the last provided by powerAPI [START_REF] Colmant | The next 700 CPU power models[END_REF]. It dynamically learns CPU power models by exploring the space of hardware performance counters.

On the other hand, we obtained the formula's values using GNU/Linux interfaces. That allows us to prove its viability and obtain the input numbers for our simulated environment. However, we will extend our approach by considering different OS and tools in future works.

The RAM's energy consumption

As it is known, the RAM (Random Access Memory) is the hardware element that the CPU actively employs to read and write data (programs, operations, operations results, etc.) in a program execution context. Here, each time the CPU needs to read an n-bit word, it first checks to see if that word is in its cache memories, spending an approximate time of two clock cycles. If so (cache hit), the CPU will continue the program's execution with the information found. Otherwise (cache miss), that component will have to search the word in the RAM and swap it with the old cache's value, spending more time and energy [START_REF] Tanenbaum | Modern Operating Systems. 4th[END_REF].

The operating systems use RAM to run applications for efficiency reasons. Permanent storage devices, such as hard drives, do not achieve enough data transfer Chapter 2

Profiling applications' power consumption speed for the CPU to operate at its optimum frequency. For example, while a solidstate hard drive on the market today offers a transfer rate of 2000𝑀𝐵/𝑠 for reading operations and 1700𝑀𝐵/𝑠 for writing operations [START_REF]Crucial P1 1TB 3D NAND NVMe PCIe M.2 SSD[END_REF], a current RAM can transfer data at 35200𝑀𝐵/𝑠 for both operations [START_REF]%2C%20or%202[END_REF]. For that reason, when an application is launched, or a file is opened, the operating system first copies the concerning data from the storage device to the RAM.

All these processes lead several RAM's electric parts to work and spend nonnegligible amounts of energy. The following section deeply explains the necessary RAM internals operation to understand its power consumption modeling.

Background

From an internal point of view, each RAM type can manage data using different electric devices. For example, if it is an SRAM (static random access memory), it stores 1 bit using a six transistor memory cell. Otherwise, in the case of DRAM (dynamic random access memory), it uses a transistor and capacitor pair to do that [START_REF]Crucial. Different Types of RAM Explained[END_REF].

In the current hardware industry, SRAMs are usually employed as CPU caches and DRAMs as user-replaceable memory modules [START_REF]Crucial. Different Types of RAM Explained[END_REF]. For this reason, this section focuses on understanding how a DRAM stick works. As Figure 2.2 shows, internally, a DRAM module can be seen as a hierarchically structured hardware component [START_REF] Cheng | Retention-Aware DRAM Auto-Refresh Scheme for Energy and Performance Efficiency[END_REF]. Within it, the most basic element is the memory cell. As aforementioned, to store 1 bit of data, each memory cell uses its internal transistor as a switch and its capacitor as short-time storage of electric charge. If the capacitor contains an electric charge, it represents a binary number 1; otherwise, the binary represented is 0 [START_REF] Drumm | Dynamic Random Access Memory (DRAM). Part 1: Memory Cell Arrays[END_REF]. The next element is the DRAM BANK, which contains a set of memory cell matrices. That set usually has an 8-bit size to simultaneously process a byte per bank. Then, a set of memory banks (typically 4, 8, or 16) makes up a single memory CHIP. Finally, the memory chips that can be accessed simultaneously by the same memory channel (the link between the CPU memory controller and RAM modules) compose a memory RANK [START_REF] Micron | Calculating Memory Power for DDR4 SDRAM[END_REF].

It is also important to mention that a RAM module can contain several ranks and access pins distributed on both sides (both easily visible). This architecture is known as DIMM (Dual Inline Memory Module).

The access speed and the energy usage of each DIMM depend on the number of pins it has, the voltage it needs to work, the frequency its clock operates, and how it executes read and write operations.

To perform the latter, current DIMMs use both the clock's rising and falling edges to trigger the transfer operation to the data bus [START_REF] Hp | Double Data Rate SDRAM: fast performance at an economical price[END_REF]. This technology is known as DDR (Double Data Rate), which has several upgrade versions over time [START_REF] Crucial | What Is the Difference Between DDR4[END_REF].

With the aim of reading or writing data, a module distributes memory addresses to each bank through a special bus. This process can be done in two ways: 1) Consecutively per bank, or 2) evenly among banks. The latter represents a working fashion known as memory interleaving mode.

The mentioned bus, alongside the RAS (row address strobe) and CAS (column address strobe) pins, are used to find the data bits to operate. First, each data bit is stored in a data buffer after bit-line precharging operations (i.e., set the bitline to half the voltage of the entire module). Then, the mentioned elements write the data bit's row and column numbers in the row and column addresses buffer. Finally, the module interprets the WE (write enable) pin's load to differentiate the operation type (read or write).

The data preservation in a DDR-DIMM is given in its normal working state by refresh cycles generated by the clock. These are synchronized with the natural capacitors' energy loss and the reading/writing operations described above. That is because executing these operations always discharges capacitors, which implies its data destruction [START_REF] Drumm | Dynamic Random Access Memory (DRAM). Part 2: Read and Write Cycles[END_REF].

Other RAM's working states aim to save energy by turning off some of its internals. They are triggered through a per-rank signal called CKE (clock en-Chapter 2

Profiling applications' power consumption able) [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF][155] [START_REF] Micron | [END_REF], depending on the OS mode and the time that the RAM is idle. For instance, the self-refresh state keeps the pins and banks working with the minimum voltage necessary to avoid the data disappearance. Here, the refresh operation is performed by a built-in timer instead of by the external clock. Other states seek to save energy by periodically deactivating the CKE or certain ranks.

As it is possible to see, each memory module uses energy to preserve data in each bank and perform read and write operations. However, the RAM implements several energy-saving states which are triggered depending on certain circumstances. The next section explains some approaches that seek to measure and optimize the RAM power consumption considering the explained elements and some software capacities.

Finding and optimizing the RAM's energy consumption

Studying the RAM power consumption is a complex task that can be achieved from a hardware or software perspective. Regarding the first, memory manufacturers have lowered the voltage and increased the transfer rate with which the modules work. This fact can be seen in each of the DDR versions. For instance, the DDR2, DDR3, and DDR4 modules provide an operating voltage of 3.3, 1.35, and 1.2, respectively [START_REF] Tanscend | What is the difference between SDRAM[END_REF]. It's important to say that these values can be easily verified with direct measurement instruments or through OS interfaces such as the dmidecode tool [148].

On the other hand, other scientists proposed some RAM structural changes. For example, the elimination of the DRAM chip timing circuitry, delegating its responsibility to the memory controller. This strategy decreases the idle state in the modules' active mode, allowing data transfers immediately after wake-up operations. As a result, this approach reduces energy per transfer by 50% with no performance impact [START_REF] Malladi | Rethinking DRAM Power Modes for Energy Proportionality[END_REF]. This value can be verified using tools such as x86_64 execution-driven processor simulators.

In the literature, it is possible to find more works related to hardware improvement; but we will not detail them as they are outside the scope of this work.

From a software perspective, some RAM configurations can be activated from the motherboard's firmware. For example, the last work we cited [START_REF] Malladi | Rethinking DRAM Power Modes for Energy Proportionality[END_REF] also mentions that it is possible to decrease the power consumption by disabling the delay-locked loops or memory interleaving in the BIOS. However, that implies serious performance penalties. Moreover, other approaches also use the BIOS options to modify the RAM's working voltage and frequency. Nevertheless, this strategy also has efficiency negative consequences without achieving desirable power consumption results [START_REF] Deng | MemScale: Active Low-Power Modes for Main Memory[END_REF]. On the other hand, some approaches study the RAM power consumption from a higher level of abstraction. They analyze the OS and compilers configurations, considering the RAM workload (amount of reading and writing operations) over time and its corresponding power states [START_REF] Micron | [END_REF] [START_REF] Micron | Calculating Memory Power for DDR4 SDRAM[END_REF]. For example, several authors tune the operating system to induce some banks (normally by ranks) to spend less power. Some do that by modifying the page allocation policies [START_REF] Lebeck | Power Aware Page Allocation[END_REF] [START_REF] Garg | Linux VM Infrastructure for memory power management[END_REF]. Others consolidate the memory allocations and/or references, preventing them from spreading across the entire address space [170]. Finally, various authors improve OS scheduling operations per thread considering the number of hardware events (floating-point operations, number of memory accesses, etc.) each performs [START_REF] Bellosa | The Benefits of Event: Driven Energy Accounting in Power-Sensitive Systems[END_REF].

The input parameters of the latter are also useful for studying power consumption from other points of view. For instance, the compilers and programming languages development, the mathematical models based on a source code's operations [START_REF] Acar | Beyond CPU: Considering memory power consumption of software[END_REF], etc. These parameters can be obtained from applications such as Heaptrack [START_REF] Kdab | First stable release of the fast Linux heap memory profiler[END_REF] and Hotspot [START_REF]Hotspot A GUI for perf report[END_REF]. Furthermore, they can also show, among others, the link between the number of memory accesses of a running application and its corresponding lines of code Finally, in the context of already built applications, some tools such as perf (Performance analysis tools for Linux)[180], Intel's Performance Counter Monitor [START_REF] Willhalm | Intel® Performance Counter Monitor -A Better Way to Measure CPU Utilization[END_REF], or different types of physical sensors, allow studying the number of RAM accesses they perform when executed or when they already run. These tools are used by works that propose methods and models to interpret the RAM energy consumption. To do that, their authors usually consider certain types of workloads and the presence of certain amounts of data in this component [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF][53] [START_REF] Appuswamy | Scaling the Memory Power Wall With DRAM-Aware Data Management[END_REF].

The table 2.2 summarizes the techniques described above for measuring and optimizing RAM power consumption. It separates the approaches into four levels of abstraction: (1) Low level, which involves hardware development or configuration, including firmware and operating systems. (2) Medium level, which studies software design and development (from the programing language point of view). [START_REF] Agrawal | O-ICN Simulator (OICNSIM): An NS-3 Based Simulator for Overlay Information Centric Networking (O-ICN)[END_REF][START_REF] Ahmad | Container scheduling techniques: A Survey and assessment[END_REF] High level, which comprises executing and running applications.

In this thesis, we study and optimize the scheduling of software components, which are running applications. For that reason, the next section focuses on deeply explaining the levels 3 and 4 mentioned in the last paragraph.

The RAM's energy consumption Section 2.4 2.4.3 Proposal to measure the RAM's power consumption from the perspective of distributed algorithms

As we indicated in section 2.1, this research analyzes and optimizes the energy consumption of software components (in fact, running applications) through distributed scheduling operations. This analysis can occur from the moment an application is launched or when it is already running. In terms of RAM, these operations should consider two factors. On the one hand, they must be based on information accessible to the scheduling platform (usually middleware). On the other hand, they must attempt to get the RAM into low-power states. Not many works have dealt with this topic since most focus on low-level aspects, as seen in the second part of the table 2.2. However, there are some exceptions. For instance, the creators of RAPL (Running Average Power Limit) proposed a weightsbased model to relate the RAM power consumption, the read/write operations it performs, and its CKE state [START_REF] David | RAPL: Memory Power Estimation and Capping[END_REF]. However, we didn't find the implementation of this model's calibration process (the model's weights). In addition, its accuracy has been re-evaluated, showing mixed results, especially when the system is in idle states [START_REF] Desrochers | A Validation of DRAM RAPL Power Measurements[END_REF].

As another example, one of the most relevant approaches for us is the one proposed by Alexey Karyakin et al. [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF]. Their work provided and tested (using measurement tools and mathematical regression) a model to calculate the energy used by the RAM when performing database operations. This model considers in a differentiated way: (1) the background consumption, which depends only on the RAM's power state, and (2) the active consumption, which is generated by the reading/writing operations it performs.

To calculate the first type of consumption, the authors considered the percentage of a given time in which the RAM is in one of the following power states: (1) Active, which represents the "normal" working state (2) CKEOFF, which represents all intermediate states of power saving and (3) self-refresh, as the state of least power consumption. Thereby, the model they propose multiplied the said time by the corresponding power consumption. Moreover, since they used physical measuring instruments, the model considers the additional consumption generated by each rank in an active state as a separate attribute.

To calculate the RAM's active consumption, the authors considered the number of reading and writing operations carried out in a given time. That is, they multiplied the number of operations of each type by the energy consumption that each one generates. Here, the authors' model also considers the consumption of each precharge and activation cycle generated per operation.

For our part, to find an application's energy consumption in terms of RAM, Chapter 2

Profiling applications' power consumption we use this same approach in a particular way. We also discover the RAM's background and active consumption but consider only the information we can obtain from the GNU/Linux interfaces. Furthermore, we differentiate between an application launching process and an application already running in the active energy consumption.

The background energy consumption (𝑬 𝑩𝑲 )

In order to determine the RAM's power state residency from OS interfaces, we consider using two different approaches:

1. Option 1: To use a processor counter monitor:

These powerful tools offer a set of easy-to-use programs that provide (among other functionalities) very verbose RAM information. For example, its internals' description, the global number of operations it performs in a given time, and (in a fairly exact way) the residence of the RAM's ranks in each of its power states.

Among these tools, the Intel Processor Counter Monitor -PCM includes the pcm-memory.x and pcm-power.x applications to do this [START_REF] Appuswamy | Scaling the Memory Power Wall With DRAM-Aware Data Management[END_REF][150].

Other vendors like AMD [START_REF]AMD mProf[END_REF] provide similar tools for their processors.

Although PCM-tools are excellent for our purposes, they are compatible with a limited range of processor models (even from the same brand). That is why we consider using the relation between the memory and OS power states, as explained below:

2. Option 2: To interpret the kernel power-states:

Following the GNU/Linux kernel specification [START_REF] Rafael | System Sleep States[END_REF], we relate its power states with those of the RAM as follows:

• The Suspend-to-idle state and Standby state both have the equivalent of the RAM's CKEOFF state. The former suspends the timekeeping and puts all I/O devices into low-power states. The latter does the same but also disables low-level system functions.

• The Suspend-to-RAM state puts the whole system into a low-power fashion. In the specific case of the RAM, it is set in the self-refresh state to allow the session's data retention.

To learn the OS power-state, we can read the /sys/power/state file [START_REF] Rafael | Power Management Interface for System Sleep[END_REF]. Its content usually is: Using any of these options, in our approach, we consider the amount of time the RAM was in each state (𝑇 𝑥 ), multiplied by its corresponding power consumption (𝑃 𝑥 ). That can be seen in the formula 2.2.

𝐸 𝐵𝐾 = 𝑇 𝑠 𝑓 × 𝑃 𝑠 𝑓 + 𝑇 𝑐𝑘𝑒𝑜 𝑓 𝑓 × 𝑃 𝑐𝑘𝑒𝑜 𝑓 𝑓 + 𝑇 𝑎𝑐𝑡 × 𝑃 𝑎𝑐𝑡 + ∑ 𝑖∈𝑟𝑎𝑛𝑘𝑠 𝑇 𝑎𝑐𝑡 × 𝑃 𝑎𝑐𝑡 𝑖 (2.2)
Moreover, as aforementioned, the model of Alexey Karyakin et al. [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF] considers additional power consumption per rank (row activations, reads, and writes) in the CKEON state. For the case of option two, we also take this consumption into account but consider the OS's active state. The value of each factor in the formula 2.2 can be obtained by: (1) The tools described in the two previous options, (2) the dmidecode -t memory[148] interface to know the number of memory ranks, and (3) the table 2.3, whose values were provided by the measurement and regression work of Alexey Karyakin et al. [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF].

The active energy consumption (𝑬 𝒂𝒄𝒕 )

As Alexey Karyakin et al. [START_REF] Karyakin | An Analysis of Memory Power Consumption in Database Systems[END_REF] do, we calculate RAM's active energy consumption from the number of read-write operations carried out in a given time or by a process. That is, we multiply the number of operations (𝑁 𝑥 ) by the energy consumption (𝐸 𝑥 ) that each one generates.

The only difference with the mentioned authors is that we do not take into account the energy consumption of the pre-charge/activation cycles. That is because we couldn't access this information from any OS interface.

We describe the RAM's active energy consumption in the formula 2.3.

Chapter 2

Profiling applications' power consumption

𝐸 𝑎𝑐𝑡 = 𝑁 𝑅 × 𝐸 𝑅 + 𝑁 𝑊 × 𝐸 𝑊 (2.3)
Following the chapter's methodology, we analyze an application's energy consumption from the moment it is executed and when it is already running. That is why we propose to obtain the values of each factor in the formula 2.3 in two slightly different ways.

1. Option 1: Analyzing an application from the moment that it is executed:

In this option, the values of each factor in the formula 2. In this option, we use the same sources as the previous one but make the perf command receive as parameters: 1) The PID of the process to be analyzed, and 2) the virtual folders of the CPU/RAM read-write events (cpu/mem-stores and cpu/mem-loads): perf (record | stat) -e cpu/mem* -p pid

It is important to mention that tools based on perf, such as Heaptrack and Hotspot [START_REF] Kdab David | Profiling CPU and Memory on Linux, with Opensource Graphical Tools[END_REF], allow analyzing the memory accesses an application performs more clearly (even visually). These help to understand its behavior at certain times and consider external variables, such as the number of requests, availability of other resources, etc.

The overall application's energy consumption in the RAM (𝑬 𝑹𝑨𝑴 𝒂𝒑𝒑 )

As the Formula 2.4 shows, we consider both the active (𝐸 𝑎𝑐𝑡 ) and the background (𝐸 𝐵𝐾 ) energy consumption to determine the energy consumed by an application in the RAM.

The NIC's energy consumption Section 2.5

𝐸 𝑅𝐴𝑀 𝑎𝑝𝑝 = 𝐸 𝐵𝐾 + 𝐸 𝑎𝑐𝑡 𝑎𝑝𝑝 (2.4)
Since the factors of the Formula 2.4 can be found from OS interfaces, we can use it either to analyze a single application (process) or entire OS instances. This consumption information is useful for distributed algorithms to make energyconscious scheduling decisions.

Important considerations and future work

As the following chapters will show, the analysis of this section allows RAM to be an energy criterion for distributed scheduling algorithms. However, we are aware that our model may not be exact. That's because of the lack of analysis of the preload cycles, variations in the hardware model, or the impressions caused by normal OS interruptions.

For this reason, although our scheduling algorithms are based on comparative aspects and not on exact quantities, we will improve the proposed model using measurement devices and regression techniques in future work.

On the other hand, we obtained the model's values using GNU/Linux interfaces. That allows us to prove its viability and obtain the input values for our simulated environment. However, we know that we can learn other energy models with different tools and operating systems. We will also do this study in future work.

The NIC's energy consumption

The NIC (Network Interface Controller) is the hardware component used by a network node to communicate with other peers. To achieve this, a NIC supports several transmission protocols [START_REF] Cdw | Types of Network Protocols: The Ultimate Guide[END_REF] and data sending/receiving abstraction levels, such as the proposed in the OSI model for Ethernet [119].

Different NICs types enable different network architectures, such as Ethernet, Token Ring, Bluetooth, or Wifi [START_REF]Networking[END_REF]. Each of these cards presents different ways of operation and, therefore, energy consumption.

In this work, we study Ethernet and Wifi devices since, to our understanding, these are the most used and studied in the distributed environments context.

Background

A network interface, whether it is embedded, internal, or external, typically consists of data buses, a memory, a processor, connectors, etc. [START_REF]Network interface card (NIC)[END_REF][226] [START_REF]Network Interface Cards -Cisco Documentation[END_REF].

Chapter 2

Profiling applications' power consumption Unlike our analysis of the CPU and RAM, we will not deeply detail the NIC's internals. That's because of two reasons. On the one hand, we have not found a way to relate the NIC circuitry's operations to its energy consumption. On the other hand, although network cards enable various energy-saving states (e.g., IEEE 802.11 power management specification [START_REF] Chiaravalloti | Power consumption of WLAN network elements[END_REF]), we have not found a way to obtain their parameters from any GNU/Linux interface. That's why the power consumption models that we study/propose for this component are mainly based on: 1) the number and size of packets it receives-sends, and 2) the transfer rate it performs.

Finally, it is important to say that we study wired and wireless cards in the same way. We do that because several differential aspects are unmanageable for us. For example, the fixed wireless cards' transfer-power value (which impacts the distance of the signal) can be obtained from tools like wavemon -tx-power [227]. However, it can only be modified by recompiling the corresponding drivers.

The following section explains some existing approaches and our proposal to find and optimize the NICs' power consumption.

Finding and optimizing the NIC's energy consumption

In the literature, several works propose mathematical models to find the NIC's power consumption from different abstraction points. To do that, some study an entire network deployment considering several aspects. Among these aspects, we can mention protocols and topologies [START_REF] Cornea | Studying the energy consumption of data transfers in Clouds: the Ecofen approach[END_REF], each node involved in the transmissions (NICs, routers, switches, etc.) [START_REF] Orgerie | ECOFEN: An End-to-end energy Cost mOdel and simulator For Evaluating power consumption in large-scale Networks[END_REF] [START_REF] Nedevschi | Reducing Network Energy Consumption via Sleeping and Rate-Adaptation[END_REF], and the transmission power-money costs [START_REF] Orgerie | ECOFEN: An End-to-end energy Cost mOdel and simulator For Evaluating power consumption in large-scale Networks[END_REF]. Furthermore, they also consider the simulation of scenarios where they relate variables such as transfer rate, the number of read/write operations, and energy consumption [START_REF] Gupta | iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments[END_REF] [START_REF] Zhang | mqSim: Enabling Accurate and Scalable Simulation for Interactive Microservices[END_REF].

On the other hand, from the analysis point of a single device, some scientists study the last-mentioned relation to develop specialized platforms, applications, or APIs [START_REF] Noureddine | Monitoring Energy Hotspots in Software[END_REF] [START_REF] Petit | Scaphandre v0.1.1: measuring the energy consumption of the tech industry (backstages)[END_REF].

Other different approaches study the energy consumption of point-to-point communications. They take into account the entire network architecture [START_REF] Cornea | Studying the energy consumption of data transfers in Clouds: the Ecofen approach[END_REF], the execution of packet sending/receiving/discarding operations that specific services perform [START_REF] Yan | Modeling the Total Energy Consumption of Mobile Network Services and Applications[END_REF][73], etc. Finally, as an example of a low-level perspective, some scientists consider the Mbit/Joule energy consumption in antennas and other network devices' circuitry [START_REF] Björnson | How Energy-Efficient Can a Wireless Communication System Become?[END_REF].

Regarding optimizing the NICs' power consumption, diverse solutions also focus on different levels of abstraction. For instance, from a low-level perspective, the GNU/Linux Kernel may use IOCTL calls to request the network driver to put the NIC (or network subsystems) in a low-power state [129].

The NIC's energy consumption Section 2.5

From a higher point of view, other works seek to improve the behavior of some transmission protocols. For example, they adjust the packet payload size and transfer patterns [START_REF] De Maio | Evaluating Energy Efficiency of Gigabit Ethernet and Infiniband Software Stacks in Data Centres[END_REF], modify the number of packets transmissions [START_REF] Jo | The Energy Saving Strategy Using the Network Coding in the Wireless Mesh Network[END_REF], improve the paths or the number of hops performed through the nodes [START_REF] Yaacoub | Cooperative Wireless Sensor Networks for Green Internet of Things[END_REF][149], and others. These strategies enable network elements to intelligently go into sleep mode or adapt bandwidth to save energy [START_REF] Nedevschi | Reducing Network Energy Consumption via Sleeping and Rate-Adaptation[END_REF].

Finally, some scientists optimize power consumption by improving data distribution among the nodes. They do that to shorten data-node distances [START_REF] Malik | Middleware for Managing Provenance Metadata. In: Middleware '10 Posters and Demos Track[END_REF], apply data consumption prediction algorithms [START_REF] Niloufar | Poster: Energy Optimization Framework in Wireless Sensor Network[END_REF], etc.

The Table 2.5 summarizes the techniques we described to find and optimize the NIC's power/energy consumption. We consider four abstraction levels within it:

(1) The low level, which involves hardware configuration, operating system/drivers customization, or protocols improvement. [START_REF] Acar | The Impact of Source Code in Software on Power Consumption[END_REF] The medium level comprises software design and development (from the conception/programming point of view) considering variables such as the amount of sending operations performed. Finally, [START_REF] Agrawal | O-ICN Simulator (OICNSIM): An NS-3 Based Simulator for Overlay Information Centric Networking (O-ICN)[END_REF][START_REF] Ahmad | Container scheduling techniques: A Survey and assessment[END_REF] the high-level analyzes executing and running applications considering variables such as transfer rate or the number of packets received/sent.

The next section explains our approach to find the NIC power consumption from the high-level perspective, which is compatible with distributed scheduling.

Proposal to measure the NIC's power consumption from the perspective of distributed algorithms

In this research, we analyze and optimize the software components' energy consumption by means of distributed scheduling operations. For this, we need to study these components' consumption from those NIC-related variables (among the others described in this chapter) that are possible to obtain from OS interfaces. As shown in both parts of table 2.5, several works provide useful methods to analyze running processes from the NIC perspective. They consider variables such as 1) the current transfer rate, 2) the number of sent-received packets in a period, and 3) the current power status of the network card.

Although these models are very interesting and potentially useful for our research, they present some problems for us. For instance, the creators of powerAPI [START_REF] Noureddine | Monitoring Energy Hotspots in Software[END_REF] offer a model based on the time that the network card spends in each of its power states. Although this model has already been tested by them, we have not found a way to obtain these states (Power-up, idle 10/100/1000, LPI, S0, SX, among others [START_REF]intel. Intel Ethernet Connection I219-LM[END_REF] using any GNU/Linux interface. Similarly, in order to find the NIC's power consumption, Feeney, L.M et al. [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF] the operations of sending, receiving and discarding packages. In addition to our problem obtaining the power states, the packets discarding correspond to the protocol's operation and not necessarily to the behavior of processes. As a last example, Nedevschi et al. [START_REF] Nedevschi | Reducing Network Energy Consumption via Sleeping and Rate-Adaptation[END_REF] propose models to find the power consumption of all the elements of a network considering the sending operations costs, processing of network packages, device's power states and the adaptation of transfer rates. Although this work is very interesting, the adequacy of transfer rates and packet processing is outside the scope of our work.

It is also important to say that, unlike previous devices, we couldn't analyze the NIC's consumption differently when a process is launched and when it is already running.

For all these reasons, we decided to propose our own energy models that relate processes' NIC-load with the corresponding power consumption. That is what the next section explains.

Analyzing a process from the moment it is executed and when it is already running

As we said above, the existing methods focus mostly on analyzing transmitted packets, the bandwidth, and the NIC's power states to find its power consumption. To achieve this objective, we don't consider the device's power states. Instead, on the one hand, we propose a model based on the process's transfer rate. On the other hand, we propose another approach based on the number of packets a process transmits/receives.

Analyzing a process from the transfer rate it generates:

To obtain the NIC's power consumption of a process, we start by finding this component's overall current consumption. For this, for a certain device D, we establish a 𝑊 𝑢 𝑑 and a 𝑊 𝑖 𝑑 values which represent the power consumption in Watts when its NIC is in an active and idle state, respectively.

For a current transfer rate 𝐿 𝐷 ,𝑊 𝑢 𝐷 multiplies 𝐿 𝐷 relative to its maximum transfer capacity 𝐿 𝑀𝐴𝑋 𝐷 . Then, this result is added to the idle state consumption. For this, 𝑊 𝑖 𝐷 multiplies the complement of the NIC's load (i.e. 𝐿 𝑀𝐴𝑋 𝐷 -𝐿 𝐷 ) relative to 𝐿 𝑀𝐴𝑋 𝐷 .

Finally, to obtain energy consumption in joules 𝑊 𝑎𝑡𝑡𝑠 × 𝑠, we take into account the time 𝑇 in seconds. That is shown in the formula 2.5, which considers a symmetrical full-duplex mode:

Chapter 2

Profiling applications' power consumption

𝐸 𝑁 𝐼𝐶 𝐷 = (𝑊 𝑢 𝐷 × 𝐿 𝐷 𝐿 𝑀𝐴𝑋 𝐷 + 𝑊 𝑖 𝐷 × 𝐿 𝑀𝐴𝑋 𝐷 -𝐿 𝐷 𝐿 𝑀𝐴𝑋 𝐷 ) × 𝑇 𝐷 (2.5)
Before analyzing running processes, it's important to mention the lastformula factors' sources:

• The NIC's transfer capacity can be obtained from standardized specifications or datasheets [START_REF] De Maio | Evaluating Energy Efficiency of Gigabit Ethernet and Infiniband Software Stacks in Data Centres[END_REF], interfaces such as ethtool input [START_REF]ethtool -utility for controlling network drivers and hardware[END_REF] for ethernet connections, or the /sys/class/net/Interface/device /max_link_speed (this could be different depending on the GNU/Linux distribution) interface for wifi, ethernet or other types of network cards.

• The current global transfer rate can be obtained from interfaces such as the iftop -i[94] program.

• The power consumption of the NIC's working states can be obtained from datasheets (e.g., the intel I219-LM datasheet [START_REF]intel. Intel Ethernet Connection I219-LM[END_REF]), or some descriptive works like the one done by Chiaravalloti et al. [START_REF] Chiaravalloti | Power consumption of WLAN network elements[END_REF].

Then, to model the energy consumption of a process M (identifiable by its PID) in terms of its workload in a device's (D) NIC, we use the equation 2.5; but only consider the mentioned workload (𝐿 𝑀 ). However, one of our challenges was figuring out how to handle idle time. In one first approach, given that at a given time 𝑇 , the transfer rate is the average of the sending/receiving operations and idle states in 𝑇 , we also considered that 𝑀 generates an idle state proportional in the same way that 𝐿 𝑀 is for the current NIC's load (𝐿 𝐷 ). We show that in the equation 2.6.

𝐸 𝑁 𝐼𝐶 𝐷 𝑀 = (𝑊 𝑢 𝐷 × 𝐿 𝑀 𝐿 𝑀𝐴𝑋 𝐷 + 𝑊 𝑖 𝐷 × 𝐿 𝑀𝐴𝑋 𝐷 -𝐿 𝐷 𝐿 𝑀𝐴𝑋 𝐷 × 𝐿 𝑀 𝐿 𝐷 ) × 𝑇 𝐷 (2.6)
This last formula implicitly considers the idle state at a certain moment of transmission. However, it may have a problem. Suppose several processes use the network card, keeping it with a relatively high load. In that case, the energy consumption of the idle state is attributed to each process, increasing its consumption in proportion to the load they generate. Although this may make sense, that increase is no longer logical and becomes artificial in different situations. For example, suppose that there is only one process that uses the NIC at a low transfer rate, and all the NIC's idle consumption is attributed to it. Here, high idle power consumption affects a process that uses the network card at a low frequency.

The NIC's energy consumption Section 2.5

That is why in a second approach, we decided to consider the idle time independent of the processes and exclusive to the NIC's background consumption. In this way, the power consumption of a process depends exclusively on the operations it performs on the NIC. We show that in the formula 2.7:

𝐸 𝑁 𝐼𝐶 𝐷 𝑀 = (𝑊 𝑢 𝐷 × 𝐿 𝑀 𝐿 𝑀𝐴𝑋 𝐷 ) × 𝑇 𝐷 (2.7)
This model is useful when it is only possible to obtain the consumption data of the NIC's idle and active state. However, it does not consider the power consumption differences that may exist between the sending and receiving operations. That is why, if this information is available, a pertinent approach is necessary. We will discuss it in the next paragraph.

Analyzing a process from the packets it sends or receives

Another way we study a process's power consumption from its NIC usage is by analyzing the sending/receiving operations it performs. Indeed, this simple principle does not consider some protocol aspects, such as link-layer fragmentation or unsuccessful attempts to acquire media contention [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF]. However, it enables quite accurate mathematical models based on data obtainable from OS interfaces.

In our approach, we start defining the 𝑊 𝐷 𝑆 and 𝑊 𝐷 𝑅 values to represent a device's (𝐷) NIC power consumption (in Watts) when sending and receiving packets. Then, to find the energy consumption (𝐸 𝑁 𝐼𝐶 𝐷 𝑀 ) that a process (𝑀) generates on the NIC, we calculate the time that said process keeps the NIC sending and receiving data. To define this time, we first multiply the number of packets sent (𝑁 𝑆 𝑀 ) or received (𝑁 𝑅 𝑀 ) by the respective average packets' size (𝑆 𝑥 ). Then, we divide the results by the corresponding total transfer speed (𝐿 𝑀𝐴𝑋 𝑥 ).

We describe that approach in the formula 2.8.

𝐸 𝑁 𝐼𝐶 𝐷 𝑀 = 𝑊 𝐷 𝑆 × 𝑁 𝑆 𝑀 × 𝑆 𝑠 𝐿 𝑀𝐴𝑋 𝑠 + 𝑊 𝐷 𝑅 × 𝑁 𝑅 𝑀 × 𝑆 𝑟 𝐿 𝑀𝐴𝑋 𝑅 (2.8)
Regarding the sources of the formula factors', let us explain two important points:

• The data concerning the packets, such as the quantity, size, and type of operation performed per process, can be obtained from applications such

Chapter 2

Profiling applications' power consumption as atop -n. For that, if the netatop-dkms kernel module is compiled, the tool provides information by protocols such as UDP and TCP. If it is the case, the model 2.8 must be extended.

• The maximum transfer rate per operation and the corresponding power consumption values can be found from the same sources described in the previous section.

Storage device energy consumption

The Storage Device is the hardware component that permanently stores users' and system's information. As we explained in section 2.4, each time an application is launched, the OS copies all or part of the application's data from the storage device to the RAM for efficiency reasons. Then, depending on the application's behavior, there could be data exchange between both components at a certain frequency. Moreover, if the amount of information exceeds the RAM capacity, the OS may use the storage device as a swap area, increasing its operational load [START_REF] Tanenbaum | Modern Operating Systems. 4th[END_REF]. All this flow causes the storage device to perform read and write I/O operations. These activate internal electrical components that consume energy when working.

In the following sections, we analyze the necessary information to understand this consumption from the perspective of running processes.

Background

Generally speaking, there are currently two types of storage devices for personal computers and servers: HDD (Hard Disk Drive) and SSD (Solid State Drive). The former comprises a stack of spinning metal disks known as platters. Each spinning disk has trillions of fragments that can be polarized to represent bits (1s and 0s in binary code). An actuator arm carries out this process. It magnetizes the fragments to write information and detects their magnetic charges to read it.

On the other hand, SDDs comprise trillions of semiconductors that store information by changing the electrical current of special internal circuits. Unlike HDDs, SDDs offer a higher transfer speed since their way of operating does not depend on moving parts [START_REF]Types of storage devices[END_REF].

Finally, both types of storage devices define four power states: Active, Idle, Standby, and Sleep. In this sequence, the more power a state saves, the longer it takes to return to the active state [194].

As we did with the network card, we will not detail more about the storage device's internals since the models we find-propose do not depend on them. Moreover, Storage device energy consumption Section 2.6

for the same reason, we consider for both the HDD and the SSD only two working states and their corresponding power consumption: The active and the idle state.

The following sections explain our approach to model applications' power consumption from the perspective of storage devices.

Finding and optimizing the hard drive's energy consumption

In the state of the art we analyzed, not many works have studied the storage device's power consumption from a software management perspective. However, some do that based on simulation techniques variables. For example, they analyze previous physical measurements and specific hard drive's working states (rotation, writing, reading, etc.) [START_REF] Zedlewski | Modeling Hard-Disk Power Consumption[END_REF], the application's execution stages considering I/O operations [START_REF] Zhang | mqSim: Enabling Accurate and Scalable Simulation for Interactive Microservices[END_REF], etc. On the other hand, others offer energy models using different approaches. For example, they analyze the cost of virtual machines deployment [START_REF] Roose | Prediction & Modeling energy consumption for IT Data Center Infrastructure[END_REF], the size of in-disk files accessed by concurrent processes [START_REF] Inoue | A Power Consumption Model for Storage-based Applications[END_REF], and others.

From an optimization point of view, most works study how to handle disk accesses efficiently. For instance, some increase applications' execution efficiency through intelligent scheduling of I/O requests [START_REF] Corral | Energy-aware Performance Evaluation of Android Custom Kernels[END_REF]. Other works reduce power consumption by caching/buffering processes' [START_REF] Chen | Caching for Bursts (C-Burst): Let Hard Disks Sleep Well and Work Energetically[END_REF] or virtual machines' [START_REF] Ye | Energyefficient Storage in Virtual Machine Environments[END_REF] disk accesses in a coordinated way. This last strategy allows the storage device to remain idle or sleep for the necessary time to meet energy savings.

Finally, the Table 2.6 summarizes the techniques described up to this point. As with the NIC, we couldn't implement any of these approaches with the values obtained from OS interfaces. The following section then explains this fact and our own consumption model.

Proposal to measure the Storage Device power

consumption from the perspective of distributed algorithms: Analyzing a process from the moment it is executed and when it is already running

As we said in the previous section, we haven't found any approaches that we can implement via OS interfaces. Furthermore, the methods described in the table 2.6 analyze variables such as the size of files managed by applications or the I/O operations they perform. Both are outside the scope of our study.

Chapter 2

Profiling applications' power consumption For the mentioned reasons, we propose a model based on the power consumption that the hard drive generates when it is in the active (performing read or write operations) or idle state.

Our model is similar to the equation 2.5 for the NIC. To find the hard-drive energy consumption, we establish the 𝑊 𝑢 𝐷 and 𝑊 𝑖 𝐷 values that represent the power expenditure when a device's (𝐷) hard drive is in an active and idle state. Then, for a current transfer rate 𝐿 𝐷 , 𝑊 𝑢 𝐷 multiplies 𝐿 𝐷 relatively to the maximum transfer capacity 𝐿 𝑀𝐴𝑋 𝐷 . Next, we add this result to the idle state consumption. For that, 𝑊 𝑖 𝐷 multiplies the complement of the hard drive load (i.e. 𝐿 𝑀𝐴𝑋 𝐷 -𝐿 𝐷 ) relatively to 𝐿 𝑀𝐴𝑋 𝐷 . Finally, we consider a time 𝑇 to obtain the disk's energy consumption in joules (Watts*s), as the equation 2.9 shows.

𝐸 𝐻 𝐷 𝐷 = (𝑊 𝑢 𝐷 × 𝐿 𝐷 𝐿 𝑀𝐴𝑋 𝐷 + 𝑊 𝑖 𝐷 × 𝐿 𝑀𝐴𝑋 𝐷 -𝐿 𝐷 𝐿 𝑀𝐴𝑋 𝐷 ) × 𝑇 𝐷 (2.9)
Then, to define the energy consumption (𝐸 𝐻 𝐷 𝐷 𝑀 ) that a process 𝑀 generates on the hard drive, we use the equation 2.9; but only consider the load generated by 𝑀 (𝐿 𝑀 ) relatively to 𝐿 𝑀𝐴𝑋 𝐷 .

As in the case of the network card, we consider the idle time independent of the processes and exclusive to the hard drive background consumption. Thereby, a process power consumption depends exclusively on its operations on the hard drive, as seen in the formula 2.10.

𝐸 𝐻 𝐷 𝐷 𝑀 = (𝑊 𝑢 𝐷 × 𝐿 𝑀 𝐿 𝑀𝐴𝑋 𝐷 ) × 𝑇 𝐷 (2.10)
Concerning the formula's factors sources, we have not found a GNU/Linux interface for the 𝑊 𝑢 𝐷 , 𝑊 𝑖 𝐷 and 𝐿 𝑀𝐴𝑋 𝐷 values. However, many HDD and SSD brands specify them in datasheets [195] [START_REF] Samsung | Samsung V-NAND SSD 860 EVO[END_REF]. Furthermore, the transfer rate generated by a process on the hard drive can be obtained from programs such as iotop[179].

Chapter Summary and Contributions

In this chapter, we have explained how various authors find and optimize the power consumption of the CPU, the RAM, the NIC, and the storage device. We have organized these approaches from a perspective of 1) hardware and operating system configuration, 2) software design and development, 3) application launching, and 4) applications already running.

The last two perspectives are compatible with our distributed algorithms' logic. For that reason, we have studied, adapted existing approaches, and proposed (if

Chapter 2
Profiling applications' power consumption concerned) our own mathematical models to describe the energy consumption of each of these components. Thereby, for the CPU and the RAM, we have selected and adapted already tested formulas to relate their workload, power state, and their power consumption. Finally, considering the same relation, we have proposed and tested our own energy consumption models for the storage device and the NIC.

It is important to say that each model's parameters' values can be obtained from different GNU/Linux interfaces (such as APIs, specialized programs, and others). In this chapter, we have described the still maintained and documented ones.

The next chapter studies and classifies important distributed scheduling approaches, detailing their operations, input variables, objectives, abstraction level, etc. As well as the models above, that study will be an input criterion for our scheduling approaches presented later in this thesis. The Distributed Approach

Introduction

A few decades ago, traditional applications used to be only conceived in a traditional monolithic way. In this manner, all the development processes and deployment strategies considered only a single host. At runtime, monolithic applications' internals communicate with each other using method invocations or function calls to produce specific results. In this process, the operating system is the entity that manages the required access time to each hardware resource, such as CPU, RAM, etc [START_REF] Tanenbaum | Modern Operating Systems. 4th[END_REF].

Although this approach is still suitable for applications such as a kernel [START_REF] Tanenbaum | Modern Operating Systems. 4th[END_REF], more modular approaches are needed today. For example, applications such as Netflix, eBay, or Zalando engines[137] require performing massive data queries and having the independence of location and platform to work. Thereby, for them, a monolithic approach would present serious disadvantages such as unmanageable scalability, low cohesion, and high coupling [START_REF] Deshpande | Challenges and patterns for modernizing a monolithic application into microservices[END_REF]. In addition, there are scenarios where several nodes must interact to produce a result or satisfy a specific user's needs. That's the case of horizontal ambients such as sensor networks [START_REF] Pilloni | Deployment of Distributed Applications in Wireless Sensor Networks[END_REF] or user device networks [START_REF] Da | Kalimucho: Middleware for Mobile Applications[END_REF]. For these two reasons, the conception and-or the deployment processes are carried out through distributed systems.

A distributed system is defined by Tanenbaum et al. [START_REF] Steen | A Brief Introduction to Distributed Systems[END_REF] as a collection of autonomous computing elements (in fact, software or hardware components) that appears to its users as a single coherent system. In their article, the authors explain that for a system to be distributed, it needs to meet some characteristics:

• Node autonomy: Each component fulfills its independent task and communicates with other peers using methods such as message passing. Therefore, they work concurrently without sharing a global clock or shared memory [START_REF] Nazimzada | Distributed Systems & Distributed Computing[END_REF].

• Single coherent system: The set of components behaves transparently according to the users' interaction level and expectations. That is, preventing them from knowing and managing the system's architectural characteristics that they don't need to know.

Chapter 3

The Distributed Approach

Thereby, from an architectural point of view and depending on the user's role, it is required: 1) to know and or be able to manage the network architecture (often an overlay) and 2) to have a technology that allows, among others (execute security services, establish the communication between processes, etc.), executing scheduling operations to manage the nodes' hardware resources. This technology is known as middleware.

Several industrial technologies and authors use said scheduling operations to achieve different objectives. For example, as it is possible to see in some surveys [START_REF] Zhong | Machine Learning-Based Orchestration of Containers: A Taxonomy and Future Directions[END_REF] [START_REF] Ren | A Survey on End-Edge-Cloud Orchestrated Network Computing Paradigms: Transparent Computing, Mobile Edge Computing, Fog Computing, and Cloudlet[END_REF][175] [START_REF] Ren | A Survey on End-Edge-Cloud Orchestrated Network Computing Paradigms: Transparent Computing, Mobile Edge Computing, Fog Computing, and Cloudlet[END_REF][152], these objectives take into account variables such as centralized/non-centralized heuristics, mathematical/artificial intelligence approaches, types of application and virtualization, etc. All this is to optimize the deployment of applications time, energy consumption, load balancing, SLA assurance, etc. However, few of them prioritize power consumption as one of their main goals. As we will show in the following sections, they do not consider energy-based scheduling analyzing variables such as hardware heterogeneity, smart resources indexing, or special hardware power capabilities.

[228][236][4][43]
In this thesis work, we analyze and improve nodes' hardware resource management in a novel way to save energy without losing the notion of QoS (Quality of Service). We schedule (middleware operations: move, duplicate, start, stop) the components that make up a distributed application through different physical nodes using multidimensional/spatial special structures. With them, we index elements such as physical nodes and applications' components at execution time according to multiple criteria, such as the current availability of hardware resources, hardware's power-related features, or the application's resource requirements. This way, our objective is to have a system that performs the elements' search, insertion, and elimination at an efficient computational cost in order to perform energy-saving scheduling strategies.

The explanation of this entire strategy is the cornerstone of our next chapter. However, to justify and contrast it, we present an analysis of the state of art in the present chapter, proposing a taxonomy of different scheduling techniques that we consider important.

In the next section, we will explain the methodology that defines the structure of the rest of the document.

Methodology

This chapter analyzes the state of the art of distributed software components deployment and scheduling techniques. To easily contrast this analysis with our Methodology Section 3.2 proposal (briefly described in the previous paragraph), we present an algorithmicbased taxonomy that considers two scheduling moments:

• Initial deployment, which studies the correct nodes to deploy a software component, and

• Execution-time scheduling, which involves operations such as migration or duplication.

For each of these moments, we describe several approaches which may span one or multiple proposals in the form of an algorithmic flow. That means we analyze the concerning input variables, the operations that are executed, the method's heuristic (centralized and non-centralized), and the optimized variables.

Finally, as it is possible to see in figure 3.1, we consider it important to show the potential extensibility of our proposal. That's why we explain the mentioned moments and flows considering two different levels of abstraction: Scheduling in the cloud and Scheduling close to data sources which involve approaches such as grid computing, edge computing, and fog computing. In both sections, we analyze only the approaches that we consider important from the current state of the art. For that, we have filtered the research/industrial works considering particularity, popularity, or topicality criteria.

Chapter 3

The Distributed Approach Our objective with this sample is to show the algorithms' trends in terms of the criteria they evaluate and the variables they optimize. To do that, we build two descriptive tables for each section: one for the analysis of the initial deployment approaches and another for the execution-time scheduling ones. Next, we have converted the number of approaches that coincide at each table point (inputoptimized variable) in a ranking system that shows average trends. Finally, we deliberately score our work to compare it with the mentioned trends, evidencing the field of action of our contribution and its strengths.

It is important to emphasize that the scores do not represent the quality of the analyzed approaches. They only show optimization trends useful to define our proposal scope.

We finish the chapter by explaining the corresponding conclusions and contributions in section 3.5.

Scheduling in the cloud: Managing virtual

entities in node clusters.

Cloud computing (whether public, private, or hybrid) is the on-demand availability of computing resources as services over the Internet (enabling the pay-per-use basis). These services are usually offered under three different models: 1) IaaS (Infrastructure as a service), which offers servers, storage, networking resources, etc., 2) PaaS (Platform as a service), which offers a develop-and-deploy environment to build cloud apps, comprising middlewares instances, development tools, data management systems, among others, and 3) SaaS (software as a service) which delivers applications functionalities as services to end users [START_REF]What is cloud computing?[END_REF][162][163][164]. All these services comprise and-or manage applications deployed on clusters. By definition, a cluster consists of a set of nodes (from personal computers to super servers) connected through the network. They work together to perform common tasks providing fast processing speed, large storage capacity, efficient data integrity, reliability, and wide availability of resources [START_REF]Definition Computer Cluster[END_REF]. Depending on the technology and its objectives (such as load balancing or high availability), a cluster can cover one or different geographical areas [START_REF] Docs | Running in multiple zones[END_REF] [START_REF]Choosing regions and availability zones[END_REF].

As in several distributed environments, in cloud computing systems, two problems must be solved when deploying applications and-or performing scheduling operations: 1) The independence of applications instances concerning a specific platform/operating system, and 2) the control of the resources quotas given to them. Both are solved by isolating these hardware resources (CPU time, RAM quantity, Scheduling in the cloud: Managing virtual entities in node clusters. Section 3.3 etc.) and needed software (dependencies) in virtual execution environments. Depending on their operation and isolation level, they can be differentiated into VM (virtual machines) and containers [START_REF]Containers vs VM, what is the difference?[END_REF].

• When using VMs, an entity called a "hypervisor" virtualizes each of the hardware components for complete instances of operating systems. Depending on its type, a hypervisor can run 1) directly on the hardware (type 1), serving as a lower abstraction layer than any operating system, or 2) as an application in a pre-existing operating system [START_REF]Hypervisors[END_REF].

• When using containers, virtualization occurs using the kernel features of the host operating system. For this, the kernel isolates the processes of the virtualized applications in user-spaces-like systems by means of namespaces and CGROUPS. Moreover, they keep the involved dependencies (libraries, executables, etc.) described in a file and deployed in a folder hierarchy [92][9][213].

Typically, the cloud systems' engines schedule [START_REF]Migrating Virtual Machines[END_REF][12](i.e., deploy, migrate, start, stop) both of these technologies to fulfill the different providers' objectives related to their offered services (IaaS, PaaS, Saas). This process seeks to make the best possible use of the nodes' hardware resources to achieve the desired QoS (quality of service) while being frugal, both money and energy-wise. In this statement, it's important to mention that although it may have different definitions, the QoS is usually approached as the time taken to process a hardware resource request [START_REF] Lin | Integrating QoS awareness with virtualization in cloud computing systems for delay-sensitive applications[END_REF].

On the other hand, some scientific works optimize virtual entities' (re)deployment to improve and adapt the scheduling processes to emerging architectures. For example, to optimize the VMs deployment, some papers propose the proper, dynamic (resources capacities and duration) and anticipated creation of VMs based on the historical scheduling data [START_REF] Zhang | Dynamic Cloud Task Scheduling Based on a Two-Stage Strategy[END_REF], the applications' workflow [START_REF] Rodriguez | Deadline Based Resource Provisioning and Scheduling Algorithm for Scientific Workflows on Clouds[END_REF], and the type of the involved tasks [START_REF] Zhang | Dynamic Cloud Task Scheduling Based on a Two-Stage Strategy[END_REF] [START_REF] Rodriguez | Deadline Based Resource Provisioning and Scheduling Algorithm for Scientific Workflows on Clouds[END_REF]. Other works make use of external/internal clouds resources (hybrid cloud) to deploy tasks based on internal VMs' overload situations, energy/cost considerations, tasks' delay bounds, and learning methods [START_REF] Zuo | Self-Adaptive Learning PSO-Based Deadline Constrained Task Scheduling for Hybrid IaaS Cloud[END_REF][241] [START_REF] Pop | Reputation Guided Genetic Scheduling Algorithm for Independent Tasks in Interclouds Environments[END_REF]. For their part, other approaches argue for applying linear programming models and graph theory to optimize the VMs deployment, taking into account variables such as VMs' resources requirements, resources availability, non-sliceable resources management, and in-host VM interference [START_REF] Lin | Integrating QoS awareness with virtualization in cloud computing systems for delay-sensitive applications[END_REF].

Furthermore, some approaches rely on serverless networks, such as the one proposed by Kirschnick et al. [START_REF] Kirschnick | Towards an Architecture for Deploying Elastic Services in the Cloud[END_REF]. They propose a deployment architecture in decentralized networks of nodes/VMS. Herein, in any node that executes the system service, the user must provide the system specification considering the Chapter 3

The Distributed Approach desired application with its service dependencies. Then, the algorithm running in this initial node performs a breadth search to determine which peers/VMs can run the described software components. Finally, the system starts working when the initial node receives a positive notification of all the concerning peers.

In addition to studying the initial deployment, other approaches analyze different ways to perform execution-time scheduling operations. For example, Beenish et al. [START_REF] Gul | CPU and RAM Energy-Based SLA-Aware Workload Consolidation Techniques for Clouds[END_REF] migrate VMs to avoid overload situations and to shut down nodes in underload situations. For that, they consider thresholds in terms of RAM and CPU. Furthermore, they execute a matching algorithm based on the first elements of two lists to perform an energy-efficient deployment. On the one hand, VMs ordered in decreasing order considering their CPU requirements. On the other hand, a list of nodes in decreasing order considering their CPU MaxCapacity/Utilization Level and their peak/current energy expenditure. This algorithm has an algorithmic complexity of 𝑂 (𝑛𝑁𝑜𝑑𝑒𝑠 × log(𝑛𝑁𝑜𝑑𝑒𝑠)

+ 𝑑𝑒𝑝𝑙𝑜𝑦𝑇𝑖𝑚𝑒 + 𝑛𝑉 𝑀𝑠 × log(𝑉 𝑀𝑠)).
Another interesting approach is the one proposed by Zhu et al. [START_REF] Zhu | Real-Time Tasks Oriented Energy-Aware Scheduling in Virtualized Clouds[END_REF]. They use the rolling-horizon (in fact, planning ahead) optimization for task scheduling in the cloud. For this, the authors sort the tasks according to their deadlines. Then, they determine in advance whether or not a task can be properly terminated considering the current hardware resources of the deployed VMs in a set of nodes. If there are no candidates, the concerning nodes are load-balanced by performing VMs migration-to-create to retry the task deployment.

It is important to say that this entire process considers optimizing energy consumption. On the one hand, the deployment strategy selects the VM currently yielding minimal CPU energy consumption to execute tasks. On the other hand, it frees up hosts to shut down in a process called scale down. For the latter, the algorithm matches VMs -nodes by sorting the source hosts (hosts to free) by their CPU utilization in increasing order and the destination hosts oppositely. The entire task allocation process and the scale down operations have a complexity of 𝑂 (𝑁 + 𝑁 × log(𝑁 )) and 𝑂 (𝑁 2 ) respectively.

In the same line of thought, many works seek to optimize the initial deployment and the execution-time scheduling through learning techniques. For the initial deployment, they focus on characterizing task types for scheduling monolithic or modular applications in hybrid or single clouds. In general, they analyze the applications' consumption history and their resource behavior variation to predict when, how often, and what resources they will need. Then, for the execution-time scheduling, they use the same variables in order to predict scaling (duplicate, close) and migration operations. All these procedures aim to optimize load balancing, monetary expenditures, system scalability, hardware resource usage, and service level agreement assurance [START_REF] Zhong | Machine Learning-Based Orchestration of Containers: A Taxonomy and Future Directions[END_REF]. For instance, Zhiheng et al. [START_REF] Zhong | Heterogeneous Task Co-location in Containerized Cloud Computing Environments[END_REF] Scheduling in the cloud: Managing virtual entities in node clusters. apply the k-means algorithm to classify tasks based on CPU, RAM, network, and storage consumption. They then deploy long-running and short-running applications, taking into account idle resources and ranking functions such as the Least Requested priority (lowest resource utilization first). Then, for executiontime scheduling, they use the Shortest Runtime Rescheduling algorithm to move the lightest application that has been running for the shortest time, thus ensuring a reduced impact on the QoS. For its part, the approach of Haitao et al. [START_REF] Zhang | Container Based Video Surveillance Cloud Service with Fine-Grained Resource Provisioning[END_REF] is also based on the prediction of resources for the deployment and migration (for them, destroy and redeploy) of containers for video processing. For this, they use service similarity matching and a time-series nearest neighbor regression on the consumption data of the corresponding containers.

[245] [192] X X X X [252] [241] [185] X X X X X X [143] X X X X [89] X X X X [251] X X X X X [78] [76] [82] X X X X Our work X X X X X X
Other works seek to migrate virtual machines, especially for energy-saving purposes. For instance, Azmy et al. [START_REF] Nour | Adaptive Power Panel of Cloud Computing Controlling Cloud Power Consumption[END_REF] create a power panel that defines the cluster's power states. On the one hand, these states consider VMs' allocation policies based on thresholds or medians. On the other hand, they consider migration policies such as the Maximum Correlation policy (VMs that consume the most in the host), Minimum migration time policy, and Random selection policy. The authors' objectives are to avoid physical nodes' overload conditions and/or achieve underload hosts shutdown. Similarly, Siddavatam et al. [START_REF] Siddavatam | Optimization of Load Balancing Algorithm for Green IT[END_REF] using a similar migration strategy, but based only on CPU usage. For their part, Pawlish et al. [START_REF] Pawlish | A Call for Energy Efficiency in Data Centers[END_REF] aim to avoid overhead costs. They migrate tasks from local data centers to clouds if the average CPU load of its nodes is greater than a certain percentage threshold. On the other hand, important companies have developed technologies that optimally manage the clusters' hardware resources to achieve specific objectives. For instance, several of them seek to improve massive data processing in parallel using nodes in a structured way. That is the case for those who use the MapReduce paradigm. It uses hash operations to parallel distribute and process data of common characteristics in common nodes known as mappers and reducers. Here, the containerized tasks' execution order and the corresponding resources allocation can be based on structured methods. For example, in the FIFO approach, each task is executed by priority and in order of arrival. On the other hand, the faircapacity scheduling creates different queues of tasks, assigning them a proportional, convenient, and fixed amount of resources [START_REF]Fair Scheduler[END_REF][76] [START_REF] Gandomi | HybSMRP: a hybrid scheduling algorithm in Hadoop MapReduce framework[END_REF].

As another example, one of the best-known technologies for container management is Docker. This platform allows developers to easily deploy, edit or delete their applications in GNU/Linux-based containers [203]. Docker schedules con-

X X X [251] X X X X [136] X X X X Linear search [248] X X X X [14] [198] X X [250] [244] X X X X X X [249] X X X [203] X X X X Our work X X X X X X
Table 3.6: Cloud execution-time approaches: Target Variables tainers on a cluster's physical nodes using tools like Docker Swarm. This tool offers centralized algorithms for cluster management such as automatic load balancing, high availability, scalability, roll-back execution, etc. In general, for the initial deployment of a container, the manager device supports by default three approaches based on resources and the number of containers: 1) The random selection of a node that contains enough resources, 2) the selection of nodes with more containers to avoid application fragmentation and 3) The choice of nodes with fewer containers to improve load balancing. Then, in order to maintain proper load balancing and high availability, Docker Swarm destroys containers and redeploys them on nodes with sufficient hardware resources. Swarm allows developers to define their own reschedule policies [8][20].

Kubernetes, for his part, groups containerized tasks in entities called PODs. Then, it seeks to schedule PODs on physical nodes or VMs according to the tasks' constraints and/or specifications. For that, Kubernetes uses 1) Strong task constraints, with which the scheduler filters available nodes by creating a list of candidates, and 2) Soft task constraints, with which the scheduler scores and sorts the mentioned list especially considering nodes CPU and RAM. Here, the first element in the list is the node on which the task will run[136] [START_REF]How the Kubernetes scheduler works[END_REF]. Also, it is Scheduling in the cloud: Managing virtual entities in node clusters.

Section 3.3 important to say that to perform execution-time scheduling on PODs (migrate or duplicate), Kubernetes uses a controller called ReplicaSet. This special process monitors the PODs' status based on a linear search of all their instances identified with certain labels in the entire cluster [135]. Finally, Kubernetes allows running different PODs-node matching criteria such as affinity, selectors, tolerances, or taints.

It is important to mention that some scientific works seek to improve certain Kubernetes methods. For example, some approaches avoid the execution of the scheduling algorithm when there is only one node. They consider additional score criteria such as network bandwidth, disk storage [START_REF] Zhiyong | An Improved Container Cloud Resource Scheduling Strategy[END_REF], and GPU [START_REF] Ting-An | KubeShare: A Framework to Manage GPUs as First-Class and Shared Resources in Container Cloud[END_REF]. Other works improve the Kubernetes scheduling by scaling the multi-resource approach to the multi-clusters environments [START_REF] Lee | Scheduler for Distributed and Collaborative Container Clusters Based on Multi-Resource Metric[END_REF]. On the other hand, some authors use the Kubernetes base system to create different services and reimplement the default scheduling approach. These services aim to execute different complex deployment and in-execution heuristics.

An important example of the last point is the one proposed by Zhiheng et al. [START_REF] Zhong | A Cost-Efficient Container Orchestration Strategy in Kubernetes-Based Cloud Computing Infrastructures with Heterogeneous Resources[END_REF]. They implement four entities to perform scheduling approaches: 1) The Resource Profiler, which maintains an updated snapshot of VMs and tasks, 2) the Cloud Adaptor, which performs the deployment and migration operations, 3) the Task Packer entity, which makes scheduling decisions, and 4) the Instance cleaner which maintains only useful instances alive.

In their system, the authors ensure that migrations are executed while maintaining the running state of the containers. On the other hand, they achieve intelligent scheduling and elastic clusters by creating special entities and services. For that, they predict the execution time of the tasks to be deployed and group them into two sets: 1) Permanent execution tasks (long-running) and 2) temporary execution tasks (batch jobs). Then, they deploy the first group to nodes that imply low energy and monetary cost (time cost per billing) and the second group to nodes with convenient hardware features. Thereby, to treat the temporary execution tasks, they arrange each POD to the most utilized node instance with enough requested resources in terms of CPU, RAM, and execution time. Then, to scale and shut down some nodes, they select those being used at less than 50% capacity. The algorithm releases them using migration operations considering virtualized images, execution time, and available bandwidth.

It is important to say that the authors show a linear algorithmic complexity for their deployment and scaling algorithm.

On the other hand, some technologies dynamically manage the different physical nodes used/shared by different cluster schedulers from a higher level of abstraction. That is the case with the Apache Mesos [START_REF]What is Mesos? A distributed systems kernel[END_REF] distributed kernel. Using a master

Chapter 3

The Distributed Approach entity, Mesos receives the available resources from each physical node and manages them among the different running cluster schedulers (two-level scheduling) [START_REF] Greenberg | Mesos: The Operating System for your Cluster[END_REF]. For that, Mesos utilizes the DRF [START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Multiple Resource Types[END_REF] (Dominant Resource Fairness) algorithm by default. It uses linear equations to ensure that: For each (non)containerized (default: Mesos container) task, the percentage of its dominant resource (the most demanded one) type that it gets cluster-wide is the same for all other tasks [START_REF]Mesos Allocation Modules[END_REF].

It's important to mention that some technologies enrich the Mesos scheduling approach. For instance, Aurora [START_REF]Apache Aurora: Scheduler Configuration[END_REF] runs on the top of Mesos kernel in order to perform containerized task grouping, scalability operations, set replica criteria, etc. For its part, Marathon [START_REF]Marathon: A container orchestration platform for Mesos and DC/OS[END_REF] is able to launch tasks at the desired times using the Chronos scheduler [START_REF]Chronos: A fault tolerant job scheduler for Mesos[END_REF].

Following the same goals as Kubernetes or Swarm, some scientific works seek to efficiently schedule containers in hardware resources [START_REF] Ahmad | Container scheduling techniques: A Survey and assessment[END_REF]. For example, Rodrigues et al. [START_REF] Rodrigues | Network-Aware Container Scheduling in Multi-Tenant Data Center[END_REF] optimize container deployment through Mixed Integer Linear Programming. For this, they study the graph of physical nodes of a cluster, and the graph made up of the connected containers deployed in it. Regarding resources, they analyze the RAM, the CPU, and the transfer rate involved in both graphs to create weights for each edge and vertex. Then, they determine the most optimal deployment by minimizing an objective function that considers the quality of service and energy consumption. Another interesting approach is the one proposed by Pongsakorn et al. [START_REF] Pongsakorn U-Chupala | Container Rebalancing: Towards Proactive Linux Containers Placement Optimization in a Data Center[END_REF]. They focus on container migration based on four stages. First, classify containers into groups of high and low duration. Secondly, group the long-lived containers based on their allocated resources and hosts. Next, on the one hand, find a pair of hosts whose difference in resource usage is significant. On the other hand, select the containers whose difference between allocated and used resources is also significant. Last, perform a swap of both containers to balance the load.

Finally, another group of works seeks to optimize the communication between deployed tasks. For example, Wu et al. [START_REF] Wu | Distributed Online Scheduling and Routing of Multicast-Oriented Tasks for Profit-Driven Cloud Computing[END_REF], in addition to a redeployment algorithm, they propose a routing improvement of multicast tasks in data centers of different zones based on optimization techniques. This area of study is beyond the scope of our research work.

Analysis and considerations

So far, we have explained some works whose objective is to figure out the convenient initial deployment and in-execution scheduling of virtual entities in cloud clusters. We have selected and analyzed several approaches proposed by Scheduling in the cloud: Managing virtual entities in node clusters. Section 3.3 scientists and applied by well-known platforms and tools. We believe that overall, the approaches analyzed here represent a strong trend of approaches today.

Following the methodology described in section 3.2, we study this trend from an algorithmic approach. To do that, in Table 3.1, 3.2, 3.3 and 3.4 (Tables 3.3 and3 Then, in Tables 3.5 and 3.6, we characterize the works concerning executiontime scheduling considering the same analysis fields. As shown in Figure 3.2, most works are based on pre-processing techniques to deploy a software component ideally. In our case, our goal is not to ensure the best possible initial deployment. Instead, we use a distributed data structure to have a stable system, which on the one hand, is reactive to hardware load changes, and on the other hand, does not need to perform expensive calculations to work.

Then, most approaches do not consider the power characteristics of several hardware components to perform scheduling decisions. For our part, we believe that we can profile hardware and software components from mathematical models and operating system interfaces (see chapter 2). That allows us to have a more extensible and clear view of a system's energy consumption. For example, we Chapter 3

The Distributed Approach study the CPU, RAM, network, and storage components' features to perform our scheduling algorithm.

Next, we can see that most works use centralized models to schedule. That is due to ease of components control, stability, and scalability, among other reasons [START_REF] Netflix | Netflix Conductor: A microservices orchestrator[END_REF]. About this point, we believe in the elasticity of structured environments. Thereby, although centralized distributed multidimensional data structures are applicable for scheduling, we have preferred to implement our algorithm in a P2P system. In addition to validating it for different deployment levels (cloud, grid, etc.), our goal is to demonstrate that said architecture is an excellent candidate for energy savings purposes. Moreover, we believe that P2P networks in the cloud would offer many advantages such as security, privacy, autonomy, etc.

Finally, most works do not consider the computational cost of their algorithms. In our case, we consider it important since our approach's algorithmic behavior is reflected in the number of network operations. On the other hand, Figure 3.3 shows the trend of the approaches' analyzed / optimized variables. Here, most of the works seek to correctly manage hardware resources to mainly improve scalability, quality of service, monetary costs, and the efficient deployment of applications.

For us, our main objective is to save energy without losing the notion of quality

Scheduling in the cloud: Managing virtual entities in node clusters.

Section 3.3 of service. To do this, we efficiently use multidimensional data structures based on a correct analysis of hardware resources load. Furthermore, our technique allows us to consider all the other variables indirectly. For example, the scalability of our approach is addressed in the overlay used; the deployment time depends on the nature of the data structure; the monetary costs are related to power consumption, and the high availability is related to the mirroring operations we consider. Regarding the execution time scheduling, in Figure 3.4, we show that, unlike the initial deployment stage, most works do not base their approaches on preprocessing operations. We believe this is because migration scenarios tend to be much more dynamic and less predictable. Another significant difference is a major concern here for the computational cost. We believe that this is because the number of operations through the network influences energy consumption, quality of service, and others.

We address both aspects with the efficient use of spatial data structures since it allows us to analyze computational costs and maintain a dynamic system. The analysis of the rest of the variables is the same as we did for Figure 3.2.

Regarding the trend of the analyzed / optimized variables at the executiontime scheduling, Figure 3.5 shows that, unlike the initial deployment, the works have a higher tendency to evaluate the energy consumption and scalability variables.

In our case, energy consumption is our primary objective. However, we indirectly manage the system's scalability performance through our chosen data structure. We analyze the rest of the variables in the same way as we did for figure 3.3.

Chapter 3

The Distributed Approach The next section analyzes several works that seek to optimize the initial deployment and the in-execution scheduling in devices beyond the cloud.

Scheduling close to data sources.

As seen in the previous section, cloud computing studies data processing and the execution of different workloads in clusters of (generally) homogeneous nodes. However, these nodes, usually located in data centers, are often physically far from the concerning data sources. This fact represents a load management problem since, as mentioned in IEEE innovation[102], more and more connected devices generate data to process. For instance, billions of them generated an unprecedented amount of data in the last year, increasing the difficulty of managing bandwidth (despite 5g, network capability is still heterogeneous globally), energy consumption, and computing resources are growing [102].

For these reasons, scientists and enterprises developed different systems hierarchies. They seek to take advantage of the computational capabilities of nodes closer to the data and workloads sources. That is the case of edge, fog, and grid computing.

Regarding the definitions of each, some scientists consider the first two as syn-

Scheduling close to data sources.

Section 3.4

onyms [175][96]. For them, both approaches consist of processing workloads considering two types of closeness. On the one hand, closeness to the concerning data source. On the other hand, closeness to where the actions related to that data are taken [START_REF]IBM Edge Computing for Servers[END_REF]. Others, however, define them differently [101]. They mention that one (fog or edge) is a kind of interface between edge devices and the cloud.

Concerning grid computing, we did not find a universal definition either. Some authors define it as a paradigm in which heterogeneous devices connected from different places perform tasks without centralized control [17][117].

This section indistinctly analyzes the works that study scheduling techniques in these three areas. The reason is that, unlike the cloud level, the three involve the management of software components in probably very heterogeneous hardware, in much more diverse and probably dynamic [START_REF] Charântola | Component-Based Scheduling for Fog Computing[END_REF] locations, and with a greater tendency towards decentralized philosophies. To do said analysis, this section applies the chapter's methodology, studying the techniques concerning the initial deployment and the execution-time scheduling phases.

Among the works mentioned in the previous paragraph, some focus on improving the overall performance of applications running on heterogeneous devices. For example, Manjot [START_REF] Bhatia | RR Based Grid Scheduling Algorithm[END_REF] seeks to achieve this goal by improving the tasks' initial deployment process. For this, he maintains a centralized entity that stores all the memory and CPU characteristics of the involved nodes. He then displays each task considering two perspectives: 1) a first-come, first-served basis or 2) applying a heuristic based on the time a task waits for a resource, the time that task typically uses that resource, and the completion time of the job.

Studying the same objective, Chauhan et al. [START_REF] Chauhan | Decentralized Scheduling Algorithm for DAG Based Tasks on P2P Grid[END_REF] conceive a dependencies-based application as a directed acyclic graph and a set of nodes as a structured overlay. Using these, they propose a fully decentralized scheduling algorithm that aims to execute in parallel the largest number of application modules of the same dependencies level. This algorithm maintains two types of information in the node which starts an application (it can be any node on the network): 1) A table with information on its neighbors such as name, IP, CPU MPIS, running tasks and subtasks, etc., and 2) the execution characteristics of the application. Then, the node deploys either any task of the same level of dependencies or the longest task of a higher level of dependencies on the most suitable node. This selection considers the peer's load, processing capacity, task dispatch time, previous processing information, etc. For this, the authors propose heuristics based on weights.

In another of their works, the authors use similar heuristics to implement high availability strategies. In them, the nodes monitor their neighbors to check that they are still working. If this is not the case, the involved task list is forwarded to available nodes, and their corresponding tables are updated accordingly [START_REF] Chauhan | Fault Tolerant Decentralized Scheduling Algorithm for P2P Grid[END_REF].

Chapter 3

The Distributed Approach

In addition to improving application performance, other researchers consider maintaining the network balance during the initial deployment process. For example, Dias et al. [START_REF] Augusto | Improving Container Deployment in Edge Computing Using the Infrastructure Aware Scheduling Algorithm[END_REF] choose the best node to deploy an application from a central entity. To do that, they consider variables such as deployment time, download queue, and bandwidth involved. For their part, Drost et al. [START_REF] Drost | Simple locality-aware co-allocation in peer-to-peer supercomputing[END_REF] execute in parallel the tasks started at a node of a decentralized network. For that, the initial node broadcasts with a specified depth looking for a peer with the necessary resources to execute one of the tasks. The nodes that have such resources accept the request. Those who do not, as well as those who receive the request twice, deny it. The algorithm achieves the network balance considering the physically closest candidates to the origin node. Finally, pursuing the same goal, Maheswaran et al. [START_REF] Fadahunsi | Locality Sensitive Request Distribution for Fog and Cloud Servers[END_REF] make a device capable of connecting to several fogs that can fulfill their workloads. The algorithm approach considers the criteria of resource availability and network latency.

Otherwise, some works base their deployment approaches on learning techniques. For example, Lordache et al. [START_REF] Iordache | A Decentralized Strategy for Genetic Scheduling in Heterogeneous Environments[END_REF] consider a set of nodes capable of executing the tasks to be deployed and/or executing scheduling operations based on genetic algorithms. Thereby, each node works as an agent that can process/designate tasks on the same processor unless they have exclusivity restrictions. Then, the first population is initialized stochastically, and the tasks are assigned to specific processors. Thereupon, the deployment space is explored by starting chromosomes using random generators. Here, 1) each agent displays different probability distributions such as normal or Poisson, and 2) the fitness function is defined by the number of processors and the total execution time of all tasks assigned (previous and current) to each processor. For their part, Toka et al. [START_REF] Toka | Machine Learning-Based Scaling Management for Kubernetes Edge Clusters[END_REF] focus on improving the horizontal scaling of Kubernetes edge clusters (explained in the previous section). To achieve this, instead of relying on the current scaling period's observations, the authors perform scaling decisions based on machine learning algorithms. These analyze request intensity over time, considering the CPU as the main component.

Besides studying the deployment of processes, other types of work focus on improving the localization of data to process. For example, Neumann [START_REF] Neumann | STACEE: Enhancing Storage Clouds Using Edge Devices[END_REF] et al. propose an architecture for P2P networks called STACEE. In it, smart services enable data characterization based on its lifetime, intermittency, and access quantity. It allows the definition of treatment metrics based on monetary costs, energy consumption, or data proximity. Furthermore, STACEE offers an objective-functions minimization model, which comprises variables of existing hardware (energy costs, CPU available, prices, et.) and customer requirements (content size, release date, distance, et.). All this aims to deploy and migrate data and processes optimally.

For their part, other works improve data access and management through clus-Section 3.4

tering techniques [START_REF] Azimi | Distributed Data Clustering in Peer-to-Peer Networks: A Technical Review[END_REF]. For example, Li et al. [START_REF] Li | PENS: An Algorithm for Density-Based Clustering in Peer-to-Peer Systems[END_REF] proposes that all the nodes of a P2P network are indexed in a multi-dimensional Cartesian plane divided into zones. For that, one or more peers have the bits-string-based metadata of each zone. Then, the latter are grouped hierarchically (clustering process) so that the whole network is seen as a binary tree for efficient queries. This tree is known as VPTree.

Finally, other scientists focus on optimizing data caching on edge devices. About this point, Shuja et al. [START_REF] Shuja | Applying machine learning techniques for caching in next-generation edge networks: A comprehensive survey[END_REF] propose a wide survey that describes the approaches concerning the when, what, where, and how to cache. They categorize the works according to whether they focus on supervised, unsupervised, reinforcement, transfer learning, and neural networks. This document explains, for example, that to do caching at the edge and to predict data mobility and popularity, most authors use reinforcement learning and neural networks. That is because the popularity of content can be learned from no data or little data sets. On the other hand, the authors describe the methods to increase the cache hit rate. This objective is one of the most sought-after and can be achieved with supervised learning, clustering techniques, etc. Moreover, the authors explain some device-to-device communications techniques for energy savings or transmissions balance. We do not develop this point further since, although we assume data management, the optimization of their treatment is outside the scope of our research work.

Other researchers consider execution-time scheduling in order to achieve load balancing objectives. For example, Charantola et al. [START_REF] Charântola | Component-Based Scheduling for Fog Computing[END_REF] perform migration operations when the cloudlets (small-scale datacenter) close to the respective data sources are saturated. The authors intelligently select which applications should be migrated to the cloud whenever a cloudlet is overloaded. They base this selection on the applications' connections, the users consuming them, and the CPU load/requirements. For their part, Puthal et al. [START_REF] Puthal | Secure and Sustainable Load Balancing of Edge Data Centers in Fog Computing[END_REF] propose a system in which each edge-cloudlet is recorded in a central entity in the cloud. Then, each cloudlet broadcasts to register all other peers performing and offering all necessary security methods. Thereby, if a cloudlet enters an overload condition, it performs a breadth search for resources. It broadcasts its identity and loads data, looking for a peer able to execute part of this load. If the security filters are reached, and another peer has sufficient resources, the cloudlet performs migration operations.

On the other hand, other approaches consider load balancing of IoT devices. That is the case of Chhikara et al. [START_REF] Chhikara | An Efficient Container Management Scheme for Resource-Constrained Intelligent IoT Devices[END_REF] who deploy an energy-savings container migration strategy for IoT networks. Their proposal applies the K-means and hierarchical clustering algorithms to classify hosts. They consider three groups that define three host states: overload, underload, and load-balanced state. They then select the first two groups to balance their load by freeing them from their Using clustering methods as well, Elbamby et al. [START_REF] Mohammed S Elbamby | Proactive edge computing in fog networks with latency and reliability guarantees[END_REF] migrate load from the end devices to the cloudlets to improve the energy and computing resources management. They propose a decentralized method that groups nodes into disjoint sets based on spatial proximity and mutual interest in certain tasks. Then, the authors get a task popularity matrix to deploy a joint task distribution and caching scheme. In it, each cloudlet hosts as many results as possible, replacing old and less frequently used data with new insertions. That seeks to optimize the latency time of the final device.

X X [27] X X [118] X X [169] X X X X X X [13] [142] X X [132] X X [197] X X X X [63] X X X Our work X X X X X X
Another way to migrate load from end devices to the edge is through a collaborative system such as the one proposed by Zhang et al. [START_REF] Zhang | DOTS: Delay-Optimal Task Scheduling Among Voluntary Nodes in Fog Networks[END_REF]. In their proposal, fog nodes register as volunteers in the non-centralized system. The system then accepts the load transaction: End device-volunteer node based on the energy consumption, delay history, and computing capabilities.

On the other hand, some authors also perform Execution-time scheduling to balance network load and manage physical distances. For example, Puliafito et al. [START_REF] Puliafito | Companion Fog Computing: Supporting Things Mobility Through Container Migration at the Edge[END_REF] keep IoT devices as close as possible to the edge containers they use. When an IoT device moves away from the container that consumes more than a certain The Distributed Approach account: 1) The input variables, the operations performed, the type of approach or special hardware considerations, and 2) the variables that the approaches analyze and/or optimize such as QoS, Energy consumption, network balance or data management. Then, in Tables 3.9 and 3.10, we characterize the works concerning execution-time scheduling considering the same analysis fields. Figure 3.6 shows that most works tend to perform preprocessing operations before deploying software components. Moreover, it is interesting to see that very few authors analyze the characteristics of hardware components despite their heterogeneity. In our case, we manage an efficient initial-deployment process only with current hardware requirements information. Nevertheless, we also consider the energy characteristics of components such as the CPU, RAM, hard disk, and network card. This analysis is very important for us, especially when batterydependent devices are present, as in the case of grid or fog environments.

Another interesting fact is the more significant trend towards decentralized scheduling approaches. That is due to the physical distances between central entities and the worker nodes deployed close to the data sources. It's important to say that said central entities may even belong to higher abstraction layers such as the cloud.

Finally, the figure does not show a great tendency to analyze algorithmic complexity. In our case, we need to study that since it is directly related to the number of operations that we perform through the network.

On the other hand, Figure 3.7 shows that most works that study the initial Scheduling close to data sources.

Section 3.4 deployment in fog-type environments focus on the proper use of hardware components, the quality of service, and the efficient network balance. The latter, unlike cloud environments, is often due to having more layers of abstraction in the architecture. Thus, having intermediate nodes between the end devices and the cloud nodes makes it imperative to manage the load at the hardware and software resources level.

In our case, although we analyze the efficient use of hardware components (including network load balancing), we have not studied the application of our method in vertical hierarchies. This point represents for us one of the future works.

The analysis of the rest of the variables is the same as the one we did for figure 3.3.

Regarding the execution-time scheduling, figure 3.8 shows that several works depend on pre-processing operations. That is due to the trend of using clustering and prediction algorithms on variables such as resource usage, data popularity, etc.

Although we do not study these points directly, we consider them compatible with the use of multidimensional structures and correct distance functions. That represents a more dynamic and less computationally expensive approach.

On the other hand, Figure 3.8 shows a greater tendency to discuss special hard-Chapter summary and contributions Section 3.5

Although we do not deal directly with this, we consider that position data can belong to an extra dimension of a multidimensional data structure. In this way, searches for nearby nodes can be performed in an efficient logarithmic complexity.

It is important to say that, as the Figure describes, the efficient use of energy is one of our primary concerns. We study that through efficient scheduling operations.

The analysis of the rest of the variables is the same as the one we did for figure 3.7.

Chapter summary and contributions

In this chapter, we have selected and analyzed works that study distributed deployment and scheduling strategies. We made this selection considering the criteria of diversity, strength, and the variables shown in all the presented tables.

Unlike many surveys, we propose an algorithmic way of analysis to study these works. In it, we evaluate the problems and interest variables concerning two scheduling moments: 1) when an application is being deployed (Initial deployment), and 2) when it is being scheduled at run-time (execution-time scheduling).

So many interesting aspects to evaluate become visible, such as the differences between cloud and fog/grid/edge architectures, the management of physical distances between devices, the energy consumption, etc. For example, while the management of cloud clusters has a greater tendency to evaluate scalability factors, in fog/grid/edge, there is a greater tendency to consider the physical location of nodes.

All these aspects have allowed us to define the scope of our work and explain some of its strengths. For example, some approaches are based on learning techniques. Usually, in addition to requiring expensive computational operations, these methods can be affected by unpredictable data variations. In our case, we believe that the efficient configuration of our approach allows a safe deployment and scheduling based on current and dynamic data. Furthermore, many authors propose the optimization of some variables, such as only the quality of service or energy consumption. For our part, our approach can manage naturally as many aspects as needed at the same time.

As we said in the introduction of this chapter, we use multidimensional data structures to index data from both the nodes running the applications and the applications themselves. Depending on their type, these structures are compatible with centralized and decentralized network heuristics. They allow us to have a representation of a custom universe of as many dimensions as needed. Based on

Multidimensional entities for energy savings

Introduction

In the previous chapter, we have explained some of the different techniques for applications' initial deployment and execution-time scheduling in distributed systems. They aim to optimize several variables such as deployment time, scalability, or energy consumption. To achieve this, they analyze the state of a system deployment at a given time (input variables: hardware usage, physical location, load, etc.) to trigger scheduling operations (i.e., tasks deployment, containers migration, VMs duplication, etc.).

In the specific case of energy consumption, they have shown that it can be decreased with efficient deployment and load balancing techniques or the proper hardware features usage (prudent shutdown, CPU frequency reduction, etc.). However, they do not consider energy-based scheduling analyzing variables such as hardware heterogeneity, intelligent and multiple hardware resources indexing, or special hardware power capabilities.

On the other hand, as mentioned in chapter 2, we profile hardware and software components through mathematical models. Once identified an application by its PID, these allow us to relate the workload of the concerning hardware devices to their energy consumption using OS (operating system) interfaces. In this way, we can make deployment and scheduling decisions based on current consumption/workload information without specialized measurement artifacts. Although these models may not give perfectly accurate results, they allow comparing consumption information based on time and the heterogeneity of devices.

In this chapter, we present our distributed scheduling approach for load balancing energy savings. However, before explaining it, it is necessary first to choose the architecture of the applications to study, taking into account scheduling-based features. For example, applications based on virtual machine instances enable migration or duplication of these entities. On the other hand, monolithic processes running directly on the host OS let only balance the load generated from requests. Finally, applications based on containers enable light migration-duplication, efficient deployment, modular scalability, etc.

In this thesis work, we have chosen to analyze containerized applications based on microservices (MS). According to Paolo Di Francesco, they are small services Chapter 4

Multidimensional entities for energy savings that make up an application, each running in its own process and communicating with lightweight mechanisms [START_REF] Di | Architecting microservices[END_REF]. We chose this architecture because it enables many scheduling advantages [START_REF] Fowler | Microservices a definition of this new architectural term[END_REF][215]:

• Microservices generally use containers as their deployment technology. Therefore, each instance is identifiable from its PID [START_REF] Hat | How containers use PID namespaces to provide process isolation[END_REF].

• Easy updates via modules. A system administrator only needs to update only one microservice to update an application functionality.

• Heterogeneity. This architecture facilitates application deployment between different types of devices and heterogeneous platforms.

• Non-centralized storage operations.

• Extra security. The failure of one functionality does not affect the entire system. Thus, the errors can be treated and corrected separately.

• Easy to implement new content. To add new features to an application, a system administrator only needs to add new microservices and re-deploy only the components that will use it.

In our work, we consider the microservices approach only as a use case. Thereby, in a microservices deployment, we analyze and improve hardware resource management in a novel way to save energy without losing the notion of QoS (Quality of Service). We schedule (middleware operations: move, duplicate, start, stop) the containerized microservices that make up a distributed application through different physical nodes using multidimensional/spatial special structures. With them, we index elements such as physical nodes and microservices at execution time according to multiple criteria, such as the current availability of hardware resources, hardware's power-related features, or the container's resource requirements. This way, our objective is to have a system that performs the elements' search, insertion, and elimination at an efficient computational cost in order to execute energy-saving scheduling strategies.

Although we consider our technique extensible for any other type of architecture, we leave this analysis for future work.

Another important issue is scheduling heuristics. These can be oriented to either centralized or decentralized philosophies. Each has advantages and disadvantages depending on the type of application, deployment politic, or deployment level (i.e., Cloud, grid, or host). For example, important technologies like Netflix prefer centralized microservices orchestration (Netflix uses its well-known Conductor) Methodology Section 4.3 mainly for scalability matters, tight coupling, SLA agreements, etc. [START_REF] Netflix | Netflix Conductor: A microservices orchestrator[END_REF]. For their part, de langue et al. [START_REF] Peter De Lange | [END_REF] took advantage of a decentralized environment to develop a non-formal learning system in CoPs (Communities of Practice) based on a microservices architecture. In terms of platforms, Kubernetes offers centralized algorithms for the efficient deployment and scale of PODs [136]. For his part, Kalimucho [START_REF] Da | Kalimucho: Middleware for Mobile Applications[END_REF] provides a middleware platform to manage microservices; but in a p2p network of heterogeneous devices. Kalimucho also enables intelligent microservices movement, duplication, and routing operations. Chapter 3 summarizes both heuristics more fully.

Although our approach is extensible for both philosophies, we will study a decentralized system in this instance. We believe that in addition to advantages such as scalability and the absence of a single point of failure [START_REF] Chauhan | Fault Tolerant Decentralized Scheduling Algorithm for P2P Grid[END_REF], a non-centralized network is a perfect fit for energy-based scheduling. We will study other approaches in future works.

Methodology

This chapter describes the non-centralized scheduling algorithms that we propose for distributed environments. In general terms, these strategies perform device self-analysis and negotiation procedures for load balancing and energy savings.

In order to understand how these procedures work, the chapter begins by explaining the scheduling instruments that each device runs. Thus, section 4.3 describes our Kaligreen middleware that consists of per-device instances of a special portable microservice. That aims to analyze its device's resource status, negotiate with other peers, and execute scheduling algorithms.

Among the algorithms we implement, Kaligreen executes neighborhood microservice exchanges based on overloading and underloading situations. That considers hardware heterogeneity and different microservices restrictions.

To enrich the operation of our middleware, section 4.3.5 explains the architecture of Kaligreen V2. That implements special tables to describe the relationship between running software features and hardware special characteristics.

Finally, section 4.4 explains our algorithms based on multidimensional spaces. Such procedures use Kaligreen in its two versions and special data structures compatible with these spaces. Subsections 4.4.1 to 4.4.5 describe the theoretical framework and the abstract structures we define. Then, from subsection 4.4.6 to the end of the chapter, we describe our algorithms' procedures per se.

Chapter 4

Multidimensional entities for energy savings

Kaligreen Middleware: Establishing entities and tools for inter-device negotiation

As mentioned in the previous section, the Kaligreen middleware [START_REF] Humberto | KaliGreen: A distributed Scheduler for Energy Saving[END_REF] represents the first step of our proposal. Kaligreen works across multiple connected devices without belonging to specific network topology. In this manner, the devices are not guaranteed to connect to other peers all the time (i.e., they turn off, the connection signal is weak, etc.). For example, let us consider a network of cloud-independent user devices. Such devices (smartphones, televisions, watches, etc.) can connect to produce deployed applications' results using different interfaces (Wifi, Bluetooth, Ethernet, etc.). Here, intelligent device negotiations are the natural way to schedule one or more applications' microservices. In Kaligreen's case, the main objective of these negotiations may be to save the most significant amount of energy, particularly for devices that depend on a battery.

The non-centralized nature of scheduling algorithms in Kaligreen enables each device to offer or request resources from peers. If two devices agree, they can execute a container migration or duplication process. However, this methodology needs mechanisms and protocols to perform correctly.

In the next section, we explain some of Kaligreen's features, which allow the execution of scheduling strategies.

The Kalimucho middleware and devices for Kaligreen

In order to execute our algorithms, we need a tool capable of managing highly heterogeneous decentralized environments. For that reason, we base our approach on the Kalimucho middleware [START_REF] Da | Kalimucho: Middleware for Mobile Applications[END_REF]. It allows to move, stop, and (re)start application's microservices efficiently and transparently. For that, Kalimucho reads and understands distributed Java applications as a set of containerized components installed on Android and desktop devices. Each component is connected to others through special connectors that can be in an active or inactive state. That means a component can have many connectors with several other peers without saturating the network since only the necessary connectors are active. Additionally, Kalimucho is able to move components from one device to another without losing their execution state. To do that, if a component requests to be migrated to another device, Kalimucho will do it by shifting its java source code along with its current execution state using special storage files.

For Kalimucho, all these operations are platform-independent (operating system, firmware, etc.) thanks to the portability offered by the Java virtual machine.

Kaligreen Middleware: Establishing entities and tools for inter-device negotiation Section 4.3

In our case, we take advantage of this feature to efficiently save the energy of user devices. We consider this a significant problem since, according to several studies [200][223][225][176], by 2016, at least 70% of people in countries like South Korea had mobile devices (phones, tablets, etc.). Moreover, more than 81% of people in the world use mobile devices with the Android operating system. On the other hand, one billion PCs run Windows, 100 million devices (desktops and smartphones) use MacOS, and 1.6% of personal computers run GNU/Linux.

In Kaligreen, we differentiate between battery-dependent devices (laptops, smartphones, tablets) and battery-independent devices (desktop computers). This differentiation allows us to establish scheduling politics considering hardware heterogeneity. For example, algorithm 1 considers battery-independent devices prioritize being freed from Kalimucho containers but not receiving them.

For all these devices to be able to communicate and execute their scheduling algorithm, it is necessary to implement a standard protocol. We define this protocol through a metadata vector, which we will detail in the next section.

The Descriptor Vector

In order to execute a non-centralized scheduler, a device in a network must be able to describe essential hardware resources information to other peers. In Kaligreen, each device 𝐷 𝑖 uses a descriptor vector 𝑉 𝑖 𝑘 to depict five possible types of metadata: 1) Its resources capacity, 2) its current average hardware resource load, 3) its hardware average resources availability, 4) the execution requirements of a microservice 𝑀 𝑖 𝑗 , and 5) the average current load generated by 𝑀 𝑖 𝑗 in each resource. This way, for example, a device 𝐷 1 can send a vector 𝑉 1 3 to other peers seeking to establish a negotiation process to migrate 𝑀 1 2 . One goal may be to find a candidate capable of executing 𝑀 1 2 more frugally.

Kaligreen considers the hardware resources described in chapter 2. As a first approach, all vector 𝑉 𝑖 stores CPU, RAM, network, and storage resources metadata in terms of GHz, MB, MB/s, and MB/s, respectively. In figures 4.1 and 4.2, we show the five possible uses of 𝑉 𝑖 . The first shows the metadata sending process concerning the hardware resources of the first device. The second shows this process for the hardware resources that an application needs and obtains from the device.

In order to complete our scheduling approach, we also categorize the containerized microservices. That is to restrict some operations such as migration to avoid damaging the user experience and the applications' functionality.

Chapter 4

Multidimensional entities for energy savings

Microservices for applications and devices' supervision

As we explained in section 4.1, we consider that a distributed application comprises microservices working together. One of the problems we analyze in KaliGreen is categorizing and scheduling these microservices without damaging the user experience or an application workflow. We treat the first issue as follows:

• UI Microservices (interactive part of the application): Kaligreen will not migrate this type of microservices since the user is the only one who can decide with which device to interact.

• Sensors-management Microservices: Kaligreen will not migrate this type of microservices since this would imply stopping obtaining data from the environment involved.

• Computation Microservices: This group includes artificial intelligence training, video treatment, or image compression. Kaligreen can migrate or duplicate the corresponding containers to save a device's energy.

In order to address the second issue, we have designed a special type of microservice that we call "Supervisor". In the Kaligreen environment, it is a demon-like process that runs by default in each device 𝐷 𝑖 . Once it starts running, it enables in 𝐷 𝑖 the following operations:

• Perform periodic analysis of each hardware component considering load and energy consumption.

• Manage a list of metadata of all the running microservices. • Execute scheduling algorithms, which may involve container operations such as stop, start, migration, and duplication.

All these operations allow us to define different scheduling heuristics. If all devices connect to a single peer, the latter could run a distributed centralized algorithm. Otherwise, the heuristic will be decentralized.

As we said in section 4.1, our goal with Kaligreen is to implement non-centralized approaches. The following section explains our first algorithm based on devices' inter-neighbor negotiations.

A first distributed algorithm in Kaligreen

Let us define a heterogeneous user network 𝑁 similar to the one explained in section 4.3. 𝑁 comprises battery-dependent and non-battery-dependent devices identified by 𝐷 𝑖 . Depending on their hardware load and battery status, 𝐷 𝑖 can have two roles: 1) help seeker or 2) resource provider. Furthermore, 𝐷 𝑖 can migrate a microservice 𝑀 𝑖 𝑗 to a device 𝐷 𝑗 after a negotiation process. We consider the devices' inefficient energy situation (for example, a smartphone that is about to finish its battery) to trigger these migrations.

We validate these situations in a function called isInEmergencySituation(). Then, if 𝐷 𝑖 enters a state of emergency, it will select the microservices to migrate. For this, 𝐷 𝑖 executes the function selectHeaviestMicroservice(n).

This last function selects the 𝑛𝑡ℎ microservice 𝑀 𝑖 𝑗 that generates the most significant impact on the device based on CPU, RAM, network load, and the current remaining battery if concerns. For this selection to be possible, we set priority values for each component (based on a previous trivial analysis of random applications). These values are 1 for Network, 0.8 for CPU, and 0.7 for RAM. With them, the function determines the most affected component by 1) multiplying the load that 𝑀 𝑖 𝑗 generates (in percentage terms) by the corresponding factor and 2) selecting the component with the highest value.

Once 𝐷 𝑖 selects a microservice 𝑀 𝑖 𝑗 , it extracts 𝑀 𝑖 𝑗 metadata and writes it in a descriptor vector 𝑉 𝑖 𝑗 . Then 𝐷 𝑖 sends 𝑉 𝑖 𝑗 to the connected peers using the 𝑠𝑒𝑛𝑑𝑉 𝑒𝑐𝑡𝑜𝑟 (𝑉 𝑖 𝑗 , 𝐷 𝑘 ) function. Then, 𝐷 𝑖 will wait a reasonable time to get candidate devices that can continue executing 𝑀 𝑖 𝑗 . We fixed that time in 100𝑚𝑠 as an average ping result for our first implementation [START_REF] Dobbin | Lag! Top 5 Reasons your Ping is so High[END_REF]. For this first implementation, 𝐷 𝑖 will consider that the best candidate peer 𝐷 𝑗 is the first one who answers. As in Kalimucho, we base this decision on the inverse relationship between physical location and response time.

Finally, 𝐷 𝑖 notifies 𝐷 𝑗 using the 𝑠𝑒𝑛𝑑𝐶𝑜𝑛𝑓 𝑖𝑟𝑚𝑎𝑡𝑖𝑜𝑛(𝐷 𝑗 ) function to avoid other peers considering 𝐷 𝑗 as a candidate. If other candidates arrived after, 𝐷 𝑖 invokes the 𝑠𝑒𝑛𝑑𝑁 𝑒𝑔𝑎𝑡𝑖𝑣𝑒𝐶𝑜𝑛𝑓 𝑖𝑟𝑚𝑎𝑡𝑖𝑜𝑛(𝐷 𝑤 ) function.

As a help seeker, 𝐷 𝑖 succeeds in the algorithm migrating the microservice 𝑀 𝑖 𝑗 to 𝐷 𝑗 and quitting the emergency situation.

It is important to say that if 𝑀 𝑖 𝑗 cannot be moved, the algorithm tries to migrate the next heaviest one. This process finishes when 𝐷 𝑖 is no more in an emergency situation or there are no possible microservices to move.

On the other hand, Algorithm 2 describes the procedure to make a device 𝐷 𝑗 a resource provider. Herein, 𝐷 𝑗 must have sufficient computational capacity to run a foreign microservice 𝑀 𝑖 𝑗 from 𝐷 𝑖 without entering an emergency state. For this, it analyzes the received concerning vector 𝑉 𝑖 𝑗 and adds its values to its components' current loads' data. If any results exceed the 80% set, 𝐷 𝑗 will not offer its resources.

The supervisor microservice runs this algorithm periodically and removes all candidate vectors after a migration process or after a maximum response time.

As we can see, kaligreen's supervisor microservice can execute scheduling algorithms iteratively. This fact has some advantages. For example, in our first algorithm, the devices' load distribution is sensitive to new changes caused by the user (opening or closing applications) while saving energy. However, to improve energy savings strategies, Kaligreen should also learn to use the appropriate 𝑑𝑒𝑙𝑒𝑡𝑒𝐴𝑙𝑙𝑅𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔𝑉 𝑒𝑐𝑡𝑜𝑟𝑠; hardware components optimally. For that, our middleware needs to consider the components' usage time, capabilities, behavior, and energy savings features.

The following section shows Kaligreen's improvement design, enabling it to be aware of the relation of two factors: 1) The microservices processing requirements and 2) the awareness of as many hardware features as possible. That will allow intelligent microservices filtering as a part of scheduling procedures.

Kaligreen V2: A middleware aware of hardware opportunities to save energy

To optimally save energy, a middleware that performs distributed scheduling algorithms needs to consider the consumption of the devices' components. On the one hand, Chapter 2 explained that the four components that we analyze in this thesis are the CPU, the RAM, the network interface, and the storage device. On the other hand, Chapter 3 explained how some distributed approaches save energy based on these components. As a first step, Kaligreen only considered the load of the four components regardless of their heterogeneity. This second version introduces microservices filtering based on their execution characteristics and the mentioned components' capabilities.

To explain the methodology of this section, let us define the mentioned execution features through two variables:

• Runtime: We define a microservice as persistent when it has no known termination point.

• Access time to a hardware component: We define that a microservice 𝑀 generates a high average load 𝐿 in a component 𝐶 𝑗 of a device 𝐷 𝑗 when 𝐿 exceeds a threshold based on the characteristics of 𝐶 𝐽 . This threshold must be set manually before applying the scheduling algorithm.

The following section explains the analysis of the first component: The CPU.

CPU analysis

In Chapter 2, we mentioned that a CPU, at the hardware level, can implement C-States and DVFS to save energy. Furthermore, it can implement turbo boost technology to increment the execution frequency for a prudent moment. In a scheduling algorithm, migration operations can be made cleverer by only considering "compatible" microservices with these features. In Kaligreen, the supervisor microservice implements the table 4.1 from the microservices metadata list. For example, suppose a device 𝐷 𝑖 executes a persistent microservice 𝑀 𝑖 that generates a high CPU load. In that case, an algorithm may evaluate migrating it to a device 𝐷 𝑗 that does not contain the boosting characteristic. The reason is that, as we explained in chapter 2, frequencies beyond those supported by the TDP considerably increase power consumption (the non-linearity of the model 2.1 and the work of fans). On the other hand, the algorithm could try to keep a persistent low-frequency demandant microservice if the CPU of 𝐷 𝑖 can lower its frequency or turn off cores and the one of 𝐷 𝑗 does not.

RAM analysis

As explained in chapter 2, the consumption that a microservice 𝑀 𝑖 generates in the RAM is determined by the number of accesses 𝑀 𝑖 executes. Since we do not find potential RAM energy features for filtering operations, the supervisor microservice may only consider the RAM usage.

Chapter 4

Multidimensional entities for energy savings

In this way, a microservice that generates a high load in RAM (triggering, for example, swap operations) is a candidate to be migrated.

The storage device analysis

In a similar way to the NIC, Chapter 2 explains that the storage device's power consumption is determined by its transfer rate. However, the filtering opportunity we find here relates to the component type: 1) SSD or 2) HDD.

The supervisor microservice can implement table 4.3 for filtering. For example, a scheduling algorithm may migrate a non-persistent microservice 𝑀 with an HDD to a device 𝐷 𝑗 if this last has an SDD. This operation might involve freeing 𝐷 ′ 𝑠 hard drive and quickly terminating 𝑀. The Network device analysis

Microservice Features

Chapter 2 described that it is possible to know the energy consumption of a network interface from its different power states. On the other hand, although some authors perform some NIC power management operations (e.g., automatic D'link green ethernet [START_REF]Technologie D-Link Green[END_REF], rate adaptation [START_REF] De Maio | Evaluating Energy Efficiency of Gigabit Ethernet and Infiniband Software Stacks in Data Centres[END_REF], etc.), they are not accessible from OS interfaces. For these reasons, the filtering implemented by the supervisor microservice considers, on the one hand, the following criteria for a microservice 𝑀:

• Bandwidth consumption.

• The size of 𝑀, which involves migration cost.

• The size of the data coupled to 𝑀.

• The load generated by links from 𝑀 to other microservices.

On the other hand, to establish the relation with the variables above, the supervisor microservice considers the following operations:

• Data migration: This operation depends on the degree of coupling of 𝑀 with its data.

• Microservice duplication: Useful for load balancing when it is due to foreign connections.

• Microservice migration.

Thereby, the supervisor microservice uses table 4.4 to implement microservice filtering considering the devices' NIC. For example, suppose a device 𝐷 𝑖 executes a persistent microservice 𝑀 𝑖 that occupies 500𝑘𝑏 and saturates more than 90% of the 𝐷 𝑖 NIC's capacity. The scheduling algorithm may try to move it, as the first operation, to another device that does not depend on the battery or has a better type of network card. Suppose now that 𝑀 𝑖 is non-persistent, occupies 1Gb, and does not saturate the 𝐷 𝑖 bandwidth. The algorithm, in this case, may avoid scheduling 𝑀 𝑖 .

In future works, we will analyze different network interfaces such as Ethernet, Wifi, or 5G.

It is important to remember that, as we describe in section 4.3.5, we define the term "high" as exceeding a threshold based on the characteristics of each device. This threshold must be set manually before applying the scheduling algorithm.

So far, we have explained the operation and the tools that Kaligreen offers to execute distributed scheduling algorithms. Among these tools, the supervisor microservices can analyze the state of its device, build descriptor vectors, negotiate with peers, and perform scheduling operations. It also manages a list with the metadata of the running microservices, which can be filtered, if necessary, in descriptive tables. The purpose of these tables is to improve the scheduling process. These relate the microservices execution characteristics with hardware components capabilities or possible migration operations.

In the next section, we explain one of the cornerstones of our proposal: A distributed algorithm based on distributed multidimensional data structures and Kaligreen tools.

An energy-saving approach: Understanding microservices and devices as multidimensional entities

In Chapter 3, we explained various scheduling approaches used by scientists and well-known tools. On the one hand, these techniques can be executed in different deployment levels such as cloud or grid. On the other hand, they can have different objectives, such as quality of service assurance, high availability, scalability, or energy savings. In terms of the latter criterion, most of the authors we analyzed do not consider the characteristics of each component in depth. In addition, they base their proposals on learning techniques, centralized migration algorithms, or the treatment of mathematical functions.

In our case, we believe that multidimensional data structures allow having a clear and updated view of an entire system. With them, we can index the current data of the average consumption of the software components, loads of the devices' hardware elements, their energy-saving capacities, the devices' geographical positions, the battery status, etc. Then, for scheduling purposes, we can perform (re)insertions, deletions, and range searches at optimal computational cost depending on the multidimensional structure we choose.

It is important to say that our approach is abstract. Researchers can select different data structures compatible with centralized, non-centralized, or hybrid approaches at any level of deployment (cloud, grid, etc.). In this way, they will be able to execute various scheduling heuristics analyzing and optimizing as many variables as necessary.

In this thesis work, we implement this idea for the case of decentralized networks using Kaligreen. Our algorithm identifies "ideal" host candidates for microservices' execution and applies runtime scheduling operations (migration or duplication) to reduce energy consumption. To do this, an overlay called MAAN (Multi-Attribute Addressable Network) [START_REF] Cai | MAAN: a multi-attribute addressable network for grid information services[END_REF] allows us to interpret a decentralized network as a multidimensional resource (capacity-demand) space, which supports range queries in a logarithmic quantity of hops.

We use MAAN to contrast the microservices' requirements and the hardware availability that each device has. Thereby, in a certain period or under certain circumstances (i.e., battery problems, overload, etc.), one device running microservices can:

• Map them in terms of their execution requirements (i.e., CPU frequency, RAM operations, Network rate, and disk speed),

An energy-saving approach: Understanding microservices and devices as multidimensional entities Section 4.4

• Nearest neighbor query 𝑁 𝑁 (𝑞). Retrieve the closest element to 𝑞 in U. This is, {𝑢 ∈ 𝑈 | ∀𝑣 ∈ 𝑈 , 𝑑 (𝑞, 𝑢) ≤ 𝑑 (𝑞, 𝑣)}.

• K-Nearest neighbor query 𝑁 𝑁 𝑘 (𝑞). Retrieve the 𝑘 closest elements to 𝑞 in U. This is, retrieve a set 𝐴 ⊂ 𝑈 such that |𝐴| = 𝑘 and ∀𝑢 ∈ 𝐴, 𝑣 ∈ 𝑈 -𝐴, 𝑑 (𝑞, 𝑢) ≤ 𝑑 (𝑞, 𝑣).

Our first structure implements a multidimensional space of hardware resources for a microservices environment. In this space, we can perform energy-savings strategies considering as many hardware features as possible (i.e., capacity, use of special features, etc.). This way, for a microservice 𝑀 𝑖 𝑗 executed in a device 𝐷 𝑖 generating a load 𝐿 and an energy consumption 𝐸, it is possible to find a device 𝐷 ′ that: 1) has at least availability of resources 𝐶, in such a way that 𝐶 ≥ 𝐿, and 2) the energy consumption 𝐸 ′ generated by 𝑀 in 𝐷 ′ is less than 𝐸 because of final load or particular hardware's characteristics of 𝐷 ′ .

The following section will explain our hardware resource space and its features.

The multidimensional resources space 𝑼

Managing microservices in a decentralized network environment is challenging.

Operations such as load balancing, scheduling, microservices discovery, or energysaving are difficult to analyze without a central entity. That is because this central entity makes all information about the state of a system readily available. However, as we explained with Kaligreen, we believe that it is also possible to perform scheduling algorithms by intelligently organizing the devices of a P2P network for opportune negotiations. Herein, a helper seeker (see section 4.3.4), on the one hand, can migrate microservices to another peer to decrease its load and-or save energy. For his part, a resource provider can even proactively offer resources to other peers to process microservices more frugally.

Nevertheless, for a device to find an "ideal" peer to trade with is still a problem. That is why multidimensional spaces are the cornerstone of our work. Depending on the scheduling strategy, these can be built to manage different data types. Let us define some instances of this relation, considering heterogeneous devices as indexable elements.

• Index current power consumption to negotiate load: In the space, devices can search for peers with a certain power consumption value in their components. Then, to migrate or duplicate microservices, a device may evaluate candidates based on their hardware resources' load (availability).

• Index physical positions to trade power consumption: Here, devices may search for physically close peers as candidates. Then, their evaluation for microservices scheduling would be done considering energy criteria (hardware components' capabilities and load, battery status, and others.).

• Index current load of hardware components to negotiate power consumption: Here, devices can search for peers able to run a certain microservice. Then the candidates will be evaluated by energy criteria.

Going further, we can even combine criteria to execute mixed queries. For example, a device could query a heterogeneous space to find all physically close candidates that are not battery dependent, that have a given current power draw, and whose RAM is not saturated.

In our case, we randomly decided to implement first the space described in the third point above, leaving others for future works. Thereby, our approach abstracts and queries hardware resources in a 4-dimensional space. It contains the devices' available capabilities in CPU frequency, RAM capacity, NIC rate, and storage device speed. We show this in the definition 4.1.

▶ Definition 4.1 (The space U ). Given a set of devices connected to a shared network, we define a space U made up of 4 dimensions/axis: 1) CPU frequency in GHz, 2) RAM capacity in MB, 3) Network transfer rate in MB/s, and 4) Storage speed in MB/s. Devices are elements of U in terms of their current-average hardware resources' availability. ◀

Queries in U allow a device to know which peers have sufficient resources to run specific microservices in an optimal time. Then, using the Kaligreen's tools, the device may select the peers with outstanding features to perform migrationduplication operations (e.g., a low CPU requirement microservice and a device whose CPU can turn off some cores). It is important to say that U can consider many more variables such as special hardware features or other functional aspects. However, we consider them at the candidate selection time in this first implementation.

The following section discusses some distributed data structures which allow devices and processes to be indexable nodes. The section describes centralized and decentralized approaches as well as our choice to implement U.

An energy-saving approach: Understanding microservices and devices as multidimensional entities Section 4.4

Multidimensional P2P structures

As previously mentioned, this implementation seeks to take advantage of some features offered by decentralized network environments for scheduling. For instance, the fact that no single central unit realizes decision-making allows devices to be autonomous. Each peer can analyze its load or energy circumstances to perform ad-hoc scheduling operations (i.e., negotiation, load balancing, query, etc.) Thus, in addition to enabling an entirely dynamic system, this approach allows us to eliminate a single point of global failure. However, for a device to find other peers to negotiate or request information, it must belong to a standard comprehensible system. For this reason, several network overlays enable these operations in an efficient number of hops. These abstract the network deployment as data structures whose nodes and information are indexed through the same universe of metadata. Some notable examples are 1) an ordered circular list iterated through hash techniques [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][134], 2) a binary tree that can be explored through bit space and logical operations like XOR [START_REF] Maymounkov | Kademlia: A Peer-to-peer Information System Based on the XOR Metric[END_REF], and (3) a linked list of nodes that can search for elements by making smart hops in the structure [START_REF] Mandal | Deterministic 1-2 skip list in distributed system[END_REF].

Nevertheless, there are circumstances where a structure that supports more than one criterion (dimension) is needed. For example, in our space, we query a p2p device network to obtain the best candidates in terms of CPU, RAM, network, and storage availability to process a microservice. For that, some existing approaches implement multidimensional data structures such as Rtree [START_REF] Du Mouza | SD-Rtree: A Scalable Distributed Rtree[END_REF] or KD Tree [START_REF] Ganesan | One Torus to Rule Them All: Multi-Dimensional Queries in P2P Systems[END_REF] in a distributed network. As in the original structure, they also keep the parent-child relation of the tree nodes in the network devices.

All these structures allow multidimensional range querying efficiently. However, balancing or restructuring operations when inserting or deleting nodes may be expensive. They could involve the participation of many devices in the network that will perform complex data movements.

On the other hand, other approaches seek to partition multidimensional spaces into more independent structures. For example, Znet [START_REF] Shu | Supporting multi-dimensional range queries in peer-to-peer systems[END_REF] divides the space using Z-order curves. Its creators use the devices of the p2p network to form a Z-zonebased skip graph, where each device stores part of the description of a rectangular zone. In this way, when a query arrives at a node, it first verifies if the element (or the range) belongs to the zone it saves by exploring the highest element of its list. If it cannot find it, it derives the search to the node closest to the destination area, descending one level each time the search gets closer to its destination. Figure 4.3 shows the mapping procedure.

Another interesting strategy is the one proposed by Cai et al. [START_REF] Cai | MAAN: a multi-attribute addressable network for grid information services[END_REF]. MAAN

Multidimensional entities for energy savings corresponding partition tree [START_REF] Shu | Supporting multi-dimensional range queries in peer-to-peer systems[END_REF] generalizes the Chord [START_REF] Stoica | Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications[END_REF] approach to deploy a multidimensional space in as many circular devices lists as the space has dimensions. In our case, we have chosen MAAN to implement our space U. This deliberate election is because this thesis does not study the (dis)advantages of different overlays. However, we will explore other structures in future works.

Before explaining the structure of MAAN, it is necessary to explain the Chord system. We do this in the next section.

The Chord system

Chord deploys an ordered circular list of devices organized in a clockwise fashion according to an ID. Furthermore, using the same IDs' family, the system also identifies the elements to look for (i.e., data, processes, and others.).

For their part, each device (node) keeps a table of addresses called "Finger table ". This structure has as many elements as the bit string length representing the system's highest possible ID. For instance, in Figure 4.4, the system supports up to 63 (111111 in the binary system) devices. Therefore, the devices' finger tables can contain up to 6 elements.

Next, each index of a device's table is defined by its ID added to 2 𝑖 , where 𝑖 goes from 0 to the length of the bit string above. This way, every time an element E is searched through a node N, N looks for the E's index successor in its finger table. That is, the highest possible index that does not exceed E's ID. For example, suppose that in the topology of figure 4.4, the element "22" is searched through node "8". The latter will find that element "22" should be in node "21" since it An energy-saving approach: Understanding microservices and devices as multidimensional entities Section 4.4 is stored in the index "16" (n8+8), which is the highest possible ID that does not exceed "22" (otherwise, N8+16 = 24). In this way, the data structure used to search for elements is a consistent hashing table.

On the other hand, because Chord manages an ever-changing network of devices, nodes can join and leave at any time. The following section explains how each join-leave operation achieves said dynamism.

The join operation

There are several procedures a node 𝑛𝑁 and other devices in the network must perform in order for 𝑛𝑁 to join the Chord system.

First, the entering node nN gets assigned a unique ID using a SHA-1 function that hashes the 𝑛𝑁 ′ 𝑠 IP address. Then, an external mechanism guarantees a connection between 𝑛𝑁 and a Chord network pre-existent node. Here, the latter is found by executing a query inside the network to find a node representative of an immediate successor of 𝑛𝑁 : 𝑛𝑁 1.

The knowledge of 𝑛𝑁 1 consists of an immediate circle predecessor node reference and a finger table. 𝑛𝑁 then uses this knowledge to assign its circle predecessor reference to the one of 𝑛𝑁 1 and fill its own finger table by copying the one of that same node. Finally, the predecessor reference of 𝑛𝑁 1 is re-set to 𝑛𝑁 .

Once 𝑛𝑁 has been initialized, an update must be issued by walking counterclockwise along the circle to update previous nodes' finger tables. The goal is to acknowledge 𝑛𝑁 ′ 𝑠 existence preserving the finger tables' consistency. This update is done by assigning 𝑛𝑁 ′ 𝑠 ID to the appropriate finger table references of each predecessor node 𝑃 if both of the following conditions are met.

1. 𝑃 precedes 𝑛𝑁 by at least 2 𝑖-1 , where 𝑖 is delimited from 1 to the length of finger tables.

2. The last finger entry of node 𝑃 succeeds 𝑛𝑁 .

This update operation is sustained until a previous node 𝑃 whose 𝑖 𝑡ℎ finger precedes 𝑛𝑁 is reached. Finally, the responsibility of corresponding keys gets delegated from 𝑛𝑁 1 to 𝑛𝑁 .

The leave operation

For a node 𝐿𝑁 to leave the network, it first informs its predecessor node 𝑝𝐿𝑁 that the 𝐿𝑁 ′ 𝑠 immediate successor in the circle, 𝐿𝑁 1, is now its immediate successor. Then, the circle predecessor reference of 𝐿𝑁 1 is set to 𝑝𝐿𝑁 . Next, an update operation similar to the one described for the join operation is performed, but using the 𝐿𝑁 1 ′ 𝑠 ID. This last operation aims to keep the finger tables of nodes located counter-clock along the circle updated. Finally, the responsibility for 𝐿𝑁 ′ 𝑠 keys is delegated to 𝐿𝑁 1.

MAAN

An energy-saving approach: Understanding microservices and devices as multidimensional entities Section 4.4

Then, sub-queries are applied to 𝑋 to obtain a sub-set of candidates whose members meet the conditions of the other attributes. Finally, the origin node 𝑁 selects the fittest candidate by correlation.

In MAAN, join and leave operations are the same as the original Chord system.

The following section explains how we tune MAAN to implement our multidimensional resource space.

Implementing the space of resources U in MAAN

As previously described in section 4.4.2, we index device resources in the U space considering the availability of their processing-related capabilities. With that, we aim to find ideal resources to migrate or duplicate microservices and save energy efficiently.

Resources to index

According to the definition of U, four different dimensions/axes relate to four different hardware resources: (1) CPU frequency in GHz, (2) RAM capacity in MB, (3) network transfer rate in Mbps, and (4) storage speed in MBps. For that, we use MAAN to index each device's resource availability values on the corresponding U axis.

The join operation

When a device intends to join our MAAN network, four different logical nodes are created in four different dimensions (axis) of the U space. These nodes follow the same operations described in section 4.4.4 for the Chord system but with some technical differences.

In our approach, we lack an IP address identifier for each device. Instead, we created a locality preserving formula that, for any dimension, transforms a numerical value representing the availability of a resource into an ID coherent to the ID space available. Formula 4.1 states a superior limit for numerical entry values and a maximum number of nodes supported. Thus, the resource availability value 𝑉 is multiplied by the maximum number of supported (at any time) nodes 𝑁 . Then, the product is divided by the maximum device's resource limit value 𝑆𝐿, where 𝑆𝐿 and 𝑁 values are relative to each dimension's constraints. Multidimensional entities for energy savings

This model allows us to preserve a unique universe of integer IDs that can be assigned to nodes according to their dimensions. Thereby, in our approach, the finger tables contain records in pairs of 𝑚 -𝑏𝑖𝑡 space identifiers and node references. These elements grant us the execution of n-dimensional queries by applying an iterative approach like MAAN's original procedure.

On the other hand, it is necessary to say that nodes with a repetitive value for any attribute can join the network resulting in an identical ID assignment as a pre-existing node. That would result in a collision causing the entering node to be placed in the circle between said pre-existing node, further referenced as twinnode, and its successor. We solve that in the following way. When a twin node 𝑇 joins the network and finds a node 𝑟 𝑁 identified with its same 𝐼𝐷, it enters a twin list of 𝑟 𝑁 , being 𝑟 𝑁 the root of the list. Herein, each member has both predecessor and successor twin-node pointers.

The leave operation

When a device intends to leave the network, our structure performs mostly the same operations as the original Chord's system but handles the twin nodes as an added feature. For any twin list with a root node 𝑟 𝑁 , if 𝑟 𝑁 intends to leave the network, its first twin successor 𝑇 𝑁 gets assigned as the new 𝑟 𝑁 . Then, 𝑟 𝑁 copies in 𝑇 𝑁 its circle predecessor reference and its finger table. On the other hand, if a node inside the 𝑟 𝑁 ′ 𝑠 twin list leaves, the system removes it from the said list and resets the concerning predecessor and successor twin-node pointers.

Data frames and the reindexing process Section 4.4.6 explained that our structure indexes nodes based on the availability of their resources. However, the latter is very dynamic in real environments since it can be altered by the OS algorithms, the running applications' behavior, etc. For that reason, we implement the concept of "data frames" in our approach.

A data frame is a FIFO-like collection of availability measurement values related to a resource. Each supervisor microservice implements four data frames for the four axes of the 𝑈 space. The implementation considers the structure size, frequency of data recollections and insertions, and run-time modifications. Then, the supervisor microservice uses the average of the data frames values and the formula 4.1 to find its resource's corresponding IDs. That allows us to control the frequency with which nodes get dynamically reindexed into our MAAN-based approach.

An energy-saving approach: Understanding microservices and devices as multidimensional entities Section 4.4

Querying for resources

In order to perform queries, we follow the MAAN's iterative approach but consider two new operations to treat any candidate list 𝑋 .

To begin, we implement a "candidate lock" function to prevent resource selection collisions. That phenomenon occurs when several query resolutions select the same node candidate as the fittest one. Thereby, simultaneous microservices migration/duplication operations may occur towards this node, causing overload and over energy-consumption conditions.

A device 𝐷 applies candidate lock to each member 𝑥 ∈ 𝑋 , meaning that they can be candidates to exclusively one query at a time. If 𝑥 was already taken as a candidate by another peer, 𝐷 removes it from 𝑋 (see section 4.3.4).

On the other hand, the system must avoid the "circular saturation" phenomenon. That occurs when 𝐷 migrates its microservices to a candidate 𝑥, causing in it an overload condition. The latter may trigger in 𝑥 mechanisms to mitigate thermal energy elevation (such as a fan) and-or initiate chain migrations in the system resulting in further network strain.

For that, the supervisor microservices implement methods that enable projecting the future percentage of each resource consumption from numeric values. In this instance, these methods are approached in the scheduling algorithm, which must be aware of the system's stability.

The Scheduling algorithm

Once a device is inserted into our MAAN's network configuration where the space 𝑈 is deployed, its supervisor microservice starts executing a scheduling algorithm (see section 4.3.3).

This section explains our scheduling algorithm that we have implemented in this thesis. That considers running microservices deployed in our 𝑈 space.

As we said in the previous section, it implements projection functions for each hardware component. That allows devices to know the load and power consumption they would generate if they perform microservices migrations or duplications.

The CPU Projection

Chapter 2 explained that the CPU power consumption is found from its capacitance, frequency, and voltage. However, heterogeneity must be considered when cross estimating (estimating from another device). That is, the frequency of a CPU executing a process is not necessarily the same as for another.

Chapter 4

Multidimensional entities for energy savings For that reason, for a microservice 𝑀, we deduce the number of 𝑀 ′ 𝑠 program instructions considering the ones that the CPU can execute per unit of time. We can get this information from the /proc/cpuinfo file).

Thereby, if (1) 𝐷 ′ 𝑠 CPU is capable of executing 𝐼 𝐷 program's instructions in a time 𝑇 1, and (2) M consumes 𝑋 % of this component frequency 𝑋 𝑀 𝐷 in 𝑇 1, then 𝑀 executes 𝐼 𝑀 𝐷 program's instructions in a proportional way too:

𝐼 𝑀 𝐷 = 𝑋 𝑀 𝐷 × 𝐼 𝐷 100 (𝑇 1) (4.2)
Then, for another device, 𝐷2, it is possible to deduce the percentage 𝑋 𝑀 𝐷2 of its CPU load if it would execute 𝑀. For that, we consider the number of instructions 𝐼 𝐷2 in 𝑇 1 that 𝐷2 can execute:

𝑋 𝑀 𝐷2 = 𝑋 𝑀 𝐷 × 𝐼 𝐷 𝐼 𝐷2 (𝑇 2) (4.3)
Finally, the energy that 𝐷2 ′ 𝑠 CPU would consume to process 𝑀, 𝐸 𝑀 𝐷2 , can be calculated following the relation shown in equation 2.1; but considering the proportions that we explained in the last two paragraphs.

𝐸 𝑀 𝐷2 = 𝑋 𝑀 𝐷 × 𝐼 𝐷 × 𝐶 𝐷2 × 𝑉 2 𝐷2 × 𝐹 𝐷2
Equation 4.4 allows obtaining from 𝐷 an estimation of the energy that 𝐷2 ′ 𝑠 CPU would consume if it executes 𝑀. Thus, in a negotiation process, this consumption can be analyzed before a migration or duplication operation.

It is important to remember that the formula considers the fan's consumption at a speed 𝑠. Said speed is related to a certain processor frequency 𝐹 𝑘 .

The RAM Projection

In chapter 2, we explained that the energy consumption of the RAM is divided into both active and background consumption. In addition, we also explained that the number of operations executed by RAM is strongly related to the CPU's work. Finally, the last section described a method to represent the work differences among An energy-saving approach: Understanding microservices and devices as multidimensional entities Section 4.4

several CPUs. Therefore, we consider implicit the heterogeneity of the RAM of various devices in terms of said number of operations. Thereby, to find the energy consumption that a microservice 𝑀 running in 𝐷 would produce in a device 𝐷 ′ 2 𝑠 RAM, we use the formula 4.5.

𝐸 𝑎𝑐𝑡 = 𝐸 𝐵𝐾 𝐷2 × (𝑓 𝑎𝑐) + 𝑁 𝑅 𝐷 × 𝐸 𝑅 𝐷2 × (𝑓 𝑎𝑐2) + 𝑁 𝑊 𝐷 × 𝐸 𝑊 𝐷2 × (𝑓 𝑎𝑐3) (4.5)
It is important to say that the factors of the formula 4.5 are the same as the models 2.2 and 2.3. Nevertheless, we have considered slight random differences in each device's 𝐸 𝐵𝐾 , 𝐸 𝑅 , and 𝑊 𝑅 for our experiments (𝑓 𝑎𝑐1, 𝑓 𝑎𝑐2, and 𝑓 𝑎𝑐3 multipliers). We did this since the model's original values were obtained from linear regression and measurement operations (see section 2.4.3) on a single device, not representing heterogeneity criteria.

In future works, we will look for more precise ways of projecting the RAM's energy consumption

The NIC Projection

Chapter 2 describes two ways to find the energy consumption of the NIC. One that studies its load and another based on the number of packages sent or received. Thus, to calculate the energy consumption that 𝑀 running in 𝐷 would produce in the 𝐷 ′ 2 𝑠 NIC, we use models 2.7 and 2.8 but in terms of 𝐷 2 :

• Analyzing 𝑀 from the average transfer rate it generates: This projection approach considers (1) the 𝐷2 ′ 𝑠 NIC power consumption in its active state, 𝑊 𝑢 𝐷2 , (2) the average load that 𝑀 produces in 𝐷 ′ 𝑠 NIC, 𝐿 𝑀 𝐷 , and (3) the maximum transfer capacity of 𝐷2, 𝐿 𝑀𝐴𝑋 𝐷2 .

𝐸 𝑁 𝐼𝐶 𝐷 𝑀 =(𝑊 𝑢 𝐷2 × 𝐿 𝑀 𝐷 𝐿 𝑀𝐴𝑋 𝐷2 )(𝑇 𝐷 ), (4.6)
• Analyzing 𝑀 from the packets it sends or receives: This projection approach considers [START_REF] Acar | Beyond CPU: Considering memory power consumption of software[END_REF]

Chapter 4

Multidimensional entities for energy savings

The Storage Device Projection

As Chapter 2 explained, we propose energy models for the storage device similar to those we use for the NIC. Thereby, we use the same arguments as the previous section for the storage-device energy projection approach. Formula 4.8 considers (1) the 𝐷2 ′ 𝑠 storage-device power consumption in its active state, 𝑊 𝑢 𝐷2 , (2) the average load that 𝑀 produces in 𝐷 ′ 𝑠 storage device, 𝐿 𝑀 𝐷 , and (3) the maximum storage rate capacity of 𝐷2, 𝐿 𝑀𝐴𝑋 𝐷2 .

𝐸 𝐻 𝐷 𝐷 𝑀 =(𝑊 𝑢 𝐷2 × 𝐿 𝑀 𝐷 × 𝑓 𝑎𝑐 𝐿 𝑀𝐴𝑋 𝐷2 )(𝑇 𝐷 ), (4.8)
So far, we have explained the projection operations for each U -space resource. The following sections explain each device's scheduling algorithms, considering these operations.

The scheduling algorithm: Analyzing microservices in the U space

Our algorithm considers a device-microservices deployment with the following characteristics:

• All devices are indexed in our MAAN configuration, which implements the U space.

• Each device is indexed on the four edges of U considering its CPU, RAM, NIC, and storage device availability.

• A device 𝐷 can run one or several microservices [𝑀 𝐷 𝑖 ...𝑀 𝐷 𝑗 ], which have initial resource requirements for CPU, RAM, NIC, and storage rate.

• Each microservice is identifiable by a PID.

• The OS of each device executes a single-priority round-robin scheduling algorithm. Thus, competing microservices obtain resources proportionally to what they request.

Then, each device 𝐷 𝑖 executes the scheduling algorithm 3, extending the Kaligreen helper seeker procedure (see algorithm 1). Thus, each supervisor microservice considers that a device is in an emergency state when any resource load exceeds 85% of its capacity. Furthermore, this entity also considers a device in an underload state when its resources (all of them) have a load under 5%. Whenever a device (D) enters an emergency or underload state, the algorithm tries to migrate microservices. To do that, it first uses the KaligreenV2 tables (section 4.3.5) to select a list of migratable microservices. Then, it sorts that list using Kaligreen's consumption factors approach. Finally, the algorithm attempts to move either the heaviest microservice, the middle-positioned, or the lightest one, recomposing the list in each iteration. We have considered only these three "pertinent" possibilities to avoid overwhelming the network with repetitive queries.

If 𝐷 does not have microservices running (after the underload state), it enters sleep mode to save energy.

For its part, algorithm 4 describes the migration function. It looks for device candidates in the MAAN-based structure for each resource requested by the microservice 𝑀. Then, it finds a single metadata list of devices capable of running 𝑀. If the candidates are not locked and simultaneously are compatible with some

The PISCO Simulator

Introduction

Nowadays, many architectures for software components (e.g., Docker-Kubernetes, Kalimucho, etc.) aim to create modular applications efficiently. As described in chapter 3, these entities are scheduled to optimize variables such as quality of service, the physical location of devices, load balancing, or energy consumption.

As explained in chapter 4, we propose distributed scheduling strategies for load balancing and energy savings using intelligent device negotiations and multidimensional data structures. To do that, we use microservice-based applications as the input to our algorithms and the formulas in Chapter 2 as energy measurement tools.

This chapter explains PISCO, an innovative simulator to deploy energy-saving methods in microservices-based networks. We have designed and implemented it as a deployment and evaluation tool for the techniques described in the previous paragraph. PISCO enables its users to focus uniquely on scheduling approaches and their hardware-software repercussions. This way, they don't need to worry about low-level network configurations or OS issues to evaluate their methods.

PISCO can deploy and schedule (move, duplicate, start/stop) MS (microservices) and their dependencies on various devices supporting heterogeneity criteria (MS's types, data and restrictions, and devices' CPU, bandwidth, RAM, Battery, etc.). Moreover, it manages scheduling algorithms and their repercussions, considering the following aspects:

• Both the capabilities and the particular characteristics of each device's hardware component.

• The simple configuration (through a GUI or an API) of centralized (i.e., clientserver), decentralized (i.e., p2p architectures like kademlia [START_REF] Maymounkov | Kademlia: A Peer-to-peer Information System Based on the XOR Metric[END_REF], chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], or multidimensional systems such as MAAN [START_REF] Cai | MAAN: a multi-attribute addressable network for grid information services[END_REF]), or hybrid networks.

• The definition and evaluation (tracking and application of linear regression techniques) of QoS, energy metrics, and quantity of operations (movements, duplications, deployments, and deletions) related to an algorithm.

Chapter 5

The PISCO Simulator

• The unexpected network circumstances or user strategies consisting of devices appearing, disappearing, turning on, or off.

Finally, PISCO is agnostic and not dedicated to a particular middleware. It can virtualize an environment controlled by any software that deploys and schedules microservices. That allows researchers to create any scheduling algorithm and measure its consequences in the terms they define.

Methodology

This chapter explains our PISCO simulator's context, entities, and functioning. To understand its creation and scope, section 5.3 explains and compares the framework of several important simulators considering different abstraction levels. Then, to explain the PISCO's engine, section 5.4.1 details the simulator entities, which are typically instances of java objects. Finally, pursuing the same objective, section 5.4.2 explains the operations that our tool supports.

We finish the chapter by explaining the corresponding conclusions and contributions in section 5.5.

Existing tools

To understand and evaluate any distributed environment, the scientists may use modeling tools supporting several appropriate criteria. For example, packetoriented simulators allow evaluating network traffic and specific transmission protocols. Among them, Packet Storm[178], IP WAN Emulator [START_REF]IP WAN Emulator[END_REF], SENS [START_REF] Sundresh | SENS: a sensor, environment and network simulator[END_REF], and Cisco Packet Tracer [START_REF]Cisco Packet Tracer[END_REF] allow modeling scenarios to evaluate data streaming techniques and features, latency, data loss and duplication, and others. For its part, the O-ICN Simulator [START_REF] Agrawal | O-ICN Simulator (OICNSIM): An NS-3 Based Simulator for Overlay Information Centric Networking (O-ICN)[END_REF] allows evaluating the network status while modeling a particular architecture called Information-Centric Networking (ICN). Finally, Green-Cloud [START_REF] Greencloud | Greencloud -The green cloud Simulator[END_REF] allows understanding of energetic issues at the packet network-protocol level.

The simulators above are helpful for modeling protocol-oriented scenarios and studying connection phenomena. However, we consider that these tools cannot replicate the behavior (i.e., use of resources, application QoS and energy consumption) of service-based architectures, where a higher level of abstraction is needed.

Considering a higher abstraction level, Petr Novotny et al. [START_REF] Novotny | Simulating Services-Based Systems Hosted in Networks with Dynamic Topology[END_REF] propose a framework for simulating architectures based on MANET (Mobile ad hoc network) service networks. It includes service, messaging, and network layers to model services'

Existing tools Section 5.3 complex message exchange behavior. For this purpose, they consider approaches like cascading flows of messages in challenging conversations, comprehensive client-driven workload profiles, and the propagation of faults through services.

This simulator is very efficient in studying services information exchange. However, it does not consider the energy repercussions of services deployment, nor does it allow to know the best way to schedule them in a given network.

At the services deployment level, Cloudsim [START_REF]cloudbus. ContainerCloudSim: An Environment For Modeling And Simulation Of Containers In Cloud Data Centers[END_REF] is a complete simulator that allows modeling service-based architectures with different virtualization policies (i.e., VMs, containers, etc.) at various CLOUD/GRID layers. It enables the study of diverse repercussions concerning energy and QoS when managing services. For its part, DockerSim [START_REF] Nikdel | DockerSim: Full-stack simulation of container-based Software-as-a-Service (SaaS) cloud deployments and environments[END_REF] considers not only strategies at service-based architecture but also entire packet-level network and protocol behaviors. Furthermore, µqSim [START_REF] Zhang | mqSim: Enabling Accurate and Scalable Simulation for Interactive Microservices[END_REF] evaluates the execution of microservices deployed with a centralized scheduler, analyzing their latency, requests, and QoS. This simulator has a power management engine and handles dependencies between microservices. However, it does not consider decentralized scheduling or heterogeneity in the execution environment. Next, the iFogSim [START_REF] Gupta | iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments[END_REF] simulator offers an approach to ensure QoS and efficient power management by moving services from the cloud to the network's edge. For its part, InterSCity [START_REF] De | Design and evaluation of a scalable smart city software platform with large-scale simulations[END_REF] is a robust microservices-based platform that counts on the InterSCSimulator. It performs load balancing and microservices scheduling while keeping awareness of power consumption and resource availability.

These simulators are very competent in analyzing scenarios in which services and containers are deployed. However, we consider that they do not offer a straightforward way to execute and evaluate distributed algorithms of the level at abstraction that we propose. That is, considering heterogeneous devices belonging to different network topologies, building network overlays compatible with multidimensional structures, analyzing the relation between energy consumption and a defined QoS, and others.

Table 5.1 shows the characteristics above of some simulators offered by important scientists. Herein, each letter has the following meaning:

• Feature A. Considers behavior aspects at the connection level (protocols, data loss, etc.).

• Feature B. Considers energy consumption at connection level (protocols, data loss, etc.).

• Feature C. Supports microservice deployment in the cloud and local network environments.

The

Furthermore, regarding this last point, PISCO also allows studying, simply and visually, the distributed scheduling considering multidimensional aspects. Moreover, in our algorithms context, we need a tool capable of deploying network overlays with the same dynamism and multidimensionality as several data structures. Within these, we also needed the tool to execute and evaluate different scheduling heuristics dynamically. This dynamism consists in the definition of heterogeneous devices, software, and topologies. As no tool we explored fulfilled these functions, we decided to design and develop PISCO.

The next section presents PISCO's structure, capabilities, and operations.

The PISCO simulator

To study the "best" way to deploy and schedule distributed applications in custom networks of heterogeneous devices, we developed PISCO. PISCO is a desktop and portable java-simulator that can manage (deploy/schedule) any distributed application in any network architecture (i.e., non-centralized, centralized, multidimensional, horizontal, and others.). In our simulator context, an application is defined as a directed graph whose nodes are microservices and edges the connections among them. Moreover, every application is deployed on a graph of connected devices, where the nodes could be: (1) devices with heterogeneous characteristics (dependant on batteries, static or mobile, devices with different network interfaces, etc.) or (2) abstract entities such as clusters or cloudlets. Furthermore, the device graph's edges are the network connections among nodes (ethernet, wireless, 4g, or Bluetooth), which can be: (1) physically direct (cable or wireless), or (2) logical (through an overlay structure). Both types of connections allow the transfer rate at which the microservices can send or receive data from each other.

The following section explains the operation and interaction of each of the elements of both graphs.

The simulator entities

Entities in PISCO are instances of Java classes. To understand their interaction, Figure 5.1 shows a condensed version of our simulator's class diagram. That schema is deeply explained in the following sections.

The PISCO simulator Section 5.4

-Current load and availability in percentage relative to the clock frequency.

-Capacitance, TDP, and voltage.

-Presence or absence of PCPG, DVFS, or Overclocking.

-Custom energy formula.

-Power expenditure in Watts.

-Energy expenditure in Joules.

• RAM:

-Current and available load in percentage and MB.

-Current read and write operations.

-Custom energy formula.

-Power expenditure in Watts.

-Energy expenditure in Joules.

• NIC and storage device:

-Current and available rate in GB/s/MB/s/percentage.

-Custom energy formula.

-Power expenditure in Watts.

-Energy expenditure in Joules.

• Battery:

-Used and available in terms of Watt-Watts hours.

• GPS position:

-Latitude and longitude values.

And on the other hand, it executes distributed scheduling algorithms (i.e., moving or duplicating a microservice to another device, performing negotiations, managing load balancing, tracking the number of operation hops, etc.).

It is important to mention that the middleware running on each device also enables centralized scheduling. For this, PISCO configures a node as a master, being able to invoke the execution operations of the peers it controls.

Chapter 5

The PISCO Simulator Network overlay PISCO implements networks in the form of data structures in which the indexed elements are devices. By default, our simulator supports graphs representing networks of direct connections, n-trees representing hierarchical networks, and multidimensional lists representing multi-attribute spaces.

The screenshots in figures 5.2 and 5.3 show two network configurations. The first one shows a devices graph, where each device is physically connected with some peers. For its part, the second one shows a MAAN network overlay (see chapter 4) in its CPU dimension.

Microservice

For PISCO, a microservice is a functional entity identifiable by a unique ID and with a defined function. The latter is a string code representing the microservice functionality and scheduling restrictions (see section 4.3.3). For instance, by default, PISCO defines three types of microservices: graphical interface, calculation, and data management. The differences among them are their default resource consumption, the amount of data they send/receive, their size, and the restriction of being moved or not from one device to another. On this point, it is also important to point out that the simulator users can create their own types of microservices.

When deployed on a device, each microservice claims a certain amount of CPU, network, RAM, and disk resources. To manage that, PISCO defines the following two attributes for each resource:

The PISCO simulator Section 5.4 • The average current resources: It defines the resource status of a microservice, which depends on the other peers competing for resources and the OS heuristic.

Connection

PISCO defines and manages two kinds of connections: Physical/logical among devices and functional connections among microservices. A physical connection logically supports many microservices' connections. That defines the current and maximum possible transfer rate (i.e., between 2 devices: the maximum transmission capacity of the device with the NIC with less transmission capacity).

Our simulator also allows graphically analyzing, on the one hand, the status (i.e., at energy and load level) of devices' NICs (even if they belong to abstract entities such as clusters or cloudlets). On the other hand, it tracks the microservices' connections (i.e., expected transmission rate vs. real transmission rate) using physical ones. For that, connections among microservices logically store the device Chapter 5

The PISCO Simulator connections they use to communicate. Thereby, the supervisor microservices are aware of the device's path they use and their current/expected transfer rate.

Application

PISCO defines applications as directed graphs of microservices. Herein, each node has connections as dependency relationships with other microservices that may run on different devices. In PISCO, applications are also identified with a unique ID.

Operations center

If needed, PISCO holds a centralized entity that stores all references to connections and existing devices of a deployed scenario. In this way, the simulator users can track their algorithm's behavior and execute centralized scheduling algorithms.

Abstract entities

Additionally, PISCO also implements entities such as cloudlets and clusters as resource providers. Both can be deployed and connected similarly to devices but considering different intra-scheduling politics. With them, our simulator is compatible with small networks of user devices and networks based on cloud/edge technologies.

The simulator operations

PISCO can apply different heuristics for microservices (re)deployment and scheduling through a network. For that, the simulator implements the following operations:

Devices and abstract entities deployment

Any simulator user can declare default or custom devices and abstract entities (i.e., desktop computer, laptop, smartphone, etc.) by specifying the desired resources (CPU, RAM, NIC, storage device, or battery). Then, the devices will be indexed by PISCO as indicated in the add method of the network overlay. This method may consider load, hierarchy, or energy criteria.

On the other hand, PISCO also supports physical positions in the form of longitude and latitude points on a Cartesian plane, as shown in figure 5.4. That allows studying deployment techniques based on distance heuristics or methods to improve communication paths.

Devices and abstract entities suppression

PISCO implements two device suppression methods: 1) Manually, by the user's decision, and 2) automatically, according to the desired strategy. A user can activate a "disappear" option for each device, causing the simulator to delete it after a random, established, or battery-related time. This option simulates unexpected loss of connection (i.e., a mobile device entering a building, battery loss, system crash, etc.).

The device suppression invokes the delete function of the network overlay.

Microservices deployment

PISCO allows simulating the execution of microservices on devices. Once deployed, a microservice uses a quantity of resources (see figure 5.4) for a determined time or indefinitely. This time can be set by: (1) the PISCO UI in an interactive way or (2) automatically by an operation center's function. Furthermore, the user must also specify the microservices' size, defining the amount of data sent over the network when it is moved or duplicated. This attribute allows analyzing the cost of reconfigurations in terms of efficiency and energy.

Chapter 5

The PISCO Simulator

Microservices suppression

Like deployment, a microservice can be killed using a simulator UI button or according to a predefined amount of time in the operation center (also set using the simulator UI). When suppressed, the microservice will stop using the device's resources and will no longer be available for any item.

Microservices migration and duplication

PISCO can move or duplicate microservices from one device to another. On the one hand, these operations can be done from the operations center, which maintains the full list of microservices and connections. On the other hand, the operations can be performed from a particular device (it knows only its connected devices) according to the algorithm its runs. When a microservice is migrated, it first releases the resources of its current device. Then, PISCO simulates the moving process by using the active network connection for a time based on the microservice's size. Finally, it starts to compete (as there could be other microservices) for the resources of the new device.

The duplication operation is similar to the previous one but without killing the microservice on the source device.

About these operations, it's important to mention that PISCO always keeps (non)centralized microservices-devices graphs updated. Thus, for example, if a microservice is moved and becomes unreachable for one of its dependencies, the user can specify search mechanisms for the same instance in the devices graph.

Figure 5.4 is a screenshot of one of the PISCO's UI. It shows a simple scenario where we deployed an application consisting of three microservices (𝑀𝑆_1, 𝑀𝑆_2, and 𝑀𝑆_3) communicating with each other at 50𝑀𝐵𝑝𝑠 and two connected devices (a laptop, 𝐷_2, and a desktop computer, 𝐷_1). Then, each device shows its status in the outline of its icon in terms of used/available network (left: 𝑋 50 𝑀𝐵/𝑠), RAM (top:

𝑌 15874 𝑀𝐵), CPU (right: 𝑍 3.6 𝐺𝐻𝑧), and storage rate(botton: 𝑊 500 𝑀𝐵/𝑠). In this example, if 𝑀𝑆_3 is moved to the device 𝐷_2, the transmission quality rate between both microservices 𝑀𝑆_2 and 𝑀𝑆_3 declines. That is because the physical network connection is limited to 25𝑀𝐵/𝑠 (between the two NICs, 𝐷_2 ′ 𝑠 one has the least transfer capacity). It is important to say that this does not necessarily affect an application's QoS level considering its definition and type. In our case, our algorithms always seek to have the highest possible QoS assuming the approaches described below.

The PISCO simulator Section 5.4

Microservices and devices Start/Stop

PISCO allows starting and stopping devices or microservices in a scheduled or manual way. Both operate as the mentioned deployment and suppression operations, but without deleting these entities permanently. Thereby, they can also be restarted manually or in a scheduled way.

QoS definition

PISCO allows users to define their own QoS philosophies, either for microservices or applications. However, the simulator offers two default heuristics: One, "nondependent, " and another, "dependent. "

These default definitions aim to model different application behaviors. The first, for example, describes applications whose modules can have: (1) different replicas, enabling load-balancing strategies in the event of QoS affection, and (2) non-critical functionalities, such as batch processing or backups creation. Here, users must specify the module's importance, as shown in the following paragraphs. On the other hand, the second describes applications whose modules are unique and important, causing that if one of them is affected, the behavior of the entire application changes.

For the non-dependent approach, PISCO calculates the microservices' QoS value in proportion to the hardware resources needed-obtained. On the other hand, the applications' QoS is obtained proportionally to its microservice's QoS value.

The non-dependent microservices' QoS is defined as follows (including equation 5.1):

• For a microservice 𝑀 being executed in a device 𝐷, PISCO defines a QoS=100% considering the resources that 𝑀 requires to run in terms of CPU frequency in 𝐺𝐻𝑧, RAM consumption in 𝑀𝐵, network transfer rate in 𝑀𝐵/𝑠, and storage transfer rate in MB/s.

• Then, there might be some differences between the resources 𝑀 requires to run and those it gets from 𝐷. We express those differences as percentages (from 0 to 100) using the following symbols: (1) 𝐷 𝐶 , for CPU frequency, (2) 𝐷 𝑅 , for RAM, (3) 𝐷 𝑁 , for network transfer rate, and (4) 𝐷 𝐻 for storage transfer rate.

• For each of these variables, a user must specify an impact value. This value must be considered from 0 to 1 so that all the values add up to 1. As seen in the equation 5.2, the 𝑀 ′ 𝑠 QoS remains at an acceptable value despite the unavailability of RAM, network, and storage rate. That is because the user has defined that the CPU is the most relevant component for quality of service. For example, this scenario may belong to an application for calculating machine learning predictions. Here, the CPU is highly required to do the calculations. However, the only use of the rest of the peripherals may be the storage of data executed by independent functions.

Next, the non-dependent application's QoS, 𝑄𝑜𝑆 𝑎𝑝𝑝 , is defined by the quality of service of each of the 𝑁 microservices, 𝑄𝑜𝑆 𝑖 , that compose it. Again, we consider the impact value 𝐼 𝑖 ,that the user must define in the same way as the last method. The following formula shows this approach: On the other hand, PISCO also offers by default a "dependent" heuristic, in which the QoS of a microservice 𝑀 is limited by the least satisfied demanded resource. As before, we consider here the impact parameter, 𝐼 , specified by the user. The following formula shows this approach: 𝑄𝑜𝑆 𝑀 = 𝑀𝑖𝑛(𝐼 𝐶 × 𝐷 𝐶 , 𝐼 𝑅 × 𝐷 𝑅 , 𝐼 𝑁 × 𝐷 𝑁 , 𝐼 𝐻 × 𝐷 𝐻 )

(5.4)

The PISCO simulator Section 5.4

Then, the QoS of an application, 𝐴𝑃𝑃, composed by a set of microservices, 𝑀 = [𝑀 0 ...𝑀 𝑛 ], is limited by the microservice 𝑀 𝑖 ∈ 𝑀 with the lowest QoS value, as shows the following formula: 𝑄𝑜𝑆 𝐴𝑃𝑃 = 𝑀𝑖𝑛(𝑄𝑜𝑆 𝑀 𝑖 ) ∀ 𝑀 𝑖 ∈ 𝑀 (5.5)

QoS analysis

Our simulator can show the QoS of applications and microservices at a specific rate and time interval defined by the user while executing a scheduling algorithm.

For that and analyzing purposes, PISCO supports graphical PLOT, performance metrics storage, and linear/polynomial regression.

Power consumption parameters definition

PISCO uses, by default, the formulas described in Chapter 2 to find the power consumption of the CPU, RAM, NIC, and storage devices.

Power/Energy consumption analysis

Our simulator analyzes the power and energy consumption in the same way as with the QoS. It supports graphical PLOT, performance metrics storage, and linear/polynomial regression. For example, the screenshot in Figure 5.5 shows the QoS and power consumption metrics of Kaligreen's default algorithm over some of its iterations. Save/Load scenario from an initial or an already modified state

To facilitate the evaluation of distributed algorithms, PISCO can save all the objects of a scenario (including their state) in JSON files. Among these objects, we can mention devices, connections, overlays, and other instances.

Chapter summary and contributions

This chapter explains the justification and operation of the simulator we created: PISCO. Regarding the first point, we needed a tool capable of deploying network overlays with the same dynamism and multidimensionality as several data structures. Within these, we also needed the tool to execute and evaluate different scheduling heuristics dynamically. This dynamism consists in the definition of heterogeneous devices, software, and topologies. Moreover, concerning the second point, the chapter explains the entities and operations of the simulator.

To the best of our understanding, only PISCO fulfills all these needs. For this reason, we use our tool to study our distributed algorithms.

On the other hand, given the novelty of our simulator, it was selected by SATT Aquitaine (AST Innovation) for a maturation process. Next, a software license and a patent were registered at INPI. Finally, two licenses are currently deployed (Univ. La Rochelle, Univ. Paris 1 -Sorbonne), and a technological transfer is under discussion with the international group SPIES.

The next chapter describes the experiments that demonstrate the effectiveness of our methods from chapter 4, which we implemented in PISCO.

Introduction and methodology

This chapter explains the experiments and results of the measurable methods proposed throughout this thesis. In each part, the latter offers a contribution according to what it studies. Chapter 2 proposes mathematical models to estimate the power consumption of the network card and storage device. Then, chapter 3 describes an algorithmic survey approach for distributed scheduling techniques. For its part, chapter 4 explains our distributed scheduling algorithms. Finally, chapter 5 details the design structure of the simulator that we have created.

Here, we will analyze the proposals that we can evaluate through experiments. In section 6.2, we analyze the approaches of Chapter 2, and in section 6.3, the ones of chapter 4. In each of these, we describe the type of experiment, its settings, its results, and the corresponding conclusions.

Analyzing the power formulas for the NIC and storage device

To analyze the power consumption of both components, we have run specialized benchmarks and applications for their saturation on a desktop computer. We do this experiment while waiting to make measurements on the SPIE company servers as part of the partnership with our laboratory and the SATT. The specifications of our testing elements are the following:

• Desktop computer:

-Motherboard: Gigabyte GA-890GPA-UD3H.

-CPU: AMD Phenom II x4 955 -3213.57 MHz.

-RAM: 4096 MB Dual Channel.

-Graphics card: Nvidia GeForce GT 710.

-Storage device: Western Digital WDC WDS 480 GB.

-OS: Windows 8 (free of installed programs).

123

Chapter 6

Experiments and results

• With a workload of 75%: 27.19 for Downloading op. and 8.99 for Uploading op.

• With a workload of 50%: 15.38 for Downloading op. and 5.29 for Uploading op.

• With a workload of 25%: 6.94 for Downloading op. and 2.41 for Uploading op.

These results are proportional to the load generated with the benchmarks. Inaccuracies shown may be due to irregular power consumption of the PC's internals. Moreover, we also see that the download operation is, on average, more expensive at 14.35W than the upload operation.

Conclusions and considerations

The results obtained from the measurements of the storage and NIC devices show the following findings:

• The power consumption is proportional to components load. That verifies our formulas 2.7 and 2.10. However, it is necessary to consider input and output operations differently.

• Reading, writing, uploading, and downloading operations may have different power consumption values.

• To improve the accuracy of consumption formulas for any component, it is necessary to consider the behavior of other PC internals.

To enrich the results of our following experiments, we will use the values shown here to describe the consumption of some devices in our scenarios.

Analyzing the distributed scheduling algorithms

This section describes the experiments and results for our two main scheduling algorithms. On the one hand, the one that Kaligreen implements by default. On the other hand, the distributed algorithm that based on multidimensional spatial structures.

To perform our experiments, we considered a collection of metrics to define devices' capabilities and hardware consumption variables. We gathered these values Analyzing the distributed scheduling algorithms Section 6.3 the first procedure did not only save energy compared to the second one; but were also smarter, keeping the QoS level as high as possible under heavy loads.

On the other hand, these movements were higher than the Kaligreen algorithm's, showing an average of 912.6 operations against 798.5, respectively. Even though this involves a higher average of data transferred (2610.29 MB and 13243.3 MB), the difference became non-significant considering they consumed 0.030 joules against 0.031 joules consumed by the Kaligreen's procedure. That is explained because mainly small microservices are moved under a heavy network resource load.

Overall, our multidimensional algorithm proved to be resilient under heavy workloads, keeping energy as low as possible and, in an inverse way, QoS as high as possible.

Conclusions and considerations

The results obtained in these experiments allow us to get the following findings:

• Running any of our distributed scheduling algorithms gives better results than the initial deployment.

• A distributed algorithm based on multidimensional data structures may perform fewer operations than a naive one, such as Kaligreen's default procedure.

If the opposite happens, it is always because the QoS value increases. That is because the structure always finds available candidates in an optimal search time.

• Kaligreen's default algorithm does not avoid oscillations or look for other candidates beyond its direct neighbors. For that reason, it does not always find good solutions in terms of consumption or QoS.

• The PISCO simulator allows efficient modeling, executing, and comparing of different planning algorithms.

This thesis work seeks to create and execute distributed tools and algorithms to save energy while maintaining the notion of QoS. For this, its chapters describe our proposal of a way forward toward intelligent distributed scheduling. The first step on this path is to have energy information usable by any distributed middleware and simulation tools. Chapter 2 studies this problem. In it, we provide energy formulas for four important hardware components (CPU, RAM, NIC, and storage) to describe the consumption of running applications in heterogeneous devices.

For the CPU, we have adapted equations that consider its frequency, capacitance, and voltage. Although this model has been tested, we believe that in the future, we need to seek or implement new approaches that consider last-technology capabilities such as dynamic overclocking or P-states. Then, we have also adjusted an already proven model for the RAM. Nevertheless, we need to study more heterogenous-representative equations for this component in the future. Finally, For the NIC and storage device, we have proposed and tested our formulas based on workload. Although they proved to be quite accurate, we have to consider further studying other interfaces like 5G, Bluetooth, different types of SSD, and others.

All the formulas will soon be tested on heterogenous environments provided by companies such as SPIES ICS.

Given the effectiveness of the four models described, we can argue that an application can be modeled with data obtained from the operating system. We have verified this fact using GNU/Linux interfaces, leaving the analysis of other operating systems for the future.

Our next step is to understand how distributed approaches work. For this, chapter 3 shows a different way of categorizing research works based on an algorithmic procedure. The strategy considers 1) important input variables such as hardware components load and devices positions, 2) scheduling operations as migrations or duplications, and 3) optimized variables such as QoS and energy consumption. Moreover, we study this flow in (de)centralized environments at different deployment levels, such as cloud, grid, or edge. That makes it easy to understand the scope of new scheduling proposals.

Chapter 7

Conclusions and Future work

To this day, we continue to study new techniques to enrich, publish, and validate our categorization policy.

Having explored state of the art in distributed environments, Chapter 4 describes our scheduling strategies. We have designed a distributed middleware called Kaligreen. It is aware of the software and hardware components of the devices on which it runs. Furthermore, it implements special communication methods that enable centralized and decentralized strategies in any network topology. Kaligreen includes a default algorithm that performs neighborhood microservices exchanges after negotiation and microservices-filtering processes.

Using Kaligreen, we have designed, implemented, and tested a fully decentralized algorithm inspired by multidimensional data structures, representing one of this thesis's major contributions. That considers the devices as nodes in a space with as many edges as the characteristics of said nodes. In this space, each device can find peers to negotiate microservice migrations or duplications at an optimal computational cost. We have chosen the MAAN network as our multidimensional space test instance. However, we have left evaluating and implementing other structures such as skip-graph for future work.

Observing the results of our algorithm, we can conclude that it is efficient to save energy while preserving the quality of service notion. In addition, our approach allows users to customize and prioritize their variables of interest. That is useful in multi-cloud environments, where the prices of the contracts are directly related to the dynamism of the quality of service offered, energy consumption, high availability, and others. On this matter, we are in the process of coordinating with important companies such as SPIES ICS.

On the other hand, to this day, we are implementing and evaluating an algorithm that considers data (based on barycenter heuristics) and microservices connections. This approach will soon be available and submitted for publication.

Finally, chapter 5 shows the design and implementation of PISCO, the simulator we created and use to deploy and evaluate our scheduling algorithms. The importance of our tool is to allow its users to focus solely on their scheduling heuristics. For this, PISCO implements an overlay as any data structure (graphs, trees, etc.), devices and software as dynamic objects, and middlewares as threads to execute any scheduling policies.

Long-term perspectives

One of the reasons for the energy waste linked to digital technology is the lack of knowledge about software and hardware behavior. That concerns any user, even novice, advanced, or expert users. For that reason, the future of PISCO and our algorithms have an industrial and scientific outlook. One free license is currently deployed in CRI/University Paris 1-Sorbonne. Moreover, a second one is now under deployment at L3I/ University La Rochelle. Next, a technological transfer is under discussion with SPIES ICS with AST Innovation (SATT Aquitaine) -this latter is at the juridic discussion level. In the coming months, we hope to verify scalability and robustness with real use cases with SPIES ICS.

Moreover, our works will also be used as a software-conception validation tool. In the context of a Ph.D. project (in collaboration with Spain), researchers are analyzing the software "footprint energy cost." The objective is to label services (individually) and applications (set of services collaborating).

The project above, jointly with ours, may help design applications while estimating their footprint according to their composition and hardware use. For that, it will integrate a software engineering part. Furthermore, our contribution set (PISCO and algorithms) is one of the two core aspects of a future industrial chair. It will be joined to a project on the domain of warehousing (Data Lakes) to help prove new architectures. On the one hand, the objective here is to apply energy-saving techniques more commonly found in dynamic approaches such as Edge/Fog Computing to the massive data analysis architectures, such as data lakes. On the other hand, it aims to perform information processing closer to their sources, enabling new analysis primitives (access/collection, cleaning, examination, consolidation, reporting) such as redundancies and sequencing awareness.

In this project, we need to perform two main operations: 1) Energetically quantify the different functional primitives of data analysis, and 2) quantify the analysis chains and weight them according to the architecture of the information system (massively distributed, sparsely distributed) and external operations (data refresh frequency, TTL -Time To Live, CRUD operation, format, and types, etc. ).

Figure 2 . 1 :

 21 Figure 2.1: Core's C-States[105].

Figure 2 . 2 :

 22 Figure 2.2: Memory module structure[216].

Figure 3 . 1 :

 31 Figure 3.1: Taxonomy Structure

  .4 are the continuation of Tables3.1 and 3.2), we characterize the works concerning the initial deployment of applications. Tables 3.1 and 3.3 describe the approaches' input variables, operations performed, or their type of policy (centralized/noncentralized). Tables3.2 and 3.4 illustrate the variables they analyze and/or optimize, such as QoS or energy consumption.

Figure 3 . 2 :

 32 Figure 3.2: Cloud computing: Initial Deployment Considerations Trend

Figure 3 . 3 :

 33 Figure 3.3: Cloud computing: Initial Deployment Variables Trend

Figure 3 . 4 :

 34 Figure 3.4: Cloud computing: Execution-time scheduling Considerations Trend

Figure 3 . 5 :

 35 Figure 3.5: Cloud computing: Execution-Time scheduling Variables Trend

Figure 3 . 6 :

 36 Figure 3.6: GRID/FOG/EDGE: Initial Deployment Considerations Trend

Figure 3 . 7 :

 37 Figure 3.7: GRID/FOG/EDGE: Initial Deployment -Scheduling Variables Trend

Figure 4 . 1 :

 41 Figure 4.1: Hardware resources' metadata sending process

Section 4. 3 Figure 4 . 2 :

 342 Figure 4.2: Application needs metadata sending process

Figure 4 . 3 :

 43 Figure 4.3: Space partitioning and mapping: (a)Z-curves at different orders, (b)corresponding partition tree[START_REF] Shu | Supporting multi-dimensional range queries in peer-to-peer systems[END_REF]

Figure 4 . 4 :

 44 Figure 4.4: (a) Finger table entries for node 8. (b) Path of a query for key 54 starting at node 8[207]

Figure 5 . 2 :

 52 Figure 5.2: Network data structure: Devices graph

Figure 5 . 3 :

 53 Figure 5.3: Network data structure: Multidimensional circular lists

Figure 5 . 4 :

 54 Figure 5.4: Devices in PISCO and their positions

𝑄𝑜𝑆 𝑀 =𝐼 1 4 ∑𝑖=0𝐼 𝑖 = 1 ( 5 . 1 )

 14151 𝐷 𝐶 + 𝐼 2 𝐷 𝑅 + 𝐼 3 𝐷 𝑁 + 𝐼 4 𝐷 𝐻 𝑤ℎ𝑒𝑟𝑒, For example, let us define that (1) 𝑀 needs a certain quantity of GHz of CPU, MB of RAM, and MB/s of NIC and storage transfer rate, (2) 𝑀 finds only half of these resources in 𝐷 (𝐷 𝐶 = 𝐷 𝑅 = 𝐷 𝑁 = 𝐷 𝐻 = 50%), and (3) the user decides to configure the impact factor of each resource equally to 0.25 for each component (𝐼 1 = 𝐼 2 = 𝐼 3 = 𝐼 4 = 0.25). Then, the QoS of 𝑀 is defined as follows: For example, let us define that (1) 𝑀 needs a certain quantity of GHz of CPU, MB of RAM, and MB/s of NIC and storage transfer rate, (2) 𝑀 finds the following resources available in D:[𝐷 𝐶 = 90%, 𝐷 𝑅 = 6%, 𝐷 𝑁 = 9%, 𝐷 𝐻 = 5%], and (3) the user decides to configure the impact factors of each resource as follows:[𝐼 1 = 0.7, 𝐼 2 = 0.1, 𝐼 3 = 0.1, 𝐼 4 = 0.1]. Then, the QoS of M is defined as: 𝑄𝑜𝑆 𝑀 = 0.7 × 90 + 0.1 × 6 + 0.1 × 9 + 0.1 × 5 𝑄𝑜𝑆 𝑀 = 73.2% (5.2)

Figure 5 . 5 :

 55 Figure 5.5: PISCO evaluation window

  Important considerations and future work . . . . . . . . . 2.4 The RAM's energy consumption . . . . . . . . . . . . . . . . . . . Important considerations and future work . . . . . . . . . 2.5 The NIC's energy consumption . . . . . . . . . . . . . . . . . . . 2.5.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Finding and optimizing the NIC's energy consumption . . 2.5.3 Proposal to measure the NIC's power consumption from the perspective of distributed algorithms . . . . . . . . . . 2.6 Storage device energy consumption . . . . . . . . . . . . . . . . . 2.6.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Finding and optimizing the hard drive's energy consumption

	1	Introduction
		vii

1 Introduction 1.1 Thesis Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Profiling applications' power consumption 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The CPU's energy consumption . . . . . . . . . . . . . . . . . . . 2.3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Finding and optimizing the CPU's energy consumption . 2.3.3 Proposal to measure the CPU's power consumption from the perspective of distributed algorithms . . . . . . . . . . 2.3.4 2.4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Finding and optimizing the RAM's energy consumption . 2.4.3 Proposal to measure the RAM's power consumption from the perspective of distributed algorithms . . . . . . . . . . 2.4.4

Table 2 .

 2

	The CPU's energy consumption	Section 2.3

1: Approaches to measure and optimize CPU energy consumption Chapter 2

Table 2 . 2 :

 22 Approaches to measure and optimize RAM energy consumption

	Chapter 2	Profiling applications' power consumption

  1) A string list of all available states if active state, 2) "freeze" if StI state, 3) "deep" if StR state and 4) "standby" if SbS state.

	The RAM's energy consumption	Section 2.4

Table 2 . 3 :

 23 Equivalence values to find RAM's background power consumption

	Memory power state	Memory system state (proposed equivalence)	Value (Watts)
	Self-refresh state(sf)	Suspend to RAM state (StR)	0.35
	CKEOFF state (ckeoff)	Suspend to Idle state (StI)	Standby State (SbS)	0.89
	CKEON state (act)	Active state (act)	1.56
	Additional consumption
	CKEON	Active state (𝑎𝑐𝑡 𝑖 )	0.098
	state per rank (𝑎𝑐𝑡 𝑖 )

  consider its power status as well as

	Chapter 2	Profiling applications' power consumption	The NIC's energy consumption	Section 2.5
		Techniques to measure NIC power/energy consumption
		Approach	Hardware manufacturing/ low level configuration	Stage of: Software Design and development Launching applications	Applications already running
		Study of topologies'
		and protocols'	X
		behavior
		Network architecture analysis		X
		Relate energy
		consumption
		with packets
		operations		X	X	X
		(read/write/
		discard)
		performed
		Relate energy
		consumption with bandwidth			X	X
		or transfer rate
		Study of devices' circuitry	X
		Techniques to optimize NIC power/energy consumption
		IOCTL CALLS	X
		Adjust payload size and transfer patterns	X
		Enable devices
		either to go into
		sleep mode or to	X		X
		adapt their
		transfer rate.
		Study network paths
		or the number of hops	X	X	X
		performed
		Intelligent distribution
		of data on the		X	X
		network
		Table 2.5: Approaches to measure and optimize NIC energy consumption

Table 2 . 6 :

 26 Approaches to measure and optimize storage device energy consumption

	Techniques to measure Hard Drive power/energy consumption
	Approach	Hardware manufacturing/ low level configuration	Stage of: Software Design and development Launching applications	Applications already running
	Perform physical measures	X			X
	Model consumption
	taking into account previous physical	X			X
	measures
	Model consumption
	taking into account application's I/O		X
	stages
	Model consumption
	taking into account		X	X	X
	files/VMs size
	Techniques to optimize NIC power/energy consumption
	Manage disk
	accesses to increase
	applications
	execution efficiency	X
	or to reduce the
	storage device
	energy consumption

Table 3 .

 3

	1: Cloud initial-deployment approaches: Input Variables | Operations performed -
	PART 1

Table 3 .

 3

2: Cloud initial-deployment approaches: Target Variables -PART 1

  pursue the same goal Scheduling in the cloud: Managing virtual entities in node clusters.

							Section 3.3
		INITIAL DEPLOYMENT IN THE CLOUD-OPERATIONS AND FEATURES -PART 2
	Ref.	Input Variables	Operations	Approach	Require pre-process ing/ learning	Consider special energy-related hardware features HDD, and NIC. of CPU, RAM,	Study computational complexity
	[136] [247] [140] [240]	-Containers HW resources. constraints. -Containers	-Filter nodes based on specified criteria criteria. and specified -Sort nodes based on HW resources	Centralized	YES	NO	NO
			-Use linear
		-Nodes'	equations to
		HW	deploy and
	[86]	resources.	equitably deliver	Centralized	YES	NO	NO
		-Tasks'	resources based
		HW load.	on dominant
			resources.
			-Create a
		-System/	component-based
	[131]	Application	tree.	Decentralized	NO	NO	NO
		specification.	-Perform breadth
			search in the tree.
	[248]	-Task execution time. resources. -Nodes' HW	-Sort tasks and nodes. enough resources. instance with -Perform matching: Most utilized	Centralized	YES	NO	YES
	[250] [249] [244]	-Applications' consumption history. -Applications' Behavior.	-Execute prediction algorithms.	Survey: Decentralized Centralized and	YES	NO	YES
		-Connected
		containers
		graph.
		-Nodes	-Linear
	[191]	Graph.	Programming	Centralized	YES	NO	NO
		-Nodes'/	Minimization.
		Containers
		HW
		resources.
	[203]	-Nodes' HW resources. load. HW -Containers'	-Random selection -Selectionbased on number. container HW usage and	Centralized	NO	NO	NO
	Our Work	-Nodes' HW resources. -Applications' HW consumption.	-Scheduling based on indexation in data structures. multidimensional	Centralized Decentralized and	NO	YES	YES

Table 3 .

 3

	3: Cloud initial-deployment approaches: Input Variables | Operations performed -
	PART 2

Table 3 .

 3

4: Cloud initial-deployment approaches: Target Variables -PART 2

  Scheduling in the cloud: Managing virtual entities in node clusters.

							Section 3.3
		EXECUTION-TIME SCHEDULING IN THE CLOUD -OPERATIONS AND FEATURES
	Ref.	Input Variables	Operations	Approach	Require pre-process ing/ learning	Consider special energy-related hardware features HDD, and NIC. of CPU, RAM,	Study computational complexity
	[89]	-Nodes' load thresholds set.	-Migrate, close and deploy VMs.	Centralized	NO	YES: and RAM's states CPU' MIPS	YES
		-VMs' HW
	[251]	resources. -tasks'	-Migrate, close and deploy VMs.	Centralized	NO	YES: CPU' MIPS	YES
		deadline.
		-Containers
		affinity,
		tolerations, etc.
		-Scalability,	-Migrate, destroy,
	[136]	high availability	start, duplicate	Centralized.	NO	NO	Linear search
		variables.	containers.
		-Custom
		schedule
		criteria.
		-Node's
	[248]	hardware load. -Node's load -Images size. time.	-Migrate, destroy, containers. start, duplicate	Centralized	NO	NO	YES
		-Bandwidth.
		-Node's
	[14] [198]	hardware load. -Applications' Images size.	-Migrate VMs/tasks.	Centralized	NO	NO	NO
		-Bandwidth.
			-Predict optimal
		-Applications'	execution-time
	[250] [244]	consumption -Applications' history.	scheduling -Perform operations.	Centralized Decentralized and	YES	NO	YES
		Behavior.	execution-time
			scheduling.
		-Node's
		hardware load.	-Migrate the
	[249]	-Applications' Images size.	lightest application with the shortest	Centralized	NO	NO	NO
		-Applications'	running time.
		running time.
	[203]	-Node's hardware load -Nodes health	-Migrate container resources to the node with enough	Centralized	NO	NO	NO
	Our Work	-Nodes' HW resources. -Applications' HW consumption.	-Scheduling based on indexation in data structures. multidimensional	Centralized Decentralized and	NO	YES	YES

Table 3 . 5 :

 35 Cloud execution-time approaches: Input Variables | Operations performed

	Chapter 3	The Distributed Approach
			EXECUTION-TIME SCHEDULING -Optimized/Analyzed Variables
										Efficient
		Ref.	HW res. usage	Deploy. time	QoS	Energy cons.	Monet. costs	Scalab.	High avail.	search/ insert/ delete for
										scheduling
		[89]

Table 3 .

 3

8: GRID/FOG/EDGE initial-deployment approaches: Target Variables most CPU/RAM-consuming containers. A list of new nodes in the system is sorted according to CPU usage.

  𝑉 𝑖 𝑗 ← 𝑏𝑢𝑖𝑙𝑑𝑉 𝑒𝑐𝑡𝑜𝑟 (𝑀 𝑖 𝑗 ); foreach 𝑐𝑜𝑛𝑛𝑒𝑐𝑡𝑒𝑑𝐷𝑒𝑣𝑖𝑐𝑒𝑠 𝐷 𝑙 do 𝑠𝑒𝑛𝑑𝑉 𝑒𝑐𝑡𝑜𝑟 (𝑉 𝑖 𝑗 , 𝐷 𝑙 ); 𝑚𝑜𝑣𝑒𝑀𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒 (𝑀 𝑖 𝑗 , 𝐷 𝑗 );

		Section 4.3
	Algorithm 1: Help seeker for a device 𝐷 𝑖
	𝑐 = 1;
	𝑀 𝑖 𝑗 ← 𝑠𝑒𝑙𝑒𝑐𝑡𝐻𝑒𝑎𝑣𝑖𝑒𝑠𝑡𝑀𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒 (𝑐);
	while isEmergencySituation() do
	if 𝑀 𝑖 𝑗 = 𝑁𝑈 𝐿𝐿 then
		𝑏𝑟𝑒𝑎𝑘;
	𝑊 𝑎𝑖𝑡𝐹𝑜𝑟𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑠𝑅𝑒𝑝𝑜𝑛𝑠𝑒𝑠 (20)
	foreach 𝑑𝑒𝑣𝑖𝑐𝑒𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠 do
		𝐷 𝑗 ← 𝑠𝑒𝑙𝑒𝑐𝑡𝐵𝑒𝑠𝑡𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒 ();
	if 𝐷 𝑗 = 𝑁𝑈 𝐿𝐿 then
		𝑀 𝑖 𝑗 = 𝑠𝑒𝑙𝑒𝑐𝑡𝐻𝑒𝑎𝑣𝑖𝑒𝑠𝑡𝑀𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒 (𝑐 + 1);
		𝑐𝑜𝑛𝑡𝑖𝑛𝑢𝑒;
	𝑠𝑒𝑛𝑑𝐶𝑜𝑛𝑓 𝑖𝑟𝑚𝑎𝑡𝑖𝑜𝑛(𝐷 𝑗 );
	foreach 𝑁𝑜𝑛𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠𝐷 𝑤 do
		𝑠𝑒𝑛𝑑𝑁 𝑒𝑔𝑎𝑡𝑖𝑣𝑒𝐶𝑜𝑛𝑓 𝑖𝑟𝑚𝑎𝑡𝑖𝑜𝑛(𝐷 𝑤 );
	𝑤𝑎𝑖𝑡 ()
	Algorithm 2: Resource provider procedure for a device 𝐷 𝑗
	if 𝑖𝑠𝐸𝑚𝑒𝑟𝑔𝑒𝑛𝑐𝑦𝑆𝑖𝑡𝑢𝑎𝑡𝑖𝑜𝑛() ≠ 𝑡𝑟𝑢𝑒 then
	foreach 𝑉 𝑒𝑐𝑡𝑜𝑟𝑠 𝑉 𝑘 𝑜 𝑓 𝑒𝑎𝑐ℎ 𝑑𝑒𝑣𝑖𝑐𝑒 𝐷 𝑘 do
		𝐸𝑣𝑎𝑙𝑢𝑎𝑡𝑒𝐸𝑛𝑒𝑟𝑔𝑦𝐼𝑚𝑝𝑎𝑐𝑡 (𝑉 𝑘 );
		if 𝑡𝑟𝑖𝑔𝑔𝑒𝑟𝑠𝐸𝑚𝑒𝑟𝑔𝑒𝑛𝑐𝑦𝑆𝑖𝑡𝑢𝑎𝑡𝑖𝑜𝑛(𝑉 𝑘 ) then
	5	𝑑𝑒𝑙𝑒𝑡𝑒 (𝑉 𝑘 );
	𝑉 𝑐 ← 𝑠𝑒𝑙𝑒𝑐𝑡𝐻𝑒𝑎𝑣𝑖𝑒𝑠𝑡𝑀𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝑉 𝑒𝑐𝑡𝑜𝑟 ();
	𝑠𝑒𝑛𝑑𝐶𝑜𝑛𝑓 𝑖𝑟𝑚𝑎𝑡𝑖𝑜𝑛(𝐷 𝑘 );
	𝑟𝑒𝑐𝑒𝑖𝑣𝑒𝑀𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒 (𝑀 𝑖 𝑗 );

Table 4

 4 .1 shows this correlation.

	Microservices' Features in 𝑫 𝒊	CPU features in 𝑫 𝒋
	Persistent Microservice	High CPU Load	Boosting	PCPG	DVFS
	NO	YES	Candidate Candidate Candidate
	NO	NO	-	-	-
	YES	YES	-	Candidate Candidate
	YES	NO	Candidate Candidate Candidate

Table 4 . 1 :

 41 Correlation between Microservices features and CPU capabilities

	Microservices' Features in 𝑫 𝒊	Scheduling Operations
	Persistent Microservice	High RAM Load	Migration
	NO	YES	Candidate
	NO	NO	-
	YES	YES	Candidate
	YES	NO	-

Table 4 .

 4

2: Correlation between RAM microservices features and middleware operations

Table 4 .

 4

	Storage Type

3: Correlation between the storage-related microservices and storage features

Table 4 . 4 :

 44 Correlation between the network-related microservices features and middleware operations

	Chapter 4	Multidimensional entities for energy savings
			Microservices' Features in 𝑫 𝒊		Scheduling operations
		Persistent MS	High MS size	High Bandwidth Load	High load generated by the MS connections	High data size	MS Migration	MS Duplication	MS Data Migration
		YES	YES	YES	YES	YES	Candidate	Candidate	-
		YES	YES	YES	YES	NO	Candidate	Candidate	Candidate
		YES	YES	YES	NO	YES	Candidate	Candidate	-
		YES	YES	YES	NO	NO	Candidate	Candidate	Candidate
		YES	YES	NO	YES	YES	-	Candidate	-
		YES	YES	NO	YES	NO	-	Candidate	Candidate
		YES	YES	NO	NO	YES	Candidate	Candidate	-
		YES	YES	NO	NO	NO	Candidate	Candidate	Candidate
		YES	NO	YES	YES	YES	Candidate	Candidate	-
		YES	NO	YES	YES	NO	Candidate	Candidate	Candidate
		YES	NO	YES	NO	YES	Candidate	Candidate	-
		YES	NO	YES	NO	NO	Candidate	Candidate	Candidate
		YES	NO	NO	YES	YES	Candidate	Candidate	-
		YES	NO	NO	YES	NO	Candidate	Candidate	Candidate
		YES	NO	NO	NO	YES	Candidate	Candidate	-
		YES	NO	NO	NO	NO	Candidate	Candidate	Candidate
		NO	YES	YES	YES	YES	-	-	-
		NO	YES	YES	YES	NO	-	-	-
		NO	YES	YES	NO	YES	Candidate	Candidate	-
		NO	YES	YES	NO	NO	Candidate	Candidate	Candidate
		NO	YES	NO	YES	YES	-	Candidate	-
		NO	YES	NO	YES	NO	-	Candidate	Candidate
		NO	YES	NO	NO	YES	-	-	-
		NO	YES	NO	NO	NO	-	-	-
		NO	NO	YES	YES	YES	Candidate	Candidate	-
		NO	NO	YES	YES	NO	Candidate	Candidate	Candidate
		NO	NO	YES	NO	YES	Candidate	Candidate	-
		NO	NO	YES	NO	NO	Candidate	Candidate	Candidate
		NO	NO	NO	YES	YES	-	-	-
		NO	NO	NO	YES	NO	-	-	Candidate
		NO	NO	NO	NO	YES	Candidate	Candidate	-
		NO	NO	NO	NO	NO	Candidate	Candidate	Candidate

  𝐽 ∀𝐾 (𝑓 𝑖 > 𝑓 𝑘 > 𝑓 𝑗 )

		100 × 𝐼 𝐷2	(𝑇 ) + 𝑓 𝑎𝑛𝑠 𝑠 (𝑡), 𝑤ℎ𝑒𝑟𝑒
	𝐶 𝐷2 =	0.7 × 𝑇 𝐷𝑃 𝐷2 𝑇 𝐷𝑃 𝐷2 𝑓 𝑇 𝐷𝑃 𝐷2 × 𝑉 2	, 𝑎𝑛𝑑
	𝑓 𝑎𝑛𝑠 𝑠 =

  the 𝑊 𝑆 𝐷2 and 𝑊 𝑅 𝐷2 values to represent 𝐷2 ′ 𝑠 NIC power consumption when sending and receiving packets, (2) the number of packets sent (𝑁 𝑆 𝑀 𝐷 ) or received (𝑁 𝑅 𝑀 𝐷 ) in 𝐷, (3) the respective average packets' size (𝑆 𝑥 𝐷 ) in 𝐷, and (4) the corresponding total transfer speed (𝐿 𝑀𝐴𝑋 𝑥 𝐷2 ) of 𝐷2. 𝐸 𝑁 𝐼𝐶 𝐷2 𝑀 =𝑊 𝑆 𝐷2 × 𝑁 𝑆 𝑀 𝐷 × 𝑆 𝑠 𝐷 𝐿 𝑀𝐴𝑋 𝑠 𝐷2 + 𝑊 𝑅 𝐷2 × 𝑁 𝑅 𝑀 𝐷 × 𝑆 𝑟 𝐷 𝐿 𝑀𝐴𝑋 𝑅 𝐷2

	,

  Algorithm 3: Help seeker for a device 𝐷 𝑖 indexed in U

		An energy-saving approach: Understanding microservices and devices as multidimensional entities	Section 4.4
	1 𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 ← 𝐾𝑎𝑙𝑖𝑔𝑟𝑒𝑒𝑛𝑉 2𝐹𝑖𝑙𝑡𝑒𝑟𝑖𝑛𝑔();
	2 𝑠𝑜𝑟𝑡𝐵𝑦𝐾𝑎𝑙𝑖𝑔𝑟𝑒𝑒𝑛𝑉 1𝑓 𝑎𝑐𝑡𝑜𝑟𝑠 (𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡);
	3 𝑠𝑖𝑧𝑒 ← 𝑠𝑖𝑧𝑒 (𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡);
	4 while isEmergencySituation() or isUnderLoadSituation() do
	5	𝑀 𝑖 𝑎 = 𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 [𝑠𝑖𝑧𝑒];
	6	𝑀 𝑖 𝑏 = 𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 [𝑠𝑖𝑧𝑒/2];
	7	𝑀 𝑖 𝑐 = 𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 [0];
	8	if MoveMicroservice(𝑀 𝑖 𝑎 ) = true then
	9	𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 .𝑑𝑒𝑙𝑒𝑡𝑒 (𝑀 𝑖 𝑎 );
		𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 -1;
		𝑐𝑜𝑛𝑡𝑖𝑛𝑢𝑒;
		else if MoveMicroservice(𝑀 𝑖 𝑏 ) = true then
		𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 .𝑑𝑒𝑙𝑒𝑡𝑒 (𝑀 𝑖 𝑏 );
		𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 -1;
		𝑐𝑜𝑛𝑡𝑖𝑛𝑢𝑒;
		else if MoveMicroservice(𝑀 𝑖 𝑐 ) = true then
		𝑚𝑖𝑐𝑟𝑜𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝐿𝑖𝑠𝑡 .𝑑𝑒𝑙𝑒𝑡𝑒 (𝑀 𝑖 𝑐 );
		𝑠𝑖𝑧𝑒 = 𝑠𝑖𝑧𝑒 -1;
		𝑐𝑜𝑛𝑡𝑖𝑛𝑢𝑒;
		else
		𝑏𝑟𝑒𝑎𝑘;
		if loadEmpty(allResources) then
		𝑠𝑙𝑒𝑒𝑝 ();
		𝑤𝑎𝑖𝑡 ();

https://askubuntu.com/questions/876286/how-to-monitor-the-vcore-voltage

[86] X X X [131] X X X X [248] X X X X X X X [250] [249] [244] X X X X X [191] X X X [203] X X X X Our work X X X X X X

As mentioned above, MAAN generalizes the Chord approach to support n-dimensional and range queries. To begin, consider a space whose nodes have several attributes to index. On the one hand, MAAN uses an SHA-1 hashing function to assign an 𝑚 -𝑙𝑒𝑛𝑔𝑡ℎ bits identifier to each node. On the other hand, it implements a locality preserving hashing function that, unlike Chord, assigns to each node's attribute an identifier in the 𝑚 -𝑏𝑖𝑡 space according to its value (the same space shared by the 𝑚 -𝑏𝑖𝑡𝑠 node identifiers specified before). The latter is crucial because the SHA-1 function would destroy the locality of keys since MAAN seeks to pair numerical attribute values to them instead of objects' names. That allows the execution of two different multi-attribute query resolution approaches that would not be possible within Chord's original system:1. The iterative approach: It consists of a query originated in a node 𝑁 . That is composed of an 𝑀 number of following sub-queries according to the 𝑛 number of attribute dimensions. The query returns a series of candidate lists later intersected in 𝑁 to find the fittest candidates.2. The single attribute query resolution: It aims to find a set of candidates 𝑋 by performing queries fulfilling the conditions of a single dominating attribute.

Table 3.10: GRID/FOG/EDGE execution-time approaches: Target Variables threshold, the system executes a migration strategy. That consists of redeploying said container in the node-edge that 1) Is the closest possible to the new location of the device and 2) has sufficient resources in terms of CPU and RAM.

Finally, some works study the communication between tasks and distributed data management. For example, Corneo et al. [START_REF] Corneo | Scheduling at the Edge for Assisting Cloud Real-Time Systems[END_REF] propose an optimal way to retrieve data from sensors. They aim to avoid bandwidth overload and lose the novelty of the data. As in the previous section, this area of study is outside the scope of our research work.

Analysis and considerations

This section has described some approaches that we consider important for initial deployment and in-execution scheduling at the edge, fog, and grid levels.

Again, following the methodology described in the first section, we study this trend from an algorithmic approach. However, unlike in the previous section, we have changed some analysis criteria due to the natural differences between Cloud and edge/grid/fog heuristics. Thereby, in Tables 3.7 and 3.8 , we characterize the works concerning the initial deployment of a certain workload, taking into ware features than the initial deployment moment. It is important to say that our approach addresses this point at both scheduling moments.

The analysis of the rest of the variables is the same as the one we did for figure 3.6. Finally, figure 3.9 shows a greater tendency to maintain an optimal network balance and energy use. That is because many works perform scheduling operations based on the position changes of some devices.

Chapter 3

The Distributed Approach them, we can perform efficient queries enabling different scheduling objectives such as energy savings, security, location dynamism, etc.

The next chapter will present our approach's structure, algorithm, and deployment.

Chapter 4

Multidimensional entities for energy savings

• Select an ideal microservice 𝑀 to be moved or duplicated,

• Find ideal peer(s) that meet the 𝑀 requirements in an optimal computational complexity, and

• Negotiate the migration or duplication of 𝑀 considering energy consumption and QoS criteria.

Before explaining this approach in detail, it is first necessary to understand the concept and operations of multidimensional spaces. We detail this in the following section.

Multidimensional spaces

Data management is a big concern in computer science. For this reason, some structures allow modeling data sets as spaces with as many dimensions as the data sets have characteristics. They allow data insertions, search, and recovery at efficient operation costs. For example, all binary-based trees like AVL, RedBlack, and B* perform one-dimensional data management operations in 𝑂 (𝑙𝑜𝑔(𝑁 )) for the average case. At the same time, hash-based structures do the same in 𝑂 (1) for the best case.

However, these operations become more complicated with the increment of dimensions (data characteristics). Several solutions based on metrics (defined by distance functions) and-or n-dimensional spaces deal with this problem. They can manage multi-dimensional data sets from the viewpoint of 1) The distances among its elements [START_REF] Chávez | Searching in Metric Spaces[END_REF] (e.g., BKT, BT, or LAESA) or 2) the abstraction of the universe in which they exist [START_REF] Gaede | Multidimensional Access Methods[END_REF] (e.g., K-D-Tree, R*tree or Z-ordering).

All these data management approaches allow, on the one hand, to process queries based on a single characteristic/dimension to obtain a single element. On the other hand, they also retrieve all data that meet various criteria in a specific range or region. Furthermore, depending on the structure heuristic, they operate from the viewpoint of one particular element or the viewpoint of the entire universe. For example, while BKT organizes the elements from a centroid-element, the RTree models all the data universe in a rectangle-based heuristic.

Edgar Chavez et al. [START_REF] Chávez | Searching in Metric Spaces[END_REF] describe the possible queries in multidimensional metric spaces, which are also applicable in spatial access methods.

• Range query (𝑞, 𝑟 ) 𝑑 . Retrieve all elements which are within distance 𝑟 to 𝑞. This is, {𝑢 ∈ 𝑈 | 𝑑 (𝑞, 𝑢) ≤ 𝑟 }.

Chapter 4

Multidimensional entities for energy savings KaligreenV2 criteria, the method projects the power consumption considering the approaches explained in section 4.4.6. The function ends by migrating 𝑀 to the device where it will consume the least amount of power.

Algorithm 4: MoveMicroservice(M)

Chapter summary and contributions

This chapter presents our distributed scheduling algorithms and the tools they need to be deployed. Among the latter, our middleware Kaligreen implements resource analysis and device negotiation operations in each network node. These tools have allowed us to develop procedures considering various heuristics. For example, from a design point of view, we have defined various types of microservices, data, and application graphs. Then, we implemented distributed scheduling using smart microservice-data selection, simple negotiations, multidimensional spaces, and

Chapter summary and contributions Section 4.5

special data structures to schedule them. To the best of our understanding, this is the first work that approaches distributed scheduling for energy savings in this way.

The next chapter will describe PISCO, the simulator we have created to execute and test the architecture and algorithms explained here. This tool allowed us to define heterogeneous applications, devices, and networks easily. Moreover, it allowed us to run and evaluate our scheduling algorithms efficiently.

Chapter 5

The PISCO Simulator • Feature D. Considers special types of microservice management.

• Feature E. Considers energetic issues when operating microservices.

• Feature F. Considers communication phenomena among services.

• Feature G. Considers Microservices dependencies when operating them.

• Feature H. Supports centralized and non-centralized scheduling algorithms, allowing to model dynamic architectures and energy-QoS criteria easily.

• Feature I. Allows a transparent way of creating custom network overlays such as multidimensional P2P networks.

For us, it's important to enable deploying and scheduling modular applications, focusing mainly on their performance and impact in any distributed environment. For this reason, table 5.1 shows the philosophy of our simulator. PISCO is strongly focused on applying both centralized and distributed scheduling algorithms, allowing to study at deployment/execution time the following criteria: 1) The definition, measurement, and modelization of applications QoS, 2) the workload of each node's hardware components, and 3) the energy consumption of a particular device (or even one/some of its hardware components) as well as of the entire custom network.

Chapter 5

The PISCO Simulator

Device

In PISCO, a device is any processing entity identifiable by a unique ID. By default, it supports desktop computers, laptops, and smartphones. Moreover, users can also define and configure their own type of device.

Each device has different capabilities in terms of CPU, RAM, hard drive, network, and battery (optional), depending on its type and custom configuration. However, users can also create different hardware components for each device.

On the other hand, each device can execute microservices, providing hardware resources according to their needs. For that, PISCO supports scheduling philosophies such as proportional share scheduling, round-robin, or a simplified version of CFS [START_REF]The Linux kernel[END_REF], which uses a red and black tree to organize processes.

Finally, each device implements a distributed middleware (like the supervisor service in section 4.3). On the one hand, the latter manages the default device's hardware components according to the following criteria:

• CPU:

The PISCO Simulator Herein, PISCO detects the iteration in the second 45 as the best since the QoS is the highest possible (100%) and the network power consumption the lowest (978𝑊 ). The rest of the curve results from deploying several microservices after said second, provoking the simulator to restart the algorithm looking for another solution.

(Non)centralized scheduling algorithm Start/Stop When PISCO launches a scheduling algorithm, it starts the concerning middlewareinstances threads (the master's one for centralized and all the devices' middleware for non-centralized). Then, the simulator automatically displays the following metrics for performance analysis: (1) Run time, (2) number of operations performed, (3) data transmitted by movements/duplications on a device or across the network, (4) energy used for movements/duplications on a device or across the network, and (5) per device and global load. For example, the screenshot in the figure 5.6 shows these variables.

The storage device

To measure the storage device's power consumption, we ran for half an hour the following benchmarks with our power monitor connected to the PC's power source: AS SSD Benchmark [START_REF]AS SSD Benchmark[END_REF], Crystal Disk Mark [START_REF]CrystalDiskMark[END_REF], SiSoftware Sandra [199]. These saturate the hard disk in its read and write operations, using the rest of the hardware components as little as possible.

We did four types of experiments to study four levels of workloads in the component. We ran the benchmarks so that they saturate 100%, 75%, 50%, and 25%, of the storage's read and write capacity. We choose this method to study the relationship between workload and power consumption (see section 2.6). To perform these percentages, we have programmed a script that interrupts the benchmark proportionally to these values during each experiment's time. We did this by mimicking the operation of any operating system. That is, giving the full access of the resource to a process for a time calculated from its priority and other competing processes. 67.20 67.7 Table 6.1: Measurement results for the Storage Device Table 6.1 shows the measurement results. It is important to note that the difference in consumption between using and not using a benchmark is as follows:

• With a workload of 100%: 8.61 for Writing op. and 6.66 for reading op.

• With a workload of 75%: 4.2 for Writing op. and 2.5 for reading op.

Analyzing the power formulas for the NIC and storage device Section 6.2

• With a workload of 50%: 4.03 for Writing op. and 1.5 for reading op.

• With a workload of 25%: 1.95 for Writing op. and 0.59 for reading op.

These results are proportional to the load generated with the benchmarks. Inaccuracies shown may be due to irregularities in power consumption and management of other PC's internals.

On the other hand, it is important to point out that the average consumption found for a load of 100% is approximately 6 and 4 watts higher than indicated in the disk datasheet [187], respectively, for each operation. These differences correspond to the other peripherals' functions.

Finally, we also find that the write operation is, on average, more expensive at 1.9W than the read operation.

The NIC

Using the same instruments and methodology as the previous device, we run the SpeedTest[204] and nPerf[174] online tools at the following four intensities: 100%, 75%, 50%, and 25% of the NIC Download-Upload capacity. 6.2 shows the measurement results. The difference in consumption between using and not using a benchmark is as follows.

• With a workload of 100%: 37.07 for Downloading op. and 12.46 for Uploading op.

Analyzing the distributed scheduling algorithms Section 6.3 from data sheets, public hardware benchmarks, and the last section's experiments.

That is to approximate results to real scenarios, facilitating the interpretation of results. Finally, we use our PISCO simulator (see section 5) as a tool for the algorithms' deployment, execution, and analysis of results.

Defining devices' capabilities

Chapter 2 considers four different devices' hardware capabilities to study the relation between load, QoS, and energy consumption: CPU frequency (GHz), RAM capacity (MB), storage transfer rate (MB/s), and finally, NIC data transfer rate (MB/s).

In our test scenarios, we considered devices with random delimited values for each hardware component capacity. For that, we choose tools that provide us with an insight into hardware resources available in the market. Table 6.3 shows this heterogeneity approach.

CPU (GHz) RAM (MB) NIC (Mb/s) Disk (MB/s) To define the CPU and RAM intervals, we studied public hardware benchmarks performed independently by millions of users [START_REF] Tuxera | CPU frequency[END_REF] [START_REF]Memory Benchmarks[END_REF]. Next, to define the NIC and storage intervals, we used hardware and software specialized websites that perform independent tests [START_REF]SSD vs HDD Tested: What's the Difference and Which Is Better?[END_REF][122].

Defining power consumption values

As for the devices' capabilities, we selected CPU consumption values following information sheets which consider overclocking, voltage, capacitance, and others [START_REF]Intel. Intel Core i5-8400 Processor[END_REF][107] [START_REF]Intel. Understanding Load Capacitance and Access Time[END_REF]. Then, we obtained the other components' values from manufacturers' datasheets, our last experiment, and scientific hardware specifications [START_REF]Crucial. How Much Power Does Memory Use?[END_REF][195] [START_REF] Samsung | Samsung V-NAND SSD 860 EVO[END_REF] [START_REF] Chiaravalloti | Power consumption of WLAN network elements[END_REF]. Table 6.4 shows this heterogeneity approach.

Chapter 6

Experiments and results

CPU

Scalability test

The objective of this test was to challenge our scheduling algorithms with increasing numbers of microservices and devices over time. The test begins with 20 heterogeneous devices and 40 heterogeneous microservices. The duration of the experiment consists of 100 seconds, deploying ten random microservices and ten random devices every 10 seconds for the first 80 seconds, leaving 20 final seconds to the scheduling algorithm for stabilizing.

We performed this experiment 100 times to ensure repeatability of testing and consistency of the results.

Stress test

The objective of this experiment was to prove the resilience of the algorithms when faced with a constant change in microservices execution. For that, we introduced a Analyzing the distributed scheduling algorithms Section 6.3 time constraint feature for the latter, which gave them a specific "time to finish." That time ranged from 5 to 30 seconds for the whole test duration of 100 seconds.

This test begins with 250 random microservices deployed among 50 heterogeneous devices. Then we randomly added microservices while the existing ones disappeared. Here, the test guaranteed the network to be stressed.

This experiment was also performed 100 times to ensure repeatability of testing and consistency of the results.

Tests metrics definition

To evaluate the performance of our approach, we analyzed five variables in our two experiments.

• The energy consumed by the entire network (Joules).

• The QoS achieved on average by all microservices executed in the network.

• The average number of movements performed by the algorithm.

• The data is transferred by microservices movements (MB).

• Energy cost of microservices movements (Joules).

Definition of "success"

To correctly interpret the data results as a "success," we compared the ones of our two algorithms against the original deployment consumption. For that, we considered the same conditions and number of experiment repetitions.

We cataloged our algorithms as successful if, in their results, the energy consumption is either lowered or kept the same while increasing on QoS. That is because the latter is always a crucial variable in any distributed system.

Scalability test results

As table 6.6 shows, in the experiments, the multidimensional-based algorithm proved to consume a total average of 27% less energy (692020.73 joules) than the scenario with no algorithm (95452.72 joules) and 11% less energy against the Kaligreen algorithm (98570.94 joules).

Furthermore, the average QoS sustained by the multidimensional-based algorithm was more significant than in the other experiments. The first algorithm

Chapter 6

Experiments and results scored an average of 99.24% of QoS against 94.04% of the no-algorithm experiments and 99.21% of the kaligreen algorithm.

It's important to point out that the multidimensional-based and Kaligreen's algorithms performed an average of 55.70 and 50.35 movement operations, transferring 850.29 MB against 775.83 MB, respectively. However, although the number of operations it executed was higher, the multidimensional algorithm proved to have better overall power management. After evaluating these results, we can consider our experiment a success, stating that our algorithm is scalable and stable.

Stress test results

This experiment revealed an interesting behavior for the multidimensional approach against the other alternatives. As it is possible to see in table 6.7, this algorithm consumed a total average of 69% more energy (578315.4 joules) than the no-algorithm experiments (340372.9 joules. Nevertheless, that keeps a low level of QoS because of the lack of scheduling operations) and 4% less energy than the naive algorithm (598737.0 joules).

However, the most revealing information shown by this test was the average QoS sustained by each approach. The multidimensional algorithm scored an average of 92.71% of QoS against the average of 87.61% sustained by Kaligreen's algorithm and 87.05% sustained when no algorithm was applied. That demonstrates that the movements performed by