Distributed Approaches for Graph-based Unsupervised Learning
Name: Konstantin Avrachenkov
Mail: K.Avrachenkov@inria.fr
Telephone: 04 92 38 77 51
Web page: http://www-sop.inria.fr/members/Konstantin.Avratchenkov/me.html
Place of the project: Inria Sophia Antipolis, Lagrange building
Address: 2004 Route des Lucioles, 06902
Team: NEO
Web page: https://team.inria.fr/neo/presentation/
Pre-requisites if needed: Good knowledge of probability theory;
some knowledge of machine learning or distributed computing is a plus;
knowledge of python is another plus.
Description:
Unsupervised learning is a type of machine learning tasks that draw
inferences from datasets consisting of input data without labeled responses
(no training set is given). The most common unsupervised learning method
is cluster analysis, which is used for exploratory data analysis to find
hidden patterns or grouping in data. It is very common to represent
dataset as a weighted graph where the weights correspond to some proximity
measure of two data points. There is a number of classical approaches
to unsupervised learning such as K-means, Principal Component Analysis
or spectral clustering. However, most of the classical approaches are not
easily distributed to make computations among distributed agents or on
a cluster of processing units. We feel that statistical physics methods
such as Gibbs sampling and Generalized Potts Model are particularly well
suited to design light complexity, distributed unsupervised machine
learning methods.
The project can accommodate two students. A student or students will do
both experimental and theoretical analysis of the Potts model based clustering
methods on various random graphs with community structure.
Scholarship is available to continue the project as a topic of PhD study.
References:
[1] Blatt, M., Wiseman, S. and Domany, E.
Clustering data through an analogy to the Potts model.
Advances in Neural Information Processing Systems, pp.416-422, 1996.
[2] Eaton, E. and Mansbach, R.
A Spin-Glass Model for Semi-Supervised Community Detection.
In Proceedings of AAAI 2012.
[3] Mezard, M. and Montanari, A., 2009. Information, physics, and computation.
Oxford University Press.
Optimization algorithms for Network Slicing for 5G
Advisors: Frédéric Giroire and Joanna Moulierac
This internship is also co-supervised by Jérémie Leguay, head of the Network and Traffic Optimization team at Huawei’s French Research Center (FRC) in Paris.
Emails: frederic.giroire@cnrs.fr, Joanna.moulierac@unice.fr
Laboratory: COATI project - INRIA (2004, route des Lucioles – Sophia Antipolis)
Web Site:
http://www-sop.inria.fr/members/Frederic.Giroire/
http://www-sop.inria.fr/members/Joanna.Moulierac/
http://jeremie.leguay.free.fr/
Pre-requisites if any:
Knowledge and/or taste for Networking
Knowledge and/or taste for discrete mathematics, linear programming, graph theory and/or combinatorial optimization
Description:
A network slice is a virtual network that is embedded on top of a physical network in a way that creates the illusion of the slice tenant of operating its own dedicated physical network. Network slicing is foreseen to be a key component of 5G to provision isolated and personalized network services to different applications (e.g., connected vehicles, smart factories).
A virtual link between virtual nodes can be realized as a multi-hop path with reserved bandwidth on all physical links constituting the path. A virtual node can implement specific network functions that can be installed on physical node (e.g., firewalls, DPI probes). Virtual links and virtual nodes can be easily established by a Software Defined Network (SDN) controller or network orchestrator.
The first step of the internship will be a thorough study of the research literature on network slicing with a focus on optimization methods used to map virtual networks on top physical resources. A starting point are the papers [1] and [2]. [1] presents the algorithmic aspects of slicing, while [2] proposes an Integer Linear program for the virtual network embedding problem. The idea is to learn how to model the problem from the ILP presented in [2] and to add specific constraints that are related to network slicing problem. We will need also to understand from the literature how the problem is generally decomposed and efficiently solved. The second step is the implementation of the optimization model within a solver such as ILOG CPLEX (available in Python, Matlab, C++, Java) and the design of efficient heuristics for larger instances.
The network of the future in Industry 4.0.
Name: Damien Saucez
Mail: damien.saucez@inria.fr
Telephone: +33 4 89 73 24 18
Web page: https://team.inria.fr/diana/team-members/damien-saucez/
Place of the project: Inria Sophia Antipolis
Address: 2004 route des Lucioles, 06902 Sophia Antipolis
Team: Diana
Web page: https://team.inria.fr/diana/
Pre-requisites if needed:
Description:
Industrial systems such as valve actuators, monitoring systems, or energy control
need specific communication mechanisms with real time, robustness, and safety
constraints and the failure of a communication can lead to catastrophes. This is why
factories and industrial units deploy a multitude of independent communication systems,
each one with different hardware and protocols as each system is designed specifically
for its usage and requirements.
With the advent of Industry 4.0 and thanks to the recent advances in commodity network
system, we are expecting to witness a progressive convergence of the communication systems
toward off-the-shelf standards coming from the Internet world. The drawback of Internet
technologies is that they don’t provide any form of guaranty such as delay, loss or safety
however, they provide bandwidth that are typically several order of magnitude higher than
industrial system and are cheap.
In this work, we will design a Software Defined Network (SDN) network to allow industrial
networks composed of multiple distinct physical systems to be merged on one single
multipurpose high speed Ethernet/IP based backbone. The student will first characterise
the main elements of industrial networks and protocols (e.g., deadline, delay constraints,
bandwidth, resiliency level). They will then propose a mapping model that defines how
the embedding of multiple independent real-time systems can be done in one unified
best-effort system. Finally, the student will validate their work either through formal
proof, numerical evaluation, simulations, or a real implementation.
Useful Information:
This work is part of a multi-year large project with a leading industrial partner (under NDA).
Knowledge in network protocols and architecture, and in embedded systems is a plus
but is not an absolute requirement.
What happens if we replace the Uber platform by a blockchain?
Name: Damien Saucez
Mail: damien.saucez@inria.fr
Telephone: +33 4 89 73 24 18
Web page: https://team.inria.fr/diana/team-members/damien-saucez/
Place of the project: Inria Sophia Antipolis
Address: 2004 route des Lucioles, 06902 Sophia Antipolis
Team: Diana
Web page: https://team.inria.fr/diana/
Description:
The Internet was thought to ease communications and it definitely outperformed the expectations to become the essential piece of our society. It was also thought to be distributed and independent but unfortunately almost 50 years after its debut we can say that it miserably failed with this objectives with only a few actors controlling the infrastructure and services. Recently we have indeed seen the emergence of platforms (a technology + an eco-system) such as Uber, Airbnb, or Doctolib that are all centralised. These platforms gain a major importance in our life and they are not centralised only for technological reasons but also for economical reasons as it eases the creation of monopoles or oligopoles and thus increase the power of the platform at the expenses of our freedom.
In contrast, the blockchain concept is emerging and promises the possibility to move back centralised systems to decentralised ones.
In this work, we will take the case of the centralised Uber platform and implement it using a blockchain. We will then study the technological and economical changes that such reorganisation would cause.
To achieve this goal, the student will first study the platforms to categorise and abstract them formally. They will then study the concept of blockchain and identify a blockchain that could be used to implement a platform. If such blockchain does not exist yet, they will design a new blockchain. Afterwards, the student will implement a proof-of-concept platform in a centralised way and on blockchain and study the differences.
As platform total eco-systems where the technology is just a part, the study will not be limited to the technological aspects but instead it will be extended to an economical study.
Useful Information:
The economical study will be performed in collaboration with researchers from the GREDEG (http://unice.fr/laboratoires/gredeg).
This work is part of a join IDEX project with the GREDEG.
ACQUA – A data-driven approach for network and Quality of Experience monitoring
Name: Chadi Barakat
Mail: Chadi.Barakat@inria.fr
Telephone: 04 92 38 75 96
Web page: http://team.inria.fr/diana/chadi/
Place of the project: Inria
Address: 2004, route des lucioles, 06902 Sophia Antipolis, France
Team: Diana
Web page: http://team.inria.fr/diana/
Pre-requisites if any: programming skills, network measurements, data analysis
Detailed description:
Context – ACQUA (http://project.inria.fr/acqua/) is a framework and mobile Application for prediCting Quality of User Experience at Internet Access. It is developed by the Diana team at Inria Sophia Antipolis – Méditerranée. ACQUA presents a new way for the evaluation of the performance of Internet access. Starting from network-level measurements as the ones we often do today (bandwidth, delay, loss rates, jitter, etc), ACQUA targets the estimated Quality of Experience related to the different applications of interest to the user without the need to run them (e.g., estimated Skype quality, estimated video streaming quality).
An application in ACQUA is a function, or a model, that links the network-level and device-level measurements to the expected quality of experience. Supervised machine learning techniques are used to establish such link between measurements both at the network level and the device level, and estimations of the Quality of Experience for different Internet applications. The required data for such learning can be obtained either by controlled experiments as we did in two recent communications on Skype and YouTube Quality of Experience [1,2], or by soliciting the crowd (i.e. crowdsourcing) for combinations (i.e. tuples) of measurements and corresponding application-level quality of experience.
The ACQUA mobile application is currently in its private beta test. This application is supposed to be on one hand the reference application for QoE forecasting for end users at their Internet access, and on the other hand, the feedback channel that allows end users to report to us (if they are willing) on their experience together with the corresponding network measurements so as to help us calibrating better and more realistic models. For this calibration, we are currently performing extensive, efficient and automatic measurements in the laboratory. We will count on end users to help us completing this dataset with further applications and more realistic network and user conditions.
Roadmap for the internship – The project comes with a long list of challenges ranging from adding new measurement features to analyzing the produced data and understanding the impact of network performance on Quality of Experience. In this internship, we want to focus on the QoE/network troubleshooting part by analyzing the crowd-sourced data. The current version of the application solicits users for their feedback, which is normally supposed to come when a QoE problem is experienced. By analyzing the data produced by the user’ own device and correlating these data with those produced by the other devices, we expect to shed light on the network status at the moment of the anomaly and pinpoint its root causes. We will be looking in this internship for techniques from the data science literature to perform this crowd-based troubleshooting and validate the sound of the obtained results. We will be also looking for technical solutions to carry the result of this troubleshooting back to the user so that it consists for him/her of a valuable incentive to provide feedback on his/her QoE. If the works in this internship goes smoothly, this new troubleshooting service is supposed to be added to the ACQUA application either directly or via a web interface that the user can consult.
This internship can lead to a PhD thesis if results are satisfactory and if funding is available.
References:
[1] Thierry Spetebroot, Salim Afra, Nicolas Aguilera, Damien Saucez, Chadi Barakat, “From network-level measurements to expected Quality of Experience: the Skype use case“, in proceedings of the IEEE International Workshop on Measurement and Networking (M&N), Coimbra, Portugal, October 2015.
[2] Muhammad Jawad Khokhar, Nawfal Abbasi Saber, Thierry Spetebroot, Chadi Barakat, “On active sampling of controlled experiments for QoE modeling“, in proceedings of ACM SIGCOMM Workshop on QoE-based Analysis and Management of Data Communication Networks (Internet-QoE), Los Angeles, August 2017.
Performance analysis and optimisation of distributed and parallel C++ codes
Advisor : Sid Touati (http://www-sop.inria.fr/members/Sid.Touati)
Grade : Professor, Université Côte d’Azur (emerged from Université
Nice-Sophia Antipolis)
Laboratory : INRIA Sophia Antipolis
Teams : KAIROS (https://team.inria.fr/kairos)
Email : Sid.Touati@inria.fr
Keywords : Efficient programming, code optimisation, object oriented
programming, distributed programming, parallel programming.
Stage-M2-Ubinet-2017-2018-Touati.pdf
Maintaining wireless sensor networks using drones and wireless power transfer
Name: Christelle Caillouet, Frédéric Giroire
Mail: christelle.caillouet@unice.fr, frederic.giroire@cnrs.fr
Telephone: +33 4 92 38 79 29
Web page: http://www-sop.inria.fr/members/Christelle.Molle-Caillouet/
http://www-sop.inria.fr/members/Frederic.Giroire/
Place of the project: COATI, joint project team between Inria and I3S lab
Address: Inria, 2004 route des lucioles, Sophia Antipolis
Team: COATI
Web page: https://team.inria.fr/coati/
Pre-requisites if needed: Linear programming, Algorithmic, Wireless Networks
Description: Wireless sensor networks are capable of periodically monitoring their vicinity and
reporting important information about the integrity and security of their
environment. The sensor nodes are powered by batteries and depending on how often
they take measurements and communicate with other devices, their energy may be
depleted fast. The replacement of the battery may be a hard task since the nodes
are often positioned in inaccessible places or the cost of replacement may be high.
To tackle this problem, a new technology has been recently developed by harvesting
energy from the transmitted RF signals. This technology uses a new type
of antenna which can convert part of the received signal power to electricity.
Depending on the transmitted power and the distance between the transmitting source
and the receiver, a node can harvest from some uW to some mW of power [1].
We assume that drones can fly over the sensor area and directionally emit energy towards
the ground nodes in order to recharge their battery. Taking into account the RF-power
harvesting limitations, the problem considered is to deploy drones while maintaining the
network operation for a given amount of time.
The guideline of the proposed project is the following :
* Bibliographic analysis of harvesting technology and related optimization models
* Development of a linear programming models for the above problem (related to [2]), taking
into account sensor's mobility and data collection.
* Development of approximation algorithms and/or distributed algorithms to efficiently
solve the problem for large instances.
* Implementation and analysis of obtained solutions.
Useful Information:
[1] Shashank Priya and Daniel J. Inman. 2008. Energy Harvesting Technologies (1st ed.). Springer Publishing Company
[2] Dimitrios Zorbas, Luigi Di Puglia Pugliese, Tahiry Razafindralambo, Francesca Guerriero, Optimal drone placement
and cost-efficient target coverage, In Journal of Network and Computer Applications, Volume 75, 2016, Pages 16-31
[3] D. Zorbas, P. Raveneau, Y. Ghamri-Doudane and C. Douligeris, "On the optimal number of chargers in battery-less
wirelessly powered sensor networks," 2017 IEEE Symposium on Computers and Communications (ISCC), Heraklion, 2017,
pp. 1312-1317.
Exploration d’insertion de méthodes formelles dans un flot de conception d’architecture SW
Name: Patricia Guitton
Place of the project: Renault
Stage_Archi_Preuve_formelle.xlsm
Composing Code Rewriting Directives
Name: Sébastien Mosser (I3S, Sophia), & remotely Laure Gonnord (LIP, Lyon)
Mail: mosser@i3s.unice.fr, laure.gonnord@ens-lyon.fr
Telephone: +334 92 96 50 58
Web page: http://www.i3s.unice.fr/~mosser/
Place of the project: I3S
Address: 930 route des colles (Polytech)
Team: SPARKS
Web page: http://sparks.i3s.unice.fr/
Pre-requisites if any: Good knowledge of Object-oriented programming
Detailed description: indicate the context of the work, what is
expected from the intern, what will be the outcome (software,
publication, …).
PDF version: http://laure.gonnord.org/pro/research/2018-rewritingcode.pdf
Rewriting code tools (e.g. Spoon [PMP+15]) that perform source-to-source transformations of a given program, are used everywhere, from code optimisation to automatic repairing, anti-pattern solving. However, all these tools face the same kinds of problems : how to deal with conflicting writes ? The general problem is the following : consider two rewriting rules ρ1 and ρ2, both to be applied to the very same program p. Each rule is defined as a function that takes as input a program, and produce another one according to its semantics. If ρ1 and ρ2 interfere (e.g., the former produces elements that will be rewritten by the latter), applying ρ1 then ρ2 does not yield the same program than applying ρ2 and then ρ1. We proposed in previous work [MBFD12] a commutative operator that complements the classical function composition operator (where ρ2 • ρ1(p) 6= ρ1 • ρ2(p)) with a parallel semantics. Using this operator (denoted as ||), applying both rules always yields the same result, i.e. the expected program or an error if the rules interfere. We propose here to enhance this work by analyzing what a conflict is from a code rewriting point of view, and how it can be anticipated and/or automatically solved. There are many instances of this problem : for instance, in the context of a recent collaboration with the Universite du Quebec a Montreal, has been proposed a set of energetic rewriting rules that permits to rewrite over-consuming android statements into less consuming ones. We can also cite the tool Alive [LMNR15] that performs peephole optimizations inside the LLVM compiler. Graph transformations has also investigated this problem by working on conflicting graph transformations identification and automated scheduling [MTR05, SVL15]. The TOM language is dedicated to code rewriting [BBK+07], and the Coccinelle approach address a similar problem with flow-based program matching [BDH+09]. We propose to explore this problem from an innovative point of view, considering techniques designed by the compilation and formal method community to complement the existing software engineering approaches
In this internship, we propose to formalize the notion of code rewriting in the specific context of program refactoring [Fow99]. The idea is to (i) implement program rewriting rules to support refactoring directives, (ii) formally analyze theses rule definitions according to different methods and (iii) define an empirical benchmark that measure the accuracy of the conflict detection mechanisms when applied to real-life programs. We might find inspiration in paper coming from communities such as package systems, code rewriting, sat-solving, and for the “optimisation” problem from logic (unsat/sat core), operational research (with the good encoding and a reasonable objective function), ...The expected result is a prototype that demonstrates main refactoring rules applied simultaneously to reference programs, and to confront theoretical results with empirical benchmarks.
References: set of bibliographical references (article, books, white papers, etc) to be read by the student before starting to work on this subject
[BBK+07] Emilie Balland, Paul Brauner, Radu Kopetz, Pierre-Etienne Moreau, and Antoine Reilles. Tom : Piggybacking rewriting on java. In Conference on Rewriting Techniques and Applications - RTA’07, volume 4533 of LNCS, pages 36–47, Paris/France, France, June 2007. Springer-Verlag.
[BDH+09] Julien Brunel, Damien Doligez, Rene Rydhof Hansen, Julia L. Lawall, and Gilles Muller. A foundation for flow-based program ´ matching : Using temporal logic and model checking. SIGPLAN Not., 44(1) :114–126, January 2009.
[Fow99] Martin Fowler. Refactoring : Improving the Design of Existing Code. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999.
[LMNR15] Nuno P. Lopes, David Menendez, Santosh Nagarakatte, and John Regehr. Provably correct peephole optimizations with alive. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’15, pages 22–32, New York, NY, USA, 2015. ACM.
[MBFD12] Sebastien Mosser, Mireille Blay-Fornarino, and Laurence Duchien. ´ A Commutative Model Composition Operator to Support Software Adaptation, pages 4–19. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
[MTR05] Tom Mens, Gabriele Taentzer, and Olga Runge. Detecting structural refactoring conflicts using critical pair analysis. Electronic Notes in Theoretical Computer Science, 127(3) :113 – 128, 2005. Proceedings of the Workshop on Software Evolution through Transformations : Model-based vs. Implementation-level Solutions (SETra 2004).
[PMP+15] Renaud Pawlak, Martin Monperrus, Nicolas Petitprez, Carlos Noguera, and Lionel Seinturier. Spoon : A library for implementing analyses and transformations of java source code. Software : Practice and Experience, 46 :1155–1179, 2015.
[SVL15] Eugene Syriani, Hans Vangheluwe, and Brian LaShomb. T-core : a framework for custom-built model transformation engines. Software & Systems Modeling, 14(3) :1215–1243, Jul 2015.
Optimizing jointly Data Center Servers and Network
Contact: Stéphane Pérennes.
Emails: stephane.perennes@cnrs.fr.
Phone: 04 92 38 50 98
Laboratory: INRIA Sophia Antipolis, COATI team-project, https://team.inria.fr/coati/
Context
Software-defined or Software-Driven Networks (SDN) is a new networking paradigm enabling innovation, centralization of network management and preventing the so-called ossification of the Internet. SDN decouples the control plane from the data plane in network equipments, which means that a switch or a router is transformed into a simple forwarding device that applies rules sent by a remote controller using a normalized protocol. This simple approach allows network administrators to get a better control on the traffic in their network, e.g., Google has recently presented an SDN-based re-design of its core backbone where it is able to reach nearly 100% utilization of links under stringent QoS constraints [1]. SDN also enables the academic community to experiment with flexible as well as high performing equipments to test new or existing protocols. The OpenFlow protocol is the leading instantiation of the SDN concept at the moment and is supported by major manufacturers, e.g., HP, Juniper, IBM as well as open-source virtual switches like Open vSwitch [2], which is at the heart of cloud management solutions like OpenStack [3]. In particular, the SDN technology allows to optimize dynamically the placement of tasks in servers which are executed by virtual machines and of routes in networks.
Objective
We consider the problem of optimizing jointly the servers and network of a datacenter. A data center has a set of tasks to be executed by the servers (backup, computations, gaming, video streaming). Some of these tasks (backup, video streaming, computation with map reduce) generate some traffic which has to be routed throughout the data center networks.
We consider the problem of jointly affecting the tasks to servers and the network demands to routes in a network with limited capacity in order to minimize the time to carry out all the tasks.
Requirements: taste for algorithmics and network optimization.
This internship is research oriented.
References
[1] JAIN, S. et al, B4: experience with a globally-deployed software defined wan. In Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM (SIGCOMM '13). ACM, New York, NY, USA, 3-14.
[2] http://openvswitch.org/
[3] http://www.openstack.org/
ElectroSmart: Revealing your exposition to the electromagnetic waves
Name: Arnaud Legout (Inria)
Mail: arnaud.legout@inria.fr
Telephone: 04 92 38 78 15
Web page: http://www-sop.inria.fr/members/Arnaud.Legout/
Place of the project: Inria Sophia Antipolis
Address: 2004 route des Lucioles
Team: DIANA
Web page: https://team.inria.fr/diana/
Pre-requisites if needed: Python programming, Android programming,
Statistical analysis (depending on the task)
Description:
The Internet and new devices such as smartphones have fundamentally
changed the way people communicate, but this technological revolution
comes at the price of a higher exposition of the general population to
microwave electromagnetic fields (EMF). This exposition is a concern
for health agencies and epidemiologists who want to understand the
impact of such an exposition on health, for the general public who
wants a higher transparency on its exposition and the health hazard it
might represent, but also for cellular operators and regulation
authorities who want to improve the cellular coverage while limiting
the exposition. Despite the fundamental importance to understand the
exposition of the general public to EMF, it is poorly understood
because of the formidable difficulty to measure, model, and analyze
this exposition.
The goal of the ElectroSmart project is to develop the instrument,
methods, and models to compute the exposition of the general public to
microwave electromagnetic fields used by wireless protocols and
infrastructures such as Wi-Fi, Bluetooth, or cellular.
We currently have an Android application deployed in Google Play that
makes measurements of electromagnetic waves. We have 33 000 downloads,
a mark of 4.6/5, and 350 million measurements. We have a team of 5
persons working full time on the project and we are in the process of
creating a startup. This internship will take place in that context. We can
propose a broad spectrum of subjects that we will adapt depending on
the competencies of the candidate. Possible subjects are: i) making
data science on the huge amount of collected data to understand the
exposition of persons (requirements: Python, statistical analysis),
ii) make android development to improve the ElectroSmart application
(requirements: Android), iii) contribute to calibration experiments in
an anechoic chamber (requirements: Electromagnetic fields knowledge,
physical experimental skills)
You can find details on the ElectroSmart project on
https://es.inria.fr/
Useful Information:
This internship can be continued with a Ph.D. thesis or
engineering position for excellent candidates.
Routing in multimodal networks with bicycles
Name: David Coudert, Nicolas Nisse
Mail: david.coudert@inria.fr, nicolas.nisse@inria.fr
Telephone: +33 4 92 38 79 81
Web page: http://www-sop.inria.fr/members/David.Coudert/
http://www-sop.inria.fr/members/Nicolas.Nisse/
Place of the project: COATI, joint project team between Inria and I3S lab
Address: Inria, 2004 route des lucioles, Sophia Antipolis
Team: COATI
Web page: https://team.inria.fr/coati/
Pre-requisites: Graph theory, Algorithmic, Optimization
Description: Mobility is an important aspect of smart-cities and there is a growing demand for services offering efficient itinerary planning. Typically, a traveler wants to be informed of the best ways to reach its destination, using any combination of the possible means of transportation (buses, tram, metro, bicycles, etc.), and with a simple query. The main difficulty of such multi-modal itinerary computation, apart from the number of possibles modes of transportation that have to be combined, is to propose realistic itineraries. Indeed, if the announced travel-time of an itinerary is 15min and that the real travel-time is 25min, the traveller is right to be unhappy.
Nowadays, even in major French cities where real-time data are available on all channels, itinerary calculations are always based on theoretical timetables (e.g., in Paris). Therefore, the proposed itinerary does not take into account the actual state of the network (delay of a bus, traffic jam, unavailability of a bicycle, etc.), and the announced travel-time is often underestimated. In medium-scale cities (e.g., Nice), better solutions are now proposed. For instance, SMEs like Instant-System integrates and continuously refreshes the position of all buses, subways, trams, etc. on the network and uses them in the itinerary calculations. Nonetheless, the proposed solution is not scalable and many improvements are necessary.
Objectives:
The goal of this internship is to study and develop algorithms for computing itineraries combining bicycle (e.g., vélo bleu, vélib’) and walk (and possibly other transportation means). The main objective is to better estimate the overall travel-time, taking into account: the cycling speed of the user, the probability that a bicycle is available at a station and that a slot will be free to return it, the number of red-lights along the path, the slope, etc. The first task is thus to compare existing algorithms both theoretically and experimentally.
The long term objectives of this internship are to design new algorithms offering better tradeoffs between pre-processing time, query-time, flexibility to handle events (blocked street, etc.), quality of the proposed itinerary, gap with real travel-time, specific constraint such as forbidden areas, computation of alternate routes, etc. Electric bicycles will require a particular attention.
This project will be done in the context of a collaboration with SMEs Instant-System (http:// www.instant-system.com) and Benomad (http://www.benomad.com).
References:
[1] H. Bast et al.: Route Planning in Transportation Networks. https://arxiv.org/pdf/1504.05140, 2015
[2] S. Storandt: Route Planning for Bicycles - Exact Constrained Shortest Paths made Practical via Contraction Hierarchy. ICAPS 2012
[3] R. Geisberger, C. Vetter: Efficient Routing in Road Networks with Turn Costs. SEA’11.
[4] D. Delling, A. Goldberg, T. Pajor, R. Werneck: Customizable Route Planning. Transportation Science, INFORMS, 2015.
[5] M. Baum, J., T., D. Wagner: Energy-Optimal Routes for Electric Vehicles. ACM SIGSPATIAL 2013.
[6] M. Baum, J. Dibbelt, L. Huebschle-Schneider, T. Pajor, and D. Wagner: Speed-Consumption Tradeoff for Electric Vehicle Route Planning. ATMOS’14.
[7] A. Kosowski, L. Viennot: Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. SODA 2017: 1462-1478
Enhancing urban mobility with shared on-demand services
Name: David Coudert, Nicolas Nisse
Mail: david.coudert@inria.fr, nicolas.nisse@inria.fr
Telephone: +33 4 92 38 79 81
Web page: http://www-sop.inria.fr/members/David.Coudert/
http://www-sop.inria.fr/members/Nicolas.Nisse/
Place of the project: COATI, joint project team between Inria and I3S lab
Address: Inria, 2004 route des lucioles, Sophia Antipolis
Team: COATI
Web page: https://team.inria.fr/coati/
Pre-requisites: Good knowledge of graph algorithms and combinatorial optimization, programming languages Java, C/C++, Python.
Description: We are interested in enhancing the mobility of citizens in urban areas by providing them, through a unique interface enabling to express their preferences, the most convenient transportation means to reach their destinations. The proposed itinerary may combine several of the many available means of transportation (buses, tram, metro, shared bicycles, carpooling, etc.). The complexity of computing such multimodal itinerary comes from the variety of the possible modes of transportation that have to be combined. Moreover, we want to enable the design of a mobility companion (a mobile application) able not only to guide the user along her journey, including when and how to change of transportation mean, but also to propose itinerary changes when the current one exceeds a threshold delay.
To this end, we collaborate with SME Instant-System that designs, commercializes and operates a multimodal platform including: the traveler’s real-time information on public transport; a multimodal trip planner; the integration of carpooling in metropolitan area, so for short trips; associated smartphone app and web sites. The real time trip planner is a very innovative technological brick. Indeed, even in major French networks where real-time data is available on all channels, trip calculations are always based on theoretical timetables (this is for instance the case in Paris). In fact, in a mobile situation, the proposed trip does not take into account the actual state of the network. To overcome this issue, Instant-System integrates and continuously refreshes the position of all bus, subway, streetcar on the network and uses them in the trip calculations.
Objectives:
In this context, we aim at studying and developing algorithms for a new form of shared on-demand services. With an Uber-like on-demand service, a user quickly gets a fast solution to reach her destination, but she has to pay a high price. With shared on-demand services, the system assigns several passengers to a vehicle to share expenses, and optimizes the routes of the vehicles so as to satisfy users constraints while optimizing operator’s costs. The quality of service for passengers is lower (longer trips) but the price is reduced. This shared mode is different from carpooling since here the route of a vehicle is optimized for its passengers.
We will investigate the algorithmic solutions enabling a city to operate such service as part of its PT offer, including constraints related to the rights and preferences of drivers. We may also study the societal and economical aspects of such service and its possible impact on the global organization of the PT offer.
This project will be done in the context of a collaboration with SME Instant-System (http:// www.instant-system.com) and UMR ESPACE (http://www.umrespace.org/).
References:
[1] H. Bast et al.: Route Planning in Transportation Networks. https://arxiv.org/pdf/1504.05140, 2015
[2] J.-F. Cordeau, G. Laporte. The Dial-A-Ride Problem: models and algorithms. Annals of Operations Research, 153(1):29-46, 2007.
[3] G. Berbeglia, J.-F. Cordeau, G. Laporte. Dynamic pickup and delivery problems. European Journal of Operational Research, 202(1):8-15, 2010.
[4] R. Masson, F. Lehuédé, O. Péton. The Dial-A-Ride Problem with Transfers. Computers \& Operations Research, 41:12-23, 2014.
[4] T. Garaix, C. Artigues, D. Feillet, D. Josselin. Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation. Computers \& Operations Research / Computers and Operations Research, Elsevier, 2011, 38 (10), pp.1435-1442.
Model Checking for open concurrent systems.
Name: Eric Madelaine
Mail: eric.madelaine@inria.fr
Telephone: 04 92 38 78 07
Web page: http://www-sop.inria.fr/members/Eric.Madelaine
Place of the project: INRIA
Address: Sophia-antipolis
Team: Kairos
Web page: https://www.inria.fr/equipes/kairos
Pre-requisites if any: Knowledge of formal methods, verification, logics.
Detailed description: indicate the context of the work, what is
expected from the intern, what will be the outcome (software,
publication, ...).
Context: We have developed a new semantic framework for the analysis of composition operators in
concurrent systems. Open pNets (parameterized networks of synchronized automata) are new
semantic objects used to define in a symbolic way the semantics of composition operators, but also of
various type of "open" programs, like parallel and distributed programming skeletons, or generic
distributed algorithms. We define the operational semantics of open pNets, using "open transitions",
and "open automata" that include symbolic hypotheses on the behavior of the pNets "holes". Data in
pNets and in open transitions is handled symbolically, using logical predicates, and reasoning on pNets
behaviours is done by using an SMT solver dealing with these predicates.
One important tool for the analysis of concurrent systems is Model Checking (MC), that is checking
whether some property expressed as a temporal logic formula is valid on the states of a (finite) model
of its behaviour. Building a Model Checker for pNets (more precisely for open automata) has a
challenging perspective to build a finite algorithm for checking properties of systems involving
unbounded data. Typical MC algorithms are traversing the model (together with the formula),
matching each action in the model transitions with "actions predicates" in the formula. For open
transitions, matching could be (naively) replaced by checking the satisfiability of a formula, using
a Satisfiablity Modulo Theories (SMT) solver. The main difficulties with this approach is that a positive
reply from an SMT solver gives an instantiation of the predicate variables validating the formula, not
all possible instantiations, and that each instantiation would correspond to a specific unfolding of the
automaton for the next step.
Subject: after familiarization with the pNet framework and with classical MC algorithms, the objective
of the work is to answer some of the following questions:
‐ is it possible to define a (bounded) MC algorithm using satisfiability on individual open transitions,
through a finite "unfolding" of the open automaton based on the results provided by the SMT solver?
‐ is it possible, based on the predicates in the transitions, to construct an abstract unfolding (that may
be finite in some cases)?
‐ is it possible to delay the satisfiability checking, simply assembling the predicates along the way, and
submit it only at the end? (hint: for this we may need to define some restrictions on the structure of
the pNets to get termination) ?
‐ is it possible to achieve one of the above compositionally, which is by working with sub‐components
of an open pNet, instead of using the composed open automaton?
and (eventually) to define / implement a prototype.
More details: http://www‐sop.inria.fr/members/Eric.Madelaine/stages2017/MC‐pNets.pdf
References: set of bibliographical references (article, books, white papers, etc) to be read by the student before starting to work on this subject
On open pNets: "A Theory for the Composition of Concurrent Processes": https://hal.inria.fr/INRIA/hal‐01271684v1
On expressiveness of closed and open pNets: "pNets: an Expressive Model for Parameterised Networks
of Processes", https://hal.inria.fr/INRIA/hal‐01139432v1
On Model-checking: any textbook... e.g.:
E. M. Clarke, O. Grumberg and D. A. Peled. Model Checking. MIT press, 1999.
Building a resilience methodology for NFV/SDN
Name: Andrea Tomassilli, Stéphane Pérennes
Mail: andrea.tomassilli@inria.fr
Telephone: +33 4 92 38 79 29
Web page: http://www-sop.inria.fr/members/Andrea.Tomassilli
Place of the project: COATI, joint project team between Inria and I3S lab
Address: Inria, 2004 route des lucioles, Sophia Antipolis
Team: COATI
Web page: https://team.inria.fr/coati/
Pre-requisites if needed: Linear programming, Algorithmic
Context
Network function virtualisation (NFV) has taken off since the publication of a White Paper in 2012 by 13 telecommunications operators [1]. This document emphasizes the need to run network functions on commoditized hardware platforms (COTS), and exploit the achievements of the IT community in the knowledge and operation of Cloud to minimize the costs of investment (CAPEX) and operations (OPEX), and to maximize the flexibility and responsiveness of digital service providers.
In parallel, software defined networking (SDN) was developed through the creation of abstraction layers and the centralization of network equipment controls. Central to this approach is the controller representing the decisional part, which is separated from the operational part. Communication protocols, e.g., OpenFlow, have been proposed in order to foster the dialogue between the control and data planes using APIs. This concept of dynamic management of network resources can be judiciously utilized for applications hosted in the Cloud.
Even if NFV is independent from SDN, the expected trend is to exploit the SDN approach in NFV architectures by using different possible patterns for switches or routers: as physical or virtualised resources, as virtualised functions, ...
These promising initiatives for the operators face, among others, non-functional requirements such as QoS and resilience criteria of the Telco world that are far more demanding compared to those of the IT environment. The results obtained to date are short-term ones, e.g., adapting resilience aspects known within the physical network functions universe to the NFV world: fault detection in the different layers of the architecture, availability estimation of an end-to-end network service, impact of the upgrade/update on service continuity are some examples.
Objectives
The internship objective is the development of a resilience methodology [5] linking theoretical results to industrial implementation. VNFs deployment should take into account the failures that occur in an operator network or a data center [11-14]. It is thus planned to study how to place these functions in order to be tolerant to links or node failures, while maintaining a good QoS. For this purpose, combinatory optimization methods will be used to find optimal solutions, when it is possible, or good solutions in other cases, for the VNFs placement.
References
[1] M. Chiosi et al., “Network functions virtualization - Introductory White Paper”, SDN and OpenFlow World Congress, 2012
[2] ETSI, “Resiliency requirements”, ETSI GS NFV-REL 001 V1.1.1, January 2015
[3] anr-disco.ens-lyon.fr
[4] anr-reflexion.telecom-paristech.fr
[5] M. Scholler et al. "Resilient deployment of VNFs", 5th IEEE International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2013
[6] R.C. Turchetti, and E.P. Duarte Jr., "Implementation of failure detector based on NFV", IEEE International Conference on Dependable Systems and Networks Workshops (DSN-W), 2015
[7] M. Xia et al. "Resource optimization for service chain monitoring in SDNs", 4th IEEE European Workshop on SDNs (EWSDN), 2015
[8] S. Rajagopalan, D. Williams, and H. Jamjoom, "Pico replication: a high availability framework for middleboxes", 4th ACM Annual Symposium on Cloud Computing (SOCC'13), 2013
[9] M. Miyazawa, M. Hayashi, and R. Stadler. "vNMF: Distributed fault detection using clustering approach for NFV", IFIP/IEEE International Symposium on Integrated Network Management (IM), 2015
[10] J. Fan et al. "GREP: guaranteeing reliability with enhanced protection in NFV", ACM SIGCOMM Workshop on Hot Topics in Middleboxes and NFV, 2015
[11] P. Veitch, M.J. McGrath, and V. Bayon, “An instrumentation and analytics framework for optimal and robust NFV deployment”, IEEE Communications Magazine, 53(2), 2015, 126-133
[12] F. Machida, K. Masahiro, and M. Yoshiharu, "Redundant virtual machine placement for fault-tolerant consolidated server clusters", IEEE Network Operations and Management Symposium (NOMS), 2010
[13] M.C. Luizelli et al. "Piecing together the NFV provisioning puzzle: efficient placement and chaining of VNFs", IFIP/IEEE International Symposium on Integrated Network Management (IM), 2015
[14] S. Song et al., “NEOD: network embedded on-line disaster management framework for SDN”, IFIP/IEEE International Symposium on Integrated Network Management (IM), 2013
[15] A. Verma et al., “Large-scale cluster management at Google with Borg”, EuroSys, 2015
[16] github.com/Netflix/Hystrix
Modularity of hypergraphs
Name: Dieter Mitsche and Konstantin Avrachenkov
Mail: dmitsche@gmail.com; k.avrachenkov@inria.fr
Telephone: 04 92 38 77 51
Web page: http://math.unice.fr/~dmitsche/
http://www-sop.inria.fr/members/Konstantin.Avratchenkov/me.html
Place of the project: LJAD (or Inria Sophia Antipolis, but LJAD
is preferred)
Address: Parc Valrose
Team: LJAD
Web page: http://math.unice.fr/
Pre-requisites if any: Knowledge of probability and basic graph theory is desirable;
Knowledge of Python is a plus.
Detailed description:
Modularity of graphs is a widely used and well understood concept for clustering the set of vertices. Hypergraphs are natural generalisations of graphs allowing for relations between more than two vertices. For hypergraphs however, the concept of modularity is not well understood, and different definitions exist. In this project, we are given a data set of WTO data about bilateral and plurilateral commercial agreements between countries. This data set will then be related to the amount of import and export flow data between countries in order to draw conclusions about the effect of agreements on the economy.
The goal of this project is to first run an existing algorithm for graph modularity on the graph resulting from the 2-section of the given hypergraph data set. Next, different hypergraph modularitiy definitions should be implemented and run on the given data set. The quality of the different modularities can then be assessed by the amount of export/import flow captured by the clustering produced by each definition. Hopefully, the final conclusion will be such that a sutiably defined hypergraph modularity outperforms typical graph modularity.
Smart IOT for Mobility
Name: Frederic Mallet
Mail: Frederic.Mallet@unice.fr
Telephone: 04 92 38 79 66
Web page: http://www-sop.inria.fr/members/Frederic.Mallet/
Place of the project: INRIA Lagrange
Address: 2004 route des Lucioles
Team: Kairos
Web page: https://team.inria.fr/kairos/
Pre-requisites if any:
Detailed description:
The Project SMART IoT for Mobility is funded by the Academy RISE of UCA and must study the use of Smart Contracts in relationship with Renault Software Lab and Orange on a project of a rental of connected vehicles in a multimodal scenario.
This project is the prelude of an ANR Project intended to fund a PhD. This internship should explore solutions to use smart contracts in the context of a mobile vehicular network. The students is expected to study the state of the art in the modeling of vehicular network, in the area of smart contracts, in the verification of smart contracts. The result should be a research report that describes the state-of-the-art in the domain. If the internship is successful the student will be offered the possibility to perform a PhD thesis in direct relation with Renault Software Lab.
The work is done in collaboration with people from the legal department of Gredeg that are specialized in the legal issues for IoT systems. One expected outcome of the ANR project is to be able to provide a formal language to model the contracts between the different partners (Car manufacturer, Telecom provider, customers, Third-Tiers of Car Manufacturers) and be able to perform simulation and verification of the interactions among them.
Reasoning on Smart Contract Deployment on Variable Platforms
Name: Philippe Collet
Mail: Philippe.Collet@unice.fr
Telephone: +33 4 92 96 51 08
Web page: http://www.i3s.unice.fr/Philippe_Collet/
Place of the project: I3S Laboratory (UNS - UCA / CNRS UMR 7271)
Address: Campus SophiaTech / Les Templiers 1 (4th floor)
930 Route des Colles, BP 145
F-06903 Sophia Antipolis Cedex, France
Team: SPARKS
Web page: http://sparks.i3s.unice.fr/
Detailed description:
SmartIoT for Mobility is a project recently funded by the RISE academy of the Université Côte d'Azur. An additional funding for 3 years is under evaluation by the french agency for research (ANR). The aim of the project is to explore a trans-disciplinary approach for enabling the new economy based on smart contracts, for the rising generation of the Internet of Things. The focus is to be able to have a clearer, more formal definitions of these smart contracts, compatible with a legal viewpoint while being mechanizable, i.e. checked for their consistency, deployed with appropriate agents on variable platforms.
In this context, the aim of the proposed internship is to provide a reasoning framework that enables to:
- take as input a description of a smart contract to be deployed and a representation of the diversity of the possible deployment platforms through a variability model
- reason on the functional matching between a high-level contract and the probes or agents that would be deployed on potential platforms
- while following a decomposable approach (the contract is broken into sub-parts and the reasoning result is composed back)
The framework will rely on an abstract model of contract, determined by a study of the recent state of the art. Previous work in the research team on code deployement on heterogeneous infrastructures will also help in tackling the problem, while classic variability modeling and checking techniques (e.g. SAT solving) are likely to be used for the reasoning part.
This internship aims at providing scientific results on a first reasoning model, together with a proof-of-concept prototype. Together, they should make up enough material for a scientific publication.
References:
- Clack, Christopher D., Vikram A. Bakshi, and Lee Braine. "Smart contract templates: foundations, design landscape and research directions." arXiv preprint arXiv:1608.00771 (2016).
- Cyril Cecchinel, Sébastien Mosser, Philippe Collet: Automated Deployment of Data Collection Policies over Heterogeneous Shared Sensing Infrastructures. APSEC 2016: 329-336
- Cyril Cecchinel, Sébastien Mosser, Philippe Collet: Software Development Support for Shared Sensing Infrastructures: A Generative and Dynamic Approach. ICSR 2015: 221-236
- I. Ayala, M. Amor, L. Fuentes and J. M. Troya, A Software Product Line Process to Develop Agents for the IoT, In International Journal of Sensors, pp 15640-15660, 15 (2015)
- Eretheum White Paper : Buterin, Vitalik. "A next-generation smart contract and decentralized application platform." (2014).
- Mathieu Acher, Philippe Collet, Alban Gaignard, Philippe Lahire, Johan Montagnat, Robert B. France:
Composing multiple variability artifacts to assemble coherent workflows. Software Quality Journal 20(3-4): 689-734 (2012)
Applying machine learning techniques to graph partitioning
Name: Fabrice Huet
Mail: fabrice.huet@unice.fr
Telephone: +33 4 92 94 26 91
Web page: https://sites.google.com/site/fabricehuet/
Place of the project: I3S Laboratory, Sophia Antipolis
Address: 2000 route des lucioles
Team: Scale
Web page: https://scale-project.github.io/
Pre-requisites if needed: Motivation for reading papers and learning new programming languages
Description:
A lot of data is represented in graphs which are often too large to be loaded and processed on one machine.
A common approach to perform computation on large graphs is to partition them into smaller sub-graphs. These
sub-graphs can then be processed by different machines. Depending on the algorithm (PageRank, Shortest Path...), some
communication will take place during execution. Partitioning the graph is a problem in itself, with already a lot of
different solution. They can be classified into two different approaches, whether we place the edges (aka vertex-cut based)
the vertices (edge-cut based) on the different machines. The partitioning can have a major impact on the execution time
of an algorithm so using the best one is of paramount importance. However, there is no single best partitioner. It depends
on a lot of different parameters, including the graph considered and the algorithm executed.
In a previous work (https://hal.inria.fr/hal-01401309), we have investigated which metrics were the most significant for
choosing the best partitioning using a linear model. We want to pursue this work in the context of machine learning and
see if we can achieve better results. Overall, we want, given a tuple (graph, algorithm, environment), predict which
partitioner will lead to the best performance. Of course the graph, the algorithm and the environment will be
represented by carefully chosen metrics.
During the PFE we have started investigating the use of ML techniques. In practice, some metrics are first
computed on the graphs and are used as input of the model. These metrics can be divided into two categories. The first
ones are called basic metrics and only depend on the graph. For example it can be the number of vertices, edges,
average degree... The second ones, called partitioned, depend on the partitioning (e.g average partition size, number
of cut vertices...). Based on these metrics we can predict with some accuracy which partitioner will lead the best
results.
The drawback with this approach is that it requires partitioning the graph and computing the partitioned metrics, which
can be a very expensive operation. Having enough data to train our models is thus time consuming. The goal of this
internship is to investigate how we speed-up the construction of training sets. We want to investigate two different
approaches:
- Computing the metrics on a sample of the original graph
- Expanding the set of basic metrics to make the partitioned metrics unnecessary.
Useful Information:
https://hal.inria.fr/hal-01401309
https://spark.apache.org/graphx/
Learning algorithms parallelization strategies on Jetson TX2 embedded modules
Name: Johan Montagnat
Mail: johan.montagnat@cnrs.fr
Telephone: 04 92 96 51 03
Web page: http://www.i3s.unice.fr/~johan
Place of the project: I3S
Address: Templiers 1 building, 930 route des Colles, 06903 Sophia Antipolis
Team: SPARKS
Web page: http://sparks.i3s.unice.fr
Pre-requisites if needed: knowledge of TensorFlow or Caffe learning frameworks is appreciated
Description:
Neural networks, and in particular deep learning algorithms, require very significant computing power. GPUs are increasingly used to tackle the computing burden generated and dedicated architectures are now available. Heavyweight computing infrastructures are not always available through. NVidia Jetson modules are an example of embedded computing platforms exploiting GPUs to achieve a very high performance to cost ratio that can address some of the learning algorithms requirements. Exploiting several Jetson modules in parallel could further improve performance in constrained environments, but it raises specific challenges related to the limited memory available on each module, the need to split large neural networks over several units, and the data exchanges needed.
This traineeship aims at studying strategies for implementing large deep learning networks on multiple Jetson TX2 embedded computing platforms interconnected through regular gigabit ethernet. The work will be based on the exploitation of deep learning frameworks such as TensorFlow or Caffe. Different network splitting strategies will be considered, taking into account the limited memory capacity of each module. Communication bottlenecks between interconnected modules and achievable performances will be studied. Experiments will be based on the "deep patient" network used for predicting medical conditions from a database of medico-administrative records.
Tasks:
- Bibliography on neural networks parallelization strategies
- Hands on Jetson TX2 modules programming
- Implementation of selected network parallelization strategy(ies)
- Experiment design and benchmarking with the deep patient workflow
References:
- https://www.semanticscholar.org/paper/Are-Very-Deep-Neural-Networks-Feasible-on-Mobile-D-Rallapalli-Qiu/d7896d6be118386a1f76f389210ca4e3a87b0d4a
- https://arxiv.org/abs/1404.5997
- http://engineering.skymind.io/distributed-deep-learning-part-1-an-introduction-to-distributed-training-of-neural-networks
- http://dudleylab.org/wp-content/uploads/2016/05/Deep-Patient-An-Unsupervised-Representation-to-Predict-the-Future-of-Patients-from-the-Electronic-Health-Records.pdf
- http://www.deeplearningbook.org/
Design and tests of streaming strategies for Virtual Reality
Advisors : Lucile Sassatelli, Ramon Aparicio-Pardo, Anne-Marie Pinna-Déry
Emails : {first.last}@unice.fr
Laboratory : I3S, SigNet and S3 groups (2000, route des Lucioles – Sophia Antipolis)
Description :
VR is growing fast with different companies rolling out cheap and not-so-cheap head-mounted sets in early 2016, from dedicated headsets like Oculus Rift and HTC Vive down to smartphone-dependent headsets (e.g., Samsung Gear VR, Google Cardboard and alike, to watch the phone screen an inch away from the eyes with magnifying lenses). VR platforms are also on the rise, such as YouTube 360 (YT 360) for distribution or Daydream presented at the last Google I/O conference in May 2016.
On the one hand, VR represents a tremendous revolution in the user’s experience, but VR also entails a daunting challenge for streaming transmission over the Internet (that is, Youtube-like, without download). The bit rates entailed by 360° videos (even H.265-compressed) are indeed much higher than for conventional videos (immersive smartphone apps [1] require about 28Mbps). These network speeds are hardly available in home accesses (of ADSL-type), forcing to offer the download option to avoid interruptions and low definitions. To tackle the challenge of streaming VR, a pre-selection of portions of the scene to be sent in priority can be made. This is enabled by the Spatial Relationship Description (SRD) amendment to the MPEG DASH standard [4,5], following pioneering works [6-9]. The decision problem of what to send is then made much more complex because it must take the user’s motion into account.
In the context of a local project, we are designing innovative streaming strategies for 360°-videos, which are meant to both decrease the required bandwidth and improve the user experience. These strategies however need to be tested and refined, and this usually requires user experiments, i.e., with a pool of human testers.
The goal of this internship is to participate in the design of new streaming strategies for VR, handle their implementation within the Samsung Gear VR framework, perform their analysis and their optimization.
- 1st phase: Design and implementation of new high-level content manipulation strategies
- manipulation of the considered principles for streaming 360°-videos
- modification of the testbed, made of 2 Android applications, a virtual network, multimedia toolboxes [6,7] and cinematographic editing tools
- 2nd phase: User experiments and data analysis
- 3rd phase: Optimization in varying network conditions (dynamic optimization, possibly based on learning)
Additional information :
This PFE can be followed by an internship.
References :
[1] Within application. Available: http://with.in/
[2] CNET. Everyone wanted a piece of virtual reality at this year's CES. CES 2016. Available: http://tinyurl.com/jr9cz7h
[3] Bo Begole. Why The Internet Pipes Will Burst When Virtual Reality Takes Off. Forbes, Feb. 2016.
[4] ISO/IEC 23009-1:2014/Amd 2:2015, "Spatial relationship description, generalized URL parameters and other extensions".
[5] O. A. Niamut, E. Thomas, L. D'Acunto, C. Concolato, F. Denoual, and S. Y. Lim, "MPEG DASH SRD: spatial relationship description," ACM Int. Conf. on Multimedia Systems (MMSys), May 2016.
[6] FFMPEG. Available: https://ffmpeg.org/
[7] MP4box. Available: https://gpac.wp.mines-telecom.fr/mp4box/
Data placement strategies on GPU clusters for deep learning
Name: Michel RIVEILL
Mail: Michel.RIVEILL@unice.fr
Telephone: 04 92 96 51 48
Web page: http://www.i3s.unice.fr
Place of the project: I3S
Address: Templiers 1 building, 930 route des Colles, 06903 Sophia Antipolis
Team: SPARKS
Web page: http://sparks.i3s.unice.fr
Pre-requisites if needed: knowledge of TensorFlow or Caffe learning frameworks is appreciated
Description:
Les GPU, de part leur capacité à traité de très nombreux calculs en parallèles, sont de plus en plus utilisés pour traiter les très important calcul générée et les architectures d'apprentissage profond Deep Learning.
Dans le cadre de cet intership nous souhaitons étudier le comportement d'un cluster construit par assemblage de petits modules GPU de type NVIDIA Jetson pour traiter de très grand volumes de données.
L'hypothèse que nous faisons est que le modèle de calcul tient sur un seul Jetson. Il s'agit donc de définir l'architecture optimale au sens de la consommation énergétique tout en conservant des résultats de classification satisfaisant.
The purpose of this internship is to compare different data placement strategies and collection of changes to the model at each iteration over a very large volume of data to implement a large learning network on a cluster of Jetson TK1 or TX2 interconnected by one or more Gigabit ethernet switch.
The work will focus on expanding insider work and using the TensorFlow library. The data used come from a medico-administrative database for which the risks of rehospitalization, the duration of a stay or other events can be predicted.
Tasks:
- Bibliography on data parallelism and neural networks parallelization strategies
- Hands on Jetson TK1 or TX2 modules programming
- Implementation of selected network parallelization strategies
- Experiment design and benchmarking with the deep patient workflow
- Buiding an experimental model in order to identify the main parameters for the parallelisation strategy
This subject is complementary to a subject, also for deploying DeepLearning architecture on Jetson cluster (resp. J. Montagnat - Team Sparks), but more dedicated to distributed the model over the network.
References:
- https://www.semanticscholar.org/paper/Are-Very-Deep-Neural-Networks-Feasible-on-Mobile-D-Rallapalli-Qiu/d7896d6be118386a1f76f389210ca4e3a87b0d4a
- https://arxiv.org/abs/1404.5997
- http://engineering.skymind.io/distributed-deep-learning-part-1-an-introduction-to-distributed-training-of-neural-networks
- http://dudleylab.org/wp-content/uploads/2016/05/Deep-Patient-An-Unsupervised-Representation-to-Predict-the-Future-of-Patients-from-the-Electronic-Health-Records.pdf
- http://www.deeplearningbook.org/
Online Learning of Caching Policies
SUPERVISORS
Name: Giovanni Neglia Mail: giovanni.neglia@inria.fr
Name: Alain Jean-Marie Mail: alain.jean-marie@inria.fr
Telephone: +33 (0) 4 92 38 7906 Web page: http://www-sop.inria.fr/members/Giovanni.Neglia/
LOCATION
Inria Sophia-Antipolis Méditerranée
Address: 2004 route des Lucioles, 06902 Sophia Antipolis
Team: Neo, https://team.inria.fr/neo/
DESCRIPTION
A large number of caching policies have been proposed, but they often require ad hoc tuning of different parameters and none of them emerges as a clear winner across a large set of different request traces. For this reason, most of the practical caching systems adopt the Least Recently Used (LRU) policy, because of its simplicity and its general good performance.
The purpose of this internship is to investigate if a neural network can be used to learn an optimal caching policy online.
PRE-REQUISITES
The student should have good programming and analytical skills (probability, algorithms, optimization). The student must contact the supervisors to check if he/she has the required background. As a reference, marks superior or equal to 14/20 for “Performance evaluation of networks” and “Graph algorithms and combinatorial optimization” can be an indication that the student has the required theoretical knowledge. The course on “Distributed Optimiation and Games” will provide the required background on continuous optimization.
OTHER INFORMATION
This subject is research oriented and can lead to a PhD research topic.
Co-modeling for segregated applications on innovative satellite hardware design
Supervisor Name: Robert de Simone (Inria Senior Researcher)
Mail: Robert.de_Simone@inria.fr
Telephone: +33 (0)4 92 38 79 41
Web page:
Place of the project: Inria Sophia-Méditerranée Center
Address: Lagrange Building, Inria
Team: Kairos team
Web page: https://team.inria.fr/kairos/
Title: Co-modeling for segregated applications on innovative satellite hardware design
Description: Due to severe life conditions in space, satellite software has always been limited in size to fit small specific ray-immune microcontrolers.
But technological advances make it now possible to pick more customary "components on-the-shelf (COTS)" for processors, enlarging the scope of software design.
In particular, dedicated control tasks ensuring the satellite basic functionalities may coexist on the same processor with additional features specific to a given mission instance assigned to that satellite. We want to extend the principles of hw/sw codesign and algorithm/architecture adaptation to cope with the issue of, first assigning the fixed constant software (with the relevant level of variability), then figuring how to optimize the addition of custom applications to this partially defined setting.
The approach is based on model-based system engineering environments, and concrete inputs for a simple case studies should be provided in the context of a starting collaboration with industrial partners as part of the IRT Saint-Exupery ATIPPIC project.
Pre-requisites: The course on Formal modeling for Embedded Systems with Networks-on-Chip. More readings available at the beginning of the internship.
A TDOA based geolocation system for LoRa Low Power Wide Area Networks
Name: Thierry Turletti & Mohamed Naoufal Mahfoudi & Walid Dabbous
Mail: thierry.turletti@inria.fr & Mohamed-Naoufal.Mahfoudi@inria.fr & walid.dabbous@inria.fr
Telephone: 0492387718
Web page: https://team.inria.fr/diana/team-members/thierry-turletti/ & https://team.inria.fr/diana/team-members/walid-dabbous/
Place of the project: Inria
Address: 2004 route des Lucioles, 06902 Sophia Antipolis
Team: Diana project-team
Web page: https://www.inria.fr/equipes/diana
Pre-requisites if any: Script programming (Python, Bash).
Detailed description:
The Diana Project-Team at INRIA works on wireless network experimentation platforms. In the last couple of years, they have built at INRIA Sophia-Antipolis an anechoic chamber with RF absorbers preventing radio waves reflections with a Faraday cage for blocking external interferences. This lab, named R2lab [1], represents an ideal environment for experiments reproducibility. The Diana project-team has also provided the nepi-ng software as python libraries to quickly script the client experiment deployment capabilities, which is complete from nodes provisioning to data collection. One of the main interests in this wireless domain is to benefit from open radio capabilities to provide cross-layer optimization. In this context, R2lab has been recently used to design a system to estimate the orientation (heading and yaw) of a MIMO WiFi equipped object, relying on a joint estimation of the angle of arrival and the angle of departure [2].
In this internship, we propose to extend this study to the use of a LoRa physical and MAC layers [3,4] instead of WiFi. LoRa is an emerging communication technology for Low Power Wide Area Network (LPWAN) which is known to be particularly efficient for long range communication links (several kilometers) at very low cost.
The goal is to explore the possibilities of using “native” geolocation with LoRa. The idea is to use three or more LoRa gateways to make a time difference of arrival (TDOA) calculation on the received LoRa signal and calculating the position [5]. However, accurate localization using any low power, narrowband, RF technology such as LoRa is extremely difficult to develop into a usable approach [6]. Therefore, in this internship, the TDOA based geolocation precision will be evaluated in simple direct LOS scenarios in the deployed LoRa network. Based on the state of the art techniques, the intern is expected to design a TDOA based geolocation system, and evaluate the solution in R2lab.
References:
[1] FIT R2lab Wireless Tesbed : http://fit-r2lab.inria.fr/
[2] Mohamed Naoufal Mahfoudi et al., ORION: Orientation Estimation Using Commodity Wi-Fi, Workshop on Advances in Network Localization and Navigation (ANLN), May 2017, Paris, France. pp.1033-1038
[3] N. Sornin, M. Luis, T. Eirich, T. Kramp, O.Hersent , “LoRa Specification 1.0,” LoRa Alliance Standard specification., 2016. https://www.lora-alliance.org/
[4] Augustin, A., Yi, J., Clausen, T., & Townsley, W. M. (2016). A study of LoRa: Long range & low power networks for the internet of things. Sensors, 16(9), 1466. http://www.mdpi.com/1424-8220/16/9/1466/pdf
[5] Thomas Verbeke, Emoke Olti, and Adrian Munteanu. 2016. Development and Demonstration of a LoRa TDOA-based Localisation System: Demo. In Proceedings of the 10th International Conference on Distributed Smart Camera (ICDSC '16). ACM, New York, NY, USA, 206-207. DOI: https://doi.org/10.1145/2967413.2974031
[6] https://www.link-labs.com/blog/lora-localization
Performance of LoRa Low Power Wide Area Networks for the Internet of Things
Name: Walid Dabbous & Mohamed Naoufal Mahfoudi & Thierry Turletti
Mail: walid.dabbous@inria.fr & Mohamed-Naoufal.Mahfoudi@inria.fr & thierry.turletti@inria.fr
Telephone: 0492387718
Web page: https://team.inria.fr/diana/team-members/walid-dabbous/ & https://team.inria.fr/diana/team-members/thierry-turletti/
Place of the project: Inria
Address: 2004 route des Lucioles, 06902 Sophia Antipolis
Team: Diana project-team
Web page: https://www.inria.fr/equipes/diana
Pre-requisites if any: Physical layer internals.
Detailed description:
The Diana Project-Team at INRIA works on wireless network experimentation platforms. In the last couple of years, they have built at INRIA Sophia-Antipolis an anechoic chamber with RF absorbers preventing radio waves reflections with a Faraday cage for blocking external interferences. This lab, named R2lab [1], represents an ideal environment for experiments reproducibility. The Diana project-team has also provided the nepi-ng software as python libraries to quickly script the client experiment deployment capabilities, which is complete from nodes provisioning to data collection.
The Internet of Things (IoT) is playing an increasingly role today and more than half of major new business systems are expected to incorporate IoT elements by 2020. LoRa is an emerging communication technology for Low Power Wide Area Network (LPWAN) which is known to be particularly efficient for long range communication links (several kilometers) at very low cost. However, first studies on the LoRaWAN MAC protocol developed by the LoRa Alliance for this technology reported important performance issues [2,3]. In the last years, colleagues from LEAT have designed miniature antennas suitable for integration into compact LoRa location tracking devices [4,5].
In this internship, the candidate will first study the principles of the LoRa LPWAN technology and its possible usages. Then she/he will have the opportunity to run live experiments with a few LoRa devices based on Arduino that have been developed by our colleagues at LEAT [6]. A benchmark will be performed using different metrics (e.g., packet loss, RSSI, SNR) for various scenarios (e.g., w/ and w/o Line Of Sight (LOS/NLOS), indoor and outdoor and possibly within the R2lab anechoic testbed). The information available at the physical and higher layers (e.g., RSSI, node’s activity time, power consumption) will be collected in order to characterize the transmission capabilities of the LoRa board developed by LEAT. The intern will also use LoRa on LimeSDR and USRP software radio devices to run similar experiments in R2lab and compare the results. This objective is to be able to reconfigure the antenna to realize specific transmission optimization objectives and to the design of enhanced transmission mechanisms and their theoritical and experimental evaluation.
This internship is in collaboration with LEAT CMA team in the context of a UCA Jedi Idex grant.
References:
[1] FIT R2lab Wireless Tesbed : http://fit-r2lab.inria.fr/
[2] N. Sornin, M. Luis, T. Eirich, T. Kramp, O.Hersent , “LoRa Specification 1.0,” LoRa Alliance Standard specification., 2016. https://www.lora-alliance.org/
[3] Augustin, A., Yi, J., Clausen, T., & Townsley, W. M. (2016). A study of LoRa: Long range & low power networks for the internet of things. Sensors, 16(9), 1466. http://www.mdpi.com/1424-8220/16/9/1466/pdf
[4] P. Monin, F. Ferrero, L Lizzi, C. Danchesi, N. Sornin, and S. Boudaud, “Enabling Miniature Position Tracker Using LoRa and GPS Technology,” 10th European Conference on Antennas and Propagation (EuCAP), Davos, Switzerland, April 10-15, 2016.
[5] L. Lizzi, F. Ferrero, C. Danchesi and S. Boudaud, “Design of antennas enabling miniature and energy efficient wireless IoT devices for smart cities,” 2016 IEEE International Smart Cities Conference (ISC2), Trento, Italy, September 12-15, 2016, pp. 1-5.
[6] Pham, C., Ferrero, F., Diop, M., Lizzi, L., Dieng, O., & Thiaré, O. (2017, June). Low-cost antenna technology for LPWAN IoT in rural applications. In Advances in Sensors and Interfaces (IWASI), 2017 7th IEEE International Workshop on (pp. 121-126).
Classification and analysis of solar irradiance data
Name: Sara Alouf (Inria),
Mail: sara.alouf@inria.fr
Web page: http://www-sop.inria.fr/members/Sara.Alouf/
Place of the project: Inria Sophia Antipolis
Address: 2004 route des Lucioles, 06902 Sophia Antipolis
Team: NEO
Web page: https://team.inria.fr/neo/
-Description:
The rate of solar energy that arrives at a surface per unit of time and per unit area is the solar irradiance and is expressed in W/m2. The global irradiance I_G (t) accounts for all radiations arriving at a surface at time t except for the ground-reflected ones. During a clear sky day without any perturbations due to a change in the meteorological conditions, the solar irradiance exhibits a predictable pattern that is called the clear sky solar irradiance I_CS(t) and that can be modelled as a sinusoidal curve. Weather conditions affect the solar irradiance. The perturbations on the clear sky irradiance I_CS(t) induced by the meteorological conditions can be captured by a multiplicative noise denoted α(t) and called clear sky index in the literature. We have I_G(t) = α(t)I_CS(t).
In [1], we propose a 4-state semi-Markov process to model the clear sky index α(t). Each state of this semi-Markov process refers to a weather condition and is characterized by the duration the process stays in this state (i.e. the period of time during which the weather condition remains the same) and by the values of the clear sky index while in this state. In [1], state sojourn times and clear sky index values in each state have phase-type distributions. We use per-minute solar irradiance data [2] to tune the model, hence we are able to capture small time scales fluctuations.
This model has been tuned and validated using data for the city of Los Angeles. The objective of this internship is to investigate the solar irradiance in multiple locations. The goal is to identify a model for the clear sky index that is as universal as possible. If this goal is not achievable, then instead the student will focus on identifying the minimal number of distinct models, such that each model is fit to a given set of locations. Specific tasks to be performed during this internship are to:
- read and comprehend the relevant literature,
- retrieve per-minute measurements of the global solar irradiance for many locations on earth,
- retrieve per-day astronomical informations for the same locations,
- compute and cluster the clear sky index for the same locations,
- find the empirical distributions of sojourn times and values in each state/cluster from the retrieved traces,
- test the robustness of the obtained semi-Markov model by computing the autocorrelation function and the periodogram of generated trajectories.
Pre-requisites: the candidate must have a solid background in stochastic processes and be proficient in data processing and analysis.
References:
1. Dimitra Politaki and Sara Alouf. Stochastic models for solar power. In Proceedings of EPEW: European Performance Evaluation Workshop, volume 10497 of LNCS, pages 282–297, Berlin, Germany, September 2017. http://dx.doi.org/10.1007/978-3-319-66583-2 18.
2. Afshin Andreas and Stephen Wilcox. Solar Resource and Meteorological Assessment Project (SOLRMAP): Rotating Shadowband Radiometer (RSR); Los Angeles, California (Data), 2012. http://dx.doi.org/10.5439/1052230.
Measuring Available Bandwidth in a Virtualized/Cloud Environment (SigNet)
Name: Guillaume Urvoy-Keller, Quentin Jacquemart, Alessio Pagliari
Mail: urvoy@unice.fr, quentin.jacquemart@unice.fr
Telephone: +33 (0)4.92.94.27.64
Web page: http://www.i3s.unice.fr/~urvoy/, http://www.qj.be/ and http://www.i3s.unice.fr/~pagliari/
Where?
Laboratoire I3S
2000, route des Lucioles
Les Algorithmes
Bât. Euclide B - BP 121
06903 Sophia Antipolis Cedex
Team: I3S/SigNet project
Web page: http://signet.i3s.unice.fr/
Pre-requisites if needed: networking
Description:
Cloud providers like Amazon Web Service (AWS) or Azure provide ample details on the virtual machines characteristics that can be instantiated by end users, e.g., CPU, disk, RAM. They further allow tenants (companies hosting part of their infrastructure in the cloud) to create virtual networks on demands. Stillt, the exact amount of bandwidth that a pair of machines located in the same or different data-center(s) (DC) can expect to obtain, remains a blind spot for the end user. This information is however of utmost interest in a number of situation, e.g. distributed applications that operate over several locations (DCs) and process data that is collected and stored locally.
Measuring bandwidth by performing tests like iperf transfers can soon become a costly operation. Our objective in this work is to develop an active bandwidth measurement tool able to infer the actual bandwidth available on virtual links that interconnect VMs in a DC (or the mix of virtual and physical links when the two machines are in different DCs). Preliminary results with Pathload [2] have been obtained in [3], and we would like to extend our study to account for specific constraints of cloud provider environments, especially multi-pathing, which is heavily used to distribute load within the cloud provider network.
The project will consist of the following phases:
1) Get familiar with the tools that have been proposed (in general over a decade ago) to measure the available bandwidth. A lot of public implementations are available.
2) Assess their performance in a controlled but virtualized environment, for which those tools were not designed. Mininet [5] could be a platform of interest to carry those tests. This analysis will entail capturing the measurement traffic and evaluate the impact of virtualization on the timing of the probe packets (this timing being the key characteristics over which those tools base their estimation) and propose some adaptations (specific filtering techniques) for those types of environment.
3) Move in the wild, to AWS, Google Cloud or Azure and develop an approach to account for the use of multi-paths in those environments, e.g. estimating a priori the number of multi-paths and then perform measurements in parallel on all those paths.
References:
[1] http://prestocloud-project.eu/new/
[2] Jain, Manish, and Constantinos Dovrolis. "Pathload: A measurement tool for end-to-end available bandwidth." In Proceedings of Passive and Active Measurements (PAM) Workshop. 2002.
[3] A. Pagliari, Q. Jacquemart, G. Urvoy-Keller . "Towards non-intrusive measurements of available bandwidth for multi-cloud applicationsPoster" ACM IMC 2017
[4] A. Paglari, "Network as an On-Demand Service for Multi-Cloud Workloads "Master thesis, UNS, 2017.
[5] http://mininet.org/
Enabling large scale network experiments with Mininet
Advisors:
Dino Lopez & Guillaume Urvoy-Keller
dino.lopez@unice.fr, urvoy@i3s.unice.fr
http://www.i3s.unice.fr/~lopezpac
http://www.i3s.unice.fr/~urvoy
Where:
SigNet team / I3S Laboratory
Les Algorithmes
Bât. Euclide B - BP 121
2000, route des Lucioles
06903 Sophia Antipolis Cedex
Web : http://signet.i3s.unice.fr/
===== Introduction =====
Mininet [1] is currently widely used in the networking research domain to evaluate the performance of current network protocols, as well as new propositions. Indeed, the promise of obtaining experimental results close to the real life with the help of emulation technologies, and allow experiments in large network scenarios by employing a few physical servers has motivated the wide adoption of Mininet by researchers. Hence, we observe a move from classical simulators (ns-2 or ns-3), or from expensive hardware-based network testbeds to the virtual testbed provided by Mininet.
In the SigNet team, we have also extensively relied on Mininet to evaluate our propositions. However, according to our experience, with Mininet, one need to carefully tune the virtual network parameters to obtain sound results. For instance, we have observed that Mininet might fail when one needs to setup networks with heterogeneous link capacities, hence leading to "strange" results (e.g. the observed end-to-end delay might be incredibly large sometimes). More generally, the research community will benefit from a more in-depth understanding of the limits, lacks and the underpinning technologies of Mininet.
===== Objectives =====
The objective of this internship is twofold. On the one hand, the student must conduct large set of experiments in order to understand the limits of Mininet. On the other hand, once the student will be aware of the problems in Mininet, he/she will conduct several experiments with Mininet in large hybrid network environments within the context of a current work in progress carried out at the SigNet team on network resilience.
Regarding the first objective about the Mininet limitations, the student is expected to explore (i) several network topologies, i.e. different Data Center topologies and ISP topologies; (ii) several network link parameters, i.e. different bandwidth capacities and delays; and (iii) different network sizes. A deep exploration of the underlying technologies in Mininet is also suitable as it will explain also the root of the Mininet's inaccuracies. Later, once the limitations of Mininet have been identified, the student must provide solutions to solve or mitigate its impact on the experimental results.
Regarding the experiments in the context of network resilience, the student is expected to emulate a large set of large hybrid networks. Note that in hybrid networks, Software Defined Networks (a network architecture where the control plane --materialized by a server controller-- is decoupled from the data plane --materialized by the SDN routers-- and the controller server can have a wide view of the network state and topology) and legacy (current) network equipments coexist.
We will consider specifically hybrid SDN [3] / OSPF [4] networks and develop methods that enable the SDN controller to interact directly with OSPF routers with the objective of minimizing the reconfiguration time of OSPF (which is several seconds in general in case of failure [5]). We will further investigate scenarios (using Mininet) where the controller uses either in-band communications (SDN control packets share the link with customers' data packets) or out-of-band communications (SDN control packets pass through dedicated management links). Preliminary work carried out in the SigNet team will serve as a basis for this study (see Chapter 4.3 from [2]).
===== Some References =====
[1] Brandon Heller. Reproducible network research with high-fidelity emulation. Ph.D. Thesis, Stanford University, 2013.
[2] Myriana Rifai. Next-Generation SDN Based Networks. Ph.D. Thesis, Université Côte d'Azur, 2017. Available at http://www.i3s.unice.fr/~lopezpac/downloads/PhD-Myriana.pdf
[3] B. A. A. Nunes, M. Mendonca, X. N. Nguyen, K. Obraczka and T. Turletti, "A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks," in IEEE Communications Surveys & Tutorials, vol. 16, no. 3, pp. 1617-1634, Third Quarter 2014.
[4] J. T. Moy, “OSPF Version 2,” RFC 2328, Apr. 1998.
[5] P. Francois, C. Filsfils, J. Evans, and O. Bonaventure, “Achieving sub-second IGP convergence in large IP networks,” ACM SIGCOMM CCR, vol. 35, no. 3, pp. 35–44, 2005.