An article by Nathann Cohen and David Coudert, entitled Le défi des 1001 graphes, has been published in Interstices (in french). It relates our approach to address (and win) the Flinders Hamiltonian Cycle Problem (FHCP) Challenge organized by the Flinders Hamiltonian Cycle Project (Flinders University, Adelaide, Australia).
PhD defense of Nicolas Huin
-
- Title: “Energy Efficient Software Defined Networks”
- When: September 28, 2017 — 14:30
- Where: Inria Sophia Antipolis, amphi Kahn
- Committee:
- Walid Dabbous, Inria, Sophia Antipolis, France
- Frédéric Giroire (Supervisor), CNRS, Sophia Antipolis,
- Brigitte Jaumard, Concordia University, Montréal, Canada
- Arie M.C.A Koster (Referee), RWTH Aachen, Germany
- Laurent Lefèvre (Referee), Inria, Lyon, France
- Jérémie Leguay, Huawei Technologies, Paris, France
- Dino Lopez (Supervisor), UCA, I3S, UNS, Sophia Antipolis, France
- François Vanderbeck, Université de Bordeaux & Inria, France
-
Abstract: In the recent years, the growth of the architecture of telecommunication networks has been quickly increasing to keep up with a booming traffic. Moreover, the energy consumption of these infrastructures is becoming a growing issue, both for its economic and ecological impact. Multiple approaches were proposed to reduce the networks’ power consumption such as decreasing the number of active elements. Indeed, networks are designed to handle high traffic, e.g., during the day, but are over-provisioned during the night. In this thesis, we focus on disabling links and routers inside the network while keeping a valid routing. This approach is known as Energy Aware Routing (EAR).
However current networks are not adapted to support the deployment of network-wide green policies due to their distributed management and the black-box nature of current network devices.The SDN and NFV paradigms bear the promise of bringing green policies to reality.The first one decouples the control and data plane and thus enable a centralized control of the network.The second one proposes to decouple the software and hardware of network functions and allows more flexibility in the creation and management of network services.
In this thesis, we focus on the challenges brought by these two paradigms for the deployment of EAR policies. We dedicated the first two parts to the SDN paradigm. We first study the forwarding table size constraints due to an increased complexity of rules. We then study the progressive deployment of SDN devices alongside legacy ones. We focus our attention on the NFV paradigm in the last part, and more particularly, we study the Service Function Chaining problem.
All the publications at the core of this thesis are available online here
Guillaume Ducoffe recipient of an accessit to PhD prize Graphes “Charles Delorme”
Guillaume Ducoffe is the recipient of an accessit to the PhD prize Graphes “Charles Delorme” 2017 for his PhD thesis entitled Metric properties of large graphs. Congratulations !
The prize will be announced during the next Journées Graphes et Algorithmes — Bordeaux, November 15-17, 2017.
Wilkes Award 2017
The paper Energy Efficient Content Distribution [1] won the Wilkes Award 2017 (The Wilkes Award is given once a year to the authors of the best paper published in the volume of The Computer Journal from the previous year)
Congratulation to the authors!
- J. Araujo, F. Giroire, J. Moulierac, Y. Liu, and R. Modrzejewski, “Energy Efficient Content Distribution,” The Computer Journal, vol. 59, iss. 2, pp. 192-207, 2016. doi:10.1093/comjnl/bxv095
[BibTeX] [Download PDF]@article{araujo:hal-01238051, TITLE = {{Energy Efficient Content Distribution}}, AUTHOR = {Araujo, J and Giroire, Fr{\'e}d{\'e}ric and Moulierac, J and Liu, Yi and Modrzejewski, R}, URL = {https://hal.inria.fr/hal-01238051}, JOURNAL = {{The Computer Journal}}, PUBLISHER = {{Oxford University Press (UK)}}, VOLUME = {59}, NUMBER = {2}, PAGES = {192-207}, YEAR = {2016}, MONTH = Feb, DOI = {10.1093/comjnl/bxv095}, KEYWORDS = {Energy Efficiency ; Integer Linear Programming ; Content Deliv-ery Network ; In-network Caching ; Future Internet}, PDF = {https://hal.inria.fr/hal-01238051/file/compj.pdf}, HAL_ID = {hal-01238051}, HAL_VERSION = {v1}, }
GreenDays@Sophia 2017
GreenDays@Sophia: “Efficacité énergétique dans les Réseaux Filaires et Mobiles, des FAI aux Centres de Données : Challenges & Opportunités”
- Main topic: Green communications in wired and wireless networks
- When: June 26-27, 2017
- Where: Sophia Antipolis, France
- Link: conference website
JCALM
17th Journées Combinatoire et Algorithmes du Littoral Méditerranéen (JCALM)
- Main topic: Designs
- When: May 4-5, 2017
- Where: Sophia Antipolis, France
- Link: conference website
Journées RESCOM 2017
Participez aux Journées non thématiques RESCOM 2017 (12-13 janvier 2017) et à la journée thématique RESCOM Communication dans la ville intelligente (11 janvier 2017). Ces évènements sont organisés dans l’amphi Kahn de Inria Sophia Antipolis – Méditerranée et dans la salle E+131 de Polytech sur le Campus SophiaTech.
Le programme et les informations pratiques sont disponibles sur la page des journées.
PhD defense of Guillaume Ducoffe
- Title: “Metric properties of large graphs”
- When: December 9, 2016 — 14:30
- Where: Inria Sophia Antipolis, amphi Kahn
- Committee:
- Victor Chepoi (Referee), LIF, Marseille, France
- David Coudert (Supervisor), Université Côte d’Azur, Inria, CNRS, I3S, France
- Michele Flammini, University of L’Aquila, Italie
- Cyril Gavoille, LaBRI – Université de Bordeaux, France
- Igor Litovsky, I3S, Univ. Nice Sophia Antipolis, France
- Nicolas Nisse, Université Côte d’Azur, Inria, CNRS, I3S, France
- Robert E. Tarjan, Princeton University and Intertrust Technologies, USA
- Laurent Viennot (Referee), Inria / IRIF, France
-
Abstract: Large scale communication networks are everywhere, ranging from data centers with millions of servers to social networks with billions of users. This thesis is devoted to the fine-grained complexity analysis of combinatorial problems on these networks.
In the first part, we focus on the embeddability of communication networks to tree topologies. This property has been shown to be crucial in the understanding of some aspects of network traffic (such as congestion). More precisely, we study the computational complexity of Gromov hyperbolicity and of tree decomposition parameters in graphs – including treelength and treebreadth. On the way, we give new bounds on these parameters in several graph classes of interest, some of them being used in the design of data center interconnection networks. The main result in this part is a relationship between treelength and treewidth: another well-studied graph parameter, that gives a unifying view of treelikeness in graphs and has algorithmic applications. This part borrows from graph theory and recent techniques in complexity theory.
The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analyzing information flows in these networks, represented as dynamical processes on graphs. First, a coloring game on graphs is studied as a solution concept for the dynamic of communities. We give a fine-grained complexity analysis for computing Nash and strong Nash equilibria in this game, thereby answering open questions from the literature. On the way, we propose new directions in algorithmic game theory and parallel complexity, using coloring games as a case example. Finally, we introduce a new learning problem that is motivated by the need for users to uncover any misuse of their personal data online. We give positive and negative results on the tractability of this problem.
All the publications at the core of this thesis are available online here
-
Keywords: Graph theory, Hyperbolicity, tree-decomposition, complexity, privacy.
- Manuscript: Core of the thesis, appendix, all in one file
- Slides of the presentation
Concurrent Disjoint Set Union
- Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
- Title: Concurrent Disjoint Set Union — (watch the video)
- When: December 9, 2016 — 10:30
- Where: Inria Sophia Antipolis, amphi Kahn
-
Abstract: The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton.
-
Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.
Winner of the FHCP Challenge
The team composed of Nathann Cohen (CNRS, LRI, Paris XI) and David Coudert won the Flinders Hamiltonian Cycle Problem (FHCP) Challenge organized by the Flinders Hamiltonian Cycle Project (Flinders University, Adelaide, Australia).
The challenge consisted in solving 1001 instances of the Hamiltonian Cycle Problem over a one year period (September 30 2015 till September 30 2016). The FHCP Challenge Set is a collection of 1001 instances of the Hamiltonian Cycle Problem, ranging in size from 66 vertices up to 9528 vertices, with an average size of just over 3000 vertices.
We were able to solve 985 instances!
- Web page of the challenge: Flinders Hamiltonian Cycle Problem (FHCP) Challenge Set
- News on Inria website: When researchers play to solve 1001 instances of the Hamiltonian Cycle Problem