Макс-мин честность - Max-min fairness

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

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

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

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

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

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

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

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

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

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

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

Вектор распределения Икс чей я-я координата - это выделение для потока я, то есть скорость, с которой пользователь я разрешено передавать данные.

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

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

Узкие ссылки

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

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

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

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

Смотрите также

• Мера справедливости
• Планирование в многозадачных операционных системах.

Рекомендации

внешняя ссылка

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