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

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

Справедливость TCP

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

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

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

${\ 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 i}$${\ displaystyle {\ widehat {c _ {\ rm {v}}}}}$${\ Displaystyle {\ tfrac {1} {п}}}$${\ displaystyle {\ tfrac {k} {n}}}$${\ displaystyle k}$${\ displaystyle nk}$

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

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

${\ Displaystyle \ альфа = {\ гидроразрыва {1-F + {\ sqrt {1-F}}} {F}}}$

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

Точный метод - позволить , где решает ${\ Displaystyle х_ {к} = А \ cdot е ^ {2 \ альфа к}}$${\ displaystyle \ alpha}$

${\ Displaystyle {\ гидроразрыва {\ tanh (п \ альфа)} {п \ tanh (\ alpha)}} = F}$.

Простой способ расчета заключается в использовании метода Ньютона на , сходящийся последовательно и довольно быстро. ${\ displaystyle \ alpha}$${\ Displaystyle \ пер \ влево ({\ гидроразрыва {\ tanh (п \ альфа) - \ tanh (\ альфа)} {(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 достигается, когда полоса пропускания распределяется одинаково и с бесконечно малыми приращениями для всех потоков, пока один из них не будет удовлетворен, затем среди остальных потоков и так далее, пока все потоки не будут удовлетворены или полоса пропускания не будет исчерпана.

Достаточно совместная эффективность использования спектра

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

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

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

QoE справедливость

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

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

Hossfeld et al. предложили индекс справедливости QoE, который учитывает нижнюю и верхнюю границы рейтинговой шкалы. ${\ 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 е (х) \ в [0,1]}$${\ Displaystyle 0 \ Leq х \ Leq 1}$

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

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

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

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

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

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

Замечено, что это очень чувствительно для малых значений . Например урожайность${\ Displaystyle {\ mathcal {L}} (\ mathbf {x})}$${\ Displaystyle х_ {я} / \ макс (\ mathbf {х})}$${\ Displaystyle \ mathbf {ч} = \ {20,10,5,1 \}}$${\ Displaystyle {\ mathcal {L}} (\ mathbf {h}) = 0,00625}$

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

Индекс справедливости G в основном используется операторами связи в контексте распределения полосы пропускания. Индекс справедливости G- го порядка масштабирует доли индекса справедливости на основе продукта с помощью усиленного синусоидального преобразования : ${\ displaystyle {\ mathcal {I}}}$${\ displaystyle k}$${\ Displaystyle е (х) = \ грех (х \ пи / 2) ^ {\ гидроразрыва {1} {к}}}$

${\ 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 к \ ин \ mathbb {R} ^ {+}}$${\ Displaystyle \ макс (\ mathbf {х})}$

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

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

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

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

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

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

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

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

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

Примечания

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

• Almeida, A .; Casetti, C .; Oueslati, S .; Авратченков К. и Йоханссон М. Таксономия контроля перегрузки (в документе D.WP.JR.2.1.1) EuroNGI, 2004
• Mo, J .; Уолранд, Дж. (2000). «Справедливое сквозное оконное управление перегрузкой» (PDF) . Транзакции IEEE / ACM в сети . 8 (5): 556–567. DOI : 10.1109 / 90.879343 . Архивировано из оригинального (PDF) 19 ноября 2012 года.