期刊
DISCRETE APPLIED MATHEMATICS
卷 234, 期 -, 页码 114-130出版社
ELSEVIER
DOI: 10.1016/j.dam.2016.07.015
关键词
Telecommunications; Traffic engineering; Multiple Spanning Tree Protocol; Network design; Mixed-integer programming
资金
- Interuniversity Attraction Poles Programme [P7/36 COMEX]
- Belgian Science Policy Office
- TCPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies
- FCT - Fundacao para a Ciencia e a Tecnologia [UID/MAT/04561/201]
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 providing a first comparison of different models that can be used in exact methods. (C) 2016 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据