We investigate a network design problem under traffic uncertainty which arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network so as to support all … Read more
In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of … Read more
In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formulation by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation … Read more
We consider the problem of installing a two-level telecommunication network. Terminal nodes communicate with each other through hubs. Hubs can be installed on terminal nodes and they are interconnected by a complete network. Each terminal is connected to a hub node by direct links. The aim is to minimize the cost of installing hubs and … Read more
Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing … Read more
A traffic matrix $D^1$ dominates a traffic matrix $D^2$ if $D^2$ can be routed on every (capacitated) network where $D^1$ can be routed. We prove that $D^1$ dominates $D^2$ if and only if $D^1$, considered as a capacity vector, supports $D^2$. We show several generalizations of this result. Citation Centro Vito Volterra, Universita’ di Roma … Read more
The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more
We discuss interior point methods for large-scale linear programming, with an emphasis on methods that are useful for problems arising in telecommunications. We give the basic framework of a primal-dual interior point method, and consider the numerical issues involved in calculating the search direction in each iteration, including the use of factorization methods and/or preconditioned … Read more
We investigate a planning problem arising in the forthcoming Digital Video Broadcasting (DVB-T) system. Unlike current analog systems, the DVB-T standard allows a mitigation of the interference by means of a suitable synchronization of the received signals. The problem we describe in this paper is that of finding a time offset to impose to the … Read more
We show in this work how the problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition coloring problem in a conflict graph. A new tabu search heuristic is also proposed for the … Read more