Publications
Following the customs in our team, the alphabetic order of authors is employed for every paper other than Energy Efficient Content Distribution in an ISP Network.
Journal papers
 J. Araujo, JC. Bermond, F. Giroire, F. Havet, D. Mazauric and R.
Modrzejewski.
Weighted Improper Colouring. Journal of Discrete Algorithms
volume 16 (JDA 2012).
[PDF]
Abstract:In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two endvertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted $t$improper $k$colouring of $(G,w)$ is a $k$colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed the threshold $t$. We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$improper $k$colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$improper $k$colouring. We show that both problems are NPhard and first present general upper bounds for both problems; in particular we show a generalisation of Lov\'asz's Theorem for the weighted $t$improper chromatic number. Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two. We derive the weighted $t$improper chromatic number for all values of $t$.
Submitted
 J. Araujo, F. Giroire, Y. Liu, R. Modrzejewski and J. Moulierac.
Energy Efficient Content Distribution.
Computer Communications
[submitted].
[PDF]
Abstract:To optimize energy efficiency, network operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion. In this work, we study the impact of using innetwork caches and content delivery network (CDN) cooperation on an energyefficient routing. We formulate this problem as Energy Efficient Content Distribution and propose an integer linear program (ILP) and an efficient heuristic algorithm to solve it. The objective is to find a feasible routing, so that the total energy consumption of the network is minimized subject to satisfying all the demands and link capacity. We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful. Experimental results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save about 20% of power in the backbone, while 16% can be gained solely thanks to the use of caches.
Conference papers

R. Modrzejewski, L. Chiaraviglio, I. Tahiri, F.
Giroire, E. Le Rouzic, E. Bonetto, F. Musumeci, R.
Gonzalez, C. Guerrero.
Energy Efficient Content Distribution in an ISP Network.
IEEE Global Communications Conference 2013 (Globecom 2013)
[accepted].
[PDF]
Abstract:We study the problem of reducing power consumption in an Internet Service Provider (ISP) network by designing the content distribution infrastructure managed by the operator. We propose an algorithm to optimally decide where to cache the content inside the ISP network. We evaluate our solution over two case studies driven by operators feedback. Results show that the energyefficient design of the content infrastructure brings substantial savings, both in terms of energy and in terms of bandwidth required at the peering point of the operator. Moreover, we study the impact of the content characteristics and the power consumption models. Finally, we derive some insights for the design of future energyaware networks.

F. Giroire, R. Modrzejewski, N. Nisse and S. Pérennes.
Maintaining Balanced Trees For Structured Distributed Streaming
Systems.
20th International Colloquium on Structural Information and
Communication Complexity (SIROCCO 2013) [accepted].
[PDF]
Abstract:In this paper, we propose and analyze a simple localized algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any $n$node tree our process converges to a balanced tree in $O(n^2)$ turns. We then describe a more restrictive model, adding a small extra information to each node, under which we adopt our algorithm to converge in $\Theta(n \log n)$ turns. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree.

F. Giroire, S. K. Gupta, R. Modrzejewski, J. Monteiro and S. Pérennes.
Repair Time in Distributed Storage Systems. 6th International
Conference on Data Management in Cloud, Grid and P2P Systems (Globe
2013) [accepted].
[PDF]
Abstract:In this paper, we analyze a highly distributed backup storage system realized by means of nano datacenters (NaDa). NaDa have been recently proposed as a way to mitigate the growing energy, bandwidth and device costs of traditional data centers, following the popularity of cloud computing. These service providercontrolled peertopeer systems take advantage of resources already committed to alwayson set top boxes, the fact they do not generate heat dissipation costs and their proximity to users. In this kind of systems redundancy is introduced to preserve the data in case of peer failures or departures. To ensure longterm fault tolerance, the storage system must have a selfrepairing service that continuously reconstructs the fragments of redundancy that are lost. The speed of this reconstruction process is crucial for the data survival. This speed is mainly determined by how much bandwidth, which is a critical resource of such systems, is available. In the literature, the reconstruction times are modeled as independent (e.g., poissonian, deterministic, or more generally following any distribution). In practice, however, numerous reconstructions start at the same time (when the system detects that a peer has failed). Consequently, they are correlated to each other because concurrent reconstructions do compete for the same bandwidth. This correlation negatively impacts the efficiency of the bandwidth utilization and henceforth the repair time. We propose a new analytical framework that takes into account this correlation when estimating the repair time and the probability of data loss. Mainly, we introduce a queuing model in which reconstructions are served by peers at a rate that depends on the available bandwidth. We show that the load is unbalanced among peers (young peers inherently store less data than the old ones). This leads us to introduce a correcting factor on the repair rate of the system. The models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the GRID’5000 testbed platform. This new model allows system designers to operate a more accurate choice of system parameters in function of their targeted data durability.

J. Araujo, F. Giroire, Y. Liu, R. Modrzejewski and J. Moulierac.
Energy Efficient Content Distribution.
IEEE International Conference on Communications 2013 (ICC 2013)
[accepted].
[PDF]
Abstract:To optimize energy efficiency in network, operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion. In this work, we study the impact of using innetwork caches and content delivery network (CDN) cooperation on an energyefficient routing. We formulate this problem as Energy Efficient Content Distribution. The objective is to find a feasible routing, so that the total energy consumption of the network is minimized subject to satisfying all the demands and link capacity. We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful. Experimental results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save a total up to 23% of power in the backbone, while 16% can be gained solely thanks to caches.

J. Araujo, JC. Bermond, F. Giroire, F. Havet, D. Mazauric and R.
Modrzejewski.
Weighted Improper Colouring.
22nd International Workshop on Combinatorial Algorithms (IWOCA
2011)
[PDF]
Abstract:In this paper, we study a new colouring problem up to our best knowledge inspired by the imperative of practical networks. In reallife wireless networks, nodes interfere with one another with various intensities depending on numerous parameters: distance between them, the geographical topography, obstacles, etc. We model this with a noise matrix. The interference perceived by a node then is the sum of all the noise of the nodes emitting on the same frequency. The problem is then to determine the minimum number of colours (or frequencies) needed to colour the whole graph so that the interference does not exceed a given threshold. We provide several general results, such as bounds on this number of colours (e.g. a Brook's like theorem). We then study the practical case of square of infinite grids which corresponds to operators' network and a noise decreasing with the distance. We provide the chromatic number of the square, triangular and hexagonal grids for all possible admissible interference levels. Finally, we model the problem using linear programming, propose and test a heuristic and an exact branch&bound algorithms on random celllike graphs, namely the Poisson Voronoi tessellations.
Internal reports

F. Giroire, R. Modrzejewski, N. Nisse and S. Pérennes.
Maintaining Balanced Trees For Structured Distributed Streaming
Systems.
Research Report RR8309, INRIA, 05 1023.
[WWW]
[PDF]
Abstract:In this paper, we propose and analyze a simple localized algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any $n$node tree our process converges to a balanced tree in $O(n^2)$ turns. We then describe a more restrictive model, adding a small extra information to each node, under which we adopt our algorithm to converge in $\Theta(n \log n)$ turns. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree.

J. Araujo, F. Giroire, Y. Liu, R. Modrzejewski and J. Moulierac.
Energy Efficient Content Distribution.
Research Report RR8091, INRIA, 05 2013.
[WWW]
[PDF]
Abstract:To optimize energy efficiency, network operators try to switch off as many network devices as possible. Recently, there is a trend to introduce content caches as an inherent capacity of network equipment, with the objective of improving the efficiency of content distribution and reducing network congestion. In this work, we study the impact of using innetwork caches and content delivery network (CDN) cooperation on an energyefficient routing. We formulate this problem as Energy Efficient Content Distribution and propose an integer linear program (ILP) and an efficient heuristic algorithm to solve it. The objective is to find a feasible routing, so that the total energy consumption of the network is minimized subject to satisfying all the demands and link capacity. We exhibit the range of parameters (size of caches, popularity of content, demand intensity, etc.) for which caches are useful. Experimental results show that by placing a cache on each backbone router to store the most popular content, along with well choosing the best content provider server for each demand to a CDN, we can save about 20% of power in the backbone, while 16% can be gained solely thanks to the use of caches.

J. Araujo, JC. Bermond, F. Giroire, F. Havet, D. Mazauric
and R. Modrzejewski.
Weighted Improper Colouring.
Research Report RR7590, INRIA, 04 2011.
[WWW]
[PDF]
Abstract:In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph $(G,w)$ where the weight function $w$ on the edges of $G$ represents the noise (interference) between the two endvertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted $t$improper $k$colouring of $(G,w)$ is a $k$colouring of the nodes of $G$ (assignment of $k$ frequencies) such that the interference at each node does not exceed the threshold $t$. We consider here the Weighted Improper Colouring problem which consists in determining the weighted $t$improper chromatic number defined as the minimum integer $k$ such that $(G,w)$ admits a weighted $t$improper $k$colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number $k$ of colours, we want to determine the minimum real $t$ such that $(G,w)$ admits a weighted $t$improper $k$colouring. We first present general upper bounds for both problems; in particular we show a generalisation of Lovász's Theorem for the weighted $t$improper chromatic number. We then show how to transform an instance of the Threshold Improper Colouring problem into another equivalent one where the weights are either one or $M$, for a sufficiently large $M$. Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two. We derive the weighted $t$improper chromatic number for all values of $t$. Finally, we model the problem using integer linear programming, propose and test heuristic and exact BranchandBound algorithms on random celllike graphs, namely the PoissonVoronoi tessellations.

F. Giroire, S. K. Gupta, R. Modrzejewski, J. Monteiro and S. Pérennes.
Analysis of the Repair Time in Distributed Storage Systems.
Research Report RR7538, INRIA, 02 2011.
[WWW]
[PDF]
Abstract:Distributed or peertopeer storage systems introduce redundancy to preserve the data in case of peer failures or departures. To ensure longterm fault tolerance, the storage system must have a selfrepair service that continuously reconstructs lost fragments of redundancy. The speed of this reconstruction process is crucial for the data survival. This speed is mainly determined by available bandwidth, a critical resource of such systems. We propose a new analytical framework that takes into account the correlation of concurrent repairs when estimating the repair time and the probability of data loss. Mainly, we intro duce queuing models in which reconstructions are served by peers at a rate that depends on the available bandwidth. The models and schemes proposed are validated by mathematical analysis, extensive set of simulations, and experimentation using the Grid'5000 testbed platform.
Above list is up to date as of: Mon May 27 16:04:55 CEST 2013