TKK | Tietoverkkolaboratorio | Julkaisut

Ilmari Juva: Analysis of Quality of Service Routing Approaches and Algorithms

Abstract of the Master's Thesis

So far the Internet has offered only best effort service. All traffic is processed as quickly as possible and no preferences are given to any type of traffic. Today there are more and more applications that need service guarantees in order to function properly. These kinds of applications include for instance IP telephony, video-conference applications or video on-demand services.

One important part of the QoS framework is the ability to find the paths that have sufficient resources to support the QoS requirements of a traffic flow. Current Internet routing protocols always forward packets to the shortest path based on hop count. This can cause problems for flows with a need for performance requirements, if the shortest path does not have the resources needed to meet these requirements. Quality of Service routing is a routing scheme that considers the quality of service requirements of a flow when making routing decisions. As opposed to traditional shortest path routing, which only considers the hop count, QoS routing is designed to find feasible paths that satisfy multiple constraints.

This thesis is a survey on QoS routing. It presents the most important problems in QoS routing concerning path selection algorithms, cost of QoS routing, and different approaches. Routing problems for cases with one or two metric are formalized as optimization problems, and solutions algorithms are presented. For the most complex problems heuristic approximation algorithms and their evaluations found in literature are discussed. Algorithms for the important special case where available bandwidth and hop count are used as metrics are considered in detail. The cost of QoS routing, and the factors contributing to the cost, are evaluated based on simulation and implementation study results found in literature. Different approaches concerning algorithm classes, link state information and timing of path computation are discussed.

While providing paths that satisfy the QoS guarantees of traffic flows, QoS routing can cause inter-class effects that may lead to congestion or even starvation of low priority traffic. The authors own contribution consists of a simple Markov-model to study the effects of a bandwidth reservation scheme that sets aside some portion of a link’s bandwidth for low priority traffic only, in order to prevent the starvation.

Ilmari Juva: Palvelunlaatureitityksen eri lähestymistavat ja algoritmit

Diplomityön tiivistelmä

Sellaisten polkujen löytäminen, jotka pystyvät täyttämään vaaditut palvelunlaatu-ehdot liikennevoille, on tärkeä osa palvenlaatua. Nykyisessä Internetissä reititysprotokollat reitittävät liikenteen aina lyhimmälle polulle. Tämä saattaa aiheuttaa ongelmia voille, joilla on palvelunlaatuvaatimuksia, joita lyhin polku ei pysty tukemaan. Palvelunlaatureititys sen sijaan ottaa huomioon palvelunlaatuvaatimukset reitityspäätöksissään. Se pystyy myös löytämään useamman ehdon täyttäviä polkuja, toisin kuin perinteinen lyhimmän polun reititys.

Tämä diplomityö on kirjallisuuskatsaus palvelunlaatureityksestä. Se esittelee alueen tärkeimmät ongelmat polun valintaan, kustannuksiin ja eri lähestymistapoihin liittyen. Yhden ja kahden metriikan reititysongelmat ja niiden ratkaisualgoritmit esitellään. Kompleksisimmille ongelmille käydään läpi kirjallisuudessa esitettyjä heuristisia algoritmeja sekä niiden arviointeja. Tarkemmin keskitytään tärkeään erikoistapaukseen, jossa metriikkana käytetään polun pituutta ja vapaata kaistanleveyttä. Palvelunlaatureitityksen kustannuksia, ja niihin vaikuttavia tekijöitä, arvioivia simulointi- ja implementaatiotutkimuksia tarkastellaan, kuten myös eri algortimiluokkia, linkkitila informaatiota ja polun laskennan ajoitusta.

Palvelunlaatuvaatimukset täyttävän polkujen valitseminen saattaa aiheuttaa liikenneluokkien välisiä vaikutuksia. Tällaiset inter-class effect -nimellä kutsutut vaikutukset saattavat johtaa alemman prioriteetin liikenteen ruuhkautumiseen tai täydelliseen estymiseen. Tekijän oma osuus käsittelee yksinkertaista Markov-mallia, jolla tutkitaan sellaisen kaistanvarausmallin vaikutusta, joka varaa tietyn osan kaistanleveydestä yksinomaan alemman luokan liikenteen käyttöön.

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