3.1 Introduction

The scientific foundations of our work are those of network design and network analysis. Specifically, this concerns the principles of packet switching and in particular of IP networks (protocol design, protocol testing, routing, scheduling techniques), and the mathematical and algorithmic aspects of the associated problems, on which our methods and tools are based.

These foundations are described in the following paragraphs. We begin by a subsection dedicated to Quality of Service (QoS) and Quality of Experience (QoE), since they can be seen as unifying concepts in our activities. Then we briefly describe the specific sub-area of model evaluation and about the particular multidisciplinary domain of network economics.

3.2 Quality of Service and Quality of Experience

Since it is difficult to develop as many communication solutions as possible applications, the scientific and technological communities aim towards providing general services allowing to give to each application or user a set of properties nowadays called “Quality of Service” (QoS), a terminology lacking a precise definition. This QoS concept takes different forms according to the type of communication service and the aspects which matter for a given application: for performance it comes through specific metrics (delays, jitter, throughput, etc.), for dependability it also comes through appropriate metrics: reliability, availability, or vulnerability, in the case for instance of WAN (Wide Area Network) topologies, etc.

QoS is at the heart of our research activities: We look for methods to obtain specific “levels” of QoS and for techniques to evaluate the associated metrics. Our ultimate goal is to provide tools (mathematical tools and/or algorithms, under appropriate software “containers” or not) allowing users and/or applications to attain specific levels of QoS, or to improve the provided QoS, if we think of a particular system, with an optimal use of the resources available. Obtaining a good QoS level is a very general objective. It leads to many different areas, depending on the systems, applications and specific goals being considered. Our team works on several of these areas. We also investigate the impact of network QoS on multimedia payloads to reduce the impact of congestion.

Some important aspects of the behavior of modern communication systems have subjective components: the quality of a video stream or an audio signal, as perceived by the user, is related to some of the previous mentioned parameters (packet loss, delays, ...) but in an extremely complex way. We are interested in analyzing these types of flows from this user-oriented point of view. We focus on the user perceived quality, in short, PQ, the main component of what is nowadays called Quality of Experience (in short, QoE), to underline the fact that, in this case, we want to center the analysis on the user. In this context, we have a global project called PSQA, which stands for Pseudo-Subjective Quality Assessment, and which refers to a technology we have developed allowing to automatically measure this PQ.

Another special case to which we devote research efforts in the team is the analysis of qualitative properties related to interoperability assessment. This refers to the act of determining if end-to-end functionality between at least two communicating systems is as required by the base standards for those systems. Conformance is the act of determining to what extent a single component conforms to the individual requirements of the standard it is based on. Our purpose is to provide such a formal framework (methods, algorithms and tools) for interoperability assessment, in order to help in obtaining efficient interoperability test suites for new generation networks, mainly around IPv6-related protocols. The interoperability test suites generation is based on specifications (standards and/or RFCs) of network components and protocols to be tested.

3.3 Stochastic modeling

The scientific foundations of our modeling activities are composed of stochastic processes theory and, in particular, Markov processes, queuing theory, stochastic graphs theory, etc. The objectives are either to develop numerical solutions, or analytical ones, or possibly discrete event simulation or Monte Carlo (and Quasi-Monte Carlo) techniques. We are always interested in model evaluation techniques for dependability and performability analysis, both in static (network reliability) and dynamic contexts (depending on the fact that time plays an explicit role in the analysis or not). We look at systems from the classical so-called call level, leading to standard models (for instance, queues or networks of queues) and also at the burst level, leading to fluid models.

In recent years, our work on the design of the topologies of WANs led us to explore optimization techniques, in particular in the case of very large optimization problems, usually formulated in terms of graphs. The associated methods we are interested in are composed of simulated annealing, genetic algorithms, TABU search, etc. For the time being, we have obtained our best results with GRASP techniques.

Network pricing is a good example of a multi-disciplinary research activity half-way between applied mathematics, economy and networking, centered on stochastic modeling issues. Indeed, the Internet is facing a tremendous increase of its traffic volume. As a consequence, real users complain that large data transfers take too long, without any possibility to improve this by themselves (by paying more, for instance). A possible solution to cope with congestion is to increase the link capacities; however, many authors consider that this is not a viable solution as the network must respond to an increasing demand (and experience has shown that demand of bandwidth has always been ahead of supply), especially now that the Internet is becoming a commercial network. Furthermore, incentives for a fair utilization between customers are not included in the current Internet. For these reasons, it has been suggested that the current flat-rate fees, where customers pay a subscription and obtain an unlimited usage, should be replaced by usage-based fees. Besides, the future Internet will carry heterogeneous flows such as video, voice, email, web, file transfers and remote login among others. Each of these applications requires a different level of QoS: for example, video needs very small delays and packet losses, voice requires small delays but can afford some packet losses, email can afford delay (within a given bound) while file transfer needs a good average throughput and remote login requires small round-trip times. Some pricing incentives should exist so that each user does not always choose the best QoS for her application and so that the final result is a fair utilization of the bandwidth. On the other hand, we need to be aware of the trade-off between engineering efficiency and economic efficiency; for example, traffic measurements can help in improving the management of the network but is a costly option. These are some of the various aspects often present in the pricing problems we address in our work. More recently, we have switched to the more general field of network economics, dealing with the economic behavior of users, service providers and content providers, as well as their relations.

4.1 Networking

Our global research effort concerns networking problems, both from the analysis point of view, and around network design issues. Specifically, this means the IP technology in general, with focus on specific types of networks seen at different levels: wireless systems, optical infrastructures, peer-to-peer architectures, Software Defined Networks, Content Delivery Networks, Content-Centric Networks, clouds.

A specific aspect of network applications and/or services based on video or voice content, is our PSQA technology, able to measure the Perceptual Quality automatically and in real time. PSQA provides a MOS value as close as it makes sense to the value obtained from subjective testing sessions. The technology has been tested in many environments, including one way communications as, for instance, in video streaming, and bi-directional communications as in IP telephony, UDP- or TCP-based systems, etc. It has already served in many collaborative projects as the measuring tool used.

4.2 Stochastic modeling

Many of the techniques developed at Dionysos are related to the analysis of complex systems in general, not only in telecommunications. For instance, our Monte Carlo methods for analyzing rare events have been used by different industrial partners, some of them in networking but recently also by companies building transportation systems. We develop methods in different areas: numerical analysis of stochastic models, bound computations in the same area, Discrete Event Simulation, or, as just mentioned, rare event analysis. In this last case, we focus on the main Monte Carlo approaches (Importance Sampling, Splitting, Recursive Variance Reduction, etc.) and we are mainly interested in the case of rare events of “artificial origins” (components' failures, congestion problems) as opposed to natural disasters, that need other specific mathematical tools.

5.1 Awards

6.1 Probabilistic analysis of systems

Participants: Yann Busnel, Jérome Henry, Gerardo Rubino, Bruno Sericola.

In 2021 the activities have been concentrated around different topics related to the analysis of distributed systems. We also continued the study of the transient regime of Markov models, and we also worked on some aspects of cellular networks in the area of this subsection.

Probabilistic analysis of population protocols. The computational model of population protocols is a formalism that allows the analysis of properties emerging from simple and pairwise interactions among a very large number of anonymous finite-state agents. We analyze in 38 a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This protocol relies on successive pull operations involving $k$ different nodes, with $k=2$ or $k=3$, and called $k$-pull operations. Specifically during a $k$-pull operation, an uninformed node $a$ contacts $k-1$ other nodes at random in the network, and if at least one of them knows the rumor, then node $a$ learns it. We perform a detailed study in continuous-time of ${\Theta }_{k,n}$, the total time needed for all the $n$ nodes to learn the rumor. We obtain, for $k\in \{2,3\}$, the mean value, the variance and the distribution of ${\Theta }_{k,n}$ together with their asymptotic behavior when the number of nodes $n$ tends to infinity.

These results are extended in the discrete-time case in 27, where we propose and analyze the general case of a $k$-pull operation, with $k\ge 2$. We perform a thorough study of the total number $T_{k,n}$ of $k$-pull operations needed for all the $n$ nodes to learn the rumor. We compute the expected value and the variance of $T_{k,n}$, together with their limiting values when $n$ tends to infinity. We also analyze the limiting distribution of $(T_{k,n}-E\left(T_{k,n}\right))/n$ and prove that it has a double exponential distribution when $n$ tends to infinity. Finally, we show that when $k>2$, our new protocol requires less operations than the traditional 2-push-pull and 2-push protocols by using stochastic dominance arguments. All these results generalize the standard case $k=2$.

The average-based distributed algorithms, analysed in 24, rely on simple and pairwise random interactions among a large and unknown number of anonymous agents. This allows the characterization of global properties emerging from these local interactions. Agents start with an initial integer value, and at each interaction keep the average integer part of both values as their new value. The convergence occurs when, with high probability, all the agents possess the same value, which means that they all know a property of the global system. Using a well chosen stochastic coupling, we improve upon existing results by providing explicit and tight bounds of the convergence time. We apply these general results to both the proportion problem and the system size problem.

Collecting data in large scale systems. We propose and analyse in 46 the performance and the vulnerability to attacks of three algorithms for collecting longitudinal data in a large scale system. A monitoring device is in charge of continuously collecting measurements from end-devices. The communication graph is connected but not necessarily complete. For scalability reasons, at each collect, a single end-device is randomly selected among all the end-devices to send the content of its local buffer of data to the monitoring device. Once sent, the end-device resets its buffer, and resumes its measurement process. Two of the three algorithms are randomized algorithms while the third one is deterministic. We study the transient and stationary maximum load distribution at end-devices when collects are made using the first and third algorithm, and we provide bounds via a coupling argument when the second algorithm is used. While the third algorithm provides the best performance, it is highly vulnerable to attacks.

Data streaming and sampling. Distributed systems increasingly require the processing of large amounts of data, for metrology, safety or security purposes. We consider the problem of achieving uniform node sampling in large scale systems in presence of Byzantine nodes. The uniform node sampling service offers to applications using it a single simple primitive that returns, upon invocation, the identifier of a random node that belongs to the system. We first propose an omniscient strategy that processes on the fly an unbounded and arbitrarily biased input stream made of node identifiers exchanged within the system, and outputs a stream that preserves the uniformity property. Informally, uniformity states that any node in the system should have the same probability to appear in the sample of any correct node of the system. We show through a Markov chain analysis that this property holds despite any arbitrary bias introduced by the adversary. We then propose a strategy based on a sketch data structure that is capable of approximating the omniscient strategy without requiring any prior knowledge on the composition of the input stream. We show through both theoretical analysis and extensive simulations that this "knowledge-free" strategy accurately approximates the omniscient one. We evaluate the resilience of the knowledge-free strategy by studying two representative attacks (flooding and targeted attacks). We quantify the minimum number of identifiers that Byzantine nodes must insert in the input stream to prevent uniformity. Finally, we propose a new construction that processes each input stream with sketches put in series that allows to both increase the accuracy of a single sketch and decrease the time to converge to a uniform output stream. To our knowledge, such a work has never been proposed before 17.

Phenotypic characteristics of a plant specie refer to its physical properties as cataloged by plant biologists at different research centers around the world. Clustering species based upon their phenotypic characteristics is used to obtain diverse sets of parents that are useful in their breeding programs. The Hierarchical Clustering (HC) algorithm is the current standard in clustering of phenotypic data. This algorithm suffers from low accuracy and high computational complexity issues. To address the accuracy challenge, we propose the use of Spectral Clustering (SC) algorithm. To make the algorithm computationally cheap, we propose using sampling, specifically, Pivotal Sampling that is probability based. Since application of samplings to phenotypic data has not been explored much, for effective comparison, another sampling technique called Vector Quantization (VQ) is adapted for this data as well. VQ has recently given promising results for genotypic data. The novelty of our SC with Pivotal Sampling algorithm is in constructing the crucial similarity matrix for the clustering algorithm and defining probabilities for the sampling technique. Although our algorithm can be applied to any plant species, we test it on the phenotypic data obtained from about 2400 Soybean species. SC with Pivotal Sampling achieves substantially more accuracy (in terms of Silhouette Values) than all the other proposed competitive clustering with sampling algorithms (i.e. SC with VQ, HC with Pivotal Sampling, and HC with VQ) 28. The complexities of our SC with Pivotal Sampling algorithm and these three variants are almost the same because of the involved sampling. In addition to this, SC with Pivotal Sampling outperforms the standard HC algorithm in both accuracy and computational complexity. We experimentally show that we are up to 45% more accurate than HC in terms of clustering accuracy. The computational complexity of our algorithm is more than a magnitude less than that of HC.

Due to the large sizes of data, clustering algorithms often take too much time. Sampling this data before clustering is commonly used to reduce this time. In this work, we propose a probabilistic sampling technique called cube sampling along with K-Prototype clustering. Cube sampling is used because of its accurate sample selection. K-Prototype is most frequently used clustering algorithm when the data is numerical as well as categorical (very common in today's time). The novelty of this work is in obtaining the crucial inclusion probabilities for cube sampling using Principal Component Analysis (PCA). Experiments on multiple datasets from the UCI repository demonstrate that cube sampled K-Prototype algorithm gives the best clustering accuracy among similarly sampled other popular clustering algorithms (K-Means, Hierarchical Clustering (HC), Spectral Clustering (SC)). When compared with unsampled K-Prototype, K-Means, HC and SC, it still has the best accuracy with the added advantage of reduced computational complexity (due to reduced data size) 51.

Blockchain and AI. Bitcoin system (or Bitcoin) is a peer-to-peer and decentralized payment system that uses a cryptocurrency named bitcoin (BTC) and was released as open-source software in 2009. Unlike fiat currencies, there is no centralized authority or any statutory recognition, backing, or regulation for BTCs. All transactions are confirmed for validity by a network of volunteer nodes (miners) and after that, a collective agreement is recorded into a distributed ledger “Blockchain”. The Bitcoin platform has attracted both social and anti-social elements. On the one hand, it is social as it ensures the exchange of values, maintaining trust in a cooperative, community-driven manner without the need for a trusted third party. At the same time, it is anti-social as it creates hurdles for law enforcement to trace suspicious transactions due to anonymity and privacy. To understand how the social and anti-social tendencies in the user base of BTC affect its evolution, there is a need to analyze the BTC system as a network. A first study has explored the local topology and geometry of the network during its first decade of existence. The characteristics, local and global network properties of the user's graph were analyzed at ten intervals between 2009-2020 with a gap of one year 26. Afterwards, we focused on illegal activities using BTC systems. We thus utilize machine learning for identifying these illicit entities and addressed the issue by implementing an ensemble of decision trees for supervised learning. More parameters allow the ensemble model to learn discriminating features that can categorize multiple groups of illicit users from licit ones 11. The proposed model provided a reliable tool for forensic study. In parallel, we conducted an experiment on a dataset of 1216 real-life entities 25.

Transient analysis of Markovian models. Classic performance evaluation using queueing theory is usually done assuming a stable model in equilibrium. However, there are situations where we are interested in the transient phase. In this case, the main metrics are built around the model’s state distribution at an arbitrary point in time. In dependability, a significant part of the analysis is done in the transient phase. In previous work, we developed an approach to derive distributions of some continuous time Markovian models, built around uniformization (also called Jensen’s method), transforming the problem into a discrete time one, and the concept of stochastic duality. This combination of tools provides significant simplifications in many cases. However, stochastic duality does not always exist. Recently, we discovered that an idea of algebraic duality, formally similar to stochastic duality, can be defined and applied to any linear differential system (or equivalently, to any matrix). In this case, there is no limitation, the transformation is always possible. We call it the exponential-dual matrix method. In 56, we describe the limitations of stochastic duality and how the exponential-dual matrix method operates for any system, stochastic or not. These concepts are illustrated throughout our article with specific examples, including the case of infinite matrices. The heart of the content of this chapter was presented in the JMM conference 53. In the same forum, we presented some views on the discrete time case (matrix powers)analyzing specific particluar cases 52.

Cellular Networks with Delay-Tolerant Users. In 29, we analyze the impact of delaying delay-tolerant calls under certain conditions in cellular networks. We propose to queue the call if the user agrees when the terminal has bad radio conditions and the system is loaded. The call is served as soon as radio conditions become good or the current load goes below a given threshold. We model the system as a continuous-time Markov chain, which allows us to compute the blocking probability, the mean waiting time and the mean service time. For instance, numerical results show that when the proportion of users with delay tolerance is 20%, the system can bear 16% more calls with the same blocking probability, and 113% more calls if 80% of users are delay tolerant.

6.2 Machine learning

Participants: Yassine Hadjadj-Aoul, Gerardo Rubino, César Viho, Yann Busnel, Ahcene Boumhand, Sid Ali Hamideche, Illyyne Saffar, Anouar Rkhami, Imane Taibi.

Our activities around machine learning tools continue to grow. We describe in this subsection only the approaches proposing new learning methodologies.

Monitoring with Machine Learning. The use of artificial intelligence techniques in monitoring is becoming an essential building block for the new techniques developed in recent years. In this context, we proposed an application in a specific use cases.

Multilabel scene classification has emerged as a critical research area in the domain of remote sensing. Contemporary classification models primarily emphasize on a single object or multiobject scene classification of satellite remote sensed images. These classification models rely on feature engineering from images, deep learning, or transfer learning. Comparatively, multilabel scene classification of Very High Resolution (VHR) images is a fairly unexplored domain of research. Models trained for single label scene classification are unsuitable for the application of recognizing multiple objects in a single remotely sensed VHR satellite image. To overcome this research gap, the current inquiry proposes to fine‐tune state of the art Convolutional Neural Network (CNN) architectures for multilabel scene classification. The proposed approach pre-trains CNNs on the ImageNet dataset and further fine‐tunes them to the task of detecting multiple objects in VHR images. To understand the efficacy of this approach, the final models are applied on a VHR data base: the UCMERCED image dataset containing 21 different terrestrial land use categories with a submeter resolution. The performance of the final models is compared with the graph convolutional network‐based model by Khan et al. From the results on performance metrics, it was observed that the proposed models achieve comparable results in significantly fewer epochs 22.

Mixing Reservoir Computing end Evolutionary algorithms. Reservoir Computing models are a class of recurrent neural networks that have enjoyed recent attention, in particular, their main family, Echo State Networks (ESNs). These models have a large number of hidden-hidden weights (in the so-called reservoir) forming a recurrent topology. The reservoir is randomly connected with fixed weights during learning: only readout parameters (from reservoir to output neurons) are trained; the reservoir weights are frozen after initialized. Since the reservoir structure is fixed during learning, only its initialization process has an impact on the model’s performance. In 32, we introduce an evolutionary method for adjusting the reservoir non-null weights. The evolutionary process runs on the frequency space corresponding to a Fourier transformation of the weights. This allows to reduce the dimension of the space where learning takes place. We combine an evolutionary search in the Fourier space with supervised learning for the readout weights. The resulting algorithm, called EvoESN (Evolutionary ESN), obtains promising results modeling two well-known problems of the chaotic time-series area.

Combining FFT/LSTM for Time-series forecasting. Over the last few years, networks' infrastructures are experiencing a profound change initiated by Software Defined Networking (SDN) and Network Function Virtualization (NFV). In such networks, avoiding the risk of service degradation increasingly involves predicting the evolution of metrics impacting the Quality of Service (QoS), in order to implement appropriate preventive actions. Recurrent neural networks, in particular Long Short Term Memory (LSTM) networks, already demonstrated their efficiency in predicting time series, in particular in networking, thanks to their ability to memorize long sequences of data. In 35, we propose an improvement that increases their accuracy by combining them with filters, especially the Fast Fourier Transform (FFT), in order to better extract the characteristics of the time series to be predicted. The proposed approach allows improving prediction performance significantly, while presenting an extremely low computational complexity at run-time compared to classical techniques such as Auto-Regressive Integrated Moving Average (ARIMA), which requires costly online operations.

Collaborative Exploration and Exploitation in massively Multi-Player Bandits. In 57, we propose an approach to optimize the performance of Internet of Things (IoT) networks. We formulate the optimization problem as a massive multi-player multi-armed bandit problem, where the devices are the players and the radio channels are the arms, with collisions possibly preventing message reception. For handling a realistic IoT network, we do not assume that sensing information is available (i.e. that the collision are observed) or that the number of players is smaller than the number of arms. As the optimization problem is intractable, we propose two greedy policies: the first one focusing on the number of successful communications, while the second one also takes into account fairness between players. In order to implement an approximation of the targeted policies, we propose an explore-then-exploit approach, and establish a regret lower bound. For estimating the mean reward of arms, we propose a decentralized exploration algorithm with controlled information exchanges between players. Then we state that the regret of the estimated target policy is optimal with respect to the time horizon T. Finally, we provide some experimental evidences that the proposed algorithms outperform several baselines.

Federated learning in security management for IT and OT. The Internet of Things has begun to spread over a variety of domains, including industry and finance. It represents an increasing threat for both IT and OT. The lack of collaboration results in the same attacks targeting different organizations one after the other. Often employed as an answer to this problem, cyber threat-intelligence sharing induces its own set of challenges: trust, privacy, and traceability. This work 54 takes advantages of a distributed sharing-oriented architecture and to enhance the security of industrial infrastructures. We study Federated Learning algorithms to build a distributed, autonomic system for detecting and characterizing attacks, as well as providing countermeasures. Experiments on real-world testbeds at the chair Cyber CNI allow us to validate the theoretical assumptions against realistic infrastructures and scenarios, fitting industrial use-cases.

6.3 Future networks and architectures

Participants: Yassine Hadjadj-Aoul, Yann Busnel, Gerardo Rubino, Sofiene Jelassi, Ghina Dandachi, Rahali Mohamed, Anouar Rkhami, Soumaya Kaada, Amine Rguez.

The general field dealing with next generation networks and architectures analyzes the architectural evolutions of networks while addressing the need to develop new algorithms to support the new functions of the network.

In 2021, we still have had a particular focus on network resources' orchestration, in particular through network slicing. We have also continued our work on the monitoring of these networks by trying to minimize the costs of monitoring while allowing better detection of failures.

Network slicing and resources' orchestration. Resource allocation of 5G and beyond 5G (B5G) network slices is one of the most important challenges for network operators. Network slicing mainly consists in placing constrained services, which are typically expressed in the form of a Virtual Network Function-Forwarding Graph (VNF-FG). Several solutions have already been proposed in the literature to address these types of problems. However, in these approaches, past placement experiences yield no benefit to new placements (i.e., noting is learnt from the obeserved past).

In 47, 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 compared to existing work.

In 62, we introduced a platform for dynamic virtual network embedding. The proposed solution is based on a combination of a deep reinforcement learning strategy and a Monte Carlo (MC) approach. The main idea is to learn to generate, using a Deep Q-Network (DQN), a distribution of the placement solution, on which a MC-based search technique is applied. This makes the agent’s exploration of the solution space more efficient.

Due to the exploration-exploitation dilemma, the solutions obtained by DRL-based approaches can be infeasible. This can lead to reliability concerns. To overcome this issue, we combine, in 43, DRL and relational Graph Convolutional Neural (GCN) networks in order to automatically learn how to improve the quality of heuristics in the placement of services. Simulation results show the effectiveness of our procedure. Starting with an initial solution given by the heuristics it can find an improvement of about 35% on average.

To address the diversity of use cases envisioned by the 5G technology, it is critical that the design of the future network allows maximum flexibility and cost effectiveness. This requires that network functions should be designed in a modular fashion to enable fast deployment and scalability. This expected efficiency can be achieved with the cloud native paradigm where network functions can be deployed as containers. Virtualization tools such as Kubernetes offer multiple functionalities for the automatic management of the deployed containers hosting the network functions. These tools must be applied efficiently to improve the network functions availability and resilience. Our paper 41 focuses on resource allocation in a Kubernetes infrastructure hosting different network services. The objective of the proposed solution is to avoid resource shortage in the cluster nodes while protecting the most critical functions. A statistical approach is followed for the modeling of the problem as well as for its resolution, given the random nature of the treated information.

Future networks monitoring. Network Slicing (NS) is a key technology that enables network operators to accommodate different types of services with varying needs on a single physical infrastructure. Despite the advantages it brings, NS raises some technical challenges, mainly ensuring the Service Level Agreements (SLA) for each slice. Hence, monitoring the state of these slices will be a priority for ISPs.

In 42, a new monitoring procedure for anomaly localization, customized for NFV-based network infrastructures deployed with the Service Function Chaining (SFC) mechanism, one of the most important key enablers for NFV networks. Our solution allows the deployment of efficient probing schemes that guarantee the localization of multiple simultaneously failed nodes with a minimum cost. This is formulated as a graph matching problem and solved with a max-flow approach. Simulations show that our solution localizes the failed nodes with a small rate of false positives and false negatives.

To overcome high measurements overhead, network tomography (NT) is a promising solution, in future virtualised networks. Indeed, network tomography consists of a set of methods to infer unmeasured network metrics using end-to-end measurements between monitors. In 45, we focus on inferring the additive metrics of slices such as delays or logarithms of loss rates. We model the inference task as a regression problem that we solve using neural networks. In our approach, we train the model on an artificial dataset. This not only avoids the costly process of collecting a large set of labeled data but has also a nice covering property useful for the procedure's accuracy. Moreover, to handle a change on the topology or the slices we monitor, we propose a solution based on transfer learning in order to find a trade-off between the quality of the solution and the cost to get it. Simulation results with both, emulated and simulated traffic show the efficiency of our method compared to existing ones in terms of both accuracy and computation time.

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 44, 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.

Toward operative QoE models for streaming services. The measurement of the Quality of Experience (QoE) of multimedia streaming services (MMSS) over IP networks may be done using objective QoE models. These are mathematical functions transforming metrics from technical to user domains. An interesting category of QoE models predicts QoE scores of MMSS at runtime, letting use them for the monitoring operation. This requires integrating them inside the production environments, i.e., where the actual MMSS are consumed by end-users. This aspect is often neglected by QoE modelers that focus mainly on the accuracy and fitness of their designed models with respect to a given set of settings and conditions. As a consequence, a considerable technical effort should be made in order to bring them from the laboratory to the production environments. This obviously discourages MMSS providers to easily accept and adopt them.

For the sake of enhancing QoE models integration, in 37 we propose Mesukal, a software-layer ensuring portability of QoE models over a variety of underlying MMSS, e.g. YouTube or Netflix. Specifically, Mesukal acts as a Java Virtual Machine (JVM) enabling to build portable applications over different OS, e.g. Windows, Linux or MacOS. Mesukal can be considered as a virtual MMSS that is able to seamlessly interact with QoE models, on the one hand, and arbitrary real MMSS, on the other hand. Each considered MMSS over IP networks is appropriately virtualized by a dedicated Mesukal App. Besides real MMSS, Mesukal can be used to instantiate experimental MMSS where the accuracy and portability of QoE models may be inspected and checked under controlled conditions. The inputs needed by the concerned QoE models are fetched from each real MMSS using probes that are tailored following the technology used by the considered multimedia service. In addition, Mesukal includes a rich GUI dashboard that enables to inspect QoE results.

6.4 Wireless Networks

Participants: Soraya Ait-Chellouche, Yann Busnel, Yassine Hadjadj-Aoul, Ali Hodroj, Bruno Sericola, Gerardo Rubino, César Viho.

The general domain dealing with wireless networks covers the optimization of these networks at multiples levels.

In 2021, we have continued our activities on improving the support of a large (i.e., massive) number of wireless IoT devices. We also continued our activities on improving video streaming in these networks through the improvement of multi-homing support.

Optimizing wireless IoT Networks. Driven by various services and applications, Machine Type Communications (MTC) will become an integral part of our daily life over the next few years. Meeting the ITU-T requirements, in terms of density, battery longevity, coverage, price, and supported mechanisms and functionalities, Cellular IoT, and particularly Narrowband-Internet of Things (NB-IoT), is identified as a promising candidate to handle massive MTC accesses. However, this massive connectivity would pose a huge challenge for network operators in terms of scalability. Indeed, the connection to the network in cellular IoT passes through a random access procedure and a high concentration of IoT devices would, very quickly, lead to a bottleneck. The latter procedure needs, then, to be enhanced as the connectivity would be considerable. With this in mind, we propose, in 55, to apply the access class barring (ACB) mechanism to regulate the number of devices competing for the access. In order to derive the blocking factor, we formulate the access problem as a Markov decision process that we were able to solve using one of the most advanced deep reinforcement learning techniques. The evaluation of the proposed access control, through simulations, shows the effectiveness of our approach compared to existing techniques such as the adaptive one and the Proportional Integral Derivative (PID) controller. Indeed, it manages to keep the proportion of access attempts close to the optimum, despite the lack of accurate information on the number of access attempts.

Despite the multiple benefits that such technology offers, the quick depletion of sensors’ battery power represents a major concern, mainly due to the extensive computational tasks and communication operations performed by individual sensors. Indeed, the cost of replacing batteries can be prohibitively expensive, especially when sensors are deployed in areas where access is difficult, in urbanized cities. To extend sensors’ lifetime, we proposed in 30 a new variant of the LEACH protocol named LEACH enhanced with probabilistic cluster head selection (LEACH-PRO). LEACH-PRO introduces several measures to extend WSNs nodes’ lifetime such as cluster head node selection using a probabilistic function based on maximum residual energy and minimum distance to the sink. The obtained simulation results have proven the supremacy of LEACH-PRO over LEACH and direct transmission protocol in terms of the achieved network lifetime and the generated traffic overhead. Most importantly, LEACH-PRO will significantly extend the sensors’ lifetime, which would make this type of deployment more viable in smart city scenarios.

Enhancing dynamic adaptive streaming over HTTP for multi-homed users. Nowadays, multimedia streaming traffic reaches 71% of the mobile data traffic over the world and most of the multimedia services use Dynamic adaptive streaming over HTTP (DASH) to adjust video delivery to the dynamic network environment and achieve higher user Quality of Experience (QoE) levels. Moreover, 90% of the video traffic is consumed by smart devices equipped with multiple network interfaces (Wifi, 3G, and 4G) known as multi-homed devices. In 20, we proposed a survey analyzing the protocols, the mechanisms, and the latest standards proposed in the literature for improving the performance and quality of video content in multipath and multihomed overlay networks. Multipath is a broader term, but in the context of this survey, we define multipath as enhancing network routing technique by using various paths that are not necessarily completely disjoint. Most existing surveys are specialized in one specific domain area related to multipath or multihoming. This study covers the research proposals at the different layers/sublayers of an overlay network from transport to the application and extends to cover the latest technologies like machine learning, Fog and Mobile Edge computing, VR 360 video, and the Internet of Multimedia Things (IoMT). As such, our work tries to be as comprehensive as possible to relate multipath and multihoming research solutions for video streaming to the current and emerging video streaming technologies.

For enhancing the video quality received by “multi-homed client” (i.e., clients with multiple network interfaces), we proposed, in 21, a network selection algorithm based on the Multi-Armed Bandit heuristic on top of the DASH protocol. For choosing the best network at each progression powerfully, DASH gives mobile video quality dependent on the apparent exhibition from the pre-owned system association through the Adaptive Bitrate Rules (ABR) without investigating the system conditions through the other network(s) which could give better quality. Subsequently, a few alterations for DASH ABR is required to enhance the video quality. Two of the MAB algorithms (UCB and Epsilon Greedy) were embraced for improving MPEG-Dash. The investigations are performed through a proving ground execution to show that UCB surpasses Epsilon Greedy, in stable system conditions, regarding goodput received by the Dash customer. Additionally, UCB can discover the harmony between investigating new choices, and abusing the triumphant variation. Index Terms-DASH, Multi-homed, video streaming .

Indoor localization with FTM. Metric Multidimensional Scaling is commonly used to solve multi-sensor location problems in 2D or 3D spaces. In this paper, we show that such technique provides poor results in the case of indoor location problems based on 802.11 Fine Timing Measurements, because the number of anchors is small and the ranging error asymmetrically distributed. We then propose a two-step iterative approach based on geometric resolution of angle inaccuracies 49. The first step reduces the effect of poor ranging exchanges. The second step reconstructs the anchor positions, starting from the distances of highest likely-accuracy. We show that this geometric approach provides better location accuracy results than other Euclidean Distance Metric techniques based on Least Square Error logic. We also show that the proposed technique, with the input of one or more known location, can allow a set of fixed sensors to auto-determine their position on a floor plan 19.

Because it is unauthenticated and unprotected, our experiments indicate that an adversary can implement ranging and location attacks, causing an unsuspecting client to incorporate forged values into its location computation. FTM clients tend to range against a small set of responders (top 3 to 6 responders with strongest signal). Once ranges have been collected, the client can compute its location using various techniques, such as 3-sphere intersection, matrix error minimization techniques or Kalman filter. Irrespective of the technique, we show in this paper that an attacker can cause a ranging client to deviate from its intended path, which can have dire consequences in some settings (e.g., automatic shuttle in public venue causing damages). We also show that protection intended for attacks on comparable ranging techniques, like GPS, are ineffective in the case of FTM 36. We finally show that protection intended for attacks on comparable ranging techniques, like GPS, are ineffective in the case of FTM. However, we also show that a crowd-sourcing technique that confirms that one AP is known by the others can mitigate the attack exposure 50.

6.5 Network Economics

Participants: Bruno Tuffin, Patrick Maillé, Ximun Castoreo.

The general field of network economics, analyzing the relationships between all actors of the digital economy, has been an important subject for years in the team.

In 2021, we still have had a particular focus on network neutrality issues (basically saying that in the network all flows/packets should be “considered” equal), but trying to look at them from original perspectives, and investigating so-called grey zones not yet addressed in the debate. The problems have been addressed from the following angles.

Non neutrality can be pushed by content providers. There is a trend for big content providers such as Netflix and YouTube to give grades to ISPs, to incentivize those ISPs to improve at least the quality offered to their service; this behavior can be seen as an incentive to be favored by ISPs and therefore not stick to neutrality rules as usually pushed by content providers. We have designed in 23 a model analyzing ISPs' optimal allocation strategies in a competitive context and in front of quality-sensitive users. We have showed that the optimal strategy is non-neutral, that is, it does not allocate bandwidth proportionally to the traffic share of content providers. On the other hand, we have showed that non-neutrality does not benefit ISPs but is surprisingly favorable to users' perceived quality.

Apparent difficulties to apply neutrality principles in next generation networks. Slicing is seen as one of the key characteristics of 5G and beyond networks but seems in apparent contradiction with neutrality principles promoted worldwide. We have discussed in 59 the two contradictory but considered compulsory notions.

Heterogeneity of neutrality rules. Network neutrality has recently been repealed in the United States, leading to a worldwide Internet with different imposed policies. We have built and analyzed in 31 a game-theoretic model representing the interactions between users, network providers and content providers in this heterogeneous regulation context, and investigated the impact of two neutrality relaxation policies in a part of the world on all actors, compared with a fully-neutral network. Our results show that neutrality repeal may only favor the ISP in the differentiation-authorized zone, but no other actor, and that it can be worse off for everybody if the regulation procedures are very strict in the neutral area.

Monitoring neutrality. Network Neutrality is protected by law in many countries over the world, but monitoring has to be performed to ensure operators conform to the rules. The Wehe application, jointly developed by Northeastern University and the French regulator ARCEP, allows users to take measurements and analyze them to detect possible traffic differentiation. The paper 33 presents a test bed designed to evaluate the detection capacities of Wehe; by computing the detection probabilities and estimating the potential benefit of an operator willing to differentiate while avoiding detection, we fine-tune and compare the main differentiation types (throughput, packet loss and delay) that an operator could implement.

Neutrality of search engines. Neutrality should not be restricted to access providers: it concerns all other intermediaries between end users and content. Following this idea, the search neutrality debate has appeared from content or service providers complaining about being discriminated and therefore losing market shares due to an unfairly low ranking given by search engines. Those questions stress the need for methodologies and tools to verify bias in search engine rankings and analyze their potential impact. We have developed in 58 and the popularization paper 63 a simple yet effective framework comparing the results of existing search engines. We have presented statistical tests based on outlier detection pointing out potential biases, and introduce two meta engines aiming at reducing bias. All this is implemented in a publicly-available tool from which extensive comparisons and bias investigations are carried out.

Estimation of spectrum valuation for 5G dynamic frequency. The high data rates and diversity of services in 5G require a flexible and efficient use of all the available frequencies. In 5G networks, new approaches of dynamic spectrum sharing will be deployed, allowing Mobile Network Operators (MNOs) to access other incumbents’ spectrum, after obtaining a license from the regulator. The attribution of licenses will be made via auction mechanisms valid for given geographical areas and durations. To determine how to bid, each MNO has to estimate their valuation for spectrum i.e., how much they are willing to pay for it. In 34, we propose a model for estimating that valuation. The model is based on Markov chain modeling of user behavior, to compute the MNO satisfaction as a function of the obtained spectrum, and is illustrated by applying it to real operator data.

6.6 Monte Carlo

Participants: Bruno Tuffin, Gerardo Rubino.

We maintain a research activity in different areas related to dependability, performability and vulnerability analysis of communication systems, using both the Monte Carlo and the Quasi-Monte Carlo approaches to evaluate the relevant metrics. Monte Carlo (and Quasi-Monte Carlo) methods often represent the only tool able to solve complex problems of these types.

Central Limit Theorem for Randomized Quasi-Monte Carlo. Randomized quasi-Monte Carlo (RQMC) can produce an estimator of a mean (i.e., integral) with root mean-square error that shrinks at a faster rate than Monte Carlo's. While RQMC is often employed to provide a confidence interval (CI) for the mean, this approach implicitly assumes that the RQMC estimator obeys a central limit theorem (CLT), which has not been established for most RQMC settings. To address this, we have provided in 39, and extended in 60, various conditions that ensure an RQMC CLT, as well as an asymptotically valid CI, and examine the tradeoffs in our restrictions. Our sufficient conditions, based on the Lindeberg condition and depending on the regularity of the integrand, generally require that the number of randomizations grows sufficiently fast relative to the number of points used from the low-discrepancy sequence.

Gradient-based optimization and sensitivity analysis. The generalized likelihood ratio (GLR) method is a recently introduced gradient estimation method for handling discontinuities for a wide scope of sample performances. We have put in 40, 61 the GLR methods from previous work into a single framework, simplify regularity conditions for justifying unbiasedness of GLR, and relax some of those conditions that are difficult to verify in practice. Moreover, we have combineed GLR with conditional Monte Carlo methods and randomized quasi-Monte Carlo methods to reduce the variance. Numerical experiments show that the variance reduction could be significant in various applications.

Rare event simulation of regenerative systems. Consider the hitting time $T$ to a rarely visited set $A$ of a regenerative process $X$. Let $F$ be the cumulative distribution function (CDF) of $T$, and assume we want to estimate $F$, along with its $q$-quantile and conditional tail expectation (CTE). In various asymptotic settings, the distribution of $T/E\left[T\right]$ converges to an exponential as the set $A$ becomes rarer. Thus, we can approximate $F$ by an exponential with mean $E\left[T\right]$. As the mean $E\left[T\right]$ is unknown, we estimate it via simulation with measure-specific importance sampling to calibrate the approximation. This leads to our so-called exponential estimators of $F$ and the corresponding risk measures. Moreover, as $X$ is regenerative, we can write $T=S+V$, where $S$ is a geometric sum of lengths of cycles before the one that hits $A$ and $V$ is the time to hit $A$ in the first cycle that visits $A$. In various asymptotic settings, we also have that $S/E\left[S\right]$ converges weakly to an exponential. As $S$ and $V$ are independent, we can then write the CDF $F$ of $T$ as the convolution of the CDF $G$ of $S$ and the CDF $H$ of $V$. We then exploit this to construct so-called convolution estimators of $F$ and its corresponding risk measures. We have examined in 48 the behavior of the exponential and convolution estimators. Through simple models, we have shown that the weak convergence to an exponential may hold for $S/E\left[S\right]$ but not for $T/E\left[T\right]$. Thus, the convolution estimator may be valid, but the exponential estimator may not be. We have also discussed the bias of estimators. Indeed, for moderately rare events, bias could potentially surpass variance. For this reason, we have proposed other estimators, still based on the same regenerative principle, and have compared all of them numerically.

7.1 Bilateral contracts with industry

7.2 Bilateral grants with industry

8.1 International initiatives

8.2 National initiatives

9.1 Promoting scientific activities

9.2 Teaching - Supervision - Juries

9.3 Popularization

• Patrick Maillé and Bruno Tuffin published Neutralité du Net : l’Europe doit-elle déréguler en réponse aux États-Unis? in The Conversation.
• Gerardo Rubino makes regular presentations to high school students about the research work in general, and specific technical topics in particular. Current talks:
  • Randomness as a tool
  • Internet as a research problem
  • Great challenges in maths: the Riemann Hypothesis
  • Great challenges in math/computer science: the “P versus NP” problem

10.1 Major publications

• 1 articleE.Emmanuelle Anceaume and Y.Yann Busnel. A Distributed Information Divergence Estimation over Data Streams.IEEE Transactions on Parallel and Distributed Systems252February 2014, 478-487
  HALDOI
• 2 articleE.Emmanuelle Anceaume, Y.Yann Busnel and B.Bruno Sericola. Byzantine-tolerant Uniform Node Sampling Service in Large-scale Networks.International Journal of Parallel, Emergent and Distributed Systems365June 2021, 1-28
  HALDOI
• 3 articleY.Yassine Hadjadj-Aoul and T.Tarik Taleb. An adaptive fuzzy-based CAC scheme for uplink and downlink congestion control in converged IP and DVB-S2 networks.IEEE Transactions on Wireless Communications82Feb. 2009, 816--825
• 4 inproceedingsY.Yezekael Hayel, D.David Ros and B.Bruno Tuffin. Less-than-Best-Effort Services: Pricing and Scheduling.23rd IEEE Infocom ConferenceHong-Kong, ChinaMarch 2004
• 5 articleJ.Jerome Henry, N.Nicolas Montavont, Y.Yann Busnel, R.Romaric Ludinard and I.Ivan Hrasko. A Geometric Approach to Noisy EDM Resolution in FTM Measurements.Computers103March 2021, 33
  HALDOI
• 6 articleS.Sofiene Jelassi and G.Gerardo Rubino. A perception-oriented Markov model of loss incidents observed over VoIP networks.Computer Communications128September 2018, 80-94
  HALDOI
• 7 articleP.Patrice Leguesdron, J.Jean Pellaumail, G.Gerardo Rubino and B.Bruno Sericola. Transient analysis of the M/M/1 queue.Advances in Applied Probability253September 1993, 702--713
• 8 bookP.Patrick Maillé and B.Bruno Tuffin. Telecommunication Network Economics: From Theory to Applications.Cambridge University Press2014, 288
  HAL
• 9 articleS.Samir Mohamed and G.Gerardo Rubino. A study of real-time packet video quality using random neural networks.IEEE Trans. Circuits Syst. Video Techn.12122002, 1071--1083URL: https://doi.org/10.1109/TCSVT.2002.806808
  DOI
• 10 articleH.Hedi Nabli and B.Bruno Sericola. Performability analysis: a new algorithm.IEEE Transactions on Computers4541996, 491--494
• 11 inproceedingsP.Pranav Nerurkar, Y.Yann Busnel, R.Romaric Ludinard, K.Kunjal Shah, S.Sunil Bhirud and D.Dhiren Patel. Detecting Illicit Entities in Bitcoin using Supervised Learning of Ensemble Decision Trees.ICICM 2020 : 10th International Conference on Information Communication and ManagementParis, FranceACMAugust 2020, 25-30
  HALDOIback to text
• 12 articleB.Boris Oreshkin, N.Nazim Régnard and P.Pierre L'Ecuyer. Rate-Based Daily Arrival Process Models with Application to Call Centers.Operations Research6422016
  HAL
• 13 articleG.Gerardo Rubino and B.Bruno Sericola. A finite characterization of weak lumpable Markov processes. Part II: The continuous time case.Stochastic Processes and their Applications451993, 115--126
• 14 bookG.Gerardo RubinoB.Bruno TuffinRare Event Simulation using Monte Carlo Methods.John Wiley & Sons2009
• 15 articleA.Alassane Samba, Y.Yann Busnel, A.Alberto Blanc, P.Philippe Dooze and G.Gwendal Simon. Predicting file downloading time in cellular network: Large-Scale analysis of machine learning approaches.Computer Networks145November 2018, 243-254
  HALDOI
• 16 articleB.Bruno Tuffin. Bounded Normal Approximation in Highly Reliable Markovian Systems.Journal of Applied Probability3641999

10.2 Publications of the year

10.3 Other