Date: Thu, 28 Mar 2002 14:32:01 +0300
From: Jen Linkova <jen@comp.chem.msu.su>
Newsgroups: fido7.ru.unix.bsd
Subject: FreeBSD dummynet: описание сущности поддерживамых очередей для QoS
>> RED - Random Early Detection
>> Если уровень перегрузки находится между двумя порогами, пакеты
>> отбрвсываются с линейно возврастающей вероятностю из диапазона от 0 до
>> конфигурируемой величины, который достигается при достижении второго порога.
> А это max_p (maximum probability?) и max_th.
>> Когда выше порога, все пакеты отбрасываются.
> И в чем особенность gentle RED, тоже неясно.
AFAIK, при gentle RED ситуация выглядит так:
если перегрузки лежит в интервале от min_th до max_th,
то пакеты отбрасываются с линейно возрастающей от 0 до max_p вероятностью.
Когда перегрузка превышает max_th, но не превышет 2*max_th, пакеты отбрасываются
не все (как в случае RED), а с линейно возрастающей от max_p до 1 вероятностью.
Все пакеты отбрасываются только после превышения перегрузки канала значения 2*max_th.
From: Jen Linkova <jen@comp.chem.msu.su>
>> Все пакеты отбрасываются только после превышения перегрузки канала
>> значения 2*max_th.
> А по сути получается то же самое. Только max_th=2*max_th.
Hу здрасте...Во-первых, для _заданных min_th, max_th - совсем
не одно и то же, не правда ли ;)
Во-вторых, функции в обоих случаях линейны, но если max_p != 0.5 -
то у них будут разные производные....
А вот что видно из ip_dummynet.c:
если длина очереди > max_th, то в случае gred вероятность отбрасывания пакета
вычисляется как
p_b = c_3 * avg - c_4
где c_3 = (1 - max_p) / max_th
c_4 = 1 - 2 * max_p
в случае просто RED пакет отбрасывается.
При загрузке очереди, большей min_th, но меньшей max_th,
функция вероятности одинакова и выглядит след. образом:
p_b = c_1 *avg - c_2
где c_1 = max_p / (max_th - min_th),
c_2 = max_p * min_th / (max_th - min_th)
From: Jen Linkova <jen@comp.chem.msu.su>
>>> Спасибо. А как все-таки считается этот параметр, "перегрузка"?
>> Бррр...'перегрузка' в данном контексте означает среднюю длину
>> очереди (average queue size). Считать его надо исходя из твоей
>> ситуации.
> Как именно выполняется усреднение? Интегралы/суммы можно сильно
> по-разному считать.
Тут уже приводили очень полезную URL ( кстати, намекну, что
google тоже оказывается весьма полезен ;-)))) ) -
http://www.icir.org/floyd/papers/red/red.html
Так вот, там приводится след. алгоритм:
В момент прихода пакета:
if (очередь не пуста)
avg = (1 - w_q)*avg + w_q*q
else
m = f(time - q_time)
avg = (1 - w_q)^m * avg;
где:
фиксированный параметр:
w_q - вес очереди
переменные:
avg -средний размер очереди
q_time - "start of queue idle time" - по-английски оно как-то
лучше звучит, чем все мои варианты перевода ;-))
q - размер очереди
f() - линейная функий от времени
Такой метод вычисления позволяет сглаживать всплески трафика -
для сравнения там на одном графике приводятся и изменение размера
очереди q, и усредненного размера очереди (avg) от времени.
В той же статье есть выкладки на тему значений w_q - я уж не
буду их тут пересказывать, ладно ? А то там все довольно
внятно написано, и к тому же вдруг я что-то не так поняла -
введу еще кого в заблуждение ;-))
From: Jen Linkova <jen@comp.chem.msu.su>
> Как именно выполняется усреднение? Интегралы/суммы можно сильно
> по-разному считать.
Вот, я решила довести уточнение деталей до логического
конца и пошла читать /usr/src/sys/netinet/ip_dummynet.c
Так вот там написано буквально следущее:
* RED algorithm
*
* RED calculates the average queue size (avg) using a low-pass filter
* with an exponential weighted (w_q) moving average:
* avg <- (1-w_q) * avg + w_q * q_size
* where q_size is the queue length (measured in bytes or * packets).
*
* If q_size == 0, we compute the idle time for the link, and set
* avg = (1 - w_q)^(idle/s)
* where s is the time needed for transmitting a medium-sized packet.
*
Что вполне согласуется с формулами, процитированными мной в предыдущем
постинге ;-)
Когда несколько потоков данных делят одну трубу и конкурируют,
обычно получается "кто раньше встал - того и тапки".
Weightet Fair Queue (WF2Q) позволяет задать каждому потоку свой "вес",
пропорционально которому потоку выдается часть трубы. При одинаковых
весах получится разделение поровну, отсюда "fair" (честный).
Если один из потоков прекращается, остальные делят трубу уже между
собой, каждый получит больший кусок.
В этом алгоритме существует два порога уровня перегрузки. Когда
уровеньперегрузки ниже первого порога, то пакеты не отбрасываются.
Если уровень перегрузки находится между двумя порогами, пакеты отбрвсываются с
линейно возврастающей вероятностю из диапазона от 0 до конфигурируемой
величины, который достигается при достижении второго порога.
Когда выше порога, все пакеты отбрасываются.
В качестве показателя перегрузки используется вычисляемое среднее значение
длины очереди пакетов, принадлежащей к определенной сессии TCP.
Использование усредненного, а не мгновенного значения очереди позволяет
отделить кратковременные перегрузки, которые мог быть нормально обработаны
устройством и сетью, от длительных перегрузок, которые могут утопить сеть.
465 Прочтений • [FreeBSD dummynet: описание сущности поддерживамых очередей для QoS (qos shaper limit traffic bsd dummynet)] [08.05.2012] [Комментариев: 0]
Vova
