Change search
ReferencesLink to record
Permanent link

Direct link
Robust load balancing under traffic uncertainty-tractable models and efficient algorithms
Swedish Institute of Computer Science.
KTH, School of Electrical Engineering (EES), Automatic Control.
2011 (English)In: Telecommunications Systems, ISSN 1018-4864, E-ISSN 1572-9451, Vol. 48, no 1-2, 93-107 p.Article in journal (Refereed) Published
Abstract [en]

Routing configurations that have been optimized for a nominal traffic scenario often display significant performance degradation when they are subjected to real network traffic. These degradations are due to the inherent sensitivity of classical optimization techniques to changes in model parameters combined with the significant traffic variations caused by demand fluctuations, component failures and network reconfigurations. In this paper, we review important sources for traffic variations in data networks and describe tractable models for capturing the associated traffic uncertainty. We demonstrate how robust routing settings with guaranteed performance for all foreseen traffic variations can be effectively computed via memory efficient iterative techniques and polynomial-time algorithms. The techniques are illustrated on real data from operational IP networks.

Place, publisher, year, edition, pages
2011. Vol. 48, no 1-2, 93-107 p.
Keyword [en]
Robust routing, Optimization, Traffic engineering, Traffic uncertainty
National Category
Computer Science
URN: urn:nbn:se:kth:diva-29556DOI: 10.1007/s11235-010-9336-9ISI: 000294346100008ScopusID: 2-s2.0-80054934661OAI: diva2:395649
Swedish Research CouncilEU, European Research Council

QC 20110211

Available from: 2011-02-07 Created: 2011-02-07 Last updated: 2012-08-23Bibliographically approved
In thesis
1. Aspects of proactive traffic engineering in IP networks
Open this publication in new window or tab >>Aspects of proactive traffic engineering in IP networks
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

To deliver a reliable communication service over the Internet it is essential for the network operator to manage the traffic situation in the network. The traffic situation is controlled by the routing function which determines what path traffic follows from source to destination.  Current practices for setting routing parameters in IP networks are designed to be simple to manage. This can lead to congestion in parts of the network while other parts of the network are far from fully utilized. In this thesis we explore issues related to optimization of the routing function to balance load in the network and efficiently deliver a reliable communication service to the users. The optimization takes into account not only the traffic situation under normal operational conditions, but also traffic situations that appear under a wide variety of circumstances deviating from the nominal case. In order to balance load in the network knowledge of the traffic situations is needed. Consequently, in this thesis we investigate methods for efficient derivation of the traffic situation. The derivation is based on estimation of traffic demands from link load measurements. The advantage of using link load measurements is that they are easily obtained and consist  of a limited amount of data that need to be processed. We evaluate and demonstrate how estimation based on link counts gives the operator a fast and accurate description of the traffic demands. For the evaluation we have access to a unique data set of complete traffic demands from an operational IP backbone.  However, to honor service level agreements at all times the variability of the traffic needs to be accounted for in the load balancing. In addition, optimization techniques are often sensitive to errors and variations in input data. Hence, when an optimized routing setting is subjected to real traffic demands in the network, performance often deviate from what can be anticipated from the optimization. Thus, we identify and model different traffic uncertainties and describe how the routing setting can be optimized, not only for a nominal case, but for a wide range of different traffic situations that might appear in the network.  Our results can be applied in MPLS enabled networks as well as in networks using link state routing protocols such as the widely used OSPF and IS-IS protocols. Only minor changes may be needed in current networks to implement our algorithms. The contributions of this thesis is that we: demonstrate that it is possible to estimate the traffic matrix with acceptable precision, and we develop methods and models for common traffic uncertainties to account for these uncertainties in the optimization of the routing configuration. In addition, we identify important properties in the structure of the traffic to successfully balance uncertain and varying traffic demands.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2011. xi, 63 p.
Trita-EE, ISSN 1653-5146
National Category
Control Engineering
urn:nbn:se:kth:diva-29558 (URN)978-91-7415-870-0 (ISBN)
Public defence
2011-03-01, F3, Lindstedtsvägen 26, KTH, Stockholm, 13:00 (English)
QC 20110211Available from: 2011-02-11 Created: 2011-02-07 Last updated: 2011-02-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Gunnar, AndersJohansson, Mikael
By organisation
Automatic Control
In the same journal
Telecommunications Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 39 hits
ReferencesLink to record
Permanent link

Direct link