IGP traffic engineering : a comparison of computational optimization algorithms

Wang, Hong Feng (2008-03)

Thesis (MSc)--Stellenbosch University, 2008.

Thesis

ENGLISH ABSTRACT: Traffic Engineering (TE) is intended to be used in next generation IP networks to optimize the usage of network resources by effecting QoS agreements between the traffic offered to the network and the available network resources. TE is currently performed by the IP community using three methods including (1) IGP TE using connectionless routing optimization (2) MPLS TE using connection-oriented routing optimization and (3) Hybrid TE combining IGP TE with MPLS TE. MPLS has won the battle of the core of the Internet and is making its way into metro, access and even some private networks. However, emerging provider practices are revealing the relevance of using IGP TE in hybrid TE models where IGP TE is combined with MPLS TE to optimize IP routing. This is done by either optimizing IGP routing while setting a few number of MPLS tunnels in the network or optimizing the management of MPLS tunnels to allow growth for the IGP traffic or optimizing both IGP and MPLS routing in a hybrid IGP+MPLS setting. The focus of this thesis is on IGP TE using heuristic algorithms borrowed from the computational intelligence research field. We present four classes of algorithms for Maximum Link Utilization (MLU) minimization. These include Genetic Algorithm (GA), Gene Expression Programming (GEP), Ant Colony Optimization (ACO), and Simulated Annealing (SA). We use these algorithms to compute a set of optimal link weights to achieve IGP TE in different settings where a set of test networks representing Europe, USA, Africa and China are used. Using NS simulation, we compare the performance of these algorithms on the test networks with various traffic profiles.

AFRIKAANSE OPSOMMING: Verkeersingenieurswese (VI) is aangedui vir gebruik in volgende generasie IP netwerke vir die gebruiksoptimering van netwerkbronne deur die daarstelling van kwaliteit van diens ooreenkomste tussen die verkeersaanbod vir die netwerk en die beskikbare netwerkbronne. VI word huidiglik algemeen bewerkstellig deur drie metodes, insluitend (1) IGP VI gebruikmakend van verbindingslose roete-optimering, (2) MPLS VI gebruikmakend van verbindingsvaste roete-optimering en (3) hibriede VI wat IGP VI en MPLS VI kombineer. MPLS is die mees algemene, en word ook aangewend in metro, toegang en selfs sommige privaatnetwerke. Nuwe verskaffer-praktyke toon egter die relevansie van die gebruik van IGP VI in hibriede VI modelle, waar IGP VI gekombineer word met MPLS VI om IP roetering te optimeer. Dit word gedoen deur `of optimering van IGP roetering terwyl ’n paar MPLS tonnels in die netwerk gestel word, `of optimering van die bestuur van MPLS tonnels om toe te laat vir groei in die IGP verkeer `of die optimering van beide IGP en MPLS roetering in ’n hibriede IGP en MPLS situasie. Die fokus van hierdie tesis is op IGP VI gebruikmakend van heuristieke algoritmes wat ontleen word vanuit die berekeningsintelligensie navorsingsveld. Ons beskou vier klasse van algoritmes vir Maksimum Verbindingsgebruik (MVG) minimering. Dit sluit in genetiese algoritmes, geen-uitdrukkingsprogrammering, mierkoloniemaksimering and gesimuleerde temperoptimering. Ons gebruik hierdie algoritmes om ’n versameling optimale verbindingsgewigte te bereken om IGP VI te bereik in verskillende situasies, waar ’n versameling toetsnetwerke gebruik is wat Europa, VSA, Afrika en China verteenwoordig. Gebruikmakende van NS simulasie, vergelyk ons die werkverrigting van hierdie algoritmes op die toetsnetwerke, met verskillende verkeersprofiele.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/20877
This item appears in the following collections: