Project : mascotte
Section: New Results
Network design
Designing a backbone network consists in computing paths for each traffic unit and then in assigning resources along these paths. The set of paths is chosen according to the technology, the protocol or the quality of service constraints. For instance, optical backbones use the wdm technology to take better advantage of the capacity of the optical fibers often already installed. This is achieved through multiplexing several wavelength channels onto the same fiber. In wdm networks, the huge bandwidth available on an optical fiber is divided into multiple channels. Each channel carries bandwidth up to several gigabits per second. A minimum unit of resource allocation is an optical channel, which consists of a path and a wavelength assigned on each link along the path and is called a lightpath. If wavelength translation is performed in optical switching, then each channel may be assigned different wavelengths on each link along the path; otherwise the wavelength continuity constraint must be satisfied on all links along the path. Of course, two lightpaths sharing a link must use different wavelengths on that link.
In the following we stress the problems and solutions we have investigated. This includes results for the wavelength routing and coloring problem, for the traffic grooming problem and for the virtual network embedding problem (with application to atm networks).
Routing and Wavelength Assignment Problem.
[36] [37] [57] [12]Motivated by the quest for efficient algorithms for the Routing and Wavelength Assignment problem (RWA), we address approximations of the fractional multicommodity flow problem which is the central part of a complex randomized rounding algorithm for the integral problem. Through the use of dynamic shortest path computations and other combinatorial approaches, we improve on the best known algorithm for approximations of the fractional multicommodity flow.
We addressed the design of multi-fiber optical networks. We show that the wavelength assignment constraints change from peer conflicts in mono-fiber networks to group conflicts in multi-fiber networks. We developed a new model for the wavelength assignment problem based on conflict hypergraphs which structurally capture the group conflicts. This model allows for adapting hypergraph coloring approximation algorithms to the wavelength assignment problem, and for validating them on real world networks [25] [41].
Traffic Grooming.
Efficient optical routing aims to minimize the number of different wavelengths used in the network but also the number of electronic/optical conversions (hops for lightpaths). Another way for reducing the cost of the network is to group the traffic in such a way that some units of traffic may share some optical channels.
In [29] [30] [16] [24] [18] we address the problem of traffic grooming in wdm rings with All-to-All uniform unitary traffic. The goal is to minimize the total number of sonet add-drop multiplexers (adms) required. We have shown that this problem corresponds to a partition of the edges of the complete graph into subgraphs, where each subgraph has at most C edges (where C is the grooming ratio) and where the total number of vertices has to be minimized. Using tools of graph and design theory, we optimally solve the problem for practical values and infinite congruence classes of values for a given C . Among others, we give optimal constructions when and results when . We also show how to improve lower bounds by using refined counting techniques, and how to use efficiently an ilp program by restricting the search space.
In [43] [52] [32] we develop traffic grooming algorithms for wdm networks with multi-layer switches. We consider a node as an N -layer switch, in which a given layer k is an aggregate set of elements of layer . Typical examples of layers are wavelengths, bands and fibers. The cost of a given node depends on the number of input and output ports of each layer. Assuming this model and a traffic matrix - with unity elements in layer 0 - minimizing the cost of the network will consist in grooming traffic in such a way that as much traffic as possible will be switched in the highest possible layer (fibers in our example). When some traffic is switched along a path in the network within the same layer, we represent it as a pipe. Each pipe has an associated linear cost depending on the current layer and on the number of nodes crossed in that pipe. We present an integer linear programming formulation for this model that aims to minimize the overall cost of the network for a given input traffic matrix. We ran experiments using the cplex optimization package on various topologies such as actual networks like the Pan-European all optical network as well as rings and meshes of various sizes.
Virtual Path Layout.
Another network design issue is the Virtual Path Layout problem (vpl for short). vpl consists in embedding a logical topology into a physical one. Our first concern was with atm networks but the results extend to other types of networks as well. The logical topology models the set of communication requests. For each communication request a path is associated into the physical network and we measure the quality of service as the maximum length of these paths, i.e the virtual network diameter denoted by D . The problem is to design a network of diameter at most D with a minimum edge congestion [21]. When the problem reduces to minimizing the edge congestion. When we solved (asymptotically) the problem for the All-to-All communication instance over path networks . We also obtained asymptotic bounds for the cycle network (sharp bounds when ).
Other network design
We address the problem of network design for which we present a new class of valid inequalities. These inequalities arise from the "blossom" constraints of the b-matching problem. We show that the separating problem over this class of inequalities can be solved in a polynomial time of the dimension of the space in which the problem is defined [44].
During the seventies, new needs came with the numerisation of networks. To meet these needs, the SDH technology was standardized by the UIT-T. A set of interconnected rings is a possible topology for a SDH network which provides a high protection degree. We found an heuristic method to design such a ring topology, given a set of geographical sites to be connected within the same network [58].
