Разработка методов, алгоритмов и программ моделирования сетей с дозированной балансировкой нагрузки тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Сапрыкин, Алексей Николаевич

• Сапрыкин, Алексей Николаевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Сапрыкин, Алексей Николаевич

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

иш^оишл

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

езультаты

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

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

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

УЬВ-сети

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

82

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Разработка методов, алгоритмов и программ моделирования сетей с дозированной балансировкой нагрузки»

ВВЕДЕНИЕ

Актуальность темы. В течение длительного времени проектировщики современных компьютерных сетей пытались решить проблему повышения производительности сетей, обеспечения гарантированных задержек передачи пакетов и их вариации в рамках протокола 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-сетей, теории вероятностей, теории аналитических функций комплексного переменного, теории массового обслуживания, теории имитационного моделирования, теории оптимизации, генетических алгоритмов.

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

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

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

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

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

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

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

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

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

2. Не имеющий аналогов метод моделирования характеристик агрегированного базового канала сети с дозированной балансировкой нагрузки, функционирующего по технологии OpenFlow, с функцией предварительной обработки простейших входных потоков, реализуемый на основе сети массового обслуживания M/M/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Г и отражены

в 5 отчетах по грантам 07-07-00146-а, 11-07-00121-а Российского фонда фундаментальных исследований.

Результаты исследований внедрены в Филиале ФГУП государственного научно-производственного предприятия ракетно-космический центр ЦСКБ-Прогресс - в Особом конструкторском бюро «Спектр» при проведении предварительного проектирования перспективных образцов системы сбора, и передачи информации, поступающей в реальном времени от измерительных систем.

Результаты, полученные в диссертационной работе, внедрены в учебный процесс студентов специальностей 210202_65, 230104_65; по направлениям бакалавров 211000_62, 230104_62 и магистров 211000_68, 230104_68 в ФГБОУ ВПО Рязанский государственный радиотехнический университет.

Копии актов о внедрении результатов диссертационной работы приведены в Приложении 4.

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

ГЛАВА 1. СОВРЕМЕННЫЕ ПРОБЛЕМЫ МНОГОПУТЕВОЙ МАРШРУТИЗАЦИИ. ЗАДАЧИ ДИССЕРТАЦИОННОЙ РАБОТЫ

1.1. ТЕХНОЛОГИЯ ОТКРЫТЫХ ПОТОКОВ OPEN FLOW

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

Протокол (и технология) используется для управления сетевыми коммутаторами (маршрутизаторами) с центрального устройства — контроллера сети (с сервера или персонального компьютера) [33, 63, 86, 93, 96]. Проприетарная программа осуществляет построение маршрута, создание карты коммутации и т. д. Контроллер формирует в сети прямые сетевые соединения с минимальными задержками передачи данных [94]. Он обеспечивает наполнение таблицы потоков, получение пакетов через безопасный канал от устройства. Могут быть реализованы, как простейший алгоритм с разделением пакетов по виртуальным частным сетям, так и сложная логика, влияющая на прохождение пакетов исходя из внешних причин (права доступа, загрузка серверов, приоритеты по обслуживанию и т. д.). Для расширения функциональности процессов коммутации, маршрутизации и обработки данных создаются внешние программные обработчики, которые не зависят от текущих прошивок оборудования и формируются на стороне специального внешнего приложения-контроллера. Приложения могут управлять низкоуровневыми потоками, например, можно определить, какие потоки пакетов допустимы и куда их следует направить в случае перегрузки какого-либо участка сети. Сетевую инфраструктуру можно настраивать таким образом, чтобы увеличивать полосу пропускания, оптимизировать задержки и добиваться экономии энергии [33]. Таким образом, с помощью OpenFlow функции управления

прохождением трафика через сеть, которые сейчас выполняются инфраструктурным оборудованием - коммутаторами и маршрутизаторами, можно передать владельцам сети (например, предприятиям), пользователям или приложениям [38, 75, 87]. Использование технологии Open Flow открывает, в частности, возможности построения более надежных и производительных первичных сетей [67, 72, 95, 97].

В работе [1] отмечается, что компьютеры и сетевое оборудование долгое время существовали независимо. Коммутаторы передавали данные, компьютеры их обрабатывали. В устройствах коммутации господствовали специализированные микросхемы - ASIC, нестандартные протоколы и операционные системы. До недавнего времени внесение сколько-нибудь принципиальных изменений в сетевое оборудование и протоколы являлось весьма трудным делом и было по силам лишь крупным заказчикам, производителям сетевого оборудования и стандартизирующим органам. Исследователи Стэн-фордского университета направили свои усилия на решение задачи управления таблицами коммутации коммутатора Ethernet. Именно технология Ethernet определяет высочайшие характеристики по скорости продвижения, передачи и фильтрации данных. Перехват управлением этими таблицами, позволяет произвольным образом управлять поведением и скоростными характеристиками коммутаторов, и параметрами передаваемых потоков данных в сети Ethernet.

В Ethernet для организации связей «каждый с каждым» нельзя обойтись без коммутаторов третьего уровня - маршрутизаторов. Это накладывает заметные ограничения на функциональность коммутатора и всей сети. Технология Open Flow позволяет организовать связи «каждый с каждым» на канальном уровне сетевого протокола. Задача контроллера OpenFlow состоит в принятии поступающего кадра, извлечения из него адреса и, если адресат есть в таблице коммутации, немедленной передаче кадра коммутационной матрице. В противном случае коммутатор по защищенному каналу отправляет запрос на центральный контроллер сети OpenFlow и на основании полу-

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

У OpenFlow и программируемой сетевой инфраструктуры для управления сетей есть несколько основных потенциальных преимуществ^]:

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

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

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

Список литературы диссертационного исследования кандидат наук Сапрыкин, Алексей Николаевич, 2013 год

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

1. Башилов Г. Программно-аппаратная идиллия, или OpenFlow // Журнал сетевых решений/LAN, 2011. № 09. С. 54-58.

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

3. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. - Харьков, ОСНОВА, 1997. - С. 112.

4. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: М.: Физматлит, 2010! - С. 317.

5. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. -М: Физматлит, 2003. - С. 432.

6. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. - Учебное пособие для вузов. - М.: Высшая школа, 1982. С. 256.

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

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

9. Клейнрок Л. Теория массового обслуживания. Перевод с англ. /Пер. И. И. Грушко; ред. В. И. Нейман - М.: Машиностроение, 1979. С. 432.

Ю.Корячко В.П., Кравчук Н.В., Шибанов А.П., Шибанов В.А. Основы теории GERT-сетей. -М.: Горячая линия-Телеком, 2010. С. 205.

11.Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. - М: Физматлит, 2006. - С. 272.

12. Лаврентьев М.А., Шабат Б. В. Методы теории функций комплексного переменного. М.: Наука, 1987. С. 688.

13. Олифер В., Олифер Н., Петрусов Д. ATM и MPLS враги или союзники? // Журнал сетевых решений LAN, 2002. № 12. С. 48-59.

14. Привалов И.И. Введение в теорию функций комплексного переменного. М.: Наука, 1984. С. 432.

15. Прицкер А. Введение в имитационное моделирование и язык СЛАМ II:-М.: Мир, 1987. С. 644.

16. Пчелин Б.К. Специальные разделы высшей математики. М.: Высшая школа, 1973. С. 462.

17. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудин-ского. - М,: Горячая линия - Телеком, 2006. - С. 452.

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

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

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

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

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

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

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

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

26. Шибанов А.П. Нахождение плотности распределения времени исполнения GERT-сети на основе эквивалентных упрощающих преобразований // Автоматика и телемеханика, 2003. № 2. С. 117-126.

27. Шибанов А.П. Обобщенные GERT-сети для моделирования протоколов, алгоритмов и программ телекоммуникационных систем: Докт. диссертация. Рязань: РРТА, 2004.

28. Шибанов А.П. Разработка программного обеспечения для моделирования локальных сетей Ethernet // Программирование, 2002. № 6. С. 6271.

29. Шибанов А.П., Кравчук H.B. Использование моделей GERT при оптимизации компьютерных сетей // Вестник Ряз. госуд. радиотехн. унив., 2007. Вып. 20. С. 69-75.

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

31. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. Т.1/Т.2. Пер. с англ. М.: Мир, 1984. С. 528/752.

32. Генетические алгоритмы. Электронный ресурс. // URL: http://www.iki.rssi.ru/ehips/Genetic.htm

33. Грин Т. OpenFlow в действии. Электронный ресурс. // Computerworld Россия, 2009. № 04. URL: http://www.osp.ru/cw/2009/04/6942317/

34. Anderson Е. J., Anderson Т. Е. On the stability of adaptive routing in the presence of congestion control // Proc. IEEE INFOCOM, 2003. Vol. 2. P. 948-958.

35. Bäck Т. Optimal mutation rates in genetic search // Proceedings of the Fifth International Conference on Genetic Algorithms, 1993. P. 2-8.

36. Bertsekas D. P. Nonlinear Programming. - Athena Scientific, 1999. Second ed. P. 780.

37. Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 1997. Second ed. P. 731.

38. Bianco A., Birke R., Giraudo L., Palacin M. Openflow switching: Data plane performance // IEEE ICC, 2010. P. 1-5.

39. Chiang M., Low S. H., Calderbank R. A., Doyle J. C. Layering as optimization decomposition // Proceedings of the IEEE, 2007. P. 255-312.

40. Chudasama C., Shah S. M., Panchal M. Comparison of Parents Selection Methods of Genetic Algorithm for TSP // IJCA Proceedings on International Conference on Computer Communication and Networks CSI-COMNET, 2011. Foundation of Computer Science, New York, USA. P. 102-105.

41. De Jong K.A., Spears W.M. An Analysis of the Interacting Roles of Population Size and Crossover // Proceedings of the International Workshop «Parallel Problems Solving from Nature» (PPSN'90), 1990. P. 38-47.

42. De Jong K.A., Spears W.M. A formal analysis of the role of multi-point crossover in genetic algorithms. // Annals of Mathematics and Artificial Intelligence, 1992. N. 5(1). P. 1-26.

43. Elwalid A., Jin C., Low S. H., Widjaja I. MATE: MPLS Adaptive Traffic Engineering//Proc. IEEE INFOCOM, 2001. Vol. 3. P. 1300-1309.

44. Feldmann A., Gilbert A. C., Huang P., Willinger W. Dynamics of IP traffic: a study of the role of variability and the impact of control // Proc. ACM SIGCOMM, 1999. P. 301-313.

45. Fischer S., Kammenhuber N., Feldmann A. REPLEX Dynamic Traffic Engineering Based on Wardrop Routing Policies // Proc. CoNEXT, 2006. P. 112.

46. Fogarty T. C. Varying the probability of mutation in genetic algorithms // Proceedings of the Third International Conference on Genetic Algorithms, 1989. P. 104-109.

47. Fortz B., Thorup M. Increasing Internet capacity using local search // Computational Optimization and Applications, 2004. Vol. 29. N. l.P. 13 - 48.

48. Gao R., Blair D., Dovrolis C., Morrow M., Zegura E. Interactions of Intelligent Route Control with TCP Congestion Control // Proc. of IFIP Networking, 2007. P. 1014-1025.

49. Gibben R. J., Kelly F. On packet marking at priority queues // IEEE Trans. Automatic Control, 2002. Vol. 47. P. 1016-1020.

50. Gwiazda T. D. Crossover for single-objective numerical optimization problems // Genetic Algorithms Reference, Lomianki, 2006. Vol. 1. P. 412.

51. Han H., Shakkottai S., Hollot C. V., Srikant R., Towsley D. Multi-Path TCP: A Joint Congestion Control and Routing Scheme to Exploit Path Diversity on the Internet // IEEE/ACM Trans. Networking, 2006. Vol. 14. P. 1260-1271.

52. He J., Bresler M., Chiang M., Rexford J. Towards Robust Multi-layer Traffic Engineering: Optimization of Congestion Control and Routing // IEEE J. on Selected Areas in Communications, 2007. N. 25(5). P. 868-880.

53. He J., Rexford J. Towards Internet-wide multipath routing // IEEE Network Magazine, 2008. N. 22(2). P. 16-21.

54. Holland J. H. Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence. -London: Bradford book edition, 1994. - P. 211.

55. Kandula S., Katabi D., Davie B., Charny A. Walking the Tightrope: Responsive Yet Stable Traffic Engineering // Proc. ACM SIGCOMM, 2005. P. 253-264.

56. Katabi D., Handley M., Rohrs C. Congestion Control for High Bandwidth-Delay Product Networks // Proc. ACM SIGCOMM, 2002. P. 89-102.

57. Kelly F. P., Maulloo A., Tan D. Rate control for communication networks: Shadow prices, proportional fairness and stability // J. of Operational Research Society, 1998. Vol. 49. P. 237-252.

58. Kelly F., Voice T. Stability of end-to-end algorithms for joint routing and rate control // ACM SIGCOMM Computer Communication Review, 2005. Vol. 35. P. 5-12.

59. Keslassy I., Kodialam M., Lakshman T., Stiliadis D. Scheduling schemes for delay graphs with applications to optical packet networks// High Performance Switching and Routing (HPSR), 2004. P. 99-103.

60. Key P., Massouli L., Towsley D. Path selection and multipath congestion control // Proc. IEEE INFOCOM, 2007. P. 143-151.

61. Lin X., Shroe N. B. Utility Maximization for Communication Networks with Multi-path Routing // IEEE Trans. Automatic Control, 2006. Vol. 51. P. 766-781.

62. Low S. H. A duality model of TCP and queue management algorithms // IEEE/ACM Trans. Networking, 2003. Vol. 11. P. 525-536.

63. McKeownN., Anderson T., Balakrishnan H., Parulkar G., Peterson L., Rexford J., Shenker S., Turner J. Openflow: Enabling Innovation in Campus Networks // ACM SIGCOMM Computer Communication, 2008. Review. Vol. 38. N. 2. P. 69-74.

64. Mo J., Walrand J. C. Fair End-to-end Window-based Congestion Control // IEEE/ACM Trans. Networking, 2000. Vol. 8. P. 556-567.

65. Paganini F. Congestion Control with Adaptive Multipath Routing Based on Optimization // Proc. Conference on Information Sciences and Systems, 2006. P. 333-338.

66. Palomar D., Chiang M. A tutorial on decomposition methods and distributed network resource allocation // IEEE J. on Selected Areas in Communications, 2006. Vol. 24. P. 1439-1451.

67. Sherwood R. Carving Research Slices Out of Your Production Networks with OpenFlow // SIGCOMM Demo, 2009. P. 129-130.

68. Shibanov A.P. Finding the distribution density of the time taken to fulfill the GERT network on the basis of equivalent simplifying transformation // Automation and Remote Control, 2003. Plenum Press New York, NY, USA. Vol. 64. Issue 2. P. 279-287.

69. Shibanov A.P. A Software Implementation Technique for Simulation of Ethernet Local Erea Networks // Programming and Computing Software, 2002. Plenum Press New York, NY, USA. Vol. 28. Issue 6. P. 349-355.

70. Sivanandam S.N., Deepa S.N. Introduction to Genetic Algorithm // Springer-Verlag, Berlin Heidelberg, 2008. P. 462.

71. Sivaraj R., Ravichandran T. A review of selection methods in genetic algorithm // International journal of Engineering Science and Technology, 2011. Vol. 3. N. 5. P. 3792-3797.

72. Software-Defined Networking: The New Norm for Networks // Open Networking Foundation, 2012. P. 1-12.

73. Tan K., Song J., Zhang Q., Sridharan M. A Compound TCP Approach for High-speed and Long Distance Networks // Proc. IEEE INFOCOM, 2006. P. 1-12.

74.Toomey W. TRUMP-a fast reliable transport protocol for distributed systems // Proceedings of IEEE Singapore International Conference, 1993. Vol. 2. P. 601-605.

75. Tootoonchian A., Ghobadi M., Ganjali Y. OpenTM: traffic matrix estimator for openflow networks // PAM, 2010. P. 201-210.

76. Valiant L.G. A scheme for fast parallel communication // SIAM Journal on Computing, 1982. N. 11(2). P. 350-361.

77. Van Haalen R., Malhotra R., De Heer A. Optimized routing for providing Ethernet LAN services // Communications Magazine, IEEE, 2005. N. 43(11). P. 158-164.

78. Voice T. Stability of Multi-Path Dual Congestion Control Algorithms // To appear in IEEE/ACM Trans. Networking. P. 1231-1239.

79. Wang J., Li L., Low S. H., Doyle J. C. Cross-layer optimization in TCP/IP networks // IEEE/ACM Trans. Networking, 2005. Vol. 13. P. 582-595.

80. Wei D. X., Jin C., Low S. H., Hegde S. FAST TCP: Motivation, architecture, algorithms, performance // IEEE/ACM Trans. Networking, 2006. P. 1246-1259.

81. Zhang X., Ansari J., Yang G., Mahonen P. TRUMP: Supporting Efficient Realization of Protocols for Cognitive Radio Networks // Proc. Of IEEE DySPAN, 2011. P. 476^187.

82. Zhang-Shen R., Kodialam M., Lakshman T.V. Achieving bounded blocking in circuitswitched networks // IEEE INFOCOM, 2006. P. 1-9.

83. Zhang-Shen R., McKeown N. Designing a Fault-Tolerant Network Using Valiant Load-Balancing // Proc. IEEE INFOCOM, 2008. P. 2360-2368.

84. Zhang-Shen R., McKeown N. Designing a Predictable Internet Backbone Network // HotNets III, 2004. P. 178-192.

85. Abilene Backbone. Электронный ресурс. URL: http ://abilene. internet2 .edu/.

86. Greene T. Researchers show off advanced network control technology. Электронный ресурс. // Network World, 2008. URL: http://www.networkworld.com/news/2008/102908-openflow.html

87. Handigol N., Seetharaman S., Flajslik M., McKeown N., Johari R. Plug-n-Serve: Load-Balancing Web Traffic using OpenFlow. Электронный ресурс. // ACM SIGCOMM Demo, 2009. URL: http://conferences.sigcomm.org/sigcomm/2009/demos/sigcomm-pd-2009-final26.pdf

88. He J., Bresler M., Chiang M., Rexford J. Rethinking Traffic Management: From Multiple Decompositions to A Practical Protocol. Электронный ресурс. // Princeton University CS Tech, 2007. Report TR-774-07. URL: http://www.cs.princeton.edu/research/techreps/TR-774-07.

89. He J., Rexford J. Towards Internet-wide Multipath Routing. Электронный ресурс. // Princeton University Tech, 2007. Report TR-787-07. URL: http://www.cs.princeton.edu/research/techreps/TR-787-07.

90. He J., Suchara M., Bresler M., Rexford J., Chiang M. From multiple decompositions to TRUMP: traffic management using multipath protocol. Электронный ресурс. // Elsevier Computer Networks, 2009. URL: http://www.cs.princeton.edu/~jrex/papers/ToN.pdf

91. He J., Suchara M., Bresler M., Rexford J., Chiang M. Rethinking internet traffic management: from multiple decompositions to a practical protocol. Электронный ресурс. // Proceedings of the 2007 ACM CoNEXT conference, New York, 2007. URL:

http://www.cs.princeton.edu/~jrex/papers/conext07.pdf

92. Lakshmikantha A., Dukkipati N., Srikant R., McKeown N., Beck C. Performance Analysis of the Rate Control Protocol. Электронный ресурс. // In submission. URL: http://yuba.stanford.edu/rcp/.

93. OpenFlow: The nextgeneration in networking interoperability. Электронный ресурс. // IBM, 2011. URL: http://public.dhe.ibm.com/common/ssi/ecm/en/qcw03010usen/QCW03010U SEN.PDF

94. Romero de Tejada Muntaner G. Evaluation of OpenFlow Controllers. Электронный ресурс. // 2012. URL: http://www.valleytalk.org/wp-content/uploads/2013/02/Evaluation_Of_OF_Controllers.pdf

95. Sherwood R. An Experimenter's Guide to OpenFlow. Электронный ресурс. // GENI Engineering Workshop, 2010. URL: http://www.rob-sherwood.net/

96. The OpenFlow Switch Specification. Электронный ресурс. // Version 1.1.0, 2011. URL: http://archive.openflow.org/documents/openflow-spec-vl.l.O.pdf

97. Tracy C. Introduction to OpenFlow: Bringing Experimental Protocols to a Network Near You! Электронный ресурс. // ESnet Engineering Group, 2010. URL: http://www.es.net/assets/Papers-and-Publications/NANOG50.Talk59.ChrisTracyNANOG500penFlow.pdf

ПРИЛОЖЕНИЕ 1. ПРОВЕРКА КОРРЕКТНОСТИ НАХОЖДЕНИЯ ПРОИЗВОДЯЩЕЙ ФУНКЦИИ МОМЕНТОВ ВРЕМЕНИ ПЕРЕДАЧИ ПОТОКА ПО НЕОДНОРОДНОМУ АГРЕГИРОВАННОМУ КАНАЛУ

Производящая функция моментов времени передачи потока по неоднородному агрегированному каналу:

МПисоА*) =

неод

- „ '1

л",

(ех-8)1 + (в2-з)2 Ч >э-')2>з-')3

Найдем српр(?) - плотность распределения вероятностей времени передачи пакета через агрегированный канал связи.

Воспользуемся интегрированием по контуру Бромвича-Вагнера

712 + ^

Я,

71,

7ТI

1

<Рпр{*)=у-. \е"Ф(г)Ыг, где

2 7Г1 •

-( оо

711

71-> —71т.2

71-

71,

71,

(б\+^)2 (б>2+г)2 6>з (б»3+г)2 (б>3+г)]

1 -г-

Л",

-(00 /оо

1 7

+- £Г<?

•тг/ J

Г,

-г—

2 Л"/

—(ОО

^ ¡00 ТГI 1

27И Г

-г—

Л "

л--

03

л-,

(57+91

¿/г

О? 2

1

Г, 712-71ъ2

* ■ . е е 7-+

I ^

7/

. /оо

-М

»7Г7* J

2л-/ •

-/00

Тг -ъ—

Л Г>

Л",

Найдем вычеты от отдельных слагаемых суммы.

г,

2 л"/ '

-г—

Л г'

1

Т\

т-Функция ф(г) = е г' 7-^

имеет полюс второго порядка в точке г =-вТогда вычет от нее равен

ЯеБ = Нш

г—>—01

2 I—

с1г

ае ^ Г1

= Нш -= Нш

( Г ^ г

V г1у

11=7Г1

( тЛ

— е

I V

( тЛ

Г-— е

I V

г т \

Г—■ ч г1/

^ /со

ТГ 7 1

7",

1

2 7П •

. 7Г 2 — 7Г 2 /\ г /12 — /I з

е2 е 1 т-^Функция Ф(г) = е 1

2 Я" 1 — П

Г

имеет полюс второго порядка в точке г =-в2. Тогда вычет от нее равен

Яез= Нш

(в2+г}<

7Г 2 — 7Г з г (02

е Г [7Г2-7ГЗг]

г->-6

= Нш <

( Т \ V г1у

(я- 2 — 7Г3 г

= Нш

г->-0,

¿/г

— п ъе

/ \ Г1

Ч 1 У

'--1^2+^302 ^

, N

ч

-0.

— пъе

П

г.

Ч 1 /

/2 =

Г-— (я-2 +тг302 )

-0,

Г у.1 -в г Г М

г— /—-

г.

Ч 1 У -пъе Ч 1 У

Г 1 Г Г? г\

/з=7г:з— е е 2л-/ г

(СО

6*з + г

-1

-Функция Ф(г) = е г' -

имеет простой полюс в точке г = — въ. Тогда вычет от нее равен

ЯеБ

г=-въ

(в3 )

г I

(?3 + * )

= Пш е

Г ( гЛ

2 г—

1 1 г>)

-в,

13 =71 з в

г\

1

'4=^4— \ Г'

2л-/

Функция ф(г) = е

имеет полюс второго порядка в точке г = -в3. Тогда вычет от нее равен

Кеэ = Нш

2->-въ

2 е

г

{в3+2у

г I-

с1г

= Иш

= Нш

г->-в.

/ т Л

г-

^ Г, ^

/ N

/4 =7Г4

V 1 /

Г ГЛ

t--е

V 1 у

ч ги

|

1

1

1 7 "27 1 _27 1

Г| 7-гтдх. Функция Ф(г) = е Гх ->-гг-

2л-/ ^ [Оз+Ч (вз+Ч

-/00

имеет полюс третьего порядка в точке г = —в3. Тогда вычет от нее равен

Яеэ = — 1ип 2

(в3+2)

2

3 е 4

г.

(в3+2у

г г т ^^

3

ч

= — 1ш1 2

с1 г'

С т \2 2 V г17

г—

ч

2

— Нш 2 V

2 ( т ^ 1

Ж,

( т^2 -

г-

',1л

Искомая плотность распределения

( -1 1. г-- г. Г

г- е V и +

V V

( \ \ж2+жъв2 )е

г—

-в;

— жъе

г ТЛ

7—-г,

V 1 У

+

-в,

+ жъе

Т\ /—-г,

V 1 /

+ 71.

?--

V г1у

ж<

+

Тг

V -в,

V Г1У

Тг

Г— ч

Упростив выражение и подставив значение коэффициентов ж и в, получаем

<Рпр( 0 =

л 2 2а 2 7*21

= 4 а2г2е 1

+ а,\(г{1-Т{)[2а2{г2г-Т2) + \]),

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

ПРИЛОЖЕНИЕ 2. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ФУНКЦИОНИРОВАНИЯ БАЗОВОГО КАНАЛА ПРИ ПЕРЕДАЧЕ ПОТОКА В СЕТИ С ДОЗИРОВАННОЙ БАЛАНСИРОВКОЙ НАГРУЗКИ С ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКОЙ ИНФОРМАЦИИ

Имитационное моделирование используется, с одной стороны для проверки адекватности полученных аналитических путем результатов, с другой стороны - для придания полученным аналитическим моделям большей функциональности. Для проведения имитационного моделирования возможно использование самых разных средств, например, общецелевого языка моделирования GPSS. Однако в данном случае имеет смысл использовать визуально-ориентированную среду моделирования Simulation, которая является одним их вариантов реализации известной в мире системы моделирования Slam II [15] (точнее ее компоненты сетевого подхода к моделированию1). Такой подход оправдан тем, что среда Simulation интегрирована на уровне файловой системы с программным обеспечением графо-аналитической системы GERT, функциональные возможности которой существенно расширены в последние годы за счет получения новых теоретических результатов, а также создания новых программных средств [10, 27, 29]. Кроме того, новые применения GERT-сетей предлагаются и в данной диссертации (использование GERT-сетей специальной структуры непосредственно в программах оптимизации с использованием генетических алгоритмов, см. раздел 2.8).

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

1 В системе Slam II имеются компоненты для сетевого, дискретно-событийного, процессно-ориентированного и непрерывного видов моделирования, объединенных общим управляющим ядром.

Модель 1. Агрегированный канал с функцией предварительной обработки измерительной информации

Экранная форма модели изображена на рис. П. 1.

и о

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

0,6

■0,5

-0,4

-0,3

■0,2

■0,1

Время

250 500 750 1000 1250 1500 1750 2000 2250 2500

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

Имитационные блоки-генераторы заявок С1, С2, ОЗ вырабатывают по 1000 простейших потоков со средней величиной интервала между поступлениями 500 мс (или 500 ед. модельного времени). Слияние этих потоков порождает также простейший поток заявок, частотная гистограмма которого изображена на рис. П.2. (снята имитационным блоком-сборщиком статистики).

Входной поток от трех источников поступает на предварительную обработку в очередь (^1. Предварительная обработка потока занимает случайное время с экспоненциальным распределением со средним значением 80 мс и имитируется блоком С выхода блока предварительной обработки заявки поступают на имитационный блок-селектор, который в имитационной системе выполняет функции ветвления поступающих на его вход заявок. Селектор Б1 направляет по дуге Ь5 в первый подканал 25 % всех заявок, а во второй подканал - 75 %. Первый подканал является менее быстродействующим. Задержка постоянной составляющей потока составляет 100 мс (имитируется блоком W2). Переменная составляющая задержки определяется распределением Эрланга 2 порядка со средним значением 40 мс. Задержанная блоком заявка поступает на выход селектора Б2, с выхода которого одновременно заявка поступает в блок задержки \УЗ и по дуге Ь7 выдается сигнал, блокирующий работу очереди С21 (выход очереди выключается, но поступление заявок на ее вход и накопление их в очереди разрешается). Заявка последовательно проходит через блоки \УЗ и W4, в каждом их которых она задерживается на экспоненциально распределенную величину со средним значением в 20 мс. Свертка законов распределения этих двух случайных величин дает в результате закон распределения Эрланга второго порядка со средним значением 40 мс. После выполнения задержки на указанную величину, отражающую случайные отклонения во времени передачи потока, сигнал с выхода блока БЗ разблокирует работу выхода очереди С>1, разрешая поступление на блок задержки \У2 следующей заявки. Частотная диаграмма,

отражающая время движения заявок от входа модели до селектора 812 приведена на рис. П.З.

Второй подканал имеет большее быстродействие, и на него направляется втрое больший поток. Постоянная составляющая задержки потока составляет 50 мс (имитируется блоком переменная составляющая задается распределением Эрланга второго порядка со средним значением 20 мс (блоки \У7 имитируют задержку, а 84 и 85 выполняют синхронизацию движения заявок подобно тому, как это делалось в модели первого подканала).

-■0,3

-0,25 -0,2 -0,15 -0,1 -0,05

■4-

4-

Время

=р

ч-

-4-

4-

0 100 200 300 400 500 600 700 600 900 1000 1100 1200 1300 1400 1500 1600

Рис. П.З. Гистограмма времени нахождения заявок в модели, выданная блоком

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

Диаграммы текущего состояния очередей приведены на рис. П.5 -П. 13. На рис. П.5 -П.7 в разных масштабах времени даны диаграммы очереди С>1 на входе агрегированного канала.

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

■0,3

-0,2

-0,1

-М

I -и-ь

Время

0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400

Рис. П.4. Гистограмма времени нахождения заявок в модели, выданная блоком 813

Время от 0 до 500000 модельных единиц

Рис. П.5. Текущая длина очереди 01 в интервале времени от 0 до 500000 модельных единиц