Online traffic engineering for MPLS networks
Date
2004-4
Authors
Botha, Marlene
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: The Internet is fast evolving into a commercial platform that carries a mixture of narrow- and broadband applications
such as voice, video, and data. Users expect a certain level of guaranteed service from their service
providers and consequently the need exists for efficient Internet traffic engineering to enable better Quality of
Service (QoS) capabilities.
Multi-protocol Label Switching (MPLS) is a label switching protocol that has emerged as an enabling technology
to achieve efficient traffic engineering for QoS management in IP networks. The ability of the MPLS
protocol to create explicit virtual connections called Label Switched Paths (LSPs) to carry network traffic
significantly enhances the traffic engineering capabilities of communication networks. The MPLS protocol
supports two options for explicit LSP selection: offline LSP computation using an optimization method and
dynamic route selection where a single node makes use of current available network state information in order
to compute an explicit LSP online.
This thesis investigates various methods for the selection of explicit bandwidth guaranteed LSPs through
dynamic route selection. We address the problem of computing a sequence of optimal LSPs where each LSP
can carry a specific traffic demand and we assume that no prior information regarding the future traffic demands
are available and that the arrival sequence of LSP requests to the network is unknown. Furthermore,
we investigate the rerouting abilities of the online LSP selection methods to perform MPLS failure restoration
upon link failure.
We propose a new online routing framework known as Least Interference Optimization (LIO) that utilizes
the current bandwidth availability and traffic flow distribution to achieve efficient traffic engineering. We
present the Least Interference Optimization Algorithm (LIOA) that reduces the interference among competing
network flows by balancing the number and quantity of flows carried by a link for the setup of bandwidth
guaranteed LSPs in MPLS networks.
The LIOA routing strategy is evaluated and compared against well-known routing strategies such as the Minimum Hop Algorithm (MHA), Minimum Interference Routing Algorithm (MIRA), Open Shortest Path
First (OSPF) and Constraint Shortest Path First (CSPF) by means of simulation.
Simulation results revealed that, for the network topologies under consideration, the routing strategies that
employed dynamic network state information in their routing decisions (LIOA, CSPF and MIRA) generally
outperformed the routing strategies that only rely on static network information (OSPF and MHA). In most
simulation experiments the best performance was achieved by the LIOA routing strategy while the MHA performed
the worse. Furthermore we observed that the computational complexity of the MIRA routing strategy
does not translate into equivalent performance gains.
We employed the online routing strategies for MPLS failure recovery upon link failure. In particular we
investigated two aspects to determine the efficiency of the routing strategies for MPLS rerouting: the suitability
of the LSP configuration that results due to the establishment of LSPs prior to link failure and the
ability of the online routing strategy to reroute failed LSPs upon link failure. Simulation results revealed
similar rerouting performance for all online routing strategies under investigation, but a LSP configuration
most suitable for online rerouting was observed for the LIOA routing strategy.
AFRIKAANSE OPSOMMING:Die Internet is voordurend besig om te evoleer in 'n medium wat 'n wye reeks moderne kommunikasietegnologiee ondersteun, insluitende telefoon, video en data. Internet gebruikers verwag gewaarborgde diens van hul diensverskaffers en daar bestaan dus 'n vraag na doeltreffende televerkeerbeheer vir gewaarborgde Internet diensgehalte. Multiprotokol Etiketskakeling (MPLS) is 'n etiketskakeling protokol wat doeltreffende televerkeerbeheer en diensgehalte moontlik maak deur die eksplisiete seleksie van virtuele konneksies vir die transmissie van netwerkverkeer in Internetprotokol (IP) netwerke. Hierdie virtuele konneksies staan bekend as etiketgeskakelde paaie. Die MPLS protokol ondersteun tans twee moontlikhede vir eksplisiete seleksie van etiketgeskakelde paaie: aflyn padberekening met behulp van optimeringsmetodes en dinamiese aanlyn padseleksie waar 'n gekose node 'n eksplisiete pad bereken deur die huidige stand van die netwerk in ag te neem. In hierdie tesis word verskeie padseleksiemetodes vir die seleksie van eksplisiete bandwydte-gewaarborgde etiketgeskakelde paaie deur mid del van dinamiese padseleksie ondersoek. Die probleem om 'n reeks optimale etiketgeskakelde paaie te bereken wat elk 'n gespesifeerde verkeersaanvraag kan akkommodeer word aangespreek. Daar word aanvaar dat geen informasie in verband met die toekomstige verkeersaanvraag bekend is nie en dat die aankomsvolgorde van etiketgeskakelde pad verso eke onbekend is. Ons ondersoek verder die herroeteringsmoontlikhede van die aanlyn padseleksiemetodes vir MPLS foutrestorasie in die geval van skakelonderbreking. Vir hierdie doel word 'n nuwe aanlyn roeteringsraamwerk naamlik Laagste Inwerking Optimering (LIO) voorgestel. LIO benut die huidige beskikbare bandwydte en verkeersvloeidistribusie van die netwerk om doeltreffende televerkeerbeheer moontlik te maak. Ons beskryf 'n Laagste Inwerking Optimering Algoritme (LIOA) wat die inwerking tussen kompeterende verkeersvloei verminder deur 'n balans te handhaaf tussen die aantal en kwantiteit van die verkeersvloeistrome wat gedra word deur elke netwerkskakel. Die LIOA roeteringstrategie word geevalueer met behulp van simulasie en die resultate word vergelyk met ander bekende roeteringstrategiee insluitende die Minimum Node Algorithme (MHA), die Minimum Inwerking Algoritme (MIRA), die Wydste Kortste Pad Eerste Algoritme (OSPF) en die Beperkte Kortste Pad Eerste Algoritme (CSPF). Die resultate van die simulasie-eksperimente to on dat, vir die netwerk topologiee onder eksperimentasie, die roeteringstratgiee wat roeteringsbesluite op dinamiese netwerk informasie baseer (LIOA, MIRA, CSPF) oor die algemeen beter vaar as die wat slegs staatmaak op statiese netwerkinformasie (MHA, OSPF). In die meeste simulasie-eksperimente vaar die LIOA roeteringstrategie die beste en die MHA roeteringstrategie die slegste. Daar word verder waargeneem dat die komputasiekomplesiteit van die MIRA roeteringstrategie nie noodwendig weerspieel word in die sukses van roeteringsuitkoms nie. In die geval waar die aanlyn roeteringstrategiee aangewend word vir MPLS foutrestorasie, toon die resultate van simulasie-eksperimente dat al die roeteringstrategiee min of meer dieselfde uitkoms lewer ten opsigte van herroetering van onderbreekte verkeersvloei. Die konfigurasie van etiketgeskakelde paaie deur die LIOA roeteringstrategie voor skakelonderbreking is egter die geskikste vir televerkeer herroetering na skakelonderbreking
AFRIKAANSE OPSOMMING:Die Internet is voordurend besig om te evoleer in 'n medium wat 'n wye reeks moderne kommunikasietegnologiee ondersteun, insluitende telefoon, video en data. Internet gebruikers verwag gewaarborgde diens van hul diensverskaffers en daar bestaan dus 'n vraag na doeltreffende televerkeerbeheer vir gewaarborgde Internet diensgehalte. Multiprotokol Etiketskakeling (MPLS) is 'n etiketskakeling protokol wat doeltreffende televerkeerbeheer en diensgehalte moontlik maak deur die eksplisiete seleksie van virtuele konneksies vir die transmissie van netwerkverkeer in Internetprotokol (IP) netwerke. Hierdie virtuele konneksies staan bekend as etiketgeskakelde paaie. Die MPLS protokol ondersteun tans twee moontlikhede vir eksplisiete seleksie van etiketgeskakelde paaie: aflyn padberekening met behulp van optimeringsmetodes en dinamiese aanlyn padseleksie waar 'n gekose node 'n eksplisiete pad bereken deur die huidige stand van die netwerk in ag te neem. In hierdie tesis word verskeie padseleksiemetodes vir die seleksie van eksplisiete bandwydte-gewaarborgde etiketgeskakelde paaie deur mid del van dinamiese padseleksie ondersoek. Die probleem om 'n reeks optimale etiketgeskakelde paaie te bereken wat elk 'n gespesifeerde verkeersaanvraag kan akkommodeer word aangespreek. Daar word aanvaar dat geen informasie in verband met die toekomstige verkeersaanvraag bekend is nie en dat die aankomsvolgorde van etiketgeskakelde pad verso eke onbekend is. Ons ondersoek verder die herroeteringsmoontlikhede van die aanlyn padseleksiemetodes vir MPLS foutrestorasie in die geval van skakelonderbreking. Vir hierdie doel word 'n nuwe aanlyn roeteringsraamwerk naamlik Laagste Inwerking Optimering (LIO) voorgestel. LIO benut die huidige beskikbare bandwydte en verkeersvloeidistribusie van die netwerk om doeltreffende televerkeerbeheer moontlik te maak. Ons beskryf 'n Laagste Inwerking Optimering Algoritme (LIOA) wat die inwerking tussen kompeterende verkeersvloei verminder deur 'n balans te handhaaf tussen die aantal en kwantiteit van die verkeersvloeistrome wat gedra word deur elke netwerkskakel. Die LIOA roeteringstrategie word geevalueer met behulp van simulasie en die resultate word vergelyk met ander bekende roeteringstrategiee insluitende die Minimum Node Algorithme (MHA), die Minimum Inwerking Algoritme (MIRA), die Wydste Kortste Pad Eerste Algoritme (OSPF) en die Beperkte Kortste Pad Eerste Algoritme (CSPF). Die resultate van die simulasie-eksperimente to on dat, vir die netwerk topologiee onder eksperimentasie, die roeteringstratgiee wat roeteringsbesluite op dinamiese netwerk informasie baseer (LIOA, MIRA, CSPF) oor die algemeen beter vaar as die wat slegs staatmaak op statiese netwerkinformasie (MHA, OSPF). In die meeste simulasie-eksperimente vaar die LIOA roeteringstrategie die beste en die MHA roeteringstrategie die slegste. Daar word verder waargeneem dat die komputasiekomplesiteit van die MIRA roeteringstrategie nie noodwendig weerspieel word in die sukses van roeteringsuitkoms nie. In die geval waar die aanlyn roeteringstrategiee aangewend word vir MPLS foutrestorasie, toon die resultate van simulasie-eksperimente dat al die roeteringstrategiee min of meer dieselfde uitkoms lewer ten opsigte van herroetering van onderbreekte verkeersvloei. Die konfigurasie van etiketgeskakelde paaie deur die LIOA roeteringstrategie voor skakelonderbreking is egter die geskikste vir televerkeer herroetering na skakelonderbreking
Description
Thesis (MSc) -- Stellenbosch University, 2004.
Keywords
MPLS standard, Computer networks -- Standards, Telecommunication -- Traffic, Label switched paths (LSPs), Least interference optimization algorithm (LIOA), Dissertations -- Computer science, Theses -- Computer science, Dissertations -- Mathematical sciences, Theses -- Mathematical sciences