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

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-01, Vol.234, p.114-130
Main Authors: Fortz, Bernard, Gouveia, Luís, Joyce-Moniz, Martim
Format: Article
Language:English
Subjects:
Computer Science
Ethernet
Formulations
Integer programming
Local area networks
Mixed-integer programming
Multiple Spanning Tree Protocol
Network design
Operations Research
Studies
Switching theory
Telecommunications
Traffic engineering
Traffic models
Virtual local area networks
Virtual networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 NP-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 providing a first comparison of different models that can be used in exact methods.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2016.07.015