SYSTEM AND METHOD FOR ENABLING AN EXECUTION OF A PLURALITY OF TASKS IN A HETEROGENEOUS DYNAMIC ENVIRONMENT

FIELD

The invention relates to data processing. More precisely, one or more embodiments of the invention pertain to a method and system for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment.

BACKGROUND

Being able to use a plurality of processing devices for executing tasks is of great advantage for various reasons.

However in many cases the use of a plurality of processing devices can be challenging.

For instance, the processing devices may be of various types rendering the execution complicated.

Another issue is the fact that the environment may be dynamic.

There is a need for at least one of a method and a system that will overcome, inter alia, at least one of the above-identified drawbacks.

Features of the invention will be apparent from review of the disclosure, drawings and description of the invention below.

BRIEF SUMMARY

According to a broad aspect there is disclosed a system for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment, the system comprising a plurality of heterogeneous host machines, each heterogeneous host machine being characterized by corresponding processing resources, each heterogeneous host machine comprising: a telecommunication application for enabling the heterogeneous host machine to be part of a telecommunication network with at least one other heterogeneous host machine; a virtualization engine for executing a received virtualized element using the corresponding processing resources of the heterogeneous host machine; a geolocation module for providing at least an indication of a present position of the corresponding heterogeneous host machine; a distributed system orchestrator for managing an execution of a plurality of tasks using at least one of the plurality of heterogeneous host machines, wherein the plurality of tasks is comprised of a corresponding plurality of virtualized elements, the distributed system orchestrator comprising: a telecommunication application for enabling the distributed system orchestrator to be part of the telecommunication network comprising at least one heterogeneous host machine of the plurality of heterogeneous host machines and a task assignment module for assigning each virtualized element of the plurality of virtualized elements to a selected heterogeneous host machine located on the telecommunication network, wherein the assigning of the virtualized element is performed according to a given multi-period workload placement problem; wherein the given multi-period workload placement problem is determined by the distributed system orchestrator using at least the indication of a present position of each available heterogeneous host machine and an indication of corresponding resource availability in at least one heterogeneous host machine of the plurality of heterogeneous host machines and in accordance with at least one given criterion.

According to one or more embodiments, the multi-period workload placement problem is determined by the distributed system orchestrator using information related to heterogeneous host machines joining or leaving the telecommunication network.

According to one or more embodiments, the telecommunication network comprises a virtual ad hoc mobile telecommunication network. According to one or more embodiments, the multi-period workload placement problem is amended in response to a given event.

According to one or more embodiments, the given event comprises a change in resources available.

According to one or more embodiments, the amendment of the multi-period workload placement problem comprises transferring a virtualized element from a first given heterogeneous host machine directly to a second given heterogeneous host machine.

According to one or more embodiments, the heterogeneous host machines are wireless host machines, further wherein the at least one given criterion is selected from a group consisting of a minimization of host machine utilization costs; a minimization of a number of migrations; a minimization of energy consumption; a minimization of refused workloads; a minimization of host machine physical movements; a throughput of at least one given host machine; a spectrum sharing behavior between at least two pairs of host machines; and an interference between at least two pairs of host machines.

According to one or more embodiments, the telecommunication application of the distributed system orchestrator reserves dedicated suitable routing paths according to the multi-period workload placement problem.

According to one or more embodiments, the given multi-period workload placement problem is further determined using at least one telecommunication network property.

According to one or more embodiments, the at least one telecommunication network property problem comprises at least one of a latency for transferring a first given virtualized element to a given heterogeneous host machine; a latency for migrating a second given virtualized element from a first given heterogeneous host machine to a second given heterogeneous host machine and a network topology.

According to one or more embodiments, the geolocation module further provides an indication of a possible future position of the corresponding heterogeneous host machine; further wherein the given multi-period workload placement problem is further determined using the indication of a possible future position of the corresponding heterogeneous host machine.

According to one or more embodiments, each heterogeneous host machine is being assigned an indication of a corresponding reputation; further wherein the given multi-period workload placement problem is further determined using the indication of a corresponding reputation.

According to one or more embodiments, each heterogeneous host machine comprises an energy module for providing an indication of a corresponding level of energy available; further wherein the given multi-period workload placement problem is further determined using the indication of a corresponding level of energy available.

According to a broad aspect, there is disclosed a method for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment, the method comprising providing a plurality of heterogeneous host machines, each given heterogeneous host machine having corresponding processing resources, each given heterogeneous host machine comprising a telecommunication application for enabling the given heterogeneous host machine to be part of a telecommunication network with at least one other heterogeneous host machine, a virtualization engine for executing a received virtualized element using the corresponding processing resources, and a geolocation module for providing at least an indication of a present position of the given heterogeneous host machine; providing a distributed system orchestrator for managing an execution of a plurality of tasks using at least one of the plurality of heterogeneous host machines with a corresponding telecommunication application for enabling the distributed system orchestrator to be part of the telecommunication network comprising at least one available heterogeneous host machine of the plurality of heterogeneous host machines and with a task assignment module for assigning each virtualized element of the plurality of virtualized elements to a selected heterogeneous host machine located on the telecommunication network; receiving, using the distributed system orchestrator, a plurality of tasks to execute, each task comprising a corresponding plurality of virtualized elements; obtaining, using the distributed system orchestrator, an indication of a present location of each available heterogeneous host machine; obtaining, using the distributed system orchestrator, an indication of a resource availability for each available heterogeneous host machine; determining, using the distributed system orchestrator, a multi-period workload placement problem using the received indication of a present location of each available heterogeneous host machine and the indication of a resource availability of each available heterogeneous host machine; and for each task of the plurality of tasks assigning each corresponding virtualized element of the plurality of corresponding virtualized elements to a corresponding host machine using the determined multi-period workload placement problem.

According to one or more embodiments, the method further comprises executing each of the assigned virtualized elements using the corresponding heterogeneous host machine.

According to one or more embodiments, the method further comprises amending the multi-period workload placement problem in response to a given event.

According to one or more embodiments, the method further comprises assigning, for each of the plurality of heterogeneous host machines, an indication of a corresponding reputation; further wherein the determining of the multi-period workload placement problem is further performed using the plurality of indications of a corresponding reputation.

According to one or more embodiments, the method further comprises obtaining an indication of a corresponding level of energy available in each of the plurality of heterogeneous host machines; further wherein the determining of the multi-period workload placement problem is further performed using the obtained indications of a corresponding level of energy available.

It will be appreciated that the system and the method disclosed above are of great advantage for various reasons.

A first reason is that they enable to use a plurality of heterogeneous host machines to execute a plurality of tasks in a dynamic environment.

Another reason is that they enable the use of heterogeneous host machines. BRIEF DESCRIPTION

In order that the invention may be readily understood, embodiments of the invention are illustrated by way of example in the accompanying drawings.

Figure 1 is a diagram which shows a system for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment comprising three heterogeneous host machines and a distributed system orchestrator.

Figure 2 shows an example of step-wise function that may represent the relationship between maximum throughput of a wireless link and the corresponding receiver distance in line of sight.

Figure 3 shows an example of a convex resource-utilization cost function that tends to infinite as utilization approaches 100%. Figure 4 shows an example of virtual application graph transformation (for application z eZ) to create a P-resilient application (with P = 2). For any virtualized element i e Vz (virtual container or virtual storage node) of application z e Z, a new virtualized element j e Vz is added to the virtual graph GzV (Vz, Az). In addition, each replicated node j e Vz is connected to the parent original node i by a new bidirectional virtual traffic demand (i, j) e Az.

Figure 5 shows an example of virtual application graph transformation to split computing from storage entities.

Figure 6 is a high-level multi-period workflow (3-stages) of a collaborative 3D mapping application.

Figure 7 shows a pair of virtual graphs representing the plurality of tasks, that regrouped in the corresponding minimal set of virtualized elements, allows to execute a collaborative 3D mapping mission powered by UAVs.

Figure 8 shows a pair of virtual graphs.

Figure 9 shows an embodiment of a method for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment.

Further details of the invention and its advantages will be apparent from the detailed description included below.

DETAILED DESCRIPTION

In the following description of the embodiments, references to the accompanying drawings are by way of illustration of an example by which the invention may be practiced. Terms

The term "invention" and the like mean "the one or more inventions disclosed in this application,” unless expressly specified otherwise.

The terms“an aspect,” "an embodiment,” "embodiment,” "embodiments,” "the embodiment,” "the embodiments,” "one or more embodiments,” "some embodiments,” "certain embodiments,” "one embodiment,” "another embodiment" and the like mean "one or more (but not all) embodiments of the disclosed invention(s),” unless expressly specified otherwise.

A reference to "another embodiment" or“another aspect” in describing an embodiment does not imply that the referenced embodiment is mutually exclusive with another embodiment (e.g., an embodiment described before the referenced embodiment), unless expressly specified otherwise.

The terms "including,” "comprising" and variations thereof mean "including but not limited to,” unless expressly specified otherwise.

The terms "a,” "an" and "the" mean "one or more,” unless expressly specified otherwise.

The term "plurality" means "two or more,” unless expressly specified otherwise.

The term "herein" means "in the present application, including anything which may be incorporated by reference,” unless expressly specified otherwise.

The term "whereby" is used herein only to precede a clause or other set of words that express only the intended result, objective or consequence of something that is previously and explicitly recited. Thus, when the term "whereby" is used in a claim, the clause or other words that the term "whereby" modifies do not establish specific further limitations of the claim or otherwise restricts the meaning or scope of the claim.

The term "e.g." and like terms mean "for example,” and thus do not limit the terms or phrases they explain.

The term "i.e." and like terms mean "that is,” and thus limit the terms or phrases they explain.

Neither the Title nor the Abstract is to be taken as limiting in any way as the scope of the disclosed invention(s). The title of the present application and headings of sections provided in the present application are for convenience only, and are not to be taken as limiting the disclosure in any way.

Numerous embodiments are described in the present application, and are presented for illustrative purposes only. The described embodiments are not, and are not intended to be, limiting in any sense. The presently disclosed invention(s) are widely applicable to numerous embodiments, as is readily apparent from the disclosure. One of ordinary skill in the art will recognize that the disclosed invention(s) may be practiced with various modifications and alterations, such as structural and logical modifications. Although particular features of the disclosed invention(s) may be described with reference to one or more particular embodiments and/or drawings, it should be understood that such features are not limited to usage in the one or more particular embodiments or drawings with reference to which they are described, unless expressly specified otherwise.

With all this in mind, the present invention is directed to a method and a system for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment.

It will be appreciated that the task may be of various types. In fact, it will be appreciated that a task corresponds to a set of instructions that, during their execution, will consume a given amount of resources (e.g. computing resources, memory resources, storage resources, etc.) or physical capacities (sensors, mobility, etc.).

For instance and in a non-limiting example, in a Web server, a task may be comprised of a set of instructions to receive and manage the requests of a web browser aiming to access a web page.

In the case where an aerial picture has to be taken, a task may comprise a set of instructions to allow an Unmanned Aerial Vehicle (UAV) controlled by a Robot Operating System (ROS) to take and store a picture from a specific point with the desired angle, zoom level, resolution, etc.

Now referring to Fig. 1 , there is shown an embodiment of a system for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment.

The system 10 comprises a plurality of heterogeneous host machines and a distributed orchestrator 12. More precisely and in this specific environment, the plurality of heterogeneous host machines comprises a first heterogeneous host machine 14, a second heterogeneous host machine 16 and a third heterogeneous host machine 18. It will be appreciated by the skilled addressee that any number of heterogeneous host machines may be used.

It will be further appreciated that the plurality of heterogeneous host machines are interconnected with the distributed orchestrator 12 via a data network 20. While it is shown a single data network in Fig. 1 , it will be appreciated that the interconnection may be performed via a plurality of data networks, each operating using a different protocol. For instance the first heterogeneous host machine 14 may be connected to the data network 20 via a first given data network while the second heterogeneous host machine 16 is connected to the first heterogeneous host machine 14 via a second given data network and the third heterogeneous host machine 16 is connected to the first heterogeneous host machine 14 using a third given data network. It will be appreciated by the skilled addressee that in this embodiment, the second heterogeneous host machine 16 and the third heterogeneous host machine 18 are not directly connected to the distributed orchestrator 12.

It will be appreciated that each host machine is a machine running its own Operating System (OS), e.g., Linux Ubuntu 16.04. It will be appreciated that each host machine is equipped with at least one corresponding processing resource and is characterized by corresponding physical capacities.

The at least one corresponding processing resource may be of various types.

For instance and in one embodiment, the processing resource is a central processing power which can be characterized by a number and a type of Central Processing Unit (CPU).

In another embodiment, the processing resource is a graphics processing power which can be characterized by a number and a type of Graphics Processing Unit (GPU).

In another embodiment, the processing resource is a memory space which is a Random Access Memory (RAM) and which can be characterized by a given size defined in Mbytes (MBs).

In another embodiment, the processing resource is a slow speed memory space which is of the type of the one offered by low-speed Hard Disk Drives (HDDs) and which can be characterized by a size defined in Mbytes (MBs).

In another embodiment, the processing resource is a high speed storage which is of the type of storage space offered by high-speed Solid-State Disks (SSDs) and which can be characterized by a size defined in Mbytes (MBs). In another embodiment, the processing resource is a networking resource which can be characterized by a number of network interfaces, a bandwidth offered per network interface, and a type of network interfaces.

Moreover, it will be appreciated that the physical capabilities may comprise various sensors, such as for instance RGB camera sensors, infrared camera sensors, temperature sensors.

For instance and in accordance with an embodiment, the physical capability comprises an aerial mobility characterized by a maximum speed, a maximum altitude, etc.

For instance and in accordance with an embodiment, the physical capability comprises a ground mobility characterized by a maximum speed, a steering angle, etc.

For instance and in accordance with an embodiment, the physical capability comprises a physical transportation system characterized by a maximum payload weight, etc.

For instance and in accordance with an embodiment, the physical capability comprises an Internet connectivity.

The skilled addressee will appreciate that the physical capability may be comprised of various other elements known to the skilled addressee.

It will be appreciated that the heterogeneous host machines may therefore comprise a set of host machines having different characteristics in terms of processing resources and physical capacities.

For instance and in accordance with one embodiment, a first heterogeneous host machine may be comprised of a One Onion Omega 2+ running Linux OpenWrt and comprised of a 1 CPU-core running at 580 MHz, 128MB or RAM, 32 MB of high- speed storage space, 1 mt7628 Wi-Fi interface split into two virtual Wi-Fi interfaces (one access point and one station).

Still in this embodiment, a second heterogeneous host machine may be comprised of a desktop server running Windows 10 and comprising an Intel® Core™ i7-7700T CPU with four 2.9 GHz cores, one Intel® HD Graphics 630, 8 GB of RAM, 1 TB of low-speed storage space, 1 Ethernet 100 Mbps interface, 1 RTL8814au Wi-Fi interface in station mode.

Still in this embodiment, a third heterogeneous host machine may be comprised of a UAV controlled by an NVIDIA TX2 running Ubuntu 16.04 for Tegra architectures and comprised of 6 CPU cores from a HMP Dual Denver 2/2 MB L2 + Quad ARM® A57/2 MB L2, one Nvidia Pascal GPU with 256 cores, 8 GB of RAM, 32 GB of hgh-speed storage space, 1 Gbps Ethernet interface, one 8021 1.ac Wi-Fi interface in station mode.

The skilled addressee will appreciate that various alternative embodiments may be provided for the heterogeneous host machines.

It will be appreciated that each host machine is running a telecommunication application for enabling the host machine to be part of a telecommunication network with at least one other heterogeneous host machine. In one embodiment, the telecommunication network comprises a virtual ad hoc mobile telecommunication network.

In one embodiment, the telecommunication application comprises a software module running on each physical host machine to enable inter-host communication even through multi-hop routing paths.

For instance and in the embodiment of a set of four host machines such as for instance three Raspberry Pi 3 Model B+ and one Onion Omega 2+, the four devices are connected over Wi-Fi through a hot-spot created by the mt7628 Wi-Fi embedded interface of the Onion Omega 2+ (the three RPI Wi-Fi interfaces are connected in station mode to the hot spot). The Onion Omega 2+ manages a WLAN with IP address 192.168.3.0/24, by keeping for itself the IP address 192.168.3.1 and assigning other three distinct IP addresses of the same network to the three RPIs. In this case, the telecommunication module on the Onion Omega 2+ is made by the TCP/IP stack and all related networking services of the OS combined to the Wi-Fi drivers managing the Wi-Fi interface in hot-spot mode, as well as the physical interface itself. On the three Raspberry Pi, the only difference consists in the Wi-Fi drivers used to control with network interface in station mode.

In another embodiment, the four devices are connected over multiple network interfaces. It will be appreciated that the embedded interfaces may be accompanied by other USB network interfaces. A network middleware running in the user space is run on each device to connect all of them on the same multi-hop network by exploiting all the network interfaces available. The telecommunication application of each host machine is now integrated with the network middleware and the other drivers necessary to run the additional external network interfaces.

In another embodiment, the four devices are equipped with a 5G network interface that enable all of them to keep constant connectivity with a server placed in the cloud acting as a bridge between the four devices. In such case, the telecommunication application on each node is made by the TCP/IP stack and all related networking services of the OS combined to the drivers of the 5G interface, as well as the physical interface itself. The telecommunication application includes also the software running in the cloud on the bridge server.

It will be appreciated that each host machine further comprises a virtualization engine. The virtualization engine is used for executing a received virtualized element using the corresponding processing resources of the given host machine. It will be appreciated that a virtualization engine is a software module that is running on the top of host machines with OS and physical hardware supporting virtualization and which enables to instantiate, run, manage and stop multiple virtualized elements on the same host machine. It will be appreciated by the skilled addressee that the virtualization engine takes care of distributing the processing resources and capacities among all the virtualized elements currently running on the same host machine. It will be appreciated that various virtualization engines may be used such as for instance Docker Engine, Kubernets Engine, Hyper-V, VMWare vSphere, KVM, etc.

It will be appreciated that a virtualized element may be defined as a dedicated software environment instantiated on a host machine, capable, through the process of virtualization, of emulating functions, software modules and hardware not supported by the underlying host machine. For instance it will be appreciated that a virtualized element enables to run for instance a Linux-based application on top of a Windows host machine. It will be further appreciated that a virtualized element runs in an isolated manner with respect to other virtualized elements placed on the same host machines. Most popular examples of virtualized elements include Virtual Containers (VCs) and Virtual Machines (VMs).

It will be further appreciated that each host machine further comprises a geolocation module. The geolocation module is used for providing at least an indication of a present position of the corresponding host machine.

The geolocation module may comprise at least one of a software module and a physical interface and is used for at least estimating a current position of a host machine. The skilled addressee will appreciate that the geolocation module may be of various types. In one embodiment, the geolocation module comprises a GPS based system comprising a GPS interface which can estimate its position by trilateration with respect to geostationary satellites, as known to the skilled addressee.

In another embodiment, the geolocation module is implemented using a Ultra- Wide Band (UWB) system. In fact, it will be appreciated that in such embodiment three host machines equipped with a UWB interface, such as for instance DWM1001 from DecaWave, may compute a relative position of a fourth host machine always equipped with a UWB interface by trilateration as known to the skilled addressee. It will be appreciated that the distance between each pair of UWB-powered host machines may be computed by estimating a flight time of each transmitted communication probe. If one host machine is chosen as origin of a reference system of coordinates, all the relative positioning measures done by each subset of four host machines can be converted according to it. It will be appreciated that such geolocation module is collaborative and therefore requires all the host machines to be on the same telecommunication network to operate.

In another embodiment, the geolocation module may be implemented using a Wi-Fi range-based system similar to UWB system. In such embodiment, host machines are equipped with a Wi-Fi interface capable of returning the Received Signal Strength Indicator (RSSI) from other host machines in range. The relative positions are computed by converting the Received Signal Strength Indicator (RSSI) into estimated distance values, e.g., by fitting a path loss function. Trilateration processes are thus based on these distance values.

The skilled addressee will appreciate that the geolocation module may be provided according to various alternative embodiments.

Still referring to Fig. 1 , it will be appreciated that the system 10 further comprises a distributed orchestrator 12. It will be appreciated that the distributed system orchestrator 12 is used for managing an execution of a plurality of tasks using at least one of the plurality of heterogeneous host machines. The plurality of tasks is comprised of a corresponding plurality of virtualized elements.

It will be appreciated that the distributed system orchestrator 12 comprises a telecommunication application for enabling the distributed system orchestrator 12 to be part of the telecommunication network comprising at least one heterogeneous host machine of the plurality of heterogeneous host machines to thereby be operationally connected with the at least one heterogeneous host machine.

The distributed system orchestrator 12 further comprises a task assignment module. The task assignment module is used for assigning each virtualized element of the plurality of virtualized elements to a selected host machine located on the telecommunication network. It will be further appreciated that the assigning of the virtualized element is performed according to a given multi-period workload placement problem.

The given multi-period workload placement is determined by the distributed system orchestrator 12 using at least the indication of a present position of each available host machine and an indication of corresponding resource availability in each of at least one host machine of the plurality of host machines and in accordance with at least one given criterion. In one embodiment, the multi-period workload placement problem is determined by the distributed system orchestrator 12 using information related to host machines joining or leaving the telecommunication network.

It will be further appreciated that in one embodiment, the given multi-period workload placement problem is further determined using at least one telecommunication network property. The at least one telecommunication network property problem may be selected from a group consisting of a latency for transferring a first given virtualized element to a given host machine, a latency for migrating a second given virtualized element from a first given host machine to a second given host machine, and a network topology.

In fact, it will be appreciated that the distributed system orchestrator 12 comprises a software module running on each host machine to manage, in a collaborative manner, virtualization and all related processes (e.g., reservation of routing paths) within a set of multiple host machines. Differently from traditional centralized orchestration solutions, e.g., VMWare vCenter, Docker Swarm, Openstack Heat, etc., the distributed system orchestrator 12 keeps virtualization decision locally, by empowering different subsets of host machines with the capability of exchanging local system information, and later take real time optimal task assignment decision. The goal of the distributed system orchestrator 12 is to find a set of task assignment decisions that optimizes at least one given criterion. The distributed nature of the distributed system orchestrator 12 is crucial to manage large set of host machines with rapidly varying physical configurations related, for instance, to host machine mobility and temporary availability.

As mentioned above, it will be appreciated that the distributed system orchestrator 12 comprises a task assignment module.

The task assignment module consists of a multi-objective placement problem defined by a Mixed-Integer-Non-Linear-Programming (MINP) formulation. It will be appreciated that in this case the workload placement problem is meant to handle workload with a multi-period nature (i.e. some tasks may not be executable simultaneously). For this reason, it is referred to as multi-period workload placement problem.

Considering a graph made by nodes and arcs representing a set of host machines (nodes) and their physical communication links (arcs), a set of workloads (applications) already placed (mapped) on the top of the set of host machines, each one represented by two dedicated graphs: wherein the first made by nodes and arcs representing a set of virtualized elements (nodes) and their communication bandwidth requirements way they are connected and wherein the second made by nodes and arcs representing a set of virtualized elements (nodes) and their parallelization/serialization constraints - already placed (mapped) on the top of the set of host machines.

Considering also a second set of workloads, represented by the same two graphs just described, demanding to be placed (mapped) on the top of the set of host machines,

It will be appreciated that a multi-period workload placement problem is a mathematical representation of the orchestration process that defines how the placement decisions, e.g. , which workload node to virtualize on each host machine, which routing path to assign between different pairs of workload nodes, which workload nodes to put in the waiting queue, which workload already placed on active host machines nodes to migrate to different host machines, where to move a host machine, which host machine to assign to dedicated communication roles, etc.

It will be appreciated that the multi-period workload placement problem defines also which combinations of placement decisions are considered feasible with respect to the system parameters, e.g. , the maximum resource of a host machine or the maximum bandwidth of a network link.

In one embodiment, the multi-period workload placement problem is amended in response to a given event.

It will be appreciated that the given event comprises a change in resources available in one embodiment.

It will be further appreciated that that in one embodiment the amendment of the multi-period workload placement problem comprises transferring a virtualized element from a first given host machine directly to a second given host machine. It will be appreciated that in one embodiment, the telecommunication application of the distributed system orchestrator 12 reserves dedicated suitable routing paths according to the multi-period workload placement problem.

It will be appreciated that each virtualized element has requirements related to the above set of processing resources and capacities. In the context of the placement of a virtualized element on the top of a host machine, the required amount of processing resources is assigned from the host machine to the corresponding virtualized element. The available processing resources are computed as the difference between the total amount of processing resources offered by a host machine in idle state and those currently assigned to the virtualized elements already mapped onto it.

It will be appreciated that the multi-period workload placement problem therefore defines a multi-objective function that the distributed orchestrator is supposed to optimize when computing a multi-period-placement (task-assignment) solution (configuration). It will be appreciated that each objective component is also referred to as a criterion. It will be appreciated that the criterion may be of various types. In one embodiment the at least one criterion is selected from a group consisting of a minimization of host machine utilization costs, a minimization of a number of migrations, a minimization of energy consumption, a minimization of refused workloads, a minimization of host machine physical movements, a throughput of at least one given host machine, a spectrum sharing behavior between at least two pairs of host machines, an interference between at least two pairs of host machines, etc.

It will be appreciated that the given multi-period workload placement problem is further determined using at least one telecommunication network property.

It will be further appreciated that the at least one telecommunication network property problem comprises at least one of a latency for transferring a first given virtualized element to a given host machine; a latency for migrating a second given virtualized element from a first given host machine to a second given host machine; and a network topology.

It will be appreciated that a given event is an event that triggers the need of re-computing a new placement solution with the distributed orchestration. These events include an arrival of a new workload, a resource scarcity observed on a host machine due to unexpected virtualized element resource consumption behavior, a triggering of under-utilization thresholds, a departure of a host machine, an arrival of a new host machine, a conclusion of a task that was blocking the placement of another task of the same workload (application).

It will be appreciated that in one embodiment, the geolocation module further provides an indication of a possible future position of the corresponding host machine. In such case, the given multi-period workload placement problem is further determined using the indication of a possible future position of the corresponding host machine.

It will be appreciated that in one embodiment each heterogeneous host machine is assigned an indication of a corresponding reputation. In such case, the given multi-period workload placement problem is further determined using the indication of a corresponding reputation.

It will be further appreciated that each heterogeneous host machine comprises an energy module for providing an indication of a corresponding level of energy available. In such case, the given multi-period workload placement problem is further determined using the indication of a corresponding level of energy available.

It will be appreciated that there is also disclosed a method for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment. According to processing step 100, a plurality of heterogeneous host machines is provided. Each given heterogeneous host machine has corresponding processing resources. Each given heterogeneous host machine comprises a telecommunication application for enabling the given heterogeneous host machine to be part of a telecommunication network with at least one other heterogeneous host machine. Each given heterogeneous host machine further comprises a virtualization engine for executing a received virtualized element using the corresponding processing resources. Each given heterogeneous host machine comprises a geolocation module for providing at least an indication of a present position of the given heterogeneous host machine.

According to processing step 102, a distributed system orchestrator is provided for managing an execution of a plurality of tasks using at least one of the plurality of heterogeneous host machines with a corresponding telecommunication application for enabling the distributed system orchestrator to be part of the telecommunication network comprising at least one available heterogeneous host machine of the plurality of heterogeneous host machines and with a task assignment module for assigning each virtualized element of the plurality of virtualized elements to a selected heterogeneous host machine located on the telecommunication network.

According to processing step 104, a plurality of tasks to execute is received using the distributed system orchestrator. Each task comprises a corresponding plurality of virtualized elements.

According to processing step 106, an indication of a present location of each available heterogeneous host machine is obtained using the distributed system orchestrator. According to processing step 108, an indication of a resource availability for each available heterogeneous host machine is obtained using the distributed system orchestrator.

According to processing step 1 10, a multi-period workload placement problem is determined by the distributed system orchestrator using the received indication of a present location of each available heterogeneous host machine and the indication of a resource availability of each available heterogeneous host machine.

According to processing step 1 12, for each task of the plurality of tasks, each corresponding virtualized element of the plurality of corresponding virtualized elements is assigned to a corresponding host machine using the determined multi period workload placement problem.

In one or more embodiments, the method further comprises executing each of the assigned virtualized elements using the corresponding heterogeneous host machine.

In one or more embodiments of the method, the telecommunication network comprises a virtual ad hoc mobile telecommunication network.

In one or more embodiments, the method further comprises amending the multi-period workload placement problem in response to a given event. In one or more embodiments, the given event comprises a change in resources available.

In one or more embodiments of the method, the amending of the multi-period workload placement problem comprises transferring a given virtualized element from a first given heterogeneous host machine to a second given heterogeneous host machine. In one or more embodiments of the method, the determining of the multi period workload placement problem is further performed using at least one property of the telecommunication network.

In one or more embodiments of the method, the method further comprises receiving, from each of the plurality of heterogeneous host machines, an indication of a possible future location; further wherein the determining of the multi-period workload placement problem is further performed using the received indications of a possible future location.

In one or more embodiments of the method, the method further comprises assigning, for each of the plurality of heterogeneous host machines, an indication of a corresponding reputation; further wherein the determining of the multi-period workload placement problem is further performed using the plurality of indications of a corresponding reputation.

In one or more embodiments of the method, the method further comprises obtaining an indication of a corresponding level of energy available in each of the plurality of heterogeneous host machines; further wherein the determining of the multi-period workload placement problem is further performed using the obtained indications of a corresponding level of energy available.

It will be appreciated that the system and the method disclosed above are of great advantage for various reasons.

A first reason is that they enable to use a plurality of heterogeneous host machines to execute a plurality of tasks in a dynamic environment.

Another reason is that they enable the use of heterogeneous host machines. Although the above description relates to a specific preferred embodiment as presently contemplated by the inventor, it will be understood that the invention in its broad aspect includes functional equivalents of the elements described herein.

Clause 1. A system for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment, the system comprising: a plurality of heterogeneous host machines, each heterogeneous host machine being characterized by corresponding processing resources, each heterogeneous host machine comprising: a telecommunication application for enabling the heterogeneous host machine to be part of a telecommunication network with at least one other heterogeneous host machine; a virtualization engine for executing a received virtualized element using the corresponding processing resources of the heterogeneous host machine; a geolocation module for providing at least an indication of a present position of the corresponding heterogeneous host machine; a distributed system orchestrator for managing an execution of a plurality of tasks using at least one of the plurality of heterogeneous host machines, wherein the plurality of tasks is comprised of a corresponding plurality of virtualized elements, the distributed system orchestrator comprising: a telecommunication application for enabling the distributed system orchestrator to be part of the telecommunication network comprising at least one heterogeneous host machine of the plurality of heterogeneous host machines; a task assignment module for assigning each virtualized element of the plurality of virtualized elements to a selected heterogeneous host machine located on the telecommunication network, wherein the assigning of the virtualized element is performed according to a given multi-period workload placement problem; wherein the given multi-period workload placement problem is determined by the distributed system orchestrator using at least the indication of a present position of each available heterogeneous host machine and an indication of corresponding resource availability in at least one heterogeneous host machine of the plurality of heterogeneous host machines and in accordance with at least one given criterion.

Clause 2. The system as claimed in clause 1 , wherein the multi-period workload placement problem is determined by the distributed system orchestrator using information related to heterogeneous host machines joining or leaving the telecommunication network.

Clause 3. The system as claimed in any one of clauses 1 to 2, wherein the telecommunication network comprises a virtual ad hoc mobile telecommunication network.

Clause 4. The system as claimed in any one of clauses 1 to 3, wherein the multi-period workload placement problem is amended in response to a given event.

Clause 5. The system as claimed in clause 4, wherein the given event comprises a change in resources available.

Clause 6. The system as claimed in clause 4, wherein the amendment of the multi-period workload placement problem comprises transferring a virtualized element from a first given heterogeneous host machine directly to a second given heterogeneous host machine.

Clause 7. The system as claimed in any one of clauses 1 to 6, wherein the heterogeneous host machines are wireless host machines, further wherein the at least one given criterion is selected from a group consisting of: a minimization of host machine utilization costs; a minimization of a number of migrations; a minimization of energy consumption; a minimization of refused workloads; a minimization of host machine physical movements; a throughput of at least one given host machine; a spectrum sharing behavior between at least two pairs of host machines;

an interference between at least two pairs of host machines.

Clause 8. The system as claimed in any one of clauses 1 to 7, wherein the telecommunication application of the distributed system orchestrator reserves dedicated suitable routing paths according to the multi-period workload placement problem.

Clause 9. The system as claimed in any one of clauses 1 to 8, wherein the given multi-period workload placement problem is further determined using at least one telecommunication network property.

Clause 10. The system as claimed in clause 9, wherein the at least one telecommunication network property problem comprises at least one of: a latency for transferring a first given virtualized element to a given heterogeneous host machine; a latency for migrating a second given virtualized element from a first given heterogeneous host machine to a second given heterogeneous host machine; and a network topology. Clause 1 1. The system as claimed in any one of clauses 1 to 10, wherein the geolocation module further provides an indication of a possible future position of the corresponding heterogeneous host machine; further wherein the given multi period workload placement problem is further determined using the indication of a possible future position of the corresponding heterogeneous host machine.

Clause 12. The system as claimed in any one of clauses 1 to 1 1 , wherein each heterogeneous host machine is being assigned an indication of a corresponding reputation; further wherein the given multi-period workload placement problem is further determined using the indication of a corresponding reputation.

Clause 13. The system as claimed in any one of clauses 1 to 12, wherein each heterogeneous host machine comprises an energy module for providing an indication of a corresponding level of energy available; further wherein the given multi-period workload placement problem is further determined using the indication of a corresponding level of energy available.

Clause 14. A method for enabling an execution of a plurality of tasks in a heterogeneous dynamic environment, the method comprising: providing a plurality of heterogeneous host machines, each given heterogeneous host machine having corresponding processing resources, each given heterogeneous host machine comprising: a telecommunication application for enabling the given heterogeneous host machine to be part of a telecommunication network with at least one other heterogeneous host machine, a virtualization engine for executing a received virtualized element using the corresponding processing resources, and a geolocation module for providing at least an indication of a present position of the given heterogeneous host machine; providing a distributed system orchestrator for managing an execution of a plurality of tasks using at least one of the plurality of heterogeneous host machines with a corresponding telecommunication application for enabling the distributed system orchestrator to be part of the telecommunication network comprising at least one available heterogeneous host machine of the plurality of heterogeneous host machines and with a task assignment module for assigning each virtualized element of the plurality of virtualized elements to a selected heterogeneous host machine located on the telecommunication network; receiving, using the distributed system orchestrator, a plurality of tasks to execute, each task comprising a corresponding plurality of virtualized elements; obtaining, using the distributed system orchestrator, an indication of a present location of each available heterogeneous host machine; obtaining, using the distributed system orchestrator, an indication of a resource availability for each available heterogeneous host machine; determining, using the distributed system orchestrator, a multi-period workload placement problem using the received indication of a present location of each available heterogeneous host machine and the indication of a resource availability of each available heterogeneous host machine; and for each task of the plurality of tasks assigning each corresponding virtualized element of the plurality of corresponding virtualized elements to a corresponding host machine using the determined multi-period workload placement problem. Clause 15. The method as claimed in clause 14, further comprising executing each of the assigned virtualized elements using the corresponding heterogeneous host machine.

Clause 16. The method as claimed in any one of clauses 14 to 15, wherein the telecommunication network comprises a virtual ad hoc mobile telecommunication network.

Clause 17. The method as claimed in any one of clauses 14 to 16, further comprising amending the multi-period workload placement problem in response to a given event.

Clause 18. The method as claimed in clause 17, wherein the given event comprises a change in resources available.

Clause 19. The method as claimed in any one of clauses 14 to 17, wherein the amending of the multi-period workload placement problem comprises transferring a given virtualized element from a first given heterogeneous host machine to a second given heterogeneous host machine.

Clause 20. The method as claimed in any one of clauses 14 to 19, wherein the determining of the multi-period workload placement problem is further performed using at least one property of the telecommunication network.

Clause 21. The method as claimed in any one of clauses 14 to 20, further comprising receiving, from each of the plurality of heterogeneous host machines, an indication of a possible future location; further wherein the determining of the multi period workload placement problem is further performed using the received indications of a possible future location.

Clause 22. The method as claimed in any one of clauses 14 to 21 , further comprising assigning, for each of the plurality of heterogeneous host machines, an indication of a corresponding reputation; further wherein the determining of the multi period workload placement problem is further performed using the plurality of indications of a corresponding reputation.

Clause 23. The method as claimed in any one of clauses 14 to 22, further comprising obtaining an indication of a corresponding level of energy available in each of the plurality of heterogeneous host machines; further wherein the determining of the multi-period workload placement problem is further performed using the obtained indications of a corresponding level of energy available.

Technical implementation of enabling an execution of a plurarity of tasks in a heterogeneous dynamic environment through a distributed orchestration system

List of Acronyms

1 Implementing a distributed multi-period orchestrator

A practical implementation of a distributed multi-period orchestration system enabling the execution of a plurality of tasks on top of a heterogeneous dynamic virtualization ready physical infrastructure is presented.

The plurality of tasks:

• Is resource aware: each task may require computing/storage resources and/or physical capacities (e.g., specific types of sensors, specific types of physical mechanisms, etc.).

• Is network aware: each task may require a certain amount of network bandwidth to exchange data with other tasks.

• Is mobile: the tasks are tied to specific operation positions.

• Is localized: the tasks can be assigned to hosting nodes placed in specific loca tions.

• Is multi-period: the tasks are characterized by inter-tasks precedence, simultan eity, serialization and parallelization relationships that regulate when each single task can be actually placed and executed.

• Requires guaranteed QoS: strict guarantees in terms of hosting machine avail ability and network performance.

• Requires best effort QoS: no guarantees in terms of hosting machine availability and network performance.

The heterogeneous dynamic virtualization-ready physical infrastructure:

• Is opportunistic: Some hosting machines may appear and depart in both a pre planned and an uncontrolled manner. A reputation value may be assigned to each hosting machine to evaluate its reliability and trustiness.

• Is mobile: Some hosting machines may be capable of moving toward a given position to satisfy the requirements of a hosted virtualized element. Some host ing machines may move in an autonomous manner without direct control of the orchestration system.

• Is battery alimented: Some hosting machines may have limited battery life and may need periodical battery recharging. • Is wireless, wired or both: Some hosting machines may be connected through wired communication links— e.g., an Ethernet connection— while other host ing machines may exploit different types of wireless communication links, from Device-to-Device (D2D) ad-hoc wireless links to traditional Wi-Fi managed links and 3G/4G/5G connections.

• Is Internet ready: if at least one hosting machine has global connectivity, it seam lessly acts as gateway by all the other hosting machines requiring global con nectivity. The availability of global connectivity is not mandatory to operate on the top of the virtualization ready physical infrastructure.

• Is virtualization ready: hosting machines offer computing/storage resources, as well as physical capacities (e.g., specific types of sensors, specific types of phys ical mechanisms, etc.). Note that a hosting machine can manage whole clusters of sensors for which it acts as gateway/sink node over a Wireless Sensor Net work (WSN); these sensor clusters represent specific physical capacities and resources that can be assigned to hosted virtualized elements.

• Can be geographically widespread: geographical proximity is not necessary to consider two hosting machines as neighbors. Any pairs of hosting machines able to exchange data (e.g., through a TCP socket) can be considered neighbors.

The practical implementation of a distributed multi-period orchestration system en abling the execution of a plurality of tasks on top of a heterogeneous dynamic virtualization-ready physical infrastructure relies on the following list of components:

1. The multi-period workload generation module to allow any user or process to translate a general application comprising multiple tasks into a proper multi period representation compatible with the new proposed distributed multi-period orchestrator for multi-period workload placement. This component is responsible for generating all the parameters characterizing a given set of heterogeneous tasks. The distributed multiperiod orchestrator can actually work without this auxiliary component, which represents the interface between the orchestrator and any entity aiming to run a set of tasks while improving the virtualization per formances observed during system operations network-aware path planning 2. The distributed multi-period orchestrator is responsible for optimizing how a given set of tasks is placed (mapped) over time, on top of the set of hosting machines representing the virtualization ready physical infrastructure. One instance of the distributed multi-period orchestrator is run on each hosting machine. Two are the key elements of each distributed multi-period orchestrator instance:

• A mathematical formulation of the multi-period workload placement prob lem.

• A collaborative multi-period placement algorithm to solve, in real-time, the multi-period workload placement problem.

3. A Distributed Advanced Storage Service (DASS) is run on each hosting machine to provide data sharing/replication services to all the other modules hosted by the same hosting machine. For instance, the collaborative multi-period placement al gorithm exploits DASS to enable the coordination and the communication among multiple hosting machines.

4. The energy manager is responsible, on each hosting machine, for managing energy-consumption related parameters and energy management processes.

5. The network-aware path manager responsible, on each hosting machine, for computing traveling paths that will guarantee a stable network configuration and a stable network performance whenever a hosting machines is required to move toward the position demanded by a hosted task (virtualized element). The distrib uted multiperiod orchestrator can work without this auxiliary component. How ever, network-aware path planning is helpful to improve overall system perform ances during operations.

6. The geo-location module is responsible, on each hosting machine, for retriev ing/estimating/managing all geo-location related parameters.

7. The reputation estimator is responsible, on each hosting machine, for retriev ing/estimating/managing all reputation related parameters.

8. The access manager is responsible, on each hosting machine, for accepting (server side) new hosting machines aiming to become members of the virtualiz ation ready physical infrastructure, as well as for gaining (client side) access to the virtualization ready physical infrastructure just discovered.

9. The virtualization engine is responsible, on each hosting machine, for instanti ating, monitoring, running, stopping, migrating, isolating the hosted application nodes.

10. The telecommunication application is responsible, on each hosting machine, for guaranteeing connectivity with all the other architecture members. In our example, the role of telecommunication application is assigned to the Hetero geneous Embedded Ad-Hoc Virtual Emergency Network (HEAVEN) middleware capable of establishing and managing an ad-hoc virtual network on the top of Wi-Fi Managed, Wi-Fi IBSS, UWB, Bluetooth, xBee 900 Mhz interfaces.

Mathematical notation and definitions

Table 2: Presentation of all the mathematical notation.

It will be appreciated that in the text, the operator un derline , e.g., ? is used to define the pre-optimization value of the corresponding variable.

Resource ID Unit of measurement

CPU Number of vCPUs, non negative, real

GPU Number of GPUs, non negative, integer

RAM GB, non negative, real

HDD GB, non negative, real

SSD GB, non negative, real

RGB camera Number of available RGB cameras

Infrared camera Number of infrared cameras available at a time

Temp sensor Number of temperature sensors available at a time

Table 3: Unit of measurements for each resource/capacity of set R.

3 The multi-period workload generation

A collaborative application can be seen as a plurality of tasks (collection of workloads, application elements, application nodes, etc.) that may mutually interfere, interact, col laborate with each other. A user or a process aiming to run an application on top of a virtualization ready physical infrastructure powered by the distributed multi-period or- chestrator must translate the given plurality of tasks into two virtual graphs (V _z , A _z ) and (V _z , U _Z ), where each task is mapped to a specific virtualized element (mul- tiple tasks can be packed within the same virtualized element). During this translation process, the relevant application parameters are configured, e.g., flavor of each virtu alized element (type of Docker container, type of Ubuntu virtual machine, etc.), CPU and RAM requirements and so on. This operation can be naturally done through a User Interface (Ul) of:

• a web-based application,

• a mobile application,

• any dedicated software running on a Windows, MAC or Linux computer.

The multi-period workload generation component connected to the Ul must have a network connection with at least one of the hosting machine of the virtualization ready physical infrastructure; if at least one hosting machine of the virtualization ready phys ical infrastructure has global internet connectivity, the multi-period workload generation component can be run somewhere in the cloud, otherwise it must run on any device locally connected to at least one hosting machine of the virtualization ready physical infrastructure, as well as directly on one of the hosting machines. In the latter case, the interaction between the user and the distributed multi-period orchestrator is enabled by a communication link provided by the telecommunication application described in Section 12.

In principle, any collaborative application (plurality of tasks) can be translated into the corresponding pair of (V _z , U _z ) graphs.

Examples of such collaborative applications include:

• Collaborative home automation applications.

• Autonomous UAV-powered 3D mapping missions.

• Autonomous UAV-powered surveillance missions.

• Collaborative Camera-powered surveillance applications.

• Autonomous road-light management applications.

The multi-period workload generation process allows the distributed multi-period or chestrator to manage a highly heterogeneous set of applications (plurality of tasks). In particular, let us put the emphasis on the heterogeneity in terms of mobility require ments:

• Static application (plurality of tasks): all the virtualized elements of graph G^ (V _z , A _z ) can be hosted on static/fixed hosting machines.

• Hybrid application (plurality of tasks): at least one virtualized element of graph G^ (V _z , A _z ) requires to be hosted on mobile (capable of changing position) host- ing machine.

• Mobile application (plurality of tasks): all the virtualized elements of graph

( V _z , A _z ) must be hosted be mobile (capable of changing position) hosting machines.

3.1 Virtualized element characterization

As already mentioned, during the multi-period workload generation process, each vir tualized element that will represent one or more application tasks from the original plur ality of tasks must be characterized by the corresponding set of parameters. These parameters will later allow the distributed multi-period orchestror to optimally place each virtualized element on top of the virtualization ready physical infrastructure. Here follows the detailed list of these parameters:

• V _{z \} Set of virtualized elements (application nodes); note that when designing the application graph the rule of thumbs is to aggregate as many possible applica tions functions (tasks from the plurality of tasks) into a single virtualized element.

• p _{lkr \} Binary parameter, equal to 1 if virtualized element (application node) i is compatible with configuration k e K ^r for resource r e R for instance, a virtual ized element may be compatible with a hosting machine of configuration k e K ^r in terms of CPUs (r e R u {CPU}) offering single cores with an operating fre quency of at least 1.4 GHz.

• f _i ^z _{t \} Non-negative real parameter, amount of resource r e R demanded by virtu alized element i e 1 of application z e Z for instance, being r e R u {RAM}, the virtualized element (application node) may ask for 512 MB of memory.

• <5 : Non-negative real parameter, minimum bandwidth to be allocated for the migration of virtualized element (application node) i e V _z of application z e Z and satisfy its maximum migration latency requirement, e.g., 100 mbps.

• <5 : Non-negative real parameter, minimum bandwidth to be allocated for the deployment of virtualized element (application node) i e V _z of application z e Z and satisfy its maximum deployment latency requirement, e.g., 100 mbps.

• M^ ^wn ·. Non negative real parameter, maximum down-time duration allowed by virtualized element (application node) i e 1 of application z e Z in case a migration is required.

• (Af ^OE , Af ^ow , Af ^ON , Af ^os ) \ 4-object tuple of non-negative real parameters (non-negative because we consider only the positive quadrant of the Cartesian space), representing the East, West, North, South boundaries of the rectangular DOA of virtualized element (application node) i of application z e Z.

• (A ^EOE , A ^EOW , A ^EON , A ^EOS ) ·. 4-object tuple of non-negative real parameters (non-negative because we consider only the positive quadrant of the Cartesian space), representing the East, West, North, South boundaries of the rectangular FOA of virtualized element (application node) i of application z e Z.

• xl . Binary parameter, equal to 1 if virtualized element (application node) i e V _z of application z e Z cannot be activated simultaneously with a second virtualized element (application node) j e V _z of the same application, when both elements are assigned to the same hosting machine.

• xl . binary parameter, equal to 1 if virtualized elements (application nodes) i, j e V _z : i F j of application z e Z have to be run simultaneously.

• Xif- binary parameters, equal to 1 if virtualized element (application node) i e V _z of application z e Z must be placed to allow the placement of a second virtualized element (application node) j e V _z .

• /¾f: Non negative real parameter, minimum reputation value demanded by virtu alized element (application node) i e V _z of application z e Z.

• z ^c ° ^mp \ Non-negative real parameter, amount of computing time explicitly reques ted by virtualized element (application node) j e V _z of application z e Z.

• Binary parameter equal to 1 if virtualized element (application node) i e V _z of application z e Z can accept to be placed on a hosting machine which may leave the virtualization ready physical infrastructure before the virtualized element itself has concluded its operation

• å? : Binary parameter equal to 1 if virtualized element (application node) i e V _z of application z e Z has to placed on the same hosting machine hosting a second virtualized element (application node) j e V _z \ {¾} of the same application.

• /¾: Binary parameter equal to 1 if virtualized element (application node) i e V _z of application z e must be activated at this round of placement, otherwise the application is considered refused (not placed).

• b _{z \} Non-negative real parameter, minimum number of virtualized elements (ap plication nodes) of application z e Z to be placed at this round of placement, otherwise the application is considered refused.

• V _z : Non-negative real parameter, penalty cost for refusing the placement of ap plication z e Z. This parameter represents the priority level of a given applica tion.

• b ^z \ Non-negative real parameter, penalty cost for migrating the virtualized ele ment (application node) i e V _z of application z e Z. This parameter represents the priority level of a virtualized element (application node).

• S _{z \} Set of types of virtualized elements (application nodes) used in application z e Z\ All the application nodes of the same type s e S _z can share the same set of host resources when placed on the same hosting machine.

• q _{s \} Binary parameter equal to 1 if virtualized element (application node) i e V _z of application z e Z can share the resources of other virtualized elements (application nodes) of the same application z e Z when they are of the same type.

• v _{s \} Binary parameter equal to 1 if virtualized element (application node) i e V _z of application z e Z is of type s e S _z .

• A _{z \} Set of traffic demands of application z e Z.

• <¾ : Non-negative real parameter, minimum bandwidth to be allocated to satisfy the communication requirements of traffic demand (i, j) e A _z of application z e Z, e.g., 10 mbps.

• D? : Non-negative real parameter. Maximum network latency accepted by traffic demand (i, j) e A _z of application z e Z.

It is worth pointing out that, besides configuring virtualized element parameters, the user may be also requested to:

• Select the desired reliability level P to allow the orchestrator to trigger the graph transformation described in Section 3.2. • Select the desired network reliability level L to demand that L routing paths are activated per traffic demand.

• Flag the option allowing to separate storage and computing components and trigger the graph transformation described in Section 3.3).

Furthermore, note that if a given application (multi-period workload) has just best- effort QoS requirements, it means that can be placed on any kind of hosting machines without accounting for their availability periods, as well as for the amount of bandwidth reserved between the multiple virtualized elements. In this case, it would be enough to create an application graph with an empty set A _z , and corresponding parameters E ^comp = 0 and y = 1. This virtualized elements can be thus placed on any nodes, also the busy ones or those whose movements are not under control.

3.2 Resilience Awareness

To minimize the negative effects of hardware failures, P copies of each virtualized elements are placed on different physical servers, and a certain amount of bandwidth is reserved between original and replicated virtual elements to support the data flow generated to keep the latter up to date.

This process can be naturally modeled through a transformation of the virtual graph G ^v ( V , A) similar to that illustrated in Section 3.3. As shown in Figure 4, for each virtualized element i e V _z of application v e V, P virtual nodes h V e {1, . . . , P} (with the same resource requirements y) are created and connected to i by two backup traffic demands (i, h ₃ ) and (/¾, i) e A _z .

Note that replicated virtualized elements are not supposed to consume any resource; however the proper amount of computing/storage resources and physical capacities (the same of the original element) has to be reserved to guarantee that the require- ments will be respected in case of failure of the original virtualized element.

3.3 Storage splitting transformation

If storage resources are allowed to be allocated on different hosting machines with respect to those serving the computing resources (see for instance Amazon Elastic Bock Store [1 ]), the application graph is modified as follows (see also Figure 5): • Each virtualized element i G V _z of application z <E Z is split among two new different virtualized elements j and h, with:

- j being a computing nodes with

* Parameters f _p forced to 0 Vr G R n {SSD,HDD} (no storage space required),

* F _p = F _it ^t G Rn {CPU, GPU, RAM}, i.e. , traditional computing, graph ical processing and RAM resources unvaried.

* P _jkr = P _kr ^k G iV ^r , Vr G R, i.e., all compatibility requirements unvar ied.

- h being a storage nodes with

* Parameters forced to 0 Vr G i? n {CPU, GPU, RAM} (no computing nor memory resources required),

* F _HT = y _it ^t e R n {HDD,SSD}, i.e. slow and high speed computing space resource requirements unvaried,

* Parameters p _jkr forced to 1 Vfc G AT ^r , Vr G R, i.e., all compatibility re quirements are ignored;

• An additional bidirectional traffic demand (j, h ) is added to the traffic demand set A _z of application z e Z to account for the network bandwidth 5 _j ^z _h required to guarantee the demanded data rate transfer for both read and write operations on the storage node.

3.4 Interaction with the other modules

Once a plurality of tasks belonging to the same application is fully translated into the corresponding pair of graphs representing a multi-period workload, the whole set of parameters that we just described is transferred to the distributed multi-period or chestration instance of at least one hosting machine. The same process is repeated whenever the user modifies the parameters of a multi-period workload already placed on top of the virtualization ready physical infrastructure.

During the life cycle of the application (multi-period workload), the hosting machine that originally received the placement request will keep updating the originating multi period workload generation module about the state of the virtualized elements, e.g., average performance, IDs of queued virtualized elements, position of involved hosting machines, etc.

The continuous flow of application-related information between these two modules allows to exploit the multi-period nature of the distributed orchestration system to gen erate new virtualized elements (application nodes) in real-time: this mechanism is driven by the real-time output of the virtualized elements already running. Section 3.5 discloses an example of how real-time virtualized element (workload) generation can be leveraged in the context of a 3D mapping application powered by UAVs.

3.5 An example: autonomous 3D mapping with UAVs

An autonomous 3D mapping mission can be characterized by the three-stage (multi period) work-flow represented in Figure 6:

1. Stage 1 : Photo collection.

2. Stage 2: Computation of optimal 3D reconstruction configuration.

3. Stage 3: Collaborative 3D reconstruction.

This 3-stage workload has to be further extended to generate the corresponding pair of virtual graphs G ^v (V _z , A _z ) and (V _z , U _z ), shown in Figure 7, ready to be managed by the distributed multi-period orchestrator. The various elements illustrated in Figure 7 are described below:

• Top graph G ^v (V _Z , A _Z ), bidirectional black arrows: standard traffic demands be longing to A _z .

• Top graph G ^v ( V _Z , A _Z ), bidirectional blue dotted arrows: storage traffic demands belonging to A _z .

• Top graph G ^v (V _z , A _z ) and bottom graph G ^T (V _Z , U _Z ) , red rectangles: special types of application node belonging to S _z .

• Bottom graph G ^T (V _z , U _z ), bidirectional dotted black arrows: simultaneity relation ships for pair of application nodes characterized by c? equal to 1 .

• Bottom graph G ^T (V _z , U _z ), bidirectional dashed black arrows: serialization rela tionships on the same physical machine for pairs of application nodes character ized by x? equal to 1 .

• Bottom graph G ^T (V _Z , U _Z ), bidirectional red arrows: global serialization relation- ships for pairs of application nodes characterized by *? equal to 1.

It is worth pointing out that a further transformation (following the logic described in Section 3.3) may be performed to graphs G ^v (V _z , A _z ) (V _z , U _z ) to separate com puting and storage application nodes (see Figure 8). Note that, in Figure 8, the bid- irectional blue arrows represent the storage traffic demands. In a similar way, graphs G ^v (V _Z , A _Z ) and G ^T _Z ( V _Z , U _Z ) could be transformed into their corresponding P-reliable version by following the procedure described in Section 3.2.

To conclude, note that the multi-period nature of the new distributed multi-period or chestration system allows the application designer to run applications (multi-period workloads) where a part of the virtualized elements (application nodes) can be gen erated in real-time in a on-demand fashion, according to the output of the virtualized elements (application nodes) already running. For instance, in our 3D mapping ex ample, the number of 3D processing virtualized elements (application nodes) may be dynamically computed by the optimization algorithm run inside the 3D optimizer vir- tualized elements; this algorithm is designed to decide how many sub-regions have to be reconstructed in parallel to minimize 3D reconstruction computing times. Oth erwise, by deciding the number 3D processing application nodes in advance, the 3D optimizer virtualized elements will simply decide which of these 3D processing nodes should be activated. The new multi-period orchestration scheme grant the application designers/owners with a substantial degree of freedom during the application devel opment/planning stage.

4 The task assignment module

The task assignment module is the core of the distributed multi-period orchestrator. It is responsible for computing the multi-period placement solution describing how to map each virtualized element on top of a hosting machine while optimizing one or multiple given criteria and respecting a given set of system constraints. The main blocks of the task assignment module consist in two strongly tied components:

• A mathematical formulation of the multi-period workload placement problem.

• A collaborative multi-period placement algorithm to solve, in real-time, the multi period workload placement problem.

It will be appreciated that the task assignment module is also referred to as the dis tributed multi-period orchestrator.

4.1 The multi-period workload placement problem

The multi-period workload placement problem is the mathematical representation of the orchestration process carried out to virtualize multiple multi-period workloads on top of the available virtualization ready physical infrastructure. The optimization prob lem is obtained by leveraging all the definitions previously presented in Table 2.

To summarize, the multi-period workload placement problem is presented below: Given

• A graph G ^p ( N , E) made by nodes and arcs represented as a set N of hosting machines (nodes) and a set E of physical communication links (arcs), where:

- Each hosting machine i e N\

* Offers an amount w„ of resource r e f?

* Is run with hardware configuration k e K ^r for resource r e f? if binary parameter ¾ _fcr is equal to 1 .

* Consumes e, Watt of energy, once activated.

* Is characterized by a overall wireless cell throughput of ¾ (if equipped with at least one wireless communication interface);

- Each physical link (i, j) e E\

* Is characterized by a step-wise throughput-distance function described by the set of pieces h e H ¹³ corresponding to link capacity values c _ljh and by non-negative distance parameters For wired links, the step-wise throughput-distance function is composed by just one hori zontal piece.

* May belong to multiple wireless cells, and thus to multiple sets Z¾ (if established by wireless network interfaces);

• A set P of routing paths, where each path p e P is characterized by a sequence of links of E that starts from source hosting machine o _p and terminates in destin ation hosting machine t _p .

• A set Z c Z of multi-period workloads (applications) already placed (mapped) on top of graph G ^P (N, E), each one represented by the dedicated graphs G ^v _z ( V _z , A _z ) and G ^T _Z ( V _z , U _z ) already described in Section 3;

• A second set Z c Z of multi-period workloads (applications) demanding to be hosted on top of graph G ^p ( N , E), each one represented by the dedicated graphs G ^v _z ( V _z , A _z ) and G ^T _Z ( V _z , U _z ) already described in Section 3;

The distributed multi-period orchestrator must decide

• Which virtualized element (application node) to host on each hosting machine and which virtualized element (application node) to put in the waiting queue— ? and y _l ^z _jhs binary variables;

• Which application to refuse in case not enough resources are available— g _z binary variables;

• Which position should be assigned to each mobile node— L , \J , u ^p , vf ,

• Which hosting machine should be activated— v _t binary variables;

• Which routing path to select to serve traffic demand between two virtualized elements— TT _to , p _ri , p _ri and /? binary variables, as well as f _{ij t} f _{ij t} f _{ij t} /? , f? _{j t} f Ci non-negative real variables.

• Which hosting machine should act as auxiliary network maintainer node for a given application— binary variables wf

• Which virtualized element already placed on a active host machine to migrate to a different hosting machine, by considering both network-based and physical migrations— w^, binary variables;

To minimize eight cost components

1. Overall energy consumption— v, binary variables.

2. Overall link delay costs— ¾ non-negative real variables.

3. Overall resource utilization costs— u„ non-negative real variables.

4. Overall refusal costs— g _z binary variables.

5. Overall migration costs— w\ ₃ binary variables.

6. Overall wireless cell congestion costs— T _% non-negative real variables.

7. Overall node movements— vf and u non-negative real variables.

8. Overall uncertainty costs— ¾/>? non-negative real variables.

While respecting multiple problem constraints, including those to

• Respect precedence/simultaneity/serialization/parallelization requirements.

• Respect network capacities while satisfying network demand requirements.

• Respect resource availability while satisfying resource demand requirements.

• Respect geo-location and mobility limitations.

• Respect reputation levels.

• Respect priority requests.

• etc.

It will be appreciated that some problem variables do not represent direct decisions of the distributed multi-period orchestrator. They are instead used as auxiliary vari ables to quantify objective function components and evaluate the secondary effects produced by the main decision variables. These variables can be found in Table 2. The multi-period workload placement problem can be formally expressed by the fol lowing Mixed Integer Non-linear Programming (MINP) formulation, which is presented one group of equations at a time to make place for the corresponding descriptions: Multi Objective function

The multi-objective function is made by eight different cost minimization components:

1. Overall energy consumption.

2. Overall link utilization cost (it can be interpreted also as a monetary price). 3. Overall resource utilization cost (it can be interpreted also as a monetary price).

4. Overall refusal penalty cost. Both the refusal of an application, as well of the single virtualized elements (application nodes) are accounted for.

5. Overall migration costs. It will be appreciated that opportunistic physical migra- tions have a lower cost with respect to active physical migrations.

6. Overall wireless cell utilization cost .

7. Overall hosting machine movement cost.

8. Overall uncertainty cost.

Basic placement rules

The first group of constraints to be added concerns the basic placement rules for the application nodes:

Vijn G {0, 1} V z E Z,i E V _z , j E V _z \ {¾} , n E N,

(16) E {0, 1} \/ G /V,

(17) 9z £ {0, 1} Vz G .

(18)

Equation (2) prevents the distributed multi-period orchestrator from placing an applic ation node multiple times, while Equation (5) prevents the distributed multi-period or chestrator from removing a virtualized element (application node) already placed dur ing previous optimization rounds. According to Equation (4), a hosting machine must be activated to host any virtualized element (application node), as well as the distrib uted multi-period orchestrator must respect the compatibility requirements of the hos ted virtualized element ( and h parameters). Equation (3) states that a virtualized ele ment (application node) i G 1 of application z e Z can be placed on hosting machine i G N only if this latter is not busy, or if it is already placed on it. A busy hosting machine is typically a moving hosting machine in the process of performing a specific task of a virtualized element as well as a task in support of another virtualized element (e.g., move to improve network performance). According to Equation (6), an application z G Z is considered placed ( g _z = 1) if and only if its mandatory virtualized elements (application nodes) i G n _z \ b _i = 1 are placed during the current optimization round. Similarly, Equation (7) states that an application is considered placed if and only at least b _z of its virtualized elements (application nodes) can be placed during the current optimization round. Equation (8) instructs the distributed multi-period orchestrator to respect precedence relationship: being i, j G V _z \ i F j two virtualized elements (ap plication nodes) of application z G Z characterized by cb = 1, virtualized element (application node) j can be placed at this optimization round if and only if also virtu alized element (application node) i is successfully placed. Slightly different is instead the meaning of Equation (9), which forces two virtualized elements (application nodes) i, j G V _z \ i F j of the same application z G Z that are characterized by c\ ₃ = cb = 1 to be placed at the same optimization round (even on different hosting machines). If two virtualized elements (application nodes) i, j G V _z \ i F j of the same application z e Z cannot be run together when co-placed on the same machine cb = cb = 1, Eq. (10) is used to allow the co-placement of those virtualized elements (applica tion nodes) only in case one of them has concluded its operations. Finally Equation (1 1 ) forces certain pairs of virtualized elements (application nodes) i, j e V _z \ i F j of application z e Z characterized = 1 to be co-placed. We define here also new co-placement constraints (12)-(14) necessary to define variables y, since these variables will be exploited later for resource availability constraints. Finally, Equations (15)-(18) define the domain of basic placement variables x, co-placement variables y, node activation variables v and application placement variables g.

Resource allocation

To correctly manage the corresponding set of hosting machines, the distributed multi period orchestrator must guarantee that enough resources are available on each host- ing machine to host the desired subset of virtualized elements (application nodes). The distributed multi-period orchestrator must also consider that some virtualized ele ments (application nodes) may be able to share the same amount of resources when placed on the same hosting machine. The following group of constraints is introduced to correctly manage the physical resources:

Viri Virsi fiirs — 0 V z G Z, s G S _z , i G /V, r G R,

(30)

U _lr > 0 Vi E N, r e R,

(31)

T ,f e {0,i} V z G Z, i G ,

(33)

¾ G {0, 1} Vz G , (i, j) G _z .

(34)

Equations (19)-(22) guarantee that hosting machine resources are not consumed bey ond availability, considering that some virtualized elements (those belonging to the same application type S _z and capable of sharing resources, see parameter q) may share some of their resources: the same principle is also considered by resource utilization cost constraint (23), which is used to evaluate the resource utilization cost on each hosting machine. Equations (24)-(27) are used to correctly compute the co- location variables T? , which are equal to 1 if virtualized element (application node) i G V _z of application z e Z has concluded his blocking operations and it is co-placed with a fully active virtualized element (application node) j of the same type s e S _z that can share its resources. Finally, Equations (28)-(29) are used to determine the traffic demands whose traffic should not be considered due to co-placement with other active virtualized elements (application nodes) of the same type. For sake of completeness, Equations (30)-(34) define the domains of the variables just introduced.

Geo-location constraints

All the constraints related to hosting machine position and the corresponding position ing rules to be respected are now introduced:

Equations (35)-(38) allow to compute the X-Y distances between two different hosting machines i, j e N\ i F j. Similarly, Equations (39)-(42) are used to estimate the X-Y distances between pre-optimization and post-optimization positions of the same hosting machine i e N. Equation (43) allows a virtualized element (application node) i e V _z of application z e Z to be placed only on top of hosting machines j e N laying within the FOA defined by the application during the workload generation phase. Equations (44)-(47) force each hosting machine to move toward the position (a valid set of coordinated within the application DOA) requested by the hosted virtualized element (application node). Thus, a hosting machine cannot host, at the same time, two different virtualized elements (application nodes) related to not overlapping DOAs. On the other side, Equations (44)-(47) prevent a hosting machine from moving beyond the boundaries of its rectangular AOA. Remind that these equations can be easily modified to account for any area shapes. For sake of completeness, Equations (52)- (54) define the domains of the variables just introduced. M is used to denote a large enough value, e.g., 100000.

Battery management constraints

Moving nodes may not be connected to an unlimited power source. For this reason, at any optimization round, the distributed multi-period orchestrator must verify that at least one reachable recharging station is in range to support each moving hosting machine. This means that the recharging station selected by the distributed multi period orchestrator may be different from the charging station that will be selected by the energy manager described in Section 6. The following group of constraints is introduced to guarantee the availability of recharging stations:

Equation (56) forces the distributed multi-period orchestrator to assign each moving hosting machine to one hosting machine with battery recharging capabilities. Equa tions (57)-(60) compute the distance between a hosting machine and its assigned hosting machine with battery recharging capabilities. Equation (61 ) computes the trav- eling time necessary to reach the hosting machine with battery recharging capabilities while respecting the maxim speed of the considered moving hosting machine, while Equation (62) computes the minimum traveling time E ™ required by a hosting ma chine i e N to move to the desired post-optimization position. Finally, Equation (63) prevents the distributed multi-period orchestrator from assigning a virtualized element (application node) to a hosting machine without enough battery life, while Equation (64) guarantees that enough battery life is available for any moving hosting machines serving traffic demands of an application. Finally, Equation (65) defines battery life constraints for all the moving hosting machines involved in active physical migrations (opportunistic migrations are not considered because the distributed multi-period or- chestrator assumes that a hosting machine has enough battery life to complete a pre programmed travel). Note that /? and variables are computed in the next groups of constraints. For sake of completeness, Equations (66)-(67) define the domains of the variables just introduced.

Reputation and availability constraints

The following group of constraints is used to manage the placement aspects related to the fact the hosting machine may appear and depart in an emergent (opportunistic, unscheduled) way:

¹ i ³ 0 Vz G Z, I G V _z , j G N. (72)

Equation (68) states that a multi-period placement configuration is valid if and only if a hosting machine j e N has a reputation /¾ greater than the minimum reputa tion level Ri required by a virtualized element (application node) i e V _z of application z e Z. Equations (69)-(70) evaluate the amount of uncertain operation time for a virtualized element (application node), which depends on the availability of both the hosting machines and the communication nodes in support. Uncertain operation time is considered whenever a virtualized element (application node) is expected to finish after the estimated departure time of the hosting machine or of the many supporting communication nodes. Finally, Equation (71 ) prevents the distributed multi-period or- chestrator from placing premium virtualized elements (application nodes) i e V _z of application z e Z {y? = 1) on the top of hosting machines expected to leave before the end of operations. For sake of completeness, Equation (72) defines the domain of the variables just introduced.

Migration constraints

Virtualized elements (application nodes) can be moved from their current hosting ma chine to another hosting machine because requested by the users (by changing, for instance, the FOA of the application node) or to mitigate resource availability problems. The next group of constraints is defined to manage this process, which can be com pleted by exploiting network based data transfer, as well as the physical movement of data. Note that set N _t with i e N is used to denote the set of hosting machines defined as N \ {¾}, while set V _z ^l with i e V _z and z e Z is used to denote the set of application nodes defined as V _z \ {/}

Equation (73) is necessary to correctly activate binary migration variables any time a virtualized element (application node) is moved to a new hosting machine, while Equation (74) guarantees that only one type of migration is selected (network-based, physical active, physical opportunistic) and that the migration is not done toward a busy hosting machine. Equation (75) prevents the distributed multi-period orches- trator from commanding an active physical migration if the current hosting machine cannot move fast enough to cover the required distance before the maximum down time delay is expired. Equation (76) forces the hosting machine supporting an active physical migration to physically move toward the destination hosting machine. It will be appreciated that the destination hosting machine will be free to move, if necessary, after the successful migration; for this reason, the pre-optimization position (not the post-optimization one) of the destination hosting machine is considered in Eq. (76). Equations (77), (80) and (82) forbid the distributed multi-period orchestrator to sup port physical migrations for the virtualized elements (application nodes) of a given application when the hosting machines are currently running the virtualized elements (application nodes) of other applications (in this way we prevent performance degrad ation for these other applications). It will be appreciated that these equation could be relaxed to allow a hosting machine to first migrate by network all the virtualized elements (application nodes) of the other applications, and then start the physical mi grations. Further information on the control of variables w are expressed in Equations (1 1 1 )-(1 13) presented in the section dealing with network routing in mobile environ ments.

Equation (78) allows a hosting machine to support an opportunistic physical migra tion if the hosting machine itself had previously communicated that it will move toward the necessary destination hosting machine, while Equation (79) guarantees that the pre-planned movement will end before the maximum downtime period allowed for the virtualized element (application node) to be migrated expires. Equation (81 ) prevents a physical migration hosting machine to become the migration target of other virtualized elements (application nodes) of the same application. It will be appreciated that we do not explicitly consider virtualized elements (application nodes) of other applications be cause they are prevented from migrating toward a physical migration hosting machine by the presence of Equations (77) and (80). Equation (82) prevents physical migra tion hosting machines from hosting virtualized elements (application nodes) of other applications not involved with the migrating virtualized elements (application nodes). Finally, Equations (83)-(85) force the distributed multi-period orchestrator to move to gether the virtualized elements (application nodes) sharing the same resources. For sake of completeness, the domains of migration variables are defined by Equation (86).

Routing in wireless networks

All the constraints and variables required to optimize routing into the virtualization ready physical infrastructure managed by the distributed multi-period orchestrator to support standard traffic demands, migration traffic, and deployment traffic are now introduced:

Vijhs — ^X ih + ^X _j s 1 V z G , (i, j) G A _z , h G N, s G N _h ,

(87)

„z

Vijhs — ^X ih V z G , (i, j) G A _z , h G N, s G N _h ,

(88)

,z

Vijh s < x z

js V z G Z, ( i, j ) G A _z , h G N, s G N _h ,

(89)

r _i < x w _l ^z _tp V z G Z, i G V _z , p G P,

(93) Equations (87)-(89) are necessary to correctly compute traffic demand placement vari ables y. Equation (90) states that at least L (reliability level) paths are activated to serve each traffic demand (i, j) e A _z of application z e Z, while Equation (91 ) pre vents the distributed multi-period orchestrator from activating the wrong paths (those not connecting the source and the destination of the corresponding traffic demand once it has been placed). Equation (92) has the same responsibility of Equation (90), but in this case tha routing paths are selected to support virtualized element (applic ation node) migrations. Similarly to (91 ), Equation (93) guarantees that the activated paths are able to support the pair of hosting machines involved in the corresponding migration. Again, Equations (94)-(95) are used to activate at least L routing paths to support the first deployment of a virtualized element (application node), while choos ing the correct paths in terms of source and destination hosting machines. Equations (96)-(98) are used to compute the total amount of flow produced on each link by each type of traffic, i.e., standard, migration-based, deployment-based. Note that T vari- ables are used to discard the portion of traffic that can be shared by co-placed virtu alized elements (application nodes). Finally, Equations (99)-(101 ) prevents the distrib uted multi-period orchestrator from modifying the routing variables involving busy links (e.g., links of hosting machines that are moving). For sake of completeness, variable domains are defined by Equations (102)-(105).

Routing in mobile environments

In fully mobile environment, network performances can be guaranteed only if node movement is somehow controlled. The moving nodes are dedicated to serve only a specific application z e Z. In this way, the movements caused by the virtualized elements (application nodes) of an application should not interfere with the perform- ance of other applications running on an overlapping subset of hosting machines. The following group of constraints are defined:

0 £ .¾ /¾ ϊy n, Vz G , (i,j) G , (115)

/- e {0,1} Vz G , (z,j) G E, (116) i5 e {0,l} VzeZ,jeV _z ,ieN, (117) m G {0, 1} VzGZ.JGi . (118)

First, Equations (106)-(108) are used to compute the total amount of traffic carried by a link which is generated by a specific application (the three types of traffic). Note that for our purpose we do not have to consider sharing variables T like in Equations (96)-(98). Then, Equation (109) is used to determine whether a link is used by the traffic related to a specific application z e Z, while Equation (110) has the same responsibility related to the fact that a hosting machine is serving traffic generated by a specific virtualized element (application node). Equations (111 )-(113) allow to mark a hosting machine as communication node for a given application z e Z if and only if it is not involved in any way with other applications (neither hosting their virtualized elements, nor serving their network traffic). Finally, according to Equation (1 14), only communication hosting machines assigned to a given application can move. For sake of completeness, variable domains are defined by Equations (1 15)-(1 18).

Mobile link capacities

In wireless networks, there exists a potential physical network link for each pair of hosting machines with a wireless network interface. The network bandwidth offered by each wireless link is related to the distance between the hosting machines at the extremities of the considered links. Note that in case of wired links, the link through put/capacity is instead fixed (one single horizontal piece). The following group of con- straints allows to correctly compute the current link capacities and, consequently, to respect them:

Cijh £ {0, 1} V, (i, j) E, h H ¹ (129) i j , T~ij z o V (i, j) e E, (130) T _r , t _r > 0 M r G R, (131 )

(132)

Equation (1 19) is used to correctly activate the right piece of the throughput distance function of each physical link, while Equation (120) imposes that one piece of that function is activated per link. Equations (121 ) and (122) prevent the capacity of each link from being overutilized (with both pre-optimization and post-optimization node po- sitions). Equations (123)-(124) compute the link delay with pre-optimization and post optimization node positions, while Equations (125)-(126) do the same but for path delays. Finally, Equations (127) and (128) enforce maximum path delay constraints, by considering both pre-optimization and postoptimization positions. For sake of com pleteness, variable domains are defined by Equations (129)-(131 ).

Mobile cell capacities

Wireless nodes communicating over the same Wireless Local Area Network (WLAN) are typically required to configure all the D2D wireless link on the same trans mission channel. This leads all the links of the same WLAN that are in range with respect to each other to share the same spectrum, and thus the same transmission capacity. The following group of constraints is introduced to model this phenomenon:

Equation (133) is necessary to evaluate when a hosting machine is close enough to another hosting machine to be considered as a member of the wireless cell of this latter. Equations (134)-(135) are used to determine the physical links that are mem bers of a given wireless cell: it is sufficient the one of the two edges of the considered link is member of the wireless cell itself. Equations (136) and (137) prevent the ca pacity of each wireless cell from being over-utilized (with both pre-optimization and post-optimization node positions). Finally, Equations (138)-(139) compute the wire less cell utilization costs by considering both pre-optimization and post-optimization node positions. For sake of completeness, variable domains are defined by Equations (140)-(141 ).

4.2 The algorithm for distributed multi-period workload placement

The MINP formulation just presented in Section 4.1 to define the multi-period workload placement problem is crucial to:

• Determine which combinations of placement decisions are feasible. • Compare the quality of different feasible solutions with respect to the defined multi-objective function.

The role of the distributed multi-period orchestrator is to heuristically compute, in real time, a feasible and optimal placement solution.

A small part of the information necessary to solve the multi-period workload placement problem is found directly in configuration files visible to the distributed multi-period or chestrator instance (see Section 4.3) running on each hosting machine. The remaining information is instead collected by the distributed multi-period orchestrator instance of each hosting machine from the other auxiliary modules (see Section 4.4).

The implementation details of the distributed multi-placement workload placement al gorithm run by the distributed multi-period orchestrator instance of each hosting ma chine (when necessary) are now introduced. A founding principle of the algorithm is that the optimization process should not consider, at each optimization iteration, the whole virtualization ready physical infrastructure. Such a global approach would create issues in terms of:

• Overhead generated by the necessity of transmitting all the problem information to at least one centralized orchestration instance.

• High computing times caused by the combinatorial explosion of variables and constraints to be considered.

• Management of mobile opportunistic nodes.

To mitigate such problems, multiple sub-clusters i e Q made by hosting machines and links laying in close proximity (in terms of hop-distance) are dynamically built. In this way, each sub-cluster i e Q can solve a small-size instance of the multi-period workload placement problem involving just the hosting machines belonging to the cor responding sub-cluster, i.e.:

• Subset Ni of hosting machines of sub-cluster i e Q.

• Subset Z¾ of physical network links of sub-cluster i e Q.

• Subset P _t of routing paths interconnecting the hosting machines by exploiting only links of Z¾.

And all related parameters. The flow process describing the optimal orchestration mechanism is now presented:

1. Optimization triggering event

A triggering event requiring placement optimization is registered by the distributed multi-period orchestration instance of a hosting machine belonging to N\

• Periodical re-optimization request: the distributed multi-period orchestrator of the hosting machine elected as sub-cluster supervisor (see next part on cluster form ation) periodically generates a re-optimization request. The rationale behind this mechanism is that a periodical re-organization can exploit real-time resource re quirement values depending on the real resource consumption values observed for the virtualized elements (application nodes) already placed. These values could greatly deviate with respect to the nominal values configured for the first placement operation by the multi-period workload generation module. Note that multiple sub-cluster supervisor nodes can be elected to improve the sub-cluster resilience.

• De-allocation event: a virtualized element is removed and the corresponding sub-cluster supervisor node generates a re-organization request to improve per formance or place virtualized elements (application nodes) that could not be placed before.

• New application event: a new application placement request is received by the orchestration instance of a hosting machine (typically a gateway node for re quests coming from the Internet) from a multi-period workload generation mod ule.

• Application modification request: a modification request for an application already placed is received by a hosting machine. The request is redirected to the distributed multi-period orchestrator instance of the sub-cluster supervisor hosting machine managing the sub-cluster where the application is currently run ning. The application modification may directly produce a migration if the DOA is changed.

• Performance degradation alert: the virtualization engine of a hosting machine observes a degradation performance of a virtualized element (application node), so it transmits a re-organization request to the distributed multi-period orches- trator instance of the sub-cluster supervisor physical machine responsible for the virtualized element itself.

• New hosting machine event: all the distributed multi-period orchestrator instances of the sub-cluster supervisor hosting machines laying within a certain hop-distance (on the telecommunication network) from a new hosting machine are notified of the potential availability of new resources. A new placement re organization request may be generated on these hosting machines.

• Hosting machine or physical link departure/failure/temporary unavailability: the distributed multi-period orchestrators of the supervisor hosting machines of the sub-cluster interested by a node/link departure/failure/temporary unavailability generate a new placement re-organization request. It will be appreciated that temporary unavailability can be related to battery recharging operations triggered by the energy manager (see Section 6)

• etc.

2. Cluster formation

The generation of a multi-period placement optimization or multi-period placement re-organization request triggers the dynamic formation of new sub-clusters. First of all, the behavior of the hosting machine whose distributed multi-period orchestrator instance generated the optimization request is now analyzed:

• If the hosting machine does not have any sub-cluster supervising responsibilities, it will trigger the progressive construction of one or more new sub-clusters that it will lead as supervisor in case the placement bidding process is won (see Paragraph 4 below).

• If the hosting machine is already a supervisor for one or more sub-clusters, it will trigger the placement optimization algorithms within these sub-clusters them selves. If configured accordingly, it may also trigger the construction of new sub-clusters through the process described in the previous bullet point.

• Independently of its supervisor status, the distributed multi-period orchestrator instance of the hosting machine will broadcast the placement request through DASS (see Section 5), by considering two strategies:

1. Broadcast limited to a pre-configured hop distance from the hosting ma chine. Note that the hop distance can be increased and the operation re peated in case no satisfying multi-period placement solution is obtained within the generated sub-clusters.

2. Broadcast destined to a specific FOA.

All the hosting machines already supervising a sub-cluster that receive a request will automatically try to solve the multi-period workload placement problem within the same sub-cluster. Otherwise, each hosting machine has a certain probability of launching the formation of a new sub-cluster that it will supervise. Note that each su pervisor candidate can build multiple clusters of different size in terms of hop-distance from the supervisor hosting machine. The cluster formation managed by a supervisor hosting machine is performed through a consensus algorithm supported by DASS to distribute the necessary information.

Before being ready to compute the best multi-period workload placement solution, the clusters must be further extended to account for:

• Placement of new applications: each sub-cluster not including the hosting ma chine that originated the first optimization request will run a route discovery pro tocol (similar to those used for ad-hoc network routing) to determine an additional subset of hosting machines and physical links to be included in the cluster to ac count for deployment bandwidth.

• Internet connectivity requirements: a similar process is run to discover Internet gateway nodes in case the involved applications require internet connectivity. Note that a sub-cluster may already include an Internet gateway due to previous placement operations.

• Migration for FOA modifications or performance deterioration: in this case, be sides discovering and including the nodes and links on the paths between the new sub-cluster and the source sub-cluster (from where operating the migra tion), the system creates a new super-cluster merging destination and origin sub-clusters. It will be appreciated that sub-cluster supervisors may be controlled by a specific al gorithms aiming to merge overlapping sub-clusters. Furthermore, other algorithms may be constantly run to delete sub-clusters that become idle, as well as split two portions of the same sub-cluster that do not interact among themselves.

3. Placement solution computation and intra-sub-cluster bidding

The supervisor hosting machine of a sub-cluster distributes all the new application in formation to the distributed multi-period orchestrators instances of all the sub-cluster members (through DASS, see Section 5). If the sub-cluster is new, all the hosting ma chine distributed multi-period orchestrator instances in the sub-cluster will distribute, always with DASS, all the other problem parameters. Otherwise, these information should be already available on each hosting machine.

Once each sub-cluster distributed multi-period orchestrator instance retrieve all the necessary problem parameters, it repeats a certain number of iterations of one or more resolution algorithms. At the end of the process, or after a user-configured time-out, the solution with the best objective function is the only kept. It will be appreciated that any algorithm generating feasible solutions for the MINP formulation of Section 4.1 can be leveraged, including meta-heuristics, local searches, greedy algorithms, genetic algorithms and many others. In this case we propose to use two different greedy algorithms, Feasible Placement (FP) and Optimal Placement (OP), each applied in two different modes, i.e., partial (only the variables related to the application nodes directly involved in the placement optimization— e.g., those of a new application)— can be adjusted) and full (the whole sub-cluster variables can be optimized).

Partial FP and OP should be tried first to avoid migrations and configuration adjust ments that may negatively affect the performance of the application nodes already running. In case the solutions of partial methods are not considered good enough, full FP and OP are launched to look for better solutions.

Both FP and OP are based on the same macro-routines:

• RSAN: Randomized sorting of the list of virtualized elements (application nodes) to be placed or moved.

• RSPN: Randomized sorting of the hosting machines. • RSTD: Randomized sorting of the traffic demands involving the considered vir tualized elements (application nodes) and all the other application components already placed, e.g., gateway hosting machines, migration sources, other virtu alized elements (application nodes).

• FTPV: Feasibility test of a virtualized element (application node) placement op tion by evaluating resource allocation, geo-location and energy-management constraints— virtualized element (application node) i e V _z of application z e Z on hosting machine j e N. Note that concerning post-optimization positions (for moving nodes), the feasibility test considers the closest position belonging to the corresponding DOA with respect to the current position of the considered hosting machine.

• FTFV: Feasibility test of a traffic demand, a migration demand or a deployment demand placement option.

• FE: Evaluation of the objective function value related to current placement con figuration.

• SPU: Computation of the shortest routing path between a pair of physical ma chines by considering current link utilization cost values r _iy

• SPC: Computation of the capacity constrained shortest routing path between a pair of physical machines by considering current link utilization cost values r _iy

• LID: Identification of LID list containing all the links preventing the computation of a shortest path with enough capacity to host a new traffic demand involved in the new placement decision.

• CND: Identification of the nodes in conditions to become communication nodes for a given application.

• SPR: Re-positioning of communication nodes to repair a shortest path link without enough capacity to host a traffic demand involved in the new placement decision. If F communication nodes are considered, SPR will just position them along the straight line connecting the two edges of the link to be repaired by ob taining F + 1 sub-pieces (sub-links) of equal distance. The reparation fails if the new positions of the communication node causes some network requirement to fail.

• FFE: Verification that no placement constraint (some constraints may be im possible to be checked during the greedy placement process) is violated. If violations are identified corresponding application nodes, and even whole ap plications may be removed.

The macro-routine above is combined to describe the FP algorithm:

1. Initialization: RSAN plus RSPN.

2. Pop the first virtualized element (application node) of the RSAN list.

3. Pop the first hosting machine of the RSPN list.

4. Perform FTPV of the considered virtualized element (application node) on the considered hosting machine. If the placement option is unfeasible, and RSPN list is not empty, then go to Point 3. If the placement option is unfeasible, and RSPN list is empty, then mark the virtualized element (application node) as queued and go to Point 2. Otherwise, go to next Point.

5. Run RSTD to obtain a randomized list of all the network flow requirements re lated to the considered virtualized element (application node) once placed on the considered hosting machine.

6. Pull the first flow request (traffic demand, or migration traffic request, or deploy ment traffic request) of the RSTD list.

7. Perform FTFV of the considered flow request, i.e.:

(a) Compute the SPC between the source and the destination hosting machine (and viceversa). If L valid paths exist and RSTD list is not empty, go to Point 6. If a valid path exists and RSTD list is empty and RSAN list is not empty, mark the virtualized element (application node) as placed and go to Point 2. If L valid paths exist and RSTD list is empty and RSAN list is empty, mark the virtualized element (application node) as placed and go to Point 9.

(b) Compute the SPU between the source and the destination hosting ma chines (and viceversa).

(c) Run LID.

(d) Pop the first link of the LID list. (e) Run CND.

(f) Pop the first node of the CND list.

(g) Run SPR with all the links popped up to now. If SPR fails and CND is not empty, go to Point 7d. If SPR fails, CND is empty and RSPN list is not empty, then go to Point 3. If SPR fails, CND is empty and RSPN list is empty, then mark the virtualized element (application node) as queued and go to Point 2. If SPR succeeds, mark the flow request as placed and go to Point 6. If SPR succeeds and RSTD list is not empty, mark the flow request as placed and go to Point 6. If SPR succeeds, the RSTD list is empty and RSAN list is not empty, mark the flow request as placed, mark the virtualized element (application node) as placed and go to Point 2. If SPR succeeds, the RSTD list is empty and RSAN list is empty, mark the flow request as placed, mark the virtualized element (application node) as placed and go to Point 9.

8. Run FFE.

9. Run FE and return the corresponding value computed through Eq. 1.

If the BF algorithm is considered, the only difference with respect to the FP procedure just described is the fact that all the hosting machines of the RSPN list are tested with FE (instead of passing to the next step any time a feasible solution is identified) to allow the algorithm to choose the best local decision. It will be appreciated that the greedy approaches of both FP and OP can lead to local optima with a significant gap from the real optimum solution. It will be appreciated that an additional step can be added between FTPV and FTFV to test different the migration types. In a FP approach, the first feasible migration type is maintained, while in a BF approach, all the three migration types could be evaluated (network-based, physical active, physical opportunistic).

DASS is then used by each sub-cluster distributed multi-period orchestrator instance (one per hosting machine) to share the best objective function found. The sub-cluster supervisor will then select the best value and retrieve the corresponding placement solution from the multi-period orchestrator instance that obtained it. It is worth pointing out that the resolution scheme just presented can be naturally applied to any version of the multi-period workload optimization problem. It could also be easily adapted also to deal with other mathematical formulations for the same problem.

4. Inter-sub-cluster bidding

All the sub-cluster supervisor hosting machines will transmit the pair composed by the best objective function and the corresponding multi-period workload placement solution to the distributed multi-period orchestrator instance that originally generated the optimization/re-organization request. This distributed multi-period orchestrator instance is thus responsible of comparing all the solutions received within a pre configured time limit by multiple sub-cluster supervisors and electing the sub-cluster that won the multi-period workload placement bidding process. The ID and address of the supervisor of the winning sub-cluster is also communicated to the multi-period workload generation module used to create, manage and stop the applications.

4.3 Parameters configured by the distributed multi-period orchestrator

When the distributed multi-period orchestrator instance is initialized on a hosting ma chine, a configuration file created by the virtualization ready physical infrastructure manager is read to correctly set some input parameters directly related to the distrib uted orchestration process:

• The set of valid physical resource and capacities R.

• The set of valid resource configurations K ^r .

• Resource over provisioning parameters _r .

• Network link over provisioning parameters C.

• Resource utilization cost functions F _G ().

• Link delay/cost function D ().

• The set of objective function weights <¾, V/ e {1, 2, 3, 4, 5, 6, 7, 8}

• Computation time-limit within a sub-cluster.

• Overall computation time-limit considered by the distributed multi-period orches trator instance that generates an optimization request before selecting a winning sub-cluster. • Maximum broadcast hop-limit for sub-cluster research.

4.4 Interaction with the other modules

The distributed multi-period orchestrator instance running on each hosting machine exploits the data distribution/replication services of the DASS to coordinate the dis tributed solution computation process. A large portion of these interactions has been already documented in Section 4.2. However, it was not mentioned that DASS is cru cial to force all the distributed multi-period orchestrator instances to converge to the same set of orchestration parameters (see Section 4.3). This specific convergence task can be executed in collaboration with the access manager described in Section 10.

The distributed multi-period orchestrator instance retrieves all the parameters related to the hosting machines and links of the same sub-clusters by interrogating the other modules running on the same physical machine:

• The energy manager: energy consumption, speed and battery autonomy dura tion parameters.

• The geo-location daemon: all physical geo-location parameters.

• The reputation estimator: reputation parameters.

• The access manager: estimated availability parameters.

• The virtualization engine: real time and nominal resource consumption values, network consumption values, state of the application nodes (running, idle, stopped, etc.).

• The telecommunication application: routing paths information, link and cell re lated parameters.

It will be appreciated that each of the modules above retrieves the information from the surrounding hosting machines through the DASS instance running on each hosting machine.

The telecommunication application and the virtualization engine receives all the re source and bandwidth reservation instructions related to the implementation of a new multi-period workload placement configuration. Finally, the distributed multi-period or chestrator instance transmits to the geo-location module all the FOA information of virtualized elements (application nodes) demanding placement; in this way the geo location module will be able to return the list of hosting machines of the sub-cluster of interests that are compatible with the FOA.

5 Distributed Databases for Seamless Information Sharing

A special virtual component is represented by a Distributed Database (DD) middle ware specifically tailored to run on the top of Mobile Ad-Hoc Networks (MANETs) and Opportunistic Networks (ONs), and compatible with any kind of network. A DD mid dleware called Distributed Advanced Storage Service (DASS) was developed. It:

• Encapsulates a standard NO-SQL database instance running on the underlying hosting machine.

• Adopts policy-driven replication strategies to distribute information among the hosting machines participating to the same DASS instance.

• Maintains content-location mapping information to retrieve information not phys ically placed on the underlying hosting machines.

· Run versioning mechanisms.

• Run conflict resolutions mechanisms based on user-defined policies.

A DASS instance is run in a dedicated virtual container that is pre-deployed on each hosting machine aiming to participate to the virtualization ready physical infrastructure. The DASS instance is leveraged by the distributed multi-period orchestrator instance of each hosting machine to distribute all the information required by the distributed multi-period workload placement algorithms to build the local sub-clusters and com pute the corresponding multi-period workload placement configurations for an applica tion demanding for resources. As already pointed out in the previous section, DASS is exploited by all the other modules (not only the orchestrator) to distribute information across the hosting machines of the virtualization ready physical infrastructure.

6 The energy manager

The energy manager has the main responsibility of triggering battery recharging pro cedures (no run by the distributed multi-period orchestration system) that temporary exclude a hosting machine from the virtualization ready physical infrastructure (it is marked as busy through the corresponding 7 parameter) to give it time to fulfill rechar ging procedures. Note that the Q variables modified by the distributed multi-period orchestrator to assign each moving node to a recharging station are simply used to guarantee that a close enough recharging station is always available; however, these variables have no impact with the energy management routines of the energy man agement layer.

This module is used to configure:

• e idle energy consumption of the underlying hosting machine.

• i3 _l : the maximum moving speed of the underlying hosting machine.

• s _¾ : current battery life of the underlying hosting machine.

• å7 current battery life equivalence parameter of the underlying hosting machine. These parameters are transmitted to the orchestrators of the same hosting machine, as well as they are distributed to the surrounding hosting machines through DASS.

At run-time (at each optimization round) the energy management daemon communic ates to the distributed multi-period orchestrator instance of its hosting machine all the real-time battery autonomy data s.

7 The network aware path manager

The multi-period workload placement solution computed by the distributed multi-period orchestration system determines the final position assigned to a moving hosting ma chines to satisfy a virtualized element (application node). The solution guarantees that all network related constraints are satisfied by considring both pre-optimization and post-optimization positions of the hosting machines.

The network aware path manager is an auxiliary module that has the responsibility of coordinating the movements of all the moving hosting machines. Its goal is to guar antee that the final network configuration computed by the distributed multi-period orchestration system by considering the hosting machines placed in their destination positions will remain valid along the whole traveling period. It will be appreciated that this process can be decomposed in multiple independent sub-instances (one per ap plication interested by moving tasks) thanks to the problem constraints (1 1 1 )-(1 13) that prevent the distributed multi-period orchestrator from co-placing a moving virtualized element with another virtualized element of a different application.

The path planning algorithm can be implemented in many different ways. It can be a centralized path planning algorithm running on each sub-cluster supervisor hosting machine, as well as a distributed network maintenance system based on proper node attraction parameters aiming to keep close the physical edges of the relevant links (see the potential-based method used in [2]).

It will be appreciated that the path-planner is also responsible of physically moving the underlying hosting machine.

8 The geo-location daemon

A system based on a software module and a physical interface, or by the combina tion of more of them, capable of estimating the current position of a host machine. Examples of geo-location modules include:

• GPS based system: a host machine equipped with a GPS interface can estimate its position by trilateration with respect to geostationary satellites.

• Ultra-Wide Band (UWB) system: three hosting machines equipped with a UWB interface (e.g., DWM1001 from DecaWave) can compute the relative position of a fourth hosting machine always equipped with a UWB interface by trilateration. The distance between each pair of UWB-powered hosting machines is computed by estimating the flight time of each transmitted communication probe. If one hosting machine is chosen as origin of a reference system of coordinates, all the relative positioning measures done by each subset of four hosting machines can be converted according to it. It will be appreciated that such geo-location module is collaborative and requires all the hosting machines to be be on the same telecommunication network.

• Wi-Fi range-based system: similar to UWB system. In this case, hosting ma chines are equipped with a Wi-Fi interface capable of returning the Received Signal Strength Indicator (RSSI) from other hosting machines in range. The re lative positions are computed by converting the RSSI into estimated distance values (e.g., by fitting a path loss function). Trilateration processes are thus based on these distance values. This module also computes, following requests of the distributed multi-period orches- trator, the binary geo-localization parameters Az9 that determine the hosting ma chines that, based on their location, are authorized to host a given application.

9 The reputation estimator

Each hosting machine that becomes member of the virtualization ready physical in frastructure runs the so-called reputation estimator, a software module responsible for computing a reputation score /¾ of each hosting machine i e N.

A reputation value is assigned to hosting machine by all the other hosting machines available on the telecommunication network. The reputation value is then continuously updated as operations keep running and hosting machines show their level of reliabil ity and participation. Practically speaking, a hosting machine that appears for the first time should receive a basic reputation score from all the other hosting machines. This score can be then progressively improved as the new hosting machine keeps host ing new virtualized elements (application nodes) while guaranteeing the desired level of QoS. In terms of practical implementation, each hosting machine is constantly in formed of the state of the other hosting machines laying within a certain hop distance (information is shared through DASS, see Section 5). Then, each hosting machine merges this real-time information with the historical data available on the surrounding hosting machines to determine metrics such as:

• Known total number of hours worked by a given hosting machine.

• Known total number of virtualized elements served by a given hosting machine.

• Historical availability ratio of a given hosting machine.

• Known total number total number of migrations caused that involved a given hosting machine.

• Historical average duration of the continuous operation interval (e.g., two hours per day) of a given hosting machine.

• Etc.

These metrics are then elaborated by an algorithm to extract the instantaneous repu tation score assigned to a surrounding hosting machine. The reputation values are constantly distributed across the hosting machines of the virtualization ready physical infrastructure, so that the final reputation value assigned to a hosting machine and used by the distributed multi-period orchestrator is the result of a collaborative estima tion effort. In fact, due to the opportunistic nature of virtualization ready physical infra structure management process, a hosting machine considered unreliable by a certain neighbor may be estimated as very efficient by another (due to past collaborations in a common virtualization ready physical infrastructure).

10 The access manager

This module has the responsibilities of managing the first interactions with a new host ing machine appeared as direct neighbor on the underlying telecommunication net- work. In particular, it will take care of:

• Authenticating the hosting machine as authorized entity to participate to the vir tualization ready physical infrastructure. For instance, only hosting machines with a certain MAC address can be white-listed.

• Transmission of common orchestration parameters relevant for the distributed multi-period orchestration processes.

• Retrieve the expected departure time and pre-planned destinations of the new hosting machine.

11 The virtualization engine

Each hosting machine participating to a virtualization ready physical infrastructure runs the so-called virtualization engine, i.e. , a software module whose main respons ibilities include:

• Instantiate a virtualized element (application node) on the top of the hosting ma chine’s operating system.

• Guarantee isolation to the multiple virtualized elements (application nodes) hos- ted on the same hosting machine.

• Share resources among multiple virtualized elements (application nodes) hosted on the same hosting machine according to pre-defined sharing ratio and priority policies.

• Monitor virtualized element (application node) states. • Stop virtualized elements (application nodes).

Note that the OS and the physical hardware of a physical server running a virtualization engine must be configured to allow resource virtualization. For instance, with Intel machines, the Intel Virtualization Technology option must be enabled into the BIOS menu. Examples of popular virtualization engines include:

• Docker Engine, LXD Engine, Kubernets Engine— Container technologies.

• Hyper-V, VMWare vSphere, KVM, Xen Server— Virtual machine technologies. The virtualization engine keeps informing the distributed multi-period orchestration in stance of the same hosting machine about:

• w„ amount of resources available on the underlying hosting machine.

• ¾ _fcr : current hardware configuration of the underlying hosting machine.

• The real time resource consumption figures observed for each hosted virtualized element (application node).

12 The telecommunication application

The whole virtualization ready physical infrastructure relies on a telecommunication network interconnecting all the hosting machine. In this implementation, the ad-hoc communication network built by the HEAVEN communication middleware is considered. HEAVEN is a middleware running in the user space, and thus poten tially compatible with any kind of device without the need of modifying the underlying Operating System (OS).

HEAVEN builds a virtual network layer able to seamlessly interact (through dedicated virtual link layers) with different types of network transmission technologies. For in stance, HEAVEN can manage Wi-Fi interfaces running in ad-hoc (or IBSS) mode [3], as well as Wi-Fi interfaces acting as base station or client in a traditional infrastructure mode.

HEAVEN offers the both unicast and broadcast communication services, by relying on three types of routing protocols:

1. Gossip : Each network node forwards all the packet in transit (not destined to him) to all the network neighbors and decreases the hop counter by 1. Caches are used to avoid forwarding duplicated packets. Gossip is perfect to serve signal- ing/overhead/coordination traffic generated by the Distributed Database running above.

2. Proactive and/or reactive shortest path: One or multiple shortest paths trees are computed by each network node (proactively or on-demand) to determine the next-hop to be used to forward a given packet toward its destination. In a fixed environment, the paths computed by this protocols are directly used to popu late the path set P\ routing become thus given and it is considered a problem parameter (all routing variables are fixed).

3. Dedicated flow-based routing: A dedicated path selected by the distributed multi period orchestrator is allocated to serve a specific traffic demand (i, j) e A _z of application z e Z.

HEAVEN is responsible for discovering new available network nodes and authoriz ing them to participate to the network. HEAVEN provides all the APIs required by the architecture orchestrator to collect the network information related to the network parameters of the multi-period workload placement problem:

• Physical graph/Network topology G ^P (N, E), of the whole virtualization ready physical infrastructure or of the desired N-hop neighborhood:

- N, hosting machine set.

- E, physical link set.

- Z¾, set of physical link laying in the cell of the underlying nodes.

• Routing path set P, if routing is problem parameter,

• Current link and cell capacity values:

- Ci _jh , for instance by calling the private function of a mt7610u Wi-Fi inter face called iwpriv [i fname] get adhocEnt ry. The same command IS used also to return the link RSSI values.

- ¾, or instance by using the Linux command iwconf ig .

• Characterization of the nominal throughput-distance function corresponding to the underlying network interfaces (iT ¹ · ⁷ , l£, l/ ):

The telecommunication network is also meant to receive the bandwidth allocation instructions directly form the distributed multi-period orchestration instance running above.

References

[1] Inc. Amazon Web Services. Amazon Elastic Block Store, Persistent block storage for Amazon EC2. https://aws.amazon.com/ebs/, 2019. Online; accessed 12-February-2019.

[2] J. Panerati, L.G. Gianoli, C. Pinciroli, A. Shabah, G. Nicolescu, and G. Beltrame.

From Swarms to Stars: Task Coverage in Robot Swarms with Connectivity Con straints. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 7674-7681 . IEEE, may 2018. [3] TP-Link Technologies Co. TP-Link, USB Adapters, Archer T2UH— Specific ations. https : //www. tp-link . com/us /products /details /cat-5520_ Archer-T2UH . htmi#specifications. Online; accessed 20-February-2019.