Содержание к диссертации
Введение
1. Обзор подходов управления телекоммуникационными системами и методов моделирования 11
1.1 Управление трафиком в компьютерных сетях 11
1.2 Управление информационными потоками путем прогнозирование пропускной способности в сетях . 22
1.3 Самоподобный трафик компьютерных сетей 31
1.4. Математические модели динамических управляемых систем 40
Выводы 55
2. Методика проведения экспериментальных исследований, обработки и анализа данных в распределенных корпоративных сетях с узким каналом связи 56
2.1. Описание исследуемой сети 56
2.2 Эмпирическая гистограмма загрузки выходного канала сети 58
2.3 Классы трафика 61
2.4 Схема получения статистических данных 61
2.5 Задача динамического управления загрузкой канала связи 66
2.6 Экспериментальный стенд 67
2.7 Методика проведения экспериментальных исследований 71
Выводы 73
3. Моделирование динамики изменения трафика на основе построения групп симметрии 74
3.1. Построение идентифицируемых моделей на основе геометрического анализа реконструированного аттрактора 74
3.2. Выявление симметрии в реконструированном аттракторе 78
3.3. Построение идентифицируемой модели , 84
3.4..Моделирование поведения трафика в управляемом переходном режиме 88
Выводы 91
4. Методика управления динамическим разделением загрузки в узком выходном канале связи корпоративных сетей, в условиях заданных ограничений 92
4.1 Алгоритм управления 92
4.2 Методика управления динамическим разделением загрузки каналов в корпоративных сетях 96
4.3 Оценка эффективности 97
4.4 Область эффективного использования 101
Выводы 102
Заключение 103
Список использованных источников 104
- Управление информационными потоками путем прогнозирование пропускной способности в сетях
- Эмпирическая гистограмма загрузки выходного канала сети
- Выявление симметрии в реконструированном аттракторе
- Методика управления динамическим разделением загрузки каналов в корпоративных сетях
Введение к работе
Современные корпоративные компьютерные сети, построенные на IP-протоколах, используются не только для классической передачи данных, но и для обмена речевой информацией, проведения мультимедийных конференций, оперативного контроля/управления, прослушивания музыкальных записей, просмотра видеоклипов, сетевых игр и других приложений реального времени. Для телекоммуникационных систем характерна следующая ситуация. С одной стороны — создается большое количество приложений, направленных на расширение области и средств общения и обмена информации, с другой — технологии передачи данных используют протоколы, не предназначенные для гарантированной передачи данных в системах реального времени. В этой ситуации часто возникают перегрузка очередей каналов связи, а также парализация сети из-за большого количества подключений к системам реального времени.
При перегрузке канала связи пакеты помещаются в очереди, в случае переполнения очереди пакеты отбрасываются, что приводит к замедлению скорости передачи пакетов протоколом ТСРЯР и потере пакетов.
Особенностью корпоративных сетей является отсутствие реальных возможностей создания новых протоколов работы сети при работе с внешней сетью и их аппаратной реализаций.
Чтобы добиться гарантии качества обслуживания от сетей, изначально на это не ориентированных, применяют QoS-архитектуру (Quality of service), которая включает в себя поддержку качества на всех уровнях стека протоколов TCP/IP и во всех сетевых элементах. Но и при этом обеспечение гарантированного качества обслуживания все равно остается самым слабым местом процесса передачи информации от источника к приемнику, т. к. QoS-архитектура представляет собой систему разделения трафика на статические,
заранее определяемые классы с фиксированными приоритетами, что не даёт возможности учитывать конкретную'ситуацию в данный момент времени.
Для эффективного использования статического назначения и выбора приоритетов необходимо использовать точные оценки параметров сети, что для общего случая является практически не решаемой задачей. Работы в области моделирования трафика и его характеристик велись и ведутся весьма интенсивно как отечественными (Морозов Е.В. [38], Шелухин О. И. [69], Городецкий А. Я. [14], Вишневский В. М. [12]), так и зарубежными учеными (М. Кровелл [85], А. Беставрос [86], Дж. Парк [71]). Тем не менее, многие вопросы здесь либо исследованы недостаточно полно, либо ориентированы на решение относительно узких прикладных задач, существующие модели не учитывают изменения количества подключенных пользователей к системе реального времени, т.е. реальную динамику загрузки сети.
Один из современных подходов строится на предположении фрактальности структуры трафика, но он используется совместно с методами теории массового обслуживания и не ориентирован на реальные прикладные вопросы динамического управления корпоративными сетями.
Таким образом, разработка моделей и алгоритмов управления динамическим разделением загрузки каналов в корпоративных сетях является актуальной задачей.
Цель исследования
Разработка методики для обеспечения гарантированной доставки пакетов в узком канале связи корпоративных сетей при использовании взвешенного справедливого обслуживания трафика, на основе динамического изменения приоритетов в условиях заданных ограничений.
Основные задачи исследования
1. Обзор подходов к управлению сетями передачи данных и методов моделирования телекоммуникационных процессов.
Постановка задачи, учитывающая особенности корпоративных сетей с узким каналом подключения.
Планирование эксперимента с учетом выбора схемы сетевой структуры, объема данных и разделения трафика на классы, для последующего сбора статистических данных.
Обоснование выбора метода моделирования трафика.
Идентификация математических моделей сети в переходном процессе и режиме нормального функционирования.
Разработка алгоритма диспетчеризации внешнего канала с динамически изменяющимися параметрами корпоративной сети на основе моделей и характеристик интенсивности трафика.
Разработка методики управления динамическим разделением загрузки каналов в корпоративных сетях.
Внедрение и анализ результатов.
Выявление области эффективного применения.
Объект исследования
Корпоративные сети с ярко выраженным превалированием скорости передачи по внутренним каналам связи над скоростью передачи по выходному каналу.
Предмет исследования
Методы моделирования трафика и архитектура обеспечения гарантированного качества управления в компьютерных сетях.
Методы исследования
В работе используются методы теоретической информатики, теории
алгоритмов, математической теории управления, качественной теории
нелинейной динамики и современные информационно-
телекоммуникационные технологии.
Научная новизна исследования
Разработана методика управления динамическим разделением загрузки в узком выходном канале связи корпоративных сетей при использовании взвешенного справедливого обслуживания трафика, на основе динамического изменения приоритетов в условиях заданных ограничений.
Разработан алгоритм диспетчеризации внешнего канала с динамически изменяющимися параметрами корпоративной сети на основе моделей, учитывающих динамические характеристики интенсивности трафика.
Сформулирована методика проведения экспериментальных исследований, обработки и анализа данных в распределенных корпоративных сетях с узким выходным каналом.
Практическая ценность
Результаты диссертации использованы при выполнении НИР по гранту РФФИ, проект № 08-07-00433а «Построение динамических моделей управления распределением загрузки каналов связи в вычислительных сетях».
Реализация результатов работы
Результаты работы использованы для построения динамических моделей управления загрузкой каналов связи в вычислительных сетях Московского государственного университета печати.
Апробация результатов работы
Результаты работы докладывались и обсуждались на 5-й научных конференциях и семинарах:
9-й Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (г. Кемерово, 2008);
9-й Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» ( Казань, КГТУ, 2008);
II Школе-семинаре молодых ученых «Задачи системного анализа, управления и обработки информации» (Москва, декабрь, 2008);
15-й Международной научно-технической конференции «Информационные технологии исистемы» (Нижний Новгород, апрель, 2009);
Регулярном научно-методическом семинаре кафедры прикладной математики и моделирования систем Московского государственного университета печати.
Результаты проведенных исследований подробно изложены в четырёх главах.
В первой главе проводится обзор подходов к управлению сетями передачи данных и методов моделирования телекоммуникационных процессов с целью формализации постановки задачи и обоснованного выбора методов и технологий ее решений. Проведен анализ методов управления телекоммуникационными сетями, направленных на обеспечение необходимой пропускной способности. Рассмотрены вопросы формирования и управления очередями в сетях передачи- данных. Показывается необходимость прогнозирования. Все известные решения заключается втом, что данные прогноза о пропускной способности позволяют получить дополнительные сведения для решения задачи управления, а именно формирования алгоритма предотвращения перегрузки. Проведен анализ публикаций по моделированию трафика на основании экспериментальных данных. Выделены группы методов, построенных в предположении о фрактальной структуре трафика
Показано, что используемые модели направлены на поиск оценок вероятностных характеристик, что не учитывает аппаратную реализацию в корпоративных сетях с внешнем переменным количеством подключенных пользователей к системе реального времени.
і I
Рассмотрены особенности идентификации динамических управляемых систем, используемые в классической математической теории управления.
Сформулирована задача создания методики управления динамическим разделением загрузки каналов в корпоративных сетях. В качестве базовых методов решения выбраны методы теории управления и качественной теории
нелинейных систем.
Во второй главе описана методика проведения экспериментальных исследований, обработки и анализа данных в распределенных корпоративных сетях, сформирована схема эксперимента для получения параметров сети с внешним узким каналом связи.
На основе данных о загрузке Интернет канала, полученных в ходе мониторинга работы сети МГУП за каждый* месяц, измеренных в течении года, была построена эмпирическая гистограмма частот загрузки канала показано, что1 наблюдаемое распределение вероятностей не согласуется с распределением Пуассона. Гистограммы частот загрузки канала, полученные для*других корпоративных сетей, также обладают,тяжеловесными хвостами свидетельствующие о наличии пиковых моментов загрузки сети, в которые происходит сильное увеличение задержек и потеря информации.
Сделан вывод, что в рассматриваемой задаче теория массового обслуживания, применяемая для управления сетями передачи данных, не гарантирует эффективное достижение поставленной цели.
Произведено разделение всей передаваемой информации на три типа трафика по уровню необходимого качества обслуживания. Предложен способ получения экспериментальных данных для анализа и его программно-аппаратная реализация.
Сформулирована задача динамического управления загрузкой канала связи. Содержательно задача состоит в динамическом разделении канала связи, таким образом, чтобы первый класс трафика передавать в заданном
объеме; критичный (второй) — передавать без потерь, а не критичный (третий) — с наименьшими потерями.
Для проверки методов управления описывается созданный экспериментальный стенд. Описывается разработанная методика проведения экспериментальных исследований, обработки и анализа данных в распределенных корпоративных сетях с узким каналом.
Третья глава посвящена построению математических моделей динамики трафика на основе использования качественной теории нелинейных систем. Приведены модели в режиме нормального функционирования и переходном процессе (при изменении пропускной способности).
Одно из современных и перспективных направлений моделирования заключается в поиске групп симметрии. Для реконструкции моделей по восстановленному аттрактору использованы симметрические свойства решений дифференциальных уравнений. Наличие симметрии в трафике показано в диссертации О. В. Козлова [27]. Получены модели и проведена оценка адекватности по среднеквадратичному критерию. Полученные значения (64% - для хаотической системы в режиме нормального функционирования, 72% - в переходном режиме) свидетельствуют о их применимости для реализации динамического управления.
В четвёртой главе изложен разработанный алгоритм управления пропускной способностью, обеспечивающий повышение надежности передачи и обработки информации; разработана методика управления динамическим разделением загрузки в узком выходном канале связи корпоративных сетей при использовании взвешенного справедливого обслуживания трафика, на основе динамического изменения приоритетов в условиях заданных ограничений и приведены оценки^ эффективности; определены области использования.
Разработан алгоритм диспетчеризации внешнего канала с динамически изменяющимися параметрами корпоративной сети на основе моделей, учитывающих динамические характеристики интенсивности трафика.
Описана сформированная методика управления динамическим разделением загрузки в узком выходном канале связи корпоративных сетей при использовании взвешенного справедливого обслуживания трафика, на основе динамического изменения приоритетов в условиях заданных ограничений.
Приводится оценка эффективности предложенной методики управления по сравнению со стандартными подходами. Показано, что наиболее эффективное решение, дает предложенный алгоритм.
Выявлена область эффективного использования предложенной методики динамического управления.
В заключении приводятся основные выводы и результаты работы.
Управление информационными потоками путем прогнозирование пропускной способности в сетях
Актуальность постановки задачи прогнозирования и ее решения заключается в том, что данные прогноза о пропускной способности позволяют получить дополнительные сведения для решения задачи управления, а именно формирования алгоритма предотвращения перегрузки. Решение указанной задачи, как правило, сводится к определению алгоритма с адаптивным механизмом перенастройки отдельных сетевых компонент. Одним из наиболее важных параметров, характеризующих качество работы сети, является пропускная способность (скорость передачи данных) канала связи между пользователями. Важным фактором, влияющим на пропускную способность, являются временные задержки, чем больше эти задержки, тем меньше пропускная способность. В высокоскоростных сетях соединения между пользователями осуществляются TCP/IP протоколом. В соответствии с алгоритмом работы этого протокола пропускная способность со стороны источника в фазе медленного старта определяется текущим окном перегрузки, равным числу разрешенных к передаче пакетов до прихода пакетов подтверждения.
Традиционная роль проектирования трафика телекоммуникационных сетей — гарантировать достаточную пропускную способность сети, чтобы встретить ожидаемый спрос адекватным качеством обслуживания. Важно понять трёхстороннюю связь между спросом, ёмкостью и пропускной способностью. Степень, с которой это возможно в будущих мультисервисных сетях, остаётся неясной, особенно из-за неотъемлемой самоподобности трафика и обусловленных этим трудностей моделирования.
Качество обслуживания в мультисервисных сетях существенно зависит от двух факторов: модели обслуживания (которая определяет различные классы обслуживания и устанавливает распределение сетевых ресурсов) и процедур трафикового- проектирования, используемых для определения ёмкости этих ресурсов. Хотя модель обслуживания и может обеспечить различные уровни обслуживания, гарантирующие некоторым пользователям хорошее качество, чтобы предоставить это качество для определённой совокупности пользователей, основываются на заблаговременном предоставлении достаточной пропускной способности для обеспечения их спроса.
При построении модели обслуживания важно правильно определить объект, к которому применяется трафиковое управление. В сети без установления соединения этим объектом служит датаграмма. На более высоких уровнях практически нет возможности для предоставления качества обслуживания, большего чем по принципу «максимальных усилий». С другой стороны, сети, имеющие дело по большей части с самоподобными трафиковыми объединениями, такими как все пакеты, передаваемые из одной локальной сети (LAN) в другую? могут с трудом предоставлять гарантии, разве что трафик изначально имеет определённую форму некоторого вида в чётко заданной области. Модель обслуживания, как правило, основывается на промежуточном трафиковом объекте, называемом «поток», который представляет собой последовательность пакетов определённого приложения, такого как видеоконференция или пересылка документа [12, 14, 16, 35, 47].
Аналитическое моделирование сетей Аналитическая модель сети представляет собой совокупность математических соотношений, связывающих между собой входные и выходные характеристики сети. При выводе таких соотношений приходится пренебрегать какими-то малосущественными деталями или обстоятельствами. Телекоммуникационная сеть при некотором упрощении может быть представлена в виде совокупности процессоров (узлов), соединенных каналами связи. Сообщение, пришедшее в узел, ждет некоторое время до того, как оно будет обработано. При этом может образоваться очередь таких сообщений, ожидающих обработки. Время передачи или полное время задержки сообщения d равно: где Тр, S и W, соответственно, время распространения, время обслуживания и время ожидания. Одной из задач аналитического моделирование является определение среднего значения D. При больших загрузках основной вклад дает ожидание обслуживания W. Для описания очередей в дальнейшем будет использована нотация: A/B/C/K/m/z, где А - процесс прибытия: В - процесс обслуживания; С - число серверов (узлов); К- максимальный размер очереди (по умолчанию - ); m -число клиентов (по умолчанию - ); z - схема работы буфера (по умолчанию FIFO). Буквы А и В представляют процессы прихода и обслуживания и обычно заменяются следующими буквами, характеризующими закон, соответствующий распределения событий [67,22]. D - постоянная вероятность; М- марковское экспоненциальное распределение; G - обобщенный закон распределения; Ек - распределение Эрланга порядка к; Нк - гиперэкспоненциальное распределение порядка к; Аналитическая модель для сетей Ethernet (CSMA-CD) разработана Лэмом [82]. Здесь предполагается, что сеть состоит из бесконечного числа станций, соединенных каналами с доменным доступом. То есть станция может начать передачу только в начале какого-то временного домена. Распределение сообщений подчиняется закону Пуассона с постоянной скоростью следования. Среднее значение времени ожидания для таких сетей составляет: где е - основание натурального логарифма, т - задержка распространения сигнала в сети, S и S2, соответственно первый и второй моменты распределения передачи или обслуживания сообщения, X преобразование Лапласа для распределения времени передачи сообщения. Следовательно Возможны разные подходы к моделированию. Классический подход заключается в воспроизведении событий в сети как можно точнее и поэтапное моделирование последствий этих событий. Другим подходом может стать метод, где для каждого логического сегмента (зоны столкновений) сначала моделируется очередь событий. При этом в каждой рабочей станции моделируется последовательность пакетов, ожидающих отправки. Эта очередь может время от времени модифицироваться, например, при получении ЭВМ пакета извне и, необходимости послать на него отклик. После того как такая очередь для каждого сетевого объекта построена, запускается программа отправки пакетов. Следует заметить, в этом подходе снимаются ограничения "дискретности" временной шкалы, использованной в предыдущем "классическом" подходе. Этот подход позволяет заметно ускорить расчеты при большом числе узлов, но малой загрузке сети. Проблемы реализации данной концепции моделирования связаны с обслуживанием довольно сложного списка, описывающего очередь пакетов, ожидающих отправки.
Эмпирическая гистограмма загрузки выходного канала сети
В связи с тем, что функция распределения имеет тяжеловесный хвост и не согласуется с распределением Пуассона сделан вывод, что в рассматриваемой задаче теория массового обслуживания, применяемая для управления сетями передачи данных, не гарантирует эффективное достижение поставленной цели.
Для выбора механизмов управления необходимо знать объем трафика которому необходим требуемый уровень обслуживания [95].
Для приоритеризации вся передаваемая информация была разделена на три типа трафика по уровню необходимого качества обслуживания:
1. Служебный трафик — трафик обмена служебными данными сетевого оборудования для поддержания сетевой инфраструктуры: whois, bgp, rip, dns, db, netbios, isakmp и т.д. Должен всегда иметь гарантированную полосу пропускания для поддержания сети в рабочем состоянии.
2. Потоковый трафик — трафик реального времени такой как аудио и видео, интерактивные данные следующих протоколов и служб: VoIP, IPTV, graphics, Windows Media, Apple Quick Time и т. д. Данный трафик сильно критичен к потерям и задержкам.
3. «Классический» трафик — трафик таких протоколов как: http, smtp, рорЗ, ftp, irc, icq, ssl, tftp, imap и других обычных протоколов LAN. Данный класс трафика не сильно критичен к задержкам, что позволяет незначительно увеличивать задержки для данного класса освобождая пропускную способность канала другим классам.
Для получения информации о количестве переданных данных каждого из типов трафика предложен способ получения экспериментальных данных для анализа и его программно-аппаратная реализация (рис. 2.7).
При поступлении на внутренний порт GigabitEthernetO/О центрального маршрутизатора Cisco 2851 пакет идентифицируется, попаданием в один из трех access-list. Согласно правилам ip policy route-map, пакет маршрутизируется на один из трех логических интерфейсов Loopback, соответствующих классу. Далее пакет попадает на внешний порт GigabitEthernetO/1. Сервер статистики на базе программы Paessler Router Traffic Grapher, по протоколу snmp и netfiow [53] снимает информацию о загрузке и количестве переданной информации со всех логических и физических интерфейсов [93].
Первый тип трафика имеет сглаженную структуру и занимает 3% от пропускной способности канала.
Загрузка канала вторым и третьим типами трафика динамически изменяется, то есть они имеют пульсирующую структуру с диапазоном изменения 67%.
Загрузки на выходном канале связи составляют порядка 300 мс в пиковые моменты, в связи с чем обрывается порядка 20% сессий видео вещания, происходит потеря качества аудио и видео передачи.
Для обеспечения качества передаваемой информации была проверена работа существующих алгоритмов на сети МГУП, с различными приоритетами.
Анализ показал, что лучше качество передачи достигается при использовании алгоритма управления очередями WFQ, по сравнению с остальными рассмотренными, но при этом задержка на передачу не приоритиризированных данных в Интернет увеличивается примерно в 3 раза. При использовании алгоритма приоритетного обслуживая, происходила остановка передачи трафика третьего типа, из-за того что трафик первых двух типов занимал всю пропускную способность канала, что останавливало работу пользователей с приложениями сети Интернет. При использовании алгоритмов взвешенного и справедливого взвешенного обслуживания, не удавалось добиться от сети задержки на передачу второго типа не более 20 мс в ряде моментов времени, из-за пульсирующей структуры трафика, но передача трафика третьего типа не прерывалась. Таким образом использование известных методов, улучшающих качество доставки данных не обеспечивает нужный уровень качества обслуживания трафика.
Для повышения качества работы сети первому типу трафика необходимо выделить статически пропускную способность 3% от канала, в связи с тем что он имеет сглаженную структуру. Второму классу трафика нужно выделять необходимую пропускную способность, которая может быть немного снижена, не приводя к потерям, чтобы обеспечить передачу трафика третьего типа. То есть, так распределить пропускную способность канала между классами, чтобы обеспечить постоянную передачу трафика третьего типа и гарантированный уровень обслуживания трафику второго типа [94].
Сформулирована задача динамического управления загрузкой канала связи. Необходимо для каждого класса трафика ( = 1,3) построить закон управления us{t) на интервале [/,;,] для динамической системы
Выявление симметрии в реконструированном аттракторе
Неоднозначно определяемые функции, представляющие собой центральное многообразие, имеют одинаковое инфинитезимальные образующие, а, следовательно, локально могут быть описаны одной группой симметрии [43]. Это справедливо в каждой точке, траектория которой остается в малой окрестности О при всех значениях t. Следовательно, рассматриваемая система может быть идентифицирована на основании инвариантов центрального многообразия — групп преобразований фазовых траекторий.
Аналогичны построения для систем с дискретным временем. Пусть система имеет размерность {п + 1); таким образом, секущая я-мерна. Пусть т мультипликаторов периодической траектории лежат на единичной окружности, к мультипликаторов лежат строго внутри единичной окружности, а остальные (п — т — к) мультипликаторов строго больше 1 по абсолютной величине. Отображение Пуанкаре вблизи неподвижной точки О записывается в виде, аналогичном (3.2), с той разницей, что spectr Л = {Х,,...Дт}, \=1, (j = \,m); spectr В = {Хт+},...,Хк} , k, 1, (j = m + \,k)\ построенной по восстановленному аттрактору.
Для реконструкции нелинейной системы в виде (3.4), (3.5) в [6] предлагается выделение локальных областей фазовых траекторий, близких к периодическим, и построение конечнопараметрических преобразований переводящих одну область в другую. То есть, построение группы симметрии фазовых траекторий, которая характеризуется преобразованием графиков
Для управляемых систем с нелинейной динамикой можно воспользоваться классической техникой группового анализа, изложенной, например, в [74]. Основы техники вычисления групп симметрии для дискретных моделей определены в [44].
Проиллюстрируем изложенные идеи, использую в качестве объекта моделирования реальную сети передачи данных. Сложность задачи состоит в нелинейности процесса передачи данных.
В качестве исходных данных использован процесс изменения загрузки канала связи. Восстановленный по экспериментальным данным аттрактор, построенный в соответствии с теоремой Такенса по методам, приведенным в [4] показан на рис. 3.1. Размерность реконструкции равна 6.
Для решения используем результаты исследований, проведенные О. В. Козловым [27]. Необходимо выделить на исходной последовательности набор участков таким образом, чтобы при приведении их к единому масштабу, положению и углу поворота они были бы максимально схожи между собой, а также получить численные показатели преобразований, переводящих один фрагмент в другой без учёта нарушений симметрии, дать численную оценку степени нарушения симметрии [28]. На рис. 3.1 приведена схематическая иллюстрация постановки задачи. где к - априори заданная величина, то есть существует ли набор фрагментов, в котором произведение максимального нормированного расстояния между фрагментами и суммарной нормированной длины фрагментов не больше к?
Для реализации проверяющего алгоритма A(S), который возвращает 1, в случае если S удовлетворяет поставленному условию, и 0 в противном случае, необходимо произвести 1{п) действий по расчёту масимального расстояния и суммарной длины фрагментов, следовательно поставленная задача принадлежит к классу NP, задачам проверяемым за полиномиальное время.
Представим вход задачи в виде полносвязного графа G, вершинами в котором будут фрагменты Vt, а рёбрами оценки соответствующих пар фрагментов полученные с помощью функции Dist(cM. рис. 3.2).
В таком случае задание параметра к будет выделять в графе G подграф G He содержащий вершин-фрагментов и рёбер, длина которых больше к (см. рис. 3.3). Все решения S удовлетворяющие условию (3.6) являются кликами (clique), полносвязными компонентами, графа Gk, т.е. решениями не содержащими вершин, рёбра между которыми исключены. И хотя обратное утверждение неверно — не все клики являются корректными решениями, задача выделения набора схожих фрагментов в контуре (NEAR-FRAGMENTS-SET) таким образом сводится к задаче поиска клики графа Gk Задача CLIQUE является NP-полной задачей, следовательно задача NEAR-FRAGMENTS-SET также является NP-полной.
Задача предобработки заключается в выделении на исходной последовательности набора рассматриваемых фрагментов и получении на основе каждого из них дескриптора - образа инвариантного относительно сдвига, поворота и масштабирования. Результаты применения работы О. В. Козлова [27] приведены на рис. 3.4.-3.6.
Исходный набор данных состоит из 200 точек. Сначала был построен фазовый портрет. Сглаживание не применялось.
Далее контур был подвергнут расстановке маркеров. Общее количество маркеров: 192. После маркировки из 18153 возможных контуров было отобрано 2633, остальные не удовлетворили ограничениям по длине: от 15 до 30 точек исходного контура. Каждый фрагмент был интерполирован 60-ю равномерно расположенными по его длине точками и подвергнут процедуре нормализации. После этого была построена матрица смежности фрагментов:
Был осуществлён эволюционный подбор решения (размер популяции 200, показатели вероятности мутации а = о,з и р = о,1, количество шагов ограничения длины: 8, элитарный отбор в новое поколение, тип выбора родителей - аутбридинг, особи в популяции уникальны) и отобрано решение-победитель. Экспериментальная машина: Intel Core2 CPU 6600 - 2.4 ГТц, 2,93 ГБ ОЗУ. Время проведения этапа предобработки: 12 мин. 43 сек. Время этапа генетического подбора решения: 6 мин. 11 сек., популяция сошлась 8 раз за 652 итераций, решение победитель: схожесть фрагментов 0.576, длина 125.
Методика управления динамическим разделением загрузки каналов в корпоративных сетях
На основании полученных теоретических и практических результатов сформирована методика управления динамическим разделением загрузки каналов в корпоративных сетях, состоящая из четырех этапов [92]. 1 этап. Методика проведения экспериментальных исследований, обработки и анализа данных в распределенных корпоративных сетях с узким каналом на имеющейся структуре сети, с целью выявления необходимости динамического управления. 2 этап. Построение математических моделей и их идентификация в соответствии с результатами, изложенными в главе 3 и оценка адекватности моделей. 3 этап. Реализация алгоритма управления приведенного выше. 4 этап.
Внедрение и оценка эффективности применения. Для проверки работы алгоритма было была реализована методика управления динамическим разделением загрузки каналов в корпоративных сетях. Для алгоритма взвешенного справедливого обслуживания с заданными приоритетами (показавшими наилучшее качество обслуживания при проверке работы алгоритмов на сети МГУП) и предложенного алгоритма, был смоделирован интервал работы сети из 70 шагов, интенсивностью повторяющей интенсивность трафика реальной сети, содержащий критичные моменты работы, в которые требуемая пропускная способность превышает пропускную способность канала связи. На рис. 4.2, 4.3, 4.4. приведены полученные экспериментальные данные для второго и третьего типа трафика (красный — необходимая пропускная способность, оранжевый и синий — пропускная способность в условиях ограничений, при использовании алгоритма справедливого взвешенного обслуживания с заданными приоритетами, зеленый - пропускная способность при использовании предложенного алгоритма).
Экспериментально получены следующие показатели, обеспечивающие эффективное использование предложенной методики динамического управления: - узкий внешний канал (соотношение скорости внешнего канала к внутренним скоростям не менее чем 1 к 10); - пульсирующая структура трафика реального времени с диапазоном изменения более 60%; - наличие разных классов трафика, различающихся по функциональному назначению и по необходимому уровню обслуживания; - идентифицируемость динамических прогнозирующих моделей с адекватностью не менее 60% и прогнозом на 10 шагов дискретизации при топологической эквивалентности фазовых портретов моделей и системы. 101 1. Разработан алгоритм управления пропускной способностью, обеспечивающий повышение надежности передачи и обработки информации, основанный на динамического изменения гарантированной пропускной способности трафика разных типов. 2. Сформирована методика управления динамическим разделением загрузки каналов в корпоративных сетях. 3. Произведена оценка эффективности, показывающая что предложенный алгоритм дает наиболее эффективное решение в смысле критерия управления. 4. Определены области эффективного использования предложенной методики динамического управления.
