Rättvisemått

Rättvisa mått eller mått används i nätverksteknik för att avgöra om användare eller applikationer får en rättvis andel av systemresurserna. Det finns flera matematiska och konceptuella definitioner av rättvisa.

TCP rättvisa

Överbelastningskontrollmekanismer för nya nätverksöverföringsprotokoll eller peer-to-peer- applikationer måste interagera väl med TCP . TCP-rättvisa kräver att ett nytt protokoll inte får en större andel av nätverket än ett jämförbart TCP-flöde. Detta är viktigt eftersom TCP är det dominerande transportprotokollet på Internet, och om nya protokoll får orättvis kapacitet tenderar de att orsaka problem som att trafikstockningar kollapsar . Detta var fallet med de första versionerna av RealMedias strömningsprotokoll : det var baserat på UDP och blockerades i stor utsträckning vid organisatoriska brandväggar tills en TCP-baserad version utvecklades. Orättvisa TCP-genomströmning över WiFi är ett kritiskt problem och behöver ytterligare undersökningar.

Jains rättvisa index

Raj Jains ekvation,

${ \displaystyle {\mathcal {J}}(x_{1},x_{2},\dots ,x_{n})={\frac {(\sum _{i=1}^{n}x_{i} )^{2}}{n\cdot \sum _{i=1}^{n}{x_{i}}^{2}}}={\frac {{\overline {\mathbf {x} }} ^{2}}{\overline {\mathbf {x} ^{2}}}}={\frac {1}{1+{\widehat {c_{\rm {v}}}}^{2}} }}$

bedömer rättvisan för en uppsättning värden där det finns $n$ användare, $x_{i}$ är genomströmningen för den ${\displaystyle i}:$ e anslutningen och ${\widehat {c_{\rm {v}}}}$ är provvariationskoefficienten . Resultatet sträcker sig från ${\tfrac {1}{n}}$ (sämsta fallet) till 1 (bästa fallet), och det är maximalt när alla användare får samma tilldelning. Detta index är ${\tfrac {k}{n}}$ när $k$ -användare delar lika på resursen, och de andra $nk$ -användarna får noll tilldelning.

Detta mått identifierar underutnyttjade kanaler och är inte onödigt känsligt för atypiska nätverksflödesmönster.

För att uppnå en given rättvishetsnivå $F$ är en ungefärlig metod att låta ${\displaystyle x_{k}=A\cdot k^{\alpha }} ,$ där

$\alpha ={\frac {1-F+{\sqrt {1-F}}}{F}}$

och A är en godtycklig faktor, som vanligtvis används för normalisering. Detta ger en tilldelning med en rättvisa nära F , och tilldelningen kan sedan förfinas för att komma ännu närmare. Observera att detta också tillåter en prioritering av allokering, eftersom $​​{\displaystyle x_{k}}$ s kommer att sorteras.

En exakt metod är att låta ${\displaystyle x_{k}=A\cdot e^{2\alpha k}} ,$ där $\alpha$ löser

${\frac {\tanh(n\alpha )}{n\tanh(\alpha )}}=F$ .

Ett enkelt sätt att beräkna $\alpha$ är att använda Newtons metod på ${\displaystyle \ln \left({\frac {\tanh(n\alpha )-\tanh(\alpha )}{(nF-1)\cdot \tanh(\alpha )}}\right)=0} , som konvergerar$ konsekvent och ganska snabbt.

Båda dessa metoder ger icke-heltalsallokeringar, i allmänhet, och ibland krävs heltalsallokeringar. Detta kan göras genom att använda en av allokeringsmetoderna ovan, avrunda varje allokering nedåt till närmaste heltal ( $x_{k}'=\left\lfloor x_{k}\right\ rfloor$ ), och sedan iterativt allokera en enhet till en användare, med sannolikheten att användare k tar emot den är proportionell mot $x_{k}-\left\lfloor x_{k}\right \rgolv$ .

Max-min rättvisa

Huvudartikel: Max-min rättvisa

Max-min-rättvisa sägs uppnås genom en allokering om och endast om allokeringen är genomförbar och ett försök att öka allokeringen av något flöde med nödvändighet resulterar i minskningen av allokeringen av något annat flöde med en lika stor eller mindre allokering. En max-min rättvis allokering uppnås när bandbredden allokeras lika och i oändligt små steg till alla flöden tills ett är uppfyllt, sedan bland resten av flödena och så vidare tills alla flöden är uppfyllda eller bandbredden är slut.

Ganska delad spektrumeffektivitet

I trådlösa paketradionätverk kan den ganska delade spektrumeffektiviteten (FSSE) användas som ett kombinerat mått på rättvisa och systemspektrumeffektivitet . Systemets spektrala effektivitet är den sammanlagda genomströmningen i nätverket dividerat med den använda radiobandbredden i hertz. FSSE är den del av systemets spektrala effektivitet som delas lika mellan alla aktiva användare (med minst ett eftersatt datapaket i kö eller under överföring). Vid schemaläggning av svält skulle FSSE vara noll under vissa tidsintervall. I fallet med lika delade resurser skulle FSSE vara lika med systemets spektrumeffektivitet. För att uppnå max-min rättvisa bör FSSE maximeras.

FSSE är särskilt användbart när man analyserar avancerade radioresurshanteringsscheman (RRM), till exempel kanaladaptiv schemaläggning, för cellulära nätverk med bästa möjliga paketdatatjänst. I ett sådant system kan det vara frestande att optimera spektrumeffektiviteten (dvs genomströmningen). Det kan dock leda till att "dyra" användare schemalägger svält på långt avstånd från åtkomstpunkten, närhelst en annan aktiv användare är närmare samma eller en angränsande åtkomstpunkt. Därmed skulle användarna uppleva instabil service, vilket kanske skulle resultera i ett minskat antal nöjda kunder. Att optimera FSSE resulterar i en kompromiss mellan rättvisa (särskilt undvikande av schemaläggning av svält) och att uppnå hög spektral effektivitet.

Om kostnaden för varje användare är känd, i termer av förbrukade resurser per överförd informationsbit, kan FSSE-måttet omdefinieras för att återspegla proportionell rättvisa . I ett proportionellt rättvist system är denna "proportionellt rättvisa delade spektrumeffektivitet" (eller "rättvist delade radioresurskostnad") maximerad. Denna policy är mindre rättvis eftersom "dyra" användare ges lägre genomströmning än andra, men ändå undviks schemaläggning av svält.

QoE rättvisa

Idén med QoE fairness är att kvantifiera rättvisa bland användare genom att ta hänsyn till Quality of Experience (QoE) som uppfattas av slutanvändaren. Detta är särskilt viktigt i nätverkshantering där operatörer vill hålla sina användare tillräckligt nöjda (dvs hög QoE) på ett rättvist sätt, se QoE management . Flera tillvägagångssätt har föreslagits för att säkerställa rättvisa QoE över hela nätverket, särskilt för adaptiv videoströmning.

Till skillnad från nätverksrelaterade mätningar som genomströmning, mäts QoE vanligtvis inte på förhållandeskalor . Därför kan rättvisa mått som Jains rättvisa index inte användas, eftersom mätskalan kräver att vara en kvotskala med en tydligt definierad nollpunkt (se exempel på missbruk för variationskoefficienter). QoE kan mätas på intervallskalor . Ett typiskt exempel är en MOS-skala med 5 poäng , där 1 anger lägsta kvalitet och 5 anger högsta kvalitet. Även om variationskoefficienten är meningslös ger standardavvikelsen $\sigma$ ett mått på spridningen av QoE bland användare.

Hossfeld et al. har föreslagit ett QoE Fairness-index som tar hänsyn till den nedre gränsen $L$ och den högre gränsen $H$ på betygsskalan.

$F=1-{\frac {2\sigma }{HL}}$

QoE rättvisa index $F$ har några önskade egenskaper som skala och metriskt oberoende. Måttenheten spelar ingen roll. En linjär transformation av QoE-värdena ändrar inte värdet på rättviseindexet. Rättvisa index är avgränsat i intervallet $[0;1]$ med 1 som indikerar perfekt QoE-rättvisa – alla användare upplever samma kvalitet. 0 indikerar total orättvisa, t.ex. 50 % av användarna upplever högsta QoE $H$ och 50% upplever lägsta QoE $L$ .

Produktbaserade Fairness Index

Produktbaserade rättvisa index är baserade på den allmänna rättvisa formuleringen:

${\mathcal {A}}(\mathbf {x} )=\prod _{i=0}^{n}f\ vänster({\frac {x_{i}}{\max(\mathbf {x} )}}\right)$ ,

där $f$ är en godtycklig transformationsfunktion. För att $f$ ska vara en giltig transformationsfunktion: $f(x)\in [0,1]$ för $0\leq x \leq 1$ . Det resulterande indexet har alltså ett värde mellan 0 och 1. Eftersom Jains rättvisa index sägs vara överdrivet känsligt under atypiska förhållanden kan den produktbaserade rättvisan definieras godtyckligt för att få en önskad känslighet.

En tilldelning som har rättvisa F enligt formuleringen ovan kan ges av

$x_{j}=A\cdot f^{-1} \left(\exp \left(\ln(F)\cdot g(j)/\sum _{i=0}^{n}g(i)\right)\right)$ ,

där $g(x)$ är en icke-minskande funktion med $g(0)=0$ . det är ofta bekvämt att ta g för att vara något som $g(x)=x^{m}$ . Om vi ​​antar att f ökar och $f(0)=0$ och $f(1)=1$ ger detta ett minimum till maximum förhållande på ca.

$f^{-1}\left(\exp \left({\frac {m+1}{n}}\ln( F)\höger)\höger)$ .

Det linjära produktbaserade rättvisa indexet har $f(x)=x$ och ser ut som följer:

${\mathcal {L}}(\mathbf {x} )={\frac {\prod _{i=0}^{n} x_{i}}{\max(\mathbf {x} )^{n}}}$ .

Det har observerats att $}}(\mathbf {x} )}$$x_{i}/\max (\mathbf {x} )$ är mycket känslig för små värden på . Till exempel $\mathbf {h} =\{20,10,5,1\}$ ger ${\mathcal {L} }(\mathbf {h} )=0,00625$

G:s rättviseindex

G:s rättvisa index ${\mathcal {I}}$ används främst av telekomoperatörer i samband med bandbreddsallokering . G:s $k$ th-orders fairness index skalar bråkdelen av det produktbaserade fairness indexet med en driven sinustransformation $f(x)= \sin(x\pi /2)^{\frac {1}{k}}$ :

${\mathcal {G}}_{k}(\mathbf {x} )=\prod _ {i=1}^{n}\sin \left({\frac {\pi x_{i}}{2\max(\mathbf {x} )}}\right)^{\frac {1}{k }}$ ,

där $k\in \mathbb {R} ^{+}$ . Den första kvadranten av sinusvågen används som en mappningsfunktion för att blåsa upp bråk. Som sådan minskar känsligheten för den produktbaserade rättvisan för värden nära ${\displaystyle \max(\mathbf {x} )} ,$ medan indexet fortfarande matar ut ett värde mellan 0 och 1.

Jämfört med Jains rättvisa index ger G:s rättvisa index mindre värden, det är mer känsligt för potentiell orättvis bandbreddsfördelning och kan gå till noll. I nätverkssammanhang är det sistnämnda en fördel gentemot Jains rättvisa index när några värden i ett set faller till låga nivåer. Dessutom anses Jains rättviseindex som en genomsnittlig användaruppfattning om rättvisa medan G:s rättviseindex fokuserar mer på jämlikhet inom en grupp. Till exempel, för $\mathbf {m} =\{20,20,20,0\}$ får vi $\ mathrm {Jain} (\mathbf {m} )=0,75$ och ${\mathcal {G_{1}}}(\mathbf {m} )=0$ .

Bossaers rättviseindex

Medan G:s rättvisa index blåser upp bråken närmare $\max(\mathbf {x} )$ , blåser Bossaers rättvisa index upp bråken närmare 0. Bossaers $k$ transformationsfunktion i e-ordningen $f(x)=x^{\frac {1}{k}}$ ger rättvisa index:

${\mathcal {B}}_{k}(\mathbf {x} )=\prod _{i=1 }^{n}\left({\frac {x_{i}}{\max(\mathbf {x} )}}\right)^{\frac {1}{k}}$ .

De linjära produktbaserade rättvisa indexen är ett specialfall av Bossaers där $k=1$ .

Kausal rättvisa

Causal fairness mäter den frekvens med vilken två nästan identiska användare eller applikationer som skiljer sig åt endast i en uppsättning egenskaper med avseende på vilka resursallokeringen måste vara rättvis, får identisk behandling.

Andra mätvärden

Flera andra mätvärden har definierats, till exempel Worst Case Fairness.

Vidare läsning

• Almeida, A.; Casetti, C.; Oueslati, S.; Avratchenkov, K. & Johansson, M. A Taxonomy of Congestion Control (i leverans nr: D.WP.JR.2.1.1) EuroNGI, 2004
• Mo, J.; Walrand, J. (2000). "Rättvis end-to-end fönsterbaserad överbelastningskontroll" (PDF) . IEEE/ACM-transaktioner på nätverk . 8 (5): 556–567. doi : 10.1109/90.879343 . Arkiverad från originalet (PDF) 2012-11-19.