Мера справедливости

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

Справедливость протокола управления передачей

контроля перегрузки Механизмы для новых протоколов сетевой передачи или одноранговых приложений должны хорошо взаимодействовать с протоколом управления передачей (TCP). Справедливость TCP требует, чтобы новый протокол получал не большую долю сети, чем сопоставимый поток TCP. Это важно, поскольку TCP является доминирующим транспортным протоколом в Интернете, и если новые протоколы приобретают несправедливую пропускную способность, они могут вызвать такие проблемы, как коллапс перегрузки . Так было с первыми версиями RealMedia протокола потоковой передачи : он был основан на UDP и широко блокировался на межсетевых экранах организаций, пока не была разработана версия на основе TCP. Неравномерность пропускной способности TCP через Wi-Fi является критической проблемой и требует дальнейшего исследования. ^[1]

Индекс справедливости Джайна

Раджа Джайна Уравнение ,

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

оценивает справедливость набора ценностей, где существуют $n$ пользователи, $x_{i}$ это пропускная способность для $i$ е соединение, и ${\widehat {c_{\rm {v}}}}$ – выборочный коэффициент вариации . Результат варьируется от ${\tfrac {1}{n}}$ (худший случай) до 1 (лучший случай), и это максимальное значение, когда все пользователи получают одинаковое распределение. Этот индекс ${\tfrac {k}{n}}$ когда $k$ пользователи поровну делят ресурс, а остальные $n-k$ пользователи получают нулевое распределение.

Эта метрика определяет недостаточно используемые каналы и не является чрезмерно чувствительной к нетипичным моделям сетевых потоков. ^[2]

Для достижения заданного уровня справедливости $F$ , один из приближенных методов состоит в том, чтобы позволить $x_{k}=A\cdot k^{\alpha }$ , где

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

и A — произвольный коэффициент, обычно используемый для нормализации. Это дает распределение со справедливостью, близкой к F , а затем распределение можно уточнить, чтобы сделать его еще ближе. Обратите внимание, что это также позволяет установить приоритет распределения, поскольку $x_{k}$ s будет отсортировано.

Точный метод состоит в том, чтобы позволить $x_{k}=A\cdot e^{2\alpha k}$ , где $\alpha$ решает

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

.

Простой способ расчета $\alpha$ заключается в использовании Ньютона метода $\ln \left({\frac {\tanh(n\alpha )-\tanh(\alpha )}{(nF-1)\cdot \tanh(\alpha )}}\right)=0$ , которая сходится последовательно и довольно быстро.

Оба эти метода обычно дают нецелочисленные выделения, но иногда требуются целочисленные выделения. Это можно сделать, используя один из вышеперечисленных методов распределения, округляя каждое распределение до ближайшего целого числа ( $x_{k}'=\left\lfloor x_{k}\right\rfloor$ ), а затем итеративно выделяя одну единицу пользователю, причем вероятность того, что пользователь k получит ее, пропорциональна $x_{k}-\left\lfloor x_{k}\right\rfloor$ .

Макс-мин справедливости

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

Справедливо разделенная эффективность использования спектра

В пакетной радиосвязи беспроводных сетях эффективность совместного использования спектра (FSSE) может использоваться как комбинированная мера справедливости и эффективности использования спектра системы . Спектральная эффективность системы представляет собой совокупную пропускную способность сети, деленную на используемую полосу пропускания радиоканала в герцах. FSSE — это часть спектральной эффективности системы, которая поровну распределяется между всеми активными пользователями (по крайней мере, с одним пакетом данных, находящимся в очереди или на стадии передачи). В случае планирования голодания FSSE будет равен нулю в течение определенных интервалов времени. В случае равномерного распределения ресурсов FSSE будет равен эффективности использования спектра системы. Чтобы достичь максимальной и минимальной справедливости , FSSE должен быть максимальным.

FSSE особенно полезен при анализе схем расширенного управления радиоресурсами (RRM), например адаптивного планирования каналов , для сотовых сетей с услугой пакетной передачи данных с максимальной эффективностью . В такой системе может возникнуть соблазн оптимизировать эффективность использования спектра (т.е. пропускную способность). Однако это может привести к планированию голодания «дорогих» пользователей на большом расстоянии от точки доступа, когда другой активный пользователь находится ближе к той же или соседней точке доступа. Таким образом, пользователи будут испытывать нестабильное обслуживание, что, возможно, приведет к уменьшению количества довольных клиентов. Оптимизация FSSE приводит к компромиссу между справедливостью (особенно во избежание планового голодания) и достижением высокой спектральной эффективности.

Если известна стоимость каждого пользователя в терминах потребляемых ресурсов на каждый переданный информационный бит, показатель FSSE может быть переопределен, чтобы отразить пропорциональную справедливость . В пропорционально-справедливой системе эта «пропорционально справедливая эффективность совместного использования спектра» (или «справедливо разделенная стоимость радиоресурсов») максимизируется. Эта политика менее справедлива, поскольку «дорогим» пользователям предоставляется меньшая пропускная способность, чем другим, но при этом удается избежать планового голодания.

Справедливость качества взаимодействия

Идея справедливости QoE заключается в количественной оценке справедливости среди пользователей путем рассмотрения качества опыта (QoE), как его воспринимает конечный пользователь. Это особенно важно при управлении сетью , где операторы хотят, чтобы их пользователи были достаточно удовлетворены (т. е. имели высокий уровень QoE) на справедливой основе, см. Управление QoE . Было предложено несколько подходов для обеспечения справедливости QoE в масштабах всей сети, особенно для адаптивной потоковой передачи видео. ^[3]^[4]

В отличие от показателей, связанных с сетью, таких как пропускная способность, QoE обычно не измеряется по шкале отношений . Следовательно, меры справедливости, такие как индекс справедливости Джайна, не могут быть применены, поскольку шкала измерения должна быть шкалой отношений с четко определенной нулевой точкой (см. примеры неправильного использования коэффициентов вариации). QoE можно измерять по интервальным шкалам . Типичным примером является 5-балльная шкала среднего мнения (MOS) , где 1 указывает на самое низкое качество, а 5 — на самое высокое качество. Хотя коэффициент вариации не имеет смысла, стандартное отклонение $\sigma$ обеспечивает меру дисперсии QoE среди пользователей.

Хоссфельд и др. предложили индекс справедливости QoE, который учитывает нижнюю границу $L$ и верхняя граница $H$ рейтинговой шкалы. ^[5]

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

Индекс справедливости QoE $F$ имеет некоторые желаемые свойства, такие как независимость от масштаба и метрики. Единица измерения не имеет значения. Любое линейное преобразование значений QoE не меняет значения индекса справедливости. Индекс справедливости ограничен интервалом $[0;1]$ где 1 указывает на идеальную справедливость QoE — все пользователи получают одинаковое качество. 0 указывает на полную несправедливость, например, 50 % пользователей имеют самое высокое качество взаимодействия. $H$ и 50% испытывают самое низкое качество обслуживания $L$ .

Индексы справедливости на основе продуктов

Индексы справедливости на основе продуктов основаны на общей формулировке справедливости:

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

,

где $f$ — произвольная функция преобразования. Для $f$ быть допустимой функцией преобразования: $f(x)\in [0,1]$ для $0\leq x\leq 1$ . Таким образом, результирующий индекс имеет значение от 0 до 1. Поскольку индекс справедливости Джайна считается чрезмерно чувствительным в нетипичных условиях, справедливость на основе продукта может быть определена произвольно, чтобы получить желаемую чувствительность.

Распределение, имеющее справедливость F в соответствии с приведенной выше формулировкой, может быть задано формулой

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

,

где $g(x)$ любая неубывающая функция с $g(0)=0$ . часто удобно считать g чем-то вроде $g(x)=x^{m}$ . Предполагая, что f увеличивается и $f(0)=0$ и $f(1)=1$ , это дает минимальное и максимальное соотношение примерно

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

.

Линейный индекс справедливости, основанный на продукте, имеет $f(x)=x$ и выглядит следующим образом:

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

.

Замечено, что ${\mathcal {L}}(\mathbf {x} )$ очень чувствителен к малым значениям $x_{i}/\max(\mathbf {x} )$ . Например $\mathbf {h} =\{20,10,5,1\}$ урожайность ${\mathcal {L}}(\mathbf {h} )=0.00625$

Индекс справедливости G

Индекс справедливости G ${\mathcal {I}}$ в основном используется операторами связи в контексте распределения полосы пропускания. ^{[ нужна ссылка ]}. G $k$ Индекс справедливости третьего порядка масштабирует доли индекса справедливости на основе продукта с помощью мощного синусоидального преобразования. $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}}

,

где $k\in \mathbb {R} ^{+}$ . Первый квадрант синусоиды используется как отображающая функция для увеличения дробей. Таким образом, чувствительность справедливости, основанной на продукте, снижается для значений, близких к $\max(\mathbf {x} )$ , в то время как индекс по-прежнему выводит значение от 0 до 1.

По сравнению с индексом справедливости Джайна, индекс справедливости G дает меньшие значения, он более чувствителен к потенциально несправедливому распределению полосы пропускания и может достигать нуля. В контексте сетей последнее является преимуществом перед индексом справедливости Джайна, когда несколько значений в наборе падают до низкого уровня. Более того, индекс справедливости Джайна считается средним пользователем . восприятием справедливости ^[6] тогда как индекс справедливости G больше ориентирован на равенство внутри группы. Например, для $\mathbf {m} =\{20,20,20,0\}$ мы получаем $\mathrm {Jain} (\mathbf {m} )=0.75$ и ${\mathcal {G_{1}}}(\mathbf {m} )=0$ .

Индекс справедливости Боссаера

В то время как индекс справедливости G раздувает дроби ближе к $\max(\mathbf {x} )$ , индекс справедливости Боссаера увеличивает дроби ближе к 0. $k$ функция преобразования четвертого порядка $f(x)=x^{\frac {1}{k}}$ дает индекс справедливости:

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

.

Линейные индексы справедливости, основанные на продукте, представляют собой особый случай Боссаера, когда $k=1$ .

Причинная справедливость

Причинная справедливость измеряет частоту, с которой два почти идентичных пользователя или приложения, отличающиеся только набором характеристик, в отношении которых распределение ресурсов должно быть справедливым, получают одинаковое обращение. ^[7]

Другие показатели

Было определено несколько других показателей, таких как « Справедливость в наихудшем случае». ^[8]

Примечания

^ Похрел, Шива Радж; Панда, Манодж; Ву, Хай Л.; Манджес, Мишель (2016). «Производительность TCP через Wi-Fi: совместное влияние потерь в буфере и канале». Транзакции IEEE на мобильных компьютерах . 15 (5): 1279–1291. дои : 10.1109/TMC.2015.2456883 . S2CID 10323290 .
^ Джайн, Р.; Чиу, DM; Хоу, В. (1984). «Количественная мера справедливости и дискриминации при распределении ресурсов в общих компьютерных системах» (PDF) . Отчет об исследовании DEC TR-301 .
^ Георгопулос, Панайотис; Эльхатиб, Йехия; Бродбент, Мэтью; Му, Му; Гонка, Николас (2013). «На пути к обеспечению справедливости QoE в масштабах всей сети с использованием адаптивной потоковой передачи видео с помощью openflow». Материалы семинара ACM SIGCOMM 2013 года по теме «Будущие человеко-ориентированные мультимедийные сети» . стр. 15–20. дои : 10.1145/2491172.2491181 . ISBN 9781450321839 . S2CID 2946134 .
^ Петранджели, Стефано; Клейс, Максим; Латре, Стивен; Фамэй, Йерун; Де Турк, Филип (2014). «Мультиагентная платформа Q-Learning для достижения справедливости в адаптивной потоковой передаче HTTP». Симпозиум IEEE по сетевым операциям и управлению (NOMS) 2014 г. стр. 1–9. дои : 10.1109/NOMS.2014.6838245 . ISBN 978-1-4799-0913-1 . S2CID 16573649 .
^ Хоссфельд, Тобиас; Скорин-Капов, Лия; Хеггард, Пол Э.; Варела, Мартин (11 октября 2016 г.). «Определение справедливости QoE в общих системах» . Коммуникационные письма IEEE . 21 (1): 184–187. дои : 10.1109/LCOMM.2016.2616342 . HDL : 11250/2433049 . S2CID 23790117 . Хобфельд, Тобиас; Скорин-Капов, Лия; Хеггард, Пол Э.; Варела, Мартин (19 сентября 2017 г.). «Определение справедливости QoE в общих системах» . Препринт Зенода . дои : 10.5281/zenodo.893343 .
^ Индекс справедливости пропускной способности: объяснение
^ Галхотра, Сайньям; Брун, Юрий; Мелиу, Александра (2017). «Тестирование справедливости: тестирование программного обеспечения на предмет дискриминации». Материалы 11-го совместного совещания по основам программной инженерии 2017 г. стр. 498–510. arXiv : 1709.03221 . дои : 10.1145/3106237.3106277 . ISBN 9781450351058 . S2CID 6324652 .
^ Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .

Дальнейшее чтение

Алмейда, А.; Казетти, К.; Уэслати, С.; Авратченков К. и Йоханссон М. Таксономия контроля перегрузки (номер результата: D.WP.JR.2.1.1) ^{[ постоянная мертвая ссылка ]} ЕвроНГИ, 2004 г.
Мо, Дж.; Уолранд, Дж. (2000). «Справедливое сквозное управление перегрузкой на основе окон» (PDF) . Транзакции IEEE/ACM в сети . 8 (5): 556–567. дои : 10.1109/90.879343 . Архивировано из оригинала (PDF) 19 ноября 2012 г.

[1] Похрел, Шива Радж; Панда, Манодж; Ву, Хай Л.; Манджес, Мишель (2016). «Производительность TCP через Wi-Fi: совместное влияние потерь в буфере и канале». Транзакции IEEE на мобильных компьютерах . 15 (5): 1279–1291. дои : 10.1109/TMC.2015.2456883 . S2CID 10323290 .

[2] Джайн, Р.; Чиу, DM; Хоу, В. (1984). «Количественная мера справедливости и дискриминации при распределении ресурсов в общих компьютерных системах» (PDF) . Отчет об исследовании DEC TR-301 .

[3] Георгопулос, Панайотис; Эльхатиб, Йехия; Бродбент, Мэтью; Му, Му; Гонка, Николас (2013). «На пути к обеспечению справедливости QoE в масштабах всей сети с использованием адаптивной потоковой передачи видео с помощью openflow». Материалы семинара ACM SIGCOMM 2013 года по теме «Будущие человеко-ориентированные мультимедийные сети» . стр. 15–20. дои : 10.1145/2491172.2491181 . ISBN 9781450321839 . S2CID 2946134 .

[4] Петранджели, Стефано; Клейс, Максим; Латре, Стивен; Фамэй, Йерун; Де Турк, Филип (2014). «Мультиагентная платформа Q-Learning для достижения справедливости в адаптивной потоковой передаче HTTP». Симпозиум IEEE по сетевым операциям и управлению (NOMS) 2014 г. стр. 1–9. дои : 10.1109/NOMS.2014.6838245 . ISBN 978-1-4799-0913-1 . S2CID 16573649 .

[5] Хоссфельд, Тобиас; Скорин-Капов, Лия; Хеггард, Пол Э.; Варела, Мартин (11 октября 2016 г.). «Определение справедливости QoE в общих системах» . Коммуникационные письма IEEE . 21 (1): 184–187. дои : 10.1109/LCOMM.2016.2616342 . HDL : 11250/2433049 . S2CID 23790117 . Хобфельд, Тобиас; Скорин-Капов, Лия; Хеггард, Пол Э.; Варела, Мартин (19 сентября 2017 г.). «Определение справедливости QoE в общих системах» . Препринт Зенода . дои : 10.5281/zenodo.893343 .

[6] Индекс справедливости пропускной способности: объяснение

[causal-7] Галхотра, Сайньям; Брун, Юрий; Мелиу, Александра (2017). «Тестирование справедливости: тестирование программного обеспечения на предмет дискриминации». Материалы 11-го совместного совещания по основам программной инженерии 2017 г. стр. 498–510. arXiv : 1709.03221 . дои : 10.1145/3106237.3106277 . ISBN 9781450351058 . S2CID 6324652 .

[8] Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]