ABSTRACT This paper introduces a variant of the dynamic Facility Location Problem with modular capacities. Inspired by the challenges faced by cellular telecommunication networks, the problem seeks to optimize the placement and equipment of facilities to meet the fluctuating demand of clients while minimizing installation and operational costs. Selected facilities must provide coverage to the whole considered area. In addition, clients must be served by the active facility that provides the best quality of service. We propose two integer linear programming formulations and analyze their theoretical properties in terms of lower bound. Furthermore, we propose a reinforcement for one formulation and valid inequalities. To evaluate the performance of the proposed formulations, we performed computational experiments with a commercial solver on instances with up to 20 candidate sites and 60 clients. The formulations proved to be very sensitive to the size of the instances. The analysis, both theoretical and numerical, provides meaningful insights on the formulations performance, and it constitutes a key starting point for developing further approaches, either exact methods or heuristics.

The Network Function Virtualization (NFV) service chaining problem, which involves locating Virtual Network Functions (VNFs) in an NFV-enabled network and routing network demands through their required VNFs, is key to the success of NFV. Solving the chaining problem can efficiently reduce required network resources, and thus reducing capital expenditures (CAPEX) and operational expenditures (OPEX). Previous works mainly focus on finding heuristic solutions, rather than investigating the intrinsic features of the problem. In this paper, we investigate the features of the problem from both theoretical and numerical points of view, by shrinking the NFV service chaining problem into a particular version and conducting tests to study what makes the NFV service chaining problem fundamentally difficult to solve. Results reveal that the demand routing part of the problem has a significant impact on solving the mathematical formulated problem, i.e., finding a feasible routing can be time-consuming. We further propose constructive methods that improve upon the mathematical formulation, which make the time of finding the optimal solution be reduced in most cases.

Abstract Thanks to the increased availability of computing capabilities in data centers, the recently proposed virtual network function paradigm can be used to keep up with the increasing demand for network services as internet and its applications grow. The problem arises then of managing the virtual network functions, that is, to decide where to instantiate the functions and how to route the demands to reach them. While it arises in an application field, the Virtual Network Function placement and routing problem combines location and routing aspects in an interesting, challenging problem. In this paper, we propose several ILP‐based heuristics and compare them on a dataset that includes instances with different sizes, network topologies, and service capacity. The heuristics prove effective in tackling even large size instances, with up to 50 nodes and more than 80 arcs.

Abstract The mass diffusion of internet applications, both from computers and mobiles, has yielded to an increasing demand for network services with which the expensive and not flexible hardware appliances cannot keep up. On the other hand, computational capability has become available on the network nodes connected with computing servers and the cloud. This has suggested the network functions virtualization paradigm: services are provided on a software basis thus giving a flexible and cost effective response to the request for services. The network functions virtualization proposes challenging optimization problems such as the virtual network functions (VNFs) chaining problem, where service instances must be located on some network nodes and each demand must be routed through the services it requires. Most of the literature is currently focused on heuristic solutions, rather than on studying the problem properties or comparing approaches. With the aim of investigating the problem properties and comparing existing formulations, both from the theoretical and the numerical points of view, we consider a single service VNFs chaining problem, with different link and service capacities and the objective of minimizing the number of installed VNF instances.

This article focuses on the problem of minimizing the energy consumption in a resilient telecommunications network. For each demand, an edge‐disjoint pair of paths (primary and backup) must be provided and the shared protection scheme is used. The energy consumption is due only to edges used in the no‐fault scenario, but both primary and backup paths contribute to capacity consumption. We propose a projected formulation for the problem and show its effectiveness by comparing it with the complete formulation. We propose valid inequalities for both formulations. We evaluate the performances of the proposed formulations and valid inequalities through computational tests. Furthermore, we investigate the relationship between the shared and the dedicated protection version of the problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 6–22 2017

The rapid evolution of mobile radio network technologies poses severe technical and economical challenges to mobile network operators (MNOs); on the economical side, the continuous roll-out of technology updates is highly expensive, which may lead to the extreme, where offering advanced mobile services becomes no longer affordable for MNOs which thus, are not incentivized to innovate. Mobile infrastructure sharing among MNOs becomes then an important building block to lower the required per-MNO investment cost involved in the technology roll-out and management phases. We focus on a radio access network (RAN) sharing situation where multiple MNOs with a consolidated network infrastructure coexist in a given set of geographical areas; the MNOs have then to decide if it is profitable to upgrade their RAN technology by deploying additional small-cell base stations and whether to share the investment (and the deployed infrastructure) of the new small-cells with other operators. We address such strategic problems by giving a mathematical framework for the RAN infrastructure sharing problem which returns the “best” infrastructure sharing strategies for operators (coalitions and network configuration) when varying techno-economic parameters such as the achievable throughput in different sharing configurations and the pricing models for the service offered to the users. The proposed formulation is then leveraged to analyze the impact of the aforementioned parameters/input in a realistic mobile network environment based on LTE technology.

To accommodate the ever-growing traffic load and bandwidth demand generated by mobile users, mobile network operators (MNOs) need to frequently invest in high spectral efficiency technologies and increase their hold of spectrum resources; MNOs have then to weigh between building individual networks or entering into network and spectrum sharing agreements. We address here the problem of radio access network and spectrum sharing in 4G mobile networks by focusing on a case when multiple MNOs plan to deploy small cell base stations in a geographical area in order to upgrade their existing network infrastructure. We propose two cooperative game models (with and without transferable utility) to address the proposed problem: for given network (user throughput, MNO market, and spectrum shares) and economic (coalition cost and mobile data pricing model) settings, the proposed models output a cost division policy that guarantees coalition (sharing agreement) stability.

This work considers the strategic situation which arises when Mobile Network Operators (MNOs) coexisting in a given geographical area have to decide whether to invest in new radio access technology and whether to share the investment (and the infrastructure) with other operators. We focus on heterogeneous networks (HetNet) where MNOs add a layer of small cells to their existing macro cells. We address such strategic scenario by proposing a Mixed Integer Linear Programming formulation of the infrastructure sharing problem which takes as input techno-economic parameters as the achievable throughput in different sharing configurations, the pricing models for the service offered to the end users and the expectations on the return on investment for the mobile operators, and returns as output the “best” infrastructure/investment sharing options for the MNOs. The proposed formulation is finally leveraged to analyze the dynamics involved in the infrastructure sharing process under different techno-economic conditions in realistic network scenarios.

Recent data confirm that the power consumption of the information and communications technologies (ICT) and of the Internet itself can no longer be ignored, considering the increasing pervasiveness and the importance of the sector on productivity and economic growth. Although the traffic load of communication networks varies greatly over time and rarely reaches capacity limits, its energy consumption is almost constant. Based on this observation, energy management strategies are being considered with the goal of minimizing the energy consumption, so that consumption becomes proportional to the traffic load either at the individual-device level or for the whole network. The focus of this paper is to minimize the energy consumption of the network through a management strategy that selectively switches off devices according to the traffic level. We consider a set of traffic scenarios and jointly optimize their energy consumption assuming a per-flow routing. We propose a traffic engineering mathematical programming formulation based on integer linear programming that includes constraints on the changes of the device states and routing paths to limit the impact on quality of service and the signaling overhead. We show a set of numerical results obtained using the energy consumption of real routers and study the impact of the different parameters and constraints on the optimal energy management strategy. We also present heuristic results to compare the optimal operational planning with online energy management operation .

We propose a multi-period model to minimize the energy consumption of IP networks while guaranteeing the satisfaction of all the traffic demands. Energy savings are achieved by putting into sleep mode cards and chassis. The multi-period optimization is constrained by inter-period limitations necessary to guarantee the stability of the networks. Both exact and heuristic solutions are proposed. Results show that up to 50% of the energy savings can be achieved for realistic test scenarios in networks operated with flow-based routing protocols (i.e. MPLS).

Abstract In many telecommunication networks, a given set of client nodes must be served by different sets of facilities—providing different services and having different capabilities—which must be located and dimensioned in the design phase. Network topology must be designed as well, by assigning clients to facilities and facilities to higher level entities, when necessary. We tackle a particular location problem, where two sets of facilities have to be located, and in which different devices can be installed at each site, providing different capacities at different costs. We optimize location and dimensioning of these facilities simultaneously. We introduce a compact formulation of that problem, we use discretization and Dantzig–Wolfe reformulation techniques to improve models, and we design an exact optimization algorithm. We test our approach on a set of instances derived from existing literature on facility location. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Energy demand management for residential users is a promising research area within the Smart Grid revolution. The whole energy generation and distribution system performance can indeed be improved by optimizing the house energy management while still meeting the energy needs of customers. In this paper we propose Non-Cooperative models for the optimal planning of energy loads of a single house, with the final goal of minimizing the energy bill. A Pre-emptive variant of the model is also presented where some appliances activities can be interrupted in some phases. Finally, Cooperative models are defined for jointly managing the energy consumption of a group of users in order to easily decrease the aggregated maximum power demand, thus reducing the peak absorption. Numerical results, obtained applying models on realistic data, are presented and discussed.

Abstract This article presents a column generation approach to a resource allocation problem arising in managing Wireless Mesh Networks. The problem consists in routing the given demands over the network and to allocate time resource to pairs of nodes. Half‐duplex constraints are taken into account together with the aggregate interference due to simultaneous transmissions, which affects the signal quality. Different problems are considered, according to the assumptions on the transmission power and rate. The resource allocation problem can be formulated as a Mixed Integer Linear Programming (MILP) problem and dealt with a column generation‐based approach. The pricing problem, due to signal quality constraints, turns out to be computationally demanding. To tackle these difficulties, besides a classical mathematical programming approach, we have applied a hybrid column generation approach where the pricing subproblem is solved using Constraint Programming. Numerical results show that the two methods are comparable. The results of the column generation are then used to solve heuristically the problem. The obtained results provide very small gaps (between lower bounds and Heuristic solutions) for two of the three considered problems and reasonable gaps for the third problem. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

The new packet services and applications are radically changing not only traffic demands but also the architecture of transport networks. Adding packet layer support into backbone nodes is considered an important opportunity by telecom carriers that want to integrate packet technologies of the access and metropolitan networks within their networks to improve efficiency and flexibility. In this context, Multi- Protocol Label Switching (MPLS) is at the moment the most promising and popular packet technology. The resulting new network architecture requires new models and methodologies for designing the network in a cost effective way. The classical network design approaches are no longer appropriate since they cannot capture the traffic aggregation effect due to the added packet layer and new multi-layer network design models must be adopted. In a previous work we proposed a mathematical programming model for the design of two-layers networks in the presence of point-to-point traffic demands. In this paper we extend the model to the case of multicast services which are becoming more and more popular due to IPTV applications. A MPLS layer is considered on top of a transport network (SDH or WDM depending on required link speed) and the conflicting effects of the additional cost of MPLS support in the nodes, and the cost saving due to traffic aggregation are taken into account in the models. Traffic aggregation allows to save bandwidth due to the statistical multiplexing and the granularity of capacity values available for links and nodes. We present a MIP (Mixed Integer Programming) model for the problem that aims at optimizing the number and location of MPLS nodes in the network and the link capacity dimensioning. The problem includes the minimum cost Steiner-tree problem as a special case and is, therefore, NP-hard. We propose a local search based heuristic. This algorithm provides reasonable good solutions in short computational time as shown by the computational results obtained for realistic instances.

Wireless MESH networks are a new networking paradigm that allow to extend the coverage of traditional wireless access networks with multi-hop connections through fixed wireless mesh routers. Wireless MESH networks partially replace wired backbone networks, and it is reasonable to carefully plan radio resource assignment in order to provide quality guarantees to traffic flows. Differently from ad hoc networks, energy consumption is usually not a problem with wireless MESH routers, routes are quite stable and bandwidth requirements of traffic flows can be considered almost constants. In this paper we study the scheduling optimization problem in wireless MESH networks assuming a time division multiple access (TDMA) scheme, a dynamic power control able to vary emitted power slot-by-slot, and a rate adaptation mechanism that sets transmission rates according to the signal-to-interference-and-noise ratio (SINR). Traffic quality requirements are expressed in terms of minimum bandwidth and modelled with constraints defining the number of information units (packets) that must be transmitted on each link per frame. We propose an alternative problem formulation where decision variables represent compatible sets of links active in the same slot. Approaches to solve both lower and upper bound for the problem are proposed: since compatible set variables are exponentially many, we use column generation to compute a lower bound for the problem. Heuristic approaches to compute feasible integer solutions are proposed and tested

Abstract This article deals with a Hub Location Problem arising in Telecommunication Network Design. The considered network presents two different kinds of nodes: access nodes, that represent source and destination of traffic demands but cannot be directly connected, and transit nodes, that have no own traffic demand but collect traffic from access nodes and route it through the network. Transit nodes are supposed to be fully connected. Given a set of access nodes and a set of potential locations for the transit nodes, the problem is to decide number and positions of the transit nodes to guarantee that all access nodes are allocated to a transit node, satisfying capacity constraints. The goal is to minimize the total cost of the network, which is the sum of connection costs and nodes fixed costs. The problem is a Hub Location Problem, which is known to be NP‐hard. A local search approach is proposed, and different metaheuristic algorithms, such as tabu search, iterated local search and random multistart, have been developed, based on such local search. [A preliminary procedure has been developed in a research project joint with Telecom Italia (Turin Research & Innovation Laboratories) and a patent application has been filed to cover this issue.] © 2004 Wiley Periodicals, Inc. NETWOEKS, Vol. 44(2), 94–105 2004

In this paper, we address the problem of determining an optimal topology for Bluetooth wireless personal area networks (BT-WPAN). In BT-WPAN, multiple communication channels are available, thanks to the use of a frequency hopping technique. The way network nodes are grouped to share the same channel, and which nodes are selected to bridge traffic from a channel to another, has a significant impact on the capacity and the throughput of the system, as well as the nodes' battery lifetime. The determination of an optimal topology is thus extremely important; nevertheless, to the best of our knowledge, this problem is tackled here for the first time. Our optimization approach is based on a model derived from constraints that are specific to the BT-WPAN technology, but the level of abstraction of the model is such that it can be related to the more general field of ad hoc networking. By using a min-max formulation, we find the optimal topology that provides full network connectivity, fulfills the traffic requirements and the constraints posed by the system specification, and minimizes the traffic load of the most congested node in the network, or equivalently its energy consumption. Results show that a topology optimized for some traffic requirements is also remarkably robust to changes in the traffic pattern. Due to the problem complexity, the optimal solution is attained in a centralized manner. Although this implies severe limitations, a centralized solution can be applied whenever a network coordinator is elected, and provides a useful term of comparison for any distributed heuristics.