TKK | Tietoverkkolaboratorio | Julkaisut

Riikka Susitaival: Load balancing by MPLS in differentiated services networks


Työ PDF-muodossa. The work in PDF format.
Date:September 4, 2002
Pages:68
Department:Department of Electrical and Communications Engineering
Professorship:S-38 Networking Technology
Supervisor: Professor Jorma Virtamo
Instructors: Ph.D. Pirkko Kuusela and Ph.D. Samuli Aalto

Abstract of the Master's Thesis

In IP routing, forwarding decisions are made independently in each router. Multi Protocol Label Switching (MPLS) as a new technique assigns a short label to each packet at the ingress node of MPLS network and packets are forwarded according to these labels. The most significant application of MPLS is the Traffic Engineering, which is used to optimize the performance of networks.

The capability of MPLS of explicit routing as well as of splitting of the traffic on several paths allows load balancing . The goal of this thesis is to study a flow allocation that minimizes the mean delay of the network. The thesis concentrates on the minimum-delay algorithm presented by Gallager and its two approximations. The first approximation defines the paths using the LP-optimization and after that allocates traffic using the NLP-optimization. The second approximation divides traffic into parts and routes them consecutively using Dijkstra's algorithm.

Using the load balancing algorithms as a starting point, the main goal of this thesis is to develop optimization algorithms that differentiate classes in terms of mean delay. In the thesis, the differentiation is achieved by the use of both routing and WFQ-scheduling. Both optimal and approximative algorithms are developed for the joint optimization of the WFQ-weights and routing.

The load balancing algorithms and the algorithms to differentiate classes are implemented and tested. As a result it is found that the use of the approximations simplifies the optimization problem but still provides results that are near to optimal. The algorithms that try to differentiate traffic classes by both routing and WFQ-scheduling provide the best performance.

Keywords: MPLS, load balancing routing, differentiated services, WFQ

Riikka Susitaival: Kuormantasaus MPLS:n avulla eriytetyn palvelun verkoissa

Diplomityön tiivistelmä

IP-verkossa reitityspäätökset tehdään itsenäisesti jokaisessa reitittimessä. Multi Protocol Label Switching (MPLS) on leimakytkentäprotokolla, joka liittää jokaiseen pakettiin leiman MPLS-verkon reunalla. Leiman avulla määritellään reititys MPLS-verkossa. MPLS:n merkittävin sovellus on Traffic Engineering, jota käytetään verkon suorituskyvyn optimointiin.

MPLS:n eksplisiittisellä reitityksellä sekä jakamalla liikennettä useille poluille voidaan tasata kuormaa. Työn tarkoituksena on tutkia liikenteenjakoa, joka minimoi verkon keskiviiveen. Työssä keskitytään Gallagerin esittämään, viiveen minimoivaan algoritmiin sekä kahteen sen approksimaatioon. Ensimmäinen approksimaatio määrittelee ensin polut lineaarisella optimoinnilla ja tämän jälkeen reitittää liikenteen epälineaarisella optimoinnilla. Toinen approksimaatio jakaa liikenteen osiin ja reitittää osat perätysten Dijkstran algoritmin avulla.

Työn tärkein päämäärä on kehittää optimointialgoritmeja, jotka eriyttävät luokkia viiveen mukaan. Kuormaa tasaavia algoritmeja käytetään lähtökohtana. Eriyttämistä saavutetaan sekä reitityksellä että WFQ-skeduloinnilla. Työssä kehitetään sekä optimaalisia että approksimoivia algoritmeja WFQ-painojen ja reitityksen yhtäaikaista optimointia varten.

Kuormaa tasaavat sekä palvelua eriyttävät algoritmit toteutetaan ja testataan. Havaitaan, että approksimaatiot pienentävät laskenta-aikaa merkittävästi kuitenkaan huonontamatta reitityksen suorituskykyä. Palvelua eriyttävistä algoritmeista parhaiten toimivat ne, jotka hyödyntävät sekä reititystä että WFQ-skedulointia.

Avainsanat: MPLS, kuormantasaus, palvelun eriyttäminen, WFQ

Tietoverkkolaboratorio on nyt osa Tietoliikenne- ja tietoverkkotekniikan laitosta. Tällä sivulla oleva tieto voi olla vanhentunutta.

Tämän sivun sisällöstä vastaavat ja Webmaster.
Sivua on viimeksi päivitetty 11.09.2002 15:11.
URI: http://www.netlab.tkk.fi/julkaisut/tyot/diplomityot/927/index.shtml
[ TKK > Sähkö- ja tietoliikennetekniikan osasto > Tietoverkkolaboratorio > Julkaisut ]