How to achieve max-min fairness in discrete domain?

A feasible solution is max-min fair if it is not possible to increase the utility of one user (1) while maintaining feasibility, and (2) without reducing the utility of another user that has equal or less utility.

In discrete domains, max-min fair solution may not exist. In this case, maximal fairness was defined in [1], as an alternative.

Maximally fair solution can be achieved using a progressive filling approach: allocate each stream its lowest bitrate. Then, select and upgrade the stream with the lowest utility value to the next higher bitrate if the new total of allocated bitrates does not exceed the link capacity. Repeat the previous step.


References
[1] A. Mansy. Network and End-host support for HTTP Adaptive Video Streaming. PhD thesis, Georgia Institute of Technology, 2014.

When to use Proportional Fairness?

Proportional fairness performs well when all users have the same utility function [1].


References
[1] Mu, Mu, et al. "User-level fairness delivered: network resource allocation for adaptive video streaming." 2015 IEEE 23rd International Symposium on Quality of Service (IWQoS). IEEE, 2015.

should users receive the same bitrate or the same quality?

Since there is no linear correlation between the bitrate of a video stream and its perceptual quality [1], the fairness algorithm should assure that users get similar qualities rather than similar bitrates.



References  
[1] G. Cermak, M. Pinson, and S. Wolf. The relationship among video quality, screen resolution, and bit rate. Broadcasting, IEEE Transactions on, 57(2):258–262, 2011.

Metrics for Adaptive Video Streaming

Metrics can be divided into user-level and network-level groups.

• User-level Fairness Delivered: Network Resource Allocation for Adaptive Video Streaming [1]
• They used three metrics: video quality, switching impact, and network cost (or utility)
• They solved the problem just based on video quality metrics, and then adjusted the results based on a weighted average of the three metrics.
• They considered that clients might have devices with varying resolutions, but didn't consider that the representations on the server might also have different resolutions.
• To simulate wireless conditioned they randomly changed the available bandwidth between 500 kbps and 8 Mbps.
• In switching impact metric, they considered forgiveness effect [2][3][4].
• To implement fairness, they minimized the Relative Standard Deviation (RSD) of the metrics.  
• 
  

References

[1] Mu, Mu, et al. "User-level fairness delivered: network resource allocation for adaptive video streaming." 2015 IEEE 23rd International Symposium on Quality of Service (IWQoS). IEEE, 2015.

[2] Z. Liu, Y. Shen, K. W. Ross, S. S. Panwar, and Y. Wang. Layerp2p: Using layered video chunks in p2p live streaming. IEEE Transactions on Multimedia, 11(7):1340–1352, 2009.

[3] V. Seferidis, M. Ghanbari, and D. Pearson. Forgiveness effect in subjective assessment of packet video. Electronics Letters, 28(21):2013–2014, 1992.

[4] D. Hands. Temporal characterization of forgiveness effect. Electronics Letters, 37, 2002.