В сетях связи , мультиплексировании и разделении ограниченных ресурсов считается, что максимально-минимальная справедливость достигается путем распределения, если и только если распределение осуществимо, а попытка увеличить распределение любого участника обязательно приводит к уменьшению распределения какого-либо другого участника с равным или меньшим распределением.
В статистическом мультиплексировании с наилучшими усилиями часто используется политика планирования «первым пришел, первым обслужен » (FCFS). Преимущество принципа максимальной-минимальной справедливости перед FCFS заключается в том, что он приводит к формированию трафика , что означает, что плохо себя ведущий поток, состоящий из больших пакетов данных или всплесков множества пакетов, накажет только себя, а не другие потоки. Следовательно, в некоторой степени удается избежать перегрузки сети .
Справедливая очередь является примером алгоритма максимально-минимального справедливого планирования пакетов для статистического мультиплексирования и сетей с наилучшими усилиями, поскольку она дает приоритет планирования пользователям, которые достигли самой низкой скорости передачи данных с момента их активации. В случае пакетов данных одинакового размера циклическое планирование является максимально-минимальным справедливым.
Как правило, политики совместного использования ресурсов, характеризующиеся низким уровнем справедливости (см. меры справедливости ), обеспечивают высокую среднюю пропускную способность, но низкую стабильность качества обслуживания, что означает, что достигнутое качество обслуживания меняется со временем в зависимости от поведения других пользователей. Если эта нестабильность серьезна, это может привести к недовольству пользователей, которые выберут другой, более стабильный сервис связи.
Максимально-минимальное справедливое распределение ресурсов приводит к более высокой средней пропускной способности (или спектральной эффективности системы в беспроводных сетях) и лучшему использованию ресурсов, чем политика равного распределения ресурсов, экономящая работу. [ необходимо дополнительное объяснение ] При равном распределении некоторые потоки данных могут не иметь возможности использовать свою «справедливую долю» ресурсов. Политика равного распределения не позволит потоку данных получать больше ресурсов, чем любой другой поток, и использовать свободные ресурсы в сети.
С другой стороны, справедливость max-min обеспечивает более низкую среднюю пропускную способность, чем управление ресурсами максимальной пропускной способности , где наименее дорогим потокам назначается вся емкость, которую они могут использовать, и для самых дорогих потоков может не остаться никакой емкости. В беспроводной сети дорогой пользователь обычно является мобильной станцией на большом расстоянии от базовой станции, подверженной высокому затуханию сигнала. Однако политика максимальной пропускной способности приведет к истощению дорогих потоков и может привести к меньшему количеству «счастливых клиентов».
Компромиссом между максимальной-минимальной справедливостью и планированием максимальной пропускной способности является пропорциональная справедливость , где ресурсы делятся с целью достижения одинаковой стоимости для каждого пользователя или минимизации максимальной стоимости за единицу, которую достигает поток данных. Дорогостоящие потоки данных достигают более низкого качества обслуживания, чем другие при пропорциональной справедливости, но не страдают от голодания. Максимально-минимальная справедливость приводит к более стабильному качеству обслуживания и, следовательно, возможно, большему количеству «довольных клиентов».
Максимально-минимальная справедливость в сетях связи предполагает, что ресурсы (пропускные способности каналов связи) распределяются по потокам заранее, в отличие от сетей с максимальными усилиями .
Рассмотрим потоки данных i , иногда называемые пользователями или источниками . Каждый поток данных имеет определенный начальный узел, узел назначения и желаемую скорость передачи данных. Поток на своем пути через сеть может быть разделен между «параллельными» связями в схеме балансировки нагрузки .
Вектор распределения x, i -я координата которого представляет собой распределение для потока i , т.е. скорость, с которой пользователю i разрешено отправлять данные.
Распределение ставки x является «максимально-минимально справедливым» тогда и только тогда, когда увеличение любой ставки в пределах области допустимых распределений должно происходить за счет уменьшения некоторой уже меньшей ставки. В зависимости от задачи, максимально-минимально справедливое распределение может существовать или не существовать. Однако, если оно существует, оно уникально.
Название «макс-мин» происходит от идеи, что это скорость меньших (или минимальных) потоков, которая делается максимально возможной (максимизируется) алгоритмом. Поэтому мы даем более высокий относительный приоритет малым потокам. Только когда поток запрашивает потребление больше, чем C/N (пропускная способность канала/количество потоков), он подвергается риску ограничения своей пропускной способности алгоритмом.
Узким местом для потока данных i является полностью загруженное ( насыщенное ) соединение , и из всех потоков, разделяющих это соединение, поток данных i достигает общей максимальной скорости передачи данных. [1] Обратите внимание, что это определение существенно отличается от общепринятого значения узкого места . Также обратите внимание, что это определение не запрещает разделять одно узкое место между несколькими потоками.
Распределение скорости передачи данных является максимально-минимальным справедливым тогда и только тогда, когда поток данных между любыми двумя узлами имеет хотя бы одно узкое место.
Если ресурсы распределены заранее в узлах сети, можно получить максимально-минимальную справедливость, используя алгоритм прогрессивного заполнения. Вы начинаете со всех скоростей, равных 0, и увеличиваете все скорости вместе в одном темпе, пока не будет достигнут один или несколько пределов пропускной способности ссылок. Скорости для источников, которые используют эти ссылки, больше не увеличиваются, и вы продолжаете увеличивать скорости для других источников. Все остановленные источники имеют узкое место. Это происходит потому, что они используют насыщенное соединение, а все другие источники, использующие насыщенное соединение, останавливаются в то же время или были остановлены раньше, таким образом, имеют меньшую или равную скорость. Алгоритм продолжается до тех пор, пока увеличение становится невозможным. Наконец, когда алгоритм завершается, все источники были остановлены в какой-то момент и, таким образом, имеют узкое место. Это распределение является максимально-минимальной справедливостью.