Содержание к диссертации
Введение
ГЛАВА 1. Методологические аспекты исследования производительности компьютерных сетей 24
1.1 Проблемы организации корпоративных сетей и подходы к их исследованию 24
1.2 Концепция построения моделей корпоративных сетей передачи данных как сложных систем 28
1.3 Анализ аппаратно-программных средств оценки количественных и качественных показателей функционирования сетей 36
1.4 Обзор математического и программного инструментария моделирования компьютерных сетей 43
1.4.1 Использование теории сетей массового обслуживания для исследования компьютерных сетей 46
1.4.2 Расчет характеристик сетей пакетной коммутации 49
1.4.3 Модели сетей с ограниченной буферной памятью в узлах коммутации 53
1.4.4 Аналитические методы и модели анализа производительности компьютерных сетей 57
1.4.5 Определение показателей производительности сети путем имитационного моделирования сетевого трафика и событий 66
1.5 Методы построения моделей активного оборудования и управления потоками в сетях пакетной коммутации 74
1.6 Постановка проблемы 81
1.7 Выводы 84
ГЛАВА 2. Математическая модель трафика в виде уравнений баланса потоков в сетевых структурах на уровне двух первых моментов распределений интервалов времени между событиями 86
2.1 Реализация математической операции мультиплексирования потоков на основе аппроксимации законов распределений 90
2.2 Определение неизвестных параметров аппроксимирующих функций распределений 95
2.3 Определение характеристик распределения результирующего (мультиплексированного) потока... 98
2.4 Математическое мультиплексирование потоков на основе их диффузионной аппроксимации 106
2.5 Анализ точности полученных результатов по математическому мультиплексированию потоков 113
2.6 Реализация математических операций демультиплексирования потоков 117
2.7 Метод баланса потоков на уровне дисперсий распределений времен между событиями 123
2.8 Развитие метода баланса в сетевых моделях при наличии избыточных потоков 125
2.9 Развитие метода баланса потоков в случае неоднородного трафика 128
2.10 Выводы 132
ГЛАВА 3. Аппроксимативная модель массового обслуживания общего вида как математическая модель функционирования узла сети 134
3.1 Известные методы диффузионной аппроксимации процессов функционирования СМО типа G/G/1 и исследование их точности 134
3.2 Метод обобщенной двумерной диффузионной аппроксимации процессов функционирования СМО общего вида и расчет ее характеристик 142
3.3 Расчет характеристик СМО типа G/G/1/oo с бесконечной очередью 146
3.4 Расчет характеристик СМО типа G/G/1/m с конечной очередью и потерями 154
3.5 Определение характеристик сетевых моделей через характеристики узлов 156
3.6 Проверка адекватности аппроксимативной модели массового обслуживания общего вида 158
3.7 Структура разработанного программного комплекса анализа производительности компьютерных сетей на основе аппроксимативного подхода 169
3.8 Выводы 176
ГЛАВА 4. Применение разработанных методов и моделей к анализу и расчету самоподобного трафика 178
4.1 Введение в самоподобные процессы 178
4.2 Распределения с тяжелыми хвостами РТХ 183
4.3 Принципы описания структуры трафика и установление связи между коэффициентами Херста и вариации интервалов времени между событиями потока 185
4.4 Сравнительный анализ результатов расчетов классических моделей массового обслуживания и 196 моделей на основе РТХ
4.5 Исследование на самоподобие реальных трафиковых процессов и установление связи с РТХ 199
4.6 Другие подходы к восстановлению моментных характеристик интервалов времени для целочисленных процессов 207
4.7 Выводы 212
ГЛАВА 5. Применение разработанных методов к анализу производительности сетевых структур 213
5.1 Моделирование основного фрагмента сети филиала Центробанка РФ с неоднородными потоками 213
5.1.1 Моделирование работы сети филиала Центробанка РФ в режиме номинальной нагрузки 215
5.1.2 Моделирование работы сети филиала Центробанка РФ в высоконагруженном режиме 221
5.2 Проектирование и моделирование сети кафедры ВУЗа 225
5.2.1 Методика сбора сетевого трафика 228
5.2.2 Сбор статистики для одного сегмента сети и формирование матриц вероятностей передач 234
5.2.3 Определение длины пакета и интенсивности обслуживания сетевых устройств 237
5.2.4 Анализ производительности сети кафедры в программном комплексе на основе аппроксимативного подхода
5.3 Имитационное моделирование сети кафедры в системе Opnet Modeler 254
5.4 Моделирование сети двух факультетов ВУЗа
5.4.1 Анализ трафика и моделирование сети факультетов в программном комплексе на основе аппроксимативного подхода 261
5.4.2 Имитационное моделирование сети факультетов в системе Opnet Modeler 273
5.5 Моделирование сети факультетов и кафедр с
использованием механизма NAT 278
5.6 Выводы 283
ГЛАВА 6. Анализ производительности корпоративных сетей 286
6.1 Анализ структуры трафика сети ВУЗа 286
6.2 Моделирование сети ВУЗа в программном комплексе
на основе аппроксимативного подхода 289
6.3 Имитационное моделирование сети ВУЗа в системе OPNET Modeler 297
6.4 Моделирование сети ВУЗа с использованием механизма NAT 301
6.5 Корпоративная сеть энергосбывающей компании 304
6.6 Анализ и расчет параметров глобальных каналов связи удаленных офисов компании 308
6.7 Моделирование корпоративной сети ОАО «Оренбургэнергосбыт» в программном комплексе на основе аппроксимативного подхода 320
6.8 Имитационное моделирование корпоративной сети ОАО «Оренбургэнергосбыт» 329
6.9 Выводы 339
Заключение 341
Список использованных источников
- Обзор математического и программного инструментария моделирования компьютерных сетей
- Математическое мультиплексирование потоков на основе их диффузионной аппроксимации
- Метод обобщенной двумерной диффузионной аппроксимации процессов функционирования СМО общего вида и расчет ее характеристик
- Принципы описания структуры трафика и установление связи между коэффициентами Херста и вариации интервалов времени между событиями потока
Введение к работе
Актуальность проблемы. В предисловии к монографии Вишневского В. М. «Теоретические основы проектирования компьютерных сетей» академиками РАН Е. П. Велиховым и Н. А. Кузнецовым сказано, что повсеместное внедрение компьютерных сетей должно сопровождаться опережающим развитием фундаментальной теории в этой области, созданием инженерных методов анализа и синтеза, систем автоматизации проектирования, направленных на сокращение сроков и повышение качества проектирования компьютерных сетей.
Современные методы и модели анализа производительности компьютерных сетей явно можно разделить на два направления: аналитическое вероятностное моделирование на основе теории массового обслуживания (ТМО) и имитационное (дискретно-событийное) моделирование. Методы первого направления, основанные на последних результатах теории массового обслуживания, ограничиваются пуассоновскими потоками в сетях систем массового обслуживания (СМО) 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 наименований литературы.
Обзор математического и программного инструментария моделирования компьютерных сетей
Проектирование компьютерных сетей, как и любой другой сложной системы, начинается с этапа системного проектирования. На этом этапе создается математическая модель сети, и она исследуется с помощью, ЭВМ; Построение математической модели компьютерной сети в целом, из-за сложности процессов ее функционирования, оказывается практически трудновыполнимой. задачей. В этом случае сеть декомпозируют на- отдельные подсистемы, сохраняя связи между ними. Тогда к компьютерной сети можно применить определение сложной- системы, как многоуровневой конструкции из взаимодействующих элементов, объединяемых в подсистемы различных уровней [62].
Как правило, стохастические объекты, учитывающие случайные факторы, могут быть описаны вероятностными автоматами, системами массового обслуживания и марковскими процессами. . Компьютерную сеть будем рассматривать как вычислительную систему, т.е. совокупность элементов: и подсистем, предназначенную для выполнения определенного набора услуг, предоставляемых пользователям сети. Оценкой качества работы сети будут служить показатели эффективности функционирования: загрузка каналов, время задержки сообщений (пакетов), производительность, объем памяти буферов и др.
В последнее время сложность компьютерной сети как объекта исследования увеличивается. Можно перечислить причины увеличивающейся сложности: - претерпевает изменение характер . поступающей нагрузки; - строже становятся требования к информационной безопасности и надежности сети; - изменились критерии качества функционирования сети, оценивающиеся по конечному результату предоставления пользователям информационных услуг, а не качеством работы отдельных подсистем; - изменился характер услуг: видеоконференции, передача голосовых сообщений; - в процессе эксплуатации меняется состав предоставляемых услуг. К особенностям создания корпоративных сетей можно отнести [102]: - сохранение имеющегося ресурса; - масштабирование сети; - на основе опорной сети объединение локальных сетей, рабочих групп в единую интегрированную сеть. При системном проектировании сети решаются три группы задач: - синтез топологической структуры; - реализация технологии доставки информации по сети; - управление взаимодействием. На сегодняшний день практически все средние и крупные потребители услуг сетей передачи данных (СПД) не ограничиваются только локальными сетями и услугами. Все больше растет потребность в корпоративных, распределенных сетях передачи данных.
Корпоративные сети передачи данных (КСПД) представляют собой территориально распределенные, соединенные между собой сегменты единой сети, использующие выделенные централизованные ресурсы и сервисы.
Цель построения корпоративных сетей передачи данных — обеспечение транспорта для территориально распределенных бизнес-приложений. К таким приложениям обычно относят сетевые базы данных, информационные порталы, электронную почту, традиционный файловый обмен, IP телефонию, видеоконференцсвязь и дистанционное обучение. Это же в полной мере касается и построения корпоративных сетей ВУЗов, где на первом месте стоит качественная организация учебного процесса.
КСПД - один из важнейших инструментов развития бизнеса. Качественную и надежную корпоративную сеть имеют, в первую очередь, географически распределенные компании, бизнес которых зависит от надежности и гибкости совместной работы ее подразделений [97].
При создании КСПД необходимо, сохраняя уже имеющийся ресурс, провести масштабирование, объединить локальные сети служб, рабочих групп, производств, офисов в единую интегрированную сеть. Этот момент определяет состав и топологию сети. В корпоративной сети выделяются три структурообразующих звена - локальные сети; - базовая магистральная сеть; - межсетевые устройства - коммутаторы для сопряжения локальных сетей с базовой сетью.
Построение КСПД в общем - это организация связности по протоколу IP между рабочими станциями и серверами предприятия. Сеть образуется совокупностью узлов связи, располагаемых на территории офисов или других точек присутствия предприятия. В основе построения корпоративных сетей передачи данных положена методология проектирования компании Cisco Systems на основе композитной сетевой модели предприятия. Данное решение - это модульный подход к построению структуры сети. Методология решения позволяет строить как небольшие сети, объединяющие несколько офисов, так и крупные, включающие сотни узлов. Развивая сеть путем добавления новых модулей или узлов, подход обеспечивает предсказуемость качественных характеристик сети и требует минимальных усилий и средств для поиска и устранения неисправностей.
В основе композитной модели (рисунок 1.3) лежит принцип разделения сети на модули (декомпозиции). Каждый модуль характеризуется свойственными только ему функциями и особенностями реализации. Ключевым компонентом, связующим узлы КСПД, является услуга связи, которая обеспечивает передачу трафика между узлами. Виды услуг связи, используемые при организации каналов между узлами, делятся на следующие группы: 1) выделенные линии связи - оптические или медные кабели, соединяющие узлы сети заказчика (это могут быть как свои, так и арендуемые линии связи); 2) выделенные каналы данных - каналы данных, предоставляемые оператором связи поверх своей сети передачи данных: Frame Relay (PVC); ATM (PVC); E1/E3/STM-1; Ethernet VLAN; 3) услуги по соединению на базе «группового» доступа:
Математическое мультиплексирование потоков на основе их диффузионной аппроксимации
Из математической теории надежности известно [66], что функция распределения для остаточного времени жизни элемента, т.е. вероятность безотказной работы элемента на интервале времени (J, t + x) до очередного отказа определяется как 1 Р(В1 т) = —l[l-FT(t)]dt, где Т0-\1Х - среднее время жизни элемента. Применительно к нашему случаю это будет вероятность Р(х - t) = Xj l[l-FXj(u)]du. Тогда интересующая нас вероятность t события P(xR t) по формуле полной вероятности, может быть записана в виде: P(xR t)=P(xl t) P(xr2 t)-\l%L+P(x2 t)-P(x\ 0-V s (2-! -3) где X-L=Xl+X2, а вероятность Х:/Х% представляет собой долю j -го потока в результирующем. Из выражения (2.1.3) непосредственно и следует справедливость утверждения 1. Утверждение 1 доказано. Теперь, используя функцию распределения (2.1.2), можем определить среднее значение и дисперсию распределение величины xR. Для этого введем обозначения: 00 00 8i(0= \[l-Fx{u)}du, g2(t)= \[\-F2{u)]du. (2.1.4) t t Тогда, как известно из [66], средние значения интервалов между событиями в потоках равны: Т] =gj(0), т2 = g2(0) т-е- эти функции в т.О равны соответствующим средним значениям интервалов времен в потоках. Не сложно показать, что функция плотности fXR (t) = F;R (t) = [gl(t) -g2(or Математическое ожидание, т.е. среднее значение интервала между событиями в результирующем потоке 00 Т, Л 00 Т. Л 00 О Б О Е О -1[g.«-ft(0]lf=0 + T12 = J-, (2.1.5) что полностью подтверждает справедливость интегрального выражения (2.1.2). Определим теперь второй начальный момент распределения интервала т для вычисления дисперсии этой случайной величины: СО Л 1 СО 1 1 м(х)= \t2fR{t)dt = №gl(t).g2(t)Tdt= {t2[gl(t).g2(t)} tS О Е О Е О л2 О = 2 Ь(0-Я2(0 (2.1.6) As о Тогда дисперсия времени между событиями в результирующем потоке 2Хтя) = 2Ьк/й(0-й«)А- - (2-1.7)
На основании полученных результатов для дисперсии времени между событиями в результирующем потоке (2.1.4) и (2.1.7), сформулируем следующее утверждение.
Утверждение 2. Дисперсию величины TR- интервала времени между событиями результирующего потока, а также моменты более высоких порядков, нельзя выразить в виде элементарных функций от дисперсий и математических ожиданий составляющих потоков. Таким образом, дисперсия величины iR и моменты высших порядков не разложимы. Следовательно, не существует точной формулы их определения.
Доказательство этого утверждения заключено в самом выражении (2.1.7) для вычисления дисперсии распределения интервалов времен между событиями в результирующем потоке.
Учитывая тот факт, что в сетевых моделях и в самих реальных сетях мы не знаем точных законов распределений потоков, остается единственно возможный путь для вычисления этого интеграла через элементарные функции - это аппроксимация функций gi(t) (/=1,2) на уровне двух первых моментов распределений интервалов времени. Эти моменты можно на практике определить путем съёма трафика с помощью программно-аппаратных средств измерения трафика в узлах сети.
Таким образом, будем считать, что потоки в сетевых моделях определены на уровне средних значений т и дисперсий DT распределений интервалов, и функции распределения Fj(t) будем аппроксимировать отдельно при с .1 и с . 1 (/= 1, 2). В качестве примера возьмем два экспоненциально распределенных потока с параметрами Х1иХ2 Fx{t) = l-e 1?,F2(t) = l-e 2 . Тогда по формуле (2.1.7) дисперсия величины xR - Dx =1/А,. Это означает, что при мультиплексировании потоков, распределенных по экспоненциальному закону, снова получается пуассоновский поток. В качестве следующего примера рассмотрим два независимых потока событий, распределенных по равномерному закону на интервале (0;1). Тогда дисперсия величины xR по формуле (2.1.7) О _3_ 80 1 1 \ч) DXR=2j[j(l-u)du\(\-u)du]dt 0 t t Выражение, аналогичное (2.1.2), без доказательства приведено в [123].
В качестве функции распределения в случае с 1 рассмотрим смещенное экспоненциальное распределение, а в случае с - гиперэкспоненциальное. Функция распределения в первом случае 1-ехр{-(?-ту1)/ту2}, t xj{ а во втором І И0 - 1 , (2.2.1) F it X-p -lpjtlT -iX-pj -lil-p lx j]. (2.2.2) Теперь возникает задача выбора параметров распределений (2.2.1) и (2.2.2). Для этого определим функции gj(t) по формуле (2.1.4), подставив в их выражения функцию (2.2.1) в случае с .- 1, (7=1,2): (0 = Іт,2-ехр{-( -туі)/т,2}, t xn (2-2-3) В случае c j \ подставим (2.2.2) в выражение (2.1.4) для функции gj(t): gJ(t) = T {exp[-2pjt/T ] + exp[-2(l-pJ)t/ i ]}/2. (2.2.4)
Если же при этом один поток будет иметь коэффициент вариации меньше 1, а другой - больше 1, то в таком случае функции gj(t), очевидно, будут скомбинированы из выражений (2.2.1) и (2.2.2). Параметры искомых аппроксимирующих функций распределений (2.2.1) и (2.2.2) подберем, используя метод моментов, приравняв их первые два момента к соответствующим моментам х- и Д. распределений исходных потоков. Математическое ожидание случайной величины, распределенной по закону (2.2.1), равно т = \t-ехрН/-тд)/xj2}/xJ2 -dt = -exp{-(t-xjX)/xj2} \A + + Jexp{-( - Tji)/Tj2 } flfr =Tyl + T7-2 . Также, проинтегрировав дважды по частям, найдем дисперсию распределения (2.2.1): Используя метод моментов, запишем: Г ту1+т,2 = т, Отсюда параметры функции распределения (2.2.1) равны: ч=ъ- - =v 7- 2-2-5 Аналогично, те же операции проделаем с функцией распределения (2.2.2). В этом случае функция плотности /у.(0=(2 /т})-ехрК2 /х}).ґ]+[2(1-Ру)2/т}]-ехрЬ2(1- )/х}) ]. Математическое ожидание случайной величины т , распределенной по этому закону, равно Ty=V Из равенства первых моментов получим первую часть выражения(2.2.6), а дисперсию этой величины т/ найдем, дважды проинтегрировав по
Таким образом, параметры функций распределений F (t) и FJ2\t), аппроксимирующих законы распределений Fj(t), составляющих результирующего потока, полностью определены для всех случаев: при с .- 1 - (выражения (2.2.5)) и при с .- \ (выражения (2.2.6) и (2.2.7)). Тогда, подставив функции gj(t) (/—1,2) с однозначно определенными их параметрами, в выражение (2.1.7) и после вычисления всех интегралов, можем определить дисперсию интервала времени мультиплексированного потока [6].
Метод обобщенной двумерной диффузионной аппроксимации процессов функционирования СМО общего вида и расчет ее характеристик
В классической литературе по теории массового обслуживания недостаточно внимания уделено вычислению моментных характеристик мультиплексированных (агрегированного) потоков и демультиплексированного (разреженного) потока. Например, в [87] приводятся формулы вычисления дисперсии результирующего потока для случая предельного пуассоновского потока, а разреженного — для случая потоков Пальма. Следует заметить, что вышеприведенные результаты справедливы для любых стационарных потоков.
Теперь, после того, как определены математические операции мультиплексирования и демультиплексирования потоков, по аналогии с уравнениями баланса потоков на уровне их средних значений (2.1.1), можем записать уравнения баланса относительно их дисперсий. Для этого повторно заметим, что на входе в /- й узел в общем случае агрегируются (мультиплексируются) разреженные (демультиплексированные) выходные потоки от у-го узлов (/=0, 1, 2,..., »). Дисперсии времен между событиями этих потоков, полученные по формуле (2.6.2) равны: Dnji= (DBbKj+—%L) (i,j=l,2,...,n). (2.7.1) Тогда уравнения баланса однородных потоков на уровне дисперсий времен между событиями на входе и выходе /-го узла сетевой модели можно записать в виде уравнений DBXl =)(Я0/ (Я1/ ... (ЯЯ_І І ЯІІ/))). (2.7.2) Здесь и в дальнейшем, выражение D{nj_lti IIji) означает операцию вычисления дисперсии попарно мультиплексируемых по формулам (2.3.5),(2.3.9) и (2.4.2) выходных потоков от (/-1)-го (Яу.1(/) и у -го узлов (#у7), поступающих на вход z-го узла.
Обозначение D0i- дисперсия потока П0і, поступающего на вход Ї-го узла от внешнего источника. Значения дисперсий выходных потоков DBWiJ в уравнениях (2.7.1) будут определены в главе 3.
Тогда решение уравнений (2.1.1) и (2.7.2) позволяет декомпозировать сетевую модель на отдельные узлы на уровне двух первых моментов распределений потоков для последующего расчета их характеристик. Для решения задачи декомпозиции предлагается итерационная процедура, состоящая из следующих шагов. 1. В качестве начального приближения считаем сетевую модель как экспоненциальную сеть (сеть Джексона) и тогда системы уравнений (2.1.1) и (2.7.2) становятся линейными. Решением систем линейных алгебраических уравнений (2.1.1) и (2.7.2) определяем средние значения т - = XJ и дисперсии DBXi интервалов времени между соседними1 заявками во входных потоках для каждой СМО сети МО. Матрицы коэффициентов при неизвестных в этих системах не вырождены и поэтому существует единственное решение. 2. Используя значения %ХІ и Дхг- для /=1,...,п, полученные на первом шаге, применяем метод двумерного диффузионного приближения (см. главу 3) для нахождения дисперсий времени между соседними заявками в выходном из /-ой СМО потоке DBblxl, а затем уже уточняем значения входных дисперсий )вх/ по формулам (2.7.1), (2.7.2) совместно с (2.3.5), (2.3.9), (2.4.2). 124 3. Подставляем полученные значения дисперсий DBXi в систему (2.7.2) и повторяем шаг 2) в случае необходимости. Как показывают практические вычисления, на это требуется обычно несколько уточнений в связи с хорошей обусловленности системы (2.7.2).
Рассмотрим теперь случай, когда сетевая модель включает также узлы с конечной очередью и потерями, например, канальные буферы (рис.2.21, здесь О - очередь, а П — обслуживающий прибор).
Тогда в сетевой модели будут циркулировать также потоки отказов (избыточные потоки), вследствие чего в уравнениях баланса потоков (2.1.1) и (2.7.2) появятся дополнительные слагаемые. Для этого необходимо определить характеристики избыточного потока аналогично характеристикам выходного потока. Интенсивность потока отказов может быть определена по формуле Л-ОТК / ОТК ВХ) (2.8.1) 125 где ротк - вероятность потери заявки. Ее определение по методу двумерной диффузионной аппроксимации процессов функционирования СМО показано в главе 3. Отсюда среднее время между заявками в потоке отказов может быть определено по формуле тотк =1А0ТК . (2.8.2) С другой стороны, на основании баланса интенсивности потоков на входе и выходе узла следует Хвх =А,ВЫХ + -отк или Тотк = вх вых ІЛшх- твх/ {2.0.3) Этот факт в дальнейшем будет учтен для контроля вычислений. Для определения дисперсии DT0TK времени между соседними заявками в избыточном потоке, воспользуемся результатами, полученными при выводе формулы (2.6.2) п. 2.6. Так как избыточный поток получается из входного -преобразованием с вероятностью ротк , то дисперсия времени между событиями в избыточном потоке
Принципы описания структуры трафика и установление связи между коэффициентами Херста и вариации интервалов времени между событиями потока
Ниже в табл. 3.1 приведена часть результатов вычислений среднего количества заявок в системе N (первое значение — результат метода обобщенной двумерной диффузионной аппроксимации, через дробь - результаты имитационного моделирования). Имитационное моделирование проводилось с использованием программной системы расчета СМО с встроенным генератором псевдослучайных последовательностей гамма-распределения. Из таблицы 3.1 и из рисунков 3.5 а), б) видно, как увеличение коэффициентов вариаций распределений входного потока и времени обслуживания ухудшает показатели-производительности системы.
Проведены также расчеты характеристик СМО с потерями с использованием В- формулы Эрланга. Результаты расчетов частично отражены на рис. 3.6 и 3.7. Из них видно, что результаты расчетов для таких СМО также хорошо согласуются с теоретическими значениями. На рис. 3.6 и 3.7 приведены примерные графики зависимостей вероятности потери сообщения. ротк в каналах приема-передачи от интенсивности X входного потока (при интенсивности обслуживания Р- = 1) и от объема буферной памяти- т, выраженного в единицах от сообщений. Графики построены для диапазона изменения коэффициента вариации времени, обслуживания заявок сц от 0,1 до 2 ,0 при коэффициенте вариации распределения времен поступления сх=1, т.е. для пуассоновского входного потока. Аналогичные графики построены для среднего времени ожидания (рис. 3.8, 3.9). Графики, приведенные на рисунках 3.6-3.9, позволяют рассчитать необходимые объемы памяти для буферных накопителей при ограничениях на вероятность потери и на время задержки сообщения в узле коммутации. При этом значения объемов, выраженные в единицах от сообщений, можно пересчитать в единицы.от бит умножением значений объемов на среднюю длину сообщения. -—___ Из вышеприведенных графиков, видно, что при увеличении объема буфера среднее время ожидания W стремится к времени ожидания СМО в случае с бесконечной очередью (пунктирная линия на рис. 3.9).
Вышеуказанный подход расчета узловых характеристик в программной системе реализован в виде процедур GG1 и GGM совместно с методом декомпозиции сети МО на отдельные СМО решением уравнений баланса потоков на уровне двух первых моментов распределений интервалов времен поступления и обслуживания (см. главу 2).
На рисунке 3.5 приведены примерные графики зависимости среднего времени ожидания сообщений в узле от параметров трафика и закона обслуживания.
Эти результаты доказывают необходимость учета при вычислении показателей производительности сетевых моделей вторых моментов (дисперсий) распределений временных параметров трафика и обслуживания в узлах, что не может быть сделано методами теории экспоненциальных сетей или другими приближенными методами с такой точностью и за приемлемое время. Графики построены по данным таблицы 3.1.
На рисунках 3.6 и 3.7 приведены примерные графики зависимостей вероятности потери сообщения ротк в каналах приема-передачи от интенсивности X входного потока (при интенсивности обслуживания ц = 1) и от объема буферной памяти т, выраженного в единицах от сообщений. Такие же примерные графики построены для среднего времени ожидания W . Графики построены для диапазона изменения коэффициента вариации времени обслуживания заявок сц от 0,1 до 2,0 при коэффициенте вариации распределения времен поступления сх=\.
Ниже, в таблицах 3.2 -3.5, приведены расчеты среднего времени ожидания Wt, среднего количества заявок в системе S0 и дисперсии выходного потока Dtl при варьировании параметров потока: загрузки от 0,05 до 0,99; коэффициентов вариаций времени обслуживания cm и входного потока с/ - от 0,1 до 5,0. N = р + р (1 + Сц)/(2(1 - р)) можно убедиться, что относительная погрешность модели не превышает 5%. Например, для последней таблицы 3.5, среднее количество заявок в системе М/М/1 - N = 0,99 + 0,992 /0,01 = 99,0. В таблице 3.5 это значение равно 99,37. Дисперсия выходного потока для этого случая равна 1/0,992 = 1,020, а в таблице это значение равно 1,013.
Структура разработанного программного комплекса анализа производительности компьютерных сетей на основе аппроксимативного подхода Ниже, на рис. 3.11 приведена укрупненная схема алгоритма работы программы. Коротко опишем основные процедуры. Процедуры VNGG1 и VNGGM рассчитывают характеристики отдельных систем G/G/1 и G/G/m соответственно. Данные работы этих процедур были приведены выше в п.3.6. Процедуры VNGG1 и VNGGM реализуют вычисления по методикам разделов 3.3 и 3.4 соответственно.
Процедура UODNET предназначена для расчета характеристик сетей при однородном (агрегированном) трафике по методике разделов 2.1-2.7. Алгоритм работы процедуры UODNET описан в разделе 2.7. Процедура UODNET работает совместно с процедурами DISP, MULTIPLM, VNGG1 (см. рис. 3.12-3.15).
Схема алгоритма процедуры MULTIPLM описана и приведена в п.2.5. Процедура DISP определяет и уточняет методом итераций дисперсии входящих и исходящих потоков в сети массового обслуживания по рабочим формулам главы 2.
Процедура UNEODNET предназначена для расчета сетевых моделей с неоднородным трафиком, путем приведения его к обобщенному однородному потоку. Методика расчета характеристик сетевой модели с неоднородным трафиком описана в п.2.9. В этой процедуре расчет трафика может проводиться по различным протоколам. Данная процедура взаимодействует с процедурами UODNET, DISP, MULTIPLM, VNGG1 (см. рис. 3.11 и 3.12). Таким образом, программный комплекс автора «Анализ производительности компьютерных сетей на основе аппроксимативного подхода» целиком и полностью опирается на теоретическом материале второй и третьей глав.
