# 2022: Компьютерные системы и сети. Лекция 8.
[TOC]

# Меры распределения ресурсов (Fairness measure) и качества сервиса (QoS)

Меры адекватного распределения ресурсов (или просто "метрики справедливости") используются в сетевой инженерии и программировании для определения получаемых пользователем или компонентом распределенного приложения "справедливых" долей ресурсов канала, сервера, системы. Существует много философских и математических определений "справедливости".

## "TCP Справедливость" разделения ресурсов в протоколах поверх TCP
Механизм контроля перегрузки при разработке новых протоколов передачи данных и функционирования клиент-серверных распределенных интернет-приложений

или даже [одноранговых (пиринговых)](https://ru.wikipedia.org/wiki/%D0%9E%D0%B4%D0%BD%D0%BE%D1%80%D0%B0%D0%BD%D0%B3%D0%BE%D0%B2%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C) приложений

должен быть не хуже, чем соответствующие механизмы TCP и должен безконфликтно взаимодействовать с TCP.

"TCP справедливость" обязует новые протоколы получать не большую долю ресурсов сети, чем сравнимый поток TCP. Это связано с тем, что этот протокол является на данный момент доминантым, хорошо протестированным транспортным протоколом интернета, и, если новый протокол будет получать "несправедливую" долю пропускной способности, он будет явно или неявно вызывать уже давно известные проблемы, в частности, коллапс производительности из-за перегрузки.

Например, такие проблемы были в первой версии протокола [RealMedia](https://ru.wikipedia.org/wiki/RealMedia): он базировался на UDP и блокировался файрволами из-за отсутствия адекватной обратной связи по перегрузке каналов, до тех пор пока не была разработана его TCP версия.

А вот противоположный пример. "Несправедливость" (или неподготовленность)
использования каналов WiFi и мобильных сетей протоколом TCP до сих пор является критической проблемой [1]. Возможно, именно этим и была вызвана активная разработка протокола [HTTP3](https://en.wikipedia.org/wiki/HTTP/3)

## [Индекс Джайна](https://www.researchgate.net/publication/220486705_A_Quantitative_Measure_Of_Fairness_And_Discrimination_For_Resource_Allocation_In_Shared_Computer_Systems)

Индекс Радж Джайна,
$$
{\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}}}}
$$
оценивает справедливость распределения $X= (x_{1},x_{2},\dots ,x_{n})$ потребления ресурсов ${\displaystyle n}$ пользователями.
Например, ${\displaystyle x_{i}}$ может быть пропускная способность для ${\displaystyle i}$-того соединения в канале, и ${\displaystyle {\widehat {c_{\rm {v}}}}}$ - оценка [коэффициента вариации](https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%8D%D1%84%D1%84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82_%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D1%86%D0%B8%D0%B8) $c_{\rm {v}} = {\displaystyle {\frac {s}{\bar {x}}}}$ данной выборки ($s$ - среднеквадратическое отклонение). Результат находится в диапазоне от ${\displaystyle {\frac {1}{n}}}$ (в худшем случае) до 1 (в лучшем случае), и этот максимум индекса достигается, когда все пользователи получают одинаковые доли использования ресурса. Это индекс равен ${\displaystyle {\frac {k}{n}}}$, когда ${\displaystyle k}$ пользователей равно делят ресурс между собой, а остальные ${\displaystyle n-k}$ получили нулевую долю.

**Задание. Докажите эти замечательные свойства**

Эта метрика хорошо выявляет недоиспользованность каналов, но не является слишком чувствительной к атипичному поведению потоков в сети.

Если нужно решить обратную задачу, когда по заданному индексу $\mathcal {J'}$ надо сгенерировать тестовые данные $X= (x'_{1},x'_{2},\dots ,x'_{n})$ можно применить
а) приближенный метод:
выбрать значения ${\displaystyle x'_{k}=A\cdot k^{\alpha }}$, где
$$
{\displaystyle \alpha ={\frac {1-\mathcal {J'}+{\sqrt {1-\mathcal {J'}}}}{\mathcal {J'}}}}
$$
и $A$ - фактор, служащий для нормализации или масштабирования
б) точный метод:
точный метод основан на представлении значений ${\displaystyle x'_{k}}$ в виде
$$
{\displaystyle x'_{k}=A\cdot e^{2\alpha k}},
$$
где ${\displaystyle \alpha }$ - решение уравнения
$$
{\displaystyle \tanh(n\alpha )-\mathcal {J'} \cdot n\tanh(\alpha ) = 0} .
$$

## [Индекс QoE справедливости для разделяемых ресурсов](https://osf.io/xczvp/)

Желаемые свойства хорошей оценки справедливости в системах с разделяемыми ресурсами

a) Независимость от количества клиентов разделяемого ресурса
б) Независимость от масштабирования единиц измерения ресурса
в) Ограниченность показаний в интервале [0;1]
г) Непрерывность
д) Интуитивное понимания уровней значений

Этим свойствам удовлетворяет индекс Джайна

Однако часто появляются дополнительные требования:
e) Независимость от начальной точки отсчета
ж) симметричность
з) чувствительность

Одной из удобных оценок "справедливости" (равномерности) распределения ресурсов, удовлетворяющим свойствам а)-з) является индекс QoE справедливости, определяемый следующим образом.

Рассмотрим выборку случайной величины $X$ с ограниченными минимальным $L$ и максимальным $H$ значениями. Если $s$ - среднеквадратическое отклонение случайной величины $X$, a $s_{max}=(H-L)/2$, то индекс справедливости $F_{_{QoE}}$:
$$
F_{_{QoE}} = 1 - \frac{s}{s_{max}}=1 - \frac{2s}{H-L}
$$

<iframe src="//www.slideshare.net/slideshow/embed_code/key/9cWIvlguFf63ID" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/tobiashossfeld/on-qoe-metrics-and-qoe-fairness-for-network-traffic-management" title="On QoE Metrics and QoE Fairness for Network &amp; Traffic Management" target="_blank">On QoE Metrics and QoE Fairness for Network &amp; Traffic Management</a> </strong> from <strong><a href="//www.slideshare.net/tobiashossfeld" target="_blank">Tobias Hoßfeld</a></strong> </div>

Регулировать чувствительность можно, построив обобщенный индекс:
$$
F_{_{QoE}}^\alpha = 1 - {( \frac{s}{s_{max}} )}^\alpha, \\
0 < \alpha
$$
где $\alpha$ - параметр чувствительности индекса

## [Метод максимизации минимального уровня справедливости (Max-min fairness)](https://en.wikipedia.org/wiki/Max-min_fairness)

Достижение макс-мин критерия справедливого распределения ресурса интуитивно описывается как справедливое выделение доли ресурсов для пользователей с небольшими запросами, и равного выделения долей неиспользуемых еще ресурсов оставшимся "большим" запросам.


Формально определить алгоритм макс-мин критерия выделения ресурсов можно так:
* Ресурсы выделяются в порядке возрастания требований
* Никто не получает доли ресурса больше, чем запрашивает
* Клиенты, для которых не возможно удовлетворить их запросы, получают доли ресурса пропорционально их весу (приоритету)

### Макс-мин с равными правами доступа к ресурсу

Это формальное описание соответствует следующим операциям.
Рассмотрим множество источников запросов $1, ..., n$, c запросами $x_1, x_2, ..., x_n$. Без потери общности сортируем запросы по возрастанию:
$$ x_1 \le x_2 \le ... \le x_n.$$
Пусть сервер имеет пропускную способность $C$. Тогда, в качестве начальной доли, выдается доля $C/n$ ресурса на самый малый запрос $x_1$. Может оказаться, что эта доля больше, чем надо первому (самому маленькому) клиенту. Однако, далее это превышение будет скорректировано. Процесс выдачи долей ресурса будет закончен, когда каждый клиент получит не больше, чем он затребовал. И меньшие клиенты получат не меньше, чем большие. Именно поэтому так и называется данный принцип выделения ресурсов.

Пример 1
Определить макс-мин справедливое разделение ресурсов для множества из четырех запросов: 2, 2.6, 4, 5 при условии, что пропускная способность равна 10.

Решение: Справедливое разделение ресурсов получается в ходе нескольких итераций.
1) На первом шаге ресурс просто делится на 4 порции размером 2.5.
Поскольку такая доля больше, чем необходимо первому пользователю, доля размером 0.5 освобождается для оставшихся трех пользователей.
2) Оставшуюся часть пропускной способности делим на 3, получая доли 2.66 для каждого. Но это больше, чем надо второму пользователю, и мы получаем избыток 0.066, который мы добавляем к оставшейся пропускной способности и делим на двух оставшихся пользователей, получая для каждого из них
2.5 + 0.66... + 0.033... = 2.7.

Таким образом, честное разделение ресурсов таково: пользователь 1 получил 2, пользователь 2 получил 2.6, пользователи 3 и 4 получили по 2.7 каждый.

### Макс-мин с приоритетами доступа к ресурсу
Можно расширить этот алгоритм и на случай пользователей с весами (приоритетами).

В предыдущем примере предполагалось, что все пользователи имеют равные приоритеты на выделение ресурсов. Однако часто приходится ранжировать пользователей по разным долям доступа к ресурсу. В частности, можно пользователям c идентификаторами $1, 2, ..., n$ назначить веса $w_1, w_2, ..., w_n$, отражающие их относительные доли в разделении ресурса.

Расширение макс-мин алгоритма выделения ресурсов на случай с весами можно описать следующим образом.
* Ресурсы выделяются в порядке возрастания запросов, нормализованных весами
* Никакой пользователь не получает доли большей, чем его запрос
* Пользователи, для которых невозможно в полной мере удовлетворить его запрос, получают долю ресурсов, пропорциональных его весу (приоритету)

Следующий пример показывает это на практике.
Пример 2.
Определить макс-мин справедливое разделение ресурсов для множества из четырех запросов: 4, 2, 10, 4 и весам пользователей: 2.5, 4, 0.5, 1 , при ограничении ресурса равного 16.

Решение:
1. Нормализация весов такая, что самый малый вес равен 1.
В этой задаче мы получаем нормализованные веса: 5, 8, 1, 2.
Масштабируем количество виртуальных пользователей до 5 + 8 + 1 + 2 = 16 вместо 4 реальных. Следовательно, наша задача разбить ресурс уже не на 4, а на 16 долей.
2. На каждой итерации, выделеяется доля ресурса пропорциональная его весу. Так на первой итерации получаем $C/n= 16/16 = 1$. На этом шаге пользователи получают 5, 8, 1, 2 единиц ресурса соответственно.
3. Пользователь 1 получает 5 долей при запросе 4, то есть на 1 единицу больше, чем требуется. Аналогичноe пользователь 2 получает на 6 единиц больше. Пользователи 3 и 4 ждут, поскольку их доли меньше их запросов.
4. Пользователям 3 и 4 должны быть отданы 7 единиц ресурсов.
Их веса 1 и 2, и самый малый вес 1, так что на этом шаге нет пока необходимости заново нормализоать веса.
Пользователю 3 добавляются 7 × 2/3 единицы (поскольку его вес 1), и пользователю 4 добавляются допольнительные 7 × 2/3 единицы.
В результате пользователь 4 получает долю 2 + 7 × 2/3 = 6.666 единиц ресурса, что больше его запроса. Поэтому излишек в 2.666 единицы отдается пользователю 3, который в результате получает 1 + 7/3 + 2.666 = 6 единиц.

Окончательные доли: 4, 2, 6, 4.

# Ресурсы
1. [TCP Performance over Wi-Fi: Joint Impact of Buffer and Channel Losses](https://www.researchgate.net/publication/280601540_TCP_Performance_over_Wi-Fi_Joint_Impact_of_Buffer_and_Channel_Losses)
2. [Индекс Джайна](https://www.researchgate.net/publication/220486705_A_Quantitative_Measure_Of_Fairness_And_Discrimination_For_Resource_Allocation_In_Shared_Computer_Systems)
3. [Definition of QoE Fairness in Shared Systems](https://osf.io/xczvp/)
8. [Fairness_measure](https://en.wikipedia.org/wiki/Fairness_measure)
4. [Max-min_fairness](https://en.wikipedia.org/wiki/Max-min_fairness)
5. [Computer Networks performance and Quality of Services](https://www.ece.rutgers.edu/~marsic/books/CN/book-CN_marsic.pdf)
6. [PERFORMANCE EVALUATION OF COMPUTER AND COMMUNICATION SYSTEMS](https://leboudec.github.io/perfeval/book/perf.pdf)
https://leboudec.github.io/perfeval/index.html
7. [Rate adaptation, Congestion Control and Fairness:A Tutorial](https://ica1www.epfl.ch/PS_files/LEB3132.pdf)