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

005537387

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

Сапрыкин Алексей Николаевич

РАЗРАБОТКА МЕТОДОВ, АЛГОРИТМОВ И ПРОГРАММ МОДЕЛИРОВАНИЯ СЕТЕЙ С ДОЗИРОВАННОЙ БАЛАНСИРОВКОЙ НАГРУЗКИ

Специальность 05.13.18 - Математическое моделирование, численные методы

и комплексы программ

АВТОРЕФЕРАТ

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

7 НСЯ 2013

Рязань 2013

005537387

Работа выполнена на кафедре «Системы автоматизированного проектирования вычислительных средств» ФГБОУ ВПО «Рязанский государственный радиотехнический университет» (ФГБОУ ВПО РГРТУ»).

Научный Шибанов Александр Петрович

руководитель: доктор технических наук, профессор

каф. САПР ВС ФГБОУ ВПО «РГРТУ»

Официальные Каширии Игорь Юрьевич оппоненты: доктор технических наук, профессор

каф. ВПМ ФГБОУ ВПО «РГРТУ»

Старков Александр Владимирович

кандидат технических наук, старший преподаватель кафедры 604 ФГБОУ ВПО МАИ, г. Москва

Ведущая ФГУП «ГНПРКЦ «ЦСКБ-Прогресс» -

организация: «ОКБ «Спектр» (г. Рязань)

Защита состоится 18 декабря 2013 года в 12.00 часов на заседании диссертационного совета Д 212.211.02 в ФГБОУ ВПО «Рязанский государственный радиотехнический университет» по адресу: 390005, г. Рязань, ул. Гагарина, д.59/1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Рязанский государственный радиотехнический университет».

Автореферат разослан «2.8 » ОКтй «ГрА 2013 года.

Ученый секретарь диссертационного совета канд. техн. наук, доцент

Д.А. Перепелкин

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

Актуальность темы. В течение длительного времени проектировщики современных компьютерных сетей пытались решить проблему повышения их производительности в рамках протокола TCP/IP, на основе которого функционируют сети Интернет. Причина неудач заключается в том, что в управлении сетью участвуют два «игрока»: сетевые операторы, с одной стороны, и алгоритмы динамической маршрутизации - с другой. Пользовательские приложения не участвуют в управлении сетью. Выдвинутая недавно в Стэн-фордском университете концепция программно определяемых сетей (SDN) с использованием технологии OpenFlow подключает к управлению сетью множество приложений, которые могут направлять свой трафик на менее загруженные маршруты, пользуясь специальными контроллерами OpenFlow, через которые сообщается информация о состоянии сети в наиболее важных точках. 11ри этом пользовательские приложения получают доступ к таблицам маршрутизации узлов сети. Характерным свойством концепции SDN, является параллельная передача потока сразу по множеству путей через ряд транзитных участков. Одной из важнейших задач является повышение производительности и отказоустойчивости наиболее ответственных участков сетей при передаче информации реального времени, например, видеоконференций, IP-телефонии, команд управления техническими системами ti т. п.

Поэтому задача создания средств моделирования и оптимизации отказоустойчивых сетей с двухфазной маршрутизацией с перераспределением на1рузки но множеству параллельных путей (сетей VLB) с участием приложений на основе технологии OpenFlow является актуальной. Актуальность работы подтверждается тем, что она выполнена при финансовой поддержке Российского фонда фундаментальных исследований в форме грантов 07-07-00146-а и 11-07-00121-а.

Степень проработанности темы. Принципиальный скачок в развитии архитектуры современных сетей предопределил появление значительного числа исследований по организации оптимальной структуры сетей нового поколения и методов управления трафиком в них. Первыми, и наиболее существенными, являются проекты исследовательской группы Принстонского университета, га участников которой в первую очередь следует отмстить Jennifer Rexford, Jiayue Не, Martin Suchara, Ma'ayan Bresler, and Mung Chiang. Большое число исследований выполнено и другими учеными, например, F.P. Kelly, А. Maulloo, and D. Tan, S.H. Low. X. Lin, N.B. Shro, J. Wang, T.. Li, S.H. Low, J.C. Doyle, H. Han, S. Shakkottai, C'.V. Hollot, R. Srikant, D. Towsley, J. Mo, J.C. Walrand и др. Технология OpenFlow в России только начинает развиваться с поставкой оборудования из США, по в части разработки математических алгоритмов можно отметить большое число работ так или иначе связанных с управленцем многопотоковым трафиком. Эти проблемы исследовали, например, Баканов A.C., Вишневский В.М., Корячко В.П., Ляхов А.И., Батарин Г.П., Бочаров П.П., Коган Я. А., Захаров Г.П., Шибанов А.П., и многие другие.

Наиболее совершенный метод управления реализуется в многопутсвом протоколе TRUMP - {Traffic-management Using Multipath Protocol), разработанным в Принстонском университете. Он представляется распределенным, адаптивным, надежным, гибким и простым в управлении. Однако в данном протоколе существует функциональный сдвиг в сторону AS. Настройка весов линий, оценка состояния каналов, их загрузки, нахождение наилучших путей при маршрутизации производится в рамках AS, и при этом могут возникнуть проблемы плохой стыковки частей маршрутов «из конца в конец». Сеть, постро-

?

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

Целью работы является создание математического обеспечения для:

оценки ВВХ и надежности функционирования неоднородного агрегированного базового канала VLB-сети, являющегося основой построения сетевой канальной инфраструктуры с дозированной балансировкой нагрузки;

оценки функционирования AS па основе VLB-сетей и технологии OpenFlow;

оптимизации структуры и показателей качества сетей типов «цепь» «кольцо» «дерево». «ячеистая сеть», построенных из AS, функционирующих на основе концепции VLB-сетей и технологии OpenFlow.

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

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

2. Разработка методов синтеза сетей с дозированным распределением нагрузки по параллельным путям без использования явных обратных связей по магистральным кана-

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

4. Создание методов, алгоритмов и методик распределения полосы пропускания каналов оез проведения перемаршрутизации сети: 1) в случае отказов каналов или коммутационных устройств; 2) при возникновении пульсаций; 3) при необходимости создания виртуальных канатов явной обратной связи.

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

6. Создание методов, алгоритмов, программ и методик их применения для нахождения заданного резерва полосы пропускания каналов сети с дозированной балансировкой нагрузки с нахождением решения, близкого к глобальному экстремуму.

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

Научная новизна работы заключается в следующем.

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

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

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

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

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

Основные положения, выносимые на защиту.

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

2. Не имеющий аналогов метод моделирования характеристик агрегированного базового каната сети с дозированной балансировкой нагрузки, функционирующего по технологии OpenFIow, с функцией предварительной обработки простейших входных потоков, реализуемый па основе сети массового обслуживания М/М/1-M/G/1.

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

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

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

Достоверность научных положений определяется:

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

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

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

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

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

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

Апробация работы. Результаты настоящей работы докладывались и обсуждались на 7 всероссийских и международных конференциях и семинарах, в том числе на 14-18-й Всероссийских научно-технических конференциях «Новые информационные технологии в научных исследованиях и образовании» (Рязань, 2009, 2010, 2011, 2012, 2013); 13-й международной телекоммуникационной конференции «Молодежь и наука» (Москва, МИФИ 2009); 16-й международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (Рязань, 2010).

Публикации. Опубликовано 11 работ, в том числе 2 статьи в рецензируемых научных журналах, рекомендованных ВАК РФ для опубликования основных научных результатов диссертаций, - «Системы управления и информационные технологии» «Вестник РГРТУ».

Опубликовано 7 материалов докладов международных и всероссийских конференций и семинаров; опубликовано 2 статьи в межвузовских сборниках РГРТУ.

Реализация и внедрение результатов работы. Исследования по тематике диссертационной работы проводились по НИР 16-07Г, 14-11Г (гранты 07-07-00146-а, 11-07-00121-а Российского фонда фундаментальных исследований). Результаты внедрены в Филиале ФГУП ГПП РКЦ «ЦСКБ-Прогрссс»-ОКБ «Спектр» при проектировании перспективных образцов системы сбора и передачи информации, поступающей в реальном времени от измерительных систем, а также внедрены в учебный процесс в ФГБОУ ВПО Рязанский государственный радиотехнический университет.

Структура работы. Диссертация содержит 147 страниц основного текста и состоит из введения, четырех глав, заключения, библиографического списка из 97 наименований и 4 приложений на 38 страницах. В диссертацию включено 56 рисунков и 4 таблицы.

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

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

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

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

В настоящее время в Интернете управление трафиком охватывает контроль перегрузки (на конечных хостах), протоколы маршрутизации (на маршрутизаторах) и управление трафиком (по сети операторов). В работах Martin Suchara, Ma'ayan Bresler, Jennifer Rexford, Mung Chiang рассматривается управление трафиком с помощью последних инноваций в теории оптимизации. Предлагается целевая функция, которая учитывает цели конечных пользователей и сетевых операторов, и строится интегрированный протокол управления трафнком TRUMP. Он является распределенным, адаптивным, падежным, гибким и простым в управлении. Кроме того, TRUMP может работать с неявной обратной связью на основе сведений о потере пакетов и возникающих задержках. Он имеет малое количество настраиваемых параметров.

Для построения алгоритма TRUMP объединяются лучшие части всех ранее разработанных алгоритмов. Для максимизации совокупной полезности с участием источников и линий используется протокол DUMP (Dual-based Utility Maximizing Protocol). Кроме того, используются распределенные алгоритмы оптимизации, основанные на множественных разложениях алгоритма DUMP; частично-двойственный алгоритм, субградиентное обновление прямой и двойственной задач, полный дуальный алгоритм. Авторы объединили лучшее из каждого алгоритма для построения TRUMP. Однако это объединение не является следствием прямого математического вывода, а полезные свойства «алгоритмов-предшественников» наследуются на качественном уровне. Поэтому алгоритм TRUMP является эвристическим. Следовательно, сходимость и оптимальность автоматически не гарантированы теорией оптимизации. Имеются доказательства сходимости TRUMP, когда сеть загружена слабо. Алгоритм TRUMP эффективно реагирует на изменения топологии и изменение трафика на небольших интервалах времени с реалистичной задержкой обратной связи.

Формально алгоритм TRUMP представлен следующим образом:

Цена обновления обратной связи: s, (/ +1)= р, (t + 1 )+ ql it + l),

Цена обновления потерь: P/{t +1) =

f

Цена обновления задержки: <7/ (f +1 )= W z'i/c'

V ' 1

( \

Обновление путь-скорость: ¿у + 0= тах1ш!ге£/(. ^х)

Здесь цена обновления обратной связи, I- номер итерации, Р/— цена потерь, цена задержки, Рр - размер шагав соответствии с ценой, с, — емкость линии Н\ равно 1. если путь ] из источника / использует линию 1, 0 - в противном случае, гу' (?)-

скорость передачи из источника i на j -м пути, w - переменная для взвешивания факторов, U, - мера для пары «источник - назначение», s, (t) - цена обновления обратной связи.

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

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

2. Сеть, построенная на алгоритме TRUMP, не имеет специальных механизмов контроля величины вариации пакетов и потоков или «джиггера», что может отрицательно сказаться на показателях качества передачи синхронной информации.

3. Для обеспечения хорошей сходимости и быстродействия в алгоритме TRUMP необходима подстройка параметров, например, переменной взвешивания факторов w.

4. 11ри оптимизации не гарантируется нахождение глобального экстремума.

5. Проведенное математическое моделирование на MATLAB и эксперименты на реальных сетях не в полной мере репрезентативны, и требуется проведение дополнитечь-ных исследований метода TRUMP.

На основании проведенного анализа предметной области сформулированы основные задачи диссертационной работы.

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

Потоки от __

измерительных Общий Г 1

систем пптп.. Часть потока 1 /г

V'i

Предварительная обработка

I

Подканал 1

Подканал 2

Общий поток

I

Очередь на предварительную обработку

Онередьк каналу

Часр. потока \jr2

Рис. 1. Схема базового канала сети с дозированной балансировкой нагрузки

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

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

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

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

чсское отклонение, а к — некоторое число. Чем меньше «джиттер» пакетов, тем выше качество передаваемого по компьютерной сети изображения или речи.

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

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

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

Предлагается метод расчета характеристик неоднородного базового канала без предварительной обработки, когда колебания задержки передачи пакетов в од "вене ти н е превышают 5 мс. Для моделирования «джитгера» пакетов используется нормГро-ванное распределение Орланга 2-го порядка с плотностью

Ш-ка{ках) е "*1{к-\)\. На рис. 2 изображена GERT-модель передачи пакета через неагрегированный канал.

s Kí>--->-Kg>---,<3> Г

Рис. 2. Модель передачи пакета через подканал

Эквивалентная производящая функция моментов времени передачи пакета через одно звено M^MaVV^-,)2. Моделирование передачи потока в одном подканале основывается на следующем подходе. Если случайная величина п является функцией случайной величины п = а? + Ь, где а и b константы, то Х„{с)=х,, где X„(Ö и Z&)- характеристические функции случайных величин r¡ и £ соответственно. Агрегированный канал состоит из 2 подканалов с разной производительностью или из 2 однородных каналов, „о при условии, что число посылаемь^ вних п ™„с одинаково (сами пакеты имеет одну и ту же длину). Установим типовую длшГ~ на входе агрегированного канала, которая делится на части, передаваемы, попо~ам Для случая передачи по подканалу связи потока в г раз меньще номинал но"™ ременную , заменяем на s/r. Тогда при произвольном , "ем:

Ml(r](s)=4r^c.P(sT r)/(2ra-sy . Плотность распределения времени передачи части потока по каналу находится с использованием теории аналитических фикций Выполняется замена z = -, и интехрирование по контуру Бромвича. Получа«™

<Pi(r)(t) = 4r2a-(t-T/r)e 2гп '"г г) и функцию распределения времени передачи потока

по подканалу /^l-«"^^-^!]. t-T/r> 0. Найдена производящая функция моментов времени передачи потока но агрегированному каналу

[i^W (^f е3 -S föif: (1)

где коэффициенты я- и в зависят от значения параметров 7",, Г2 , г,, г2, в, , «2 . По данному выражению найдены значения среднего времени передачи потока t и среднеквадратичен отклонение а, используемые в задачах оптимизации сетей VLB.

Предложен метод расчета базового канала передачи потока в cera с дозированной оаланспровкои нагрузки с простейшим входным потоком с общей интенсивностью^ Л Причем заявкой считается не пакет, а поток. Функционирование базового "Гп™та' чи потока в сети с дозированной балансировкой нагрузки отражается систеГи масео'вош

обслуживания M/G/1. Обработка потоков ведется в порядке поступления, а режим работы канала стационарный. Среднеквадратический коэффициент вариации времени передачи потока находится через первый и второй начальные момешы дифференцированием выражения (1). Найдены наиболее важные характеристики базового канала: среднее число потоков, проходящих через базовый канал Ñ ; среднее число потоков, находящихся в очереди О ; среднее время передачи потока через базовый канал Г ; среднее время нахождения потока в очереди W ; среднее время периода простоя базового канала; среднее время периода занятости базового канала VLB; распределение длины очереди потоков базового канала VLB.

На основе теории GERT-сетей предложена модель базового канала в сети с дозированной балансировкой нагрузки с учетом возможности отказа одного из подканалов.

Разработан не имеющий аналогов метод расчет характеристик базового канала при случайной длине входящего потока. Входной поток Гфедставлястся последовательностью пакетов, передаваемых без пауз. Число этих пакетов случайное, но закон распределения их числа задан производящей функцией вида ¿(z)=p,z + />,z2 + p3z3 +... + рnzn , где

Рь ■■■ Р„ - вероятности того, что в потоке содержатся один, два и т. д. пакетов одинаковой длины. Для нахождения математического ожидания, дисперсии, а также распределения времени передачи потока агрегированного канала находятся производящие функции числа пакетов, посылаемых в каждый подкапал. Число пакетов в потоке изменяется от 1 до п . Тогда в одном из каналов должно передаваться п j гх пакетов, а во втором -

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

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

I. Умножение исходных производящих функций. Пусть Д(г)= b0z° +... + bmzm и

C-(z) = c0z° + ... + crzr, причем b0 и сп не равны нулю одновременно, что означает, что

хотя бы один пакет потока поступает па вход агрегированного канала. При этих условиях определим функцию A(z)=B(z)C{z) = az] + z где коэффициенты определяются произведением вероятностей числа пакетов, выбираемых от двух различных источников потоков, в результате чего образуется общий поток.

II. Вероятностная смесь производящих функций. Формально это определяется-Áz) = qB{z) + {\-q)c(z)4qb0+{\-q)ca}za+... + {rtm+(i-q)Cm\z^m>r

и qba + (l - q)C{) ф 0 . с использованием этих двух типов преобразований миут быть покроены более сложные процедуры преобразований, составляющих вспомогательную -сеть, дуги которой характеризуются производящими функциями. Для определенного таким образом входного потока найдено распределение времени его передачи по базовому агрегированному каналу. Если случайное число пакетов на входе агрегированного канала определяется производящей функцией A(z)=ptz + p2z2 +... + pnz" , а вре-

передачи пакета выражением (1), то производящая функция моментов «(.?) времени

мя

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

а> (5)= р,Минюд(г)+ р2[мЯнеод(*)]2 + ... +р„[Мц неод(?)]" -

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

Xи неол(^) и применении формулы обращения

/(') = . (2)

-со

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

Предложен метод определения резерва полосы пропускания физического канала УЬВ-сети при условии, что в нем организуется множество виртуальных каналов для реализации следующих функций: 1) передачи потоков информации пользователей (задаются матрицей потоков); 2) создания резервных каналов для оперативного перенаправления потоков с отказавших путей без проведения перемаршрутизации; 3) планирования дополнительных каналов для организации явных обратных связей в сети.

Для нахождения оценок «джиггера» определяется дисперсия суммы вспомогательных случайных величин, выраженных не непосредственно в единицах времени (в миллисекундах), а в мегабитах в секунду. Тогда выражения для функции распределения вероятностей, плотности распределения вероятностей и производящей функции моментов времени передачи потока через эрегированный канал связи нужно соответственно обозначить: ^//нсод(г), </>цнсод (г), Мйнеод(5), где переменная времени I заменена на переменную скорости передачи г . Тогда эквивалентная производящая функция моментов полосы пропускания физического капала, определяющего совокупный «джиттер»

Л'

//неодЛ5)' Плотность распределения вероятностей находится численно по

;=1

формуле (2). По производящей функции моментов А/£(.у) находится соответствующая

■V

характеристическая функция ХЕ{^)= ц »^¡(С) и ее действительная и

г=>

мнимая 1т XЕ (с) части во всех узлах интерполяции. Вычислительная сложность метода оценивается как О(пт), где п - число узлов интерполяции, т - число потоков, передаваемых через канал в данный момент врелетш.

В третьей главе предложен не имеющий аналогов метод расчета характеристик параллельного тракта передачи потока в сети с дозированной балансировкой на1рузки в рамках технологии ОрепР1о\¥, основанный на разложении подинтегральной функции при нахождении плотности распределения по формуле Бромвича-Вагнера в ряд Лорана в ок-

рестности бесконечно удаленной точки. В сети VLB 'одновременно передается множество потоков. По каждому пути от источника % к узлу назначения j (i,j = \,N j) поток передается через промежуточный узел к. Каждый ¡входной поток сети может распределяться между двумя промежуточными узлами к = 1, N - 2; к * i, кф j . На основе автономных VLB-систем строятся сети типов: «цепь», «кольцо», «дерево», «ячеистая сеть» (рис. 3).

Рис. 3. Сеть VLB и структуры «а ее основе

Для нахождения плотности распределения вероятностей времени передачи потока по сетевому тракту, в котором используется базовый агрегированный канал (без агрегирования на уровне VLB-сети), используется GERT-сетъ, состоящая из последовательно соединенных дуг (рис. 4).

м^) MtiU?) M$Us) MfrUs)

s ко *—ю——Ю—— ——КО'

12 3 „

Рис. 4. Стохастическая модель пути передачи

п

Эквивалентная »-функция данной GERX-ccnc ^E(s)=]~[Af{;'Heuii(<;), гдеМ^неод(^)

;=i

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

Л/2ф(.?) ■ При г = -5 находятся функции Функция Ф (z)= Ф1ф($) Ф2ф{з) в

полуатоскости Rez<0 удовлетворяет условиям леммы Жордана, и интеграл, взятый

вдоль контура Бромвича (рис. 5), равен сумме вычетов функции Ф (г) относительно всех ее особенностей.

Особые точки функции Ф(г) лежат левее начала координат

Рис. 5. Положение особых точек функций Ф и Ф2ф(г) в контуре Бромвича

Плотность распределения вероятностей передачи потока через одну фазу <рф (?) находится через сумму вычетов через разложение Лорана в окрестности точки г = со

п(0=

1 Г „А'-Ь п)

2от

■л

г, я-,-лъг

- + -!-=-+-+ -

а г.

((9,+г)2 {в2 + г)2 в. + г (<93 + г)2 +

Существует особая точка при г = оо . Выполняя преобразование г = 1/и< , получаем разложение Лорана в окрестности точки и» = 0 :

7Г, - ;Г31 И' Я'з

(<93 +1 + я-4(б»3 +1 и>)+ л

(«?3 +1 н-)3

При малых и* разложение Лорана в окрестности нулевой точки Г-Г, г, (/-Г, г,)2 (/-Г, г,)3 1

1 + -

... \[к2 м2 +А:4 IV4 + ...). Для

IV-1! и.-2 -2! IV3-3!

получения разложения подинтегральной функции в ряд Лорана в окрестности точки 2-оо выполним обратное преобразование переменных уи=г~'

'^-туг.^-г, г,)У ^Г-Г. г,)3;3

х-1 '

Теперь плотность распределения вероятностей р.ф(г) определяется значениями коэффициентов при первой отрицательной степени z :

+~к.^-ТУ1г,У + ....

В четвертой главе рассматриваются методы оптимизации структуры и показателей качества сетей при балансировке потоков при ограничениях по «джиттеру» пакетов в автономных VLB-системах, соединенных пиринговыми ¡каналами (рис. 6). Сеть состоит из AS VLB. Каждая из них имеет свой внутренний трафик, а кроме того, каждая из AS VLB передает и принимает информацию от соседней VLB-системы через пиринговые каналы. Задаются: предельно допустимые значения загрузки каналов, необходимый резерв полосы пропускания каждого канала, матрицы внутреннего трафика в автономных VLB-системах, матрица трафика между автономными VLB-систсмами, матрицы ограничений на задержки и «джпттер» при передаче потоков. Максимизируется совокупная резервная мощность параллельных путей передачи. 1

А г, v^ ^v

Рис. 6. Автономные VLB-системы пиринговыми каналами

Каждая линия I имеет фиксированную предельную скорость передачи С/. , Од-)

Сеть ЛХВ-1

С

Пиринговые к.шатты

Сеть VLB-'

Обозначим через РI '"' долю трафика от маршрутизатора ] к маршрутизатору к, который проходит по линии /. В процессе многолутевой маршрутизации устанавливаются

( / О

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

. Штрафная функция g является выпуклой, неубывающей и дважды диф-

/

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

(„Р и ее вариации & пр в пути I представляется как

минимизировать ]Гехр

.м $

при условии ^ X '

¡■к

Для нахождения решения используется гевстэтеский алгоритм. На рис. 7 представлен пример кодирования хромосомы для двух автономных 'УТВ-систем, соединенных между собой пиринговыми каналами.

Хромосома (часть.. 1)

Пр оыЕжутэчжк' узлы

1-й часта части для. 1-й части дашХ-йчасти

потока в сети I потока в сети I потакая еешГ лщв в сети I

Рис. 7. Слруктура хромосомы

I I II1 I

|о| ПоПЮЮЮЮ! 1 ЮН 10ЮЮ11!оИ №101.11'-сПИ!1ШЮЮ1о]

Хросмоеома (часть- 2}

Конечный узел для

?!д 1-й части, 2-й части

Промежуточ ныйузел 3-й части потока в сети!

потока в сети!

потока в- сетаИ.потока в сети II

I

т ] о |о} 11111 {11 о 111 о I о |о! о 111 о-]; г; 11 о | т |;11 |.о | о |:г ¡а | о} г I о I

Хромосома (часть 3)

Промежуточные узлы

Проме-нсуто-ч-ньйузе-л 1-й для 1-й части для 2-й части части потока потока всетиИпотокавсетиП в сети Н

Начальный узел для потока нсетиП

I

I

I

Хромосома описывается: оаланси-ровочными параметрами q[1, д 2/, Ци,, Цщ для первой и второй

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

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

Для выхода алгоритма из: возможных "тупиковых" ситуаций используется оператор мутации, который производит случайное изменение каждой позиции в хромосоме с вероятностью 5-10 %. Запрещенными считаются хромосомы, в которых после скрещивания получаются недействительные номера узлов, а также те из них, для которых не выполняются ограничения по задержкам и «джиттеру». Отбор в новое поколение происходит по методам турнирного отбора и хштизма. Чтобы избежать потери хорошего промежуточного решения, заданное число особей формируется с использованием стратегии элитизма. Для этого популяция сортируется по убыванию функции полезности, после чего лучшие особи гарантированно переходят В; новое поколение. Такой подход позволяет анализировать различные варианты хромосом из пространства поиска. Остальное количество необходимых для скрещивания особей выбирается турнирным отбором. В реализованной программе предусмотрена выдача графика функции приспособленности и диаграмм суммарных нагрузок на каждый канал после оптимизации. На рис. 8 изображена типовая диа-1рамма загрузки автономной УЬВ-системы до и после оптимизации.

Нагрузка Мбит/с)

1»

I С' | о 1 о 11111 о! 111111 о I о I о 1 о 11111 г I о 1 о | о.} о |: 1И |о|оТо1

I

Рис. 8. Нагрузка каналов автономной У1.В-системы до и после оптимизации

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

¡5-1 6-1 <5-4 6»? Обозначения пугей

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

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

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

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

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

2) Разработана не имеющая аналогов модель базового канала с предварительной обработкой нескольких входных потоков на основе двухфазной сети массового обслуживания M/M/1-M/G/1. При этом произвольный закон распределения времени передачи потока по базовому каналу находится на основе модификации численного метода нахождения плотности распределения вероятностей выходной величины GERT-cern.

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

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

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

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

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

Статьи в изданиях, рекомендованных ВАК

1. Ижванов Ю.Л., Корячко В.11.» Шибашв А.П., Лукьянов О.В., Сапрыкин А.Н. Оптимизация сети с дозированной балансировкой нагрузки // Системы управления и информационные технологии. Москва-Воронеж,.2012. № 3(49). С. 37-42.

2. Ижвапов Ю.Л., Корячко B.1L. Шибанов А.П., Лукьянов О.В., Сапрыкин А.Н. Оптимизация сетей с дозированной балансировкой нагрузки и пиринговыми каналами // Вестник РГРТУ, 2013. № 1 (выи. 4Т). С. 67-74.

Другие публикации

3.Сапрыкин А.Н. Применение'генетических алгоритмов для огггимизацйи структуры односегментной сети Ethernet нш основе: коммутатора с разноскоростными портами // Тез. докл. XIV Всероссийской научио-тазшической конференции «Новые информационные технологии в научных исследования!«; и. в образовании». Рязань: РГРТУ, 2009. С. 99100.

4. Славнов К.А., Рябов Д.А.,. Сапрыкин А.Н., Жеребцов Н.Б. Оптимизация базовой опорной сети Интернет // Тез. докл1. XLLT Международной телекоммуникационной конференции молодых ученых и студентов «Молодежь и паука». Москва, 2009.

5. Сапрыкин А.Н. Генетический! алгоритм балансировки нагрузки портов коммутатора // Межвузовский сборник научных-, трудов «Информационные технологии в научных исследованиях». Рязань: РГРТУ, 201:0. С. 116-119.

6. Сапрыкин А.Н. Выбор оптимальных: структур корпоративных сетей передач данных // Тез. докл. XVI Международной научно-технической конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТУ,

2010. С. 160-162.

7. Сапрыкин А.Н. Выбор оптимального-числа резервных каналов в сетях SDH // Тез. докл. XV Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях, к В'образовании». Рязань: РГРТУ, 2010. С. 84.

8. Сапрыкин А.Н. Метод моделирования первичных сетей с учетом резервирования каналов // Тез. докл. XVI Всероссийской, научно-технической конференции «Новые информационные технологии в научных исследованиях и в образовании». Рязань: РГРТУ,

2011.C. 90-91.

9. Сапрыкин А.Н. Оптимизация, сетей, е. дозированной балансировкой нагрузки с учетом сценариев отказов // Тез. докл.. XVII Всероссийской научно-технической конференции «Новые информационные технологии- в: научных исследованиях и в образовании». Рязань: РГРТУ, 2012. С. 154-156.

10. Шибанов А.П., Сапрыкин- А.П.. Зотов А.И. Оптимизация сетей с VLB-маршрутизацией пирингового трафика // Межвузовский сборник научных трудов «Информационные технологии в образовании». Рйзань: РГРТУ, 2012. С. 163-166.

11. Сапрыкин А.Н. Агрегирование, параллельных потоков информации в сети с дозированной балансировкой нагрузки. // Тез. докл. XVIII Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и в образовании». Рязань: РГРТУ, 2013.

Сапрыкин Алексей Николаевич

РАЗРАБОТКА МЕТОДОВ, АЛГОРИТМОВ И ПРОГРАММ МОДЕЛИРОВАНИЯ СЕТЕЙ С ДОЗИРОВАННОЙ БАЛАНСИРОВКОЙ НАГРУЗКИ

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

Подписано в печать 22.10.2013 г. Формат бумаги 60x84/16. Бумага офсетная. Печать ризографическая. Усл. печ. л. 1.0. Тираж 100 экз.

Отпечатано в ЗАО «Колорит». 390013, г. Рязань, Первомайский проспект, д. 37/1.

ФГБОУ ВПО "Рязанский государственный радиотехнический университет"

На праваэиэукописи 04201452846 ¿Оп^

Сапрыкин Алексей Николаевич

Разработка методов, алгоритмов и программ моделирования сетей с дозированной балансировкой нагрузки

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

программ

ДИССЕРТАЦИЯ

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

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

доктор технических наук, профессор,

Шибанов Александр Петрович

Рязань 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.......................................................................................... 6

ГЛАВА 1. Современные проблемы многопутевой маршрутизации. Задачи диссертационной работы...................................................................... 17

1.1. Технология открытых потоков Open Flow................................... 17

1.2. Организация управления трафиком по протоколу TRUMP........ 20

1.3. Протокол управления трафиком DUMP....................................... 22

1.4. Распределенные алгоритмы оптимизации, основанные на множественных разложениях алгоритма DUMP........................................................ 27

1.4.1. Эффективная мощность (емкость)............................................ 28

1.4.2. Локальная оптимизация: частично-двойственная.................... 28

1.4.3. Субградиентное обновление прямой и двойственной задач.... 29

1.4.4. Согласование цены: полный дуальный алгоритм..................... 30

1.5. Использование штрафной функции............................................. 30

1.6. Исследование свойств сходимости алгоритмов.......................... 32

1.7. Взвешивание полезности пользователя и стоимости оператора 34

1.8. Сравнение алгоритмов между собой............................................ 36

1.9. TRUMP: математический алгоритм............................................. 37

1.10. TRUMP: переход к сетевому протоколу.................................... 40

. 1.11. Открытые проблемы в оптимизации управления трафиком .... 43

иш^оишл ..............................................

ертационной работы................................................

езультаты .................................................................

ый канал передачи потока в сети с дозированно:

гтов и потоков при агрегировании каналов

ние передачи пакетов и потоков без учета вли 5отки .........................................................................

УЬВ-сети.......................................

2.10. Основные результаты

82

ГЛАВА 3. Расчет параллельного тракта передачи потока в сети с дозированной балансировкой нагрузки ....................................................... 83

3.1. Цели оптимизации полномасштабной сети, построенной на основе архитектуры автономных систем VLB ........................................................ 83

3.2. Метод расчета вероятностно-временных характеристик каналов, путей и трактов VLB-сети. Общие положения............................................ 88

3.3. Расчет плотности и функции распределения вероятностей времени передачи потока в автономной VLB-сети.................................................... 93

3.4. Расчет функции распределения вероятностей времени передачи потока в автономной VLB-сети при многопотоковой маршрутизации ......... 106

3.5. Основные результаты................................................................... 107

ГЛАВА 4. Оптимизация сетей с дозированной балансировкой нагрузки и пиринговыми каналами.............................................................................. 108

4.1. Моделирование и оптимизация функционирования коммутатора сети с дозированной балансировкой нагрузки ............................................ 110

4.2. Балансировка потоков при ограничениях по джиттеру пакетов в автономной VLB-системе................................................................................. 121

4.3. Балансировка потоков при ограничениях по джиттеру пакетов в двух автономных VLB-системах, соединенных пиринговыми каналами .. 127

4.4. Основные результаты................................................................... 133

ЗАКЛЮЧЕНИЕ ................................................................................... 134

БИБЛИОГРАФИЧЕСКИЙ СПИСОК................................................. 138

ПРИЛОЖЕНИЕ 1. Проверка корректности нахождения производящей функции моментов времени передачи потока по неоднородному агрегированному каналу............................................................................................... 148

ПРИЛОЖЕНИЕ 2. Имитационное моделирование функционирования базового канала при передаче потока в сети с дозированной балансировкой нагрузки с предварительной обработкой информации................................ 152

ПРИЛОЖЕНИЕ 3. Исходный код основных процедур программы оптимизации сетей с автономными системами с дозированной балансировкой нагрузки по параллельным путям с использованием генетических алгоритмов............................................................................................................. 165

ПРИЛОЖЕНИЕ 4. Акты внедрения.................................................... 183

ВВЕДЕНИЕ

Актуальность темы. В течение длительного времени проектировщики современных компьютерных сетей пытались решить проблему повышения производительности сетей, обеспечения гарантированных задержек передачи пакетов и их вариации в рамках протокола TCP/IP, на основе которого функционируют современные сети Интернет. Определенные успехи достигнуты за счет внедрения технологии многопротокольной коммутации по меткам (MPLS), которая относительно Интернет является «вставкой» в пределах «облака» MPLS другой технологии — создания заранее сконфигурированных виртуальных каналов с постоянным соединением. Другой подход связан с применением «физических усилителей» — сетей DWDM с мно-голямбдовой коммутацией, в которой по одномодовому кабелю передается не одна длина волны (несущая, например, поток со скоростью 10 Гбит/с), одновременно 40, 80 и даже больше длин волн, что позволяет в принципе добиться терабитных скоростей передачи.

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

ется обобщенная информация о состоянии сети в ее наиболее важных точках. Пользовательские приложения получают доступ к таблицам маршрутизации узлов сети, помещая свои программы в контроллер OpenFlow, связанный специальным каналом с маршрутизатором. Характерным свойством концепции SDN, приходящей на смену протоколу TCP/IP, является параллельная передача потока сразу по множеству параллельных путей передачи через ряд транзитных участков. Концепция SDN находится только в стадии попыток создания стандартов, и она породила множество вариантов архитектурных решений с использованием технологии открытых потоков Open-Flow.

Другим источником для проведения дальнейших исследований в рамках данной диссертационной работы стали идеи L.G. Valiant. Им была впервые предложена схема маршрутизации через случайно выбранный промежуточный узел в пути до места назначения пакета. Такая маршрутизация называется VLB-маршрутизацией с дозированной балансировкой нагрузки или двухфазной (двухканальной) маршрутизацией. В процессе проведения многих исследований сетевого VLB было показано, что применение VLB улучшает вероятностно-временные и надежностные характеристики сети.

Принципиальный скачок в развитии архитектуры современных сетей предопределил появление значительного числа исследований по организации оптимальной структуры сетей нового поколения и методов управления трафиком в них. Первыми, и наиболее существенными, являются проекты исследовательской группы Принстонского университета, из участников которой в первую очередь следует отметить Jennifer Rexford, Jiayue Не, Martin Suchara, Ma'ayan Bresler, and Mung Chiang. Большое число исследований выполнено и другими учеными, например, F.P. Kelly, A. Maulloo, and D. Tan, S.H. Low, X. Lin, N.B. Shro, J. Wang, L. Li, S.H. Low, J.C. Doyle, H. Han, S. Shakkottai, C.V. Hollot, R. Srikant, D. Towsley, J. Mo, J.C. Walrand и др. Технология OpenFlow в России только начинает развиваться с поставкой оборудования из США, но в части разработки математических алгоритмов

можно отметить большое число работ так или иначе связанных с управлением многопотоковым трафиком. Эти проблемы исследовали, например, Баканов А.С., Вишневский В.М., Корячко В.П., Ляхов А.И., Башарин Г.П., Бочаров П.П., Коган Я. А., Захаров Г.П., Шибанов А.П. и многие другие.

Наиболее совершенным на данный момент времени является многопутевой протокол (так в англоязычных источниках, точнее сказать метод) TRUMP - (Traffic-management Using Multipath Protocol), разработанный в Принстонском университете. Он представляется распределенным, адаптивным, надежным, гибким и простым в управлении, и имеет только один дополнительный настраиваемый параметр.

Однако данный метод не лишен и недостатков, что прямо констатируется его разработчиками. Метод TRUMP рассчитан на такое распределение функций между пользовательскими приложениями и операторами сети, что существует функциональный сдвиг в сторону автономных систем (AS). Настройка весов линий, оценка состояния каналов, их загрузки и сбор другой статистической информации выполняется в пределах AS. Нахождение наилучших путей при маршрутизации также производится в рамках AS. Поэтому, если потоки должны передаваться через несколько AS, в каждой из которых маршрутизация выполняется независимо, то могут возникнуть проблемы плохой стыковки частей маршрутов «из конца в конец». Протокол TRUMP использует явные обратные связи, что предполагает увеличение оборудования и удорожание системы. Алгоритмы TRUMP при возникновении пульсаций постепенно отрабатывают перегрузку, на что затрачивается определенное время. Это может приводить к неприемлемым потерям пакетов. Сеть, построенная на алгоритме TRUMP, не имеет специальных механизмов контроля величины вариации пакетов (и потоков) или «джитгера», что может отрицательно сказаться на показателях качества передачи синхронной информации, такой как видеоконференции, видеотрансляции, речевой и аудио- информации, управляющих команд и т. п. Для обеспечения хорошей сходимости и быстродействия в алгоритме TRUMP необходима

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

Поэтому задача создания свободных от вышеуказанных недостатков методов, алгоритмов и программ для моделирования и оптимизации сетей с дозированной балансировкой нагрузки по множеству параллельных путей (сетей VLB) с применением технологии открытых потоков, предназначенных для предварительного проектирования особо ответственных участков сетей с повышенными требованиями к производительности, надежности, отказоустойчивости и к показателям качества передачи пакетов и потоков, является актуальной. Актуальность работы подтверждается тем, что она выполнена при финансовой поддержке Российского фонда фундаментальных исследований в форме грантов 07-07-00146-а - «Разработка методов автоматизированного проектирования, моделирования и сопровождения многопротокольных конвергентных сетей» (2007 - 2009) и 11-07-00121-а «Методы автоматизированного проектирования, моделирования и сопровождения широкополосного Интернет G4 на основе развития теории GERT-сетей и генетических алгоритмов» (2011 -2013).

Соответствие паспорту специальности. Содержание диссертационной работы соответствует специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ». Согласно формуле специальности 05.13.18 ее содержанием является разработка фундаментальных основ и применение математического моделирования, численных методов и комплексов программ для решения научных и технических, фундаментальных и прикладных проблем. В работах, выполненных в рамках данной специальности, должны присутствовать оригинальные результаты одновременно из трех областей: математического моделирования, численных методов и комплексов программ.

Проблематика диссертации соответствует четырем областям исследований: 1) разработка новых математических методов моделирования объек-

тов и явлений; 2) развитие качественных и приближенных аналитических методов исследования математических моделей; 3) реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента; 4) разработка систем компьютерного и имитационного моделирования.

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

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

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

• оценки вероятностно-временных характеристик и надежности функционирования автономной сети на основе концепции VLB-сетей и технологии открытых потоков;

• оптимизации структуры и показателей качества сетей типов «цепь», «кольцо», «дерево», «ячеистая сеть», построенных из промежуточных автономных систем (AS), соединенных пиринговыми каналами, и функционирующими на основе концепции VLB-сетей и технологии открытых потоков.

Задачи исследований. Для достижения целей диссертационной работы необходимо решение следующих задач:

1. Разработка методов, алгоритмов и программ предварительного проектирования (на этапе эскизного проекта) сетей с дозированной балансировкой нагрузки, основанных концепции программно определяемых сетей

ББЫ и технологии открытых потоков ОрепБЪш при обеспечении централизованной стратегии распределения параллельных потоков по множеству каналов и передаче потоков через промежуточные автономные системы (АБ).

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

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

4. Создание методов, алгоритмов и методик распределения полосы пропускания каналов с учетом обеспечения резервов: 1) на случай отказов каналов или коммутационных устройств; 2) при возникновении пульсаций; 3) при необходимости реализации, в отдельных случаях, виртуальных каналов явной обратной связи. Решение о введении резерва в действие должно приниматься на локальном уровне в отдельных АБ без проведения перемаршрутизации сети.

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

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

7. Создание методов, алгоритмов, программ и методик их применения для нахождения заданного резерва полосы пропускания каналов сети с до-

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

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

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