How to design graphs with low forwarding index and limited number of edges

Frédéric Giroire 1 Stéphane Pérennes 1 Issam Tahiri 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The (edge) forwarding index of a graph is the minimum, over all possible rout-ings of all the demands, of the maximum load of an edge. This metric is of a great interest since it captures the notion of global congestion in a precise way: the lesser the forwarding-index, the lesser the congestion. In this paper, we study the following design question: Given a number e of edges and a number n of vertices, what is the least congested graph that we can construct? and what forwarding-index can we achieve? Our problem has some distant similarities with the well-known (∆, D) problem, and we sometimes build upon results obtained on it. The goal of this paper is to study how to build graphs with low forwarding indices and to understand how the number of edges impacts the forwarding index. We answer here these questions for different families of graphs: general graphs, graphs with bounded degree, sparse graphs with a small number of edges by providing constructions, most of them asymptotically optimal. For instance, we provide an asymptotically optimal construction for (n, n + k) cubic graphs-its forwarding index is ∼ n 2 3k log 2 (k). Our results allow to understand how the forwarding-index drops when edges are added to a graph and also to determine what is the best (i.e least congested) structure with e edges. Doing so, we partially answer the practical problem that initially motivated our work: If an operator wants to power only e links of its network, in order to reduce the energy consumption (or wiring cost) of its networks, what should be those links and what performance can be expected?
Type de document :
Communication dans un congrès
26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Oct 2015, Verona, Italy. Springer-Verlag Lecture Notes in Computer Science
Liste complète des métadonnées


https://hal.inria.fr/hal-01221650
Contributeur : Frédéric Giroire <>
Soumis le : mercredi 28 octobre 2015 - 13:15:45
Dernière modification le : jeudi 29 octobre 2015 - 01:09:21
Document(s) archivé(s) le : vendredi 28 avril 2017 - 08:03:46

Fichier

iwoca15-camera-ready (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01221650, version 1

Collections

Citation

Frédéric Giroire, Stéphane Pérennes, Issam Tahiri. How to design graphs with low forwarding index and limited number of edges. 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Oct 2015, Verona, Italy. Springer-Verlag Lecture Notes in Computer Science. <hal-01221650>

Partager

Métriques

Consultations de
la notice

122

Téléchargements du document

153