TKK | Tietoverkkolaboratorio | Julkaisut

Vesa Timonen: Simulation Studies on Performance of Balanced Fairness

Abstract of Master's Thesis

Most traffic in current data networks is elastic, i.e. the rates of traffic flows adjusts to use all bandwidth available. Concurrent flows compete for the finite resources or capacity of a network and the rate allocated for flows has to be regulated by some control mechanism to avoid congestion and to reduce packet losses in the network.

One essential objective of the bandwidth sharing policies is to assure fairness of the realized rate allocation. Different fairness criteria favor or discriminate sources or traffic classes on different basis. As a mathematical notion fairness can be generalized to an optimization problem. These classical, utility-based fairness criteria are considered in a static network scenario. In a dynamic network scenario using the optimal bandwidth sharing policy adapted from a static scenario can lead to non-optimal results. Also analysis of flow-level characteristics becomes difficult excluding most simple network cases. Utility-based fairness criteria have been proven to be sensitive in the sense that the steady state distribution depends on detailed traffic characters.

Balanced fairness is a new allocation policy that can be considered as the most efficient insensitive allocation. When bandwidth allocation is based on balanced fairness, the distribution of the number of flows in progress and expected throughput depend only on the average traffic load of each flow class. In some cases the exact probability distribution of the number of concurrent flows of different flow classes can be calculated and performance metrics can be evaluated.

In this thesis the utility-based fairness criteria and their generalization to optimization problem is presented. Also the notion of balanced fairness and its main features are described. The effect of allocation policies on flow-level characters is studied via simulations under different network topologies. Three different allocation policies are used in simulations -- balanced, max-min and proportional fairness.

In all the cases examined the differences in throughputs provided by different fairness criteria were comparatively small. Generally max-min fairness provided better throughput on the long routes and penalized the shorter ones more than balanced fairness. It was verified that proportional fairness coincides with balanced fairness in homogenous hypercubes, and with max-min fairness in trees. The insensitivity of balanced fairness was verified via sensitivity simulations. Also the sensitivity of max-min fairness and proportional fairness seem to be quite weak. Results attained via simulations follow exactly the analytical results.

Vesa Timonen: Tasapainotetun reiluuden suorituskyvyn arviointi simuloimalla

Diplomityön tiivistelmä

Nykyisten tietoverkkojen liikenne on valtaosin ns. elastista liikennettä. Liikennelähteet säätävät lähetysnopeutensa siten, että kaikki käytössä oleva kapasiteetti tulee hyödynnettyä. Samanaikaiset vuot kilpailevat verkon rajallisista resursseista. Ruuhkautumisen ja pakettihäviöiden estämiseksi lähteiden nopeutta on kontrolloitava jollakin ruuhkanhallintamekanismilla.

Ruuhkanhallintamekanismien yksi keskeinen tarkoitus on taata toteutuvan kaistanjaon reiluus. Eri reiluuskriteerit suosivat tai syrjivät liikennelähteitä tai liikenneluokkia eri perustein. Reiluuden käsite voidaan yleistää optimointiongelmaksi, jossa pyrikimys on löytää kriteerikohtaisen kohdefunktion maksimoiva tai minimoiva kaistanjako. Nämä klassiset utiliteettipohjaiset reiluuskriteerit rakentuvat staattisen verkkomallin varaan. Dynaamisessa verkkoskenaariossa staattisessa mallissa optimaalinen kaistanjako saattaa kuitenkin johtaa epäedulliseen tulokseen. Myös vuotason tunnuslukujen tarkastelu on vaikeaa joitakin yksinkertaisimpia verkkotopologioita lukuunottamatta. Utiliteettipohjaisten reiluuskriteerien tapapainojakauma on riippuvainen liikenteen tunnusluvuista, mikä tekee vuotason tarkastelut vaikeaksi.

Tasapainotettu reiluus on uusi kaistanjakomenetelmä, jota voidaan pitää tehokkaimpana insensitiivinä kaistanjakona. Kaistanjaon noudattessa tasapainotettua reiluutta aktiivisten voiden lukumäärän jakauma sekä läpäisyn odotusarvo riippuvat vain jokaisen vuoluokan keskimääräisestä kuormasta. Joissakin tapauksissa nämä suureet voidaan laskea eksaktisti.

Tässä työssä esitellään keskeisimmät utiliteettipohjaiset reiluuskriteerit sekä niiden yleistys optimointiongelmaksi. Tasapainotetun reiluuden käsite sekä sen ominaisuuksia esitellään. Kaistanjakomenetelmien vaikutusta vuotason suureisiin tutkittiin simuloimalla eri verkkotopologiossa sekä pyrittiin verifioimaan kirjallisuudessa esitettyjä tuloksia. Käytettyjä menetelmiä olivat tasapainotettu, suhteellinen sekä max-min-reiluus. Kaikissa tarkastelluissa tapauksissa eri kriteerien tuottamat erot läpäisyssä olivat melko vähäiset. Yleisesti ottaen max-min-reiluus suosii pitkiä vuoluokkia tasapainotettua reiluutta enemmän. Simulaatiot tukivat lauseita, joiden mukaan suhteellinen reiluus yhtyy tasapainotettuun reiluuteen homogeenisissa hyperkuutioissa ja vastaavasti max-min-reiluuteen puutopologioissa. Simuloinnit vahvistavat tasapainotetun reiluuden insensitiivisyyden. Myös max-min-reiluuden sekä suhteellisen reiluuden sensitiivisyys oli vähäistä. Simuloidut tulokset vastasivat tarkasti analyyttisia.

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