Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Aspects of proactive traffic engineering in IP networks
KTH, School of Electrical Engineering (EES), Automatic Control.
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.
Series
Trita-EE, ISSN 1653-5146
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:kth:diva-29558ISBN: 978-91-7415-870-0 (print)OAI: oai:DiVA.org:kth-29558DiVA: diva2:395667
Public defence
2011-03-01, F3, Lindstedtsvägen 26, KTH, Stockholm, 13:00 (English)
Supervisors
Note
QC 20110211Available from: 2011-02-11 Created: 2011-02-07 Last updated: 2011-02-11Bibliographically approved
List of papers
1. Traffic matrix estimation on a large IP backbone: a comparison on real data
Open this publication in new window or tab >>Traffic matrix estimation on a large IP backbone: a comparison on real data
2004 (English)In: IMC '04 Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, 2004, 149-160 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper considers the problem of estimating the point-to-point traffic matrix in an operational IP backbone. Contrary to previous studies, that have used a partial traffic matrix or demands estimated from aggregated Netflow traces, we use a unique data set of complete traffic matrices from a global IP network measured over five-minute intervals. This allows us to do an accurate data analysis on the time-scale of typical link-load measurements and enables us to make a balanced evaluation of different traffic matrix estimation techniques. We describe the data collection infrastructure, present spatial and temporal demand distributions, investigate the stability of fan-out factors, and analyze the mean-variance relationships between demands. We perform a critical evaluation of existing and novel methods for traffic matrix estimation, including recursive fanout estimation, worst-case bounds, regularized estimation techniques, and methods that rely on mean variance relationships. We discuss the weaknesses and strengths of the various methods, and highlight differences in the results for the European and American subnetworks.

Keyword
Traffic matrix estimation, Optimization, SNMP, MPLS
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-7729 (URN)10.1145/1028788.1028807 (DOI)2-s2.0-14944378851 (Scopus ID)
Conference
IMC’04 October 25–27, 2004, Taormina, Sicily, Italy
Note
QC 20101105Available from: 2007-11-25 Created: 2007-11-25 Last updated: 2012-03-02Bibliographically approved
2. Performance of traffic engineering in operational IP-networks: an experimental study
Open this publication in new window or tab >>Performance of traffic engineering in operational IP-networks: an experimental study
2005 (English)In: 5th IEEE International Workshop on IP Operations and Management, 2005, 202-211 p.Conference paper, Published paper (Refereed)
Abstract [en]

Today, the main alternative for intra-domain traffic engineering in IP networks is to use different methods for setting the weights (and so decide upon the shortest-paths) in the routing protocols OSPF and IS-IS. In this paper we study how traffic engineering perform in real networks. We analyse different weight-setting methods and compare performance with the optimal solution given by a multi-commodity flow optimization problem. Further, we investigate their robustness in terms of how well they manage to cope with estimated traffic matrix data. For the evaluation we have access to net-work topology and traffic data from an operational IP network.

Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, ISSN 0302-9743
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-7730 (URN)10.1007/11567486_21 (DOI)978-354029356-9 (ISBN)
Conference
5th IEEE International Workshop on IP Operations and Management, IPOM 2005; Barcelona; 26 October 2005 through 28 October 2005
Note
QC 20101105Available from: 2007-11-25 Created: 2007-11-25 Last updated: 2011-02-11Bibliographically approved
3. Data-driven traffic engineering: techniques, experiences and challenges
Open this publication in new window or tab >>Data-driven traffic engineering: techniques, experiences and challenges
2006 (English)In: 2006 3RD INTERNATIONAL CONFERENCE ON BROADBAND COMMUNICATIONS, NETWORKS AND SYSTEMS, VOLS 1-3, NEW YORK: IEEE , 2006, 211-220 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents a global view of measurement-driven traffic engineering, explores the interplay between traffic matrix estimation and routing optimization and demonstrates how demand uncertainties can be accounted for in the optimization step to guarantee a robust and reliable result. Based on a unique data set of complete measured traffic matrices, we quantify the demand uncertainties in an operational IP network and demonstrate how a number of robust optimization schemes allow to find fixed WLS configurations that are close to the Performance limits given by time-varying routing under full demand knowledge. We present a novel scheme for computing a sparse MPLS mesh to complement a baseline routing, and explore how the performance depends on the size of the partial mesh. Corresponding methods for robust OSPF optimization are discussed and a number of challenges are detailed.

Place, publisher, year, edition, pages
NEW YORK: IEEE, 2006
National Category
Information Science
Identifiers
urn:nbn:se:kth:diva-26555 (URN)10.1109/BROADNETS.2006.4374362 (DOI)000250867800023 ()2-s2.0-51749111438 (Scopus ID)
Conference
3rd International Conference on Broadband Communications Networks and Systems San Jose, CA, OCT 01-05, 2006
Note
QC 20110111Available from: 2011-01-11 Created: 2010-11-25 Last updated: 2011-10-06Bibliographically approved
4. Robust load balancing under traffic uncertainty-tractable models and efficient algorithms
Open this publication in new window or tab >>Robust load balancing under traffic uncertainty-tractable models and efficient algorithms
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.

Keyword
Robust routing, Optimization, Traffic engineering, Traffic uncertainty
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-29556 (URN)10.1007/s11235-010-9336-9 (DOI)000294346100008 ()2-s2.0-80054934661 (Scopus ID)
Funder
Swedish Research CouncilEU, European Research Council
Note

QC 20110211

Available from: 2011-02-07 Created: 2011-02-07 Last updated: 2017-12-11Bibliographically approved
5. Cautious Weight Tuning for Link State Routing Protocols
Open this publication in new window or tab >>Cautious Weight Tuning for Link State Routing Protocols
2011 (English)Report (Other academic)
Abstract [en]

Link state routing protocols are widely used for intradomain routing in the Internet. These protocols are simple to administer and automatically update paths between sources and destinations when the topology changes. However, finding link weights that optimize network performance for a given traffic scenario is computationally hard. The situation is even more complex when the traffic is uncertain or time-varying.  We present an efficient heuristic for finding link settings that give uniformly good performance also under large changes in the traffic. The heuristic combines efficient search techniques with a novel objective function. The objective function combines network performance with a cost of deviating from desirable features of robust link weight settings. Furthermore, we discuss why link weight optimization is insensitive to errors in estimated traffic data from link load measurements. We assess performance of our method using traffic data from an operational IP backbone.

Publisher
16 p.
Series
SICS Technocal Report, ISSN 1100-3154 ; 2011:01
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-29557 (URN)
Funder
ICT - The Next Generation
Note
QC 20110211Available from: 2011-02-07 Created: 2011-02-07 Last updated: 2011-10-30Bibliographically approved

Open Access in DiVA

fulltext(2545 kB)1161 downloads
File information
File name FULLTEXT01.pdfFile size 2545 kBChecksum SHA-512
703dbd9c6880979ce4b0d63ab3510898bd13a6484b812ed1f4899f23110aa4cc72e5c15eeebc8b4d745465f297bc9a63165535a5faee9839621a9e43f768d871
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Gunnar, Anders
By organisation
Automatic Control
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 1161 downloads
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 503 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf