Fairness-Maßnahme – Wikipedia

Posted on January 11, 2021 by lordneo

before-content-x4

Fairness-Maßnahmen oder Metriken werden in der Netzwerktechnik verwendet, um zu bestimmen, ob Benutzer oder Anwendungen einen angemessenen Anteil an Systemressourcen erhalten. Es gibt verschiedene mathematische und konzeptionelle Definitionen von Fairness.

Table of Contents

TCP-Fairness[edit]

Überlastungskontrollmechanismen für neue Netzwerkübertragungsprotokolle oder Peer-to-Peer-Anwendungen müssen gut mit TCP interagieren. TCP-Fairness erfordert, dass ein neues Protokoll keinen größeren Anteil des Netzwerks erhält als ein vergleichbarer TCP-Fluss. Dies ist wichtig, da TCP das dominierende Transportprotokoll im Internet ist. Wenn neue Protokolle unfaire Kapazitäten erwerben, können sie Probleme wie den Zusammenbruch von Überlastungen verursachen. Dies war bei den ersten Versionen des Streaming-Protokolls von RealMedia der Fall: Es basierte auf UDP und wurde an organisatorischen Firewalls weitgehend blockiert, bis eine TCP-basierte Version entwickelt wurde. Die Ungerechtigkeit des TCP-Durchsatzes über WLAN ist ein kritisches Problem und erfordert weitere Untersuchungen.^[1]

Jains Fairness-Index[edit]

Raj Jains Gleichung,

{ 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} }}}

bewertet die Fairness einer Reihe von Werten, sofern vorhanden

{ displaystyle n}

$n$ Benutzer,

{ displaystyle x_ {i}}

$x_ {i}$ ist der Durchsatz für die

{ displaystyle i}

$ich$ th Verbindung und

{ displaystyle { widehat {c _ { rm {v}}}}

${ displaystyle { widehat {c _ { rm {v}}}}$ ist der Stichprobenvariationskoeffizient. Das Ergebnis reicht von

{ displaystyle { tfrac {1} {n}}}

${ tfrac {1} {n}}$ (Worst Case) bis 1 (Best Case), und es ist maximal, wenn alle Benutzer die gleiche Zuordnung erhalten. Dieser Index ist

{ displaystyle { tfrac {k} {n}}}

${ tfrac {k} {n}}$ wann

{ displaystyle k}

$k$ Benutzer teilen die Ressource gleichermaßen und die andere

{ displaystyle nk}

$nk$ Benutzer erhalten keine Zuordnung.

Diese Metrik identifiziert nicht ausgelastete Kanäle und reagiert nicht übermäßig empfindlich auf atypische Netzwerkflussmuster.^[2]

Um ein bestimmtes Fairness-Level zu erreichen

{ displaystyle F}

$F.$ Eine ungefähre Methode ist zu lassen

{ displaystyle x_ {k} = A cdot k ^ { alpha}}

${ displaystyle x_ {k} = A cdot k ^ { alpha}}$ , wo

{ displaystyle alpha = { frac {1-F + { sqrt {1-F}}} {F}}}

und EIN ist ein beliebiger Faktor, der typischerweise zur Normalisierung verwendet wird. Dies ergibt eine Allokation mit einer Fairness nahe F.und die Zuordnung kann dann verfeinert werden, um noch näher zu kommen. Beachten Sie, dass dies auch eine Priorisierung der Zuordnung ermöglicht, wie z

{ displaystyle x_ {k}}

$x_ {k}$ s wird sortiert.

Eine genaue Methode ist zu lassen

{ displaystyle x_ {k} = A cdot e ^ {2 alpha k}}

${ displaystyle x_ {k} = A cdot e ^ {2 alpha k}}$ , wo

{ displaystyle alpha}

$Alpha$ löst

{ displaystyle { frac { tanh (n alpha)} {n tanh ( alpha)}} = F}

Eine einfache Methode zur Berechnung

{ displaystyle alpha}

$Alpha$ ist die Newtonsche Methode anzuwenden

{ displaystyle ln left ({ frac { tanh (n alpha) – tanh ( alpha)} {(nF-1) cdot tanh ( alpha)}} right) = 0}

${ displaystyle ln left ({ frac { tanh (n alpha) - tanh ( alpha)} {(nF-1) cdot tanh ( alpha)}} right) = 0}$ , die konsequent und ziemlich schnell konvergiert.

Beide Methoden ergeben im Allgemeinen nicht ganzzahlige Zuweisungen, und manchmal sind ganzzahlige Zuweisungen erforderlich. Dies kann mithilfe einer der oben genannten Zuweisungsmethoden erfolgen, wobei jede Zuordnung auf die nächste Ganzzahl abgerundet wird (

{ displaystyle x_ {k} ‘= left lfloor x_ {k} right rfloor}

${ displaystyle x_ {k} '= left lfloor x_ {k} right rfloor}$ ) und dann iteratives Zuweisen einer Einheit zu einem Benutzer, wobei die Wahrscheinlichkeit, dass Benutzer k sie empfängt, proportional zu ist

{ displaystyle x_ {k} – left lfloor x_ {k} right rfloor}

${ displaystyle x_ {k} - left lfloor x_ {k} right rfloor}$ .

Max-Min-Fairness[edit]

Max-Min-Fairness soll durch eine Allokation nur dann erreicht werden, wenn die Allokation machbar ist und ein Versuch, die Allokation eines Flusses zu erhöhen, notwendigerweise zu einer Verringerung der Allokation eines anderen Flusses mit einer gleichen oder kleineren Allokation führt. Eine faire Max-Min-Zuweisung wird erreicht, wenn die Bandbreite allen Flüssen gleichmäßig und in infinitesimalen Schritten zugewiesen wird, bis einer erfüllt ist, dann unter den verbleibenden Flüssen usw., bis alle Flüsse erfüllt sind oder die Bandbreite erschöpft ist.

Ziemlich gemeinsame Spektrumseffizienz[edit]

In drahtlosen Paketfunknetzen, Die ziemlich geteilte Spektrumseffizienz (FSSE) kann als kombiniertes Maß für Fairness und Effizienz des Systemspektrums verwendet werden. Die spektrale Systemeffizienz ist der Gesamtdurchsatz im Netzwerk geteilt durch die genutzte Funkbandbreite in Hertz. Die FSSE ist der Teil der spektralen Systemeffizienz, der von allen aktiven Benutzern zu gleichen Teilen geteilt wird (mit mindestens einem zurückgebliebenen Datenpaket in der Warteschlange oder während der Übertragung). Im Falle eines geplanten Hungers wäre die FSSE in bestimmten Zeitintervallen Null. Bei gleich gemeinsam genutzten Ressourcen entspricht die FSSE der Effizienz des Systemspektrums. Um eine Max-Min-Fairness zu erreichen, sollte die FSSE maximiert werden.

FSSE ist insbesondere bei der Analyse von RRM-Schemata (Advanced Radio Resource Management), z. B. Channel Adaptive Scheduling, für Mobilfunknetze mit Best-Effort-Paketdatendienst nützlich. In einem solchen System kann es verlockend sein, die Spektrumseffizienz (dh den Durchsatz) zu optimieren. Dies kann jedoch dazu führen, dass “teure” Benutzer in großer Entfernung vom Zugangspunkt verhungern, wenn sich ein anderer aktiver Benutzer näher am selben oder einem benachbarten Zugangspunkt befindet. Auf diese Weise würden die Benutzer einen instabilen Service erleben, was möglicherweise zu einer verringerten Anzahl zufriedener Kunden führen würde. Die Optimierung des FSSE führt zu einem Kompromiss zwischen Fairness (insbesondere Vermeidung von Terminmangel) und dem Erreichen einer hohen spektralen Effizienz.

Wenn die Kosten jedes Benutzers in Bezug auf verbrauchte Ressourcen pro übertragenem Informationsbit bekannt sind, kann die FSSE-Kennzahl neu definiert werden, um die proportionale Fairness widerzuspiegeln. In einem proportionalen fairen System wird diese “proportional faire Effizienz des gemeinsamen Spektrums” (oder “fair geteilte Kosten für Funkressourcen”) maximiert. Diese Richtlinie ist weniger fair, da “teure” Benutzer einen geringeren Durchsatz als andere erhalten, die Planung von Hunger jedoch vermieden wird.

QoE-Fairness[edit]

Die Idee der QoE-Fairness besteht darin, die Fairness unter den Benutzern zu quantifizieren, indem die vom Endbenutzer wahrgenommene Quality of Experience (QoE) berücksichtigt wird. Dies ist besonders wichtig beim Netzwerkmanagement, bei dem die Betreiber ihre Benutzer auf faire Weise ausreichend zufrieden stellen möchten (dh eine hohe QoE), siehe QoE-Management. Es wurden verschiedene Ansätze vorgeschlagen, um die netzwerkweite QoE-Fairness sicherzustellen, insbesondere für adaptives Video-Streaming.^[3]^[4]

Im Gegensatz zu netzwerkbezogenen Maßnahmen wie dem Durchsatz wird die QoE normalerweise nicht auf Verhältnisskalen gemessen. Daher können Fairness-Kennzahlen wie der Fairness-Index von Jain nicht angewendet werden, da die Messskala eine Verhältnisskala mit einem klar definierten Nullpunkt sein muss (Variationskoeffizienten siehe Beispiele für Missbrauch). QoE kann auf Intervallskalen gemessen werden. Ein typisches Beispiel ist eine 5-Punkte-MOS-Skala (Mean Opinion Score), wobei 1 die niedrigste Qualität und 5 die höchste Qualität angibt. Während der Variationskoeffizient bedeutungslos ist, ist die Standardabweichung

{ displaystyle sigma}

$sigma$ liefert ein Maß für die Streuung der QoE unter den Benutzern.

Hossfeld et al. haben einen QoE-Fairness-Index vorgeschlagen, der die Untergrenze berücksichtigt

{ displaystyle L}

$L.$ und die höhere Grenze

{ displaystyle H}

$H.$ der Bewertungsskala.^[5]

{ displaystyle F = 1 – { frac {2 sigma} {HL}}}

Der QoE-Fairness-Index

{ displaystyle F}

$F.$ hat einige gewünschte Eigenschaften wie Skalierung und metrische Unabhängigkeit. Die Maßeinheit spielt keine Rolle. Eine lineare Transformation der QoE-Werte ändert den Wert des Fairness-Index nicht. Der Fairness-Index ist im Intervall begrenzt

{ displaystyle [0;1]}}

$[0;1]$ 1 zeigt perfekte QoE-Fairness an – alle Benutzer erfahren die gleiche Qualität. 0 bedeutet völlige Ungerechtigkeit, z. B. erleben 50% der Benutzer die höchste QoE

{ displaystyle H}

$H.$ und 50% erfahren die niedrigste QoE

{ displaystyle L}

$L.$ .

Produktbasierte Fairness-Indizes[edit]

Produktbasierte Fairness-Indizes basieren auf der allgemeinen Fairness-Formulierung:

{ displaystyle { mathcal {A}} ( mathbf {x}) = prod _ {i = 0} ^ {n} f left ({ frac {x_ {i}} { max ( mathbf { x})}} right)}

{ displaystyle f}

$f$ ist eine beliebige Transformationsfunktion. Zum

{ displaystyle f}

$f$ eine gültige Transformationsfunktion sein:

{ displaystyle f (x) in [0,1]}}

${ displaystyle f (x) in [0,1]}}$ zum

{ displaystyle 0 leq x leq 1}

$0 leq x leq 1$ . Der resultierende Index hat somit einen Wert zwischen 0 und 1. Da der Fairness-Index von Jain unter atypischen Bedingungen als übermäßig empfindlich bezeichnet wird, kann die produktbasierte Fairness willkürlich definiert werden, um eine gewünschte Empfindlichkeit zu erhalten.

Eine Zuordnung, die Fairness F gemäß der obigen Formulierung aufweist, kann gegeben werden durch

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

{ displaystyle g (x)}

$g (x)$ ist eine nicht abnehmende Funktion mit

{ displaystyle g (0) = 0}

$g (0) = 0$ . Es ist oft bequem, g als etwas zu betrachten

{ displaystyle g (x) = x ^ {m}}

${ displaystyle g (x) = x ^ {m}}$ . Angenommen, f nimmt zu und

{ displaystyle f (0) = 0}

$f (0) = 0$ und

{ displaystyle f (1) = 1}

$f (1) = 1$ Dies ergibt ein minimales zu maximales Verhältnis von ungefähr

{ displaystyle f ^ {- 1} left ( exp left ({ frac {m + 1} {n}} ln (F) right) right)}

Der lineare produktbasierte Fairness Index hat

{ displaystyle f (x) = x}

$f (x) = x$ und sieht aus wie folgt:

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

Es wird beobachtet, dass

{ displaystyle { mathcal {L}} ( mathbf {x})}

${ displaystyle { mathcal {L}} ( mathbf {x})}$ ist sehr empfindlich für kleine Werte von

{ displaystyle x_ {i} / max ( mathbf {x})}

${ displaystyle x_ {i} / max ( mathbf {x})}$ . Zum Beispiel

{ displaystyle mathbf {h} = {20,10,5,1 }}

${ displaystyle mathbf {h} = {20,10,5,1 }}$ ergibt

{ displaystyle { mathcal {L}} ( mathbf {h}) = 0,00625}

${ displaystyle { mathcal {L}} ( mathbf {h}) = 0,00625}$

G’s Fairness Index[edit]

Der Fairness-Index des G.

{ displaystyle { mathcal {I}}}

${ mathcal {I}}$ wird hauptsächlich von Telekommunikationsbetreibern im Zusammenhang mit der Bandbreitenzuweisung verwendet. G’s

{ displaystyle k}

$k$ Der Fairness-Index der Ordnung skaliert die Bruchteile des produktbasierten Fairness-Index durch eine angetriebene Sinustransformation

{ displaystyle f (x) = sin (x pi / 2) ^ { frac {1} {k}}}

${ displaystyle f (x) = sin (x pi / 2) ^ { frac {1} {k}}}$ ::

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

{ displaystyle k in mathbb {R} ^ {+}}

${ displaystyle k in mathbb {R} ^ {+}}$ . Der erste Quadrant der Sinuswelle wird als Abbildungsfunktion zum Aufblasen von Brüchen verwendet. Daher verringert sich die Sensitivität der produktbasierten Fairness für Werte nahe

{ displaystyle max ( mathbf {x})}

${ displaystyle max ( mathbf {x})}$ , während der Index noch einen Wert zwischen 0 und 1 ausgibt.

Im Vergleich zum Fairness-Index von Jain liefert der Fairness-Index von G kleinere Werte, ist empfindlicher gegenüber einer möglichen unfairen Bandbreitenverteilung und kann auf Null gehen. Im Zusammenhang mit Netzwerken ist letzteres ein Vorteil gegenüber dem Fairness-Index von Jain, wenn einige Werte in einem Satz auf ein niedriges Niveau fallen. Darüber hinaus wird der Fairness-Index von Jain als Durchschnitt angesehen Nutzer Wahrnehmung von Fairness^[6] Der Fairness-Index von G konzentriert sich mehr auf die Gleichstellung innerhalb einer Gruppe. Zum Beispiel für

{ displaystyle mathbf {m} = {20,20,20,0 }}

${ displaystyle mathbf {m} = {20,20,20,0 }}$ wir bekommen

{ displaystyle mathrm {Jain} ( mathbf {m}) = 0,75}

${ displaystyle mathrm {Jain} ( mathbf {m}) = 0,75}$ und

{ displaystyle { mathcal {G_ {1}}} ( mathbf {m}) = 0}

${ displaystyle { mathcal {G_ {1}}} ( mathbf {m}) = 0}$ .

Bossaers Fairness-Index[edit]

Während der Fairness-Index von G die Fraktionen näher anbläst

{ displaystyle max ( mathbf {x})}

${ displaystyle max ( mathbf {x})}$ Der Fairness-Index des Bossaer erhöht die Fraktionen näher an 0. Bossaer’s

{ displaystyle k}

$k$ Transformationsfunktion th-order

{ displaystyle f (x) = x ^ { frac {1} {k}}}

${ displaystyle f (x) = x ^ { frac {1} {k}}}$ ergibt den Fairness Index:

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

Die linearen produktbasierten Fairness-Indizes sind ein Sonderfall von Bossaer

{ displaystyle k = 1}

$k = 1$ .

Kausale Fairness[edit]

Die kausale Fairness misst die Häufigkeit, mit der zwei nahezu identische Benutzer oder Anwendungen, die sich nur in einer Reihe von Merkmalen unterscheiden, für die eine faire Ressourcenzuweisung erforderlich ist, identisch behandelt werden.^[7]

Andere Metriken[edit]

Es wurden mehrere andere Metriken definiert, z Worst-Case-Fairness.^[8]

^ Pokhrel, Shiva Raj; Panda, Manoj; Vu, Hai L.; Mandjes, Michel (2016). “TCP-Leistung über WLAN: Gemeinsame Auswirkungen von Puffer- und Kanalverlusten”. IEEE-Transaktionen auf Mobile Computing. 15 (5): 1279–1291. doi:10.1109 / TMC.2015.2456883.
^ Jain, R.; Chiu, DM; Hawe, W. (1984). “Ein quantitatives Maß für Fairness und Diskriminierung bei der Ressourcenzuweisung in gemeinsam genutzten Computersystemen” (PDF). DEC-Forschungsbericht TR-301.
^ Georgopoulos, Panagiotis; Elkhatib, Yehia; Broadbent, Matthew; Mu, Mu; Rennen, Nicholas (2013). “Auf dem Weg zu einer netzwerkweiten QoE-Fairness durch Openflow-gestütztes adaptives Video-Streaming”. Vorträge des ACM SIGCOMM-Workshops 2013 über zukünftige menschenzentrierte Multimedia-Netzwerke.
^ Petrangeli, Stefano; Claeys, Maxim; Latre, Steven; Famaey, Jeroen; De Turck, Filip (2014). “Ein auf Q-Learning basierendes Multi-Agent-Framework zur Erzielung von Fairness beim adaptiven HTTP-Streaming”. IEEE-Symposium für Netzwerkbetrieb und -verwaltung (NOMS).
^ Hossfeld, Tobias; Skorin-Kapov, Lea; Heegaard, Poul E.; Varela, Martin (11. Oktober 2016). “Definition der QoE-Fairness in gemeinsam genutzten Systemen”. IEEE-Kommunikationsbriefe. 21 (1): 184–187. doi:10.1109 / LCOMM.2016.2616342.Hobfeld, Tobias; Skorin-Kapov, Lea; Heegaard, Poul E.; Varela, Martin (19. September 2017). “Definition der QoE-Fairness in gemeinsam genutzten Systemen”. Zenodo Preprint. doi:10.5281 / zenodo.893343.
^ http://www.cse.wustl.edu/~jain/atmf/ftp/af_fair.pdf
^ Galhotra, Sainyam; Brun, Yuriy; Meliou, Alexandra (2017). Fairness Testing: Testsoftware auf Diskriminierung. Bericht über das 11. gemeinsame Treffen der Europäischen Software Engineering Konferenz und des ACM SIGSOFT Symposiums über die Grundlagen des Software Engineering (ESEC / FSE). S. 498–510. arXiv:1709.03221. doi:10.1145 / 3106237.3106277. ISBN 9781450351058.
^ Bennett, JCR; Hui Zhang (1996). “WF / sup 2 / Q: Worst-Case-Fair-Weighted-Fair-Queuing”. Verfahren von IEEE INFOCOM ’96. Konferenz über Computerkommunikation. 1. p. 120. doi:10.1109 / INFCOM.1996.497885. ISBN 978-0-8186-7293-4.

Weiterführende Literatur[edit]

after-content-x4