Advanced

Optimization of link load balancing in multiple spanning tree routing networks

Santos, Dorabella; de Sousa, Amaro; Alvelos, Filipe; Dzida, Mateusz and Pioro, Michal LU (2011) In Telecommunications Systems 48(1-2). p.109-124
Abstract
In telecommunication networks based on the current Ethernet technology, routing of traffic demands is based on multiple spanning trees: the network operator configures different routing spanning trees and assigns each demand to be routed in one of the selected spanning trees. A major optimization issue in this solution is the combined determination of (i) a set of appropriate spanning trees, and (ii) assignment of demands to the trees, in order to achieve an optimal load balancing on the links of the network. In this paper we consider models and solving techniques for lexicographical optimization of two load balancing objective functions. The first objective is the min-max optimization of the n worst link loads (with n up to the total... (More)
In telecommunication networks based on the current Ethernet technology, routing of traffic demands is based on multiple spanning trees: the network operator configures different routing spanning trees and assigns each demand to be routed in one of the selected spanning trees. A major optimization issue in this solution is the combined determination of (i) a set of appropriate spanning trees, and (ii) assignment of demands to the trees, in order to achieve an optimal load balancing on the links of the network. In this paper we consider models and solving techniques for lexicographical optimization of two load balancing objective functions. The first objective is the min-max optimization of the n worst link loads (with n up to the total number of network links), and the second objective is the minimization of the average link load (when n is smaller than the total number of network links). Besides exact methods, a heuristic technique that can compute both feasible solutions and lower bounds for the addressed optimization problem is proposed. Finally, we discuss effectiveness of different solution using results of a numerical study of realistic case studies. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Ethernet networks, Load balancing, Multiple spanning tree routing, Traffic engineering, Integer programming
in
Telecommunications Systems
volume
48
issue
1-2
pages
109 - 124
publisher
Springer
external identifiers
  • wos:000294346100009
  • scopus:80054944612
ISSN
1018-4864
DOI
10.1007/s11235-010-9337-8
language
English
LU publication?
yes
id
6682ed60-eec2-4a36-a14e-78e3e52fe5d6 (old id 2159021)
date added to LUP
2011-09-26 08:20:29
date last changed
2017-08-20 03:18:27
@article{6682ed60-eec2-4a36-a14e-78e3e52fe5d6,
  abstract     = {In telecommunication networks based on the current Ethernet technology, routing of traffic demands is based on multiple spanning trees: the network operator configures different routing spanning trees and assigns each demand to be routed in one of the selected spanning trees. A major optimization issue in this solution is the combined determination of (i) a set of appropriate spanning trees, and (ii) assignment of demands to the trees, in order to achieve an optimal load balancing on the links of the network. In this paper we consider models and solving techniques for lexicographical optimization of two load balancing objective functions. The first objective is the min-max optimization of the n worst link loads (with n up to the total number of network links), and the second objective is the minimization of the average link load (when n is smaller than the total number of network links). Besides exact methods, a heuristic technique that can compute both feasible solutions and lower bounds for the addressed optimization problem is proposed. Finally, we discuss effectiveness of different solution using results of a numerical study of realistic case studies.},
  author       = {Santos, Dorabella and de Sousa, Amaro and Alvelos, Filipe and Dzida, Mateusz and Pioro, Michal},
  issn         = {1018-4864},
  keyword      = {Ethernet networks,Load balancing,Multiple spanning tree routing,Traffic engineering,Integer programming},
  language     = {eng},
  number       = {1-2},
  pages        = {109--124},
  publisher    = {Springer},
  series       = {Telecommunications Systems},
  title        = {Optimization of link load balancing in multiple spanning tree routing networks},
  url          = {http://dx.doi.org/10.1007/s11235-010-9337-8},
  volume       = {48},
  year         = {2011},
}