Моделирование работы методов управления очередями маршрутизатора в сетях TCP/IP

Неравномерный рост скоростей каналов передачи данных неизбежно приводит к возникновению «узких» мест в телекоммуникационной сети и соответственно к возникновению перегрузок, особенно при подключении сетей доступа к транспортной сети. Предметом исследования в данной статье является маршрутизатор, одной из задач которого является предотвращение перегрузок в канале. Именно маршрутизатор с непосредственно подключенным каналом передачи данных обладает необходимой информацией о возникновении перегрузки в канале или состоянии, которое может повлечь за собой ее наличие. Маршрутизатор оценивает текущую степень загруженности выходной очереди и текущий рост или спад интенсивности нагрузки, и сообщает TCP передатчикам о необходимости снижения окна перегрузки. Для явного уведомления о перегрузке, путем соответствующей маркировки проходящих пакетов, используется протокол ECN (Explicit Congestion Notification). Если отсутствует поддержка ECN, то при угрозе перегрузки вместо маркировки пакеты могут сбрасываться в случайном порядке. В противном случае переполнение очереди приведет к множественным потерям пакетов и последующим периодическим чередованиям моментов переполнения и опустошения буфера маршрутизатора.

В условиях конкуренции за полосу пропускания большого числа одновременных TCP сессий, принадлежащих разным приложениям с различным поведением, на входе агрегирующего порта маршрутизатора возникает трафик со сложной нелинейной динамикой. В данной статье рассматривается случай, когда конкурирующие соединения имеют одинаковый класс обслуживания и попадают в одну очередь, сравниваются различные современные методы управления очередями и проверяется их влияние на параметры качества передачи данных путем имитационного моделирования в симуляторе ns-2.

Наиболее часто в сетях передачи данных используется пассивный механизм сброса излишка пакетов данных при переполнении очереди (Drop Tail). При передаче TCP трафика этот механизм приводит к возникновению явления глобальной синхронизации, когда при переполнении буфера маршрутизатора сбрасываются все приходящие пакеты, и все TCP-передатчики одновременно уменьшают размер TCP-окна, а потом синхронно его увеличивают, вызывая новую перегрузку. Кроме того, сброс пакетов в данном случае происходит уже в момент перегрузки, и не предпринимается активных действий для её предотвращения. Однако, в современных маршрутизаторах наиболее распространены методы активного управления очередью (AQM), заблаговременно предотвращающие переполнение буфера маршрутизатора.

В данной статье рассматривается механизм раннего обнаружения перегрузок RED (Random Early Detection) [1,2,3], в случайном порядке сбрасывающий пакеты с вероятностью, линейно увеличивающейся с ростом усредненной длины очереди, и его адаптивная модификация ARED (Adaptive RED) [4].

Функции вероятности сброса/маркировки p для исследуемых алгоритмов описываются следующим образом (q – длина очереди (пакет), C – пропускная способность канала (пакет/с)):

а) Drop Tail

де q_max – максимально допустимый размер очереди.

б) RED

RED случайно отбрасывает или маркирует поступающие пакеты, когда среднее значение длины очереди avg превышает минимальный порог min_th. Вероятность отказа растет с увеличением средней длины очереди вплоть до значения максимальной вероятности сброса пакета max_p. Когда средняя длина очереди достигает значение максимального порога max_th, все пакеты получают отказ. Т.к. avg варьируется от min_th до max_th, вероятность сброса/маркировки изменяется линейно от 0 до max_p:

Финальная вероятность сброса пакетов p_a медленно увеличивается с ростом числа пакетов count, которые поступили с момента сброса последнего пакета:

Средняя длина очереди, которая рассчитывается каждый раз по поступлению нового пакета, определяется следующим образом:

где w_q – весовой коэффициент очереди, avg – предыдущее значение средней длины очереди, q – мгновенное значение длины очереди.

Таким образом, функция вероятности сброса пакета принимает следующий вид:

На рисунке 1 представлены вышеописанные функции алгоритмов:

Однако, недостатком RED является зависимость его поведения от установки фиксированных параметров, которые достаточно сложно подобрать, чтобы они адекватно соответствовали характеру поведения обрабатываемого трафика.

в) ARED

Для адаптивной подстройки параметров был предложен механизм ARED, который путем минимальных изменений исходного алгоритма, решает эту проблему, динамически изменяя max_p в пределах от 1-50% в зависимости от средней загруженности очереди по принципу AIMD:

где

Чтобы уменьшить необходимость настройки других параметров RED, они также рассчитываются автоматически. Определены следующие процедуры для max_th и w_q:

Имитационное моделирование проводилось с использованием NS-2. Для оценки влияния алгоритмов управления очередью, а именно Drop Tail, RED, ARED, на качество передачи в сети было проведено моделирование перегрузки в канале между двумя маршрутизаторами, через которые передавался мультисервисный трафик 2-х типов: длительные TCP-сессии, создаваемые 100 одновременными FTP приложениями; короткие TCP-сессии, создаваемые HTTP источниками.

Задержка в каналах передачи распределена по равномерному закону в интервале от 1 до 20 мс. Скорость канала между маршрутизаторами ограничена 10 Мбит/с. Использовалась реализация протокола TCP Reno.

Результаты моделирования представлены на следующих графиках (рис.2-4) и в табл. 1:

На основании полученных данных моделирования был проведен анализ исследуемых методов управления очередью, который позволяет утверждать, что использование в маршрутизаторах алгоритмов RED и ARED является более рациональным, чем Drop Tail, т.к. данные алгоритмы позволяют минимизировать дрожание задержки пакетов путем контроля среднего размера очереди, большую стабильность интенсивности трафика и его непредвзятое обслуживание в случае кратковременных всплесков. Также, ARED за счет адаптированной подстройки параметра max_p и автоматической настройки max_th и w_q поддерживает предсказуемое значение средней длины очереди и снижает чувствительность параметров RED, уменьшается вероятность превышения верхнего порога и вариативность задержки. За счет чего, соответственно, увеличивается возможный объем переданных данных. Однако остается вопрос выбора диапазона, в пределах которого будет удерживаться очередь, и который должен соответствовать компромиссу между коэффициентом использования и величиной задержки в канале связи.

Перечень ссылок

1. Floyd S., Jacobson V. Random Early Detection gateways for Congestion Avoidance / S. Floyd, V. Jacobson // IEEE/ACM Transactions on Networking. – August 1993. – Режим доступа: http://www.icir.org/floyd/...
2. Hollot C.V., Misra V., Towsley D., Gong Wei-Bo Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED / C.V. Hollot, V. Misra, D. Towsley, Wei-Bo Hong // Proceedings of ACM Sigcomm, Stockholm, Sweden. – August, 2000. – Режим доступа: http://dna-pubs.cs.columbia.edu...
3. Батыр С.С. Управление длиной очереди на пограничном маршрутизаторе участка сети Интернет / С.С. Батыр // Збірник наукових праць ДонІЗТ, № 30. – Донецьк, 2012. – c.71-79.
4. Floyd S., Gummadi R., Shenker S. Adaptive RED: An Algorithm for Increasing the Robustness of RED’s Active Queue Management / S. Floyd, R. Gummadi, S. Shenker // August 2001. – Режим доступа: http://www.icir.org/floyd/...