Publications

Journal Articles

2023

Routing and Slot Allocation in 5G Hard Slicing

by Huin, Nicolas and Leguay, Jérémie and Martin, Sébastien and Medagliani, Paolo
in Computer Communications

Abstract

Current network slicing solutions suffer from poor inter-slice isolation, as the performance of one slice can be influenced by the traffic in other slices. New technologies such as Flex Ethernet can offer hard isolation via dedicated resources at the physical and MAC layers. However, to create cost-efficient hard slices in large 5G access networks, a “routing and slot allocation” must be solved quickly. While the underlying network design problem is not new, two extra constraints need to be considered: a specific order in slot activations and a bandwidth allocation policy with statistical multiplexing. We propose a compact and extended formulation to derive FlexE-CG, an algorithm based on column-generation to solve large instances. We reinforce the extended formulation to improve the lower bound by deriving valid inequalities, and we provide necessary and sufficient conditions under which the inequalities are facet-defining. We show that these inequalities improve the lower bound by more than 20% on various IP-Radio Access Networks ( RAN). We also show that FlexE-CG can provide solutions within an optimality gap of 10% in a few minutes.

Bibtex

@article{huin_routing_2023,
  title = {Routing and Slot Allocation in 5G Hard Slicing},
  volume = {201},
  issn = {01403664},
  url = {https://linkinghub.elsevier.com/retrieve/pii/S0140366423000166},
  doi = {10.1016/j.comcom.2023.01.008},
  pages = {72--90},
  journaltitle = {Computer Communications},
  shortjournal = {Computer Communications},
  author = {Huin, Nicolas and Leguay, Jérémie and Martin, Sébastien and Medagliani, Paolo},
  urlyear = {2023-02-22},
  year = {2023},
  langid = {english}
}

An Approach to Network Service Placement Reconciling Optimality and Scalability

by Taghavian, Masoud and Hadjadj-Aoul, Yassine and Texier, Geraldine and Huin, Nicolas and Bertin, Philippe
in IEEE Transactions on Network and Service Management

Abstract

The inevitable transition from physical dedicated hardware devices towards lightweight containerized reusable software modules with Network Function Virtualization (NFV) introduces countless opportunities while presenting several unprecedented challenges. Satisfying NFV expectations in post-5G networks heavily depends on the efficient placement of network services. In this paper, after modeling the placement problem and proposing the exact resolutions using Integer Linear Programming and Column Generation we propose our deterministic placement solution, capable of obtaining optimal results with the scalability of a heuristic-grade approach. Our method is organized as a Branch-and-Bound structure, applying AI search strategies (especially A\textasteriskcentered) to address the problem of network service placement. We believe that it is suitable for a range of applications in online placement scenarios, whether we concentrate on the quality of the results or on the strict time constraints. We are interested in the popular objective of Service Acceptance maximization and have carried out several extensive evaluations. The obtained results confirm the effectiveness of our solution.

Bibtex

@article{taghavian_approach_2023,
  title = {An Approach to Network Service Placement Reconciling Optimality and
               Scalability},
  author = {Taghavian, Masoud and Hadjadj-Aoul, Yassine and Texier, Geraldine and Huin, Nicolas and Bertin, Philippe},
  year = {2023},
  journaltitle = {IEEE Transactions on Network and Service Management},
  shorttitle = {IEEE TNSM},
  pdf = {taghavian\_approach\_2023.pdf}
}

2018

Energy-Efficient Service Function Chain Provisioning

by Huin, Nicolas and Tomassilli, Andrea and Giroire, Frédéric and Jaumard, Brigitte
in Journal of Optical Communications and Networking

Abstract

Network function virtualization (NFV) is a promising network architecture concept to reduce operational costs. In legacy networks, network functions, such as firewall or TCP optimization, are performed by specific hardware. In networks enabling NFV coupled with the software defined network (SDN) paradigm, virtual network functions (VNFs) can be implemented dynamically on generic hardware. This is of primary interest to implement energy-efficient solutions, in order to adapt the resource usage dynamically to the demand. In this paper, we study how to use NFV coupled with an SDN to improve the energy efficiency of networks. We consider a setting in which a flow has to go through a service function chain, which is several network functions in a specific order. We propose an integer linear programming (ILP) formulation, an ILP-based heuristic, and a decomposition model that relies on joint routing and placement configuration to solve the problem. We show that virtualization provides between 22% and 62% of energy savings for networks of different sizes.

Bibtex

@article{huin_energy-efficient_2018,
  title = {Energy-Efficient Service Function Chain Provisioning},
  volume = {10},
  rights = {All rights reserved},
  issn = {1943-0620, 1943-0639},
  url = {https://www.osapublishing.org/abstract.cfm?URI=jocn-10-3-114},
  doi = {10.1364/JOCN.10.000114},
  pages = {114--124},
  number = {3},
  journaltitle = {Journal of Optical Communications and Networking},
  shortjournal = {J. Opt. Commun. Netw.},
  author = {Huin, Nicolas and Tomassilli, Andrea and Giroire, Frédéric and Jaumard, Brigitte},
  urlyear = {2021-05-29},
  year = {2018},
  langid = {english}
}

Energy-Efficient Service Function Chain Provisioning

by Huin, Nicolas and Tomassilli, Andrea and Giroire, Frédéric and Jaumard, Brigitte
in Electronic Notes in Discrete Mathematics

Abstract

Network Function Virtualization (NFV) is a promising network architecture concept to reduce operational costs. In legacy networks, network functions, such as firewall or TCP optimization, are performed by specific hardware. In networks enabling NFV coupled with the Software Defined Network (SDN) paradigm, network functions can be implemented dynamically on generic hardware. This is of primary interest to implement energy efficient solutions, in order to adapt dynamically the resource usage to the demands. In this paper, we study how to use NFV coupled with SDN to improve the energy efficiency of networks. We consider a setting in which a flow has to go through a Service Function Chain, that is several network functions in a specific order. We propose a decomposition model that relies on chaining and function placement configurations to solve the problem. We show that virtualization allows to obtain between 15% to 62% of energy savings for networks of different sizes.

Bibtex

@article{huin_energy-efficient_2018-1,
  title = {Energy-Efficient Service Function Chain Provisioning},
  volume = {64},
  rights = {All rights reserved},
  issn = {15710653},
  url = {https://linkinghub.elsevier.com/retrieve/pii/S1571065318300283},
  doi = {10.1016/j.endm.2018.02.001},
  pages = {265--274},
  journaltitle = {Electronic Notes in Discrete Mathematics},
  shortjournal = {Electronic Notes in Discrete Mathematics},
  author = {Huin, Nicolas and Tomassilli, Andrea and Giroire, Frédéric and Jaumard, Brigitte},
  urlyear = {2021-05-29},
  year = {2018},
  langid = {english}
}

Bringing Energy Aware Routing Closer to Reality With SDN Hybrid Networks

by Huin, Nicolas and Rifai, Myriana and Giroire, Frederic and Lopez Pacheco, Dino and Urvoy-Keller, Guillaume and Moulierac, Joanna
in IEEE Transactions on Green Communications and Networking

Abstract

Energy-aware routing aims at reducing the energy consumption of Internet service provider (ISP) networks. The idea is to adapt routing to the traffic load to turn off some hardware. However, it implies to make dynamic changes to routing configurations which is almost impossible with legacy protocols. The software defined network (SDN) paradigm bears the promise of allowing a dynamic optimization with its centralized controller. In this paper, we propose smooth energy aware routing (SENAtoR), an algorithm to enable energy-aware routing in a scenario of progressive migration from legacy to SDN hardware. Since in real life, turning off network devices is a delicate task as it can lead to packet losses, SENAtoR also provides several features to safely enable energy saving services: tunneling for fast rerouting, smooth node disabling, and detection of both traffic spikes and link failures. We validate our solution by extensive simulations and by experimentation. We show that SENAtoR can be progressively deployed in a network using the SDN paradigm. It allows us to reduce the energy consumption of ISP networks by 5%-35% depending on the penetration of SDN hardware while diminishing the packet loss rate compared to legacy protocols.

Bibtex

@article{huin_bringing_2018,
  title = {Bringing Energy Aware Routing Closer to Reality With {SDN} Hybrid
               Networks},
  volume = {2},
  rights = {All rights reserved},
  issn = {2473-2400},
  url = {https://ieeexplore.ieee.org/document/8369161/},
  doi = {10.1109/TGCN.2018.2842123},
  pages = {1128--1139},
  number = {4},
  journaltitle = {{IEEE} Transactions on Green Communications and Networking},
  shortjournal = {{IEEE} Trans. on Green Commun. Netw.},
  author = {Huin, Nicolas and Rifai, Myriana and Giroire, Frederic and Lopez Pacheco, Dino and Urvoy-Keller, Guillaume and Moulierac, Joanna},
  urlyear = {2021-05-29},
  year = {2018}
}

Energy-Aware Routing in Software-Defined Network using Compression

by Giroire, Frédéric and Huin, Nicolas and Moulierac, Joanna and Phan, Truong Khoa
in The Computer Journal

Abstract

Software-defined Network (SDN) is a new networking paradigm enabling innovation through network programmability. Over past few years, many applications have been built using SDN such as server load balancing, virtual-machine migration, traffic engineering and access control. In this paper, we focus on using SDN for energy-aware routing (EAR). Since traffic load has a small influence on the power consumption of routers, EAR allows putting unused links into sleep mode to save energy. SDN can collect traffic matrix and then computes routing solutions satisfying QoS while being minimal in energy consumption. However, prior works on EAR have assumed that the SDN forwarding table switch can hold an infinite number of rules. In practice, this assumption does not hold since such flow tables are implemented in Ternary Content Addressable Memory (TCAM) which is expensive and power hungry. We consider the use of wildcard rules to compress the forwarding tables. In this paper, we propose optimization methods to minimize energy consumption for a backbone network while respecting capacity constraints on links and rule space constraints on routers. In details, we present two exact formulations using Integer Linear Program (ILP ) and introduce efficient heuristic algorithms. Based on simulations on realistic network topologies, we show that using this smart rule space allocation, it is possible to save almost as much power consumption as the classical EAR approach.

Bibtex

@article{giroire_energy-aware_2018,
  title = {Energy-Aware Routing in Software-Defined Network using Compression},
  volume = {61},
  rights = {All rights reserved},
  issn = {0010-4620, 1460-2067},
  url = {https://academic.oup.com/comjnl/article/61/10/1537/4953376},
  doi = {10.1093/comjnl/bxy029},
  pages = {1537--1556},
  number = {10},
  journaltitle = {The Computer Journal},
  author = {Giroire, Frédéric and Huin, Nicolas and Moulierac, Joanna and Phan, Truong Khoa},
  editor = {Anta, Antonio Fernandez},
  urlyear = {2021-05-29},
  year = {2018},
  langid = {english}
}

Optimal Network Service Chain Provisioning

by Huin, Nicolas and Jaumard, Brigitte and Giroire, Frederic
in IEEE/ACM Transactions on Networking

Abstract

Service chains consist of a set of network services, such as firewalls or application delivery controllers, which are interconnected through a network to support various applications. While it is not a new concept, there has been an extremely important new trend with the rise of software-defined network ( SDN) and Network Function Virtualization (NFV). The combination of SDN and NFV can make the service chain and application provisioning process much shorter and simpler. In this paper, we study the provisioning of service chains jointly with the number/location of virtual network functions (VNFs). While chains are often built to support multiple applications, the question arises as how to plan the provisioning of service chains in order to avoid data passing through unnecessary network devices or servers and consuming extra bandwidth and CPU cycles. It requires choosing carefully the number and the location of the VNFs. We propose an exact mathematical model using decomposition methods whose solution is scalable in order to conduct such an investigation. We conduct extensive numerical experiments, and show we can solve exactly the routing of service chain requests in a few minutes for networks with up to 50 nodes, and traffic requests between all pairs of nodes. Detailed analysis is then made on the best compromise between minimizing the bandwidth requirement and minimizing the number of VNFs and optimizing their locations using different data sets.

Bibtex

@article{huin_optimal_2018,
  title = {Optimal Network Service Chain Provisioning},
  volume = {26},
  rights = {All rights reserved},
  issn = {1063-6692, 1558-2566},
  url = {https://ieeexplore.ieee.org/document/8362669/},
  doi = {10.1109/TNET.2018.2833815},
  pages = {1320--1333},
  number = {3},
  journaltitle = {{IEEE}/{ACM} Transactions on Networking},
  shortjournal = {{IEEE}/{ACM} Trans. Networking},
  author = {Huin, Nicolas and Jaumard, Brigitte and Giroire, Frederic},
  urlyear = {2021-05-29},
  year = {2018},
  hal_id = {hal-01920951}
}

2017

Minnie: An SDN world with few compressed forwarding rules

by Rifai, Myriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Frederic and Moulierac, Joanna and Lopez Pacheco, Dino and Urvoy-Keller, Guillaume
in Computer Networks

Abstract

Software Defined Networking (SDN) is gaining momentum with the support of major manufacturers. While it brings flexibility to the management of flows within the data center fabric, this flexibility comes at the cost of smaller routing table capacities. Indeed, the Ternary Content-Addressable Memory (TCAM ) needed by SDN devices has smaller capacities than CAMs used in legacy hardware. In this paper, we investigate compression techniques to maximize the utility of SDN switches forwarding tables. We validate our algorithm, called Minnie, with intensive simulations for well-known data center topologies, to study its efficiency and compression ratio for a large number of forwarding rules. Our results indicate that Minnie scales well, being able to deal with around a million of different flows with less than 1000 forwarding entries per SDN switch, requiring negligible computation time. To assess the operational viability of Minnie in real networks, we deployed a testbed able to emulate a Fat-Tree data center topology. We demonstrate on the one hand, that even with a small number of clients, the limit in terms of number of rules is reached if no compression is performed, increasing the delay of new incoming flows. Minnie, on the other hand, reduces drastically the number of rules that need to be stored, with no packet losses, nor detectable extra delays if routing lookups are done in the Application-Specific Integrated Circuits (ASICs). Hence, both simulations and experimental results suggest that Minnie can be safely deployed in real networks, providing compression ratios between 70% and 99%.

Bibtex

@article{rifai_minnie_2017,
  title = {Minnie: An {SDN} world with few compressed forwarding rules},
  volume = {121},
  rights = {All rights reserved},
  issn = {13891286},
  url = {https://linkinghub.elsevier.com/retrieve/pii/S1389128617301433},
  doi = {10.1016/j.comnet.2017.04.026},
  shorttitle = {Minnie},
  pages = {185--207},
  journaltitle = {Computer Networks},
  shortjournal = {Computer Networks},
  author = {Rifai, Myriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Frederic and Moulierac, Joanna and Lopez Pacheco, Dino and Urvoy-Keller, Guillaume},
  urlyear = {2021-05-29},
  year = {2017},
  langid = {english}
}

Conference Articles

2024

Virtual Multi-Topology Routing for QoS Constraints

by Huin, Nicolas and Martin, Sébastien and Leguay, Jérémie
in NOMS 2024-2024 IEEE/IFIP Network Operations and Management Symposium

Bibtex

@inproceedings{huin_2024,
  author = {Huin, Nicolas and Martin, Sébastien and Leguay, Jérémie},
  title = {Virtual Multi-Topology Routing for QoS Constraints},
  year = {2024},
  booktitle = {NOMS 2024-2024 IEEE/IFIP Network Operations and Management
                   Symposium},
  pdf = {huin_2024.pdf}
}

2023

Optimal placement of virtualized DUs in O-RAN architecture

by Ndao, Amath and Lagrange, Xavier and Huin, Nicolas and Texier, G\’ eraldine and Nuaymi, Loutfi
in 2023 IEEE 97th Vehicular Technology Conference (VTC2023-Spring)

Abstract

Open Radio Access Network (O-RAN) is very promising for flexible and efficient 5G and 6G wireless networks. The O-RAN architecture consists of three main units: Radio Unit (RU), Distributed Unit (DU) and Centralized Unit (CU). In this paper we study the placement of virtualized DUs. This placement has strong consequences on cost and delay, among other, and is then an important challenge. First, we analyze the throughput between the O-RAN interfaces. Based on our analysis, we propose an efficient Integer Linear Programming (ILP) model. The objective is to minimize the O-RAN cost depending on the DU placement while respecting the delay and capacity constraints. We evaluate our model on a real topology. Our results provide interesting insights on the cost savings with regard to a legacy architecture. Moreover, the proposed model provides solutions, in a configuration where a fully centralized Cloud RAN architecture would not. We also estimate the limits of capacity of a given configuration.

Bibtex

@inproceedings{ndao_2023,
  title = {Optimal placement of virtualized DUs in O-RAN architecture},
  author = {Ndao, Amath and Lagrange, Xavier and Huin, Nicolas and Texier, G\' {e}raldine and Nuaymi, Loutfi},
  year = {2023},
  hal_id = {hal-04117608},
  booktitle = {2023 IEEE 97th Vehicular Technology Conference (VTC2023-Spring)
                   },
  pdf = {ndao\_2023.pdf}
}

A Fair Approach to the Online Placement of the Network Services over the Edge

by Taghavian, Masoud and Hadjadj-Aoul, Yassine and Texier, Geraldine and Huin, Nicolas and Bertin, Philippe
in 19th International Conference on Network and Service Management (CNSM)

Abstract

Unavoidable transition from rigid dedicated hardware devices towards flexible containerized network services, introduced by Network Function Virtualization (NFV), brings novel opportunities while several new challenges. Meeting the expectations of NFV in post-5G networks depends on the efficient placement of the services. The online placement of the network services, demanding strict end-to-end latency requirements over the edge networks, with restricted computing resources presents a challenging problem which is worth investigating. We propose a Branch-and-Bound search approach for finding optimal placements of the network services by applying several different cost functions to maximize the service acceptance. Extensive evaluations has been carried out, and the results confirm significant improvements when we consider a fair distribution of the resources on the edge.

Bibtex

@inproceedings{taghavian_fair_2023,
  title = {A Fair Approach to the Online Placement of the Network Services
               over the Edge},
  author = {Taghavian, Masoud and Hadjadj-Aoul, Yassine and Texier, Geraldine and Huin, Nicolas and Bertin, Philippe},
  year = {2023},
  booktitle = {19th International Conference on Network and Service Management
                   (CNSM)}
}

Optimal DU Placement in an O-RAN Multi-Band System

by Ndao, Amath and Lagrange, Xavier and Huin, Nicolas and Texier, Geraldine and Nuaymi, Loutfi
in 2023 6th International Conference on Advanced Communication Technologies and Networking (CommNet) (CommNet’23)

Abstract

Open Radio Access Network (O-RAN) is the most promising solution for future RAN deployments. This attractive and efficient solution presents complex and new challenges w.r.t to cost, energy consumption and other performance indicators. In this work , we study function placement in the Open Radio Access Network (O-RAN) architecture. Our objective it to minimize the operating costs, while respecting other network constraints. We consider a RAN load that varies over the day and we study the ORAN-DUs (ORAN-Distributed Units) placement for different frequency bands. We use data obtained from real topology. First, we analyze the percentage of utilization, throughput and Modulation and Coding Scheme (MCS) selections of each frequency band for each hour of the day. Based on our analysis, we propose an Integer Linear Programming (ILP) model whose objective is to minimize computing and routing cost while respecting the delay and capacity constraints of ORAN interfaces. Our results analyse the cost savings of the proposed model w.r.t the DRAN (Distributed RAN), the solution prevailing before ORAN, during off-peak and peak hours.

Bibtex

@inproceedings{ndao_optimal_2023,
  author = {Ndao, Amath and Lagrange, Xavier and Huin, Nicolas and Texier, Geraldine and Nuaymi, Loutfi},
  title = {Optimal {DU} Placement in an {O-RAN} {Multi-Band} System},
  booktitle = {2023 6th International Conference on Advanced Communication
                   Technologies and Networking (CommNet) (CommNet'23)},
  address = {, Morocco},
  pages = {7},
  year = {2023}
}

Placement of Logical Functionalities in 5G/B5G Networks

by Ziazet, Junior Momo and Jaumard, Brigitte and Larabi, Adel and Huin, Nicolas
in 2023 IEEE Future Networks World Forum (FNWF)

Bibtex

@inproceedings{ziazet_2023,
  title = {Placement of Logical Functionalities in 5G/B5G Networks},
  author = {Ziazet, Junior Momo and Jaumard, Brigitte and Larabi, Adel and Huin, Nicolas},
  booktitle = {2023 IEEE Future Networks World Forum (FNWF)},
  year = {2023},
  pdf = {ziazet_2023.pdf}
}

Radio resource allocation in low- to medium-load regimes for energy minimization with C-RAN

by Alhajj, Tania and Huin, Nicolas and Amis, Karine and Lagrange, Xavier
in 26th International Symposium on Wireless Personal Multimedia Communications (WPMC 2023)

Abstract

Radio resource allocation is critical in order to manage available bandwidth and optimize network behavior. In Centralized-Radio Access Networks (C-RAN), simple Radio Units (RUs) are deployed and can be controlled remotely to allow cooperation. In this paper, we consider micro-cell systems with low-to-medium load regimes. We study the resource allocation problem with minimization of the energy consumption due to radio transmission and signal processing. We propose to mix two transmission modes over a reference period allowing resource reuse: one with all RUs transmitting the same signal, the other with each RU transmitting a specific signal. We impose the same target rate for each user equipment (UE), the same transmit power for the RUs, and a maximum resource block (RB) number, which defines the constraints. The resulting optimization problem is formulated so as to be mixed integer linear programming (MILP). Simulations are run using CPLEX Python API and show the efficiency of the proposed scheme to increase the capacity while consuming the least energy. We also observe that the mode with all RUs simultaneously serving the same UE is more efficient (fewer RB and lower consumed energy) than the mode with a single RU activated at a time.

Bibtex

@inproceedings{alhajj_2023,
  title = {Radio resource allocation in low- to medium-load regimes for energy
               minimization with C-RAN},
  author = {Alhajj, Tania and Huin, Nicolas and Amis, Karine and Lagrange, Xavier},
  year = {2023},
  month = nov,
  booktitle = {26th International Symposium on Wireless Personal Multimedia
                   Communications (WPMC 2023)},
  pdf = {alhajj\_2023.pdf}
}

2022

Lagrangian relaxation for the design of virtual IGP topologies

by Huin, Nicolas and Leguay, Jeremie and Martin, Sébastien and Zengde, Gao
in 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d’Aide à la Décision

Bibtex

@inproceedings{huin_lagrangian_2022,
  location = {Villeurbanne - Lyon, France},
  title = {Lagrangian relaxation for the design of virtual {IGP} topologies},
  rights = {All rights reserved},
  url = {https://hal.science/hal-03595310},
  eventtitle = {23ème congrès annuel de la Société Française de Recherche
                    Opérationnelle et d'Aide à la Décision},
  booktitle = {23ème congrès annuel de la Société Française de Recherche
                   Opérationnelle et d'Aide à la Décision},
  publisher = {{INSA} Lyon},
  author = {Huin, Nicolas and Leguay, Jeremie and Martin, Sébastien and Zengde, Gao},
  year = {2022},
  keywords = {{IGP}, Lagrangian relaxation, {LARAC}}
}

Constrained Deep Reinforcement Learning for Smart Load Balancing

by Houidi, Omar and Zeghlache, Djamal and Perrier, Victor and Quang, Pham Tran Anh and Huin, Nicolas and Leguay, Jérémie and Medagliani, Paolo
in 2022 IEEE 19th Annual Consumer Communications & Networking Conference (CCNC)

Abstract

In this paper, we explore the use of an actor-critic architecture for Deep Reinforcement Learning (DRL) to improve load balancing beyond traditional algorithms. Some centralized Reinforcement Learning (RL) algorithms have targeted in the reward function expression the Quality of Experience (QoE) for video flows, but this requires access to clients, or the Maximum Link Utilization (MLU) for other types of flows. In our approach, we tune the actor-critic algorithm to only leverage on QoS parameters in order to load balance traffic in the network and maximize the QoE experienced by the users. This avoids having to collect observations and performance measurements from client applications, as it only focuses on network metrics that can be easily measured. We explore both centralized and distributed solutions to assess the feasibility of the proposed smart load balancing solutions. We compare them to ECMP, QoE -based reward methods, and RILNET that uses an underlying DDPG optimization approach. The proposed algorithms are shown to outperform previous approaches.

Bibtex

@inproceedings{houidi_constrained_2022,
  location = {Las Vegas, {NV}, {USA}},
  title = {Constrained Deep Reinforcement Learning for Smart Load Balancing},
  rights = {All rights reserved},
  isbn = {978-1-66543-161-3},
  url = {https://ieeexplore.ieee.org/document/9700657/},
  doi = {10.1109/CCNC49033.2022.9700657},
  eventtitle = {2022 {IEEE} 19th Annual Consumer Communications \& Networking
                    Conference ({CCNC})},
  pages = {207--215},
  booktitle = {2022 {IEEE} 19th Annual Consumer Communications \& Networking
                   Conference ({CCNC})},
  publisher = {{IEEE}},
  author = {Houidi, Omar and Zeghlache, Djamal and Perrier, Victor and Quang, Pham Tran Anh and Huin, Nicolas and Leguay, Jérémie and Medagliani, Paolo},
  year = {2022}
}

Resource Defragmentation for Network Slicing

by Medagliani, Paolo and Martin, Sebastien and Leguay, Jeremie and Cai, Shengming and Zeng, Feng and Huin, Nicolas
in IEEE INFOCOM 2022 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)

Abstract

Network automation in the fifth generation of mobile networks (5G) requires network slices to be efficiently computed and deployed. In order to guarantee physical isolation for virtual networks and no interference between different slices, it is possible to rely on hard slicing, whose principles can be implemented using Flex Ethernet (FlexE) technology. As slices are created and deleted over time, it is necessary from time to time to defragment resources and reoptimize bandwidth reservations for the remaining slices.In this demo, we present our algorithmic framework, based on Column Generation, and we showcase how to efficiently defragment the network in order to reduce the Maximum Link Utilization (MLU) of current reservations with a minimum number of configuration changes.

Bibtex

@inproceedings{medagliani_resource_2022,
  location = {New York, {NY}, {USA}},
  title = {Resource Defragmentation for Network Slicing},
  isbn = {978-1-66540-926-1},
  url = {https://ieeexplore.ieee.org/document/9797986/},
  doi = {10.1109/INFOCOMWKSHPS54753.2022.9797986},
  eventtitle = {{IEEE} {INFOCOM} 2022 - {IEEE} Conference on Computer
                    Communications Workshops ({INFOCOM} {WKSHPS})},
  pages = {1--2},
  booktitle = {{IEEE} {INFOCOM} 2022 - {IEEE} Conference on Computer
                   Communications Workshops ({INFOCOM} {WKSHPS})},
  publisher = {{IEEE}},
  author = {Medagliani, Paolo and Martin, Sebastien and Leguay, Jeremie and Cai, Shengming and Zeng, Feng and Huin, Nicolas},
  urlyear = {2022-12-08},
  year = {2022},
  keywords = {Conferences, Network slicing, 5G mobile communication, Network
                  Slicing, Automation, Combinatorial Optimization, Ethernet,
                  Flexible printed circuits, Interference, Network Virtualization,
                  Resource Allocation}
}

2021

Constrained Policy Optimization for Load Balancing

by Kamri, Ahmed Yassine and Quang, Pham Tran Anh and Huin, Nicolas and Leguay, Jérémie
in 2021 17th International Conference on the Design of Reliable Communication Networks (DRCN)

Abstract

To improve the bandwidth utilization in IP networks, a centralized controller splits flow aggregates over multiple paths and decides load balancing weights. Ideally, load balancing policies should anticipate the impact of their decisions on the Quality of Service (QoS). However, the embedding of accurate performance models into load balancing optimization algorithms is a challenge. In this context, we propose a Deep Reinforcement Learning (DRL) based solution that is able to learn the relationship between traffic and QoS, while providing safety to maximize throughput and avoid violating link capacity constraints. Our safe solution for QoS-aware load balancing integrates DRL algorithms with the Reward Constrained Policy Optimization algorithm. In a scenario where link delays follow the M/M/1 queuing model, we demonstrate, using a non-linear integer program, that our solution can reach a close to optimal end-to-end delay. We also show that our solution automatically learns reward parameters to meet capacity constraints.

Bibtex

@inproceedings{kamri_constrained_2021,
  location = {Milan, Italy},
  title = {Constrained Policy Optimization for Load Balancing},
  rights = {All rights reserved},
  isbn = {978-1-66542-234-5},
  url = {https://ieeexplore.ieee.org/document/9477375/},
  doi = {10.1109/DRCN51631.2021.9477375},
  eventtitle = {2021 17th International Conference on the Design of Reliable
                    Communication Networks ({DRCN})},
  pages = {1--6},
  booktitle = {2021 17th International Conference on the Design of Reliable
                   Communication Networks ({DRCN})},
  publisher = {{IEEE}},
  author = {Kamri, Ahmed Yassine and Quang, Pham Tran Anh and Huin, Nicolas and Leguay, Jérémie},
  year = {2021}
}

Optimisation contrainte d’une politique d’équilibrage de charge

by Kamri, Ahmed and Quang, Pham Tran Anh and Huin, Nicolas and Leguay, Jérémie
in ALGOTEL 2021–23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Bibtex

@inproceedings{kamri_optimisation_2021,
  location = {La Rochelle, France},
  title = {Optimisation contrainte d'une politique d'équilibrage de charge},
  rights = {All rights reserved},
  url = {https://hal.science/hal-03221149},
  booktitle = {{ALGOTEL} 2021--23èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Kamri, Ahmed and Quang, Pham Tran Anh and Huin, Nicolas and Leguay, Jérémie},
  year = {2021}
}

Network Slicing with Multi-Topology Routing

by Huin, Nicolas and Martin, Sébastien and Leguay, Jéré mie and Cai, Shengming
in 2021 IFIP Networking Conference (IFIP Networking)

Abstract

The deployment of 5G networks is paving the road to custom network services. It is now possible to envision the automatic decomposition of a physical network into several virtual networks to serve a wide range of user needs. This technology is also referred to as network slicing. To guarantee the strict isolation of virtual networks, it is possible to rely on underlay technologies such as Flex Ethernet (FlexE). In this demo, we present a slicing solution based on Multi-Topology-Routing (MTR ). We will demonstrate how IGP weights can be designed for the embedding of a slice, described by a traffic matrix and end-to-end latency requirements, to minimize the cost of underlay bandwidth reservations.

Bibtex

@inproceedings{huin_network_2021,
  location = {Espoo and Helsinki, Finland},
  title = {Network Slicing with Multi-Topology Routing},
  rights = {All rights reserved},
  isbn = {978-3-903176-39-3},
  url = {https://ieeexplore.ieee.org/document/9472833/},
  doi = {10.23919/IFIPNetworking52078.2021.9472833},
  eventtitle = {2021 {IFIP} Networking Conference ({IFIP} Networking)},
  pages = {1--2},
  booktitle = {2021 {IFIP} Networking Conference ({IFIP} Networking)},
  publisher = {{IEEE}},
  author = {Huin, Nicolas and Martin, Sébastien and Leguay, Jéré mie and Cai, Shengming},
  year = {2021}
}

2020

Génération de colonnes pour le problème de routage \‘a délai variable

by Huin, Nicolas and Leguay, Jeremie and Martin, Sébastien
in ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

Avec la promesse d’un réseau plus performant, la 5G va amplifier l’apparition de services avec des besoins plus stricts pour la latence de bout en bout. Satisfaire des contraintes de d élais plus strictes nécessite d’intégrer des modè les d’évolution du délai en fonction de la charge plus r éalistes. De nombreuses approches permettent de modéliser le délai d’un réseau dans les cas stochastiques ou dé terministes, mais peu de travaux ont intégré ces modè les dans l’optimisation globale du routage. Dans cet article, nous proposons une nouvelle méthode de décomposition qui permet d’inclure ces modèles et nous montrons que nous pouvons satisfaire des contraintes plus fortes qu’avec des mod\‘ eles simplistes.

Bibtex

@inproceedings{huin_generation_2020,
  location = {Lyon, France},
  title = {Génération de colonnes pour le problème de routage \`{a } délai
               variable},
  rights = {All rights reserved},
  url = {https://hal.science/hal-02875446},
  eventtitle = {{ALGOTEL} 2020 – 22èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2020 – 22èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Huin, Nicolas and Leguay, Jeremie and Martin, Sébastien},
  year = {2020},
  keywords = {5G, génération de colonnes, méthodes de dé composition, modèle
                  de délai, Programmation linéaire}
}

2019

Découpage rigide des réseaux 5G avec FlexE

by Huin, Nicolas and Leguay, Jeremie and Martin, Sébastien and Medagliani, Paolo
in ALGOTEL 2019 - 21èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

La cinquième génération des réseaux mobiles (5G) promet d’améliorer l’utilisation des ressources réseau gr âce au network slicing, qui permet aux opérateurs de cr\’ eer des réseaux virtuels pour chacun de ses clients avec une qualité de service (QoS) spécifique. Le dé coupage du réseau peut être fait de façon "souple" ou "rigide". La première manière est plus facile à mettre en place mais ne permet qu’une séparation logique des tranches et ne donne pas de garanties de QoS lors de la surcharge de l’une des tranches. Découper le réseau de fa çon "rigide", grâce à des technologies telles que Flex Ethernet (FlexE), permet de garantir une isolation physique des tranches. Cependant cette technologie nécessite d’allouer la bande passante par canaux. Dans cet article, nous introduisons le problème de routage et d’allocation de canaux FlexE dans un réseau 5G et proposons une décomposition par génération de colonnes pour le résoudre. Nous comparons ensuite cette approche sur des scénarios IPRAN de plusieurs tailles et montrons que notre décomposition permet d’obtenir des bornes inférieures et des solutions proches de l’optimal.

Bibtex

@inproceedings{huin_decoupage_2019,
  location = {Saint Laurent de la Cabrerisse, France},
  title = {Découpage rigide des réseaux 5G avec {FlexE}},
  rights = {All rights reserved},
  url = {https://hal.archives-ouvertes.fr/hal-02119527},
  eventtitle = {{ALGOTEL} 2019 - 21èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2019 - 21èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Huin, Nicolas and Leguay, Jeremie and Martin, Sébastien and Medagliani, Paolo},
  year = {2019},
  keywords = {5G, column generation, network slicing}
}

Routing and Slot Allocation in 5G Hard Slicing

by Huin, Nicolas and Leguay, Jérémie and Martin, Sé bastien
in Proceedings of the 9th International Network Optimization Conference, INOC 2019, Avignon, France, June 12-14, 2019

Abstract

5G networks will enable the creation of network slices to serve very different user requirements. Flex Ethernet (FlexE) is a standard technology that provides strict isolation between slices , also called hard slicing, by allocating capacity slots of physical links to slices. The resulting resource allocation problem is called Routing and Slot Allocation problem (RSA). We first prove that this problem is NP-hard and cannot be approximated. Then, we develop two matheuristics to efficiently solve the problem, by leveraging on a combination of Column Generation and Gauss Seidel procedures. The numerical evaluation, carried out by comparing the two matheuristics against a greedy algorithm over a realistic IP-RAN networks, shows an optimality gap smaller than 7%, while reducing the reservation cost by 4% compared to the greedy algorithm.

Bibtex

@inproceedings{huin_routing_2019,
  location = {Avignon, France},
  title = {Routing and Slot Allocation in 5G Hard Slicing},
  rights = {All rights reserved},
  url = {https://openproceedings.org/2019/conf/inoc/INOC\_2019\_paper\_30.pdf},
  doi = {10.5441/002/INOC.2019.14},
  eventtitle = {{INOC} 2019},
  booktitle = {Proceedings of the 9th International Network Optimization
                   Conference, {INOC} 2019, Avignon, France, June 12-14, 2019},
  publisher = {{OpenProceedings}.org},
  author = {Huin, Nicolas and Leguay, Jérémie and Martin, Sé bastien},
  urlyear = {2021-05-29},
  year = {2019},
  langid = {english},
  keywords = {Network Optimization}
}

Hard-isolation for Network Slicing

by Huin, Nicolas and Medagliani, Paolo and Martin, Sebastien and Leguay, Jeremie and Shi, Lei and Cai, Shengming and Xu, Jinchun and Shi, Hao
in IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)

Abstract

The fifth generation of mobile networks (5G) promises to improve network utilization by allowing operators to create virtual networks for their tenants with different Quality of Service ( QoS) requirements. This technology is also referred to as network slicing. To guarantee physical isolation for virtual networks and no interference between different slices, it is possible to rely on the Flex Ethernet (FlexE) technology. It isolates different slices by allocating resources in a TDMA -fashion. In this demo, we will present our algorithmic framework , based on a Column Generation routine, and we will showcase how the configuration of FlexE interfaces to guarantee hard isolation between slices.

Bibtex

@inproceedings{huin_hard-isolation_2019,
  location = {Paris, France},
  title = {Hard-isolation for Network Slicing},
  rights = {All rights reserved},
  isbn = {978-1-72811-878-9},
  url = {https://ieeexplore.ieee.org/document/8845282/},
  doi = {10.1109/INFCOMW.2019.8845282},
  eventtitle = {{IEEE} {INFOCOM} 2019 - {IEEE} Conference on Computer
                    Communications Workshops ({INFOCOM} {WKSHPS})},
  pages = {955--956},
  booktitle = {{IEEE} {INFOCOM} 2019 - {IEEE} Conference on Computer
                   Communications Workshops ({INFOCOM} {WKSHPS})},
  publisher = {{IEEE}},
  author = {Huin, Nicolas and Medagliani, Paolo and Martin, Sebastien and Leguay, Jeremie and Shi, Lei and Cai, Shengming and Xu, Jinchun and Shi, Hao},
  urlyear = {2021-05-29},
  year = {2019}
}

Automated Mechanism Design: Compact and Decomposition Linear Programming Models

by Jaumard, Brigitte and Babashahi Ashtiani, Kia and Huin, Nicolas
in 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI)

Abstract

In the context of multi-agent systems, Automated Mechanism Design (AMD) is the computer-based design of the rules of a mechanism, which reaches an equilibrium despite the fact that agents can be selfish and lie about their preferences. Although it has been shown that AMD can be modelled as a linear program, it is with an exponential number of variables and consequently, there is no known efficient algorithm. We revisit the latter linear program model proposed for the AMD problem and introduce a new one with a polynomial number of variables. We show that the latter model corresponds to a Dantzig-Wolfe decomposition of the second one and design efficient solution schemes in polynomial time for both two models. Numerical experiments compare the solution efficiency of both models and show that we can solve very significantly larger data instances than before, up to 2,000 agents or 2,000 resources in about 35 seconds.

Bibtex

@inproceedings{jaumard_automated_2019,
  location = {Portland, {OR}, {USA}},
  title = {Automated Mechanism Design: Compact and Decomposition Linear
               Programming Models},
  rights = {All rights reserved},
  isbn = {978-1-72813-798-8},
  url = {https://ieeexplore.ieee.org/document/8995323/},
  doi = {10.1109/ICTAI.2019.00031},
  shorttitle = {Automated Mechanism Design},
  eventtitle = {2019 {IEEE} 31st International Conference on Tools with
                    Artificial Intelligence ({ICTAI})},
  pages = {165--169},
  booktitle = {2019 {IEEE} 31st International Conference on Tools with
                   Artificial Intelligence ({ICTAI})},
  publisher = {{IEEE}},
  author = {Jaumard, Brigitte and Babashahi Ashtiani, Kia and Huin, Nicolas},
  urlyear = {2021-05-29},
  year = {2019}
}

When Network Matters: Data Center Scheduling with Network Tasks

by Giroire, F. and Huin, N. and Tomassilli, A. and Perennes, S.
in IEEE INFOCOM 2019 - IEEE Conference on Computer Communications

Abstract

We consider the placement of jobs inside a data center. Traditionally, this is done by a task orchestrator without taking into account network constraints. According to recent studies, network transfers represent up to 50% of the completion time of classical jobs. Thus, network resources must be considered when placing jobs in a data center. In this paper, we propose a new scheduling framework, introducing network tasks that need to be executed on network machines alongside traditional (CPU) tasks. The model takes into account the competition between communications for the network resources, which is not considered in the formerly proposed scheduling models with communication. Network transfers inside a data center can be easily modeled in our framework. As we show, classical algorithms do not efficiently handle a limited amount of network bandwidth. We thus propose new provably efficient algorithms with the goal of minimizing the makespan in this framework. We show their efficiency and the importance of taking into consideration network capacity through extensive simulations on workflows built from Google data center traces.

Bibtex

@inproceedings{giroire_when_2019,
  location = {Paris, France},
  title = {When Network Matters: Data Center Scheduling with Network Tasks},
  rights = {All rights reserved},
  isbn = {978-1-72810-515-4},
  url = {https://ieeexplore.ieee.org/document/8737415/},
  doi = {10.1109/INFOCOM.2019.8737415},
  shorttitle = {When Network Matters},
  eventtitle = {{IEEE} {INFOCOM} 2019 - {IEEE} Conference on Computer
                    Communications},
  pages = {2278--2286},
  booktitle = {{IEEE} {INFOCOM} 2019 - {IEEE} Conference on Computer
                   Communications},
  publisher = {{IEEE}},
  author = {Giroire, F. and Huin, N. and Tomassilli, A. and Perennes, S.},
  urlyear = {2021-05-29},
  year = {2019}
}

2018

Algorithmes d’approximation pour le placement de chaı̂nes de fonctions de services avec des contraintes d’ordre

by Tomassilli, Andrea and Giroire, Frédéric and Huin, Nicolas and Pérennes, Stéphane
in ALGOTEL 2018 - 20èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

Le modèle des réseaux programmables virtualisés permet aux opérateurs de télécommunications d’offrir des services réseaux complexes et flexibles. Un service se modélise alors comme une chaı̂ne de fonctions réseaux (firewall, compression, contr\^ ole parental,...) qui doivent \^ etre appliquées séquentiellement à un flot de donn ées. Dans cet article, nous étudions le problème du placement de fonctions de services qui consiste à dé terminer sur quels n\oeuds localiser les fonctions afin de satisfaire toutes les demandes de service, de facon à minimiser le coût de déploiement. Nous montrons que le problème peut être ramené à un problème de Set Cover, m\^ eme dans le cas de séquences ordonnées de fonctions réseau. Cela nous permet de proposer deux algorithmes d’approximation à facteur logarithmique, ce qui est le meilleur facteur possible. Finalement, nous évaluons les performances de nos algorithmes par simulations. Nous montrons ainsi qu’en pratique, des solutions presque optimales peuvent être trouvées avec notre approche.

Bibtex

@inproceedings{tomassilli_algorithmes_2018,
  location = {Roscoff, France},
  title = {Algorithmes d'approximation pour le placement de cha\^{\i}nes de
               fonctions de services avec des contraintes d'ordre},
  rights = {All rights reserved},
  url = {https://hal.archives-ouvertes.fr/hal-01774540},
  eventtitle = {{ALGOTEL} 2016 - 18èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2018 - 20èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Tomassilli, Andrea and Giroire, Frédéric and Huin, Nicolas and Pérennes, Stéphane},
  year = {2018}
}

Optimisation pour le Provisionnement de Chaı̂nes de Services R éseau

by Huin, Nicolas and Jaumard, Brigitte and Giroire, Frédéric
in ALGOTEL 2018 - 20èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

La virtualisation des réseaux, portée en partie par l’initiative virtualisation des fonctions de réseau (Network Function Virtualization-NFV), apporte une plus grande flexibilité aux opérateurs de réseaux ainsi qu’une baisse des coûts de gestion. Les fonctions réseau exé cutées sur du matériel dédié peuvent maintenant être exécutées par des serveurs virtuels. Un service correspond alors à une séquence de fonctions, appelée chaı̂ne de services, à effectuer dans un ordre précis sur l’ensemble des flots du service. Le problème considér é est alors de satisfaire les requêtes des chaı̂nes de services tout en trouvant le meilleur compromis entre l’utilisation de la bande passante et le nombre d’emplacements pour héberger les fonctions réseau. Nous proposons un mod èle de génération de colonnes pour le routage et le placement de chaı̂nes de service. Nous montrons à l’aide d’expérimentations poussées que nous pouvons résoudre le problème de façon optimale en moins d’une minute pour des réseaux ayant une taille allant jusqu’à 65 noeuds et 16 000 requêtes. Nous étudions aussi le compromis entre l’utilisation de la bande passante et le nombre de noeuds capables d’héberger des fonctions réseau.

Bibtex

@inproceedings{huin_optimisation_2018,
  location = {Roscoff, France},
  title = {Optimisation pour le Provisionnement de Cha\^{\i}nes de Services R
               éseau},
  rights = {All rights reserved},
  url = {https://hal.archives-ouvertes.fr/hal-01779589},
  eventtitle = {{ALGOTEL} 2018 - 20èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2018 - 20èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Huin, Nicolas and Jaumard, Brigitte and Giroire, Frédéric},
  year = {2018}
}

Resource Requirements for Reliable Service Function Chaining

by Tomassilli, Andrea and Huin, Nicolas and Giroire, Frederic and Jaumard, Brigitte
in 2018 IEEE International Conference on Communications (ICC)

Abstract

In the context of Software-Defined Networks (SDN), Network Function Virtualization (NFV) is a new network paradigm in which network functions are implemented in software as Virtual Network Functions (VNFs). To meet the demand, VNFs are next interconnected to form different complete end-to-end services, also known as a Service Function Chains (SFCs). We study the problem of deploying reliable Service Function Chains over a virtualized network function architecture. While there is a need for reliable service function chaining, there is a high cost to pay for it in terms of bandwidth and VNF processing requirements. We investigate two different protection mechanisms and discuss their resource requirements, as well as the latency of their paths. For each mechanism, we develop a scalable exact mathematical model using column generation.

Bibtex

@inproceedings{tomassilli_resource_2018,
  location = {Kansas City, {MO}},
  title = {Resource Requirements for Reliable Service Function Chaining},
  rights = {All rights reserved},
  isbn = {978-1-5386-3180-5},
  url = {https://ieeexplore.ieee.org/document/8422774/},
  doi = {10.1109/ICC.2018.8422774},
  eventtitle = {2018 {IEEE} International Conference on Communications ({ICC}
                    2018)},
  pages = {1--7},
  booktitle = {2018 {IEEE} International Conference on Communications ({ICC})},
  publisher = {{IEEE}},
  author = {Tomassilli, Andrea and Huin, Nicolas and Giroire, Frederic and Jaumard, Brigitte},
  year = {2018}
}

Optimal Design of Filterless Optical Networks

by Jaumard, Brigitte and Wang, Yan and Huin, Nicolas
in 2018 20th International Conference on Transparent Optical Networks (ICTON)

Abstract

We study the design of filterless optical networks in order that the maximum link network capacity is minimized. We propose a one step model to simultaneously generate and provision filterless sub-networks, together with a solution process that allows its exact solution. Numerical experiments illustrate the performance of the proposed optimization model and algorithm.

Bibtex

@inproceedings{jaumard_optimal_2018,
  location = {Bucharest},
  title = {Optimal Design of Filterless Optical Networks},
  rights = {All rights reserved},
  isbn = {978-1-5386-6605-0},
  url = {https://ieeexplore.ieee.org/document/8473596/},
  doi = {10.1109/ICTON.2018.8473596},
  eventtitle = {2018 20th International Conference on Transparent Optical
                    Networks ({ICTON})},
  pages = {1--5},
  booktitle = {2018 20th International Conference on Transparent Optical
                   Networks ({ICTON})},
  publisher = {{IEEE}},
  author = {Jaumard, Brigitte and Wang, Yan and Huin, Nicolas},
  urlyear = {2021-05-29},
  year = {2018}
}

Provably Efficient Algorithms for Placement of Service Function Chains with Ordering Constraints

by Tomassilli, A. and Giroire, F. and Huin, N. and Perennes, S.
in IEEE INFOCOM 2018 - IEEE Conference on Computer Communications

Abstract

A Service Function Chain (SFC) is an ordered sequence of network functions, such as load balancing, content filtering, and firewall. With the Network Function Virtualization (NFV) paradigm, network functions can be deployed as pieces of software on generic hardware, leading to a flexibility of network service composition. Along with its benefits, NFV brings several challenges to network operators, such as the placement of virtual network functions. In this paper, we study the problem of how to optimally place the network functions within the network in order to satisfy all the SFC requirements of the flows. Our optimization task is to minimize the total deployment cost. We show that the problem can be seen as an instance of the Set Cover Problem, even in the case of ordered sequences of network functions. It allows us to propose two logarithmic factor approximation algorithms which have the best possible asymptotic factor. Further, we devise an optimal algorithm for tree topologies. Finally, we evaluate the performances of our proposed algorithms through extensive simulations. We demonstrate that near-optimal solutions can be found with our approach.

Bibtex

@inproceedings{tomassilli_provably_2018,
  location = {Honolulu, {HI}},
  title = {Provably Efficient Algorithms for Placement of Service Function
               Chains with Ordering Constraints},
  rights = {All rights reserved},
  isbn = {978-1-5386-4128-6},
  url = {https://ieeexplore.ieee.org/document/8486275/},
  doi = {10.1109/INFOCOM.2018.8486275},
  eventtitle = {{IEEE} {INFOCOM} 2018 - {IEEE} Conference on Computer
                    Communications},
  pages = {774--782},
  booktitle = {{IEEE} {INFOCOM} 2018 - {IEEE} Conference on Computer
                   Communications},
  publisher = {{IEEE}},
  author = {Tomassilli, A. and Giroire, F. and Huin, N. and Perennes, S.},
  urlyear = {2021-05-29},
  year = {2018}
}

2017

Bringing Energy Aware Routing Closer to Reality with SDN Hybrid Networks

by Huin, N. and Rifai, M. and Giroire, F. and Lopez Pacheco, D. and Urvoy-Keller, G. and Moulierac, J.
in GLOBECOM 2017 - 2017 IEEE Global Communications Conference

Abstract

Energy aware routing aims at reducing the energy consumption of ISP networks. The idea is to adapt routing to the traffic load in order to turn off some hardware. However, it implies to make dynamic changes to routing configurations which is almost impossible with legacy protocols. The Software Defined Network ( SDN) paradigm bears the promise of allowing a dynamic optimization with its centralized controller. In this work, we propose SENAtoR, an algorithm to enable energy aware routing in a scenario of progressive migration from legacy to SDN hardware. Since in real life, turning off network equipments is a delicate task as it can lead to packet losses, SENAtoR provides also several features to safely enable energy saving services: tunneling for fast rerouting, smooth node disabling and detection of both traffic spikes and link failures. We validate our solution by extensive simulations and by experimentation. We show that SENAtoR can be progressively deployed in a network using the SDN paradigm. It allows to reduce the energy consumption of ISP networks by 5 to 35% depending on the penetration of SDN hardware, while diminishing the packet loss rate compared to legacy protocols.

Bibtex

@inproceedings{huin_bringing_2017,
  location = {Singapore},
  title = {Bringing Energy Aware Routing Closer to Reality with {SDN} Hybrid
               Networks},
  rights = {All rights reserved},
  isbn = {978-1-5090-5019-2},
  url = {http://ieeexplore.ieee.org/document/8254456/},
  doi = {10.1109/GLOCOM.2017.8254456},
  eventtitle = {2017 {IEEE} Global Communications Conference ({GLOBECOM} 2017)
                    },
  pages = {1--7},
  booktitle = {{GLOBECOM} 2017 - 2017 {IEEE} Global Communications Conference},
  publisher = {{IEEE}},
  author = {Huin, N. and Rifai, M. and Giroire, F. and Lopez Pacheco, D. and Urvoy-Keller, G. and Moulierac, J.},
  urlyear = {2021-05-29},
  year = {2017}
}

Optimization of network service chain provisioning

by Huin, Nicolas and Jaumard, Brigitte and Giroire, Frederic
in 2017 IEEE International Conference on Communications (ICC)

Abstract

Software-Defined Networking is a new approach to the design and management of networks. It decouples the software-based control plane from the hardware-based data plane while abstracting the underlying network infrastructure and moving the network intelligence to a centralized software-based controller where network services are deployed. The challenge is then to efficiently provision the service chain requests, while finding the best compromise between the bandwidth requirements, the number of locations for hosting Virtual Network Functions (VNFs ), and the number of chain occurrences. We propose two ILP (Integer Linear Programming) models for routing service chain requests, one of them with a decomposition modeling. We conduct extensive numerical experiments, and show we can solve exactly the routing of service chain requests in a few minutes for networks with up to 50 nodes, and traffic requests between all pairs of nodes. We investigate the best compromise between the bandwidth requirements and the number of VNF nodes.

Bibtex

@inproceedings{huin_optimization_2017,
  location = {Paris, France},
  title = {Optimization of network service chain provisioning},
  rights = {All rights reserved},
  isbn = {978-1-4673-8999-0},
  url = {http://ieeexplore.ieee.org/document/7997198/},
  doi = {10.1109/ICC.2017.7997198},
  eventtitle = {{ICC} 2017 - 2017 {IEEE} International Conference on
                    Communications},
  pages = {1--7},
  booktitle = {2017 {IEEE} International Conference on Communications ({ICC})},
  publisher = {{IEEE}},
  author = {Huin, Nicolas and Jaumard, Brigitte and Giroire, Frederic},
  urlyear = {2021-05-29},
  year = {2017}
}

2016

MINNIE : enfin un monde SDN sans (trop de) règles

by Rifai, Myriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Frédéric and Moulierac, Joanna and Lopez Pacheco, Dino and Urvoy-Keller, Guillaume
in ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

Le paradigme des Software Defined Networks (SDNs), ou ré seaux programmables, gagne en popularité ces dernières années. Il permet d’obtenir un meilleur contrôle sur le r éseau en regroupant l’intelligence des commutateurs ou des routeurs sur un ou plusieurs contrôleurs. Cependant, ce gain se fait au détriment de la taille disponible pour les tables de "forwarding" des équipements SDN qui utilisent des m\’e moires spécifiques de petite taille. Dans ce papier, nous proposons MINNIE, un algorithme de routage SDN se fondant sur des techniques de compression de règles pour réduire la taille des tables. Nous le validons par simulation pour diffé rentes topologies de réseaux de centres de données, et par expérimentation sur une plateforme de type fat tree composée de 20 commutateurs. Côté simulation , nous montrons que MINNIE peut supporter aux alentours d’un million de flots lorsque la limite est de seule-ment 1000 règles par table, et avec des temps de calcul (routage et compression) n \’e gligeables. Côté expérimentation, nous montrons que, sans MINNIE, la limite de règles peut être rapidement atteinte avec un faible nombre de clients, ce qui accroı̂t le délai sur le réseau. Avec MINNIE, le nombre de rè gles est réduit de manière importante sans introduire de perte de paquets ni de délai supplémentaire visible. Dans les deux cas, MINNIE affiche des taux de compression de tables entre 70 et 99%.

Bibtex

@inproceedings{rifai_minnie_2016-1,
  location = {Bayonne, France},
  title = {{MINNIE} : enfin un monde {SDN} sans (trop de) règles},
  rights = {All rights reserved},
  url = {https://hal.inria.fr/hal-01304687},
  eventtitle = {{ALGOTEL} 2016 - 18èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2016 - 18èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Rifai, Myriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Frédéric and Moulierac, Joanna and Lopez Pacheco, Dino and Urvoy-Keller, Guillaume},
  year = {2016}
}

Étude d’un système distribué de diffusion de vidéo en direct

by Giroire, Frédéric and Huin, Nicolas
in ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

Dans cette étude, nous nous penchons sur les systèmes pair-à-pair pour la diffusion de vidéo en direct. Ces systèmes peuvent être divisés en deux sous-groupes. Dans les systèmes non-structurés, le choix des liens sur lesquels transmettre la vidéo n’est pas régit par une structure et la diffusion se fait de façon opportuniste. Dans les systèmes structurés , la transmission s’effectue selon un ou plusieurs arbres de diffusion. Bien que les systè mes structurés offrent une diffusion plus efficace, les syst èmes non structurés sont préférés en raison de leur meilleure gestion du départ et de l’ arrivée des utilisateurs (aussi appelés churn). En effet, dans les syst\‘ emes structurés, le churn casse la structure du réseau. Dans ce papier, nous proposons plusieurs protocoles de maintenance de l’arbre de diffusion d’un système structur\’e soumis au churn. Nous fournissons une étude de ces protocoles par simulation ainsi qu’une analyse formelle de l’un d’entre eux. Nous donnons une estimation de métriques du syst ème telles que le délai ou le nombre d’interruptions et temps total d’interruption de la diffusion. Nous montrons ainsi que les réseaux structurés peuvent être facilement maintenus face au churn, tout en utilisant un faible niveau d’information sur le réseau et en étant proche d’une diffusion optimale.

Bibtex

@inproceedings{giroire_etude_2016,
  location = {Bayonne, France},
  title = {\'{E}tude d'un système distribué de diffusion de vidéo en direct},
  rights = {All rights reserved},
  url = {https://hal.inria.fr/hal-01305116},
  eventtitle = {{ALGOTEL} 2016 - 18èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2016 - 18èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Giroire, Frédéric and Huin, Nicolas},
  year = {2016},
  keywords = {pair-à-pair}
}

2015

Routage vert et compression de règles SDN

by Havet, Frédéric and Huin, Nicolas and Moulierac, Joanna and Phan, Khoa
in ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications

Abstract

La technologie SDN permet de séparer le plan de contrô le et le plan de données qui cohabitent actuellement sur les routeurs dans les architectures réseaux classiques et de r\’ e aliser le routage par un ou plusieurs contrôleur(s) centralisé(s). Nos travaux portent sur l’utilisation de cette technologie pour minimiser la consommation d’énergie dans les réseaux, notamment en permettant au contrôleur d’é teindre à distance des liens non utilisés. Une des probl ématiques est que les tables de routage SDN ne peuvent contenir qu’un nombre tr es limité de règles. Ceci est d û au type particulier de mémoire utilisé pour permettre l’ajout a distance de règles de routage par le contrôleur SDN. Dans ce papier, nous étudions le probl ème de compression de tables de routage bidimensionnelles avec priorité, en particulier la complexité algorithmique et proposons des algorithmes d’approximation. Nous proposons ensuite des algorithmes de routage vert qui effectuent en mê me temps le choix des routes, la compression des tables de routages et la mise en veille des liens non utilisés. Ces algorithmes sont testés sur les réseaux de la librairie SNDLib .

Bibtex

@inproceedings{havet_routage_2015,
  location = {Beaune, France},
  title = {Routage vert et compression de règles {SDN}},
  rights = {All rights reserved},
  url = {https://hal.archives-ouvertes.fr/hal-01148471},
  eventtitle = {{ALGOTEL} 2015 - 17èmes Rencontres Francophones sur les
                    Aspects Algorithmiques des Télécommunications},
  booktitle = {{ALGOTEL} 2015 - 17èmes Rencontres Francophones sur les Aspects
                   Algorithmiques des Télécommunications},
  author = {Havet, Frédéric and Huin, Nicolas and Moulierac, Joanna and Phan, Khoa},
  year = {2015}
}

Study of Repair Protocols for Live Video Streaming Distributed Systems

by Giroire, Frederic and Huin, Nicolas
in 2015 IEEE Global Communications Conference (GLOBECOM)

Abstract

We study distributed systems for live video streaming. These systems can be of two types: structured and unstructured. In an unstructured system, the diffusion is done opportunistically. The advantage is that it handles churn, that is the arrival and departure of users, which is very high in live streaming systems, in a smooth way. On the opposite, in a structured system, the diffusion of the video is done using explicit diffusion trees. The advantage is that the diffusion is very efficient, but the structure is broken by the churn. In this paper, we propose simple distributed repair protocols to maintain, under churn, the diffusion tree of a structured streaming system. We study these protocols using formal analysis and simulation. In particular, we provide an estimation of the system metrics, bandwidth usage, delay, or number of interruptions of the streaming. Our work shows that structured streaming systems can be efficient and resistant to churn.

Bibtex

@inproceedings{giroire_study_2015,
  location = {San Diego, {CA}, {USA}},
  title = {Study of Repair Protocols for Live Video Streaming Distributed
               Systems},
  rights = {All rights reserved},
  isbn = {978-1-4799-5952-5},
  url = {http://ieeexplore.ieee.org/document/7417647/},
  doi = {10.1109/GLOCOM.2015.7417647},
  eventtitle = {{GLOBECOM} 2015 - 2015 {IEEE} Global Communications Conference
                    },
  pages = {1--7},
  booktitle = {2015 {IEEE} Global Communications Conference ({GLOBECOM})},
  publisher = {{IEEE}},
  author = {Giroire, Frederic and Huin, Nicolas},
  urlyear = {2021-05-29},
  year = {2015}
}

2014

Too Many SDN Rules? Compress Them with MINNIE

by Rifai, Miriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Frederic and Lopez-Pacheco, Dino and Moulierac, Joanna and Urvoy-Keller, Guillaume
in 2015 IEEE Global Communications Conference (GLOBECOM)

Abstract

Software Defined Networking (SDN) is gaining momentum with the support of major manufacturers. While it brings flexibility in the management of flows within the data center fabric, this flexibility comes at the cost of smaller routing table capacities. In this paper, we investigate compression techniques to reduce the forwarding information base (FIB) of SDN switches. We validate our algorithm, called MINNIE, on a real testbed able to emulate a 20 switches fat tree architecture. We demonstrate that even with a small number of clients, the limit in terms of number of rules is reached if no compression is performed, increasing the delay of all new incoming flows. MINNIE, on the other hand, reduces drastically the number of rules that need to be stored with a limited impact on the packet loss rate. We also evaluate the actual switching and reconfiguration times and the delay introduced by the communications with the controller.

Bibtex

@inproceedings{rifai_too_2014,
  location = {San Diego, {CA}, {USA}},
  title = {Too Many {SDN} Rules? Compress Them with {MINNIE}},
  rights = {All rights reserved},
  isbn = {978-1-4799-5952-5},
  url = {https://ieeexplore.ieee.org/document/7417661},
  doi = {10.1109/GLOCOM.2014.7417661},
  shorttitle = {Too Many {SDN} Rules?},
  eventtitle = {{GLOBECOM} 2015 - 2015 {IEEE} Global Communications Conference
                    },
  pages = {1--7},
  booktitle = {2015 {IEEE} Global Communications Conference ({GLOBECOM})},
  publisher = {{IEEE}},
  author = {Rifai, Miriana and Huin, Nicolas and Caillouet, Christelle and Giroire, Frederic and Lopez-Pacheco, Dino and Moulierac, Joanna and Urvoy-Keller, Guillaume},
  urlyear = {2021-05-29},
  year = {2014}
}

Theses

2017

Energy Efficient Software Defined Networks

by Huin, Nicolas

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.

Bibtex

@thesis{huin_energy_2017,
  title = {Energy Efficient Software Defined Networks},
  url = {https://theses.hal.science/tel-01679263},
  institution = {University of C\^{o}te d'Azur, France},
  type = {phdthesis},
  author = {Huin, Nicolas},
  year = {2017},
  keywords = {\'{E}conomie d'énergie, Energy aware routing, Réseaux pilotés
                  par logiciel, Routage vert, Software defined networks ,
                  Virtualisation, Virtualization}
}

dataset

2024

Loss/Delay instances for vIGP

by Huin, Nicolas and Martin, Sébastien and Leguay, Jérémie

Bibtex

@dataset{huin_2024_dataset,
  author = {Huin, Nicolas and Martin, Sébastien and Leguay, Jérémie},
  title = {Loss/Delay instances for {vIGP}},
  month = jan,
  year = {2024},
  publisher = {Zenodo},
  version = {1.0.0},
  doi = {10.5281/zenodo.10469172},
  url = {https://doi.org/10.5281/zenodo.10469172}
}