Daniel Balouek-Thomert

Pedro Silva
email: pedro.silva@hpi.de

Kevin Fauvel
email: kevin.fauvel@inria.fr

Alexandru Costan
email: alexandru.costan@irisa.fr

Gabriel Antoniu
email: gabriel.antoniu@irisa.fr

Manish Parashar
email: manish.parashar@utah.edu

Fauvel, Costa, Antoniu Balouek-Thomert Silva

MDSC: Modelling Distributed Stream Processing across the Edge-to-Cloud Continuum

Keywords: Computing Continuum, Stream Processing, Modelling Daniel Balouek-Thomert, Pedro

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

With the proliferation of the Internet of Things (IoT), we have witnessed the development and popularization of new Machine Learning (ML) applications aiming to leverage distributed and heterogeneous data sources to automate decision-making. These applications bring new data processing challenges, in particular related Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. Woodstock '18, June 03-05, 2018, Woodstock, NY © 2018 Association for Computing Machinery. ACM ISBN 978-1-4503-XXXX-X/18/06. . . $15.00 https://doi.org /10.1145/1122445.1122456 to the need to process large volumes of streamed data under highthroughput and low-latency constraints.

Moving away from traditional centralized Cloud models, the use of resources spanning at the Edge of the infrastructure and in the Fog (i.e., between the Edge and Cloud), allows to distribute analytics while preserving low latency, high availability, and privacy. This aggregation of heterogeneous resources along the data path from the Edge to the Cloud, also referred to as the Edge-to-Cloud Continuum, or the Computing Continuum [START_REF] Balouek-Thomert | Towards a computing continuum: Enabling edge-to-cloud integration for data-driven workflows[END_REF][START_REF] Beckman | Harnessing the computing continuum for programming our world[END_REF], can be harnessed to support distributed analytics.

As IoT and ML applications are powered by pipelines of multiple data processing frameworks [START_REF]AWS IoT Greengrass[END_REF][START_REF]Microsoft Azure IoT Edge[END_REF][START_REF] Carbone | Apache Flink: Stream and Batch Processing in a Single Engine[END_REF], the integration of the different software, libraries and platform components is a significant challenge on large and heterogeneous infrastructures. Understanding the dependencies between the application workflows to best leverage the underlying infrastructure is crucial for the end-to-end performance. However, we are currently missing models enabling this adequate mapping of distributed analytics pipelines on the Edge-to-Cloud Continuum.

To tap into the power of the Computing Continuum, we propose MDSC, an approach for modeling distributed stream-based applications running across the Edge-to-Cloud continuum. The objective of MDSC is to facilitate the definition and evaluation of alternative deployment options for such applications atop the Edge-to-Cloud Continuum, in a versatile way.

To enable this vision, MDSC leverages a set of simple but expressive architectural concepts (e.g., layers, processing units, buses), which aim to describe the essential components of the application and to make more explicit their inter-relations and functionalities. These abstractions further enable grouping for components of similar nature and allow to characterize the communication among those groups. Subsequently, this model facilitates the definition of alternative mappings onto the underlying edge/fog/cloud infrastructure.

The contributions of this paper are:

• a hierarchical approach for modeling distributed streambased applications on the Edge-to-Cloud Continuum -MDSC (Section 3); • an illustration of how this model can be applied to a complex ML-based real-life application for Earthquake Early Warning -MDSC EEW (Section 4); • a large-scale experimental validation of MDSC EEW through various experiments on an Edge-to-Cloud infrastructure emulated atop the Grid'5000 testbed (Sections 5 and 6); 1

BACKGROUND AND CHALLENGES

State-of-the-art stream-based analytics applications are mostly built on the premise that data ingestion, management, and processing are done in centralized locations by leveraging general purpose analytics frameworks such as Apache Flink [START_REF] Carbone | Apache Flink: Stream and Batch Processing in a Single Engine[END_REF] or Apache Spark [START_REF] Zaharia | Apache Spark: A Unified Engine for Big Data Processing[END_REF]. At the same time, legacy single-machine ML libraries start to receive support for execution in distributed settings, based on dataflow models [START_REF] Abadi | TensorFlow: A system for large-scale machine learning[END_REF][START_REF] Pedregosa | Scikit-Learn: Machine Learning in Python[END_REF]. Efforts from major Cloud providers enable ML capabilities when consuming data from devices at large scale but do not offer the ability to orchestrate application components across hybrid Edge-Cloud infrastructures [START_REF]Google Cloud IoT Edge[END_REF][START_REF]AWS IoT Greengrass[END_REF][START_REF]Microsoft Azure IoT Edge[END_REF]. Edge Analytics systems take advantage of the processing power of machines located at and near the Edge of the network in order to accelerate and to scale up analytics applications with minimum resource usage. This decentralization of stream-based data analytics systems leads to multiple challenges:

Expressive and versatile models for both the application and the infrastructure. To effectively leverage the computing power near the network edges, powerful and expressive models are necessary to help describe the application by considering the possible configurations and limitations of the underlying infrastructure.

Sustained real-time processing Many Edge analytics systems (ML-enabled or not), such as home assistants and health care systems, require real-time or near real-time processing latency. Achieving it is non-trivial when processing huge volumes of data streamed from heterogeneous sources.

Effective processing distribution considering constrained resources Complex trade-offs needs to be considered when deploying stream-based analytics pipelines across the Continuum: which parts should be executed at the Edge and which in the Cloud?

Given their different scopes, addressing all these challenges within a single framework is a non-trivial endeavour. There is already work on processing distribution [START_REF] Renart | Distributed Operator Placement for IoT Data Analytics Across Edge and Cloud Resources[END_REF] and ML on constrained resources [START_REF] Gupta | Protonn: Compressed and accurate knn for resourcescarce devices[END_REF]. Therefore, in this paper, we focus on the first challenge: provide expressive and versatile models for the application and for the infrastructure, as an effective means to enable real-time processing in analytics applications deployed on the Edge-to-Cloud Continuum (the second challenge).

MDSC: AN APPROACH FOR MODELLING DISTRIBUTED STREAM-BASED ANALYTICS

In this section, we introduce MDSC, a modelling approach which aims to help developers organize the different components of processing frameworks used by analytics applications (ML-based or not), separate their concerns and roles, and provide a set of good practice guidelines for distributing data processing on the Computing Continuum. MDSC can be summarized as a composition of layers, consisting of units, connected by buses.

Modeling Infrastructures as Layers

Processing Layers A layer is an abstract representation of a subset of computing resources of an infrastructure. The main objective of a layer is to describe data processing and characterize the data flow among resources. The strategy for grouping resources is mainly related to the location of the resources and their processing objective.

For example, in an infrastructure composed of Edge, Fog and Cloud, there could be 3 different layers, one for each part of the infrastructure. Each layer groups resources with different characteristics.

Processing units are responsible for data processing (e.g., data transformation, aggregation, or filtering) by means of user-defined logic. Key components of processing units are libraries, data connectors and user-defined logic, that can be extended by system designers. The objective of modeling processing units is to have a straightforward and compact view of the available processing resources of a layer, of their composition and interactions. For example, in a ML application, a processing pod could define the Python Standard Library and scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] as libraries, a Docker image containing an off-the-shelf third party software as user-defined logic, and an implementation of a Kafka connector class as a data connector.

Helper Units provide an environment from which processing units can benefit in order to process data. helper units may be ingestion systems, key-value stores, load-balancing servers, or proxy servers. Notice that a unit does not necessarily map to an entire machine. It can represent management resources and can be encapsulated by a virtual machine, a container, or a process.

Buses They connect layers or units inside a layer. Units inside of the same layer share the same network, however this is not necessarily the case for units from different layers. Helper units have the responsibility of pulling or receiving data through the network and making it accessible for processing units.

Modeling Applications as UDL Components

The main role of UDL (user-defined logic) components of processing units is to expose their data processing logic, i.e., the procedures defined by the user to transform the data. Consequently, UDL components are responsible for mapping the application itself and its placement among the different processing units and layers. For example, UDL components can be encapsulated in a Java program, a standalone binary, a container, or in the processing operators of a workflow/dataflow or stream processing engine, such as Flink.

Features

MDSC has two main features which help the application and infrastructure modeling process.

Organization is crucial when designing complex systems because of the amount of different technologies that need to work together, and their consequent configurations and characteristics. With MDSC, the concepts of layers and buses and processing/helper units help the designers organize and arrange together the different frameworks and technologies at their hands. While conceptually simple, these abstractions are powerful in terms of expressiveness (as illustrated in Section 4).

Separation of concerns is enhanced by organization. MDSC aims at grouping similar roles and functionalities together so that the interactions as well as the interference of the frameworks and technologies become clearer. We argue that besides helping the modeling process, these features allow for a compact and easy to understand way of abstracting an application, especially in environments shared by designers with different backgrounds (as it is often the case of ML applications).

MODELING AND DEPLOYING A REAL-LIFE ML APPLICATION ON THE EDGE-TO-CLOUD CONTINUUM

In this section we illustrate the use of MDSC to model an ML-based Earthquake Early Warning system.

4.1 DMSEEW: An Algorithm for Distributed ML-Based Earthquake Early Warning Earthquake Early Warning (EEW) systems provide earthquake alerts before the shaking damage of a seismic event reaches sensitive areas, giving governments and communities a time window of seconds to minutes to take protective actions. Traditionally, EEW is executed in a fully centralized fashion with data from sensors being sent to Clouds.

In a previous work [START_REF] Fauvel | A Distributed Multi-Sensor Machine Learning Approach to Earthquake Early Warning[END_REF], we proposed moving part of the sensor data processing towards the Edge to speed-up detection while further enhancing network usage reduction, fault tolerance, and idle machines usage. The Distributed Multi-Sensor Earthquake Early Warning (DMSEEW) takes sensor-level class predictions (normal activity, medium earthquake or large earthquake) based on the data gathered by each sensor, aggregates them using a bag-of-words representation, and use it to predict the final earthquake category. A high-level illustration of DMSEEW and its important processing steps are presented in Figure 1.

Modeling the DMSEEW Hierarchical Processing

By-sensor classification To perform the by-sensor classification, it is necessary to gather measurements streamed by each sensor and apply the WEASEL+MUSE [START_REF] Schäfer | Multivariate Time Series Classification with WEASEL+MUSE[END_REF] classifier on those data. To gather and process the data without interrupting the stream, we use sliding windows configured to hold and then process 30 seconds of data every 1 second. The processing performed at the moment that the window data is evaluated can be summarized as sorting the data points and running the WEASEL+MUSE classifier on the resulting time-series. Hence, each sensor produces a stream of seismic measurements which is processed and transformed into a stream of predictions. By-region prediction Sensors are organized into regions, with the objective of predicting the magnitude of eventual seismic events in each of those regions. As sensors generate streams of by-sensor predictions, it is necessary to filter those streams by region, then, for each stream containing only predictions of a given region, to predict the final event category. For doing that, we use 1-second tumbling windows (i.e., processing abstractions that store the last 1 second of data before processing it) to gather predictions from a given region and we calculate the final prediction using the 1NN classifier on a normalized frequency vector of predictions.

Deploying DMSEEW on the Edge-to-Cloud Continuum

MDSC EEW is a model of DMSEEW mapped on the hybrid infrastructure, based on MDSC (Figure 2). In summary, it uses 4 layers: (i) Edge, where the data are produced; (ii) Fog, where data are pre-processed (by-sensor classification); (iii) Cloud, where the partially processed data are gathered and finally processed (by-region prediction); and (iv) Bus, connecting the above layers.

The Edge layer holds seismic sensors which act as processing units, grouped by region. Their only processing capability is sending the data to a predefined gateway server, located in the Fog. Each group within the Edge layer has one bus which models the LAN that connects all sensors isolated from the outside world and forwards sensor data to other networks. Note that in this example we consider 50 sensing regions; for each region we define a separate group of 20 processing units inside the Edge layer.

The Fog layer is essentially composed of gateway machines. They aggregate data coming from a set of sensors in the Edge and process them. For each of the 50 sensing regions we consider one fog-level gateway with an MQTT server, which ingests data coming from the sensors, and a Java program, that pulls data from the MQTT server, processes them and sends the results to the Cloud. Hence, we model every MQTT server as a helper unit and every Java program as a processing unit. Furthermore, processing units have access to different libraries such as Java JDK, Eclipse Paho, and WEASEL+MUSE. They describe the by-sensor classification step as user-defined logic and use connectors to the MQTT servers and to the Kafka cluster.

The Cloud layer is mainly composed of an Apache Kafka cluster, an Apache Zookeeper server, modeled as helper units, and an Apache Flink cluster, whose Task Managers are modeled as processing units. Apache Kafka brokers ingest the data, Apache Zookeeper manages Kafka metadata, and Flink processes the data pulled from Kafka and pushes the results back to Kafka. processing units rely on many libraries to process the data, such as Java SDK, the Flink API, and the ML library LIBSVM [START_REF]LIBSVM -A Library for Support Vector Machines[END_REF]. These libraries are used by the userdefined logic component implementing the by-region prediction step (cf. Section 4.2).

Buses model the intra-and inter-processing layers communication. Each Edge-level group of processing units has its own LAN and can communicate with the corresponding Fog-level helper unit through high speed region LANs. The Fog layer communicates with the Cloud layer using Internet or a dedicated network.

EVALUATION METHODOLOGY

To illustrate the versatility of the MDSC modeling, we used it to enable a comparative performance analysis of the Edge-based implementation of DMSEEW with various cloud-only implementations. The goal of this evaluation is to show that: a) MDSC is able to gracefully scale up to thousands of sensors and tens of processing nodes; b) MDSC isolates performance bottlenecks at various levels, from application to infrastructure; c) MDSC is able to identify trade-offs between Edge-to-Cloud and Cloud-only deployments;

Baselines

The default Edge-to-Cloud MDSC implementation of EEW, using the WEASEL+MUSE predictor, is further denoted as WME and will be compared to three different baselines: WEASEL+MUSE EEW Cloud-only (WME-CO), Random EEW (RE), and Random EEW Cloudonly (RE-CO). They are all based on MDSC but differ in the layer where the by-sensor data processing is performed and the prediction library used for that purpose, as shown in Figure 3.

WME-CO

The by-sensor data processing step is performed on the Cloud, i.e., the Fog machines only forward the data produced by the sensors to the Cloud. The prediction library used is the same as MDSC, i.e., WEASEL+MUSE.

RE The by-sensor data processing is performed on the Fog, as in MDSC, using an integer pseudo-random generator as predictor. This baseline acts as a lower bound for Edge computing scenarios, since, in practice, there is no processing done for calculating the predictions.

RE-CO

The by-sensor data processing is performed uniquely on the Cloud and the by-sensor and the by-region predictions are calculated using an integer pseudo-random generator. This baseline acts as a lower bound for Cloud-only scenarios.

Fog Cloud

RE-CO

WME-CO

Edge

Data Source

Cyber-Infrastructure

We implemented the architecture described in Section 3 and deployed it on the gros cluster from the Grid'5000 experimental test bed [START_REF] Desprez | Adding Virtualization Capabilities to the Grid'5000 Testbed[END_REF]. We rely on the prototype of an experimental platform [START_REF] Daniel | E2Clab: Exploring the Computing Continuum through Repeatable, Replicable and Reproducible Edge-to-Cloud Experiments[END_REF][START_REF] Silva | Towards a Methodology for Benchmarking Edge Processing Frameworks[END_REF] able to set up the environment, execute the experiments and gather metrics and results. This platform was designed based on a methodology ensuring the repeatability of the experiments, so that the comparison of MDSC with the baselines remains fair. In absolute numbers, the resulting distributed EEW system has 1: Fog-to-Cloud network configurations used for the evaluation of MDSC EEW 1,000 sensors emulated by virtual machines deployed on 25 host machines. Each set of 20 sensors composes an Edge layer and it is connected to one of the 50 implemented Fog layers. All Fog layers communicate and transfer their data to one Cloud layer containing a 5-machine Apache Kafka cluster, a 5-machine Apache Flink cluster and one Apache Zookeeper server. We describe in detail in Table 1 the values of bandwidth, minimum latency and jitter for each type of network configuration.

The end-to-end latency measures in milliseconds the time elapsed between the production of an event by a sensor and the prediction of the corresponding seismic event on the Cloud. This metric contains the by-sensor window processing time (maximum of 30s plus the classifier execution time) and the by-region window processing time (maximum of 1s plus the processing time). It also contains Edge-to-Fog and Fog-to-Cloud transfer times.

Datasets

Initially, our objective was to use real seismic data1 from the American Incorporated Research Institutions for Seismology (IRIS) [START_REF]Incorporated Research Institutions for Seismology[END_REF], as in [START_REF] Fauvel | A Distributed Multi-Sensor Machine Learning Approach to Earthquake Early Warning[END_REF]. Nevertheless, with its size of 58MB from 897,060 data points, it is not large enough for stressing the infrastructure of the scenarios proposed in this work. Hence, we artificially generate data using the IRIS format. We generate 12,000 messages for each of the 1,000 sensors distributed in 50 regions with a frequency of 100Hz. Hence, each sensor produces 100 messages per second for 2 minutes (resulting in a total of 12,000,000 messages to be processed).

EVALUATION RESULTS

We first assess the performance of the lower bound RE and RE-CO baselines. Then, we compare the WME and WME-CO scenarios, highlighting issues related to network and library constraints.

Random EEW: Lower Bounds

We start by presenting the performance of RE and RE-CO, the lower bound scenarios that are used as a basis of comparison to the other scenarios throughout this section. The main characteristic of those scenarios is that predictions are calculated through the generation of pseudo-random integers whenever the processing windows are ready to be evaluated. Due to that, the main performance bottleneck of this scenario is the network, as observed in Figure 4.

The behavior of RE experiments is very similar because, in Edge computing scenarios, messages are aggregated in the Fog and only the predictions are sent to the Cloud, generating less data load on the network. Consequently, even on network constrained scenarios, the latencies only vary between 30 and 45 seconds. The difference between the amount of data transferred from the Fog to the Cloud is illustrated in Table 2. There are more than 13 times less data being sent to the Cloud compared to RE-CO scenarios.

On RE-CO experiments, the impact of network constraints is shown by the translation of the latency curves as the network characteristic changes. Observe that the RE-CO 10Gb scenario has better latency than the Edge scenarios, showing that, when the network is not constrained, processing everything on the Cloud can be a better option in terms of latency.

MDSC EEW: Performance Overview

We can now discuss the performance of WME (the vanilla MDSC implementation of EEW on Edge-to-Cloud) using WME-CO, RE and RE-CO as baselines. We show that despite the amount of computing resources available, the latency of WME is directly affected by the choice of the classification library used in DMSEEW. The extent of the performance degradation caused by that library is further discussed using the results of WME-CO.

We illustrate the WME and WME-CO scenarios in Figure 5. The main observation from this chart is the gap between the latencies of the WME and WME-CO experiments. While WME's latencies vary between 40 and 50 seconds, 90% of WME-CO latencies are above 100 seconds.

Starting with WME-CO, we observe very high latencies even for 10Gb scenarios. While the lower bound performance (cf. Figure 4) indicated that 10Gb scenarios provide better latencies than Edge computing ones, in Figure 5 that scenario has latencies close to 400 seconds. We identify, however, a similar behavior of IE compared to the lower bound RE, but with slightly higher latencies, varying between 32s and 50s.

The behavior of WME-CO observed in Figure 5 can be explained by the existence of two bottlenecks: the network, in 2G and 3G scenarios, as discussed in Section 6.1, and the interaction between WEASEL+MUSE, the ML library used for predicting the sensorwise magnitudes of events, and Apache Flink. The implementation of WEASEL+MUSE [START_REF] Schäfer | Last accessed on[END_REF] is a prototype, hence, it is not optimized in terms of execution time complexity, and it is not thread-safe. Because of the latter, it is not possible to share the same instance of the model among processing window instances running in the same Flink Task Manager. Since there will be one new open window per sensor every 1 second and for 30 seconds, that procedure demands more memory than the available one on each Task Manager, slowing down the data processing due to garbage collection and swapping.

RELATED WORK

A rich set of tools, libraries and frameworks are currently proposed at the intersection of Edge computing and ML. In this section, we provide an overview of the state of the art of the efforts from the converging communities of Big Data and Artificial Intelligence at the network edge.

Stream processing with ML libraries. In the Big Data community, the baseline approach for ML tasks like prediction and classification is to periodically transfer all the raw data from the Edge to the Cloud. Back-end stream processing frameworks like Apache Spark [START_REF] Zaharia | Apache Spark: A Unified Engine for Big Data Processing[END_REF] and Apache Flink [START_REF] Carbone | Apache Flink: Stream and Batch Processing in a Single Engine[END_REF] perform advanced analytics once the data is collected. They are supported by rich dedicated libraries like MLlib [START_REF] Meng | MLlib: Machine Learning in Apache Spark[END_REF] and FlinkML [START_REF]Apache FlinkML[END_REF] respectively. These frameworks are greedy in terms of resources and cannot be executed on Edge nodes per se. Instead, some dedicated systems such as Azure IoT Edge [START_REF]AI Toolkit for Azure IoT Edge[END_REF], and the AWS IoT Greengrass [START_REF]AWS IoT Greengrass[END_REF] can be used to offload the ML computations on the Edge nodes.

ML at the Edge. Several studies [START_REF] Chen | Deep Learning With Edge Computing: A Review[END_REF][START_REF] Sarwar Murshed | Machine Learning at the Network Edge: A Survey[END_REF] identified the main vectors driving a shift towards using resources at the Edge of the network, near the data sources, building what is called the Edge intelligence [START_REF] Wang | Convergence of Edge Computing and Deep Learning: A Comprehensive Survey[END_REF]: ML training and ML inference at the Edge.

Fast inference was initially achieved on single Edge devices. Instead of transmitting raw contextual data in the network, [START_REF] Portelli | Leveraging Edge Computing through Collaborative Machine Learning[END_REF] only transmits the inferred knowledge using incremental ML on the Edge nodes. DeepDecision [START_REF] Ran | DeepDecision: A Mobile Deep Learning Framework for Edge Video Analytics[END_REF] and MCDNN [START_REF] Han | MCDNN: An Approximation-Based Execution Framework for Deep Stream Processing Under Resource Constraints[END_REF] take the offloading decision based on constraints such as the size of input data, the model to be executed, the tradeoffs between the inference accuracy, network latency and bandwidth. Most of these approaches are application specific. When applied to different contexts, the overhead of the adaptation increases the inference latency particularly on high-dimensional input data and on mobile devices [START_REF] Sarwar Murshed | Machine Learning at the Network Edge: A Survey[END_REF].

Edge-enhanced architectures Distributed deep learning has motivated the use of computing hierarchies by splitting neural network [START_REF] Teerapittayanon | Distributed DNN over the Cloud, the Edge and End Devices[END_REF] or using sparse updates [START_REF] Tao | eSGD: Communication Efficient Distributed Deep Learning on the Edge[END_REF] to aggressively reduce communication costs. However, these works are either not resilient/sensitive to topology changes [START_REF] Wen | ApproxIoT: Approximate Analytics for Edge Computing[END_REF] or rely on unsuitable resource management for service delivery [START_REF] Hyunseok | Bringing the cloud to the edge[END_REF]. Previous work from authors have explored Edge-enhanced infrastructures for Urgent Science and large-scale application [START_REF] Balouek-Thomert | Harnessing the Computing Continuum for Urgent Science[END_REF].

Conclusion Different from these works, our architecture for ML executions on the Continuum: (i) is general enough to be adapted to any application, in any context, without loss of efficiency, and (ii) holistically considers the deployment issues of ML on Edge/Cloud nodes (i.e., communication and computation constraints).

CONCLUSION AND FUTURE WORK

In this paper we present MDSC, an approach for modeling distributed stream-based applications on Edge-to-Cloud continuum infrastructures. It uses interconnected layers and units to model the core components of an application, such as libraries, data processing and management tools. We illustrate the versatility of MDSC by modeling of a complex real-life ML application, that was deployed on an Edge-to-Cloud infrastructure emulated atop Grid'5000.

As future work, we are looking into developing the description of the helper units to reflect their internal configuration and libraries, which can have an impact on the application performance. Another interesting research direction is the design of scheduling algorithms that help designers decide where to deploy processing units on the different available layers of a hybrid infrastructure.

2

 2

Figure 1 :

 1 Figure 1: Earthquake Early Warning use-case (DMSEEW).

REFigure 3 :

 3 Figure 3: Baselines summary according to the layers used for by-sensor and by-region processing.

  Distributed Stream Processing across the Edge-to-Cloud Continuum Woodstock '18, June 03-05, 2018, Woodstock, NY 2G (0.3Mb/s), Edge 2G (0.3Mb/s), Cloud-only 3G (2Mb/s), Edge 3G (2Mb/s), Cloud-only 10Gb (10Gb/s), Edge 10Gb (10Gb/s),

Figure 4 :

 4 Figure 4: Latency resulting from processing one seismic event on lower bound scenarios RE and RE-CO.

Figure 5 :

 5 Figure 5: Latency resulting from processing one seismic event on WME and WME-CO scenarios.

Table 2 :

 2 Amount of messages transferred between Fog and Cloud on different network configurations for WME and WME-CO experiments. The same behavior is observed on RE and RE-CO experiments.

	WME-2G/3G/10Gb WME-CO-3G WME-CO-2G WME-CO-10GB
	9,100	1,647,126	11,695,871	12,000,000

https://figshare.com/articles/EarthquakeEarlyWarningDataset/9758555


Masoud Taghavian

Yassine Hadjadj-Aoul

Géraldine Texier

Philippe Bertin

An Approach to Network Service Placement using Intelligent Search Strategies over Branch-and-Bound

Keywords: Network function virtualization, branch and bound, artificial intelligence, a-star

Network Function Virtualization (NFV) has been a significant shift from traditional dedicated hardware devices towards reusable software modules running over lightweight virtualized environments. While it brings many promising opportunities, it introduces several unprecedented complexities that need further considerations. Efficient placement of services is essential for achieving NFV expectations. We propose a highly reliable solution for systematically placing network services, touching the optimal results while maintaining the scalability, making it suitable for online scenarios with strict time constraints. We organized our solution as a Branch and Bound search structure, which leverages Artificial Intelligence (AI) search strategies (Especially A-Star) to address the placement problem, following the popular objective of Service Acceptance (SA). Extensive empirical analysis has been carried out and the results confirm a significant improvements.

I. Introduction

The need for increasingly flexible networks with the ability to instantly integrate new services has led network operators to adopt Network Function Virtualisation (NFV) and Software-Defined Networking (SDN) in 5G networks. By separating the control and data planes, SDN enables networks to be managed centrally and intelligently, using software applications. Meanwhile, NFV uses the cloud computing technologies to virtualize the entire classes of network functions, connecting and chaining them together to realise services. Service Chain Description (SC-D), Service Chain Composition (SC-C), Virtual Network Function-Forwarding Graph Placement (VNF-P) and VNF Scheduling (VNF-S) are the four stages of Service Function Chaining (SFC) [START_REF] Mirjalily | Optimal network function virtualization and service function chaining: A survey[END_REF].

To satisfy the expectations of NFV, sophisticated algorithms are required to allocate the physical resources in an optimal way, within a fair time constraint. Resources are allocated by determining the suitable placements of the service requests over the Substrate Network (SN). The placement problem is classified as an NP-Hard problem in terms of complexity, i.e., it is a generalization of the Virtual Network Embedding (VNE) problem which has already been proven to be NP-Hard [START_REF] Fischer | Virtual network embedding: A survey[END_REF], [START_REF] Mijumbi | Network function virtualization: State-of-theart and research challenges[END_REF].

A considerable part of the literature on the placement problem is dedicated to the exact resolution of the problem, which is generally formulated as an Integer Linear Programming (ILP) [START_REF] Bari | Orchestrating virtualized network functions[END_REF], [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF]. Although they are powerful and optimal, they suffer from scalability and exponential time complexity. Using Meta-Heuristics is another approach to address the problem [START_REF] Khoshkholghi | Optimized service chain placement using genetic algorithm[END_REF], [START_REF] Pham | Virtual network functionforwarding graph embedding: A genetic algorithm approach[END_REF]. In spite of being effective, they can suffer from convergence problems and unpredictability. Besides, they imply a search over the whole solution space, which is a waste of time considering the large number of constraints inherent to the problem (related to nodes, links, Quality of Service (QoS), different objectives, etc.), and it makes a huge proportion of the solutions infeasible. Meanwhile, using Artificial Intelligence (AI) and Machine Learning (ML) techniques for the placement problem is quite recent but highly promising. [START_REF] Manias | Depthoptimized delay-aware tree (do-dat) for virtual network function placement[END_REF], [START_REF] Wahab | Maple: A machine learning approach for efficient placement and adjustment of virtual network functions[END_REF] apply ML and [START_REF] Fu | Dynamic service function chain embedding for nfv-enabled iot: A deep reinforcement learning approach[END_REF], [START_REF] Pei | Optimal vnf placement via deep reinforcement learning in sdn/nfv-enabled networks[END_REF], [START_REF] Quang | A deep reinforcement learning approach for vnf forwarding graph embedding[END_REF], [START_REF] Sun | A q-learning-based approach for deploying dynamic service function chains[END_REF] propose solutions in Deep Reinforcement Learning (DRL) and Q-Learning for the placement problem. Most of the works in this category, until recently, use greedy heuristic search. Despite of being super fast, they are not optimal, and the risk of getting stuck in local optimums is extremely high.

In this paper, we address the placement problem, proposing a fast reliable solution for systematically placing network services based on a Branch and Bound (BB) method, which allows us to give different AI search strategies (especially A*) the opportunity to develop in this field of study. We will see how to touch theoretically proved optimal results (The distinguishing advantage of ILP-based methods), while maintaining the scalability of a heuristic-grade placement strategy. It is suitable for on-line scenarios that we need to conform to a time constraint. We adopted the popular objective of Service Acceptance (SA), which distinguishes the strategies based on the number of successfully placed services.

It is worth mentioning some of the motivations driving our approach. BB approach caught our attention for several reasons. First, we have a large number of different types of constraints in this problem, which are leveraged by BB in a beneficial way (the more constraints we have, the more we can prune the tree and limit the branches, leading to faster search procedure). Another advantage of BB is the guarantee of not producing infeasible placements in any circumstance. It systematically respects all of the constraints as the search advances and avoids to progress in non-promising constraints-violating areas. It is suitable when we need to result a good-enough solution as fast as possible and to be able to improve it as we give it more time. That is why we think BB is a good choice for online placements. It also has an intrinsic potential of making use of parallel execution.

In the following, after formal specification of basic constraints, we investigate the source of the complexity, and propose our approach. We conclude with our meticulous evaluations to assure the effectiveness of our method.

II. The placement model

The placement consists in finding a pair of mappings of the VNFs and the Virtual Links (VLs) of a service into the nodes and the paths (sequence of links) of a SN. These mappings specify for each VNF the serving node, and for each VL data flow the sequences of links over which it is conducted. A Service Graph (SG) is denoted by a directed graph, composed of VNFs, connected via VLs, accompanied with a Service Level Agreement (SLA), reflecting the acceptable QoS requirements. The SN is the physical network represented by a directed graph with its corresponding topology, the available resources related to nodes and links, as well as QoS metrics associated with the links (e.g., Latency, Loss, etc.). We are interested in online placement of services, so, we place a service as soon as it arrives [START_REF] Mirjalily | Optimal network function virtualization and service function chaining: A survey[END_REF]. We use Z-notation [START_REF] Spivey | The Z notation[END_REF] to make a formal specification of the basic constraints of the placement. Table I introduces the sets and functions, utilised in the specifications of the constraints. Note that the primitive types like sets, relations, functions and sequences as well as several operators like dom and ran (domain and range of a function) are already specified mathematically in Znotation. A VL is placed over a path which is a sequence of distinct links [START_REF] Bari | Orchestrating virtualized network functions[END_REF], chained together [START_REF] Fischer | Virtual network embedding: A survey[END_REF], in order to connect two nodes of the SN. In order to avoid loops, we add (3). We consider available amounts for different types of resources for a path, similar to a link, which is defined as the subsection or minimum of the available amounts for different types of resources of the paths links [START_REF] Khoshkholghi | Optimized service chain placement using genetic algorithm[END_REF].

∀p ∈ P | p = seq L ∀i, j ∈ Z | i, j < #p ∧ i = j ⇒ p(i) = p(j)
(1)

S(p(0)) = S(p) ∧ D(p(#p -1)) = D(p) ∧ S(p(i)) = D(p(i -1)) (2)
S(p) = D(p) ∧ S(p(i)) = S(p(j)) (3) A(p, t) = n ∩ i=1 A(p(i), t) , ∀t ∈ ∆ (4)
The available amount of resources of a node must be adequate to provide the amount of resources required by

N -1 ∈ PPE). To clarify N -1 (l) = {∀e ∈ E, ∀p ∈ P | e → p ∈ N ∧ l ∈ ran p • e}
all the VNFs of a SG that have been placed on that node [START_REF] Luizelli | Piecing together the nfv provisioning puzzle: Efficient placement and chaining of virtual network functions[END_REF]. Similarly, the available amount of resources of a link must satisfy the amount of resources needed by all of the paths placed on that link [START_REF] Manias | Depthoptimized delay-aware tree (do-dat) for virtual network function placement[END_REF]. The placement is complete, when all of the VNFs and VLs of the SG are placed, i.e., the domain of the M and N functions are equal to the V and E sets respectively (dom

M = V ∧ dom N = E). ∑ v ∈M -1 (n) R(v, t) ≤ A(n, t) , ∀n ∈ N, ∀t ∈ ∇ (5) ∑ e ∈N -1 (l) R(e, t) ≤ A(l, t) , ∀l ∈ L, ∀t ∈ ∆ (6)
III. Proposed solution A. Branch-and-Bound-Based Service Graph Placement 1) Branch and Bound: BB is generally used for solving combinatorial optimization problems that are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. BB partitions the total set of feasible solutions into smaller subsets and systematically avoids non-promising branches of the tree by pruning. Our proposed BB approach is organized as a tree search (figure 1). Here, we use the the term state, to refer to the nodes of the search tree, to better differentiate the nodes of SN and search tree. Each state includes a status of the SN (capturing remaining

Complete placements (terminal states)

Pruning the branches that violate constraints resources of every single nodes and links). It inherits a list of unplaced VNFs and VLs from its parent state, and it carries a partial placement for a subset of VNFs and VLs of a SG. A terminal state is reached when the placement is finished (i.e., all of the VNFs and VLs of a SG are placed successfully without violating any constraints). A search strategy defines a specific traversal (the order of visiting the states of the tree). This traversal is performed with the help of an ordered list of states, which is called fringe. Fringe can be a basic queue (e.g., in Breadth-First Search (BFS)) or a stack (e.g., in Depth-First Search (DFS)) or a priority queue (e.g., in A*).

At the beginning, we create a sorted list of VNFs from the requested SG. The order of the list of VNFs of a SG is determined by traversing the SG in BFS order, starting from the entry point (BFS traversal ensures that our partial placements are connected-subgraphs of the SG, which can be verified against constraint violations). Next, the search starts from the root of the tree by placing the head of the list (the entry point of the SG). We start by instantiating the root state and putting it into the fringe. Then, we enter a search loop. At each iteration, we pop a state from the fringe and check whether it is a terminal state or not. If it is a terminal state, the search terminates. Otherwise, the state is expanded by taking another VNF from the list of VNFs and placing it over each of the SN node. As we place the VNFs, we place a subset of unplaced VLs that now get the chance to be placed into the SN, due to the latest VNF placement (a VL can be placed into SN if its source and destination VNFs are already placed). The expansion results in a list of child states, which are candidate placements of a specific VNF over different SN nodes. The children which does not violate any constraints are added into the fringe to be expanded later. The others are pruned and do not appear later. The search continues until it finds a terminal state and succeeds or reaches a timeout and fails. The depth of the tree is equal to the number of VNFs of the SG, and the branching factor is equal to the number of nodes of the SN.

2) Objectives: To distinguish between different feasible placements of a specific SG over a SN, we need a criteria or an objective. Several objectives are studied in the literature. They can be divided mainly into two categories. The first category belongs to resource-based objectives. They minimize the usage of a particular resource type or a combination of them (regarded as multi-objective). The other category includes objectives that evaluate the overall behavior of the placement strategy and is not necessarily related to specific resource types. Cost of Revenue, Energy Consumption and Service Acceptance (SA) are some of the well-studied objectives in this category [START_REF] Mirjalily | Optimal network function virtualization and service function chaining: A survey[END_REF]. This second category is commonly preferred in the literature, and we are interested in SA, which is defined as the number of services that can be placed successfully over the SN. The objective of SA can be considered as a practical generalization of a resource-based multi-objective strategies.

3) Constraints: We consider CPU and storage as the node resources, bandwidth as the link resource, as well as link latency and end-to-end delay as QoS metrics for the links and the services. Our solution does not impose any limitation for adding more resource types or more QoS metrics for nodes, links or services.

4) A*: A* is among the most popular Artificial Intelligence (AI) Informed Search algorithms that allows traversing the search tree according to f -costs, which are calculated by f (n) = g(n) + h(n) for an arbitrary state of n [START_REF] Russell | Artificial intelligence: a modern approach[END_REF], where f is an estimation of the cost of an optimal solution from the root to a target state, the heuristic function h estimates the cost of an optimal solution from the current state to a target state, and g is a real cost of path from the root to the current state. A* search is proved to be optimal and complete if we choose a heuristic function that is admissible and consistent [START_REF] Russell | Artificial intelligence: a modern approach[END_REF].

B. Search Strategies

We study the influence of five strategies: A* Bandwidth Optimized (ABO), DFS Bandwidth Optimized (DBO), A* and DFS combined Bandwidth Optimized (ADBO), Enhanced Decreasing First-Fit (DFF) (EDFF) and Enhanced Increasing First-Fit (IFF) (EIFF). While EDFF and EIFF concentrate on node-resources, ABO, DBO and ADBO focus on link-resources (i.e., bandwidth). Our ultimate goal is to see how different resource types affect the number of SG that can be accepted. All of the placement candidates of a SG over a SN will eventually use the same amount of SN node-resources, which is equal to the sum of the required resources by its VNFs. Yet, in terms of linkresources, various placement candidates use quite different amount of resources.

1) A* Bandwidth Optimized (ABO): In ABO, we use A* in order to perform a complete and optimal search as fast as possible. Here, the cost is defined as the amount of bandwidth used by the placement. In this case, the fringe is a priority queue. It sorts the states based on f -costs and the head of the queue belongs to the state with minimum f -cost. As a recall, we want to place a SG over the SN optimizing the bandwidth usage. An optimistic heuristic to estimate the cost of placement would be the cost of placing each unplaced VL over a single SN link instead of a path of several links. Therefore, we consider the total amount of required bandwidth by all of the unplaced VLs as h, and g is the total amount of used bandwidth for all of the placed VLs. Our heuristic is optimistic since it never overestimates the cost to the target state. We need at least one SN link to accommodate each VL. If we cannot place source and destination of a VL over two adjacent SN node, i.e., if we need a path of links to accommodate a VL, the cost would be more what our heuristic had estimated, thus, our heuristic is optimistic.

We can also demonstrate that our heuristic is consistent, or the f -cost would never decrease along a path. In other words, if n is a successor state of n and c is the cost of placing unplaced VLs on n that are already placed on n (i.e. c = g(n )g(n)), we need to prove the triangle inequality in 7 illustrated in figure 2.

h(n) ≤ c + h(n ) (7)
We know that the estimated cost of placement on n is less than the estimated cost on n (since, we have less unplaced VLs on n ). We label the estimated cost of transition from n to n as c . So, we have h(n ) = h(n)-c . Therefore, we just need to prove that c ≤ c. Since, we know that our heuristic do not overestimate the cost, this inequality is always true, thus, our heuristic is also consistent. Now, we can assure that our A* search is optimal as well as complete. The optimality of ABO guarantees that if it succeeds to find a placement, no other placement exists using less bandwidth than the found one.

2) DFS Bandwidth Optimized (DBO): In DBO, like ABO, we concentrate on link bandwidth and the cost is defined as the amount of bandwidth used by the placement. We traverse the tree in DFS, so, our fringe will be a stack. After expanding a state, the list of generated states is sorted according to their cost and are put into the fringe. Accordingly, since, the fringe is a stack; the next time that we will pop the fringe, we will expand the child having the lowest bandwidth usage. DBO do not necessarily guarantee optimality or completeness, but it finds a bandwidth-optimized placement faster than ABO. It makes a satisfactory compromise between optimality and speed.

3) A* and DFS combined Bandwidth Optimized (ADBO): ADBO mixes two strategies of ABO and DBO. The search starts finding a placement using ABO. If it finds a placement, the search terminates. Otherwise, if the timeout is reached and ABO could not find a placement, it means that satisfying optimality by ABO would cost us an extra time which is limited in an online-placement. At this point, we give DBO a chance to find a near optimal placement. Since, ADBO uses two strategies sequentially, in order to make a fair evaluation of ADBO along with other strategies, we need to share the given timeout between two strategies (we simply halve the timeout and share it between the two strategies).

4) Enhanced DFF (EDFF) and Enhanced IFF (EIFF): DFF and IFF are two well-known heuristics for service placement. DFF (aka Best-Fit) sorts the nodes and places the VNF over the node with the maximum amount of available resources that is adequate to accommodate it. IFF is like DFF but it places the VNF over the node with the minimum amount of available resources. The placement fails to place a service as soon as it does not find any candidate to accommodate a VNF of that SG. We thought how to give these strategies another chance to revise the previously placed VNFs to see how far we can benefit from these heuristics. One of the advantages of BB structure of the search is that it makes it possible to put simply into practice our intuition. By a small tweak in DBO, we can obtain an enhanced version of DFF and IFF heuristics. By sorting the generated children of a state by their amount of available resources instead of their bandwidth usage, we can have EDFF and EIFF (according to whether the sort is ascending or descending). This enhancement allows us to profit from these strategies as much as possible. The evaluations show that EDFF and EIFF can place on average nearly 3-times more SGs than the original ones.

IV. Experimentations

Typically, there are two general approaches to evaluations in the literature. The first one is based on random initialization of the inputs of the evaluation. Reliability and reproducibility is assured by repeating the evaluations with different seeds of randomness. Monte Carlo is a powerful technique, used in this category. Another approach guarantees reliability and reproducibility systematically, also it allows to track the evolution of the results. This is achieved by considering the entire acceptable range of the inputs. In general, although the second approach is more accurate, it is not always feasible, regarding the number of inputs and their wide acceptable range. A practical approximation which facilitates to follow the second approach is dividing the acceptable range into a handful of values. For the reasons of reliability, we follow the second approach. Throughout this section, we choose the parameters for presenting the results by considering the page limitations and results' similarities for different types and parameters (it is only a brief presentation of a complete investigation on the sheer size of the results).

A. Assumptions

In order to evaluate our search strategies, we necessarily need to consider some assumptions in order to make our evaluations reliable, correct and reproducible (i.e., it is not required to consider these assumptions for the real scenarios; we only need these assumptions in order to make a concentrated and realistic evaluation of our methods). Our assumptions include:

1) No constraints for QoS metrics: We do not consider constraints on QoS metrics in our evaluations. The violations of QoS metrics are systematically detected and taken care in BB search structure. Here, we concentrate on the resources rather than QoS metrics.

2) No constraints for node resources: We performed an interesting evaluation, to reveal the effect of limiting node resources in order to distinguish several placement strategies. We noticed that, by considering low amount of resources for the nodes of the SN, all of our placement strategies act exactly likewise, and each strategy places the same number of services. By increasing this limitation, the effectiveness of different strategies becomes more and more clear. Therefore, limiting node resources at any point, only leads to poor evaluation of the strategies. The results of this evaluation are shown in the Fig. 3.

3) Placing each VNF of a SG in separate SN nodes: We respect the constraint of not placing any two VNFs of a SG over a single SN node on our evaluations. We performed an experiment without this constraint and noticed that the placement problem becomes so simple and relaxed that evaluating different strategies becomes senseless. As it is shown in the Fig. 4, the strategies try to save the resources by placing as many VNFs as possible over a single node in order to minimize bandwidth usage and it continues as long as there is enough node resources left. Additionally, in the production, this constraint is essential in order to satisfy the availability of the services (at least for the services requiring certain degree of availability). By considering redundancy in the service-level and placing the VNFs on separate nodes, we ensure that a node failure would not violate the availability of the services.

B. Parameters and Structure of Evaluations

Our evaluations are executed on a system with Intel Core i7-3687 CPU and 8GB of RAM. The implementations are made in Java, running on Windows 10 OS. All of the evaluations are executed in a single thread. Apparently, their performance could be improved dramatically, regarding parallel execution capability of our strategies. We respect a timeout of 2000 ms in all of our evaluations (i.e., if a strategy could not find a placement within the timeout, it fails). We perform our evaluations over 3 types of SN topologies, which are selected from the dataset of Zoo Topology, named by BT-Europe, BT-Asia-Pacific and BT-North-America with 24, 20 and 36 number of nodes and 74, 62, 152 number of bi-directional links, respectively. We tried three types of topology for SGs (Daisy chain, Ring and Star) with the size of 3 to 8 VNFs and bidirectional VLs. Each VNF requires a single unit of CPU and a single unit of storage and each VL requires a range of bandwidth units from 1 to 10. Each SN node has unlimited resources of CPU and storage and each SN link has 10 units of bandwidth at the beginning of the evaluation. To place a VL over a path in SN, we use Dijkstra's shortest path over hop-count as our routing algorithm for evaluations. Apparently, using sophisticated routing algorithms like SAMCRA [START_REF] Van Mieghem | Concepts of exact qos routing algorithms[END_REF], which can take QoS metrics into consideration, are preferable for production, but since we concentrate on resources rather that QoS metrics, and we use the routing only for comparing different placement strategies, we tried to choose a basic deterministic routing algorithm. Our evaluations are performed by initializing the entire SN nodes and links with the maximum available resources, then entering a loop. On each iteration, a SG is created based on a topology, size, amount of required resources of VNFs and VLs. Then, we try to place this SG over the SN using a strategy within a time limit. If the strategy succeeded to find a placement, then the placement is applied to the SN by updating the remaining resources then we start a new iteration. Otherwise, we terminate the evaluation and report the number of SGs that we have been able to place.

C. DFF and IFF vs. Their Enhanced Versions

D. The Idea Behind ADBO

Table II demonstrates the number of placed SGs as well as the percent of the total remained bandwidth on SN at the end of the placement for ABO, DBO and ADBO strategies. We place different sizes of SGs of daisy chain topology (each VNF requiring 1 unit of cpu and storage and each VL, 1 unit of bandwidth) over BT-Europe network. It is highly satisfactory that by placing SGs with 6 VNFs, ABO can place more SGs than DBO (60 vs. 57), besides, leaving more remaining bandwidth for SN (18.92% vs 12.97%). But, regarding the placement of SGs with 8 VNFs, although ABO can leave a valuable amount of SN bandwidth untouched (43.24% vs 7.03%), it places lower number of SGs (30 vs 38), i.e., time is sacrificed over optimality. Considering the entire results of evaluations, we came to this idea that we can benefit from combining ABO and DBO, introducing ADBO which shares the timeout between ABO and DBO and executes DBO after ABO consecutively.

E. Service Acceptance

Comprehensive evaluations has been carried out. We performed 900 evaluations for each SN type, considering different types and parameters. By having 3 types of SN, it makes 2700 evaluations altogether. It is observed that ADBO is almost always superior to other strategies, making us able to measure other strategies compared to ADBO (Table III). We utilize quartiles (Q1, Q2 (Median), Q3) as well as min-avg-max, in order to better represent the results. Note that, an improvement of 400% means that ADBO could place 5 times more SGs having the same evaluation parameters in comparison to the related strategy. Beyond this satisfactory results in terms of average, it is quite rewarding to witness that ADBO could place 24 to 35 times more SGs (regarding max in the figure), when the placement problem becomes so complicated that DBO, EDFF and EIFF could not find any placement or they could only find 1 or 2.

F. Execution Time and Complexity

Each strategy places SGs as long as it succeeds in accepting them. The placements fail and are terminated when no solution is possible or when the time limit elapses. Except the last placement, which fails within the timeout, others are executed in a relatively short time. Although, it depends on the size of the SG and SN, on average, ADBO, ABO, DBO, EDFF and EIFF could place a service in 53, 52, 40, 43 and 46 ms respectively, according to our evaluations. In terms of the complexity, considering that the placement problem is NP-Hard, clearly, the complexity of our strategies is not polynomial. The complexity of a BB method heavily depends on the number of expanded states, which is determined by the traversal strategy. While, the complexity of these strategies grows exponentially, they do not grow equally (e.g., take the complexity of O(e n ) vs. O(e 0.01n ). If we remove the heuristic component of A*, we get Uniform-Cost Search (UCS). Using UCS instead of A* in ABO, gives us an intuition about the complexity. In general, an informed search strategy, if the heuristic respects the triangle inequality, in the worst case, acts better than an optimal uninformed search strategy like UCS. By evaluations, we noticed that obtaining optimal results by UCS is not even possible for more than 90% of our cases, even by giving it more time. The results witness the incomparable superiority of ABO and the effectiveness of our heuristic.

V. Conclusion

Although the VNF placement problem has been around for several years, but the need for a solution that could compromise optimality and scalability to a certain degree still exists. Formerly, the researches were mainly concentrated on ILP formulations or heuristic greedy search. They were trying whether to guarantee optimal results or to meet scalability and time constraint requirements. Recently, sophisticated AI and ML techniques have gained attention, regarding their capability to bring optimality and scalability close to each other. We proposed a solution based on a BB structure, leveraging AI search strategies, especially A*, using an admissible and consistent heuristic, which is capable of finding optimal placements, relatively fast. Sizeable empirical analysis has been performed and the results confirm a considerable improvement (429% on average) in comparison with the popular heuristic placement method of Best-Fit.

Investigating the effects of QoS metrics over the VNF placement problem, and exploring SNs with Edge/Core topologies that are short on edge network resources, are some open issues for future direction.

Figure 1 .

 1 Figure 1. A sample BB search tree, placing a SG with 3 VNFs over a SN with 4 nodes

Figure 2 .

 2 Figure 2. Illustration of triangle inequality on equation 7

Figure 5 compares

 5 Figure 5 compares DFF and IFF heuristics vs. their enhanced versions, placing different sizes of SGs of daisy chain topology (each VL requiring 1 unit of bandwidth) over BT-Europe network. As shown, this enhancement allows us to place on average nearly 3-times more SGs than the original DFF and IFF.

Figure 3 .Figure 4 .

 34 Figure 4. Illustration of being able to place multiple VNFs over a single SN node impact

Figure 5 .

 5 EDFF and EIFF vs. DFF and IFF


Anouar Rkhami

Gerardo Rubino

MonGNN: A neuroevolutionary-based solution for 5G network slices monitoring

Monitoring the status of network slices is a priority for network operators to ensure that SLAs are not violated. To overcome the limitations of direct slices' monitoring, network tomography (NT) is seen as a promising solution. NT-based solutions require constraining monitoring traffic to follow specific paths, which we can achieve by using segment-based routing (SR). This allows deploying customized probing scheme, such as cycles' probing. A major challenge with SR is, however, the limited length of the monitoring path. In this paper, we focus on the complexity of that task and propose MonGNN, a standalone solution based on Graph Neural Networks (GNNs) and genetic algorithms to find a trade-off between the quality of monitors' placement and the cost to achieve it. Simulation results show the efficiency of our approach compared to existing methods.

I. INTRODUCTION

By leveraging the latest advances in Network Functions Virtualization (NFV) and Software-Defined Networking (SDN), Network Slicing (NS) enables an efficient support of constrained and diverse services, in terms of Quality of Service (QoS) needs, on top of a single infrastructure. This capability is considered to be one of the most important features of 5G networks and beyond [1]. Indeed, NS opens up new business opportunities for network operators by allowing them to automatically lease customized network slices to third parties.

Despite the advantages it brings, NS poses a set of challenges. Once the slices are leased, network operators will have to ensure that the negotiated Service-Level Agreements (SLAs) with slices' tenants are not violated. As a result, monitoring the status of the slices will be a priority for them to perform troubleshooting and traffic engineering.

Several approaches in the literature focus on the problem of network monitoring, considering in particular end-to-end measurements. These approaches are generally referred to as network tomography (NT) [START_REF] He | Network Tomography[END_REF]. Some recent works focus on a specific approach of source routing for probing, where only cycles are used [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF]. The probing cycle schemes have a significant advantage compared to regular paths. Since the source probe is actually the destination, this reduces synchronization problems. Despite the flexibility offered by source routing in monitoring, this technology presents many challenges. Indeed, most commercial switches only support a limited number of SIDs in packet headers [START_REF] Guedrez | Label encoding algorithm for mpls segment routing[END_REF]. This adds a constraint on the length of the probed cycles.

The construction of an NT based solution is done through three main steps: placement of monitors, deployment of the probing strategy (paths to follow) to collect end-to end measurements and then the inference of network metrics. In this work we focus on finding the optimal number of monitors and their placement such that we cover all the slices by probing cycles of limited length. The task becomes then equivalent to the minimum set covering problem, which is known as an NP-Complete problem [START_REF] Beasley | An algorithm for set covering problem[END_REF].

Several solutions have been proposed to solve the problem of monitors' placement, that can be classified into two classes: exact and heuristics. Exact methods ensure optimality but they are applicable only on small instances. On the other hand, heuristics can be applied to large instances but they are suboptimal.

To find a trade-off between the quality of the solution and the cost to obtain it, we propose MonGNN, an autonomic solution based on Graph Neural Networks (GNN) to learn to predict the optimal number of monitors and then use genetic algorithms to reveal their identity.

The main contributions of our paper can be summarized as follows:

• We propose an Integer Linear Programming (ILP) formulation of the following problem: given a set of slices running some services, determine the optimal placement of monitors in order to cover all these slices using cycles whose length is less than a certain amount k. • We propose a learning-based approach to find a trade-off between the quality and the cost of the solution. • We unveil the potential of Graph Neural Networks to predict the optimal number of monitors. • We define a Genetic Algorithm (GA) to identify the monitors, based on the predicted value of the objective function.

• We enhance the GA by a local search method to deal with the estimation error that can occur in predicting the number of monitors. • We conduct extensive simulations and we compare our approach against benchmark solutions. The results show the superiority of our technique in terms of optimality gap as well as computational complexity.

The remainder of this paper is organized as follows. We introduce background information in Sec. II. Sec. III presents the main related work on network tomography. In Sec. IV, we provide an overview of the context of the paper and the notation we have used as well a formal definition of the problem we aim to solve. Then, in Sec. V, we delve into the details of our proposed solution. In Sec. VI, we describe both the simulation setup and the results analysis. Finally, in Sec. VII, we conclude and give an overview of our future work.

II. BACKGROUND

A. Graph Neural Networks (GNN)

Graph Neural Networks (GNNs), are a type of neural networks dedicated to graph structured data. They were introduced in [START_REF] Scarselli | The graph neural network model[END_REF] and several variants of it have been proposed [START_REF] Wu | A comprehensive survey on graph neural networks[END_REF]. Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs) are among the most known variants.

GCNs [12] generalize the convolution operation from euclidean data (images and grid shaped data) to non-euclidean data (graphs). The key objective of GCNs is to learn a function that for each node in a graph generates a vector representation of it by aggregating its own features and its neighbors' features.

Let G = (V, E) be a graph, where V is the set of nodes and E the set of edges. We assume that each node n ∈ V is characterized by an input feature vector in n . The graph convolution operation takes as input the feature vector in n and outputs a new vector out n according to the following equation:

out n = f m∈N (n) 1 √ d m d n in m W l (1)
where N (n) represents the set composed of the node n and its neighbours, d m is the degree of the node m plus one, W l is the weight matrix of the l th GCN layer, and f is an activation function.

GATs [START_REF] Veličković | Graph attention networks[END_REF] have been proposed as an improvement of GCNs. Instead of doing a normalized sum of the features of the neighbors, GATs include the attention mechanism in the propagation step to generate the nodes' encoding, which is computed using the following equations:

out n = f m∈N (n) α nm in m W l , (2)
α nm = exp LeakyReLU a T in m W l ||in n W l j∈N (n) exp (LeakyReLU (a T [in n W l ||in j W l ])) , (3)
where || denotes the concatenation operator, a is a fully connected neural network and . T the transposition.

To stabilize the training process, the authors of GAT proposed to use multi head attention. It applies H independent attention head matrices to compute the hidden states and then concatenates their features. With the multi-head attention mechanism the node encoding becomes governed by the following equations:

out n = h=H h=1 f m∈N (n) α k nm in m W l , (4)
α h nm = exp LeakyReLU a T h in m W l ||in n W l j∈N (n) exp LeakyReLU a T h [in n W l ||in j W l ] . (5)

B. Segment routing

In segment routing, each probing cycle is encoded by a list of segment IDs (SID). There are two types of SIDs: nodes-SIDs and adjacency-SIDs. The former identify a shortest-path while the latter identify a link segment. The use of nodes-SIDs is feasible; however it may lead to an ambiguous definition of the probing cycle and accordingly introduce a bias in the measurement process [START_REF] Rahali | Feal: A source routing framework for efficient anomaly localization[END_REF]. In fact, when using nodes-SIDs to identify a path between a source s and a destination d and due to the load balancing mechanism deployed, we will not be sure which path the traffic followed exactly.

In this work, we consider the adjacency-SIDs and we assume that each probing cycle is encoded only using a list of adjacency-SIDs of a maximum length of k.

III. RELATED WORK

The emergence of networks and services virtualization brings new issues and challenges. Among these, the monitoring of network slices is certainly among of the most important ones given the multiplicity of services and their diversity in terms of QoS.

We generally distinguish between two categories of monitoring: direct and indirect methods. Direct methods rely on protocol-based tools such as SNMP or traceroute. This type of methods incurs a significant monitoring traffic overhead and is not always feasible due to the dependence on cooperation between internal nodes. Indirect methods overcome these limitations and infer the state of the network based on end-toend measurements between nodes with monitoring capabilities (i.e., monitors). This is known in the literature as Network Tomography (NT) [START_REF] Vardi | Network tomography: Estimating source-destination traffic intensities from link data[END_REF]. Another motivation for using NT approaches for the slices' monitoring is their perfect fit with the SDN and the NFV paradigms. Indeed, NT methods require a holistic view of the state of the network, which is guaranteed through SDN technologies. Alongside the holistic view, NT methods also require that monitoring traffic follow a specific path. To achieve this, segment routing (SR) is considered as a promising candidate. It provides, indeed, fast and efficient tools to deploy traffic forwarding strategies along arbitrary paths without any additional protocol or signaling procedures. It enables to constrain the traffic to pass through particular places and thus, to build specific probing schemes. Besides, SDNs allow arbitrary routing, but SR is more scalable and practical [START_REF]Cisco. Making networks sdn-ready with segment routing[END_REF]. In SR, the path is encoded in the packet header as a list of segment IDs (SIDs). Then, the packet is forwarded according to the instructions corresponding to the stacked SIDs.

Thanks to the advantages it brings, SR routing was proposed as a key tool for network monitoring in several works. In [START_REF] Aubry | Scmon: Leveraging segment routing to improve network monitoring[END_REF], the authors introduce an SR-based monitoring solution where only a single monitor is deployed, and monitoring probes follow the cycles starting and ending at that monitor. They propose Scmon, a framework that minimizes the number of cycles covering the physical topology and encodes efficiently the probing cycles with segment IDs. The use of a single monitor reduces the monitoring cost and avoids the synchronization issues. However, this requires the use of very long cycles to cover all the resources which can introduce a bias in the measurements. Similarly, X.Li and al. [14], focused on using a single monitor and proposed an improvement of the Scmon framework. They put the accent on minimizing the total length of all probing cycles that can be generated from a single monitor. Furthermore, the authors of [13] proposed several ILP formulations of the minimum cycles cover problem. The common points between our proposal and these works is the use of segment routing and cycles probing. However, what distinguishes us is that we focus on finding a subset of nodes as monitors and not a single monitor.

In [START_REF] Gopalan | On identifying additive link metrics using linearly independent cycles and paths[END_REF], the authors studied theoretically the problem of monitor placement to identify additive links metrics. They gave necessary and sufficient conditions to identify an additive metric on all the network links for a given topology. Then, they proposed a solution that minimizes the number of monitors to exchange probes with regular paths or cycles. However, no constraint on the length of the path is considered. Similarly, in [START_REF] He | Robust and efficient monitor placement for network tomography in dynamic networks[END_REF], authors built necessary and sufficient conditions on identifying additive metrics but using only regular paths. They followed an algebraic approach, and they proposed an algorithm based on the graph decomposition into strongly connected components to identify the minimum number of monitors that guarantee the identifiability of all links. Another work [START_REF] Ma | Link identifiability in communication networks with two monitors[END_REF] focuses on a different vision of the problem of monitoring placement, where the number of monitors is fixed first and then they aim to find their optimal placement to identify as many links as possible.

More recently, M.Rahali and al. [START_REF] Rahali | Feal: A source routing framework for efficient anomaly localization[END_REF] focused on the same problem we consider here. They propose a Greedy solution to which we compare our learning based method.

IV. CONTEXT & PROBLEM FORMULATION A. Context

As mentioned earlier, in this work we aim to monitor the state of a set of slices deployed on top of a physical infrastructure and running different services using a network tomography-based method.

In general building a network tomography monitoring solution consists of three main steps: the placement of monitors, the establishment of a probing strategy and finally inferring internal metrics based on external measurements.

In this work, we focus on the optimal monitor placement problem, but under certain constraints: the probing scheme will consist of cycles that we deploy using segment routing. The use of probing cycles eliminates the synchronization problem that one might have when using regular monitoring paths. It should be noted, however, that the use of segment routing adds a constraint to the length of the probing cycles.

B. Problem Formulation

The notation used in this subsection are summarized in Table I. We assume that the topology of the physical network The objective of collecting the end-to end measurements is to detect failures and to monitor the state of the links on top of which slices are deployed. Therefore, the state of a link is defined by the fact that the monitored metric (e.g. delay, loss rate) is above or below a threshold. Hence, the metric of interest becomes non additive (its value on a link is 1 iff there is an anomaly on that link).

Covering all the physical links on top of which slices are deployed, will allow then the detection of any anomaly. In this work, we focus on covering all physical links, not just the subset of links hosting slices, as this will be more robust in the event of slice migration and will not necessitate recalculating the monitors' placement. From this observation we focus on finding the minimum number of monitors to cover the maximum number of physical links using cycles.

Given the physical network, we denote the cycles formed by at most k links that can be generated from each node v as C k v . Similarly, for each vertex v the set of links covered by C k v is denoted as L v k . The first step in solving the monitor placement is to compute for each node v, the set of cycles whose length is less than k:

C = {C k v1 , C k v2 , • • • , C k vn }. Algorithm 1 summarizes this process.
Once the list of cycles is obtained, the next step is to determine the minimum set of monitors M ⊂ V such that:

v∈M L k v = L.
In other words, the task of finding the optimal set of monitors which cover all links can be considered as a particular case of the Minimum set cover problem, which is known to be NP-Complete.

To summarize, to determine the optimal set of monitors we Algorithm 1 Compute Cycles whose length less or equal to k [START_REF] Rahali | Feal: A source routing framework for efficient anomaly localization[END_REF] Input: a graph G = (V, L), maximum length of cycles k Output: The set of cycles C

1: for all node v in V do

2: v start ← v 3: C k v ← ∅ 4:
visited ← ∅

min v∈V x v s.t v:l∈L v k x v ≥ 1, ∀l ∈ L x v ∈ {0, 1} V. PROPOSED METHOD
To solve the problem presented in previous section and due to its NP-completeness, we introduce MonGNN, a GNN based framework that divides the problem into two tasks: determining the number of monitors and then identifying them.

A. Learn to predict the number of monitors

The main process of the first task is depicted in Figure 1. The objective of this task is to learn a function f that maps a graph and a maximum cycle length to the needed number of monitors. It is defined as follows:

f (G, k) = m n (6)
To learn this function we model it using neural networks (NNs). In fact, NNs can approximate any function as long as the hidden layers contain sufficient numbers of hidden neurons. Since f takes as input a graph, we used a Graph Neural Network (GNN). GNNs take as input a graph and outputs a node-level representation: a matrix, where each row is a vector that encodes both the attributes and the structure of a vertex in the input graph. Then, to obtain a graph-level representation (a vector that encodes the whole graph), we choose to apply a simple average of the node-level representation. Figure 2 summarizes the main parts of the GNN module represented in Figure 1.

Next this graph encoding is fed into a Multilayer Perceptron (MLP) [START_REF] Ramchoun | Multilayer perceptron: Architecture optimization and training[END_REF] to obtain the number of monitors.

To train this neural architecture, we consider a supervised setting. We start by the data collection process, which is summarized below:

• We generate N graphs.

• For each graph we compute the cycles map using Algorithm 1. • Based on the cycles map, we generate a link map that models the relation between the nodes and the links they can cover.

• The problem becomes a set covering problem that we solve using the ILP defined in previous section (using Gurobi1 ) to obtain the optimal labels. At the end of this process, we obtained a dataset of pairs (graphs, optimal number of monitors needed to cover all links). This dataset was, then, used for the training of the neural architecture minimizing the mean square error (MSE) between the true labels and predicted ones.

Once the training step was done, we got a model that, given a graph, predicts the optimal number of monitors that we need to cover all links.

Apart from the fast prediction, the obtained model doesn't need to compute neither the cycles map nor the link cover bipartite graph in order to determine the number of monitors. It learns how to directly map the raw physical topology to that optimal number of monitors.

B. Monitors identification

Until now, our model is able just to predict the number of monitors we need. In this step we aim to answer the following question: given the optimal number of monitors, how can we determine their identity?

The answer to the question above is depicted in Figure 3. The GNN module refers to a trained model.

The process of revealing the identity of the optimal monitors is done as follows: we feed a graph to the trained module to obtain a prediction of the optimal number of monitors. Then we compute the link bipartite graph, and we feed them with the graph to the genetic algorithm in charge of revealing the identity of monitors. The genetic algorithm (GA) have 5 phases: initialization, fitness score, selection, crossover and mutation. The general workflow of the GA is presented in Figure 4.

• Initialization step: In the initialization step, we generate a random generation of solutions (individuals). Each solution is a boolean vector whose size equals the number of nodes in the graph. The j th node is selected as a monitor if and only if the j th of the boolean vector equals one. The generation of this initial population is based on the predicted number of monitors. For example let's suppose that the number of nodes in the graph is set to N and the predicted number is m; in this case, all random • Selection step and fitness score: The objective of the selection step is to select individuals (solutions) that pass their genes to the next generation. We consider a simple selection process, only keeping the best elements and killing the rest. • Fitness score: To quantify the fitness of an individual we define a fitness score using the following equation: s(solution) is equal to the number of links covered by the selected elements of the solution.

• Mutation and cross over: In the cross-over, the aim is to combine the genes of two individuals in the hope of obtaining a better solution. In the context of our problem, the cross-over is done by taking two individuals and swapping a single different element between them. Finally, the mutation is done by randomly changing the state of two nodes while keeping the number of ones in each individual equal to n As we will show in the performance evaluation part, the trained model may underestimate or overestimate the optimal number of monitors. In spite of this misestimation, the prediction remains close to the optimal solution because it will add one node at most to the number of monitors. To handle this error we propose a local search approach to enhance the process of determination of the identity of the optimal monitors. The local search process checks if the solution with n nodes cover all links. If it does, it will try to find a solution with n -1, otherwise it will increase the number to search with n + 1 nodes using the genetic algorithm explained before.

VI. PERFORMANCE EVALUATION

In this section, we assess the performance of our approach based on extensive simulations. First we describe the simulation setup and the baselines, to which we compare the performance of our model. Then, we present and discuss the results.

A. Simulation setup

In order to measure the performance of our method, we tested it using different topologies. We consider two families of random graphs: Erdos Reyni(ER) [START_REF] Erdős | On the evolution of random graphs[END_REF] and Barbasi-Albert (BA) [START_REF] Barabási | Network science[END_REF].

For ER topologies they are defined by two parameters, the number of nodes n and the probability pr of edge creation. To ensure that the generated graph is connected we selected pr = For each type of graph and for each number of nodes, we generate 20000 graphs that we split into 15000 graphs for training and 5000 for test.

For the neural architecture, in the GNN part we use a two layers GAT network with 3 heads and use the Exponential Linear Unit (ELU) as an activation function. Then, we consider a seven layer MLP where each hidden layer contains respectively 256, 128, 64, 32, 16, 8 hidden units and the output layer with a single neuron. For the training, we set the batch size to 8 and to learn, we use Adam optimizer [11] with a learning rate of 0.0001.

B. Baselines

We compare our approach, with two methods:

• A greedy solution that takes as input the link maps and selects iteratively the nodes that cover the highest number of links uncovered. • A genetic algorithm combined with a binary search (GABS): this is a variant of our proposal but without the GNN part. We directly run the GA to find the optimal solution.

C. Simulation results

1) Prediction of the number of monitors: Fig. 5 and Fig. 6 illustrate the performance of the neural architecture in predicting the number of monitors. We put the accent on the distribution of the prediction error. The prediction was conducted on the test graphs, that the model has never seen during training. In both types of graphs and in all sizes, we observe that the model predicts correctly the optimal number of monitors with a high frequency. Furthermore, when it misses the optimal values, it stays close to it. The absolute value of the error is either zero or one.

Note that, once the model is trained, our model can reach this performance without recalculating neither the cycles of the graphs nor the link map. The model learnt how to directly map the topology of the network into the number of required monitors. 2) Optimality gap: Hereafter, we propose to benchmark the performance of MonGNN against the baselines mentioned earlier. We compare the three methods in terms of the optimality gap, which is defined as follows:

optimal gap(%) = 100 × optimal valuemethod value optimal value (7) where optimal value represents the optimal number of monitors and method value refers to the number of monitors given by a certain method.

The results for ER and BA graphs are shown, respectively, in Fig. 7 and Fig. 8. We can observe that our methods outperform the greedy solution in all cases, especially with the ER graphs. In the BA graphs, all solutions have the same performance on small graphs. Our method conserve the same behaviour on large graphs, while the optimality gap of the greedy method starts to increase.

MonGNN and GABS have the same performance. We then compare them in terms of execution time. Fig. 9 and Fig. Although both methods have quasi the same performance we can see that MonGNN is faster than GABS. In fact, with the learning part, our method can predict efficiently the number of monitors, hence, it reduces effectively the search space and then reduce the time wasted in exploring trivial and unfeasible solutions.

VII. CONCLUSION

In this work, we proposed a new solution to find the optimal monitor placement to cover all slices with probing cycles. We formulated the task as a set cover problem, and we proposed a learning based approach. We divided the task into two subtasks: the prediction of the number of monitors, and their identification. We unveiled the potential of GNNs in solving the first sub-task. Then, we proposed a genetic algorithm to deal with the second one.

There are lot of directions to go for the future work:(1) Even we avoid the process of computing cycles in the prediction step, we are obliged to do it to reveal the identity of monitors, so it is useful to find a solution that avoids this;

(2) Given that the optimal solution for large instances can not be determined, it would be good to propose methods to enhance the generalization on large graphs of the model that was trained on small instances.

vv

  Set of physical nodes and links C Set of measurement cycles S Set of slices to monitor k Maximum length of probing cycles C k Set of cycles starting at node v L k Links covered by C k v TABLE I: Main notations is known, and we model it as an undirected graph G = (V, L), where V and L represent the sets of physical nodes and of the physical links, respectively. Let C denote the set of the probed cycles and S the set of slices we want to monitor and which are deployed on top of the physical network G. The cardinals of the sets V, L, S and C are respectively : n = |V|, m = |L|, p = |C| and s = |S|

Fig. 1 :

 1 Fig.1:The training process to learn to predict the number of monitors.

Fig. 3 :

 3 Fig. 2: GNN Module

Fig. 4 :

 4 Fig. 4: Genetic algorithm workflow

Fig. 5 :

 5 Fig. 5: Error prediction of number of monitors with BA graphs

10

 10

(a) n = 20 (Fig. 6 :

 206 Fig. 6: Error prediction of number of monitors with ER graphs

Fig. 7 :

 7 Fig. 7: Optimality gap : ER graphs

https://www.gurobi.com/

MonGNN

GABS Greedy