Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Вычислительные машины, системы и сети

Диссертационная работа:

Бахарева, Надежда Федоровна. АППРОКСИМАТИВНЫЕ МЕТОДЫ И МОДЕЛИ МАССОВОГО ОБСЛУЖИВАНИЯ ДЛЯ ИССЛЕДОВАНИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ : диссертация ... доктора технических наук : 05.13.15 / Бахарева Надежда Федоровна; [Место защиты: ГОУВПО "Пензенский государственный университет"].- Пенза, 2011.- 335 с.: ил.

смотреть введение
Введение к работе:

Актуальность проблемы. В предисловии к монографии Вишневского В. М. «Теоретические основы проектирования компьютерных сетей» академиками РАН Е. П. Велиховым и Н. А. Кузнецовым сказано, что повсеместное внедрение компьютерных сетей должно сопровождаться опережающим развитием фундаментальной теории в этой области, созданием инженерных методов анализа и синтеза, систем автоматизации проектирования, направленных на сокращение сроков и повышение качества проектирования компьютерных сетей.

Современные методы и модели анализа производительности компьютерных сетей явно можно разделить на два направления: аналитическое вероятностное моделирование на основе теории массового обслуживания (ТМО) и имитационное (дискретно-событийное) моделирование. Методы первого направления, основанные на последних результатах теории массового обслуживания, ограничиваются пуассоновскими потоками в сетях систем массового обслуживания (СМО) M/M/1, M/D/1, M/G/1 и др. Второе направление представлено пакетами со встроенными генераторами потоков по различным законам распределений (COMNET, NetCracker, OPNET Modeler и др.).

Ограниченность пуассоновских моделей подтверждают публикации о самоподобных процессах как моделях трафика с «тяжелохвостными» распределениями (Цыбаков Б. С., Петров В. В., Шелухин О. И., Осин А. В., Wilson D., Leland W., Willinger W., Taggu M. S. и др.). В этих работах утверждается, что трафик компьютерных сетей не может адекватно описываться пуассоновскими моделями, так как они приводят к слишком оптимистичным результатам по задержкам. В качестве моделей массового обслуживания эффективнее использовать СМО G/G/1 или G/G/m.

Как известно из ТМО, среднее время ожидания в СМО M/M/1 выражается равенством , для системы M/G/1 – . Здесь М(Х2) означает 2-й начальный момент времени обслуживания. Наконец, для системы G/G/1 это время равно . Здесь – загрузка системы; – интенсивность входного потока; – соответственно дисперсии интервалов поступления и времени обслуживания; – соответственно среднее значение и второй начальный момент периода простоя, которые неизвестны. Из приведенных выражений следует, что при анализе сетей МО G/G/1 необходимо учитывать дисперсии времен поступления и обслуживания.

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

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

Традиционный подход к решению задач анализа производительности вычислительной сети, предложенный Л. Клейнроком, состоит в решении уравнений равновесия потоков относительно их интенсивностей в модели для ее декомпозиции на отдельные узлы и в нахождении характеристик узлов и всей сети в целом по формулам через характеристики СМО M/M/m или Полачека – Хинчина для СМО M/G/1. Таким образом, решение в конечной форме в виде произведения может быть найдено только при пуассоновском входном потоке.

В диссертации рассматривается альтернативный подход, использующий замену дискретных случайных процессов поступления и обслуживания в СМО G/G/m диффузионными процессами, т.е. подход, основанный на описании трафика на уровне двух первых моментов распределений временных интервалов. В качестве математической модели трафика сети рассматриваются уравнения равновесия потоков также на уровне двух первых моментов распределений интервалов времен между событиями. Для их вывода использованы математические модели мультиплексирования и демультиплексирования потоков. Решение уравнений равновесия позволяет декомпозировать сети МО на отдельные узлы, восстановить средние значения и дисперсии интервалов между событиями во всех потоках, если знать матрицу вероятностей передач P = {pij} и характеристики внешнего потока и , а также рассчитать показатели производительности узлов и сети в целом.

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

Объектом исследования являются методы и модели массового обслуживания.

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

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

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

– анализ известных моделей, методов и программных средств для исследования сетей по оценке их точности и степени адекватности;

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

– исследование адекватности предложенных моделей в вычислительных экспериментах на имитационных моделях;

– разработка метода баланса потоков в сетевых моделях типа G/G/1 на уровне средних значений и дисперсий интервалов времени для их восстановления, как в однородных, так и неоднородных потоках;

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

– обоснование применения метода обобщенной двумерной диффузионной аппроксимации СМО для анализа и расчета самоподобного трафика в случае входных распределений с «тяжелыми хвостами»;

– разработка метода декомпозиции сетей на подсети (узлы), который упрощает процесс моделирования многозвенных ЛВС с учетом их вложенности;

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

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

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

Научная новизна результатов диссертации. Научная новизна диссертации определяется следующими результатами.

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

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

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

4. Установлена связь между коэффициентами Херста H и вариации интервалов (при H > 0,5 > 1) для класса субэкспоненциальных распределений, которая позволяет использовать метод обобщенной двумерной диффузионной аппроксимации СМО при > 1 для расчетов самоподобного трафика.

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

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

Обоснованность и достоверность результатов диссертации. Предложенные в диссертации новые решения математически строго аргументированы и критически оценены по сравнению с другими известными результатами. Предложенные в работе сетевые модели построены с использованием данных, полученных экспериментальным путем с реальных сетей ЭВМ программными комплексами анализа трафика и системы активного мониторинга приложений. Достоверность полученных результатов подтверждена данными проведенных вычислительных экспериментов и имитационных экспериментов на моделях универсальной системы моделирования OPNET Modeler. Результаты диссертационной работы использованы при исследовании сетей филиала Центробанка РФ, вуза и компании.

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

Расчеты сетей вуза показали, что до 90 % всей нагрузки на сеть,
а следовательно, и других показателей производительности, создает внешний трафик и только до 10 % – внутренний трафик. В сетях предприятий, наоборот, выше доля внутреннего трафика.

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

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

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

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

Основные научные результаты, полученные автором и выносимые на защиту:

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

2. Метод баланса потоков в сетях МО для восстановления средних значений и дисперсий интервалов времени в однородных и неоднородных потоках с учетом ограничений на длину очереди для сегментирования сети ЭВМ.

3. Метод обобщенной двумерной диффузионной аппроксимации СМО общего вида G/G/1 и G/G/1/m при произвольных законах распределений временных интервалов поступления и обслуживания для расчетов характеристик функционирования сетевого ресурса.

4. Результаты применения метода обобщенной двумерной диффузионной аппроксимации СМО для анализа и расчета самоподобного трафика.

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

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

7. Результаты анализа эффективности предложенных методов моделирования при решении задач по оценке производительности сетей
в сравнении с результатами пакета OPNET Modeler.

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

Реализация и внедрение результатов диссертационной работы. Основные компоненты программного комплекса официально зарегистрированы Федеральной службой по интеллектуальной собственности, патентам и товарным знакам: «Анализ производительности компьютерных сетей на основе аппроксимативного подхода» – свидетельство об официальной регистрации № 2010613539. Результаты исследований, полученные в диссертационной работе, внедрены и используются в ОАО «ГИПРОСВЯЗЬ» (г. Москва и г. Самара), Главном управлении ЦБ РФ по Оренбургской области, ОАО «Оренбургэнергосбыт» (г. Оренбург), Центре информационных технологий ГОУ ВПО «Оренбургский государственный университет» (г. Оренбург), в учебном процессе ГОУ ВПО «Поволжский государственный университет телекоммуникаций и информатики» (г. Самара) и ГОУ ВПО «Оренбургский государственный университет» (г. Оренбург).

Связь исследований с научными проектами. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных работ «Разработка математического и программного обеспечения вычислительной техники и автоматизированных систем» – Г/б НИР № ГР 01950006416, «Разработка и исследование интерактивной системы вероятностного моделирования компьютерных систем» – Г/б НИР № ГР 01200600172 в Оренбургском государственном университете и «Проектирование и моделирование сетей ЭВМ» – Г/б НИР № ГР 0120. 0805270 в Поволжском государственном университете телекоммуникаций и информатики.

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

– XI и XII международных конференциях Российского научно-технического общества радиотехники, электроники и связи им. А. С. Попова, серия «Цифровая обработка сигналов и ее применение» (Москва, 2009, 2010);

– Международной конференции «Перспективные информационные технологии для авиации и космоса» СГАУ (Самара, 2010);

– IX, X, XI международных научно-технических конференциях «Проблемы техники и технологий телекоммуникаций» КГТУ (Казань, 2008), ПГУТИ (Самара, 2009) и УГАТУ (Уфа, 2010);

– международной конференции «Наука и образование: фундаментальные основы, технологии, инновации» ОГУ (Оренбург, 2010);

– VIII и IX всероссийских межвузовских научно-практических конференциях СамГТУ (Самара, 2009, 2010);

– IV Всероссийской научно-практической конференции ОГУ (Оренбург, 2009);

– X и ХI международных конференциях «Проблемы управления и моделирования в сложных системах» СНЦ РАН (Самара, 2008, 2009);

– научно-практической конференции научно-образовательного центра «Перспектива» «Управление созданием и развитием систем, сетей и устройств телекоммуникаций» СПбГПУ (С. Петербург, 2008);

– научно-практической конференции с международным участием «Перспективы информационных технологий в научных исследованиях, проектировании и обучении» СГАУ (Самара, 2006);

– всероссийских научно-практических конференциях с международным участием «Современные информационные технологии в науке, образовании и практике» ОГУ (Оренбург, 2003, 2004, 2005);

– региональной научно-практической конференции с международным участием «Современные информационные технологии в науке, образовании и практике» (Оренбург, 2002, 2003);

– IV Всероссийской научно-практической конференции «Методы и средства измерений физических величин» (Нижний Новгород, 1999).

Публикации. По теме диссертации опубликовано 53 работы,
в том числе 45 статей, из них 20 – в журналах, входящих в перечень ВАК,
а также получено 4 свидетельства о регистрации программ для ЭВМ.

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

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, библиографического списка и приложений; содержит 360 страниц основного текста, 133 рисунка, 41 таблицу. Библиографический список включает 158 наименований литературы.


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net