Search

When adopting a novel mobile technology, a mobile network operator faces the dilemma of determining which is the best time to install the next generation equipment onto the existing infrastructure. In a strategic context, the best possible time for deployment is the best response to competitors' actions, subject to normative and material constraints and to the customer's adoption curve. We formulate in this paper a finite timing game in discrete-time which captures the main features of the problem for a two players formulation. Under mild assumptions on the time scale at which operators decide on the installation, we provide a methodology to obtain a subgame-perfect equilibrium for the resulting extensive form game. Our numerical results compare the utility of each player with the social optimum and describe the trade off between fixed costs and installation strategies.

International audience; We model the network slice provisioning as an optimization problem including novel mapping and provisioning requirements rising with new radio and core function placement policies. We propose an open-access framework based on an MILP formulation that encompasses flexible functional splitting, with possibly different splitting for different slices and slice subnets, while taking into account different network sharing policies from 5G specifications. We also consider novel mapping and continuity constraints specific to the 5G architectures and beyond. We show by numerical simulations the impact of taking into full and partial consideration these peculiar novel technical constraints.

Wireless data demands keep rising at a fast rate. In 2016, Cisco measured a global mobile data traffic volume of 7.2 Exabytes per month and projected a growth to 49 Exabytes per month in 2021. Wi-Fi plays an important role in this as well. Up to 60% of the total mobile traffic was off-loaded via Wi-Fi (and femtocells) in 2016. This is further expected to increase to 63% in 2021. In this publication, we look into the roll-out ofpublicWi-Fi networks, public meaning in a public or semi-public place (pubs, restaurants, sport stadiums, etc.). More concretely we look into the collaboration between two parties, a technical party and a venue owner, for the roll-out of a new Wi-Fi network. The technical party is interested in reducing load on its mobile network and generating additional direct revenues, while the venue owner wants to improve the attractiveness of the venue and consequentially generate additional indirect revenues. Three Wi-Fi pricing models are considered: entirely free, slow access with ads or fast access via paid access (freemium), and paid access only (premium). The technical party prefers a premium model with high direct revenues, the venue owner a free/freemium model which is attractive to its customers, meaning both parties have conflicting interests. This conflict has been modeled using non-cooperative game theory incorporating detailed cost and revenue models for all three Wi-Fi pricing models. The initial outcome of the game is a premium Wi-Fi network, which is not the optimal solution from an outsider’s perspective as a freemium network yields highest total payoffs. By introducing an additional compensation scheme which corresponds with negotiation in real life, the outcome of the game is steered toward a freemium solution.

This chapter gives an insight into some challenging combinatorial optimization problems that have to be tackled to deliver efficient and appropriate decision algorithms to manage future networks. The first part of the chapter is dedicated to variants of routing optimization problems in future IP networks, and the second part is dedicated to two optimization problems related to network virtualization and 5G network slicing, the virtual network embedding problem and the service function chaining problem. Each of these optimization problems is described along with the main challenges to overcome, and a recent and extensive related state of the art is given, so as to highlight the most recent and promising approaches to solve them.

International audience; In this work, we model the network slice provi-sioning as an optimization problem including novel mapping and provisioning requirements rising with new 5G radio and core function placement policies. We propose an MILP-based formulation that joins different functional splitting strategies with different network function sharing policies and novel mapping continuity constraints from 5G specifications. We show by numerical simulations the impact of taking into full and partial consideration these peculiar sets of novel technical constraints.

International audience; The Third Generation Partnership Project (3GPP) was established to bring together several standards organization to address the needs related to the specification of mobile broadband. Originally targeting the evolution from 2G to 3G, 3GPP continues at the forefront of the standardization effort leading to 5G and beyond. Given the growing diversity of services and the explosion of mobile users year by year, evolving architectures have then been successively proposed by the group in order to expand the limits of legacies systems. We overview this evolution, summarizing the transformation of core systems and their related decomposition, aggregation, and mapping operations from 3G to 5G systems. We also present an in-depth description of 5G Core based on recent technical documents delivered by 3GPP. We end with the identification of potential operational and technical challenges in 5G systems.

In this paper, we address the Unsplittable Non-Additive Capacitated Network Design problem, a variant of the Capacitated Network Design problem where the flow of each commodity cannot be split, even between two facilities installed on the same link. We propose a compact formulation and an aggregated formulation for the problem. The latter requires additional inequalities from considering each individual arc-set. Instead of studying those particular polyhedra, we consider a much more general object, the unitary step monotonically increasing set function polyhedra, and identify some families of facets. The inequalities that are obtained by specializing those facets to the Bin Packing function are separated in a Branch-and-Cut for the problem. Several series of experiments are conducted on random and realistic instances to give an insight on the efficiency of the introduced valid inequalities. HighlightsWe give two ILP formulations for the UNACND problem.We introduce polyhedra associated with a general class of functions.We provide two classes of facets that are valid for all considered functions.We devise a Branch-and-Cut algorithm embedding both classes of inequalities.Our approach gives promising results and shows the efficiency of our inequalities.

We consider the Capacitated Multi-Layer Network Design with Unsplittable demands (CMLND-U) problem. Given a two-layer network and a set of traffic demands, this problem consists in installing minimum cost capacities on the upper layer so that each demand is routed along a unique “virtual” path (even using a unique capacity on each link) in this layer, and each installed capacity is in turn associated a “physical” path in the lower layer. This particular hierarchical and unsplittable requirement for routing arises in the design of optical networks, including optical OFDM based networks. In this paper, we give an ILP formulation to the CMLND-U problem and we take advantage of its sub-problems to provide a partial characterization of the CMLND-U polytope including several families of facets. Based on this polyhedral study, we develop a Branch-and-Cut algorithm for the problem and show its effectiveness though a set of experiments, conducted on SNDlib-derived instances and also on real instances.

We consider a mobile market driven by two Mobile Network Operators (MNOs) and a new competitor Mobile Virtual Network Operator (MVNO). The MNOs can partner with the entrant MVNO by leasing network resources; however, the MVNO can also rely on other technologies such as free WiFi access points. Moreover, in addition to its connectivity offer, the MVNO can also draw indirect revenues from services due to its brand. In that framework including many access technologies and several revenue sources, a possible partner MNO will then have to decide which wholesale price to charge the MVNO for its resources. This multi-actor context, added to the need to consider both wholesale and retail markets, represents a new challenge for the underlying decision-making process. In this paper, the optimal price setting is formulated as a multi-level optimization problem which enables us to derive closed-form expressions for the optimal MNOs wholesale prices and the optimal MVNO retail price. The price attractivity of the MVNO is also evaluated in terms of its indirect revenues and the proportion of resources leased from possible partner MNOs. Finally, through a game-theoretical approach, we characterize the scenario where both MNOs partner with the MVNO as the unique Nash equilibrium under appropriate conditions., Accepted in IFIP Networking 2018. Key words: Network Economics, Strategic Partnership, Multi-Level Optimization, Non-Cooperative Game Theory

We investigate a variant of the Multi-Layer Network Design problem where minimum cost capacities have to be installed upon a virtual layer in such a way that (i) a set of traffic demands can be routed AND (ii) each capacity (subband) is assigned a route in the physical layer. The traffic demands cannot be splitted along several paths (nor even several capacities installed on the same link), which makes the problem even more difficult. In this paper, we present new non-compact ILP formulations to model the problem and provide column generation procedures, based on different Dantzig-Wolfe decomposition schemes to solve it. More precisely, an arc-flow formulation is given for the problem and used to derive two different paths formulations: non-aggregated and aggregated. The former contains two families of path variables and requires a double column generation procedure to solve it, while the latter relies on a single path variable with a specific structure. These alternative modeling approaches induce two Branch-and-Price algorithms that allow to solve the problem efficiently for several classes of instances.

International audience; In this paper, we consider the Capacitated Network Design (CND) problem. We investigate the relationship between CND and the Bin-Packing problem. This is exploited for identifying new classes of valid inequalities for the CND problem and developing a branch-and-cut algorithm to solve it efficiently.

In this paper, we are interested in the Optical Multi-Band Network Design. This problem consists, given the physical layer of an optical network and a set of traffic demands, in designing a virtual layer and grooming the traffic demands on virtual links called subbands, then to determine the number of subbands and the wavelength to assign for each subband of the virtual layer. We first propose a node-arcs, and arc-paths integer linear programming formulations for the problem, then we describe the column generation procedure for solving the linear relaxation of the 0-1 arc-paths formulations.

In this paper we consider the traffic Grooming, Routing and Wavelength Assignment problem in optical WDM mesh networks. This is a network design problem which consists in grooming the demands in lightpaths, assigning a wavelength to each lightpath and routing the traffic on these lightpaths so that the total cost is minimum. We first give an Integer Linear Programming formulation for the problem. Then we discuss a preprocessing procedure for efficiently managing the existing resources of the network. We then propose a fast and effective heuristic for solving large and real instances of the problem. We finally provide an illustrative application of the proposed heuristic for a real backhaul network instance.