Меры или метрики справедливости используются в проектировании сети, чтобы определить, получают ли пользователи или приложения справедливую долю системных ресурсов. Есть несколько математических и концептуальных определений справедливости.
Справедливость TCP
Механизмы управления перегрузкой для новых сетевых протоколов передачи или одноранговых приложений должны хорошо взаимодействовать с TCP . Справедливость TCP требует, чтобы новый протокол получал не большую долю сети, чем сопоставимый поток TCP. Это важно, поскольку TCP является доминирующим транспортным протоколом в Интернете, и если новые протоколы приобретают несправедливую пропускную способность, они, как правило, вызывают такие проблемы, как коллапс из-за перегрузки . Так было с первыми версиями потокового протокола RealMedia : он был основан на UDP и широко блокировался брандмауэрами организаций, пока не была разработана версия на основе TCP. Несправедливость пропускной способности TCP по сравнению с WiFi является серьезной проблемой и требует дальнейшего изучения. [1]
Индекс справедливости джайна
Уравнение Раджа Джайна ,
оценивает справедливость набора ценностей там, где есть пользователи, пропускная способность для th соединение, и - выборочный коэффициент вариации . Результат колеблется от(в худшем случае) до 1 (в лучшем случае) и максимально, когда все пользователи получают одинаковое распределение. Этот индекс когда пользователи в равной степени разделяют ресурс, а остальные пользователи получают нулевое распределение.
Этот показатель определяет недостаточно используемые каналы и не слишком чувствителен к нетипичным схемам сетевого потока. [2]
Для достижения заданного уровня справедливости , один из приближенных методов - позволить , где
и A - произвольный коэффициент, обычно используемый для нормализации. Это дает распределение со справедливостью, близкой к F , и затем распределение может быть уточнено, чтобы стать еще ближе. Обратите внимание, что это также позволяет установить приоритет распределения, посколькуs будут отсортированы.
Точный метод - позволить , где решает
- .
Простой способ расчета использовать метод Ньютона на, который сходится последовательно и довольно быстро.
Оба этих метода обычно дают нецелочисленные выделения, и иногда требуются целочисленные выделения. Это можно сделать, используя один из вышеуказанных методов распределения, округляя каждое выделение до ближайшего целого числа (), а затем итеративно выделяя одну единицу пользователю, с вероятностью, что пользователь k получит ее, пропорциональна .
Макс-мин честность
Говорят, что максимальная-минимальная справедливость достигается распределением тогда и только тогда, когда распределение возможно и попытка увеличить распределение любого потока обязательно приводит к уменьшению распределения некоторого другого потока с равным или меньшим распределением. Справедливое распределение max-min достигается, когда полоса пропускания распределяется одинаково и с бесконечно малыми приращениями для всех потоков, пока один из них не будет удовлетворен, затем среди остальных потоков и так далее, пока все потоки не будут удовлетворены или полоса пропускания не будет исчерпана.
В беспроводных сетях пакетной радиосвязи , достаточно совместно используемая спектральная эффективность (FSSE) может использоваться как комбинированная мера справедливости и эффективности использования спектра системы . Спектральная эффективность системы - это совокупная пропускная способность в сети, деленная на используемую полосу пропускания радиосвязи в герцах. FSSE - это часть спектральной эффективности системы, которая распределяется поровну между всеми активными пользователями (по крайней мере, с одним отложенным пакетом данных в очереди или при передаче). В случае планирования голодания FSSE будет нулевым в течение определенных интервалов времени. В случае одинаково совместно используемых ресурсов, FSSE будет равняться спектральной эффективности системы. Для достижения максимальной и минимальной справедливости FSSE следует максимизировать.
FSSE особенно полезен при анализе схем расширенного управления радиоресурсами (RRM), например, адаптивного планирования каналов , для сотовых сетей с оптимальной службой пакетных данных. В такой системе может возникнуть соблазн оптимизировать эффективность использования спектра (т.е. пропускную способность). Однако это может привести к тому, что «дорогие» пользователи будут планировать нехватку ресурсов на большом расстоянии от точки доступа, когда другой активный пользователь окажется ближе к той же или соседней точке доступа. Таким образом, пользователи будут испытывать нестабильное обслуживание, что, возможно, приведет к уменьшению количества довольных клиентов. Оптимизация FSSE приводит к компромиссу между справедливостью (особенно во избежание потери расписания) и достижением высокой спектральной эффективности.
Если стоимость каждого пользователя известна в терминах потребляемых ресурсов на один передаваемый информационный бит, показатель FSSE может быть переопределен, чтобы отразить пропорциональную справедливость . В пропорционально справедливой системе эта «пропорционально справедливая совместно используемая эффективность использования спектра» (или «справедливо распределенная стоимость радиоресурсов») максимизируется. Эта политика менее справедлива, поскольку «дорогостоящие» пользователи получают меньшую пропускную способность, чем другие, но при этом избегают планирования голодания.
QoE справедливость
Идея справедливости QoE заключается в количественной оценке справедливости среди пользователей с учетом качества восприятия (QoE), воспринимаемого конечным пользователем. Это особенно важно при управлении сетью, где операторы хотят, чтобы их пользователи были в достаточной степени удовлетворены (т. Е. С высоким QoE) справедливым образом, см. Управление QoE . Было предложено несколько подходов для обеспечения справедливости QoE в масштабе сети, особенно для адаптивной потоковой передачи видео. [3] [4]
В отличие от показателей, связанных с сетью, таких как пропускная способность, QoE обычно не измеряется на шкале отношений . Следовательно, меры справедливости, такие как индекс справедливости Джайна, не могут быть применены, поскольку шкала измерения должна быть шкалой отношений с четко определенной нулевой точкой (см. Примеры неправильного использования коэффициентов вариации). QoE можно измерить по интервальным шкалам . Типичным примером является 5-балльная шкала среднего мнения (MOS) , где 1 означает самое низкое качество, а 5 - самое высокое качество. Хотя коэффициент вариации не имеет смысла, стандартное отклонение обеспечивает меру разброса QoE среди пользователей.
Hossfeld et al. предложили индекс справедливости QoE, который учитывает нижнюю границу и верхняя граница рейтинговой шкалы. [5]
Индекс справедливости QoE имеет некоторые желаемые свойства, такие как независимость от масштаба и метрики. Единица измерения значения не имеет. Любое линейное преобразование значений QoE не меняет значения индекса справедливости. Индекс справедливости ограничен интерваломгде 1 указывает на идеальную справедливость QoE - все пользователи получают одинаковое качество. 0 указывает на полную несправедливость, например, 50% пользователей испытывают наивысшее QoE. и 50% испытывают самое низкое QoE .
Индексы справедливости на основе продуктов
Индексы справедливости на основе продуктов основаны на общей формулировке справедливости:
- ,
где - произвольная функция преобразования. Для чтобы быть допустимой функцией преобразования: для . Результирующий индекс, таким образом, имеет значение от 0 до 1. Поскольку индекс справедливости Джайна считается чрезмерно чувствительным в нетипичных условиях, справедливость на основе продукта может быть определена произвольно для получения желаемой чувствительности.
Распределение, которое имеет справедливость F в соответствии с приведенной выше формулировкой, может быть задано как
- ,
где - любая неубывающая функция с . часто удобно принять g за что-то вроде. Предполагая, что f увеличивается и а также , это дает минимальное отношение к максимальному примерно
- .
Индекс справедливости на основе линейного продукта и выглядит так:
- .
Замечено, что очень чувствительна к небольшим значениям . Например дает
Индекс справедливости G
Индекс справедливости G в основном используется операторами связи в контексте распределения полосы пропускания. GИндекс справедливости -го порядка масштабирует доли индекса справедливости на основе продукта с помощью усиленного синусоидального преобразования. :
- ,
где . Первый квадрант синусоидальной волны используется как функция отображения для увеличения дробей. Таким образом, чувствительность справедливости на основе продукта снижается для значений, близких к, в то время как индекс по-прежнему выводит значение от 0 до 1.
По сравнению с индексом справедливости Джайна, индекс справедливости G дает меньшие значения, он более чувствителен к потенциальному несправедливому распределению полосы пропускания и может стремиться к нулю. В контексте сетей последний является преимуществом над индексом справедливости Джайна, когда несколько значений в наборе опускаются до низкого уровня. Кроме того, индекс справедливости Jain является считаются средним пользователем восприятием справедливости [6] , тогда как индекс справедливости G ориентирован больше на равенстве в пределах группы. Например для мы получили а также .
Индекс справедливости Босера
В то время как индекс справедливости G раздувает дроби ближе к , индекс справедливости Босера увеличивает дроби ближе к нулю. функция преобразования -го порядка дает индекс справедливости:
- .
Индексы справедливости, основанные на линейных продуктах, являются частным случаем Босера, где .
Причинная справедливость
Причинная справедливость измеряет частоту, с которой два почти идентичных пользователя или приложения, которые различаются только набором характеристик, в отношении которых распределение ресурсов должно быть справедливым, получают одинаковое отношение. [7]
Другие показатели
Были определены несколько других показателей, например справедливость наихудшего случая. [8]
Заметки
- ^ Похрел, Шива Радж; Панда, Манодж; Vu, Hai L .; Мандже, Мишель (2016). «Производительность TCP по Wi-Fi: совместное влияние потерь буфера и канала». Транзакции IEEE по мобильным вычислениям . 15 (5): 1279–1291. DOI : 10,1109 / TMC.2015.2456883 .
- ^ Jain, R .; Чиу, DM; Хаве, В. (1984). «Количественная мера справедливости и дискриминации при распределении ресурсов в общих компьютерных системах» (PDF) . Отчет об исследовании DEC TR-301 .
- ^ Георгопулос, Панайотис; Эльхатиб, Йехиа; Бродбент, Мэтью; Му, Му; Гонка, Николай (2013). «Обеспечение справедливости QoE в масштабе сети с использованием адаптивной потоковой передачи видео с поддержкой openflow». Материалы семинара ACM SIGCOMM 2013 года по будущим человеко-ориентированным мультимедийным сетям .
- ^ Петрангели, Стефано; Клейс, Максим; Латре, Стивен; Фамэй, Джерун; Де Турк, Филип (2014). «Многоагентная основа на основе Q-Learning для достижения справедливости в HTTP Adaptive Streaming». Симпозиум IEEE по эксплуатации и управлению сетью (NOMS) .
- ^ Хоссфельд, Тобиас; Скорин-Капов, Леа; Heegaard, Poul E .; Варела, Мартин (11 октября 2016 г.). «Определение справедливости QoE в общих системах» . Письма связи IEEE . 21 (1): 184–187. DOI : 10,1109 / LCOMM.2016.2616342 .Хобфельд, Тобиас; Скорин-Капов, Леа; Heegaard, Poul E .; Варела, Мартин (19 сентября 2017 г.). «Определение справедливости QoE в общих системах» . Препринт Зенодо . DOI : 10.5281 / zenodo.893343 .
- ^ http://www.cse.wustl.edu/~jain/atmf/ftp/af_fair.pdf
- ^ Галхотра, Сайньям; Брун, Юрий; Мелиу, Александра (2017). Проверка на честность: программное обеспечение для тестирования на дискриминацию . Материалы 11-го совместного заседания Европейской конференции по программной инженерии и Симпозиума ACM SIGSOFT по основам программной инженерии (ESEC / FSE) . С. 498–510. arXiv : 1709.03221 . DOI : 10.1145 / 3106237.3106277 . ISBN 9781450351058.
- ^ Беннетт, JCR; Хуэй Чжан (1996). «WF / sup 2 / Q: Справедливая организация очередей со справедливым взвешиванием в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . 1 . п. 120. DOI : 10,1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.
дальнейшее чтение
- 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 года.