BC/NW 2011; №2 (19):4

BC/NW 2011; №2 (19):4.2

МЕТОДЫ АКТИВНОГО УПРАВЛЕНИЯ ОЧЕРЕДЯМИ МАРШРУТИЗАТОРОВ

Масленников А.Г., amasl2048@gmail.com

(Московский технический университет связи и информатики)

Неравномерный рост скоростей каналов передачи данных неизбежно приводит к возникновению «узких» мест в телекоммуникационной сети и соответственно к возникновению перегрузок, особенно при подключении сетей доступа к транспортной сети. Традиционные протоколы управления очередями и предотвращения перегрузок не справляются с управлением трафиком со сложной динамикой, высокой пачечностью и нелинейностью изменения нагрузки, что приводит к возникновению перегрузок и появлению глобальной синхронизации TCP потоков. Это в свою очередь уменьшает эффективную скорость передачи данных и ухудшает параметры качества, такие как процент потерянных пакетов, задержки и вариации задержек. В данной работе сравниваются различные современные методы управления очередями (RED, Adaptive RED, PI, REM, AVQ, Fuzzy Logic) и проверяется их влияние на параметры качества передачи данных путем имитационного моделирования.

Рис. 1. Поля Differentiated services и ECN в заголовке IP

Рис. 2. Новое определение байтов 13 и 14 в заголовке TCP

Поле ECN в заголовке IP используется для установки маркеров:

- маркер ECT (ECN-capable transport): значения 01 или 10 - используется передатчиком для информирования промежуточных маршрутизаторов о поддержке ECN;

- маркер CE (congestion experienced): значение 11 - используется промежуточным маршрутизатором для информирования приемника о перегрузке.

Промежуточный маршрутизатор получив IP пакет с маркером ECT, может в случае перегрузки установить в пакете маркер CE и отправить его дальше, вместо сброса пакета. Приемник, получив пакет с маркером CE, уведомляет TCP-передатчик о перегрузке, установив в отправленном обратно TCP сегменте бит CWR, а TCP-приемник, в свою очередь, получив такой сегмент, снижает размер TCP-окна в 2 раза, таким образом, уменьшая количество передаваемых сегментов. Сокращение окна TCP-передатчик подтверждает установкой бита ECN в TCP заголовке. Схема работы метода показана на рисунке 3.

Рис. 3. Схема работы механизма явного уведомления о перегрузке ECN

Таким образом, при наступлении перегрузки нагрузку на сеть можно уменьшить без потери при этом TCP сегментов. Поддержка ECN включена в ядро операционной системы Linux, а также поддерживается последними версиями ОС Windows.

Метод случайного раннего обнаружения (RED) и адаптивный RED

Механизм RED оценивает среднее значение очереди путем вычисления взвешенного скользящего среднего по формуле:

, (1)

где q - текущее значение длины очереди,

w - весовой коэффициент с рекомендованным значением 0,002.

Оценка среднего значения длины очереди в период отсутствия пакетов равна:

(2)

Вероятность маркировки/сброса пакетов линейно изменяется в интервале от 0 до max_p по формуле:

, (3)

где min_th — минимальный порог среднего значения очереди, до которого не происходит сброса, а max_th — максимальный порог, после которого сбрасываются все пакеты.

Реальная вероятность сброса пакетов вычисляется на основе счетчика поступивших пакетов с момента последнего сброса:

(4)

Рис. 4. Зависимость вероятности сброса пакета от средней длины очереди для протокола RED

Одним из недостатков RED также является крайняя зависимость поведения от установки фиксированных параметров. Для адаптивной подстройки параметров одним из авторов RED был предложен механизм Adaptive RED [3], способный динамически изменять max_p в зависимости от загрузки очереди и автоматически рассчитывающий значение max_th и весовой коэффициент w по формуле:

, (5)

где С — полоса пропускания канала в пакетах в секунду.

Метод пропорционально-интегрального контроллера (PI)

Пропорционально-интегральный контроллер PI (Proportional-Integral) [4] является классическим регулятором с обратной связью, используемым в системах автоматического управления. Работа контроллера основывается на вычислении ошибки между текущей длиной очереди q(t) и заданной длинной q_ref_:

(6)

Управляющий сигнал u(t), изменяющий вероятность сброса, вычисляется как сумма трех значений: первое слагаемое пропорционально текущей ошибки e(t), второе слагаемое пропорционально интегралу ошибки (для устранения постоянной составляющей) и последнее слагаемое - дифференциалу ошибки (для противодействия будущим отклонениям):

, (7),

где K_x — соответствующие коэффициенты пропорциональности.

На практике для управления очередью используется упрощенная дискретная формула вычисления вероятности сброса без дифференциального слагаемого:

(8)

Рекомендованные коэффициенты пропорциональности a и b фиксированы и равны 1,822E-5 и 1,81E-5 соответственно.

Метод случайного экспоненциального маркирования (REM)

В методе случайного экспоненциального маркирования REM (Random Exponential Marking) [5] используется мера перегрузки p, называемая «ценой», и в момент времени kT вычисляемая по формуле:

, (9)

где c — пропускная способность канала (пакетов за интервал времени),

q(kT) — текущая длина очереди,

x(kT) — скорость поступления пакетов,

α и γ — константы больше нуля,

Т — интервал времени измерений,

k — номер интервала.

Вероятность сброса/маркировки пакетов рассчитывается по формуле:

, (10)

где φ — константа больше единицы.

Метод адаптивной виртуальной очереди (AVQ)

Авторы метода адаптивной виртуальной очереди AVQ (Adaptive Virtual Queue) [6] предложили оригинальную идею организовать виртуальную очередь такой же длины, как и реальная очередь. При поступлении новых пакетов в реальную очередь пакеты также помещаются в виртуальную очередь (пакеты не на самом деле помещаются в виртуальную очередь, а только отслеживаются). В отличие от реальной очереди, пакеты из виртуальной очереди обслуживаются виртуальным каналом с полосой пропускания C_V меньшей, чем полоса пропускания реального канала C_R . Соответственно пакеты в виртуальной очереди будут накапливаться быстрее, и в момент времени, когда виртуальная очередь переполнится, принимается решение о заблаговременном сбросе или маркировке пакета в реальной очереди. Таким образом, можно избежать переполнения реальной очереди и изменяя полосу пропускания виртуального канала C_V регулировать коэффициент использования реального канала передачи данных. Изменять полосу пропускания виртуального канала предлагается по следующей формуле для производной по времени C_V:

, (11)

где – λ скорость поступления пакетов,

γ – заданный коэффициент использования канала,

α - сглаживающий параметр.

То есть изменение виртуальной емкости канала пропорционально реальной емкости канала умноженной на желаемый коэффициент использования и обратно-пропорционально скорости поступления пакетов.

Метод нечеткого регулятора (FLC)

В управлении нелинейными системами со сложной динамикой себя хорошо зарекомендовал контроллер на базе нечеткой логики FLC (Fuzzy Logic Controller). Контроллером FLC решения об изменении текущего значение вероятности сброса/маркировки пакета P_drop, принимаются на основе входных переменных: ошибки текущего значения длины очереди Q_error и его изменении d_error за время измерения, и соответствующего набора правил использующего экспертные оценки. Общая структура нечеткого регулятора FLC приведена на рисунке 5.

Рис. 5. Структура нечеткого регулятора FLC

Для входных переменных вычисляется значение функции принадлежности μ нечеткому множеству, т.е. степень уверенности в том, что входная переменная принадлежит к нечеткой (лингвистической) переменной. Функции принадлежности выбираются так, что сумма значений всех функции от входной переменной равна единице. На рисунке 6 приведен пример треугольных функций принадлежности и процесса вычисления степени принадлежности нечетким множествам. Для входной переменной х принявшей текущее значение х* степень принадлежности нечеткому множеству «Среднее» будет 0,75, а множеству «Большое» будет соответственно 0,25.

Рис. 6. Пример функций принадлежности для трех нечетких множеств «Малое», «Среднее» и «Большое»

Одним из широко распространенных алгоритмов нечеткого вывода является алгоритм Мамдани (Mamdani). Нечеткий вывод делается на основе набора правил - вычисляется значение истинности для предпосылки каждого правила (операция minimum). Все нечеткие множества, полученные из правил агрегируются вместе, и формируется единственное нечеткое множество C (операция maximum). Приведение к четкости выполняется обычно с помощью дискретного метода «центра тяжести»:

, (12)

где - дискретное значение выходной переменной из m значений, а - функция принадлежности агрегированного множества C.

Рис. 7. Графическая интерпретация нечеткого вывода в программном обеспечении XFuzzy 3.0

В механизме Fuzzy Explicit Marking (FEM) [9] в качестве входных параметров нечеткого контроллера использовалось значение ошибки очереди (разница между текущим значением и заданным) и значение предыдущей измеренной ошибки. В отличие от механизма FEM, в данном исследовании в качестве второго входного параметра контроллера FLC использовалось отношение количества полученных пакетов к максимально возможному переданному количеству за интервал измерения (что должно точнее обнаруживать перегрузку), а также вычислять вероятность сброса как приращение к предыдущему значению вероятности.

Имитационное моделирование

Имитационное моделирование проводилось с использованием программного комплекса NS-2 [11]. Для оценки параметров качества при работе разных механизмов управления очередью было проведено моделирование перегрузки в канале между двумя маршрутизаторами, через которые передавался мультисервисный трафик 3-х типов:

- длительные по времени TCP сессии создавались 100 одновременными FTP приложениями;

- короткие по времени TCP сессии создавались HTTP приложениями с интенсивностью 50 новых соединений в секунду;

- трафик UDP с постоянной скоростью 128 Кбит/с полный дуплекс для создания фона.

Рис. 8. Схема сети для имитационного моделирования

Скорость в канале между маршрутизаторами ограничена 15Мбит/сек, задержка 120 мсек, максимальный размер очереди 500 пакетов. В моделировании использовалась реализация NewReno протокола TCP с включенной функцией явного уведомления о перегрузке ECN. В случае UDP трафика пакеты сбрасывались в момент перегрузки. Для моделирования динамики трафика использовался следующий сценарий каждые 100 секунд: в начальный момент времени все 100 FTP источников начинают передачу, в момент времени 40 секунд 50 FTP источников останавливает передачу, а в момент времени 70 секунд снова возобновляет передачу. Далее данный сценарий повторялся ещё пять раз. Итого общее время моделирования составило 600 секунд. FTP источники имеют различное время задержки в канале до маршрутизатора, оно равномерно распределено на интервале от 1 до 9 мсек.

В данном моделировании периодичность измерений контроллера FLC была установлена 6 мс, а максимальная величина изменения вероятности сброса 8E-5 за время измерения. Для механизма RED установлен минимальный и максимальный порог сброса 200 и 400 пакетов соответственно, а максимальная вероятность сброса 1/30.

Результаты моделирования

На рисунке 9 приведены результаты моделирования заполнения очереди для метода FLC для заданной длины в 300 пакетов.

Рис. 9. Изменение длины очереди при использовании метода FLC

Для оценки средней длины очереди и среднеквадратичного отклонения использовались 5 последовательных измерений по 100 секунд. Первый 100-секундный интервал отбрасывался как аномальные измерения. Результаты расчетов средних значений с доверительными интервалами по статистике Стьюдента t(α=0,95; k=4) приведены на рисунке 10:

Рис. 10. Средняя длина очереди и среднеквадратичное отклонение с доверительными интервалами для 5 повторяющихся экспериментов для различных методов

По стабильности средних значений можно сделать вывод о стационарном характере процесса изменения длины очереди. Значения параметров качества, рассчитанные за 600 секунд моделирования, приведены в таблицах 1 и 2:

Таблица 1. Значения параметров канала с перегрузкой для заданной длины очереди 300 пакетов в зависимости от метода обслуживания очереди.

Метод	Размер очереди в пакетах, среднее/СКО	Потери пакетов, %	Коэффициент использования
FLC	306/92	0,55	0,999
FEM	283/53	0,46	0,999
RED	273/72	0,28	0,998
A-RED	281/135	0,41	0,997
PI	305/105	0,33	0,997
REM	296/87	0,15	0,998
DropTail	449/65	2,79	0,999

Таблица 2. Значение параметров качества для различного трафика в зависимости от метода обслуживания очереди.

Метод	Трафик FTP		Трафик CBR/UDP		Трафик HTTP
	Потери пакетов, %	Средняя скорость, Мбит/с	Потери пакетов, %	Задержка/джиттер, мсек	Потери пакетов, %	Время сессий: среднее/СКО, сек	Средняя скорость, Мбит/с
FLC	0,16	11,7	5,8	227/6	1,5	1,59/3,5	3,15
FEM	0,03	11,7	5,6	265/5,8	1,4	1,58/3,4	3,21
RED	0,12	11,7	3,1	260/5,9	0,63	1,44/3,3	3,15
A-RED	0,2	11,7	3,3	265/5,7	0,89	1,48/3,5	3,16
PI	0,17	11,7	2,8	277/5,2	0,71	1,51/3,5	3,16
REM	0,16	11,7	0,13	272/5,3	0,11	1,41/3,6	3,15
DropTail	2,52	11,7	2,9	348/5,4	3,5	1,89/3,8	3,28

Заключение

Результаты показывают, что при использовании механизма DropTail значительные потери из-за переполнения буфера приходятся на короткие HTTP соединения, а при использовании активных методов управления TCP соединения имеют незначительные потери. Сброс пакетов в основном приходится на пакеты протокола UDP, который не имеет механизмов контроля передачи. Механизм REM допускает наименьшие общие потери. Из исследованных механизмов FEM демонстрирует самую стабильную очередь (наименьшее среднеквадратичное отклонение, СКО). Механизм FLC, менее стабилен, чем FEM, и требуется дальнейшая работа над оптимизацией его параметров.

Литература

1. Кучерявый Е.А., Управление трафиком и качество обслуживания в сети Интернет. - СПб. Наука и Техника, 2004.

2. Floyd, S., and Jacobson, V., Random Early Detection gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413.

3. Floyd S., Gummadi R., and Shenker S., Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management, August 2001.

4. Hollot C.V., Misra V., Towsley D. and Gong W.B., Analysis and Design of Controllers for AQM Routers Supporting TCP Flows, IEEE Transactions on Automatic Control, June 2002, pp. 945-959.

5. Athuraliya, S., Low, S.H., Li, V.H., Qinghe Yin, REM: active queue management, IEEE Networking Magazine 15 (3) (2001) p. 48-53.

6. Srisankar S. Kunniyur, R. Srikant, An Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management, IEEE/ACM Transactions on Networking (TON), Volume 12, Issue 2, April 2004

7. May M., Bolot J., Diot C., Lyles B., Reasons not to deploy RED, IWQoS '99, Seventh International Workshop on Quality of service, 1999.

8. Fengyuan R., Yong R., Xiumin S., Design of fuzzy logic controller for active queue management, Computer Communications 25 (2002) p. 874-883.

9. Chrysostomou C., Pitsillides A., Sekercioglu Y.A., Fuzzy explicit marking: A unified congestion controller for Best-Effort and Diff-Serv networks, Computer Networks 53 (2009) p. 650-667

10. Ramakrishnan K., Floyd S., Black D., The Addition of Explicit Congestion Notification (ECN) to IP, RFC-3168, Sep. 2001.

11. The Network Simulator, NS-2, http://www.isi.edu/nsnam/ns/