Optimal design of switched Ethernet networks implementing the Multiple Spanning Tree Protocol

Bernard Fortz 1, 2 Luis Gouveia 3 Martim Joyce-Moniz 1
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Switched Ethernet networks rely on the Spanning Tree Protocol (STP) to ensure a cycle-free connectivity between nodes, by reducing the topology of the network to a spanning tree. The Multiple Spanning Tree Protocol (MSTP) allows for the providers to partition the traffic in the network and assign it to different virtual local area networks, each satisfying the STP. In this manner, it is possible to make a more efficient use of the physical resources in the network. In this paper we consider the traffic engineering problem of finding optimal designs of switched Ethernet networks implementing the MSTP, such that the worst-case link utilization is minimized. We show that this problem is N P-hard. We propose three mixed-integer linear programming formulations for this problem. Through a large set of computational experiments, we compare the performance of these formulations. Until now, the problem was almost exclusively solved with heuristics. Our objective here is provide a first comparison of different models that can be used in exact methods.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2018, 234, pp.114 - 130. 〈10.1016/j.dam.2016.07.015〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01665614
Contributeur : Bernard Fortz <>
Soumis le : samedi 16 décembre 2017 - 14:23:14
Dernière modification le : mardi 3 juillet 2018 - 11:37:04

Fichier

FGM-DAM-2016-04-15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bernard Fortz, Luis Gouveia, Martim Joyce-Moniz. Optimal design of switched Ethernet networks implementing the Multiple Spanning Tree Protocol. Discrete Applied Mathematics, Elsevier, 2018, 234, pp.114 - 130. 〈10.1016/j.dam.2016.07.015〉. 〈hal-01665614〉

Partager

Métriques

Consultations de la notice

124

Téléchargements de fichiers

46