Введение
Алгоритм планирования сети данных проблема распределения ресурсов Пропорциональное справедливое планирование - это алгоритм планирования, основанный на компромиссе. Она основана на поддержании баланса между двумя конкурирующими интересами: попытками максимизировать общую пропускную способность сети (проводные или нет), в то же время позволяя всем пользователям, по крайней мере, минимальный уровень обслуживания. Это делается путем присвоения каждому потоку данных скорости передачи данных или приоритета планирования (в зависимости от реализации), который обратно пропорционален его ожидаемому потреблению ресурсов.
the resource allocation problem
Proportional fair scheduling is a compromise based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize the total throughput of the network (wired or not) while at the same time allowing all users at least a minimal level of service. This is done by assigning each data flow a data rate or a scheduling priority (depending on the implementation) that is inversely proportional to its anticipated resource consumption.
Взвешенная очередь
Пропорционально справедливое планирование может быть достигнуто с помощью взвешенного справедливого очереди (WFQ), путем установления весов планирования для потока данных на , где стоимость является количеством потребляемых ресурсов на бит данных. Например: в сетях сотовой связи с расширенным спектром CDMA стоимость может быть необходимой энергией на бит в управлении мощностью передачи (повышенный уровень помех). В беспроводной связи с адаптацией линии затраты могут быть временем, требуемым для передачи определенного количества битов с использованием схемы модуляции и кодирования ошибок, необходимой для этого. Примером этого являются сети EVDO, где сообщаемая SNR используется в качестве основного фактора расходов. В беспроводных сетях с быстрым динамическим распределением каналов стоимость может быть количеством близлежащих базовых станций, которые не могут использовать один и тот же частотный канал одновременно, чтобы избежать помех на одном канале.
In CDMA spread spectrum cellular networks, the cost may be the required energy per bit in the transmit power control (the increased interference level). In wireless communication with link adaptation, the cost may be the required time to transmit a certain number of bits using the modulation and error coding scheme that this required. An example of this is EVDO networks, where reported SNR is used as the primary costing factor. In wireless networks with fast Dynamic Channel Allocation, the cost may be the number of nearby base station sites that can not use the same frequency channel simultaneously, in view to avoid co channel interference.
Приоритетность пользователей
Другой способ планирования передачи данных, который приводит к аналогичным результатам, - это использование коэффициентов приоритета. Здесь мы планируем канал для станции, которая имеет максимальную функцию приоритета: обозначает скорость передачи данных, потенциально достижимую для станции в текущем временном интервале. является исторической средней скоростью передачи данных данной станции. и настроить "справедливость" расписания. С помощью корректировки и в формуле выше, мы можем скорректировать баланс между обслуживанием лучших мобильных устройств (те, которые находятся в лучших условиях канала) чаще и обслуживанием дорогих мобильных устройств достаточно часто, чтобы они имели приемлемый уровень производительности. В крайнем случае (и) планировщик действует в "пакетном" круглом режиме и обслуживает все мобильные телефоны один за другим (но не одинаково часто во времени), без учета потребления ресурсов, и таким образом, чтобы каждый пользователь получал одинаковое количество данных. Планировщик (и) может быть назван "планировщиком максимальной справедливости" (например, для обеспечения равного использования голосовых пользователей). Если и тогда планировщик всегда будет обслуживать мобильный с лучшими условиями канала. Это позволит максимизировать пропускную способность канала, в то время как станции с низким не обслуживаются вообще. Планировщик (и) может называться планировщиком "максимальной ставки". Используя и будет давать пропорциональный алгоритм справедливого планирования, используемый в сетях 3G. Планировщик (и) может быть реализован путем предоставления одинакового количества времени и спектра для каждого пользователя, независимо от желаемого размера пакетов, качества канала и используемой скорости передачи данных (MCS). Пропорциональный справедливый (и) планировщик может называться "планировщиком равных усилий" или "планировщиком круглого стола по времени/спектру". Этот метод может быть дополнительно параметризирован с помощью "константы памяти", которая определяет период времени, за который используется скорость передачи данных станции при расчете функции приоритета. Более высокая константа обычно улучшает пропускную способность за счет снижения краткосрочной справедливости.
denotes the data rate potentially achievable for the station in the present time slot. is the historical average data rate of this station. and tune the "fairness" of the scheduler. By adjusting and in the formula above, we are able to adjust the balance between serving the best mobiles (the ones in the best channel conditions) more often and serving the costly mobiles often enough that they have an acceptable level of performance. In the extreme case ( and ) the scheduler acts in a "packet" round robin fashion and serves all mobiles one after the other (but not equally often in time), with no regard for resource consumption, and such that each user gets the same amount of data. The ( and ) scheduler could be called "maximum fairness scheduler" (to be used to provide equal throughout to voice users for example). If and then the scheduler will always serve the mobile with the best channel conditions. This will maximize the throughput of the channel while stations with low are not served at all. The ( and ) scheduler could be called "max rate" scheduler. Using and will yield the proportional fair scheduling algorithm used in 3G networks. The ( and ) scheduler could be implemented by providing the same amount of time & spectrum for each user, irrespective of the desired packet size, channel quality and data rate (MCS) used. The proportional fair ( and ) scheduler could be called "equal effort scheduler" or "time/spectrum Round Robin scheduler". This technique can be further parametrized by using a "memory constant" that determines the period of time over which the station data rate used in calculating the priority function is averaged. A larger constant generally improves throughput at the expense of reduced short term fairness.