Fairness measure

Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness.

Transmission Control Protocol fairness

Congestion control mechanisms for new network transmission protocols or peer-to-peer applications must interact well with Transmission Control Protocol (TCP). TCP fairness requires that a new protocol receive a no larger share of the network than a comparable TCP flow. This is important as TCP is the dominant transport protocol on the Internet, and if new protocols acquire unfair capacity they tend to cause problems such as congestion collapse. This was the case with the first versions of RealMedia's streaming protocol: it was based on UDP and was widely blocked at organizational firewalls until a TCP-based version was developed. TCP throughput unfairness over WiFi is a critical problem and needs further investigations. ^[1]

Jain's fairness index

Raj Jain's equation,

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

rates the fairness of a set of values where there are ${\displaystyle n}$ users, ${\displaystyle x_{i}}$ is the throughput for the ${\displaystyle i}$th connection, and ${\displaystyle {\widehat {c_{\rm {v}}}}}$ is the sample coefficient of variation. The result ranges from ${\displaystyle {\tfrac {1}{n}}}$ (worst case) to 1 (best case), and it is maximum when all users receive the same allocation. This index is ${\displaystyle {\tfrac {k}{n}}}$ when ${\displaystyle k}$ users equally share the resource, and the other ${\displaystyle n-k}$ users receive zero allocation.

This metric identifies underutilized channels and is not unduly sensitive to atypical network flow patterns. ^[2]

To achieve a given fairness level ${\displaystyle F}$, one approximate method is to let ${\displaystyle x_{k}=A\cdot k^{\alpha }}$, where

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

and A is an arbitrary factor, typically used for normalization. This gives an allocation with a fairness close to F, and the allocation can then be refined to get even closer. Note this also allows for a prioritization of allocation, as the ${\displaystyle x_{k}}$s will be sorted.

An exact method is to let ${\displaystyle x_{k}=A\cdot e^{2\alpha k}}$, where ${\displaystyle \alpha }$ solves

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

A simple way to calculate ${\displaystyle \alpha }$ is to use Newton's Method on ${\displaystyle \ln \left({\frac {\tanh(n\alpha )-\tanh(\alpha )}{(nF-1)\cdot \tanh(\alpha )}}\right)=0}$, which converges consistently and fairly quickly.

Both of these methods give non-integer allocations, generally, and sometimes integer allocations are required. This can be done by using one of the above allocation methods, rounding down each allocation to the nearest integer (${\displaystyle x_{k}'=\left\lfloor x_{k}\right\rfloor }$), and then iteratively allocating one unit to a user, with the probability that user k receives it is proportional to ${\displaystyle x_{k}-\left\lfloor x_{k}\right\rfloor }$.

Max-min fairness

Main article: Max-min fairness

Max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any flow necessarily results in the decrease in the allocation of some other flow with an equal or smaller allocation. A max-min fair allocation is achieved when bandwidth is allocated equally and in infinitesimal increments to all flows until one is satisfied, then amongst the remainder of the flows and so on until all flows are satisfied or the bandwidth is exhausted.

Fairly shared spectrum efficiency

In packet radio wireless networks, The fairly shared spectrum efficiency (FSSE) can be used as a combined measure of fairness and system spectrum efficiency. The system spectral efficiency is the aggregate throughput in the network divided by the utilized radio bandwidth in hertz. The FSSE is the portion of the system spectral efficiency that is shared equally among all active users (with at least one backlogged data packet in queue or under transmission). In case of scheduling starvation, the FSSE would be zero during certain time intervals. In case of equally shared resources, the FSSE would be equal to the system spectrum efficiency. To achieve max-min fairness, the FSSE should be maximized.

FSSE is useful especially when analyzing advanced radio resource management (RRM) schemes, for example channel adaptive scheduling, for cellular networks with best-effort packet data service. In such system it may be tempting to optimize the spectrum efficiency (i.e. the throughput). However, that might result in scheduling starvation of "expensive" users at far distance from the access point, whenever another active user is closer to the same or an adjacent access point. Thus the users would experience unstable service, perhaps resulting in a reduced number of happy customers. Optimizing the FSSE results in a compromise between fairness (especially avoiding scheduling starvation) and achieving high spectral efficiency.

If the cost of each user is known, in terms of consumed resources per transferred information bit, the FSSE measure may be redefined to reflect proportional fairness. In a proportional fair system, this "proportionally fair shared spectrum efficiency" (or "fairly shared radio resource cost") is maximized. This policy is less fair since "expensive" users are given lower throughput than others, but still scheduling starvation is avoided.

QoE fairness

The idea of QoE fairness is to quantify fairness among users by considering the Quality of Experience (QoE) as perceived by the end user. This is especially of importance in network management where operators want to keep their users sufficiently satisfied (i.e. high QoE) in a fair manner, see QoE management. Several approaches have been proposed to ensure network-wide QoE fairness especially for adaptive video streaming. ^{[3] [4]}

In contrast to network related measures like throughput, QoE is typically not measured on ratio scales. Hence, fairness measures like Jain's fairness index cannot be applied, as the measurement scale requires to be a ratio scale with a clearly defined zero point (see examples of misuse for coefficients of variation). QoE may be measure on interval scales. A typical example is a 5-point mean opinion score (MOS) scale, with 1 indicating lowest quality and 5 indicating highest quality. While the coefficient of variation is meaningless, the standard deviation ${\displaystyle \sigma }$ provides a measure of the dispersion of QoE among users.

Hossfeld et al. have proposed a QoE Fairness index which considers the lower bound ${\displaystyle L}$ and the higher bound ${\displaystyle H}$ of the rating scale. ^[5]

${\displaystyle F=1-{\frac {2\sigma }{H-L}}}$

The QoE fairness index ${\displaystyle F}$ has some desired properties like scale and metric independence. The unit of measurement does not matter. Any linear transformation of the QoE values does not change the value of the fairness index. The fairness index is bounded in the interval ${\displaystyle [0;1]}$ with 1 indicating perfect QoE fairness – all users experience the same quality. 0 indicates total unfairness, e.g. 50% of users experience highest QoE ${\displaystyle H}$ and 50% experience lowest QoE ${\displaystyle L}$.

Product-based Fairness Indices

Product-based fairness indices are based on the general fairness formulation:

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

where ${\displaystyle f}$ is an arbitrary transformation function. For ${\displaystyle f}$ to be a valid transformation function: ${\displaystyle f(x)\in [0,1]}$ for ${\displaystyle 0\leq x\leq 1}$. The resulting index thus has a value between 0 and 1. As Jain's fairness index is said to be unduly sensitive under atypical conditions, the product-based fairness can be defined arbitrarily to obtain a desired sensitivity.

An allocation that has fairness F according to the formulation above can be given by

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

where ${\displaystyle g(x)}$ is any non-decreasing function with ${\displaystyle g(0)=0}$ . it is often convenient to take g to be something like ${\displaystyle g(x)=x^{m}}$. Assuming f is increasing and ${\displaystyle f(0)=0}$ and ${\displaystyle f(1)=1}$, this gives a minimum to maximum ratio of about

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

The linear product-based fairness index has ${\displaystyle f(x)=x}$ and looks as follows:

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

It is observed that ${\displaystyle {\mathcal {L}}(\mathbf {x} )}$ is very sensitive for small values of ${\displaystyle x_{i}/\max(\mathbf {x} )}$. For example ${\displaystyle \mathbf {h} =\{20,10,5,1\}}$ yields ${\displaystyle {\mathcal {L}}(\mathbf {h} )=0.00625}$

G's fairness index

The G's fairness index ${\displaystyle {\mathcal {I}}}$ is primarily used by telecom operators in the context of bandwidth allocation^{[ citation needed ]}. G's ${\displaystyle k}$th-order fairness index scales the fractions of the product-based fairness index by a powered sine transformation ${\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}}}$,

where ${\displaystyle k\in \mathbb {R} ^{+}}$. The first quadrant of the sine wave is used as a mapping function to inflate fractions . As such, the sensitivity of the product-based fairness is decreased for values close to ${\displaystyle \max(\mathbf {x} )}$, while the index still outputs a value between 0 and 1.

Compared to Jain's fairness index, G's fairness index yields smaller values, it is more sensitive to potential unfair bandwidth distribution and can go to zero. In the context of networks, the latter is an advantage over Jain's fairness index when a few values in a set drop to low levels. Moreover, Jain's fairness index is deemed as an average user perception of fairness ^[6] whereas G's fairness index is focused more on equality within a group. For example, for ${\displaystyle \mathbf {m} =\{20,20,20,0\}}$ we get ${\displaystyle \mathrm {Jain} (\mathbf {m} )=0.75}$ and ${\displaystyle {\mathcal {G_{1}}}(\mathbf {m} )=0}$.

Bossaer's fairness index

Whereas G's fairness index inflates the fractions closer to ${\displaystyle \max(\mathbf {x} )}$, the Bossaer's fairness index inflates the fractions closer to 0. Bossaer's ${\displaystyle k}$th-order transformation function ${\displaystyle f(x)=x^{\frac {1}{k}}}$ yields the fairness index:

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

The linear product-based fairness indices is a special case of Bossaer's where ${\displaystyle k=1}$.

Causal fairness

Causal fairness measures the frequency with which two nearly identical users or applications who differ only in a set of characteristics with respect to which resource allocation must be fair receive identical treatment. ^[7]

Other metrics

Several other metrics have been defined, such as Worst Case Fairness. ^[8]

Notes

1. Pokhrel, Shiva Raj; Panda, Manoj; Vu, Hai L.; Mandjes, Michel (2016). "TCP Performance over Wi-Fi: Joint Impact of Buffer and Channel Losses". IEEE Transactions on Mobile Computing. 15 (5): 1279–1291. doi:10.1109/TMC.2015.2456883. S2CID   10323290.
2. Jain, R.; Chiu, D.M.; Hawe, W. (1984). "A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems" (PDF). DEC Research Report TR-301.
3. Georgopoulos, Panagiotis; Elkhatib, Yehia; Broadbent, Matthew; Mu, Mu; Race, Nicholas (2013). "Towards network-wide QoE fairness using openflow-assisted adaptive video streaming". Proceedings of the 2013 ACM SIGCOMM workshop on Future human-centric multimedia networking. pp. 15–20. doi:10.1145/2491172.2491181. ISBN   9781450321839. S2CID   2946134.
4. Petrangeli, Stefano; Claeys, Maxim; Latre, Steven; Famaey, Jeroen; De Turck, Filip (2014). "A multi-agent Q-Learning-based framework for achieving fairness in HTTP Adaptive Streaming". 2014 IEEE Network Operations and Management Symposium (NOMS). pp. 1–9. doi:10.1109/NOMS.2014.6838245. ISBN   978-1-4799-0913-1. S2CID   16573649.
5. Hossfeld, Tobias; Skorin-Kapov, Lea; Heegaard, Poul E.; Varela, Martin (11 Oct 2016). "Definition of QoE fairness in shared systems". IEEE Communications Letters. 21 (1): 184–187. doi:10.1109/LCOMM.2016.2616342. hdl: 11250/2433049 . S2CID   23790117.Hobfeld, Tobias; Skorin-Kapov, Lea; Heegaard, Poul E.; Varela, Martin (19 Sep 2017). "Definition of QoE fairness in shared systems". Zenodo Preprint. doi:10.5281/zenodo.893343.
6. Throughput Fairness Index: An Explanation
7. Galhotra, Sainyam; Brun, Yuriy; Meliou, Alexandra (2017). "Fairness testing: Testing software for discrimination". Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. pp. 498–510. arXiv: 1709.03221 . doi:10.1145/3106237.3106277. ISBN   9781450351058. S2CID   6324652.
8. Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN   978-0-8186-7293-4. S2CID   17558577.

Further reading

• Almeida, A.; Casetti, C.; Oueslati, S.; Avratchenkov, K. & Johansson, M. A Taxonomy of Congestion Control (in deliverable No: D.WP.JR.2.1.1) ^{[ permanent dead link ‍]} EuroNGI, 2004
• Mo, J.; Walrand, J. (2000). "Fair End-to-End Window-Based Congestion Control" (PDF). IEEE/ACM Transactions on Networking. 8 (5): 556–567. doi:10.1109/90.879343. Archived from the original (PDF) on 2012-11-19.