Inria Associated Team EfDyNet


[bibshow file=http://www-sop.inria.fr/teams/coati/EA-EfDyNet/efdynet-biblio-proposal.bib highlight=Coudert|Giroire|Moulierac|Gausseran|Tomassilli|Gausseran|Jaumard|Duong]

EfDyNet

Efficient Dynamic Resource Allocation in Networks

Programme INRIA “Equipes Associées” 2019-2021

 

 

Inria Project-Team : COATI Foreign Partner: Concordia University, Montréal
Inria Sophia Antipolis — Méditerranée
Thème INRIA : Com B
Country: Canada (Québec)
French coordinator Canadian coordinator
Name, surname Frédéric Giroire Brigitte Jaumard
Title Chargé de Recherche CNRS (Research officer) Professor
Institution Project-team COATI, common team
INRIA Sophia Antipolis – I3S (CNRS UMR 7271, University Nice-Sophia Antipolis)
Computer Science and Software Engineering (CSE) Department, Concordia University, Montréal, Québec, Canada
Address
INRIA Sophia-Antipolis Méditerranée
2004, route des Lucioles — B.P. 93
06902 Sophia-Antipolis Cedex
France
Concordia University
Sir George Williams Campus
1455 De Maisonneuve Blvd. W.
Montreal, Quebec, Canada
H3G 1M8
URL http://www-sop.inria.fr/members/Frederic.Giroire/ http://users.encs.concordia.ca/~bjaumard/

Activity reports

Participants

Documents

Visits in 2019

Publications of the Project

Automatic extraction from HAL if contains “EfDyNet” in field “collaborations”

Publications HAL

2019

Journal articles

titre
Wavelength Defragmentation for Seamless Migration
auteur
Brigitte Jaumard, Hamed Pouya, David Coudert
article
Journal of Lightwave Technology, Institute of Electrical and Electronics Engineers (IEEE)/Optical Society of America(OSA), 2019, 37 (17), pp.4382-4393. ⟨10.1109/JLT.2019.2924914⟩
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02167682/file/RWA_MBB_JLT_hal.pdf BibTex

Conference papers

titre
Mininet on steroids: exploiting the cloud for Mininet performance
auteur
Giuseppe Di Lena, Andrea Tomassilli, Damien Saucez, Frédéric Giroire, Thierry Turletti, Chidung Lac
article
CloudNet 2019 – IEEE International Conference on Cloud Networking, Nov 2019, Coimbra, Portugal
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02362997/file/CloudNet%20%2815%29.pdf BibTex
titre
No Interruption When Reconfiguring my SFCs
auteur
Adrien Gausseran, Andrea Tomassilli, Frédéric Giroire, Joanna Moulierac
article
CloudNet 2019 – 8th IEEE International Conference on Cloud Networking, Nov 2019, Coimbra, Portugal
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02295967/file/PID6145639.pdf BibTex
titre
Bandwidth-optimal Failure Recovery Scheme for Robust Programmable Networks
auteur
Andrea Tomassilli, Giuseppe Di Lena, Frédéric Giroire, Issam Tahiri, Damien Saucez, Stéphane Pérennes, Thierry Turletti, Ruslan Sadykov, François Vanderbeck, Chidung Lac
article
CloudNet 2019 – 8th IEEE International Conference on Cloud Networking, Nov 2019, Coimbra, Portugal
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02292971/file/camera-ready-cloudnet.pdf BibTex
titre
Reconfiguration de chaînes de fonctions de services sans interruption
auteur
Adrien Gausseran, Andrea Tomassilli, Frédéric Giroire, Joanna Moulierac
article
CORES 2019 – Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de Communication, Jun 2019, Saint Laurent de la Cabrerisse, France
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-02118989/file/AlgoTel.pdf BibTex
titre
Poster: Don’t Interrupt Me When You Reconfigure my Service Function Chains
auteur
Adrien Gausseran, Andrea Tomassilli, Frédéric Giroire, Joanna Moulierac
article
IFIP Networking Conference 2019, May 2019, Varsovie, Poland
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02083579/file/networking-short.pdf BibTex
titre
When Network Matters: Data Center Scheduling with Network Tasks
auteur
Frédéric Giroire, Nicolas Huin, Andrea Tomassilli, Stéphane Pérennes
article
INFOCOM 2019 – IEEE International Conference on Computer Communications, Apr 2019, Paris, France
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01989755/file/infocom2019_camera_ready.pdf BibTex

Poster communications

titre
Demo Proposal – Distrinet: a Mininet implementation for the Cloud
auteur
Giuseppe Di Lena, Andrea Tomassilli, Damien Saucez, Frédéric Giroire, Thierry Turletti, Chidung Lac
article
CoNEXT 2019 – 15th International Conference on emerging Networking EXperiments and Technologies, Dec 2019, Orlando, FL, United States
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02359695/file/Distrinet___demo_CoNEXT19__Hal_version_.pdf BibTex
titre
Poster: Design of Survivable SDN/NFV-enabled Networks with Bandwidth-optimal Failure Recovery
auteur
Andrea Tomassilli, Giuseppe Di Lena, Frédéric Giroire, Issam Tahiri, Stéphane Pérennes, Damien Saucez, Thierry Turletti, Ruslan Sadykov, François Vanderbeck, Chidung Lac
article
NETWORKING 2019 – IFIP Networking conference, May 2019, Warsaw, Poland
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02364488/file/2019-POSTER-IFIP-global-rerouting.pdf BibTex

Documents associated with scientific events

titre
Distributed Network Experiment Emulation
auteur
Giuseppe Di Lena, Andrea Tomassilli, Damien Saucez, Frédéric Giroire, Thierry Turletti, Chidung Lac, Walid Dabbous
article
GEFI 19 – Global Experimentation for Future Internet – Workshop, Nov 2019, Coimbra, Portugal
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02359801/file/GEFI%281%29.pdf BibTex

Reports

titre
Be Scalable and Rescue My Slices During Reconfiguration
auteur
Adrien Gausseran, Frédéric Giroire, Brigitte Jaumard, Joanna Moulierac
article
[Research Report] Inria – Sophia Antipolis; I3S, Université Côte d’Azur; Concordia University. 2019
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-02416096/file/report2019.pdf BibTex

 

Additional Publications

 

Journal articles

  1. B. Jaumard, H. Q. Duong, R. Armolavicius, T. Morris, Todd and P. Djukic. Efficient real-time scalable make-before-break network re-routing. In IEEE/OSA Journal of Optical Communications and Networking (JOCN), 11(3) pp. 52—56, 2019.

Conference articles

  1.  J. Toniolli, B. Jaumard. Resource Allocation for Multiple Workflows in Cloud-Fog Computing Systems. In Workshop of IEEE/ACM International Conference on Utility and Cloud Computing (UCC Workshop), Auckland, New Zealand, Dec. 2019.

Scientific programme and objectives

Context

Networks are evolving rapidly in two directions. On the one hand, new network technologies are developed for different layers, and in particular flexible optical technologies (enabling to allocate a fraction of the optical spectrum rather than a fixed wavelength), Software Defined Networks, and Network Function Virtualization. On the other hand, the traffic patterns evolve and become less predictable due to the increase of cloud and mobile traffic. In this context, there are new possibilities and needs for dynamic resource allocations. We will study this problem mainly in two directions: network reconfiguration and the allocation of virtualized resources.

  • Network Reconfiguration.
    Network reconfiguration is required in order to adapt to traffic changes, network failures, or new deployment of network resources. It occurs at the optical layer in order to make sure that the upper layer traffic, e.g., IP layer traffic, can be efficiently carried. In such a case, we deal with lightpath reconfigurations and the primary objective is to reduce disruptions to user traffic carried by existing lightpaths, measured by the number of disrupted lightpaths or the duration of lightpath disruptions [bibcite key=li15,CoudertTCS2011,Sol09]. Network reconfiguration may also arise at the logical layer, in order to attain a better resource utilization [bibcite key=joz03,CoudertAGT2009]. In heavily loaded networks, dynamic connection addition and drop actions may result in a set of connections where some paths are not the shortest possible ones, leading to poor resource utilization compared to an optimal or at least optimized state. Thus, global connection re-optimization is proposed at certain time intervals (e.g., daily, weekly) to improve the network performance. While several works already exist on network reconfigurations, most of the approaches used in practice (i.e., by network operators) are greedy heuristics, with no information on the quality of their solutions. Our recent joint investigations on reconfiguration both for optical [bibcite key=jau18_Hamed] and for the logical layer [bibcite key=Duong2018a,Duong2018b] let us think that it is possible to solve the reconfiguration problem exactly and at scale, in addition to be able to estimate the maximum load that should be allowed in the network in order to be able to do it without any disruption, or a very limited number of them. We will benefit from a collaboration of Brigitte Jaumard with CIENA, which is helping us for assessing the accuracy of our algorithmic solutions.
  • Virtualized Software Defined Networks.
    Software-defined networking (SDN) has been attracting a growing attention in the networking research community in recent years. SDN is a new networking paradigm that decouples the control plane from the data plane. It provides a flexibility to develop and test new network protocols and policies in real networks, see e.g. the experiment of Google for its inter-datacenter network [bibcite key=jain2013b4]. Network Function Virtualization (NFV) is an emerging approach in which network functions are no longer executed by proprietary software appliances but instead, can run on generic-purpose servers located in small cloud nodes [bibcite key=han2015network]. Examples of network functions include firewalls, load balancing, content filtering, and deep packet inspection. This technology aims at dealing with the major problems of today’s enterprise middlebox infrastructure, such as cost, capacity rigidity, management complexity, and failures [bibcite key=sherry2012making]. One of the main advantages of this approach is that Virtual Network Functions (VNFs) can be instantiated and scaled on demand without the need of installing new equipment. These new technologies bear the promise of important cost savings and of new possibilities but introduces new complex problems [bibcite key=han2015network,mijumbi2016network,lai17], which need to be addressed: how to do efficiently (dynamic) resource allocations (paths and virtualized resources)?

Objectives

We will design exact and approximate methods for optimizing the usage of network resources. We will consider resource allocation and network reconfiguration in physical and logical networks as well as in SDN. Our main objectives are:

  • Network Reconfiguration.
    Reconfiguration can be performed with two strategies. For both strategies, we assume that we are given the current network provisioning, and we aim at moving to an optimized one, requiring less bandwidth while granting the same set of requests. Along the first strategy, the idea is to compute an optimized provisioning, and then find the most seamless transition from the current provisioning to the optimized one [bibcite key=CoudertALGOTEL2005,Sol09,sol10]. In the second strategy, the idea is to iteratively improve the current provisioning with one rerouting at a time [bibcite key=klo08,joz03,Duong2018a,Duong2018b], assuming each rerouting can be made before the break move, i.e., a rerouting with no disruption. While with the first strategy, we usually reach a more efficient provisioning, it is at the expense of a number of disruptions.
    Based on the expertise of B. Jaumard for solving efficiently the RWA (Routing and Wavelength Assignment) and RSA (Routing and Spectrum Assignment) problems [bibcite key=jau17_TON,Enoch2017,Enoch2018_ICNC] and the expertise of D. Coudert on graph algorithms [bibcite key=CoudertJEA2016] and routing reconfiguration [bibcite key=CoudertDAM2011,CoudertTCS2011,CoudertALGOTEL2005,CoudertAGT2009,CoudertICC2012], our objectives are as follows:
  • Investigate further the RWA reconfiguration problem. We currently completed a first study with the minimization of the number of disruptions. We plan to extend it as explained in the following in the plan for next year.
  • Study the RSA reconfiguration problem, as backbone networks are moving towards it, following the huge increase in bandwidth requirements. This is an even more challenging optimization problem than for RWA.
  • Use the gained expertise to study network reconfiguration in SDN, possibly including the live migration of virtual machines or functions.

 

  • Virtualized Software Defined Networks.
    The same virtual function can be replicated and executed on several servers. It follows that a fundamental problem arising when dealing with network functions is how to map these functions to nodes (servers) in the network while achieving a specific objective. Moreover, SDN allows to do the allocation dynamically on the fly, when new requests arrive. This means that classic networking problems (e.g. routing, scheduling, failure protection) have to be readdressed in a new context in which virtualized resources may be allocated, migrated, and removed on the fly on top of a physical infrastructure.To address this problem, we will use the expertise of both groups, in particular the corpus of works done in the context of WDM optical networks. Indeed, optical networks also are layered graphs in which a logical topology has to be mapped onto a physical fiber topology. Similarly, a set of virtualized resources has to be mapped into the physical network. We will explore different directions.

 

  • Complex optimization methods, such as decomposition techniques, and in particular column generation. These techniques are used when classical optimization techniques such as integer linear programs do not scale. The main idea is to decompose the problem into subproblems, which can then be solved independently and efficiently. Brigitte Jaumard is specialist in optimization methods and will bring her expertise to the project.
  • Algorithmics and in particular approximation algorithms. If, as stated, the main problems are very complex, some the subproblems may be solved efficiently. In particular, some variant of constrained shortest paths or of covering problems appear. COATI is expert in this area.
  • Last, we will use the knowledge gained working on optical and IP network reconfigurations to study how to re-optimize on the fly the usage of virtual resources (e.g. virtual network functions). Indeed, a shared virtual resource may have to be updated and/or moved when the demand has evolved. We will study the problem in the context of network slicing which is the topic of the Ph.D. of Adrien Gausseran (supervised by J. Moulierac). 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) [bibcite key=zhang2017network,nikaein2015network].

Work-program

During the first year of the project, we will address the following tasks:

  • Network reconfiguration. (COATI: D. Coudert, A. Gausseran | CSE: H. Duong, B. Jaumard, Quang Anh Nguyen)
    • Write a survey on the lightpath reconfiguration problem in WDM networks. To this end, we need to compare existing methods and build a framework for experiments (implement all models, build traffic instances, etc.)
    • Investigate tradeoffs in the RWA reconfiguration problem. The number of disruptions in the migration depends on the optimized RWA provisioning. Can we define metrics enabling to build an optimized RWA solution inducing the minimum number of disruptions?
      Can we avoid disruptions while maintaining the quality of the provisioning ?
    • Start studying the RSA reconfiguration problem. Based on the particularities of RSA, we plan to look at how to combine the push-pull mechanism proposed for dynamic RSA [bibcite key=wan14] with the classical reconfiguration tools in order to minimize the number of disruptions. Additionally, we would like to extend our recent work on the logical layer [bibcite key=Duong2018a,Duong2018b] in order to design a scalable model and algorithm for the RWA reconfiguration problem.
  • Tolerance for failures and dynamics of virtual resources. (COATI: F. Giroire, A. Gausseran, J. Moulierac, A. Tomassilli | CSE: B. Jaumard, Shima Ghanei Zare, Adham Mohammed)Network flows are often required to be processed by an ordered sequence of network functions. For instance, an Intrusion Detection System may need to inspect the packet before compression or encryption are performed. Moreover, different customers can have different requirements in terms of the sequence of network functions to be performed [bibcite key=savi2015impact]. This notion is known as Service Function Chaining (SFC) [bibcite key=quinn2015problem].
    This is a very complex objective as it adds a constraint of order to a set of already NP-complete problems.
    In the first year, we will consider this problem of mapping with the additional constraints (1) first of tolerating failures and (2) second of considering very dynamic traffic.

    1. Indeed, failures are very frequent in network and data centers. In particular, it is reported in [bibcite key=turner2010california], that, in the monitored Data Center Network, each link experienced in average 16 failures per year, considering a five years time period [bibcite key=turner2010california]. We will investigate with A. Tomassilli different protection techniques (link or path protection, dedicated or shared protection) for different kinds of failures (link failures, node failures, network function failures). In collaboration with B. Jaumard and during the visit in Concordia of F. Giroire, we will build scalable decomposition models to solve the problem, first in a static case in which the requests are given offline. The next step will be to consider the dynamic case.
    2. We will consider a dynamic setting in which network slices requiring virtual resources have to be set up on the fly for clients. From time to time, the virtual resources have to be updated. We will investigate how the use of reconfiguration algorithms may improve their usage. This will be the goal of the 3 month visit of A. Gausseran and of the 2 week visit of J. Moulierac in Concordia in 2019.


References

[/bibshow]

Comments are closed.