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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Алмейда, А.; Касетти, К.; Уэслати, С.; Авратенков, К. и Йоханссон, М. Таксономия управления перегрузками (в отчете №: D.WP.JR.2.1.1) ^{[ постоянная мертвая ссылка ‍ ]} EuroNGI, 2004
• Mo, J.; Walrand, J. (2000). "Справедливое сквозное управление перегрузкой на основе окон" (PDF) . IEEE/ACM Transactions on Networking . 8 (5): 556– 567. doi :10.1109/90.879343. Архивировано из оригинала (PDF) 2012-11-19.