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

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

00501823и

Миллер Александр Борисович

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

Специальность 05.13.01 — Системный анализ, управление и обработка информации (технические системы)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 2012 г.

1 9 ДПР 2072

005018230

Работа выполнена в лаборатории № 2 Федерального государственного бюджетного учреждения науки Института проблем передачи информации им. A.A. Харкевича Российской академии наук.

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

академик,

доктор технических наук, профессор Кулешов Александр Петрович

Официальные оппоненты:

доктор технических наук, старший научный сотрудник, ИППИ РАН,

заведующий лабораторией № 18 Ляхов Андрей Игоревич

кандидат технических наук,

доцент,

ИРЭ РАН,

старший научный сотрудник, Григорьев Федор Николаевич

Ведущая организация:

Институт проблем управления им. В. А. Трапезникова РАН

Защита состоится " " 2012 г. на заседании диссертационного

совета Д 002.077.01 на базе ИППИ РАН по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, 19, стр.1. С диссертацией можно ознакомится в библиотеке ИППИ РАН.

Автореферат разослан " ^ " 2012 г.

Ученый секретарь диссертационного совета Д 002.077.01 доктор физико-математических науг — И. И. Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В самом начале развития сети Интернет было замечено, что неограниченный доступ к нему приводит к плохой производительности, а именно к высокой загруженности сети и потере передаваемых пакетов. Это привело к созданию первых методов управления перегрузками для сети Интернет. Основная идея первого метода управления, предложенного В. Джекобсоном, состояла в обнаружении перегрузки в сети через потери пакетов. При обнаружении потери источник пакетов уменьшает свою скорость передачи данных (окно потока), в противном случае он увеличивает скорость. Исходный алгоритм претерпел много небольших, но важных изменений, но основные признаки алгоритма, использовавшиеся для увеличения и уменьшения окна потока, оставались неизменными в различных версиях протокола TCP (Transmission Control Protocol - протокол управления передачей), таких как TCP-Tahoe, Reno, NewReno, SACK.

Вопросы управления перегрузками в сетях передачи данных рассматривались многими авторами, такими как Р. Шрикант, Ш. Вегешна, Э. Альтман, К.Б. Авраченков, Т. Башар, Ф. Келли, М.Л. Цетлин, B.JI. Стефанкж, А.В.Бутрименко, В.А. Васенин, Г.И. Симонова, Б.М. Миллер. На протяжении последних лет основными средствами анализа потоков данных в сети Интернет были жидкостные модели (fluid models). Данные модели учитывают среднюю скорость передачи данных, эволюцию потока пакетов. Эти модели доказали свою пригодность к нахождению точек равновесия, к которым может стремится система, а также к определению условий, при которых данная сходимость выполняется, т.е. система стабильна. Однако реальное поведение сети Интернет далеко от стабильности и стационарности вследствие временных изменений, активного поведения пользователей и флуктуаций характеристик принимающих и передающих пакеты устройств.

Из-за присущей сети Интернет хаотичности, процесс передачи данных всегда имеет стохастическую и нестационарную природу. Многие авторы применяют управление марковскими цепями к передаче данных и оптимизации Интернет сетей, однако, большинство результатов, полученных до недавнего времени, относятся к стационарному случаю, при котором, как и в жидкостных моделях, система массового обслуживания устойчива, т.е. интенсивность входящего потока в среднем меньше скорости обслуживания. Поскольку в реальной жизни данное условие выполняется не всегда, для успешного функционирования система должна отклонять некоторые входящие пакеты, чтобы избежать перегрузки. Все существующие протоколы TCP работают по данному принципу. Примером могут служить хорошо известные протоколы TCP Reno, TCP Red, а так же все основные методы управления перегрузками в Интернете. В то же самое время, большинство существующих работ, связанных с анализом TCP не учитывают некоторые принципиальные особенности управления реальным потоком, они обычно рассматривают модели с дискретным временем и стационарные ECN (Ех-

plicit Congestion Notification - явное уведомление о перегрузке) потоки. Реальные потоки данных нестационарны и их характеристики зависят от управления. Теория, описывающая оптимальное управление такими системами, должна учитывать различные критерии, характеризующие качество работы системы. Оптимальное управление показывает более стабильное поведение скорости передачи данных. Преимущества методологии, основанной на использовании стохастического управления, отмечались рядом авторов, работающих над оптимизацией TCP (TCP Illinois и TCP Westwood+) и созданием высокоскоростных сетей передачи данных, работающих на большие расстояния, а также в беспроводных сетях передачи данных.

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

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

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

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

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

• Для статической модели управления доступом проведено исследование эффективности выбора профиля вероятностей отклонения пакетов аналогично алгоритму произвольного раннего случайного обнаружения (RED - random early detection) с учетом активного поведения пользователей. Предложен алгоритм вычисления вероятностей перегрузки в зависимости от профиля вероятностей отклонения пакетов.

• Впервые предложена математическая модель системы оптимального управления доступом в очередь и скоростью обслуживания в сетях

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

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

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

• Институтом проблем информатики РАН в ходе выполнения ряда НИОКР по созданию информационно-аналитических систем специального назначения при реализации подсистем управления функционированием и интегрированного доступа.

• Научно-производственным предприятием "ЗАО Центром совместных технологических разработок" (ТЕХНОР) в ходе выполнения ряда НИОКР по созданию программного обеспечения для моделирования и оптимизации систем передачи данных интегрированного доступа.

Результаты работы использованы в рамках исследований по гранту РФФИ № 10-01-00710 "Оптимальное управление нестационарными марковскими цепями с ограничениями на состояние".

Достоверность полученных результатов подтверждается строгими аналитическими выкладками и результатами имитационного моделирования.

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих научных конференциях и семинарах: 52-ой научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук" (Москва, 2009); 32-ой конференции молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы" (Москва,

2009); Melbourne Probability Seminar at Monash University, Victoria (Australia,

2010); 49-ой Международной конференции IEEE Conference on Decision and Control (Atlanta, USA, 2010); 50-ой Международной конференции IEEE Conference

on Decisión and Control (Orlando, USA, 2011); семинарах ИППИ РАН и ИПУ РАН (Москва., 2011).

Публикации. Соискатель имеет 12 научных работ, в том числе 6 по теме диссертации (общим объемом 69 стр.), из них 2 опубликованы в изданиях, входящих в Перечень ВАК [1],[2] (общим объемом 29 стр.) и 4 работы опубликованы в трудах научных конференций [3]-[6] (общим объемом 40 стр.), из них 2 выполнены в соавторстве (объемом 27 стр.). В работах, выполненных в соавторстве, соискателю принадлежит: в [5] - вывод уравнений динамического программирования для стохастической модели управления доступом и скоростью обслуживания, а также реализация программного моделирования и выполнение сравнительного анализа оптимального управления со стационарным; [6] - вывод уравнений динамического программирования для стохастической модели управления доступом и скоростью обслуживания с двумя связанными полосами пропускания, а также сравнительный анализ эффективности использования двух связанных полос пропускания.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 61 наименование. Диссертация изложена на 132 страницах текста, содержит 20 рисунков, 4 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Протоколы управления передачей используют механизм управления окном потока, под которым подразумевается максимальное количество неподтвержденных пакетов, отправляемых пользователем в сеть в любой момент времени. Сетевой протокол — это набор правил, позволяющего осуществлять соединение и обмен данными между двумя включенными в сеть компьютерами. Одним из первых алгоритмов, внедренных в протокол TCP, был адаптивный алгоритм управления окном В. Джекобсона. Основная идея алгоритма состоит в том, что размер окна увеличивается пока не наступает переполнение очереди. Наиболее распространенным в настоящее время является алгоритм произвольного раннего обнаружения (RED), использующий превентивный подход к предотвращению перегрузки сети. Вместо ожидания фактического переполнения очереди, RED начинает отбрасывать пакеты с ненулевой вероятностью, когда средний размер очереди превысит определенное минимальное пороговое значение. Данный алгоритм базируется на вычислении среднего размера очереди и вычислении вероятности отбрасывания пакетов. Совместно с протоколом TCP используется механизм активного управления очередями (Active Queuing Management), который

Рис. 1. Архитектура сети с централизованным управлением

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

В работе ставится задача исследования, заключающаяся в предотвращении перегрузок в сетях передачи данных. В качестве сети передачи данных в следующих разделах работы рассматривается сеть беспроводного доступа с централизованным управлением, т.к. в беспроводных сетях можно управлять скоростью обслуживания, в то время как в проводных сетях полоса пропускания жестко фиксирована, т.е. интенсивность обслуживания является постоянной величиной. В данной модели радиосота объединяет S оконечных станций (ОС), каждая из которых подключает к радиосоте локальную сеть s (s = 1,..., S), состоящую из Ns терминальных станций (ТС) и одного или нескольких серверов (Рис. 1). Антенны ОС сфокусированы на антенну базовой станздии (ВС), являющейся точкой доступа во внешнюю сеть. При этом ОС не имеют радиовидимости друг с другом (т.е. скрыты друг от друга) и вынуждены взаимодействовать через ретрансляционную ВС. Оконечная станция выступает в роли маршрутизатора пакетов, генерируемых терминальными станциями, т.е. ОС управляет вероятностью доступа в свою очередь. К тому же при централизованном управлении доступ ОС к беспроводному каналу управляется ВС, т.е. ВС выделяет часть полосы пропускания каждой ОС по их запросам. Таким образом, ОС может регулировать свою скорость обслуживания путем передачи соответсвующего запроса к ВС.

Во второй главе исследована детерминированная модель управления

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

Имеется N пользователей, каждый из которых генерирует поток пакетов с интенсивностью u¡(t). Для суммарного потока пакетов она равна сумме U(t) =

N

J2ui{t)- Каждый пользователь характеризуется своей собственной функцией ;=i

полезности (utility function) /¡(и) типа Кобба-Дугласа, так что при цене потока q > 0 "функция полезности минус затраты" удовлетворяет условию /¿(и) — qu —> —оо если и —» оо. Эта функция достигает единственного максимума в некоторой точке u¿(<j), что и отражает стратегию пользователя.

Пусть N пользователей посылают свои потоки пакетов на общий маршрутизатор, имеющий очередь на М пакетов (очередь характеризуется М + 1 различными состояниями, соответствующими различным значениям вероятности доступа). Считается, что приходящие пакеты должны встать в очередь, обслужиться с некоторой интенсивностью ц > 0 и отправиться дальше, т.е. освободить место в очереди. Если в момент времени t приходит новый пакет и в очереди 0 < M(t) < М пакетов, то пакет либо ставится в очередь на обслуживание, либо отражается (это называется управление доступом)1. Маршрутизатор стремится к тому, чтобы общий поток пакетов не создавал переполнения, т.к. если пакет поступает в момент когда очередь заполнена полностью, то он отражается с вероятностью 1, это и называется congestion (перегрузка, переполнение, затор и пр.). Поэтому маршрутизатору нужно заранее установить либо более высокую цену обслуживания, либо начать отражать пакеты раньше момента заполнения очереди. Пусть вероятность

N

отражения пакета равна q(M(t),U(t)), где U(t) = 2u,(í). Тогда функция

выигрыша для г'-го пользователя в момент времени t есть F¡(u,t) = /¿(и) — Аои — q(M(t), U(t))u. Пользователю известна лишь величина q(M(t), U(t)) и он выбирает свой поток так, чтобы максимизировать функцию полезности минус затраты2.

Вектор распределения вероятностей p(í) = (po(t), ■ ■ ■ ,PM{t))T удовлетворяет системе уравнений вида3 p(t) = A(U(P(t)))p(t), где матрица A(U) — переходная матрица системы уравнений процесса рождения-гибели. Стационарное решение данной системы pstat удовлетворяет нелинейной системе

1 Kelly F. P., Maulloo А. К., Tan D. К. H. Rate control for communication networks: shadow prices, proportional fairness and stability // The journal of the operational research society. 1998. V. 49, JA 3. P.237-252.

йВасенин B.A., Симонова Г.И.Матемтическле модели управления трафиком и Интернете. Новые подходы на основе схем TCP/AQM // Автоматика и телемеханика. 2005. № 8. С. S4-107.

3Феллер В. Введение в теорию вероятностей и ее приложения // М.: Мир. 1984. Т.1. С. 469-4S2.

уравнений

м

Л{и(Р*'а1))рзШ = О, £ - 1,

т—О п

и?" = ЩР**) = £

1=1

Первые два уравнения служат для определения стационарных вероятностей. Их решения как функции и(Р81а£) можно определить с помощью формул Эрланга.

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

Для анализа устойчивости системы "пользователи-маршрутизатор" и оптимизации алгоритма управления доступом разработана программа моделирования на МаЛаЬ. Для проведения моделирования задаются следующие параметры и начальные условия: М — размер очереди маршрутизатора, N — количество пользователей, }\щ) = —^ — вид функции полезности г-го пользователя, аг — коэффициент функции полезности г-го пользователя, к — цена потерь, р0 — начальное распределение вероятностей длины очереди, иен — начальное значение потока г-го пользователя, Т — временной интервал наблюдения системы, а^ > 0 — скорость настройки (агрессивность протокола г-го пользователя). Рассмотрено два случая с одинаковыми параметрами и начальными условиями, но разными наборами вероятностей отклонения пакетов. В обоих случаях: М = 19, N = 5, — 5,

а2 = 10, а3 = 25, а4 = 50, а5 = 75, к = 1, р0 = 0.05 (р0 = ^ ищ = 1,

«02 = 3, «оз = 5, и01 = 7, щ5 = 10, Т = 10. Вероятности д(т),т = 0, ..,19 отклонения пакетов для первого случая выбраны следующим образом

<?! = [0; 0; 0; 0; 0; 0; 0; 0; 0; 0.08; 0.16; 0.24; 0.32; 0.4; 0.48; 0; 0; 0; 0; 1], а для второго случая <32 = [0; 0; 0; 0; 0; 0; 0; 0; 0; 0.08; 0.16; 0.24; 0.32; 0.4; 0.48; 0.56; 0.61; 0.72; 0.8; 1].

Вероятность перегрузки системы (переполнения очереди) в первом случае устанавливается на уровне 0.43 (при средней длине очереди 18.3), а во втором случае на уровне 0.175 (при средней длине очереди 14.8) (Рис. 2, 3). Это означает, что выбор вероятностей доступа весьма эффективно влияет на вероятность перегрузки, сохраняя среднюю интенсивность обслуживания.

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

0.35 0.3 0.25 0.2 0.15 ■ 0.1 0.05

О

а)

0.05 " 0.045 0.04 0,035 0.03 0.025 0.02 0.015 Д

0.01 I-

10

б)

Рис. 2. Зависимость вероятности перегрузки (переполнения очереди) от времени (а) - для первого случая, (б) - для второго случая

2 4 6 8 10 б)

Рис. 3. Зависимость средней длины очереди от времени (а) - для первого случая, (б) - для второго случая

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

Рассматривается упрощенная модель беспроводной сети с централизованным управлением, в которой имеется несколько оконечных станций (ОС), каждая из которых подключает к радиосоте локальную сеть из N терминальных станций (ТС). Трафик передается от терминальных станций к оконечной станции, т.е. каждая ТС генерирует поток пакетов. Предполагаем, что поток пакетов представляет собой считающий процесс со случайной интенсивностью А(£) > £ [0,Т], которая зависит от потребностей ТС и текущего состояния очереди. Очередь ОС ограничена некоторой константой М < оо. Вводятся управления: интенсивность обслуживания ТС ц 6 [/¿,/1], где ¿г > 0, Д > 0, и и{£) € [0,1] — вероятность принять пакет в момент времени

г £ [0,71.

Пусть М(4) — число пакетов в системе в момент времени £, тогда общее

15 14.5 14 13.5 13 12.5 12 11.5 11 10.5

число состояний есть М + 1, а соответствующее пространство состояний 5 состоит из единичных векторов {со,..., см) вида а = (0, ..0,1,0, ..0) с единицей на г-м месте в пространстве размерности М + 1.

Т.к. управление доступом в системе зависит лишь от текущего числа пакетов, то модель управления может быть описана в терминах управляемой марковской цепи с Л/ + 1 состояниями и генератором А(1,и,ц), матрицей размерности (А/ + 1) х (М +1).

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

/;(?;, г, Р) = -^-А0г,-А0г;Р, г = 1,..,]У,

где V — интенсивность генерации пакетов г-ой ТС, До — цена трафика, Р — вероятность отклонения пакета, которая определяется ОС в зависимости от времени и длины очереди, т. е. Р = Р(Ь, М(£-)). Параметр а*(<) характеризует потребность ТС в ресурсах. Полагаем, что ОС имеет информацию о функциях полезности ТС. Максимизируя свою функцию полезности, г-ая ТС устанавливает оптимальное значение интенсивности потока, равное

vf(t, P(t, M(t-))) = max Л(М) = yÇ^S

- -, —ГТТ- При этом Л0(1 + P(t,M(t-)))

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

л (г, p(t, M(t—))) = ё vf(t, p(t, M(t-))) = ■ c{t)

i=l

\/Ao(l + P(t,M(t-)))'

N

где

= X) \/äi(t) — величина, которая характеризует все множество ТС.

<=1

Далее получаем выражение для матрицы генератора A(1.}u,¡j,) при управлении доступом в случае активных ТС. Данное выражение выведено в статье [1] и имеет вид матрицы генератора процесса размножения-гибели с управляемыми интенсивностями размножения (вероятность доступа) и гибели (скорость обслуживания).

В задаче рассматривается следующий критерий качества:

JK)i/i(-)] = E(?>o(A:T) + ]:/o(s,ti(s),^(s),Xs)ds) min (2)

lo J "(•)./<(•)

где фа(Х) = (ф0,Х), f0{s,u,ß,X) = (f0{s,u,¡i),X) и ф0 G Rn, fÓ{s: и, ¡j.) = (fa(s, и,ц,е{),..., f0(s, к, fi, e„)) 11

и каждая fo(s, ■, ■, eî) — функция стоимости, когда марковская цепь находится в состоянии е,- в момент времени s £ [0,71].

Предположение 1. Каждая из функций fo(s, •■• ,е,-),г = 1...АГ, непрерывна на [О,-Г] х [0,1] х [р.,р].

Общий подход к решению задачи оптимального управления с помощью метода динамического программирования изложен в работах Эллиота1 и Дэвиса5. Для общей модели, описываемой матрицей генератора A(t,u,p), где (и, р) £ U, определим функцию цены

V(t,X) = inf J[u(-),M-)l*t = *]. (3)

где

J[u(-),p(-)\Xt = X] = E|ri0(Xr) + } f0(s,u(s),p(s), Xs)ds Xt = X

= №),x).

(4)

Функция ç(t) является единственным решением уравнения динамического программирования

{<P'(t),X}+ min Mt),A{t,u,p)X) + (fa(t;u,p),X)]=0 (5)

с граничным условием ф{Т) = фа.

Следующий результат дает характеризацию оптимального управления.

Теорема 1. Пусть ф(£) — решение системы (5), и существует. (u0{t,X),p0{t,X)) £ U,(t,X) £ [0, Г] х S такое, что для каждой пары (t,X) £ [Oi^l х S величина с правой стороны уравнения II(ф, t, и, р, X) = (ф, A(t, и, р)Х) + (f0{t, и, р),Х)) и функция II{<t>(t),t, и, р, X) достигают минимума в точке (uo(t, X), p.o(t,X)). Тогда существует (û(t, Xq), p(t, Xq)) в классе J-f -предсказуемых управлений, являющееся оптимальным управлением, и V(t,X) = J[û(-),ß(-)\Xt = X]. Это оптимальное управление можно выбрать марковским:

(û(t, Xß.fL(t, XI)) = (uo(t, Xt), p0{t, Xt)) = argmin Н[ф{1), t, u, p, Xt)

Критерий качества учитывает среднее время нахождения пакета в очереди, среднее число отраженных пакетов, стоимость обслуживания и штраф за простой ОС [1],[4], которые балансируются коэффициентами к\,..., к4 6

4Elliott R.J., Aggoun L., Moore J.В. Hidden Markov Models. Estimation and Control // NY: Springer Verlag. 1995. 361 p.

5Davis M.H.A. Markov Models and Optimization // London: Chapman & Hall. 1993. 308 p.

eMiller B.M., Miller G.B., Siemenikhin K.V. Optimal control of Markov chains with constraints // Proceedings of joint 48th IEEE conference on decision and control and 2Sth Chinese control conference. 2009. P. 512-518.

0.8

I

0.6

I

I

0.2

J

0

N1

2 3 4

Рис. 4. Средняя по времени вероятность отклонения пакетов Ра1,гд в зависимости от загруженности очереди М

Далее были получены аналитические выражения для оптимального управления //opi(i,e,) и uopt(t, е,) [2],[5]. Подстановка ^¡(i.e,) и uopi(i,e,) в уравнение динамического программирования (5) дает систему обыкновенных дифференциальных уравнений для функции решение которой может быть получено с помощью численных методов.

Для численного моделирования была разработана программа на Maple 12, решающая систему обыкновенных дифференциальных уравнений и находящая оптимальные управления. Ниже приведен пример моделирования для следующего набора параметров и терминальных условий:/^ = 3,Ji = 8 — нижний и верхний пороги скорости обслуживания ОС;с(£) = 2+1.5 cos(2(2 — i)) — потребность ТС в трафике в зависимости от времени; к\ = 0.35, к-2 = 3, к$ — 1.5, к^ = 0.5 — коэффициенты весов интегральных критериев Ji,Ji,Jz,Ji\ Ао = 0.01 — цена трафика; М = 5 — размер очереди.

Были получены следующие зависимости для средней по времени вероятности отклонения пакетов в зависимости от загруженности очереди (Рис. 4), зависимости входного потока пакетов, интенсивности обслуживания и вероятности отклонения пакетов на интервале времени [0,10] в зависимости от загруженности очереди (Рис. 5)

Далее приведено сравнение предложенной модели динамического управления доступом в очередь и скоростью обслуживания с алгоритмом произвольного раннего обнаружения (RED). Т.к. RED не является марковским и может быть оценен только с помощью моделирования Монте-Карло, то такое сравнение является довольно трудной задачей. Поэтому произведено сравнение полученного оптимального управления с субоптимальным, для которого зададются законы управления доступом и скоростью обслуживания, основываясь на значениях оптимальных управлений u(t) и /i(i). Для субоптимального алгоритма вероятность отклонения пакета определяется как среднее значение вероятности доступа для каждого состояния по

о 2 4 6 8 10 о 2 4 6 8 10 0 2 ' 4 б 8 10

а) б) в)

Рис. 5. Состояние с загруженностью ниже среднего (а), со средней загруженностью (б), с загруженностью выше среднего (в), где (1) — входной поток, (2) — интенсивность обслуживания, (3) — вероятность отклонения пакетов

оптимальному алгоритму, А управление скоростью обслуживания выбирается

М + 7*

= (6)

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

Состояние очереди Время опт. Время субопт. Откл. опт. Откл. субопт.

М=0 0.43 0.64 6.89 7.26

0.46 0.68 7.38 7.72

М=2 0.49 0.73 7.62 8.34

м=з 0.52 0.77 7.44 9.01

М—4 0.54 0.80 8.12 9.71

М—5 0.56 0.82 8.82 10.42

Результаты исследования данной главы опубликованы в [1]-[5].

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

Рассматривается упрощенная модель беспроводной сети, аналогичная используемой в главе 3. Но предполагается, что каждая оконечная станция может устанавливать связь с несколькими базовыми станциями. Общее число БС равно й. Подключение к нескольким БС служит для повышения надежности связи и экономии энергии базовой станции. БС могут принадлежать разным провайдерам, соответственно, они могут иметь разные стоимости обслуживания

и предоставлять отличное друг от друга качество связи. Предполагается, что оконечная станция договаривается с каждой из БС о выделении полосы пропускания при передаче трафика между терминальными станциями и оконечной станцией. При этом в случае если пакет поступает в первую очередь, выделенную BCj, и если он отклоняется с некоторой вероятностью, то повторный пакет посылается в дополнительную очередь, выделенную БСг и т.д. Если пакет отклоняется в очереди, выделенной BCj, то он отклоняется окончательно.

Состояние такой системы может быть описано набором из d соединенных марковских цепей, каждая из которых имеет Miti = l,...,d возможных состояний, и представляется набором единичных векторов Xi £ S; = {ei,..., едд}, типа е,- = (0, ..0,1, 0, ..0) с единичным вектором на г-м месте в пространстве векторов ЯЛ/, где г = В общем этот набор можно

представить тензором порядка d таким, что X = {ЛТ^ЛГг!...!^}.

Предполагается, что каждая г-ая управляемая марковская цепь имеет Mi возможных состояний и описывается следующим стохастическим дифференциальным уравнением аналогично Главе 3

t

(*0t = №)о + J Ai(sMs))(X,)sds + (Wi)t, (7)

о

где (Х;)о — начальное состояние i марковской цепи.

Задача оптимального управления ставится как и в Главе 2 заменой скалярного произведения на тензорное.

Пусть <p(i) определана аналогично (3), тогда уравнение динамического программирования в отношении <p(t) имеет вид

at ueU

+Хг ® A2(t, u)X2 ® ... ® Xd + ... + Хг ® ® - ® Ad(t, u)Xd) + (/0(f, и), X)] = = — min H(t, <t>(t),u, X)

uSU

(8)

с граничными условиями ф(Т) = фд. Т.к. H(t, ф. и, X) непрерывна на {t,u) и аффинна по ф, то Hit, ф,Х) липшицева в ф.

Уравнение (8) имеет единственное решение на [0,Т]. Аналогично главе 3 получаем характеризацию оптимального управления.

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

константой М\. В случае отклонения пакета, он посылается повторно во вторую очередь М2. Входящий поток пакетов является считающим процессом с произвольной интенсивностью А(£) > О, Ь е [0,Т], зависящей от временных предпочтений пользователей терминальных станций и текущей вероятности отклонения. Оконечная станция использует следующие управления: скорости обслуживания и вероятности доступа.

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

Проведено численное моделирование для системы с М\ = Мч = 3, и с заданными ограничениями для управлений щ £ [0,1],и2 € [0,1] и € [1,2], д2 € [3,6]. Время наблюдения процесса равно 1, С(Ь) = 5 +4.5Бт104.

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

1 —■ 0.8 0.6 0.4 0.2 0

0 0.2 0.4 0.6 0.8 1

Рис. б. Управление доступом для состояния (г = 1,] — 2), (а) - щ , (б) - щ

Далее приведено качественное сравнение двух систем передачи данных, где первая система имеет одну полосу пропускания со скоростью обслуживания АЛ £ [мъР1] и длиной очереди А^. Вторая система имеет две полосы пропускания, е [/4, с длиной очереди М[ и /4 € [/4, ц'2] с длиной очереди М2, при этом А/1 = М^ = М2 = 3. Сравнение приводится по критерию качества, отвечающему за среднее время нахождения пакета в очереди. Проведенное моделирование показывает эффективность использования дополнительной полосы пропускания в состоянии перегрузки.

1.8 1.6 1.4 1.2 1

О 0.2 0.4 0.6 0.8 1 а)

О 0.2 0,4 0.6 0.S 1 б)

Рис. 7. Управление скоростью обслуживания для состояния (? = 1, ^ = 2), (а) -VI . (б) - Ц2

Полоса 1 Полоса 2 Среднее время в очереди

fi е [1,2] II, в [0.5, Ц 0.15

£ [1.2] ¿2 е [1.2] 0.10

¿1 G [1.2] fe е [2,5] 0.09

lh G [1,2] /4 G К. Ю] 0.07

€[1,2] е [Ю, 20] 0.06

Результаты исследования данной главы опубликованы в [6].

В заключении приводятся выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

7. Проведен анализ эффективности использования оконечной станции с двумя полосами пропускания (по аналогии с беспроводной сетью широкополосного радиодостуиа).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Miller А.В. Dynamic access control in the presence of active users // Journal of communications technology and electronics. 2010. V. 55, № 12. P. 1432-1441.

2. Миллер А.Б. Предотвращение перегрузок в сетях передачи данных с помощью методов стохастического управления // Автоматика и телемеханика. 2010. № 9. С. 70-82.

3. Миллер А.Б. Динамическое управление доступом к ресурсам и скоростью обслуживания при активных пользователях // Труды 52-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Часть 1. Радиотехника и кибернетика. М.: МФТИ. 2009. Т. 1. С.118-122.

4. Миллер А.Б. Динамическое управление доступом и скоростью обслуживания при активных пользователях // Сборник трудов конференции "Информационные технологии и системы" (ИТиС). М.: ИППИ. 2009. С. 436-442.

5. Miller А.В., Miller В.M. Congestion avoidance with the aid of stochastic control // Proceedings of the 49th IEEE CDC. 2010. P. 552-558.

6. Miller А.В., Miller B.M. Control of connected Markov chains. Application to congestion avoidance in the Internet // Proceedings of the 50th IEEE CDC. 2011. P. 7242-7248.

Подписано в печать:

21.03.2012

Заказ № 6860 Тираж - 100 экз. Печать трафаретная. Объем: 1 усл.п.л. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

61 12-5/2481

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ им. A.A. ХАРКЕВИЧА РАН

Миллер Александр Борисович

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

Специальность 05.13.01 — Системный анализ, управление и обработка информации (технические системы)

Работа на соискание ученой степени кандидата технических наук

Научный руководитель Академик РАН, доктор технических наук, профессор А. П. Кулешов

Москва 2012 г.

Оглавление

Введение 6

1 Обзор механизмов управления потоками данных в Интернете. 16

1.1 Управление окном потока........ ........................16

1.2 Сетевые протоколы................................................18

1.2.1 Адаптивный алгоритм управления окном Джекобсона 19

1.2.2 Механизм медленного старта и предотвращение перегрузки ......................................................19

1.2.3 TCP Reno..................................................21

1.2.4 TCP Vegas..................................................26

1.2.5 TCP Tahoe ................................................28

1.2.6 Реакция TCP-трафика на применение политики "отбрасывания хвоста" ......................................30

1.3 RED — алгоритм превентивного управления очередью с целью предотвращения перегрузки сети..........................31

1.3.1 Алгоритм вычисления среднего размера очереди ... 34

1.3.2 Алгоритм вычисления вероятности отбрасывания пакетов ........................................................36

1.3.3 Активное управление очередями.

Модель справедливого распределения ресурсов. ... 38

1.4 Задача исследования..............................................40

2 Математическая модель системы передачи данных 45

2.1 Модель системы передачи данных....................45

2.1.1 Модель потока пакетов ..................................45

2.1.2 Функция полезности пользователя......................47

2.1.3 Линейное уравнение настройки интенсивности .... 49

2.2 Модель поведения маршрутизатора............................50

2.2.1 Статическая модель предоставления ресурсов к обслуживанию ..................................................52

2.2.2 Динамическая модель предоставления ресурсов к обслуживанию ................................................54

2.3 Результаты математического моделирования..................57

2.4 Выводы из исследования модели .............................62

3 Динамическое управление доступом и скоростью обслуживания 66

3.1 Модель динамического управления..............................66

3.2 Формирование входного потока при динамическом управлении доступом и скоростью обслуживания......................72

3.2.1 Динамическое программирование и оптимальное

управление................................................75

3.3 Решение задачи оптимального управления доступом и скоростью обслуживания ..............................................79

3.4 Результаты численного моделирования ........................83

3.5 Сравнение модели динамического управления доступом и скоростью обслуживания с алгоритмом случайного раннего

обнаружения......................................................88

3.6 Выводы из исследования модели с одной марковской цепью 90

4 Исследование моделей связанных марковских цепей 92

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

4.1.1 Начальные сведения......................................92

4.1.2 Модель управляемой марковской цепи..................94

4.1.3 Общий критерий производительности..................95

4.1.4 Функция стоимости и ее представление................96

4.1.5 Метод динамического программирования и его расширение для тензорного состояния ........................96

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

4.2.1 Модель СМО с двумя СУМЦ............................98

4.2.2 Модель связанной марковской цепи с активными пользователями......................101

4.3 Динамическое программирование и оптимальное управление

для связанной марковской цепи с двумя полосами......103

4.3.1 Уравнение динамического программирования для системы двух связанных марковских цепей.......103

4.3.2 Определение функции стоимости............105

4.3.3 Уравнение динамического программирования.....109

4.3.4 Программное моделирование..............115

4.4 Сравнение моделей с двумя полосами и с одной полосой пропускания ..............................117

4.4.1 Выводы из исследования модели СУМЦ........ 119

Заключение 121

Литература 122

Введение

Интернет изначально представлял из себя компьютерную сеть, соединявшую Калифорнийский университет в Лос-Анджелесе, Стэнфордский исследовательский центр, Университет штата Юта и Университет штата Калифорния в Санта-Барбаре. С годами он эволюционировал в глобальную сущность, совершившую прорыв в средствах коммуникации, бизнесе и вычислениях. В самом начале развития сети Интернет было замечено, что неограниченный доступ к нему приводит к плохой производительности, а именно к высокой загруженности сети и потере передаваемых пакетов. Это привело к созданию первых методов управления перегрузками для сети Интернет [1]. Основная идея алгоритма состояла в обнаружении перегрузки в сети через потери пакетов. При обнаружении потери источник пакетов уменьшает свою скорость передачи данных (окно потока), в противном случае он увеличивает скорость. Исходный алгоритм претерпел много небольших, но важных изменений, но основные признаки алгоритма, использовавшиеся для увеличения и уменьшения окна потока, оставались неизменными в различных версиях протокола TCP (Transmission Control Protocol - протокол управления передачей), таких как TCP-Tahoe, Reno, NewReno, SACK.

Вопросы управления перегрузками в сетях передачи данных рассматривались многими авторами, такими как Р. Шрикант, Ш. Вегешна, Э. Альтман, К. Авраченков, Т. Башар, Ф. Келли, В. Васенин и Г. Симонова, Б. Миллер. На протяжении последних лет основными средствами анализа потоков данных в сети Интернет были жидкостные модели (fluid models). Данные модели учитывают среднюю скорость передачи данных, эволюцию потока пакетов. Эти модели доказали свою пригодность к нахождению точек равновесия, к которым может стремится система, а также к

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

Проблема устойчивой работы коллектива взаимодействующих устройств, создающих взаимные помехи, каким по сути дела является Интернет, рассматривалась еще в 60-70 г.г. В частности, в ИППИ этими вопросами занимались A.B. Бутрименко и В.Г. Лазарев [2], которые предложили методы борьбы с заторами, принятыми в международной классификации алгоритмов в то время, а также В.Л. Стефанюк и Б.А. Гинзбург, предложившие управление на сети с помощью "разрешений" [3]. В работах B.JI. Стефанюка и МЛ. Цетлина [4] и позднее B.JI. Стефаню-ка [5], [6], [7] была предложена модель коллектива радиостанций и был разработан универсальный подход к регулированию уровня мощности передающих устройств, обеспечивающий локальную устойчивость путем выбора каждым передатчиком уровня мощности, обеспечивающего получение в коллективе радиостанций некоторого (достижимого) вектора отношений сигнал/шум. Этот подход основан на модели системы радиопередатчиков как коллектива автоматов, минимизирующих собственные функции штрафов, и показана сходимость к единственному положению равновесия, являющемуся точкой Нэша, для критериев типаСг- = + где г = 1 ,...,п — номер передатчика, Аi — отношение сигнал/шум, — мощность передатчика, а^ > 0 — параметр. В тех же работах отмечается, однако, сложность практической реализации этого метода регулирования, т.к. он требует определенного уровня взаимной информированности игроков-автоматов и аккуратности в выборе критериев (как отмечалось

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

В то же время управление набором пользователей в Интернете использует другие методы управления и базируется на других типах критериев. Методы управления — стохастическое ограничение доступа в очередь и управление скоростью обслуживания за счет использования дополнительных (возможно более дорогих) линий передачи данных. Критерии, которые следует принимать во внимание — это прежде всего качество обслуживания, а именно вероятность получения доступа, среднее время ожидания, плата за трафик или простой маршрутизатора. При таком подходе наличие перегрузки — это прежде всего чрезвычайно высокая доля отброшенных пакетов, которую и следует минимизировать, учитывая стоимость обслуживания и временные предпочтения пользователей, старающихся в свою очередь максимально увеличить скорость передачи пакетов с учетом платы за трафик и вторичную пересылку. Рассмотрение совокупности пользователей, как группы стохастических автоматов, с одной стороны минимизирующих собственные потери, а с другой — демонстрирующих некоторое "целесообразное" (обеспечивающее устойчивость системы) поведение, несомненно являлось бы перспективным методом исследования, если бы не некоторые сложности автоматного подхода. Типовые подходы к автоматным стратегиям подразумевают достаточно длинные (в пределе бесконечные) интервалы функционирования и направлены на достижение некоторых устойчивых (равновесных по Нэшу) стратегий [8]. При этом, однако, вопрос существования единственной стратегии остается открытым. Тем не менее марковское описание игры автоматов является перспективным, хотя

при попытке решения задачи аналитическими методами возникают серьезные трудности.

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

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

Из-за присущей сети Интернет хаотичности, процесс передачи данных всегда имеет стохастическую и нестационарную природу. Впервые стохастический подход к проблемам, возникающим в процессе передачи данных, был предложен Пьером Бремо [9], [10]. В предложенном им мартин-гальном подходе к описанию потоков данных он применил методы оптимального стохастического управления к входящему потоку, описываемому в терминах марковских цепей. Мартингальное описание алгоритма "прореживания" входного потока с целью придания ему заданных характеристик,

предложенное П. Бремо, являлось первым строгим описанием появившегося позже вероятностного метода отбрасывания пакетов, реализованного позже в алгоритмах типа RED.

Многие авторы применяют управление марковскими цепями к передаче данных и оптимизации Интернет сетей, однако, большинство результатов, полученных до недавнего времени, относятся к стационарному случаю, в котором, как и в жидкостных моделях, система массового обслуживания устойчива, т.е. интенсивность входящего потока в среднем меньше скорости обслуживания [11], [12], [13]. Поскольку в реальной жизни данное условие выполняется не всегда, для успешного функционирования система должна отклонять некоторые входящие пакеты, чтобы избежать перегрузки. Все существующие протоколы TCP работают по данному принципу. Примером могут служить хорошо известные протоколы TCP Reno, TCP Red, а так же все основные методы управления перегрузками в Интернете. В то же самое время, большинство существующих работ, связанных с анализом TCP не учитывают некоторые принципиальные особенности управления реальным потоком, они обычно рассматривают модели с дискретным временем и стационарные ECN (Explicit Congestion Notification - явное уведомление о перегрузке) потоки. Реальные потоки данных нестационарны и их характеристики зависят от управления. Теория, описывающая оптимальное управление такими системами, должна учитывать различные критерии, характеризующие качество работы системы. Как показано в [14], [15] оптимальное управление обеспечивает более стабильное поведение скорости передачи данных. Преимущества методологии, основанной на использовании стохастического управления, отмечались рядом авторов, работающих над оптимизацией TCP (TCP Illinois и TCP Westwood+) и созданием высокоскоростных сетей передачи данных, работающих на большие расстояния,

а также в беспроводных сетях передачи данных [16], [17].

Оптимальное управление марковскими цепями известно давно [18], [19], [20], [21], [22], [23], [24]. В последние годы, был достигнуты серьезные результаты в области оценки и управления марковскими цепями с ограничениями. В ряде работ [25], [26], [27] рассматривались задачи совместного управления доступом в очередь и скоростью обслуживания, однако в них не учитывалось влияние этих управлений на интенсивность входящего потока. В результате исследования получен следующий принципиальный результат: решение проблемы оптимального управления с ограничениями может быть получено с помощью управления марковского типа и может быть найдено как решение детерминированной проблемы оптимального управления и с помощью численной процедуры, основанной на принципе максимума Понтрягина [28], [26], [25].

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

В то же время в данный момент не существует моделей управления перегрузками, учитывающих активное поведение пользователей, подстра-

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

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

Задачами диссертационного исследования являются:

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

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

• Математическое моделирование и исследование характеристик таких методов.

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

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

• Предложена математическая модель системы управления доступом в очередь и скоростью обслуживания в сетях передачи данных, учитывающая нестационарное активное (зависящее от управления) поведение пользователей;

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

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