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

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

При с максимальными усилиями статистическом мультиплексировании ( FCFS в порядке очереди часто используется политика планирования ). Преимущество максимальной и минимальной справедливости перед FCFS заключается в том, что это приводит к формированию трафика , а это означает, что поток с плохим поведением, состоящий из больших пакетов данных или пакетов из множества пакетов, наказывает только себя, а не другие потоки. перегрузки сети Таким образом, в некоторой степени удается избежать .

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

Сравнение с другими политиками совместного использования ресурсов

Как правило, политики совместного использования ресурсов, характеризующиеся низким уровнем справедливости (см. меры справедливости ), обеспечивают высокую среднюю пропускную способность, но низкую стабильность качества обслуживания, а это означает, что достигнутое качество обслуживания меняется во времени в зависимости от поведения других пользователей. Если эта нестабильность серьезна, это может привести к недовольству пользователей, которые выберут другую, более стабильную службу связи.

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

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

Компромисс между максимальной и минимальной справедливостью и планированием максимальной пропускной способности — это пропорциональная справедливость , при которой ресурсы делятся с целью достижения одинаковой стоимости для каждого пользователя или минимизации максимальной стоимости на единицу, которую достигает поток данных. Дорогостоящие потоки данных обеспечивают более низкое качество обслуживания, чем другие, при пропорциональной справедливости, но не страдают от истощения. Максимально-минимальная справедливость приводит к более стабильному качеству обслуживания и, следовательно,, возможно, к большему количеству «счастливых клиентов».

Предварительное распределение максимальной и минимальной пропускной способности справедливого канала

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

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

Вектор распределения x, -я координата которого i является распределением для потока i , т.е. скоростью, с которой пользователю i разрешено отправлять данные.

Распределение ставки x является «максимально-минимальным справедливым» тогда и только тогда, когда увеличение любой ставки в пределах области возможных распределений должно происходить за счет снижения какой-либо уже меньшей ставки. В зависимости от проблемы максимально-минимальное справедливое распределение может существовать, а может и не существовать. Однако если он существует, то он уникален.

Название «макс-мин» происходит от идеи, что именно скорость меньших (или минимальных) потоков увеличивается с помощью алгоритма (максимизируется). Следовательно, мы уделяем более высокий относительный приоритет небольшим потокам. Только когда поток запрашивает потребление большего, чем C/N (пропускная способность канала/количество потоков), существует риск ограничения пропускной способности алгоритмом.

Узкие места

Узким местом для потока данных i является канал, который полностью используется ( насыщен ), и из всех потоков, разделяющих этот канал, поток данных i достигает общей максимальной скорости передачи данных. Обратите внимание, что это определение существенно отличается от общепринятого значения узкого места . Также обратите внимание, что это определение не запрещает совместное использование одного узкого канала несколькими потоками.

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

Алгоритм прогрессивного заполнения

Если ресурсы распределяются заранее в узлах сети, максимальная и минимальная справедливость может быть достигнута с помощью алгоритма прогрессивного заполнения. Вы начинаете со всех ставок, равных 0, и увеличиваете все ставки вместе с одинаковой скоростью, пока не будет достигнуто одно или несколько ограничений пропускной способности канала. Ставки для источников, использующих эти ссылки, больше не повышаются, а вы продолжаете повышать ставки для других источников. Все источники, которые остановлены, имеют узкое место. Это связано с тем, что они используют насыщенную ссылку, а все другие источники, использующие насыщенную ссылку, останавливаются одновременно или останавливались раньше, поэтому имеют меньшую или равную скорость. Алгоритм продолжается до тех пор, пока невозможно увеличить. Наконец, когда алгоритм завершает работу, все источники в какой-то момент были остановлены и, таким образом, имеют узкое место. Это распределение максимально справедливо.

См. также

• Мера справедливости
• Планирование в многозадачных операционных системах
• Правило эгалитарного социального выбора – выбор между альтернативами по принципу максимума-минима.
• Справедливость доминирующих ресурсов - обобщение максимальной и минимальной справедливости на несколько ресурсов.

Внешние ссылки

• Алгоритм справедливой доли макс-мин