WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


 

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

Семехина Марина Вячеславовна

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ПЕРЕДАЧИ

И ОБРАБОТКИ ТРАФИКА В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ НА ОСНОВЕ АНАЛИТИЧЕСКИХ И ИМИТАЦИОННЫХ МЕТОДОВ

Специальность 05.13.18

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

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

Автореферат

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

Новокузнецк – 2012

Работа выполнена в ФГБОУ ВПО «Кемеровский государственный университет» на кафедре ЮНЕСКО по новым информационным технологиям

Научный руководитель:        кандидат физико-математических наук,

               доцент Гудов Александр Михайлович

Официальные оппоненты:        Калашников Сергей Николаевич, доктор технических наук, доцент, ФГБОУ ВПО «Сибирский государственный индустриальный университет», профессор 

               Родионов Алексей Сергеевич, доктор технических наук, старший научный сотрудник, ФГБУН «Институт вычислительной математики и математической геофизики СО РАН», зав. лабораторией        

Ведущая организация:        ФГБОУ ВПО «Новосибирский         государственный университет»

Защита состоится  21 марта 2012 года в 13 часов на заседании диссертационного совета Д 212.252.02 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Сибирский государственный индустриальный университет» (ФГБОУ ВПО «СибГИУ») по адресу: 654007,

г. Новокузнецк, Кемеровской обл., ул. Кирова, 42, СибГИУ, ауд. 3П.

Факс: (3843) 46-58-83

E-mail:  sec_nr@sibsiu.ru

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

Автореферат разослан 17 февраля 2012 г.

Ученый секретарь

диссертационного совета                                                        В. Ф. Евтушенко

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



Актуальность

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

К средствам, моделирующим работу сетей, можно отнести COMNET от CACI Products Company, SimuNet от Telenix, OPNET от MIL3, NetCracker, OMNeT++, NS-2, NS-3 и другие. В современных исследованиях теоретических основ моделирования ВС можно выделить несколько направлений. К одному из них можно отнести работы, развивающие классический подход теории массового обслуживания (ТМО). Здесь важное место занимают исследования Вишневского В.М., Тарасова В.Н, Кострова В.О., Клейнрока Л. Среди зарубежных авторов работ по сетям очередей массового обслуживания можно выделить Lam S., Lien I, Gelenbe E. В отдельное направление выделяется альтернативный подход, согласно которому, сетевой трафик обладает фрактальными свойствами и рассматривается как самоподобный процесс. В этой категории можно отметить таких авторов, как Ильницкий С.В., коллектив американских исследователей (Taqqu M.S.,Wilson D.V., Leland W.E.). К последнему направлению можно отнести исследователей в области имитационного моделирования: Павловский Ю.Н., Дубинин В.Н., Зинкин С.А., Rowe A.J.

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

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

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

  1. Разработка критерия выбора метода или комбинации аналитических и имитационных методов для решения различных задач моделирования ВС.
  2. Разработка математической модели, формально описывающей структуру, топологию ВС и потоки сетевого трафика, для применения аналитических и имитационных методов моделирования.
  3. Разработка математической модели ВС на основе сетей Петри, для проведения имитационных экспериментов.
  4. Разработка аналитических и имитационных методов, а также эффективных численных алгоритмов их реализации для расчета характеристик однородных и неоднородных ВС: среднего размера очереди сообщений, среднего времени обработки сообщений в узлах сети и общего времени реакции сети.
  5. Реализация программного комплекса для комбинированного моделирования ВС, расчета и анализа их характеристик.
  6. Проведение вычислительного эксперимента по расчету сетевых характеристик, оценка и анализ полученных результатов.

Методы исследований:

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

Научная новизна работы:

  1. Критерий выбора методов решения задач моделирования процессов передачи и обработки трафика в ВС, в качестве которого впервые предложено использовать функционал, отображающий упорядоченное множество входных параметров задачи на множество аналитических и имитационных методов решения данной задачи. Критерий предоставляет возможность построить формальный план комбинированного решения задачи, а также расширить круг задач моделирования ВС, традиционно решаемых в рамках одного специализированного программного продукта.
  2. Модифицированный метод анализа средних значений (MVA-метод) для численного расчета времени обработки сообщений и размеров очередей сообщений в неоднородных сетях, отличительной особенностью которого является возможность расчета характеристик такой сети на основе искусственно введенной однородной сети путем усреднения показателей смешанного трафика. Характеристики искомой сети рассчитываются с помощью коэффициентов перехода, характеризующих отношение исходных данных неоднородной сети к аналогичным показателям «опорной сети», без использования итерационного процесса. Такой подход позволяет уменьшить вычислительную сложность по сравнению с прямым MVA-методом в задачах моделирования различных вариантов распределения неоднородного трафика.
  3. Имитационная модель ВС на основе сетей Петри, отличающаяся введением новых объектов – ролевых функционалов, которые позволяют описывать объекты сетевой инфраструктуры (активные сетевые устройства и сегменты сети) и автоматизировать имитационный анализ сетей сложной структуры и большой размерности.
  4. Программный комплекс для решения широкого круга задач моделирования ВС, основанный на алгоритмах комбинированного использования аналитических и имитационных алгоритмов.

Практическая значимость результатов работы:

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

Реализация результатов работы:

Полученные результаты были использованы при выполнении планов научно-исследовательских работ КемГУ и ИВТ СО РАН в 2005-2011 гг.

Программный комплекс тестировался в КемГУ для исследования и анализа сегментов ВС, а также в ООО «Скиф» – аутсорсингового предприятия, обслуживающего вычислительную инфраструктуру угледобывающей компании «Кузбассразрезуголь». Использование программного комплекса на основе разработанных моделей позволило оптимизировать работу сетевых администраторов, а также подобрать ряд параметров для отдельных сегментов ВС компании «Кузбассразрезуголь», при которых среднее время реакции в исследуемом сегменте сети уменьшилось на 10-20% по сравнению с прежними значениями. Достоверность реализации программного комплекса подтверждается справкой об использовании.

Предмет защиты и личный вклад автора:

На защиту выносятся следующие основные результаты решения задач диссертационного исследования:

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

Основные научные и практические результаты диссертации получены  автором лично. В работе [3] автор участвовал в проектировании информационной системы, в работах [6,7] автор принимал участие в разработках механизмов и алгоритмов комбинированного использования аналитических и имитационных методов, в работах [8,9] – автором были разработаны модели ВС на основе аппарата сетей Петри, и операции над этими моделями.

Публикации

По теме диссертации опубликовано 11 работ, в том числе 2 статьи в изданиях, рекомендуемых ВАК для предоставления основных результатов диссертации, 9 публикаций в трудах и материалах конференций.

Основные результаты диссертации представлялись на:  Всероссийских научно-практических конференциях «Недра Кузбасса. IT-технологии» (Кемерово, 2008), «Системы автоматизации в образовании, науке и производстве» AS’2007 (г. Новокузнецк; 2007), «Научное творчество молодежи» (Анжеро-Судженск, 2007), «Системы автоматизации в образовании, науке и производстве» AS’2009 (г. Новокузнецк; 2009), «Информационные технологии и математическое моделирование» (г. Анжеро-Судженск, 2009-2010), «Проектирование и разработка распределенных информационных систем» ПРИС-2009 (г. Красноярск, 2009); Всероссийском конкурсе «Участник молодежного научно-инновационного конкурса» (УМНИК, г.Кемерово, 2008); научных семинарах кафедры ЮНЕСКО по НИТ КемГУ под руководством д.ф.-м.н., профессора К.Е. Афанасьева (Кемерово, 2005–2011).





Структура и объем работы

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 108 страниц текста, в том числе 23 таблицы, 18 рисунков. Кроме того, в работу входит список использованных источников из 75 наименований и приложений на 12 страницах.

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

Во введении  раскрывается проблематика выбранной темы и актуальность работы.

В первой главе «Теоретические основы моделирования вычислительных сетей» исследуется тема работы, определяется ее цель и общие задачи. В частности, в главе ставится и решается задача определения механизмов и области эффективного использования (Задача 1) комбинированного использования аналитических и имитационных методов моделирования процессов передачи и обработки трафика в вычислительных сетях.

Исходные данные:

    • информация об объектах предметной области: вычислительные сети, сетевые устройства, сетевой трафик и принципы его обработки;
    • существующие прикладные средства анализа и моделирования ВС;
    • данные исследований различных авторов в области анализа и моделирования ВС, в частности:
      • аналитические (вероятностные) методы;
      • имитационные методы и системы имитационного моделирования;

Требуется:

    1. Формально определить область и объекты исследования, оцениваемые параметры объектов.
    2. Проанализировать существующие методы решения задач моделирования ВС.
    3. Проанализировать классификацию задач сетевого моделирования.
    4. Определить критерий выбора методов для решения задач моделирования.

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

В первой главе приведен сравнительный анализ существующих инструментальных средств анализа и моделирования ВС: COMNET от CACI Products Company, SimuNet от Telenix, OPNET от MIL3, NetCracker, OMNeT++, NS-2, NS-3 и другие (таблица 1). Рассматриваются особенности этих систем, и приводится их оценка по следующей совокупности критериев:

  1. наличие библиотеки устройств;
  2. возможность настройки библиотеки устройств;
  3. возможность пошаговой трассировки имитационной модели;
  4. генерация отчетов о работе модели;
  5. специализированность ПО (насколько программный комплекс ориентирован именно на исследование ВС);
  6. потребность в дополнительном программном обеспечении;
  7. возможность автоматического сбора данных из реальной сети;
  8. сложность внедрения системы и работы с ней;
  9. развитие и поддержка системы
  10. стоимость программного средства.

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

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

Пусть A* – некоторая общая задача моделирования, которая может быть декомпозирована на составляющие ее задачи. A*={A1, A2, A3} – первый уровень декомпозиции, где A1 – постановка задачи, которая, в свою очередь, может быть декомпозирована на ряд более простых задач, решаемых последовательно или параллельно. A2 описывает процесс решения: A2={a21,a22,a23,..}. Например, a21 – вычисление параметров; a22 – отображение пошаговой работы модели; a23 – сбор данных о ходе выполнения задач a21, a22 и т.д. A3 аналогичным образом описывает анализ полученных результатов. Пусть M – некоторый класс методов решения (MI – имитационное моделирование; MT – аналитическое), mk – конкретный метод решения из M, {mk1,..mkn} – множество методов решения из класса M, M{MI,MT}. Обозначим mim – метод имитационного расчета сети, mb – аналитический метод баланса потоков для расчета основных сетевых характеристик, mit – итерационный метод анализа средних значений времени обработки сообщений и размеров очередей сообщений в узлах сети, mit* – модифицированный метод анализа средних значений для неоднородных сетей.

В качестве параметров Ui, влияющих на выбор решения для задачи A2 выберем следующие:

  • 1й уровень параметров U1 – тип задачи;
  • 2й уровень параметров U2 – особенности сети;
  • 3й уровень параметров U3 – особенности задачи;

Исходя из сделанных выводов, формируется система критериев для выбора метода или комбинации аналитических и имитационных методов при решении задач моделирования ВС. Пусть H(A*| U1; U2; U3)={mk1,..mkn}, где H – функционал, ставящий в соответствие параметрам A*,U1,U2,U3 набор методов {mk1,..mkn}, которые могут быть применены для решения задачи A* с учетом указанных параметров. Параметры могут быть незначимыми, при этом первый параметр U1 должен быть значимым – должен быть известен тип задачи.

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

Таблица 1. Примеры значения критерия выбора методов решения задач моделирования ВС

Параметры

H значение функционала

U1 тип задачи

U2 - особенности сети

U3 - особенности задачи

M - Класс методов

План решения /Методы

Расчет основных характеристик

Сложная сеть

Требуется высокая точность

MI –

имитационные

{mim}: Имитационный расчет основных характеристик

Не требуется высокая точность

MT –

аналитические,

MI – имитационные

{ mim,mit}: Последовательно:

1 – mim -имитационный расчет отдельных сегментов сети;

2 – аналитический расчет основных характеристик укрупненной сети (mb, mit).

Простая сеть

Требуется высокая точность

MT –аналитические

{mb}: Метод баланса потоков, или {mit} – метод анализа средних значений

Не требуется высокая точность

MT –аналитические

{mb}: Метод баланса потоков, {mit} - метод анализа средних значений

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

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

Исходные данные:

  • определенные в Задаче 1 объекты моделирования и их основные параметры;
  • принципы построения моделей сложных систем и вычислительных сетей, в частности:
      • стандарты моделирования (SADT, RDF), классификация моделей;
      • наиболее распространенные методы моделирования ВС;

Требуется:

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

Для решения поставленной задачи в главе рассматриваются следующие объекты исследования:

  1. Локальные вычислительные сети (ЛВС) как совокупность компьютеров, периферийных и коммутационных устройств и каналов связи  заданной топологии. Формально модель ВС может быть представлена в виде D(W,N), где W – количество устройств сети, N – количество сообщений, одновременно циркулирующих в сети.
  2. Процессы передачи сетевых сообщений между структурными компонентами сети, вместе с задержками на их обработку, которые характеризуются следующими параметрами: средняя интенсивность потока (сообщений в единицу времени), входящего в i-й узел сети  (λi, i=1..W); средняя интенсивность обработки в i-м узле (сообщений в единицу времени); (μi, i=1..W); среднее время обработки (Ti) одного сообщения в i-м узле; средний размер очереди сообщений (Li) в i-м узле, ожидающих обработки; вероятность того, что сообщение после обработки в i-м узле, перейдет в j-й узел (Pij).

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

  • интенсивность передачи и обработки трафика μi;
  • нагрузка на устройства и сеть в целом λi;
  • размеры очередей сообщений, ожидающих обработки в сетевых узлах: Li.

Для формализации основных объектов сети и связей между ними предложена математическая модель ВС в нотации RDF (рисунок 1).

Вторая глава «Особенности аналитического расчета сетевых характеристик» рассматривает отдельные методы аналитического моделирования ВС. В главе формулируется и решается Задача определения алгоритмов (Задача 3) для реализации аналитических методов.

Исходные данные:

- определенные в Задачах 1, 2 объекты моделирования, модель ВС в нотации RDF;

- методы аналитического моделирования;

Требуется:

  1. Определить аналитические методы, используемые для моделирования ВС: метод баланса потоков и метод анализа средних значений;

Рисунок 1. Модель сети

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

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

                                               (1)

где n=(n1,n2,…nW) – агрегированное состояние сети,  - относительные коэффициенты интенсивности потоков, j=1,W; при этом для решения полученной СЛАУ для одного из узлов произвольно, в общем случае, фиксируется e равное, например, 1.

Для оптимизации расчетов также часто используется итерационный метод анализа средних значений (MVA-метод Mean Value Analysis), который не требует расчета нормализующей константы, что позволяет существенно сэкономить вычислительные ресурсы. В реальных задачах моделирования ВС часто требуется рассмотреть несколько вариантов организации одной сети, измерить основные сетевые характеристики и выбрать оптимальный вариант. В большинстве случаев эти варианты являются различными способами распределения вычислительной нагрузки в сети с относительно определенной аппаратной структурой – то есть требуется при заданной структуре определить расположение и параметры основных сетевых серверов (почтового, ftp, СУБД и т.п.). Такие задачи сводятся к расчету модели ВС общей структуры, но с разными типами трафика, и их разной маршрутизацией в сети. Одним из способов расчета неоднородных ВС является MVA-метод.

Пусть в неоднородной сети D(W,N,R) N={Nr} – количество сообщений, W={Wr} – количество сетевых узлов, а R – количество классов сообщений. Стандартный MVA-метод для такой сети на каждом итерационном (по N) шаге рассчитывает три значения для каждого класса r=1..R: среднее время задержки сообщения Tir(N'), средний размер очереди Lir(N'), и вспомогательное значение *r – относительную среднюю интенсивность входящего потока:

Tir(N')= ir(1+ Li(N-1))                                        (2)

                               (3)

Lir(N') = r*(N')eirTir(N')                                (4)

                       (5)

Маршрутная матрица неоднородной сети массового обслуживания ||Pijr|| может быть представлена в виде матриц ||Pij|r=r||, r=1..R, R – количество типов трафика. На ее основании определяются коэффициенты eijr по аналогии с (5).

В работе предлагается использовать альтернативный подход, основанный на выражении таких связанных параметров неоднородных ВС, как среднее время задержки сообщения в узле – ir, и средняя интенсивность обслуживания ir, r=1..R через аналогичные показатели и матрицу вероятностей для соответствующей однородной сети (назовем ее опорной сетью), т.е. сети, в которой не выделяют отдельные типы трафика, а рассматривают общий усредненный трафик. Таким образом, предлагается не реализовывать весь итерационный процесс каждый раз, когда в сети происходит перераспределение трафика путем выделения различных его типов, а численно рассчитывать «в один шаг» задержки на обслуживание и размеры очередей на основании данных опорной сети, и исходных данных о типах и маршрутах трафика. То есть для неоднородной сети D(W=(W1..WR),R,NR=(N1..NR), PR=(||Pij|r=1||,..||Pij|r=R||)) рассматривается опорная однородная сеть  D'(W,R=1,,||Pij||). Тогда:

;         (6)

Lir(Nr) можно представить с помощью соотношения Li(Nr) deir r*/ *.  (7)

С учетом (2-5) рассчитываются сетевые характеристики для последнего шага неоднородного итерационного процесса:

                               (8)

где ir=ir/i – коэффициент отношения основных исходных характеристик обслуживания для выбранных узла и класса к соответствующим характеристикам опорной сети. Отметим, что для однородной сети этот параметр является вырожденным и равен 1 (опорная сеть совпадает с рассчитываемой сетью). Аналогично, при последовательном итерационном расчете неоднородной сети не строится отличная от рассматриваемой модели опорная сеть, и ir=1.

                                       (9)

где r – коэффициент перехода от опорной сети к неоднородной; при этом

r= = , где O – значение *, рассчитанное для опорной сети. Коэффициент r содержит отношение r*/* из (7), рассчитанное для второго шага итерации. Экспериментально было выявлено, что при N=1 результаты расчета получаются слишком грубыми, из-за тривиального характера процесса на данном этапе. При N=2 итерационный процесс уже опирается на расчетные, а не только на исходные данные.

Далее выполняются остальные операции итерационного шага – вычисление *r и Lir(max(Nr)) в соответствии с (2)–(4). Результаты тестовых расчетов, приведенные в работе, показывают, что вычисленные таким образом характеристики смешанной сети отличаются от характеристик, рассчитанных стандартным способом, в среднем на 5–8 %, что укладывается в допустимые пределы.

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

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

В третьей главе «Имитационное моделирование процессов обработки и передачи трафика в ВС» формулируется и решается Задача определения алгоритмов (Задача 4) для реализации имитационного моделирования ВС.

Исходные данные:

- определенные в Задачах 1, 2 объекты, методы моделирования, общая модель ВС;

- основные положения теории сетей Петри (СП).

Требуется:

    1. Определить принципы построения моделей ВС в терминах сетей Петри, для имитационного моделирования процессов передачи и обработки трафика в сети;
    2. Произвести необходимые модификации аппарата сетей Петри, предложить алгоритмы работы имитационной модели;

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

Основное определение СП: W={P,T,D,TR}, где P – множество позиций; T – множество переходов; D – множество дуг; TR – множество типов трафика; TR(p) – множество типов меток, которые могут находиться в позиции р. – вектор распределения меток по позициям, или маркировка,  m(tr,p) – метка типа tr, находящаяся в позиции р.

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

Формально определение ролевого функционала для нераскрашенной СП можно представить следующим образом:

F: {m(pin1),..m(pinn)} { m'(pin1),..m'(pinn); m''(pout1),..m''(pouts)},

где pin1.. pinn – входные позиции F; pout1.. pouts – выходные позиции F; m(p) – количество меток, входящих в позицию p извне; m’(p) – количество меток, которые остаются в позиции p после одного срабатывания всех разрешенных переходов в F; m''(p) – количество меток, выходящих из позиции p за пределы F после одного срабатывания всех разрешенных переходов в F.

Основные типы ролевых функционалов:

  • Функционал приемник/передатчик трафика (рисунок 2, А): элементарная сеть Петри, на основе которой строятся все остальные функционалы. F(n,0)=(0,n), т.е. при входе в позицию (1)  n меток и после срабатывания t, во входной позиции останется 0 сообщений, а в выходной позиции  (2) появится n меток.
  • Функционал генератор трафика независимый вариант (рисунок 2, Б).
  • Функционал генератор трафика зависимый вариант (рисунок 2, В).

Рисунок 2 – Основные ролевые функционалы: А – приемник/передатчик трафика,

Б – независимый генератор трафика, В – зависимый генератор трафика

Операции с ролевыми функционалами. Для целей моделирования ВС определяются (по аналогии с алгеброй сетей Петри) операции над элементами сетей Ai: позициями pj, переходами tk, дугами dl  (i, j, k, l Є Z): ~,,!,/,&,%  (соответственно, операции отождествления, добавления дуг, исключения дуг, переименования позиций, объединения, расщепления). Модели некоторых сетевых устройств представлены на рисунке 3.

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

Рисунок 3. Примеры моделей сетевых устройств: а – рабочая станция; б – концентратор;

Четвертая глава «Особенности реализации методов моделирования ВС» посвящена вопросам разработки информационной системы. В процессе работы над главой была сформулирована и решена задача программной реализации (Задача 5) системы моделирования и анализа компьютерных сетей «СиМАКС».

Исходные данные:

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

Требуется:

  1. Определить задачи и требования к информационной системе (ИС).
  2. Определить структуру ИС.

На основе приведенных моделей ВС и описанного подхода к комплексному использованию аналитических и имитационных методов создан прототип программного комплекса «СиМАКС» (Система моделирования и анализа компьютерных сетей). Система позволяет решать следующие основные задачи:

  1. Выбор класса задачи моделирования ВС и определение методов ее решения.
  2. Создание моделей ВС для аналитического моделирования.
  3. Создание моделей ВС для имитационного моделирования.
  4. Аналитический расчет сетевых характеристик для представленных моделей.
  5. Проведение имитационного эксперимента по передаче трафика в рамках построенной модели.
  6. Сохранение данных о моделях во внешних файлах.

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

Для реализации системы используются следующие технологии, использующие принципы объектно-ориентированного программирования:

  1. Java (jdk1.5.0_01., Eclipse SDK v.3.6.2, библиотека jpcap).
  2. Технология XML – для хранения результатов моделирования.
  3. Системные сетевые библиотеки libpcap и winpcap, в качестве базового инструментария получения сетевой статистики с сетевых устройств, для последующей ее обработки и ввода в СиМАКС.

Для проведения вычислительных экспериментов использовался сегмент реальной сети, включающий 5 рабочих станций и коммутатор-свитч, поддерживаемый топологию «звезда». Для этой сети приводятся сравнительные данные расчетов сетевых характеристик аналитическими и имитационными методами. Данные таблицы 2 показывают относительную погрешность имитационных расчетов средней очереди сообщений и среднего времени обработки сообщений по сравнению с расчетами MVA-методом, а также в таблице указаны максимальные значения погрешности во всех вариантах работы модели (Т=100, Т=1000, Т=5000, где Т – количество тактов работы модели). Характер распределения рассчитанных значений по устройствам соответствует исходным данным, за которые приняты результаты аналитического моделирования, а абсолютные максимальные показатели погрешности снижаются с ростом времени выполнения имитационной модели.

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

узла

Очередь

Время обработки

Относительная погрешность (E) / %

Относительная погрешность (E) / %

Т=100

Т=1000

Т=5000

Т=100

Т=1000

Т=5000

1

0,672

67

-0,105

10

-0,037

4

0,479

48

-0,175

17

-0,128

13

2

0,193

19

0,114

11

0,09

9

-0,103

10

-0,055

5

-0,002

0

3

-0,172

17

-0,057

6

-0,01

1

-0,001

0

-0,053

5

0,006

1

4

0,717

72

0,151

15

0,076

8

-0,257

26

-0,123

12

0,006

1

5

0,662

66

-0,077

8

0,019

2

-0,38

38

0,051

5

0,031

3

6

0,331

33

0,071

7

-0,015

1

0,202

20

0,059

6

0,028

3

Max. E (%)

72

 

15

 

9

 

48

 

17

 

13

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

  1. В работе решается задача разработки и реализации методов и алгоритмов моделирования ВС, которая является актуальной научно-технической проблемой.
  2. Предложена система классификации и декомпозиции задач моделирования, и  критерий выбора методов их решения, который позволяет расширить круг задач, традиционно решаемых с помощью программных продуктов.
  3. На основе метода анализа средних значений, известного из теории сетей очередей, разработан приближенный метод для расчета средних очередей и среднего времени обработки сообщений в устройствах ВС в задачах многократного расчета неоднородных сетей с общей опорной сетью.
  4. Предложены принципы построения имитационных моделей ВС на основе сетей Петри, позволяющие с помощью новых объектов – ролевых функционалов, автоматически конструировать и выполнять сети Петри для моделирования ВС.
  5. Реализован программный комплекс «СиМАКС», который позволяет оперативно создавать аналитические и имитационные модели ВС путем автоматического получения данных из реальных сетей, а также решать различные задачи сетевого моделирования на основе комбинированного использования методов.
  6. Проведен вычислительный эксперимент с использованием разработанного программного комплекса. Рассчитываемые показатели сети позволяют оценить качество ее работы в целом и отдельных сетевых устройств.

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

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

Публикации по теме диссертации в изданиях, рекомендованных ВАК:

  1. Гудов А. М., Семехина М. В. Имитационное моделирование процессов передачи трафика в вычислительных сетях // Управление большими системами. М.: ИПУ РАН, 2010г. Выпуск 31; стр.130-161
  2. Семехина М.В. Имитационное моделирование трафика в вычислительных сетях на основе аппарата сетей Петри // Вестник КемГУ, Кемерово, 2010г, №4(44); стр. 10-15.

Труды научно-практических конференций и сборников:

  1. Гудов А.М., Федотов А. М., Семехина М.В. Автоматизированная система сетевого моделирования // Труды VI Всероссийской научно-практической конференции «Системы автоматизации в образовании, науке и производстве» AS' 2007, г. Новокузнецк, 2007 г.; стр.107-109.
  2. Семехина М.В. Автоматизированная система сетевого моделирования // Материалы XI Всероссийской научно-практической конференции «Научное творчество молодежи», г. Анжеро-Судженск, 2007 г.; стр.118-121.
  3. Семехина М.В. Распределенная информационная система моделирования компьютерных сетей // Материалы VII Всероссийской научно-практической конференции «Инновационные Недра Кузбасса. IT-технологии», г. Кемерово, 2008 г.; стр.65-67.
  4. Гудов А.М., Семехина М.В. «Комплексный подход к моделированию компьютерных сетей» // Труды VII всероссийской научно-практической конференции «Системы автоматизации в образовании, науке и производстве» AS' 2009, г. Новокузнецк, 2009 г.; стр.114-117.
  5. Гудов А.М., Семехина М.В. «Комплексное моделирование трафика в вычислительных сетях» // Материалы VIII Всероссийская научно-практическая конференция с международным участием "Информационные технологии и математическое моделирование", г. Анжеро-Судженск, 2009; стр.98-100.
  6. Гудов А.М., Семехина М.В. Имитационное моделирование процессов передачи трафика в вычислительных сетях на основе модифицированных сетей Петри // Интеллектуальные технологии в образовании, экономике и управлении 2009. Сборник материалов VI международной научно-практической конференции, Воронеж, г. Воронеж, "Воронежская областная типография", 2009; стр. 348-353.
  7. Семехина М.В. Гудов А.М. Комплексный подход к моделированию трафика в корпоративных вычислительных сетях // Сборник материалов VII Всероссийской конференции по теоретическим основам проектирования и разработки распределенных информационных систем "ПРИС-2009". г. Красноярск, 2009; стр.49-51.
  8. Семехина М.В. Гудов А.М. Аспекты имитационного моделирования трафика в вычислительных сетях на основе Сетей Петри // Материалы IX Всероссийской научно-практической конференции с международным участием. Часть 1, Издательство Томского университета, г. Томск,2010; стр. 73-77.
  9. Гудов А.М., Семехина М.В. Комплексное моделирование трафика в вычислительных сетях // Материалы IX Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование» г. Анжеро-Судженск, 2010; стр.137-142.

а также регулярно на научных семинарах кафедры ЮНЕСКО по НИТ КемГУ под руководством профессора К. Е. Афанасьева (Кемерово, 2005–2011).

Подписано к печати 13.02.2012  г. Формат 60х841 /16. Печать офсетная. Бумага офсетная № 1. Печ. л. 1,0. Тираж 100 экз.

_____________________________________________________________________________________________________

ФГБОУ ВПО «Кемеровский государственный университет»

650043, г. Кемерово, ул. Красная, 6.

Отпечатано: Салон печати «Хорошие традиции» г.Кемерово, ул. Н.Островского, 16.






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.