PhD defense of Nicolas Huin

PhD Nicolas Huin

    • Title: “Energy Efficient Software Defined Networks”
    • When: September 28, 2017 — 14:30
    • Where: Inria Sophia Antipolis, amphi Kahn
    • Committee:

    • 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


PhD Nicolas Huin

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},
}

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.

GDR RSD labex Inria

PhD defense of Guillaume Ducoffe

PhD Guillaume Ducoffe

  • Title: “Metric properties of large graphs”
  • When: December 9, 2016 — 14:30
  • Where: Inria Sophia Antipolis, amphi Kahn
  • Committee:

  • 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

Robert E. Tarjan

  • 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

, ,

FHCP Challenge Set

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!