Дисциплины пропорционально-интегрального (PI) контроллера и расширенного PI Controller (PIE) очереди

Пропорциональный интегральный (ПИ) регулятор представляет собой алгоритм AQM. Он управляет очередью на выходном порту маршрутизатора. Он включает в себя основные функции, отсутствовавшие в RED. Пропорциональный интегральный (ПИ) регулятор был разработан для преодоления проблем КРАСНОГО. Он использует «мгновенную длину очереди» в качестве показателя перегрузки.

PI работает во время постановки в очередь точно так же, как алгоритм RED. Обратите внимание на этот момент и не путайте его с «входным портом» в архитектуре маршрутизатора. PI работает на «выходном порту», но во время «постановки в очередь» PI «не работает с прибытием каждого пакета, как это делает RED. RED работает с прибытием каждого пакета во время постановки в очередь. Но PI запускается один раз каждые 6 мс (иногда называется w). PI решает, следует ли входящий пакет поставить в очередь или отбросить после некоторых вычислений.

Работа ПИ-контроллера:

Алгоритм PI содержит следующие компоненты:

• Расчет текущей длины очереди, как и в алгоритме RED, PI сначала вычисляет текущую длину очереди и использует ее в качестве показателя перегрузки. Основываясь на текущей длине очереди, алгоритм сделает следующий шаг и решит, следует ли отбросить входящий пакет или перенаправить его на следующее устройство.
• Расчет вероятности отбрасывания: если вероятность отбрасывания превышает определенный порог, пакет будет отброшен, иначе он будет перенаправлен.
• Логика принятия решения, эта логика помогает решить, следует ли входящий пакет поставить в очередь или отбросить.

1. Как происходит расчет текущей длины очереди (PI)? В отличие от RED, который вызывает алгоритм каждый раз, когда приходит новый пакет. PI запускается через определенный частый интервал времени, это обозначается переменной w в оригинальном RFC PI. Каждые 'w' мс алгоритм PI извлекает информацию о текущей очереди.

2. Как происходит расчет вероятности падения (PI)? Вероятность падения рассчитывается, как показано в уравнении ниже:

=> drop_prob = a (cur_qlength – target) – b (old_qlength – target) + old_drop_prob

=> cur_qlength= current queue length calculated in above step.

=> target= target queue length, it is a fixed value.

=> old_qlength= old or previous queue length calculated last time PI was invoked.

=> old_drop_prob= it is old probability calculated last time PI was invoked. a and b are the constant weights associated. 

3. Как устроена логика принятия решений? После вычисления drop_prob PI использует следующую логику, чтобы решить, должен ли входящий пакет быть поставлен в очередь или отброшен:

=> if (drop_prob ≤ R) enqueue the incoming packet

=> else drop the incoming packet

=> where, R = uniformly distributed random  number generated between [0, 1]

=> Note: It is important that a well known random number generator is used to generate R. 

=> If the implementation of the random number generator is not correct, PI and PIE’s performance might get affected.

Усовершенствованный ПИ-контроллер:

Дисциплина очереди PI Controller Enhanced (PIE) предлагается в RFC 8033. Это популярный вариант PI Controller. PIE использует задержку очереди в качестве показателя перегрузки, как и CoDel. PIE реализован в ядре Linux с нуля командой NITK.

Как и алгоритм RED, PIE также работает во время постановки в очередь. Время постановки в очередь — это время, когда пакет поступает на выходной порт. Перед дальнейшей пересылкой пакет буферизуется на выходном порту. PIE работает на «выходном порту», но во время «постановки в очередь» PIE «не работает с прибытием каждого пакета, как это делает RED. PIE запускается один раз каждые 15 мс (переменное название t_update), он не запускается при поступлении каждого пакета, как RED. PIE решает, следует ли входящий пакет поставить в очередь или отбросить на основе некоторых вычислений.

Улучшена работа PI Controller:

Алгоритм PIE содержит следующие компоненты:

• Расчет мгновенной задержки очереди (PIE).
• Расчет вероятности падения.
• Логика принятия решений помогает решить, следует ли входящий пакет поставить в очередь или отбросить.

Алгоритм:

Расчет текущей задержки очереди (PIE). Существует два возможных подхода к вычислению текущей задержки в очереди. Оба метода упоминаются в исходном RFC 8033. Алгоритм PIE вызывается каждый период времени t_update. Как и RED, он не вызывается каждый раз, когда приходит новый пакет.

1. Для каждого 't_update' мс алгоритм PIE вычисляет задержку очереди. Два способа оценить текущую задержку в очереди (cur_qdelay):

=> Little’s Law  method is recommended as default in RFC 8033.

=> cur_qdelay = cur_qlength / avg_departure_rate Eq. (1)

=> current queue delay is calculated by dividing the current queue length by the average departure rate.

=> suppose current queue length is 20 packets, and avg departure rate is 5 packets/ms. then all the packets will be dequeued in 4 ms, that means a packet will be delayed by atmost 4 ms in the queue.

=> Using timestamps like CoDel, as shown in Eq. (2).  

=> cur_qdelay = dequeue_time – enqueue_time Eq. (2)

=> enqueue_time= the time when the packet entered in the queue.

=> dequeue_time= the time when the packet left the queue. the difference between these two times is the delay faced by currently leaving packet. This is more accurate way of calculating the current queue delay. 

=> Initially the researchers had implemented the first method. But later of Team from NITK proved that first method was inefficient and implemented the second method.

2. Расчет вероятности падения (PIE)

=> Drop probability is calculated as shown in the equation below:

=> drop_prob = a (cur_qdelay – target) + b (cur_qdelay – old_qdelay) Eq. (4) a and b are the fixed constants. There value can be changed manually.

=> cur_qdelay = current queue delay

=> target = it is the target value of the queue delay, its also fixed constant.

=> old_qdelay = it is the old value of the queue delay,calculated the last time PIE was invoked.

3. Логика принятия решений точно такая же, как и в PI Controller.

Дополнительные возможности в PIE:

PI и PIE являются усовершенствованиями алгоритма RED. Но у PIE больше возможностей, чем у PI Controller.

• Допуск на разрыв. PIE позволяет небольшим всплескам проходить без наказания, он не наказывает маленькие всплески. Когда 5-10 пакетов приходят вместе, он не наказывает этот небольшой пакет, отбрасывая некоторые пакеты, а безопасно пересылает их. Основное различие между CODEL и PIE заключается в том, что CODEL ожидает 100 мс, прежде чем перейти к фазе отбрасывания, тогда как PIE ждет 150 мс, прежде чем наказывать пакеты. Итак, если всплеск небольшой, он исчезнет через 150 мс.
• Автонастройка drop_prob. В реальной реализации существует много пар значений [a, b]. Глядя на текущее значение вероятности падения, мы можем определить значение a и b. Вот циклическая зависимость. [a, b] зависит от drop prob, а drop_prob зависит от [a, b].
• Позволяет избежать резкого роста drop_prob. Вероятность падения увеличивается медленно, как адаптивный КРАСНЫЙ. Он увеличивает drop_prob медленно, а не резко.
• Затухает drop_prob, когда очередь простаивает. Когда никакие пакеты не приходят, он затухает. КРАСНЫЙ не затухает drop_prob, когда очередь пуста. RED также не обновляет длину очереди и drop_prob, когда очередь пуста, но PIE обновляет qdelay и drop_prob, когда очередь пуста.
• Активация/деактивация PIE в зависимости от текущей длины очереди. PIE требует больше циклов процессора, больше вычислительной мощности. Поэтому, если PIE не требуется, когда размер очереди меньше порогового значения, деактивируйте PIE, когда он не нужен. Когда понадобится PIE, активируйте его, эта идея была рекомендована в оригинальном RFC. Но команда NITK обнаружила, что частое переключение режима PIE затруднительно, и поэтому не реализовала эту функцию в ядре Linux.

Другие варианты ИП:

Дисциплина очереди Flow Queue PIE (FQ-PIE). Он поддерживает отдельную очередь для каждого потока. Популярный вариант PIE реализован в ядре Linux. Другим вариантом является дисциплина очереди DOCSIS PIE, которая предлагается в RFC 8034. Вариант PIE был разработан для стандарта DOCSIS.