Пропорционально-справедливое планирование

Алгоритм планирования сети передачи данных

Пропорционально-справедливое планирование — это алгоритм планирования, основанный на компромиссе . Он основан на поддержании баланса между двумя конкурирующими интересами: попытка максимизировать общую пропускную способность сети (проводной или нет) и в то же время предоставить всем пользователям хотя бы минимальный уровень обслуживания. Это делается путем назначения каждому потоку данных скорости передачи данных или приоритета планирования (в зависимости от реализации), который обратно пропорционален его ожидаемому потреблению ресурсов. ^{[1] [2]}

Взвешенная справедливая организация очереди

Пропорционально справедливое планирование может быть достигнуто с помощью взвешенной справедливой очереди (WFQ), путем установки весов планирования для потока данных на , где стоимость — это количество потребляемых ресурсов на бит данных. Например: ${\displaystyle i}$ ${\displaystyle w_{i}=1/c_{i}}$ ${\displaystyle c_{i}}$

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

Приоритезация пользователей

Другой способ планирования передачи данных, который приводит к аналогичным результатам, — использование коэффициентов приоритетности. ^[3] Здесь мы планируем канал для станции, которая имеет максимум функции приоритета:

${\displaystyle P={\frac {T^{\alpha }}{R^{\beta }}}}$

• ${\displaystyle T}$обозначает скорость передачи данных, потенциально достижимую для станции в текущем временном интервале.
• ${\displaystyle R}$— это историческая средняя скорость передачи данных этой станции.
• ${\displaystyle \alpha }$и настроить «справедливость» планировщика. ${\displaystyle \beta }$

Путем корректировки и в приведенной выше формуле мы можем скорректировать баланс между обслуживанием лучших мобильных телефонов (тех, которые находятся в лучших условиях канала) чаще и обслуживанием дорогостоящих мобильных телефонов достаточно часто, чтобы они имели приемлемый уровень производительности. ${\displaystyle \alpha }$ ${\displaystyle \beta }$

В крайнем случае ( и ) планировщик действует по принципу «пакетного» циклического перебора и обслуживает все мобильные устройства по одному (но не одинаково часто по времени), не обращая внимания на потребление ресурсов, и таким образом, что каждый пользователь получает одинаковый объем данных. Планировщик ( и ) можно назвать «планировщиком максимальной справедливости» (например, для предоставления равного доступа голосовым пользователям). Если и , то планировщик всегда будет обслуживать мобильные устройства с наилучшими условиями канала. Это максимизирует пропускную способность канала, в то время как станции с низкими условиями не обслуживаются вообще. Планировщик ( и ) можно назвать планировщиком «максимальной скорости». ^[2] Использование и даст алгоритм пропорционального справедливого планирования, используемый в сетях 3G. ^[3] Планировщик ( и ) можно реализовать, предоставляя одинаковое количество времени и спектра для каждого пользователя, независимо от желаемого размера пакета, качества канала и используемой скорости передачи данных (MCS). Пропорциональный справедливый ( и ) планировщик можно назвать «планировщиком равных усилий» или «планировщиком Round Robin по времени/спектру». ${\displaystyle \alpha =0}$ ${\displaystyle \beta =1}$ ${\displaystyle \alpha =0}$ ${\displaystyle \beta =1}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =0}$ ${\displaystyle T}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =0}$ ${\displaystyle \alpha \approx 1}$ ${\displaystyle \beta \approx 1}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =1}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =1}$

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

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

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

Ссылки

1. Кушнер, Х. Дж.; Уайтинг, П. А. (июль 2004 г.), «Сходимость алгоритмов пропорционально-справедливого распределения при общих условиях», IEEE Transactions on Wireless Communications , 3 (4): 1250–1259, CiteSeerX  10.1.1.8.6408 , doi : 10.1109/TWC.2004.830826, S2CID  6780351.
2. Guowang Miao , Jens Zander, Ki Won Sung и Ben Slimane, Основы мобильных сетей передачи данных, Cambridge University Press, ISBN 1107143217 , 2016. 
3. Цзи Ян; Чжан Ифань; Ван Ин; Чжан Пин (2004), «Механизм обновления средней скорости в пропорциональном справедливом планировщике для HDR», IEEE Global Telecommunications Conference, 2004. GLOBECOM '04 , т. 6, стр. 3464–3466, doi :10.1109/GLOCOM.2004.1379010, ISBN 0-7803-8794-5

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

• Эндрюс, Мэтью (сентябрь 2004 г.), «Неустойчивость алгоритма пропорционального справедливого планирования для HDR», IEEE Transactions on Wireless Communications , 3 (5): 1422–1426, CiteSeerX  10.1.1.73.4092 , doi :10.1109/TWC.2004.833419, S2CID  34595035.
• Эндрюс, Мэтью ; Кумаран, К.; Раманан, К.; Стояр, А.; Уиттинг, Фил (февраль 2001 г.), «Обеспечение качества обслуживания по общему беспроводному каналу связи», IEEE Communications , 39 (2): 150–154, doi :10.1109/35.900644.
• Parruca, Donald; Grysla, Marius; Gortzen, Simon; Gross, James (2013), «Аналитическая модель пропорционального справедливого планирования в сетях OFDMA/LTE с ограниченным уровнем помех», 78-я конференция IEEE по транспортным технологиям 2013 г. (осень VTC) , стр. 1–7, arXiv : 1303.1778 , Bibcode : 2013arXiv1303.1778P, doi : 10.1109/VTCFall.2013.6692106, ISBN 978-1-4673-6187-3, S2CID  8236469