Предотвращение перегрузок в сетях передачи данных с помощью методов стохастического управления тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Миллер, Александр Борисович

• Миллер, Александр Борисович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Миллер, Александр Борисович

Оглавление

Введение

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

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

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

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

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

1.2.3 TCP Reno

1.2.4 TCP Vegas

1.2.5 TCP Tahoe

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

управление

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

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

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

обнаружения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Предотвращение перегрузок в сетях передачи данных с помощью методов стохастического управления»

Введение

Интернет изначально представлял из себя компьютерную сеть, соединявшую Калифорнийский университет в Лос-Анджелесе, Стэнфордский исследовательский центр, Университет штата Юта и Университет штата Калифорния в Санта-Барбаре. С годами он эволюционировал в глобальную сущность, совершившую прорыв в средствах коммуникации, бизнесе и вычислениях. В самом начале развития сети Интернет было замечено, что неограниченный доступ к нему приводит к плохой производительности, а именно к высокой загруженности сети и потере передаваемых пакетов. Это привело к созданию первых методов управления перегрузками для сети Интернет [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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты работы использованы в рамках исследований по гранту РФФИ № 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 Decision and Control (Orlando, USA, 2011); семинарах ИППИ РАН и ИПУ РАН (Москва, 2011).

Публикации. Основные результаты диссертации опубликованы в статьях [29], [30] в изданиях из перечня ВАК, и в трудах международных

научных конференций [31]- [34].

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Миллер, Александр Борисович

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

Возьмем упрощенную модель беспроводной сети, аналогичную используемой в главе 3. Но допустим, что каждая оконечная станция может устанавливать связь с несколькими базовыми станциями. Пусть имеется й базовых станций. Подключение к нескольким ВС служит для повышения надежности связи и экономии энергии базовой станции [46]. ВС могут принадлежать разным провайдерам, соответственно, они могут иметь разные стоимости обслуживания и предоставлять отличное друг от друга качество связи. Предположим, что оконечная станция договаривается с каждой из ВС о выделении полосы пропускания при передаче трафика между терминальными станциями и оконечной станцией. При это в случае если пакет поступает в первую очередь, выделенную ВС]., и если он отклоняется с некоторой вероятностью, то повторный пакет посылается в дополнительную очередь, выделенную БС2 и т.д. Если пакет отклоняется в очереди, выделенной БС^, то он отклоняется окончательно.

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

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

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

4. Проведенное моделирование показывает эффективность использования дополнительной полосы пропускания в состоянии перегрузки.

Заключение

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

2. Исследована стохастическая модель управления потоками пакетов в беспроводной сети передачи данных, основанная на использовании теории управляемых марковских цепей. В данной модели учитывается активное поведение терминальных станций, генерирующих потоки пакетов, которые они посылают на оконечную станцию с одной полосой пропускания. Модель позволяет получить оптимальное управление доступом в очередь оконечной станции и скоростью обслуживания, с учетом естественных критериев, характеризующих функционирование сети. Модель основана на методах теории активных систем и учитывает функции полезности терминальных станций и различные критерии качества, характеризующие функционирование системы "терминальные станции-оконечная станция" при нестационарных внешних условиях. Показана эффективность алгоритма управления потоками данных на основе теории управляемых марковских цепей. Сравнение оптимального управления со стационарным управлением (использующим алгоритм RED) показывает более высокую эффективность первого.

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

Список литературы диссертационного исследования кандидат технических наук Миллер, Александр Борисович, 2012 год

Литература

[1] Jacobson V. Congestion avoidance and control // Proceedings of the ACM SIGCOMM. 1988. P. 314-329.

[2] Бутрименко A.B., Лазарев В.Г. Система поиска оптимальных путей передачи сообщений // Проблемы передачи информации. 1965. Т. 1, № 1. С. 80-87.

[3] Ginzburg S.L., Stefanuk V.L. п- automata game with single Nash point 11 Automat. Remote Control. 1970. № 8. P. 1264-1272.

[4] Стефанюк B.JI., Цетлин М.Л. О регулировке мощности в коллективе радиостанций // Проблемы передачи информации. 1967. Т. 3, № 4. С. 49-57.

[5] Стефанюк В.Л. Некоторые локальные критерии устойчивой регулировки мощности в коллективе радиостанций // Проблемы передачи информации. 1968. Т. 4, № 1. С. 90-91.

[6] Стефанюк В.Л. О локальных критериях устойчивого выбора уровня мощности // Проблемы передачи информации. 1969. Т. 5, № 3. С. 46-63.

[7] Stefanuk V.L. Collective Behaviour of Automata and the Problems of

Stable Local Control of a Large Scale System // Proceedings of the II IJCAI, London. 1971.

[8] Бутрименко A.B. Об играх автоматов, обладающих различной активностью // Проблемы передачи информации. 1967. Т. 3, № 4. С. 81-88.

[9] Bremaud P. Optimal thinning of a point processes // SIAM J. Control and Optimization. 1979. V. 17, № 2. P. 222-230.

[10] Bremaud P. Point processes and queues (Martingale dynamics) // New York: Springer Verlag. 1981. 354 p.

[11] Altman E. Constrained Markov Decision Processes // Boca Raton, FL: Chapman к Hall/CRC. 1999. 242 p.

[12] Altman E., Avrachenkov K., Barakat C. A Stochastic Model of TCP/IP with Stationary Random Losses // Comput. Commun. Rev. 2000. V. 30, № 4. P. 231-242.

[13] Altman E., Avrachenkov K., Barakat C. TCP in Presence of Bursty Losses // Perform. Eval. 2000. V. 42, № 2-3. P. 129-147.

[14] Miller В., Avrachenkov K., Stepanyan K., Miller G. Flow Control as Stochastic Optimal Control Problem with Incomplete Information // INRIA Report № 5239. 2004.

[15] Miller В., Avrachenkov K., Stepanyan K., Miller G. The problem of the optimal stochastic control of a data flow with incomplete information // Problems of Information Transmission. 2005. V. 41, № 2. P. 150-170.

[16] Liu S., Basar Т. TCP-Illinois: A loss-and delays-based congestion control algorithm for high-speed networks // Performance Evaluation. 2008. V. 65, № 6-7. P. 417-440.

[17] Kliazovich D. Logarithmic window increase for TCP Westwood+ for improvement in high speed, long distance networks // Computer Networks. 2008. V. 52, № 12. P. 2395-2410.

[18] Feinberg E.A. Non-randomized Markov and Semi-Markov Strategies in Dynamic Programming // Theory of probability and its Applications. 1982. V. 27, № 1. P. 116-126.

[19] Feinberg E.A. Continuous-time Jump Markov Decision Processes: A Discrete-event Approach // Math. Oper. Res. 2004. V. 29. P. 492-524.

[20] Howard R. Dynamic Programming and Markov Processes // MIT Press. 1960. V. 3, № 49. 120 p.

[21] Kitaev M.Y., Rykov V.V. Controlled Queueing Systems // Boca Raton, FL: CRC. 1995. 287 p.

[22] Miller Bruce L. Finite state continuous time Markov decision process with a finite planning horizon // SIAM J. Control. 1968. V. 6, № 2. P. 266-279.

[23] Pliska S. Controlled jump processes // Stochastic processes and their applications. 1975. V. 3. P. 259-282.

[24] Serfozo R. Optimal Control of Random Walks, Birth and Death Processes and Queues // Advances in Applied Probability. 1981. V. 13, № 1. P. 61-83.

[25] Miller B., Miller G., Siemenikhin K. Optimal control of Markov chains with constraints // Proceedings of Joint 48th IEEE CDC and 28th Chinese Control Conference. 2009. P. 512-518.

[26] Miller B., Miller G., Siemenikhin K. Torwards the optimal control of markov chains with constraints // Automatica. 2010. V. 46. P. 1495-1502.

[27] Миллер Б.M., Миллер Г.Б., Семенихин К.В. Методы синтеза оптимального управления Марковским процессом с конечным множеством состояний при наличии ограничений // Автоматика и телемеханика. 2011. № 2. С. 111-130.

[28] Miller В. Optimization of stochastic networks via stochastic control // Труды VII Международной конференции по идентификации систем и проблемам управления. М: ИПУ. 2008. С. 385-397.

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

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

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

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

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

[34] 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.

[35] Семенов Ю.А. Алгоритмы телекоммуникационных сетей, раздел "Сети передачи данных. Методы доступа" // http://book.itep, раздел 4.4 Интернет.

[36] Srikant R. The mathematics of Internet congestion control // Boston: Birkhauser. 2004. 164 p.

[37] Вегешна III. Качество обслуживания в сетях IP // Глава 6. РНВ-политика: предотвращение перегрузки и политика отбрасывания пакетов. Cisco Press. 2003.

[38] Hale J., Lunel S. M. V. Introduction to functional differential equations // New York: Springer Verlag. 1991.

[39] Floyd S., Jacobson V. On traffic phase effects in packet-switched gateways // Internetworking: Research and Experience. 1992. V. 3, № 3. P. 115-156.

[40] Floyd S., Jacobson V. Random Early Detection Gateways for Congestion Avoidance // IEEE/ACM Transactions on Networking. 1993. V. 1, № 4. P. 393-413.

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

[42] Kelly F.P., Maulloo А.К., Tan D.K.H. Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability // The

Journal of the Operational Research Society. 1998. V. 49, № 3. R 237252.

[43] Low S.H. A duality model of TCP and queue management algorithms // IEEE/ACM Transactions on Networking. 2003. V. 11, № 4. P. 525-536.

[44] Welzl M. Network Congestion Control: Managing Internet Traffic // John Wiley & Sons Ltd. 2005. 282 p.

[45] Hardin G. The Tragedy of the Commons // Science. 1968. № 162. P. 1243-1248.

[46] Вишневский B.M., Ляхов А.И., Портной С.Л., Шахнович И.В. Широкополосные беспроводные сети передач информации // М.: Техносфера. 2005. 592 с.

[47] http://standards.ieee.org/about/get/802/802.ll.html

[48] http://standards.ieee.org/about/get/802/802.16.html

[49] Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Mesh-сети: в ожидании стандарта IEEE 802.11s // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. 2008. № 3. С. 98-106.

[50] Бурков В.Н. Основы математической теории активных систем // М.: Наука. 1977. 255 с.

[51] Миллер Б.М., Панков А.Р. Теория случайных процессов // М.: Физ-матлит. 2007. 320 с.

[52] Low S.H., Paganini F., Doyle J.C. Internet Congestion Control // IEEE Control Systems Magazine. 2002. P. 28-43.

[53] Ramakrishnan К., Jain R. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with Connectionless Network Layer // ACM Trans. Comput. Syst. 1990. V. 8, № 2. P. 158-181.

[54] Elliott R.J., Aggoun L., Moore J.B. Hidden Markov Models. Estimation and Control // New York: Springer Verlag. 1995. 373 p.

[55] Феллер В. Введение в теорию вероятностей и ее приложения // М.: Мир. 1984. Т. 1. 511 с.

[56] Ширяев А.Н. Вероятность // М.: Наука. 1980. 519 с.

[57] Davis М.Н.А. Markov Models and Optimization // London: Chapman к Hall. 1993. 308 p.

[58] Wan C.B., Davis M.H.A. Existence of optimal control for stochastic jump processes // SIAM Journal on Control and Optimization. 1979. V. 17, № 4. P. 511-524.

[59] Miller В., Mclnnes D. Management of dam systems via optimal price control // Procedia Computer Science. 2011. V. 4. P. 1373-1382.

[60] Delebecque F., Quadrat J.P. Optimal control of Markov Chains Admitting Strong and Weak Interactions // Automatica. 1981. V. 17, № 2. P. 281-296.

[61] Miller В., Mclnnes D. Optimal Management of a Two Dam System via Stochastic Control: Parallel Computing Approach // Proceedings of 50th IEEE CDC. 2011. P. 1417-1423.