автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическая модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока

004609311

На правах рукописи

Королькова Анна Владиславовна

Математическая модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока

05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

з о СЕН 7070

Москва — 2010

004609311

Работа выполнена на кафедре систем телекоммуникаций Российского университета дружбы народов

Научный руководитель:

кандидат физико-математических наук, доцент Д. С. Кулябов Официальные оппоненты:

доктор физико-математических наук, профессор О. В. Дружинина доктор физико-математических наук, профессор Е. Ю. Щетинин Ведущая организация:

Лаборатория информационных технологий Объединённого института ядерных исследований (ЛИТ ОИЯИ)

Защита состоится «15» октября 2010 г. в 15 ч. 30 мин на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе д. 3, ауд. 110.

С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов по адресу: 117198, г. Москва, ул. Миклухо-Маклая, д. 6. (Отзывы на автореферат просьба направлять по указанному адресу.)

Автореферат разослан « У » сентября 2010 г.

Учёный секретарь диссертационного совета

М. В. Фомин

Общая характеристика работы

Диссертация посвящена построению и анализу математической модели процесса передачи трафика с регулируемой алгоритмом типа Random Early Detection (RED) динамической интенсивностью потока, в которой при некоторых значениях параметров алгоритма возникает автоколебательный режим.

Актуальность работы

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

В современных сетях передачи данных для регулирования интенсивности потока широко применяются механизмы управления перегрузкой, в частности, механизм Explicit Congestion Notification (ECN) — явное уведомление о перегруженности канала связи, — в совокупности с алгоритмами типа RED.

Алгоритм RED (и его многочисленные модификации) благодаря простоте своей реализации в сетевом оборудовании достаточно эффективен, но обладает рядом недостатков. В частности, при некоторых значениях параметров возникает устойчивый автоколебательный режим функционирования системы, что негативным образом сказывается на показателях качества обслуживания сети (пропускной способности, задержке передачи пакетов и т.д.). До енх пор нет чётких, обоснованных рекомендаций по выбору значений параметров RED, при которых система не входила бы в автоколебательный режим. Часто предлагается использовать предустановленные в сетевом оборудовании параметры или подстраивать их по результатам натурного эксперимента. Существующие на данный момент исследования в этой области направлены в основном на попытки уменьшения амплитуды оецплляций, но не на определение условий и области их возникновения.

На основании изложенной выше научной проблемы сформулированы следующие цель и задачи диссертации.

Цель диссертационной работы

Разработка математической модели, обеспечивающей обоснованный выбор

значений параметров алгоритма RED или его модификации с целью избежания

попадания в область возйикновения автоколебательного режима.

Задачи диссертационной работы

— разработка математической модели процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока;

— качественный анализ разработанной математической модели с целью изучения характера и устойчивости особых точек;

— разработка метода анализа эффекта возникновения автоколебаний в построенной модели с целью корректного выбора значений параметров алгоритмов типа RED для избежания попадания в область возникновения автоколебаний;

— получение стационарных характеристик разработанной модели.

Результаты, выносимые на защиту

1. Разработана математическая модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока.

2. Для предложенной модели проведён качественный анализ с помощью разработанного для вычислительного эксперимента комплекса программ. Показало, что модель имеет 2 положения равновесия — узел и предельный цикл, определяющие отсутствие или наличие автоколебательного режима соответственно, а также, что эти положения устойчивы.

3. Предложен новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика.

4. Получено стационарное распределение вероятностей состояний и вероятностные характеристики двумерного марковского процесса, соответствующего разработанной модели.

Научная новизна

1. Отличительной особенностью предложенной математической модели процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока является применение для описания динамических переменных модели аппарата стохастических дифференциальных уравнений с пуас-соиовскпм процессом и учёт по сравнению с жидкостной моделью из [1G, 17] дополнительных факторов, оказывающих влияние на возникновение автоколебательного режима.

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

3. Впервые предложен новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика.

4. Для нахождения стационарных характеристик двумерного марковского процесса, соответствующего разработанной в диссертации модели, в отличие от других известных работ [18,19] впервые построена вложенная цепь Маркова и детально учтены принципы функционирования протокола TCP-Reno (фазы избежания перегрузки и быстрого восстановления) и процесса регулирования состояния потока (потери по тайм-ауту и потери по функции сброса пакетов).

Методы исследования

В работе использовались методы теории нелинейных колебаний, теории стохастических дифференциальных уравнений, качественной теории дифференциальных уравнений, численные методы, а также методы теории случайных процессов.

Обоснованность и достоверность результатов

Обоснованность полученных результатов следует из того, что на всех этапах аналитического и численного решения поставленных задач использовались строгие и проверенные методы: методы качественного анализа (анализ фазовых и параметрических портретов), широко известные и хорошо себя зарекомендовав-

шпе численные методы Ньютона и Рунге-Кутта 4-го порядка, метод точечных отображений, метод вложенной цепи Маркова.

Достоверность полученных в диссертации результатов численного анализа подтверждается пх сравнением при одинаковых условиях проведения численного эксперимента с результатами имитационного моделирования на NS-2, полученными в работах [16,17].

Практическая значимость

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

— определение способов улучшения качества обслуживания в современных сетях передачи данных;

— качественный анализ математической модели с различными алгоритмами регулирования состояния потока с целью оценки нх эффективности функционирования;

— определение значений параметров алгоритма типа RED, при которых отсутствует автоколебательный режим с целью стабилизации работы системы;

— количественный анализ стационарных характеристик модели для оценки качества обслуживания в современных сетях передачи данных.

Апробация работы

Результаты, полученные в ходе выполнения работы, были представлены на:

— IX, XI п XII научных конференциях МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» — ИММ РАН» по математическому моделированию и информатике (Москва, 2006, 2008, 2009);

— LXII научной сессии РНТОРЭС им. Попова, посвящённой Дню радио (Москва, 2007);

— Международной научной конференции «Моделирование нелинейных процессов и систем» (Москва, «Станкин», 2008);

- The 8th WSEAS International Conference on APPLIED INFORMATICS and COMMUNICATIONS (AIC'08) (Rhodes, Greece, 2008);

- 52-ii научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (Москва, 2009);

- 16 и 17 международных конференциях «Математика. Компьютер. Образование» (г. Пущино, 2009; г. Дубна, январь 2010);

- XLV и XLVI Всероссийской конференции по проблемам математики, информатики, •физики и химии (Москва, 2009, апрель 2010);

- The 13-tli Workshop on Computer Algebra (г. Дубна, май 2010).

Публикации

По теме диссертации опубликовано 15 работ, из которых 4 (работы [1-4]) — в ведущих рецензируемых журналах и изданиях, определённых Высшей аттестационной комиссией.

Личный вклад автора

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

— по поставленным задачам определены методы исследований;

— проведено исследование и выявлены особенности алгоритма RED и его модификаций, для классификации определены общие признаки алгоритмов;

— построена улучшенная по сравнению с [16,17] модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока;

— разработан и реализован новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока па поведение TCP-подобного трафика;

— получено стационарное распределение и вероятностные характеристики соответствующего модели двумерного марковского процесса.

Структура и объем диссертации

Диссертация состоит из введения, трёх глав, заключения и списка литературы из 104 наименований. Диссертация содержит 115 страниц текста, 1 таблицу и 44 рисунка.

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

В первой главе рассмотрены алгоритмы регулирования состояния потока в сетях передачи данных.

В разделе 1.1 проведён обзор работ, посвящённых методам регулирования состояния потока в сетях передачи данных. Акцент сделан на исследованиях, анализирующих эффективность функционирования алгоритма RED и его многочисленных модификаций. Кроме того, сделан обзор публикаций, посвящённых задаче моделирования устойчивого состояния TCP-трафика при возникновении случайного сброса пакетов.

В разделе 1.2 проведено исследование и определены особенности алгоритма RED и его модификаций, выявлены общие признаки рассмотренных автором модификаций RED и построена их классификация, которая априори является частичной, поскольку применённый фасетный метод не задаёт полной таксономии предметной области.

Для иллюстрации построенной классификации в разделе 1.3 приведено описание наиболее характерных для каждого класса модифицированных алгоритмов RED и составлена сводная таблица.

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

В разделе 2.1 проводится построение модели. Описание рассматриваемой системы даётся в терминах теории массового обслуживания.

В системе узел состоит из управляющего по некоторому алгоритму семейства RED модуля и очереди конечной ёмкости R < оо. Скорость передачи пакетов в канале связи — С пакетов в единицу времени.

В случае TCP-Reno трафика на систему поступает групповой пуассоновский поток заявок (заявка соответствует TCP-пакету) II рода с динамической интен-

спвносгыо, зависящей or состояния системы. Число заявок в группе соответствует размеру TCP-Reno окна w(i) передачи в момент времени £, i > 0. Размер окна w(i) (интенсивность входящего потока) зависит от двух функций сброса пакетов в системе: Рто (t) ~ учитывает потерн, возникающие по тайм-ауту в момент времени i, t ^ 0, и р{д) — учитывает потери, возникающие при функционировании алгоритма типа RED в момент времени t, t ^ 0. Функция сброса p(q) зависит от значения экспоненциально взвешенной скользящей средней длины очереди q(t) в момент времени t, t ^ 0, для которого Определены пороговые значения gluill н glllllx.

Если в момент времени t поступления заявки прибор свободен, то заявка поступает на обслуживание и занимает прибор на всё время обслуживания, которое является случайной величиной с функцией распределения B(t) = I(t — 1), t Js 0,

Если в момент времени t поступления заявки прибор занят и 0 < q(t) ^ диии, то заявка занимает одно место в очереди и ожидает доступа к прибору (порядок выбора заявок из очереди на обслуживание First Call First Served (FCFS), первым пришёл — первым обслужи лея). Если в момент времени t поступления заявки прибор занят и qla-ш < q(t) ^ дшах, то может произойти потеря заявки согласно функции сброса p(q(t)), 0 < p(q{t)) ^ jw<. Если в момент времени t поступления заявки прибор занят и q(t) > Qniiix, то заявка теряется.

Интенсивность поступления заявок в систему соответствует размеру TCP-Reno окна в момент времени t и моделируется случайным марковским процессом (МП) {w(£)} = {w(t),t ^ 0} с пространством состояний W - {l,...,wumx} для некоторого \vllmx < оо. Число заявок в очереди в момент времени t моделируется случайным процессом {q(i)} = {q(t),t Js 0}. Таким образом, определён двумерный МП {\v(t),q(t)} ~ {\v(t),q(t),t > 0} с пространством состояний

По аналогии с работами [1G, 17] для математического описания динамических переменных w(t), q{t) и q{t) системы применён аппарат стохастических дифференциальных уравнений с пуассоновским процессом. В отличие от [1G, 17] в уравнении для TCP-окна учтено возникновение потерь пакетов по так называемому «тайм-ауту» (максимальное время, в течение которого ожидается подтверждение доставки пакета), а в уравнении для мгновенной длины очереди — возникновение сброса пакетов в следствие функционирования алгоритма типа RED. Также

1, х > 0, 0, х s£ 0,

— индикаторная функция.

= W х [0, Я].

в отличие от [16,17] с целью дальнейшего качественного исследования эффекта возникновения автоколебаний система СДУ сведена к автономной системе ОДУ:

+ I (w(i) - 1)

дн*)] 2

d£[w(Q] /(wlllilx - E[v(t)]) d t E[T(t)]

,(l-E[PTO(v(t .llifmt_T)] X (E[pm(q(t - r))}.+ E[pd(q(t - r))]) + + (1 - S[w(i)]) E [ProWt - г))] lpd(q(t ■

E[T(t - t)\

r))]

(1)

dE[q{t))

dt

I(R - E{q(t)])N^}] (1 - E[pd(q(tm ~ E[C(t)),

dE[q{t)} _ ln(l - wq)

E[q(t))

E[T(t)}

ln(l - Wq)

E[q(t)},

dt 5 5

описывающей моделируемую систему. Здесь T(t) вычисляется по формуле

Ф)

т =

Ть +

Ть,

car q{t)>0' C(t) = Sc' q{t)>c'

q(t)= 0, ■ W)> 9(0

где Tb — время на передачу и подтверждение приёма (Round Trip Time, RTT) одного пакета, q(i) — значение мгновенной длины очереди в момент времени t, t ^ 0, C(t) — интенсивность обслуженной нагрузки; p(q(t)) — функция сброса пакетов из окна w(t) в момент времени t ^ 0, состоящая из функции Pm(q(t)) маркировки пакета на сброс (механизм ECN) и собственно функции Pd{q{t)) сброса пакета; т ^ 0 — время оповещения источника о потере пакета; N — число поступающих в очередь потоков; 5 — время между поступлениями пакетов в систему;

wq = 1 — е_1/,с — параметр (весовой коэффициент) экспоненциально взвешенного

t

скользящего среднего, E[x(t)] = \ f x(t')dt' — усреднение функции x(t).

о

Весьма актуальна задача изучения характера изменения фазовых портретов системы в зависимости от её параметров или деформации. В процессе деформации могут возникнуть бифуркационные ситуации, прн которых качественно меняется фазовый портрет. Конечной целью качественного исследования является получение параметрического портрета, т.е. разбиения фазового пространства параметров на области, соответствующие топологически различным фазовым портретам.

Система (1) определяет разбиение фазового пространства на траектории, образующие при заданных значениях параметров фазовый портрет системы. Качественная картина фазового портрета определяется положениями равновесия (особыми точками п особыми траекториями). Положение равновесия, отвечающее стационарному режиму, представляет собой точку qs фазовой плоскости, в которой обращаются в ноль правые части системы (1). Действительные корни полученной таким образом нелинейной системы являются стационарными точками.

Для рассматриваемой модели возникновение автоколебаний обусловлено характером разрывов функции сброса p(q(t)), когда значение qs, вычисленное в рабочей области (<7шш,дшах), попадает на интервал безусловного сброса (p(q(t)) = 1). Предложен следующий метод определения области возникновения режима автоколебаний:

— зафиксировать п параметров процесса регулирования состояния потока;

— вычислить значения стационарной точки qs для свободных параметров;

— построить параметрический портрет системы (поверхность размерности п) в предположении, что участок безусловного сброса (p(q(t)) = 1) отсутствует;

— построить граничную поверхность размерности п — 1 (переход к области p(q(t)) = 1), разделяющую области с различным поведением системы.

Тогда области возникновения автоколебаний будет соответствовать область, лежащая выше граничной поверхности.

В разделе 2.2 рассмотрена стандартная жидкостная модель [18,19], которая описывает общий подход к моделированию потоков. В последующем разделе 2.3 этот подход применён с необходимыми уточнениями для нахождения стационарного распределения и вероятностных характеристик построенной в разделе 2.1 модели.

Система рассматривается в моменты тп,п = 1,2,... сразу после начала передачи первого сегмента из группы сегментов. Размер группы передаваемых сегментов соответствует текущему значению окна TCP-Reno. Тогда последовательность {Х„ = w(тп),п > 0} с начальным условием Хо = 1 на пространстве состояний W является цепью Маркова (ЦМ) для случайного процесса {w(i), i ^ 0}, вложенной по моментам сразу после начала передачи первого сегмента из n-ой группы сегментов.

Стационарные вероятности по ЦМ pi = lim Р{Хп = i},i £ W, соответствуют

TL—>00

стационарным вероятностям по процессу 7Гt = lim iTi(t) = lim P{v/(t) = г}.

Переходные вероятности pij = Р{Хп = j,Xn-1 = г}, i,j € Ж, n ^ 1 ЦМ {Хп,п ^ 0} в данном случае определяются в соответствии с принципами функционирования протокола TCP-Reno:

' Pii = l-{l-Pd)(l-PTo), Pi,i+1 = (1 — p<i)(l - Рто), P2,i = ра{ 1 - -Pro) + -Рто, Pi,l = Рто,

Pi.LfJ+i =Pd(1-pro), „ Pwm«,wt,ra = (1 - Pd){ 1 - Pro).

Pij

г = l,Wm,ix - 1,

i — 3, wmax,

i = 3, wmnx,

(2)

На фазе избежания перегрузок размер окна увеличивается на 1/w при получении каждого подтверждения, что соответствует переходу из г в состояние г + 1. В случае TD-потери, определяемой функцией pd, размер окна сокращается вдвое, что соответствует переходу из г в состояние |_§_1- При возникновении потери по тайм-ауту, определяемой функцией Рто, размер окна становится равным 1, что соответствует переходу пз г в состояние 1.

Стационарные вероятности pi, удовлетворяют системе уравнений равновесия:

Pi= Y1 i&w

г £ If.

(3)

По эргодической теореме для конечной ЦМ стационарные вероятности ЦМ определяются как единственное решение системы уравнений равновесия с условием нормировки Рг = 1.

iew

Замечание 1. Средний размер окна перегрузки может быть вычислен по формуле:

ЯМ = 2>4. (4)

Процесс {д(Ь)} = , 4 ^ 0}, определяющий изменение содержимого очереди системы, удовлетворяет дифференциальному уравнению

Aq(t) d t

max{sj,0}, q(t) = 0, Si, 0 < q(t) ^ R,

где функция s : i i-> Si := s(i) имеет вид:

+ - о,

Sl 4 - C(0 + (1 - Vd{q{t))), 0 < 9(0 < R. (6)

Замечание 2. При конкретном значении q(t) величины q(t), C(t), T(t) принимают конкретные числовые значения. Следовательно, правая часть (G) не зависит явно от времени i, a S; — скаляр, зависящий только от w(i) = г, г = 1,..., w„„lx.

Для двумерного МП (w(i),q,(i)} 5 {\v(t),q(t),t > 0} с пространством состояний = fx [0,й| определены функции Fi(y,t) = P{w(t) = i, q(t) < y|w(0),q(0)}, (i,y) e if, t ^ 0, причём Fi(0,t) = 0 для г e У/+ и P{w(t) 6 W-,q(t) = R} = 0, Fi(R—,t) = 7Ti(i), если г € W-, t > 0, У/С. = {¿6 У/^вг < 0}, У/4 = {t€ > 0}.

теорема 1. Стационарные вероятности Fi(y) удовлетворяют уравнению

с граничными условиями Fi(0) = 0, если г € Fi(R-) = Pi, если г € Ж., где pi определяются из (3), S = diag(si,..., Swm„), Si ф 0 для всех г 6 W определяются из (6), А = {aij), i,j G УР, — матрица интенсивностей случайного процесса {w(i),i ^ 0}, aij = dipij > 0 при i ф j, an := —at = — ay < oo,

f Pij(l - Ргг)"1, ¿¿J, Pij = < pij определяются из (2).

I 0, г = j,

Замечание 3. Средняя длина очереди может быть вычислена по формуле:

у=О i=l

В главе 3 проведён анализ построенной в главе 2 модели. В разделе 3.1 приведены примеры численного анализа модели при использовании для регулирования состояния потока трафика алгоритмов RED, GRED, DSRED, ARED. Решение системы (1) из раздела 2.1 было получено численно посредством метода Рунге-Кутта 4-го порядка при упрощающих предположениях

N = 1, Pm(q{t)) = 0, Pxo(w(i)) = min |l, ^y |. Для численного решения получившейся системы нелинейных уравнений использовался метод Ньютона. Изменяя дШщ в пределах [l,i£] и gmax в пределах [gmin, R], получен параметрический портрет для нескольких модификаций RED

Для алгоритма RED параметрический портрет (рис. 1) показывает наличие изменения структуры фазового портрета (рис. 2), на котором видно, что узел переходит в предельный цикл, т.е. имеет место бифуркация Андронова-Хопфа. [20], что подтверждается наличием для систем с рассматриваемым алгоритмом как стационарного поведения E[q\, так и релаксационных автоколебаний (рис. 3).

Стационарная точка

Рис. 1. Параметрический портрет для системы с RED

EMII1 12 T«—£s-i

100 80

RED, qmai = 75 — REO, qmax = 85

■■■ииаа^аггетзеэ»

40 20

100 120 140 160 180 200

Рис. 2. Фазовый портрет для системы с RED, 9mm = 20

Рис. 3. Поведение £%(t)], t > 0, для системы е RED, gmjn = 20

В разделе 3.2 проведён качественный анализ модели.

Качественное поведение модели проанализировано путём линеаризации системы (1) и исследования характера её собственных значений, являющихся корнями характеристического многочлена.

В автореферате приведён только случай для алгоритма RED.

Утверждение 1. Положение равновесия типа узел модели (1) асимптотически устойчиво по первому приближению.

Утверждение 1 следует из теоремы Ляпунова [20] и того факта, что все корпи характеристического уравнения линеаризованной системы имеют отрицательные действительные части (показано средствами компьютерной алгебры MAXIMA для случая алгоритма RED при упрощающих предположениях Рто = 0, p(q) = Pd(g), т = 0).

Для положения равновесия типа предельный цикл модели (1) с помощью метода точечных отображений Пуанкаре построена функция последования и диаграмма Ламерея, которая показала, что справедливо следующее утверждение.

Утверждение 2. Положение равновесия типа предельный цикл модели (1) ор-бнтально устойчиво.

ю

9 8 7 6

Ï 4 3 2 1 0

0123456789 10 s

Функция последования £= f(s) ~ Биссектриса s= s

Рис. 4. Диаграмма Ламерея для системы с PED, qm¡u = 20, gmax = 75

В разделе 3.3 проведена верификация построенной в диссертации модели. Сравнение проводилось с имитационной моделью на Network Simulator (NS-2), в которой имеется эталонная реализация алгоритмов RED, GRED, ARED, разработанная автором этих алгоритмов — С. Флойд.

Для оценивания адекватности был выбран параметр E[q(t)}, t Js 0. Для каждого алгоритма (RED, GRED, ARED) построены графики поведения E[q(t)] для математической модели с учетом и без учёта тайм-аута и график q(t) для NS-2. Анализ показал, что реализация математической модели с учётом тайм-аута более адекватна модели на NS-2 — соответствующие графики находятся на одном уровне. Следовательно, предположение о существенном влняшш этого параметра на поведение системы оказалось верным.

В Заключении перечислены основные результаты диссертации.

Основные выводы и результаты

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

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

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

4. Предложен новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика. Метод позволяет корректно выбрать значения параметров алгоритмов типа RED для избежания попадания в область возникновения автоколебаний.

5. Получено стационарное распределение вероятностей состояний и вероятностные характеристики двумерного марковского процесса, соответствующего разработанной модели, что позволяет оценить количественные характеристики модели.

6. Проведены численные эксперименты по моделированию и определению области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика. Верификация результатов моделирования показала, что разработанная модель, метод и комплекс программ позволяют определять область возникновения автоколебательного режима, корректно выбирать значения параметров алгоритмов типа RED для избежания попадания в область возникновения автоколебаний.

По материалам диссертации опубликованы следующие работы:

1. Королькова А. В. Метод расчета вероятности сброса пакетов в алгоритме RED // Вестник Российского университета дружбы народов, серия «Математика. Информатика. Физика». — 2007. - № 1-2. - С. 32-37.

2. Королькова А. В., Кулябов Д. С., Чернопванов А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия «Математика. Информатика. Физика». - 2009. - № 3. - С. 34-46.

3. Королькова А. В. Определение области возникновения автоколебаний в системах типа RED // Вестник РУДН. Серия «Математика. Информатика. Физика». - 2010. - № 1. - С. 110-112.

4. Королькова А. В., Кулябов Д. С. Математическая модель динамики поведения параметров систем типа RED // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2010. — № 2. — С. 54-64.

5. Королькова А. В., Кулябов Д. С. Реализация модели схемы управления трафиком в IP-сетях с предоставлением дифференцированных услуг с использованием модуля DiffServ пакета NS-2 // Сборник докладов. IX-я научная конференция МГТУ «Станкнн» и «Учебно-научного центра математического моделирования МГТУ «Станкнн» — ИММ РАН» по математическому моделированию и информатике. — М.: «ЯНУС-К», ИЦ ГОУ МГТУ «Станкнн», 2006. - С. 116-118.

6. Кулябов Д. С., Королькова А. В. Аналитическая модель для расчета вероятности сброса пакетов в алгоритме RED // Труды РНТОРЭС им. Попова. Серия: Научная сессия, посвященная Дню радио. — 2007. — Вып. LXII. — С. 233-234.

7. Кулябов Д. С., Королькова А. В. Инструментальные средства моделирования DiffServ // Фундаментальные физико-математические проблемы и моделирование технико-технологических систем. Ежегодный сборник научных трудов / под ред. Л. А. Уваровой. — М.: Янус-К, 2008. — Вып. 11. — С. 161-167.

8. Королькова А. В., Кз'лябов Д. С. Инструментальные средства моделирования DiffServ // Материалы XI научной конференции МГТУ «СТАНКИН» и «Учебно-научного центра математического моделирования МГТУ «СТАНКИН» — ИММ РАН» по математическому моделированию и информатике. Программа. Сборник докладов / под ред. О. А. Казакова. — М.: ИЦ ГОУ ВПО МГТУ «Станкнн», 2008. - С. 93-96.

9. Кулябов Д. С., Королькова А. В., Геворкян М. Н. Разработка модулей Click, реализующих алгоритмы активного управления очередью DSRED и SDRED // Международная научная конференция «Моделирование нелинейных процессов п систем». — М.: МГУП «Станкнн», 2008. — С. 181-182.

10. Kulyabov D., Korolkova A., Gevorkyan M. Development of Click modules: DSRED and SDRED algorithms // New Aspects of Applied Informatics and Com-

munications. Proceedings of the 8th WSEAS International Conference on APPLIED INFORMATICS and COMMUNICATIONS (AIC'08). — Rhodes, Greece: 2008. — Pp. 363-368.

11. Королькова А. В., Кулябов Д. С. Предварительная классификация алгоритмов семейства RED // Материалы XII научной конференции МГТУ «Стан-кин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и информатике: Программа. Сборник докладов / под ред. О. А. Казакова. — М.: ИЦ ГОУ ВПО МГТУ «Станкин», 2009. - С. 125-128.

12. Королькова А. В., Черноиванов А. И. Моделирование при помощи стохастических дифференциальных уравнений поведения TCP-трафика при взаимодействии с узлом, работающим по алгоритму RED. — М.: МФТИ, 2009. — Т. 1. - С. 130-133.

13. Королькова А. В., Черноиванов А. И. Использование стохастических дифференциальных уравнений для моделирования поведения TCP-трафика при взаимодействии с узлом, работающим по алгоритму RED // «Математика. Компьютер. Образование». Тезисы. — Дубна, 2010.

14. Королькова А. В., С. Кулябов Д. Определение области возникновения автоколебаний в системах типа RED // XLVI Всероссийская конференция по проблемам математики, информатики, физики и химии: Тезисы докладов. Секция физики. - М.: РУДН, 2010. - С. 68-69.

15. Королькова А. В., Черноиванов А. И. Математическое описание при помощи аппарата стохастических дифференциальных уравнений изменения окна алгоритма TCP-NewReno // XLVI Всероссийская конференция по проблемам математики, информатики, физики п химии: Тезисы докладов. Секция физики. - М.: РУДН, 2010. - С. 72-73.

Цитируемая литература

16. Misra V., Gong W.-B., Towsley D. Stochastic Differential Equation Modeling and Analysis of TCP-Windowsize Behavior. — 1999.

17. Misra V., Gong W.-B., Towsley D. Fluid-Based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED // ACM SIG-COMM Computer Communication Review. — 2000. — Vol. 30, issue 4. — Pp. 151-160.

18. Kulkarni V. G. Fluid Models for Single Buffer Systems // Frontiers in Queueing. Models and Applications in Science and Engineering / Ed. by J. H. Dshalalow. — CRC Press, 1997. — Pp. 321-338.

19. van Foreest N. D. Queues with congestion-dependent feedback: Ph.D. thesis. — Enschede: University of Twente, 2004. — http://doc.utwente.nl/ 50783/.

20. Андронов А. А., Витт А. А., Хайкпн С. Э. Теория колебаний. — 2-е издание. — Государственное издательство физико-математической литературы, 1959. — 916 с.

Королькова Анна Владиславовна (Россия) Математическая модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока

В работе разработана математическая модель процесса передачи трафика с регулируемой алгоритмом типа Random Early Detection (RED) динамической интенсивностью потока.

Для построенной модели проведены качественное исследование и анализ с помощью разработанного для вычислительного эксперимента комплекса программ. Показано, что модель имеет 2 положения равновесия — узел и предельный цикл, определяющие отсутствие или наличие автоколебательного режима соответственно. Положения равновесия исследованы на устойчивость.

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

Получено стационарное распределение вероятностей состояний соответствующего модели двумерного марковского процесса, а также формулы для расчёта среднего размера TCP-окна передачи и средней длины очереди.

Korolkova Anna Vladislavovna (Russia) Mathematical model of the process transfer of traffic with an adjustable by

RED rate

In this paper, the mathematical model of the traffic transfer process with a dynamic rate regulated by Random Early Detection (RED) algorithm is introduced.

For the constructed model the qualitative research and analysis with the help of programs for numerical experiments are made. It is shown that the model has two equilibrium states — a node and a limit cycle, determining the absence or the presence of self-oscillatory regime, respectively. The equilibrium points were tested for stability.

The new method for determining the area of self-oscillatory regime under the influence of the flow state control process on the behavior of TCP-like traffic is introduced.

Steady-state probabilities distribution of two-dimensional Markov process for the given model as well as formulas for the average size of TCP-window and the average queue length are obtained.

Подписано в печать 07.09.10. Формат 60x84/16. Тираж 100 экз. Усл. печ. л. 1,25. Заказ 928

Типография Издательства РУДН 117923, ГСП-1, г. Москва, ул. Орджоникидзе, д.З

Список сокращений.

Список основных обозначений.

Введение.

Глава 1. Механизмы и алгоритмы регулирования состояния потока в сетях передачи данных.

1.1. Исследования в области методов регулирования состояния потока и анализа процессов передачи трафика.

1.2. Классификация алгоритмов семейства RED.

1.3. Обзор алгоритмов на базе RED.

Диссертация посвящена построению и анализу математической модели процесса передачи трафика с регулируемой алгоритмом типа Random Early Detection (RED) [lj динамической интенсивностью потока, в которой при некоторых значениях параметров алгоритма возникает автоколебательный режим.

Актуальность работы

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

В современных пакетных сетях передачи данных доминирующим транспортным протоколом остаётся TCP (Transmission Control Protocol) [2], обладающий рядом особенностей, которые могут привести к неэффективной работе сети в следствие резкого увеличения интенсивности поступающего в сеть потока и соответственно возникновения перегрузок. Для регулирования интенсивности потока широко применяются механизмы управления перегрузкой, в частности, механизм Explicit Congestion Notification (ECN) — явное уведомление о перегруженности канала связи [3], — в совокупности с алгоритмами типа RED. Механизм ECN используется при возникновении перегрузки для маркировки пакетов и посылки сообщения отправителю о необходимости снижения интенсивности предложенной нагрузки. Алгоритм RED [1] и его модификации используют экспоненциально взвешенное скользящее среднее (Exponentially Weighted Moving Average, EWMA) для определения интенсивности сброса пакетов при превышении порогового значения заполненности очереди.

Алгоритм RED (и его многочисленные модификации) благодаря простоте своей реализации в сетевом оборудовании достаточно эффективен, но обладает рядом недостатков. В частности, при некоторых значениях параметров возникает устойчивый автоколебательный режим функционирования системы, что негативным образом сказывается на показателях качества обслуживания сети (пропускной способности, задержке передачи пакетов и т.д.). До сих пор нет чётких, обоснованных рекомендаций по выбору значений параметров RED, при которых система не входила бы в автоколебательный режим. Часто предлагается использовать предустановленные в сетевом оборудовании параметры или подстраивать их по результатам натурного эксперимента. Существующие на данный момент исследования в этой области направлены в основном на попытки уменьшения амплитуды осцилляций, но не на определение условий и области их возникновения.

Таким образом, актуальным представляется исследование эффекта возникновения автоколебательного режима процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока путём построения и анализа адекватной математической модели, которая позволит определить область возникновения автоколебаний и обосновать выбор значений параметров алгоритмов типа RED для избежания попадания в эту область.

На основании изложенной выше научной проблемы сформулированы следующие цель и задачи диссертации.

Цель диссертационной работы

Разработка математической модели, обеспечивающей обоснованный выбор значений параметров алгоритма RED или его модификации с целью избежания попадания в область возникновения автоколебательного режима.

Задачи диссертационной работы разработка математической модели процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока; качественный анализ разработанной математической модели с целью изучения характера и устойчивости особых точек; разработка метода анализа эффекта возникновения автоколебаний в построенной модели с целью корректного выбора значений параметров алгоритмов типа RED для избежания попадания в область возникновения автоколебаний; получение стационарных характеристик разработанной модели.

Результаты, выносимые на защиту

1. Разработана математическая модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока.

2. Для предложенной модели проведён качественный анализ с помощью разработанного для вычислительного эксперимента комплекса программ. Показано, что модель имеет 2 положения равновесия — узел и предельный цикл, определяющие отсутствие или наличие автоколебательного режима соответственно, а также, что эти положения устойчивы.

3. Предложен новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика.

4. Получено стационарное распределение вероятностей состояний и вероятностные характеристики двумерного марковского процесса, соответствующего разработанной модели.

Научная новизна

1. Отличительной особенностью предложенной математической модели процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока является применение для описания динамических переменных модели аппарата стохастических дифференциальных уравнений с пуассоновским процессом и учёт по сравнению с жидкостной моделью из [4,5] дополнительных факторов, оказывающих влияние на возникновение автоколебательного режима.

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

3. Впервые предложен новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика.

4. Для нахождения стационарных характеристик двумерного марковского процесса, соответствующего разработанной в диссертации модели, в отличие от других известных работ [6, 7] впервые построена вложенная цепь Маркова и детально учтены принципы функционирования протокола TCP-Reno [8] и процесса регулирования состояния потока.

Методы исследования

В работе использовались методы теории нелинейных колебаний, теории стохастических дифференциальных уравнений, качественной теории дифференциальных уравнений, численные методы, а также методы теории случайных процессов.

Обоснованность и достоверность результатов

Обоснованность полученных результатов следует из того, что на всех этапах аналитического и численного решения поставленных задач использовались строгие и проверенные методы: методы качественного анализа (анализ фазовых и параметрических портретов), широко известные и хорошо себя зарекомендовавшие численные методы Ньютона и Рунге-Кутта 4-го порядка, метод точечных отображений, метод вложенной цепи Маркова.

Достоверность полученных в диссертации результатов численного анализа подтверждается их сравнением при одинаковых условиях проведения численного эксперимента с результатами имитационного моделирования на NS-2, полученными в работах [4,5].

Практическая значимость

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

Структура и объем диссертации

Диссертация состоит из введения, трёх глав, заключения и списка литературы из 104 наименований. Диссертация содержит 115 страниц текста, 1 таблицу и 44 рисунка.

Основные выводы и результаты диссертационной работы:

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

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

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

4. Предложен новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика. Метод позволяет корректно выбрать значения параметров алгоритмов типа RED для избежания попадания в область возникновения автоколебаний.

5. Получено стационарное распределение вероятностей состояний и вероятностные характеристики двумерного марковского процесса, соответствующего разработанной модели, что позволяет оценить количественные характеристики модели.

6. Проведены численные эксперименты по моделированию и определению области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение ТСР-подобного трафика. Верификация результатов моделирования показала, что разработанная модель, метод и комплекс программ позволяют определять область возникновения автоколебательного режима, корректно выбирать значения параметров алгоритмов типа RED для избежания попадания в область возникновения автоколебаний.

По теме диссертации опубликовано 15 работ [16-18,82,83,95-104], из которых 4 (работы [83,96,101,102]) — в ведущих рецензируемых журналах и изданиях, определённых Высшей аттестационной комиссией.

Все представленные в диссертационной работе результаты получены лично автором и состоят в следующем: по поставленным задачам определены методы исследований; проведено исследование и выявлены особенности алгоритма RED и его модификаций, для классификации определены общие признаки алгоритмов; построена улучшенная по сравнению с [4, 5] модель процесса передачи трафика с регулируемой алгоритмом типа RED динамической интенсивностью потока; разработан и реализован новый метод определения области возникновения автоколебательного режима при воздействии процесса регулирования состояния потока на поведение TCP-подобного трафика; получено стационарное распределение и вероятностные характеристики соответствующего модели двумерного марковского процесса.

Заключение

1. Floyd S., Jacobson V. Random Early Detection Gateways for Congestion Avoidance // IEEE/ACM Transactions on Networking. — 1993. — No 1(4). — Pp. 397-413.

2. Transmission Control Protocol. RFC 793 / Ed. by J. Postel. — Information Sciences Institute, 1981. —http://www.faqs.org/rfcs/rfc793. html.

3. Floyd S. Explicit Congestion Notification (ECN) Mechanism in the TCP/IP Protocol // ACM Computer Communications Review. — 1994. — Vol. 24.

4. Misra V., Gong W.-B., Towsley D. Stochastic Differential Equation Modeling and Analysis of TCP-Windowsize Behavior. —1999.

5. Misra V., Gong W.-B., Towsley D. Fluid-Based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED // ACM SIGCOMM Computer Communication Review. —2000. — Vol. 30, issue 4. — Pp. 151-160.

6. TCP Congestion Control. RFC-2581 / Ed. by M. Allrnan, V. Paxson, W. Stevens. — United States: RFC Editor, 1999.

7. Jacobson V. Congestion Avoidance and Control // SIGCOMM '88: Symposium Proceedings on Communications Architectures and Protocols. — New York, NY, USA: ACM, 1988. — Pp. 314-329.

8. Requirements for Internet Hosts — Communication Layers. RFC-1122 / Ed. by R. Braden. — United States: RFC Editor, 1989.

9. Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers, RFC 2474 / K. Nichols, S. Blake, F. Baker, D. Black. — 1998. — http://tools.ietf.org/html/ rfc2474.txt.

10. An Architecture for Differentiated Services, RFC 2475 / S. Blake, D. Black, M. Carlson et al. — 1998. — http: //tools . ietf . org/html/ rfc2475.txt.

11. Assured Forwarding PHB Group, RFC 2597 / J. Heinanen, F. Baker, W. Weiss, J. Wroclawski. — 1999. — http://tools.ietf.org/html/ rfc2597.

12. Jacobson V., Nichols K., Poduri K. An Expedited Forwarding PHB, RFC 2598. — 1999. — http://tools.ietf.org/html/rfc2598.

13. Grossman D. New Terminology and Clarifications for Diff-serv, RFC 3260. — 2002. — http://tools.ietf.org/html/ rfc3260.

14. The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm / M. Mathis, J. Semke, J. Mahdavi, T. Ott // SIGCOMM Corn-put. Commun. Rev. — 1997. — Vol. 27, No 3. — Pp. 67-82. — ISSN 0146-4833.

15. Floyd S., Fall K. Promoting the Use of End-to-End Congestion Control in the Internet // IEEE/ACM Transactions on Networking. — 1999. — Vol. 7, No 4. — P. 458-472.

16. Misra A., Ott T. J. The Window Distribution of Idealized TCP Congestion Avoidance with Variable Packet Loss // INFOCOM. — 1999. — Pp. 1564-1572.

17. Altman E., Avrachenkov K., Barakat Ch. A Stochastic Model of TCP/IP with Stationary Random Losses // SIGCOMM Comput. Commun. Rev. — 2000. — Vol. 30, No 4. — Pp. 231-242. — ISSN 01464833.

18. Altman E., Avrachenkov K., Barakat Ch. A Stochastic Model of TCP/IP with Stationary Random Losses // IEEE/ACM Trans. Netw. — 2005. — Vol. 13, No 2. — Pp. 356-369. — ISSN 10636692.

19. Mellia M., Stoica I., Zhang H. TCP Model for Short Lived Flows // IEEE Communications Letters. — 2002. — Vol. 6. — P. 85-87.

20. Misra A., Baras J., Ott T. Generalized TCP Congestion Avoidance and its Effect on Bandwidth Sharing and Variability // Proc. IEEE GLOBECOM. — Vol. 1. — San Francisco, CA, USA.: 2000. — Pp. 329-337.

21. Padhye J., Firoiu V., Towsley D. F. Modeling TCP Reno Performance: a Simple Model and its Empirical Validation // IEEE/ACM Trans. Networking. — 2000. — Vol. 8. — Pp. 133-145.

22. Roy R., Mudumbai R. C., Panwar S. S. Analysis of TCP Congestion Control using a Fluid Model // Proc. IEEE ICC 2001. — Vol. 8. — Helsinki, Finland: 2001. — P. 2396-2403.

23. Андронов А. А., Витт А. А., Хайкин С. Э. Теория колебаний. — 2-е издание. — Государственное издательство физико-математической литературы, 1959. — 916 с.

24. Арнольд В. И. Дополнительные главы теории обыкновенных дифференциальных уравнений. — М.: Наука, 1978.

25. Теория бифуркаций / В. И. Арнольд, В. С. Афраймович, Ю. С. Ильяшенко, JL П. Шильников // Динамические системы

26. Итоги науки и техники. Современные проблемы математики. Фундаментальные направления. — М.: ВИНИТИ, 1986. — Т. 5. — С. 5-218.

27. Floyd S. Recommandations on using the Gentle Variant of RED. — 2000. — http://www.aciri.org/floyd/red/gentle. html.

28. Iannaccone G., May M., Diot C. Aggregate Traffic Performance with Active Queue Management and Drop From Tail // SIGCOMM Comput. Commun. Rev. — 2001. — Vol. 31, No 3. — Pp. 4-13. — ISSN 01464833.

29. Ott Т., Lakshman Т., Wong L. SRED: Stabilized RED // Proceedings of INFOCOM'99. — 1999. — Pp. 1346-1355.

30. Techniques for Eliminating Packet Loss in Congested TCP/IP Network: Techrep CSE-TR-349-97 / W.-C. Feng, D. Kandlur, D. Saha, K. Shin / U. Michigan. — 1997.

31. A Self-Configuring RED Gateway / W.-C. Feng, D. Kandlur, D. Saha, K. Shin // Infocom. — 1999.

32. Floyd S., Gummadi R., Shenker S. Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management. — 2001. — http://www.icir.org/floyd/papers/ adaptiveRed.pdf.

33. POWARED for Non-Linear Adaptive RED / В. K. Ng, M. S. Ud-din, A. A. Y. M. Abusin, D. Chieng // Asia-Pacific Conference on Communications, Perth, Western Australia, 3-5 October 2005. —2005.

34. Kim T.-H., Lee K.-H. Refined Adaptive RED in TCP/IP Networks // SICE-ICASE International Joint Conference. — Bexco, Busan, Korea:2006.

35. Zheng В., Atiquzzarnan M. DSRED: A New Queue Management Scheme for the Next Generation Internet // IEICE TRANS. COM-MUN. — 2006. — Vol. E89-B, No 3.

36. Ryoo I., Yang M. A State Dependent RED: An Enhanced Active Queue Management Scheme for Real-Time Internet Services // IEICE Trans. Commun. — 2006. — Vol. E89-B, No 2. — Pp. 614-617.

37. Wu H.-M., Wu C.-C., Lin W. SF-RED — a Novel Server-based AQM to Provide Inter-server Fairness Service // Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS'06). — 2006.

38. Que D., Chen Z., Chen B. An Improvement Algorithm Based on RED and Its Performance Analysis // IEEE. — 2008. — Pp. 2005-2008.

39. Floyd S. RED: Discussions of Setting Parameters. — 1997. — http: //www.aciri.org/floyd/REDparameters.txt.

40. Dynamics of Random Early Detection / D. Lin, D. Lin, R. Morris, R. Morris // Proceedings of ACM SIGCOMM. — Sophia Antipolis, France: 1997. — Pp. 127-137.

41. Floyd S., Fall K., Tieu K. Estimating Arrival Rates from the RED

42. Packet Drop History. — 1998.

43. Reasons not to Deploy RED / M. May, J. Bolot, C. Diot, B. Lyles // Proceedings of IWQoS'99. — 1999. — Pp. 260-262.

44. Improving Fairness and Stability in Best Effort Service: a new Congestion Control Algorithm for SACK-TCP / Y. Atsurni, E. Kondoh, O. Al-tintas, T. Yoshida // IEICE Trans. Commun. — 1998. — Vol. E81-B. — Pp. 2023-2033.

45. Pazos С. M., Juan S. A., Gerla M. Using Back Pressure to Improve TCP Performance with Many Flows // Proc. INFOCOM99. — New York: 1999. — Pp. 431-438.

46. Ziegler Т., Fdida S., Brandauer C. A Quantitative Model of RED with TCP Traffic // IEEE/ACM IWQoS. — Karlsruhe: 2001.

47. Buffer Management Schemes for Supporting TCP in Gigabit Routers with Per-Flow Queuing / B. Suter, Т. V. Lakshman, D. Stiliadis, A. K. Choudhury // IEEE J. Sel. Areas Commun. — 1999. — Vol. 17. — P. 1159-1169.

48. Kim W.-J., Lee B. G. The FB-RED algorithm for TCP over ATM // IEEE GLOBECOM. — Sydney, Australia: 1998. — Pp. 551-555.

49. User Datagram Protocol. RFC 768 / Ed. by J. Postel. — Information Sciences Institute, 1980. — http: //www. f aqs . org/rf cs/rf c768. html.

50. Ziegler Т., Fdida S., Hofmann U. Red+ Gateways For Identification

51. And Discrimination Of Unfriendly Best-Effort Flows In The Internet // Flows in the Internet, Proceedings of IFIP Broadband Communications 99. — 1999. — Pp. 27-38.

52. Anjurn F., Tassiulas L. Fair Bandwidth Sharing among Adaptive and Non-Adaptive Flows in the Internet // INFOCOM. — 1999. — Pp. 1412-1420.

53. Anjum F. M., Tassiulas R. Balanced-RED: An Algorithm to Achieve Fairness in the Internet // Proc. IEEE INFOCOM '99. — 1999.

54. Athuraliya S., Low S. H., Lapsley D. E. Random Early Marking // QoflS. — 2000. — Pp. 43-54.

55. Feng W.-C., Kandlur D. D., Saha D., Shin K. G. BLUE: A New Class of Active Queue Management Algorithms. — 1999.

56. Stochastic Fair Blue: A Queue Management Algorithm for Enforcing Fairness / W.-C. Feng, D. D. Kandlur, D. Saha, K. G. Shin // INFOCOM. — Anchorage, Alaska, USA: 2001. — P. 1520-1529.

57. Clark D. D., Fang W. Explicit Allocation of Best-Effort Packet Delivery Service // IEEE/ACM Transactions on Networking. — 1998. — Vol. 6, No 4. — Pp. 362-373. — http://nms.lcs.mit.edu/ 6829-papers/p362-clark.pdf.

58. A Fairness Study of the Adaptive RIO Active Queue Management Algorithm / R. Cartas, J. Orozco, J. Incera, D. Ros // Proceedings of ENC 2004 5th Mexican International Conference on Computer Science. —

59. Colima, Mexico. — Pp. 57-63.

60. Orozco J. Adaptive RIO // Active Queue Management Algorithm. — 2003. — http://www.rennes.enst-bretagne.fr/~jorozco/aqm. htm.

61. Ranjan P., Abed E. H., La R. J. Nonlinear Instabilities in TCP-RED // Proc. IEEE INFOCOM 2002. — Vol. 1. — New York, NY, USA: 2002. — P. 249-258.

62. Ranjan P., La R. J., Abed E. H. Bifurcations of TCP and UDP traffic under RED // Proc. 10th Mediterranean Conference on Control and Automation (MED) 2002. — Lisbon, Portugal: 2002.

63. Ranjan P., Abed E. H., La R. J. Nonlinear instabilities in TCP-RED // IEEE/ACM Trans. Netw. — 2004. — Vol. 12, No 6. — Pp. 1079-1092. — ISSN 1063-6692.

64. Prycker M. D. Asynchronous Transfer Mode, Solution for Broadband ISDN. — Prentice Hall, 1995.

65. Schwartz M. Broadband Integrated Networks. — Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1996. — ISBN 0-13-5192404.

66. Roberts J. W., Massouli'e L. Bandwidth Sharing and Admission Control for Elastic Traffic // Telecommunication Systems. — 2000. — Vol. 15. — P. 185-201.

67. Kosten L. Stochastic Theory of a Multi-Entry Buffer, part 1 // Delft Progress Report. — 1974. — Vol. 1. — P. 10-18.

68. Anick D., Mitra D., Sondlii M. M. Stochastic Theory of a Data-Handling

69. System with Multiple Sources // Bell Sys. Tech. J. — 1982. — Vol. 61(8). — Pp. 1871-1894.

70. Kosten L. Stochastic Theory of Data Handling Systems, with Groups of Multiple Sources // Performance of Computer-Communication Systems / Ed. by H. Rudin, W. Bux. — Elsevier Science Publishers B.V., 1984. — P. 321-331.

71. Van Doom E. A., Jagers A. A., De Wit J. A Fluid Reservoir Regulated by a Birth-Death Process // Stochastic Models. — 1988. — Vol. 4(3). — Pp. 457-472.

72. Mitra D. Stochastic Theory of a Fluid Model of Producers and Consumers Coupled by a Buffer // Adv. Appl. Prob. — 1988. — Vol. 20. — Pp. 646-676.

73. Cooper R. В., Heyman D. P. Encyclopedia of Telecommunications. — Marcel Dekker, Inc., 1998. — Vol. 16. — P. 453-483.

74. Sericola В., Tuffin B. A Fluid Queue Driven by a Marko-vian Queue // Queueing Systems. — 1999. — Vol. 31. — Pp. 253-264.

75. Virtamo J., Norros I. Fluid Queue Driven by an M\M\1 Queue // Queueing Systems. — 1994. — Vol. 16. — Pp. 373-386.

76. Tucker R. Accurate Method for Analysis of a Packet-Speech Multiplexer with Limited Delay // IEEE Transactions on Communications. — 1988. — Vol. 36(4). — Pp. 479-483.

77. Sericola B. A Finite Buffer Fluid Queue Driven by a Mar коvian Queue // Queueing Systems. — 2001. — Vol. 38. — Pp. 213-220.

78. Ren Q., Kobayashi H. Transient Solutions for the Buffer Behavior in Statistical Multiplexing // Performance Evaluation. — 1995. — Vol. 23. — Pp. 65-87.

79. Tanaka Т., Hashida O., Takahashi Y. Transient Analysis of Fluid Model for ATM Statistical Multiplexer // Performance Evaluation. — 1995. — Vol. 23. — Pp. 145-162.

80. Королькова А. В., Кулябов Д. С., Черноиванов А. И. К вопросу о классификации алгоритмов RED // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2009. — № 3. — С. 34-46.

81. Вентцель А. Д. Курс теории случайных процессов. — 2 издание. — М.: Наука, Физматлит, 1996.

82. Клейнрок JL Теория массового обслуживания / под ред. В. И. Неймана. — М.: Машиностроение, 1979.

83. Колмогоров А. Н. Упрощенное доказательство эргодической теоремы Биркгофа-Хинчина // УМН. — 1938. — Вып. 5. — С. 52-56.

84. Башарин Г. П., Бочаров П. П., Коган Я. А. Анализ очередей в вычислительных сетях. Теория и методы расчёта. — М.: Наука, 1989.

85. Бочаров П. П., Печинкин А. В. Теория массового обслуживания. — М.: Изд-во РУДН, 1995. С. 529.

86. Оксендаль Б. Стохастические дифференциальные уравнения. Введение в теорию и приложения: Пер. с англ. — М.: Мир, ООО «Из-дательсво ACT», 2003.

87. Эльсгольц J1. Э. Дифференциальные уравнения и вариационное исчисление. — 3 издание. — М.: УРСС, 1998.

88. Эрроусмит Д., Плейс К. Обыкновенные дифференциальные уравнения. Качественная теория с приложениями: Пер. с англ. — М.: Мир, 1986.

89. Бутенин Н. В., Неймарк Ю. И., Фуфаев Н. JI. Введение в теорию нелинейных колебаний. — М.: Наука, 1976. — 384 с.

90. Горяченко В. Д. Элементы теории колебаний. Учебное пособие для студентов высших учебных заведений. Издание второе переработанное и дополненное. — М.: Высшая школа, 2001.

91. Kella О., Stadje W. Exact Results for a Fluid Model with State-Dependent Flow Rates // Probab. Eng. Inf. Sci. — 2002. — Vol. 16, No 4. — Pp. 389-402. — ISSN 0269-9648.

92. Кулябов Д. С., Королькова А. В. Аналитическая модель для расчета вероятности сброса пакетов в алгоритме RED // Труды РНТОР-ЭС им. Попова. Серия: Научная сессия, посвященная Дню радио. — 2007. — Вып. LXII. — С. 233-234.

93. Королькова А. В. Метод расчета вероятности сброса пакетов в алгоритме RED // Вестник Российского университета дружбы народов, серия «Математика. Информатика. Физика». — 2007. — № 1-2. — С. 32-37.

94. Королькова А. В., Черноиванов А. И. Моделирование при помощи стохастических дифференциальных уравнений поведения ТСР-трафика при взаимодействии с узлом, работающим по алгоритму RED. — М.: МФТИ, 2009. Т. 1. - С. 130-133.

95. Королькова А. В., Черноиванов А. И. Использование стохастических дифференциальных уравнений для моделирования поведения

96. TCP-трафика при взаимодействии с узлом, работающим по алгоритму RED // «Математика. Компьютер. Образование». Тезисы. — Дубна, 2010.

97. Королькова А. В. Определение области возникновения автоколебаний в системах типа RED // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2010. — № 1. — С. 110-112.

98. Королькова А. В., Кулябов Д. С. Математическая модель динамики поведения параметров систем типа RED // Вестник РУДН. Серия «Математика. Информатика. Физика». — 2010. — № 2. — С. 54-64.

99. Королькова А. В., С. Кулябов Д. Определение области возникновения автоколебаний в системах типа RED // XLVI Всероссийская конференция по проблемам математики, информатики, физики и химии: Тезисы докладов. Секция физики. — М.: РУДН, 2010. — С. 68-69.