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

БАХАРЕВА Надежда Федоровна

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

МАССОВОГО ОБСЛУЖИВАНИЯ

ДЛЯ ИССЛЕДОВАНИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ

Специальность 05.13.15 – Вычислительные машины,

комплексы и компьютерные сети

АВТОРЕФЕРАТ

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

Пенза 2011

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» на кафедре программного обеспечения и управления в технических системах.

Научный консультант – доктор технических наук, профессор Тарасов Вениамин Николаевич

Официальные оппоненты: доктор технических наук, профессор Алиев Тауфик Измайлович;

доктор технических наук, профессор Прохоров Сергей Антонович;

доктор технических наук, профессор Султанов Борис Владимирович

Ведущая организация: ФГУ «Государственный научноисследовательский институт информационных технологий и телекоммуникаций» (г. Москва)

Защита диссертации состоится «13» октября 2011 г. в «14» часов на заседании диссертационного совета Д 212.186.01 при Пензенском государственном университете по адресу: 440026, г. Пенза, ул. Красная, 40.

С диссертацией можно ознакомиться в библиотеке Государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет».

Автореферат размещен на сайте ВАК.

Автореферат разослан «07» сентября 2011 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Гурин Е. И.

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

Актуальность проблемы. В предисловии к монографии Вишневского В. М. «Теоретические основы проектирования компьютерных сетей»

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

Современные методы и модели анализа производительности компьютерных сетей явно можно разделить на два направления: аналитическое вероятностное моделирование на основе теории массового обслуживания (ТМО) и имитационное (дискретно-событийное) моделирование. Методы первого направления, основанные на последних результатах теории массового обслуживания, ограничиваются пуассоновскими потоками в сетях систем массового обслуживания (СМО) 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 (X 2 ) / / ется равенством W =, для системы M/G/1 – W =. Здесь 1 М(Х 2 ) означает 2-й начальный момент времени обслуживания. Наконец, для 2 D + D + (1 ) / I системы G/G/1 это время равно W =. Здесь – загрузка системы; – интенсивность входного потока; D, D – соответственно дисперсии интервалов поступления и времени обслуживания;

I и I 2 – соответственно среднее значение и второй начальный момент периода простоя, которые неизвестны. Из приведенных выражений следует, что при анализе сетей МО G/G/1 необходимо учитывать дисперсии времен поступления и обслуживания.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведен анализ состояния и тенденций развития средств моделирования и исследования основных показателей производительности сетей.

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

Это связано с имеющимися ограничениями современных программных продуктов для проектирования и моделирования сетей передачи данных.

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

В связи с этим, в работе обоснована необходимость разработки собственных адекватных реальным сетям моделей и методов анализа производительности компьютерных сетей. Для проверки достоверности полученных результатов при решении поставленных задач использована программная система Opnet Modeler IT GURU дискретно-событийного моделирования сетей связи.

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

В настоящее время не существует аналитических методов для точного определения моментных характеристик интервалов потоков в сетевых моделях, кроме как на уровне их средних значений. Для сетевых моделей с произвольными потоками, состоящих из систем G/G/1 или G/G/m, необходимость учета дисперсий времен поступления и обслуживания очевидна.

Рассмотрим открытую сетевую модель с матрицей вероятностей передач P = {pi j}, (i, j = 1, …, n), где pij – вероятность того, что заявка, покидающая узел Si, поступит в узел Sj. В сетях связи аналогом этой матрицы будет «матрица тяготений узлов», состоящая в основном из 0 и 1. Далее рассмотрим полную структуру отдельного узла с номером i сетевой модели (рис. 1).

Рис. 1. Полная структура потоков в i-м узле сетевой модели Решением системы уравнений равновесия потоков (1) относительно интенсивностей i на входе и выходе каждой СМО сети определяем средние значения интервалов времен между соседними заявками i = i1 для каждого потока в сети:

где 0i – интенсивность потока извне в i-й узел (см. рис. 1).

На рис. 1 точка А – точка композиции (агрегирования) потоков, точка В – точка декомпозиции (вероятностного разрежения) агрегированного потока. Из рисунка и уравнений (1) следует, что на входе i-го узла агрегируются (знак ) разреженные выходные потоки ( p ji j ) от других узлов. Это будет отправной точкой для вывода уравнений равновесия потоков относительно дисперсий интервалов для их последующего восстановления.

Узел представляет собой многоканальную (с равным доступом) систему G/G/m c бесконечной очередью, для которой определены числовые характеристики случайного времени обслуживания: i – среднее значение и Di – дисперсия времени обслуживания. Для внешнего потока задана совокупность средних значений 0i и дисперсий D0i времени между соседними заявками потока, входящего в узел Si. При знании характеристик внешнего потока ставится задача восстановления средних значений и дисперсий интервалов между заявками во всех потоках такой сетевой модели.

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

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

Агрегирование (мультиплексирование) двух потоков.

Среднее значение и дисперсия интервала времени R в результирующем потоке при агрегировании двух независимых потоков с интенсивностями 1 и 2 с функциями распределения вероятностей (ФРВ) F1 (t ) и F2 (t ) Здесь случайная величина R не является суммой величин 1 и 2, т.е. не имеет места композиция законов распределений. С другой стороны, результирующий поток в этом случае не будет рекуррентным, кроме случая пуассоновских составляющих.

Из выражения (3) следует, что дисперсию D нельзя выразить в элементарных функциях через дисперсии составляющих, кроме случая пуассоновских составляющих. Для практического применения выражения (3) исходные неизвестные ФРВ F j (t ) интервалов аппроксимируем функцией смещенного экспоненциального распределения в случае, когда коэффициенты вариаций составляющих c j 1 (j = 1, 2):

В случае c j > 1 исходные функции распределений аппроксимируем гиперэкспоненциальным распределением:

В смешанном случае одну ФРВ аппроксимируем функцией (4), а другую – (5). Тогда задача определения D по формуле (3) сводится к вычислению табличных интегралов. Если же вместо функций (4) и (5) рассматривать более общие законы распределений типа Вейбулла или гамма, задача (3) усложняется в связи с появлением специальных функций в интегралах. Задавая исходные агрегируемые потоки на уровне средних значений j и дисперсий D j интервалов между событиями в потоках, неизвестные параметры функций (4) и (5) находим известным методом моментов:

Имитационное моделирование агрегирования двух потоков на широком классе распределений показало, что в случае c j > 1 формула (4) не обеспечивает 5 % относительную погрешность. Для этого случая в работе предложен второй способ аппроксимации потоков, а именно их диффузионное приближение, которое дает лучший результат.

Аппроксимируем дискретный процесс поступлений N(t) со средним = 1/ и дисперсией D интервалов непрерывным диффузионным процессом x(t). Тогда процесс x(t) при больших t будет гауссовским процессом со средним значением t / и дисперсией D t / 3. Сумма двух независимых процессов N (t ) = N1 (t ) + N 2 (t ) также будет гауссовским случайt / R = t / 1 + t / При этом равенства (2) и (6) являются равносильными и точными.

Выражение (7) – приближенное, но точное для пуассоновских потоков.

В дальнейшем применение формулы (3) или (7) к потокам П1 и П2 будем сокращенно обозначать D (П1 П 2 ), и эти формулы будут математической моделью мультиплексирования потоков.

Разрежение (демультиплексирование) потоков.

При вероятностном разрежении потока со средним значением и дисперсией D времени между событиями (точка В на рис. 1 и 2), в которой заявки с вероятностью p 0 уходят из потока (просеянный поток 2), среднее значение и дисперсия времени между соседними Рис. 2. Разрежение потока Аналитические выражения (8) и (9) являются математической моделью операции демультиплексирования потока на уровне средних значений и дисперсий времени между событиями (p – преобразование потока). Полученное из формул (8) и (9) выражение для квадрата коэффициента вариации просеянного потока 2: c 2 = p c 2 + q позволяет судить о характере распределения этого потока – разрежение исходного потока существенно влияет на его закон распределения, кроме случая пуассоновского потока.

Все доказанные утверждения в работе проверены с помощью имитационного моделирования по специально разработанным программам агрегирования и разрежения потоков. Для этого проводились серии из пяти испытаний, в каждом из которых генерировались по 10000 интервалов. Интервалы генерировались по экспоненциальному, равномерному, нормальному, Вейбулла, гамма и другим законам распределений времени между заявками. Результаты имитационного моделирования полностью подтверждают справедливость утверждений. Относительная погрешность моделирования при этом не превышает 5 %.

Используя формулы (3), (7) и (9) для суммы разреженных потоков на входе i-й СМО сетевой модели, дисперсию интервалов времени между соседними заявками в суммарном входном потоке в стационарном режиме можно выразить через известные параметры сети и дисперсии Dвых j выходных потоков j-й СМО сети (i, j = 1, …, n) (см. рис. 1):

дисперсии попарно мультиплексируемых разреженных выходных потоков П j 1 вых и П j вых от (j – 1)-го и j-го узлов по формулам (3) или (7) в зависимости от величин коэффициентов вариаций составляющих. Эти потоки при p ji 0 поступают на вход i-го узла после их p-преобразования по формуле (9) с дисперсиями:

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

Система (10) совместно с (11) решается методом итераций. На каждой итерации дисперсия D j вых времени между соседними заявками в выходном из j-й СМО потоке определяется методом двумерной диффузионной аппроксимации СМО, тем самым уточняются значения дисперсий D i вх входных потоков. В программе процесс уточнения завершается по достижении 1 % относительной погрешности. Методика определения дисперсий интервалов времени между заявками в выходных потоках D j вых будет описана в следующей главе.

При решении некоторых частных задач из области сетевых технологий, а именно: при определении загрузки каналов или других ресурсов сети, а также при определении задержек «источник – адресат» в сетях связи, в матрице вероятностей передач P = {pij}(i, j = 1, …, n) – элементы pij принимают значения в основном 0 и 1. В связи с этим уравнения (1) и (10) в таком случае упрощаются. В более общем случае, когда сетевая модель может включать узлы с ограничениями на объемы канальных буферов (СМО G/G/1/k с потерями), уравнения (1) и (10) модифицируются. Они модифицируются также в случае неоднородных потоков как моделей трафика мультисервисных сетей.

Рассмотрим первый случай с узлами с конечной очередью и потерями. С учетом потоков отказов (избыточные потоки) в уравнениях баланса потоков (1) и (11) появятся дополнительные слагаемые. Для этого вначале определим характеристики избыточного потока аналогично характеристикам выходного потока.

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

Для определения дисперсии Dотк времени между соседними заявками в избыточном потоке воспользуемся выражением (9). Тогда где вх – интенсивность входного потока вх = вх1, а Dвх – дисперсия времени между заявками во входном потоке. Тогда уравнения баланса потоков, циркулирующих в стохастической сети на уровне средних значений и дисперсий времени между заявками в потоках:

Diвх = D(П0i (П1вых, i... (Пn1вых, i Пnвых, i )) (П1i... (Пизб i Пизб ))). (13) Примечание. Уравнения баланса потоков (1) и (10) будут частными случаями уравнений (12) и (13) соответственно в случае отсутствия в сетевой модели узлов с конечной очередью и потерями.

Далее рассмотрим случай неоднородного трафика. Пусть от внешнего источника S0 в сеть (на вход i-й СМО) поступает неоднородный поток заявок с интенсивностями 0i и дисперсиями D0i для каждого типа заявок m (m = 1,..., M; i = 1,..., n). Матрица вероятностей передач для каждого типа заявок m – P ( m ) = { pijm) } (i, j = 1, …, n). Уравнения баланса интенсивностей потоков заявок для каждого типа m на входе и выходе каждой СМО сети имеют вид Это так называемые открытые сети, но, как будет видно из главы 5, некоторые классы заявок могут циркулировать только в замкнутой сети.

В этом случае значения ( m) = 0, и тогда i m) будут выражать относительi ные частоты посещения заявкой типа m узла i.

Параметры потоков заявок из множества заявок типа m усредним с целью приведения неоднородного потока к однородному, с соблюдением условия: чтобы однородный поток заявок на обслуживание «усредненной»

заявки создавал такую же нагрузку на каждую СМО сети, как и неоднородный поток, т.е.

Уравнения баланса неоднородного потока относительно интенсивностей и дисперсий интервалов между соседними обобщенными заявками на входе и выходе каждой СМО сети имеют вид, аналогичный (1) и (10):

где D Тогда итерационная процедура расчета сети с неоднородным потоком заявок будет такая же, что и для однородного потока (описана выше).

Программно данная методика декомпозиции сети МО на отдельные СМО реализована каскадным способом с переключательной схемой. Если число типов потоков в сети M = 1, то системы уравнений (15) и (16) автоматически трансформируются в системы (1) и (10) для однородных потоков соответственно. Аналогично, если в сети МО отсутствуют узлы с ограниченной очередью, то системы уравнений (12) и (13) также трансформируются в системы (1) и (10) соответственно.

Третья глава посвящена разработке и исследованию метода обобщенной двумерной диффузионной аппроксимации СМО общего вида, включающей системы G/G/1/ и G/G/1/m. К примеру, ее выходная характеристика (дисперсия интервалов выходного потока) D j вых входит в уравнения равновесия потоков, полученные во второй главе. Точных методов для расчета характеристик такой системы на данный момент не существует. Рассмотрим функционирование СМО G/G/1, управляемой не всегда рекуррентным входным потоком с параметрами и D – средним и дисперсией интервала времени между событиями входного потока. Среднее значение и дисперсию времени обслуживания обозначим как и D.

Вероятностные процессы поступления N1(t) и обслуживания N2(t), являющиеся дискретными ступенчатыми процессами, аппроксимируем на периоде занятости СМО непрерывными марковскими (диффузионными) процессами х1(t) и х2(t) соответственно. При этом дискретные и непрерывные процессы будут определенно согласованы на уровне двух первых моментов. Тогда коэффициенты сноса ai = i1 и диффузии bi = Di i3 (i = 1, 2) процесса {х1(t), х2(t)} однозначно выражаются через известные средние значения i и дисперсии Di интервала времени между скачками дискретного процесса Ni. Текущее значение N числа заявок, находящихся в СМО, определяется разностью целой части от x1 и целой части от х2: N = [x1] [х2] (рис. 3).

Выделим область, определенную условиями N 0 и Nmax = m (m – максимально допустимое число заявок в СМО). В области плотность распределения (t, x1, x2) векторного диффузионного процесса {х1(t), х2(t)} удовлетворяет уравнению Колмогорова Область снизу ограничена ступенчатой поглощающей границей Г1, определенной условием [N] = 0 и физически означающей завершение периода занятости, а сверху – ступенчатой отражающей границей Г2 (переполнение буфера). Таким образом, Рис. 3. Область решения уравнения Траектория двумерного процесса {х1(t), х2(t)} соединяет начало и конец периода занятости, т.е. физически означает длину периода занятости.

Обозначим через k(y2) распределение ординаты процесса x2(t) в момент прохождения процессом {х1(t), х2(t)} границы x1 = k + 1 области k.

Аналогично, через k(y1) распределение ординаты процесса х1(t) в момент достижения границы x2 = k той же области. При достижении траекторией процесса {х1(t), х2(t)} границы Г2 ордината процесса х1(t) мгновенно должна сдвинуться вниз на единицу, что будет означать потерю очередной «лишней» заявки (траектория 2).

Учитывая сложный характер границы, решение уравнения (17) в области будем искать в виде совокупности решений:

в прямоугольных подобластях k = (x1 k + 1, x2 k) (k = 1, 2,...), где Qk (•) – функция Грина. Затем эти решения будем «сшивать» на границах подобластей. Через решение (18) выведены рекуррентные формулы для определения плотностей распределений k(y2) и k(y1):

где Q (•) и Q (•) – соответствующие функции перехода с уровня k – 1 на уровень k (рис. 3). Вычисления интегралов в (19) и (20) в программе реализованы по квадратурным формулам Гаусса с 15-ю узлами.

Распределение ординаты процесса х1(t) в момент достижения двумерным процессом {х1(t), х2(t)} границы Г1 (траектория 1) – k ( y1) k(y1) позволяет определить все основные характеристиy1) = ки функционирования СMO, а также неизвестные параметры p0, и D, входящие в формулы для определения характеристик выходного потока.

Неизвестные параметры: p0 – вероятность того, что обслуженная заявка оставляет СМО пустой, и D – среднее значение и дисперсия остаточного времени, в течение которого СМО ожидает поступления непосредственно следующей заявки, т.е. времени простоя СМО.

Пусть вых, Dвых,, D – соответственно средние значения и дисперсии времен между заявками в выходном потоке из CMO G/G/1/ и времени обслуживания. Тогда справедливы следующие аналитические выражения для определения вых, Dвых с любой точностью:

Методика расчета основных характеристик СМО начинается с определения параметров двумерного диффузионного приближения p0, и D.

Обозначим математическое ожидание и дисперсию распределения (y1) через m и D. Тогда искомые параметры выражаются через известные параметры входного потока и D – среднее и дисперсию интервалов и моментные характеристики распределения (y1).

Обозначим через pk вероятность того, что за весь период занятости в СМО пришло ровно k заявок (k = 1, 2,...): pk = k (y1 )dy1, и пусть за достаточно большой интервал времени Т имело место m периодов занятости.

Из них в среднем за mi = m · pi (i = 1, 2,...) периодов занятости через СМО прошло ровно i заявок.

Тогда вероятность p0 того, что обслуженная заявка оставляет СМО пустой, может быть выражена через вероятности pk :

Определим теперь среднее время ожидания W, используя известную формулу для системы G/G/1 через первые два начальных момента распределения случайной величины I – периода простоя:

В выражении (23) неизвестно второе слагаемое в правой части. Метод двумерной диффузионной аппроксимации СМО позволяет определить математическое ожидание квадрата случайной величины I. Для этого заметим, что I = = m, а I = D m + m2, где m2 = D + m – второй начальный момент распределения ( y1 ). Окончательно для среднего времени ожидания получим Остальные характеристики такой СМО определяются как производные среднего времени ожидания по классическим формулам теории массового обслуживания.

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

а среднее количество заявок в СМО Среднее время ожидания можно определить по формуле W = m, где m – математическое ожидание распределения ( y2 ) = i ( y2 ).

Все выше приведенные характеристики СМО определяются через моментные характеристики распределений вероятностей k(y2) и k(y1).

Для их определения в работе получены рекуррентные формулы через решение уравнения Колмогорова (17) для данной задачи.

В главе проведены расчеты для широкого диапазона изменения параметров потоков (загрузки узлов от 0,01 до 0,99, коэффициентов вариаций распределений времен поступления и обслуживания от 0,1 до 5,0). Относительная погрешность составляет 5–6 %. При этом точность предлагаемой методики оценивалась в сравнении, как с известными результатами теории МО, так и с результатами имитационного моделирования.

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

1. В качестве начального приближения сетевой модели берется экспоненциальная сеть (Джексона), тогда системы уравнений (1), (10) совместно с (11) будут линейными. Решением их методом Гаусса с выбором главного элемента определяются средние значения i = i 1 и дисперсии D i вх интервалов во входных потоках для каждой СМО сети МО. Матрицы коэффициентов при неизвестных в этих системах не вырождены, и поэтому существует единственное решение.

2. Используя значения i и D i вх для i = 1, …, n, полученные на первом шаге, применяем метод обобщенной двумерной диффузионной аппроксимации для нахождения дисперсий интервалов в выходном из i-й СМО потоке D i вых, а затем уже уточняем значения дисперсий входных потоков D i вх по формулам (10), (11) совместно с (3) или (7) в зависимости от величины коэффициента вариации.

3. Подставляем полученные значения дисперсий D i вх в систему (10) и повторяем этап 2 до достижения 1 % относительной погрешности.

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

В работах D. L. Jagerman, B. Melamed, W. E. Leland, M. S. Taqqu, W. Willinger и других авторов рассматривался стационарный неотрицательный процесс X n, определяющий последовательность интервалов времени между поступлениями трафикового процесса. Обозначим функцию распределения процесса X n через FX ( x), интенсивность трафика – X = 1/ M ( X n ), дисперсию – 2 = 2 ( X n ), коэффициент вариации интерваX лов c X = X X. Предполагается, что для потока 0 < <, и P { X n = 0} = 0.

Четкую связь между значениями индекса дисперсии J X и X, где – коэффициент корреляции последовательности X n, дает выражение Эта характеристика используется для описания структуры сетевого трафика. Если рассматривать сетевой трафик как процесс восстановления (с независимыми интервалами), т.е. при X = 0, то коэффициент вариации интервалов между событиями потока можно использовать в роли характеристики (описателя) структуры трафика.

Этот факт и послужил основанием к возможности применения метода двумерной диффузионной аппроксимации, развитого в главе 3, к анализу и расчету самоподобного трафика в случае cX > 1. Среди функций распределений с тяжелым хвостом (РТХ), описывающих самоподобные процессы, рассмотрен подкласс так называемых субэкспоненциальных распределений, куда можно отнести распределения Вейбулла, гамма, логнормальное и гиперэкспоненциальное. Эксперименты с искусственно сгенерированными процессами, интервалы в которых распределены по указанным распределениям, позволили установить связь между коэффициентами Хёрста H и вариации cX. Таким образом, если величина H > 0,5, то и cX > 1.

В главе на многочисленных экспериментах показано, что классические модели массового обслуживания дают заниженные результаты по задержкам в сравнении с непуассоновскими моделями трафика. Например, если входящий трафик распределен по закону гамма с характеристиками m = D = 0, 25 (коэффициент вариации времени между пакетами c = 2,0 ), то значения для среднего времени ожидания W, определенные методами двумерной диффузионной аппроксимации и имитационного моделирования, Рис. 4. Укрупненная схема сегмента Данный сегмент можно также рассматривать как многофазную СМО, так как с сервера обработки на терминалы по обратной связи могут передаваться некорректные документы.

В этом сегменте участвуют удаленные терминалы и многопроцессорный обрабатывающий сервер. При анализе этой сети рассмотрены два преобладающих типа трафика. Это в первую очередь платежи, по которым в сутки проходит порядка 45–50 тыс. документов. Интенсивность поступления запросов первого типа трафика равна ( ) 0,579 док./с. Интенсивность обработки платежа составляет (1) 2 док./с.

Второй тип трафика – это поток статистической отчетности от кредитных организаций и расчетно-кассовых центров (РКЦ). Учитывая, что в среднем поступает 7620 документов в сутки, интенсивность запросов второго типа составит ( ) = 0,088 док./с. Интенсивность обработки запросов (2) = 1 док./с.

Загрузка обрабатывающего сервера в виде системы M/M/1 составила = 0,398 ( ( ) = 0,305; ( ) = 0,093), а времена задержки u ( ) = 0,71 с и u ( ) = 1,09 с. В случае равномерного закона распределения времен поступления и обслуживания загрузки те же, а времена задержки меньше:

u ( ) = 0,58 с, u ( ) = 1,03 с. Для такой загрузки сервера выбрано оптимальное число процессоров, равное 5.

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

Далее в главе рассмотрена сеть кафедры вуза. Для формирования исходных данных для применения авторской программы к практическим расчетам использован программный комплекс съема трафика NetFlow Analizer (безотносительно к типам трафика) и PRTG Traffic Grapher (с учетом типа трафика). С использованием этих программных средств, проводился сбор статистики для трафика по интересующим нас протоколам HTTP, FTP и NetBIOS как преобладающего трафика. Анализ трафика для такой сети показал, что 88 % его составляет внешний трафик и только 12 % – внутренний. Часть отчета по трафику сети в пакетах показана на рис. 5.

Длина пакета принята равной 763 байта (половина от максимальной длины 1526 байт). Анализ дневного трафика сети кафедры показывает, что его среднее значение интенсивности (в пакетах/мин) равно 790, а дисперсия – 1393473, что говорит о том, что он сильно отличается от пуассоновского. При этом недельные значения его показывают, что коэффициент вариации c времени между пакетами может колебаться от 1,5 до 8. Максимальное значение интенсивности равно 12153/60 203 пакета/с (см. рис. 5).

В сети кафедры (рис. 6) выделены маршрутизатор Cisco 2621 как внешний источник, сервер, главный коммутатор Cisco 2924, неуправляемые коммутаторы Cisco 1912 и подсети LAN1-LAN3, моделирующие работу трех компьютерных классов (10 рабочих станций в каждом). Сети отделов (офисов) предприятий имеют примерно такую же структуру. В свою очередь, в дальнейшем при анализе сети вуза или корпоративных сетей, Показатели производительности будем оценивать при максимальных значениях интенсивности трафика. Сравнение результатов имитационного (рис. 6) Рис. 6. Результаты имитационного моделирования сети кафедры Также очевидно, что реальные загрузки каналов связи и узлов будут еще меньше, так как рассматривалось поведение сети при максимальном значении интенсивности входящего трафика. Следовательно, существует резерв по пропускной способности, позволяющий задействовать в сети дополнительные сетевые приложения.

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

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

Рис. 7. Результаты расчетов входящего трафика сети кафедры В этой же главе исследована сеть двух факультетов вуза. Как и в случае с сетью кафедры, детально проанализирован трафик этой сети.

Максимальное значение интенсивности входящего трафика составило 4030 пакетов/с. Среднее значение интенсивности трафика – 16095 (пакетов/мин), дисперсия 1100877197, что также подтверждает сильное отличие от пуассоновского потока. Коэффициент вариации интервалов колеблется от 2 до 9,9.

Сравнение результатов численного (табл. 1) и имитационного (рис. 8) моделирования по загрузке показывает их совпадение до доли процента.

Адекватность модели реальной сети подтверждает тот факт, что результат загрузки канала сети кафедры VT (1,4 % / 0,8 %) на рис. 5 и 8, а также при численном моделировании (табл. 1, 2) полностью совпадают.

Часть результатов моделирования входящего трафика сети факультетов Узловые характеристики Средняя задержка, с 0,00013 0,00011 0,00007 0,00007 0,00007 0,00007 … 0, Среднее число заявок 0,5110 0,4046 0,0286 0,0309 0,0140 0,0577 … 0, Сетевые характеристики Ср. время ожидания, с Средняя задержка, с Средняя длина очереди Производительность Время расчета: 0,218 с Часть результатов моделирования исходящего трафика сети факультетов Узловые характеристики Средняя задержка, с 0,00012 0,00011 0,00007 0,00007 0,00007 0,00007 … 0, Среднее число заявок 0,3881 0,3865 0,0233 0,0257 0,0076 0. 0458 … 0, Сетевые характеристики Ср. время ожидания, с Средняя задержка, с Средняя длина очереди Производительность Время расчета: 0,156 с Результаты моделирования показали (рис. 8), что максимальная загрузка каналов связи составляет 26,3 % (входящего канала) и 21,6 % (исходящего канала), и это при пиковом значении нагрузки. Следовательно, реальная загрузка каналов и узлов у этой сети меньше, и поэтому имеется также большой запас производительности, так как задержки в сети минимальны.

Рис. 8. Результаты моделирования сети двух факультетов Численное моделирование для этих показателей при непуассоновском потоке (коэффициент вариации времени между пакетами равен 2) дает результаты 0,33 мс для сети кафедры и 0,34 мс – для сети факультетов.

Эти данные полностью согласуются с результатами главы 3. Полученные показатели производительности свидетельствуют об устойчивой работе рассмотренных сетей. Существует резерв по пропускной способности, позволяющий задействовать в сети дополнительные сетевые приложения, как для сетей кафедр, так и для сети факультетов. Учитывая, что указанная сеть двух факультетов в свою очередь является подсетью корпоративной сети вуза, куда входят еще сети остальных 10 корпусов, дополнительно исследован их «вклад» в общую нагрузку.

В шестой главе проведено исследование двух корпоративных сетей – вуза и ОАО «Оренбургэнергосбыт». Они разнятся, во-первых, функциональным назначением, а во-вторых – наличием в последней большой доли трафика IP-телефонии. Эти сети можно рассматривать как большие многозвенные ЛВС.

Сеть вуза включает 11 подсетей корпусов и факультетов, 6 подсетей филиалов, главный коммутатор, сервер и маршрутизатор. При этом сети филиалов подключены к сети вуза с помощью выделенных каналов Интернет и будут играть роль внешнего источника. В этой сети как сети третьего уровня учтены подробно структурные связи подсетей факультетов и корпусов вплоть до сетей кафедр и отделов, т.е. сетей второго и нижнего уровней. К примеру, сеть двух факультетов (сеть 2-го уровня), представленная в общей сети как подсеть UNPK, исследована в главе 5. Эта сеть в свою очередь включает сети кафедр как сети нижнего уровня. Одна из таких сетей представлена сетью кафедры ВТ и исследована подробно также в главе 5. Подсети представляют собой отдельные ЛВС кафедр, факультетов и корпусов, объединенные в общую сеть каналами связи на 100 Мбит/с.

Каналы связи Интернет маршрутизатор Cisco 3640 проксисервер главный коммутатор Cisco 4506 представляют собой гигабитные каналы. Канал Интернет от провайдеров может достигать ширины полосы до 100 Мбит/с.

Исследование трафика всей сети вуза в течение месяца позволило определить максимальное значение интенсивности входящего трафика – 14500 пакетов/с, а коэффициент вариации близок к 2,5. Для исходящего трафика максимальная интенсивность – 13550 пакетов/с. Часть результатов моделирования сети вуза в авторской программе представлена в табл. 3. Исследованная ранее сеть двух факультетов здесь представлена узлом 6 – UNPK.

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

Часть результатов численного моделирования входящего трафика сети вуза Узловые характеристики Средняя задержка, с 0,00449 0,00001 0,00001 0,00007 0,00007 0,00009 … 0, Сетевые характеристики Ср. время ожидания, с Средняя задержка, с Средняя длина очереди Производительность Время расчета: 0,344 с В проведенных исследованиях в явном виде использован метод декомпозиции сетей на подсети вплоть до узлов с подробным анализом входящего и исходящего трафика. Такой подход в свою очередь повышает степень адекватности моделей реальным сетям.

Сеть ОАО «Энергосбыт» включает следующие основные ресурсы:

маршрутизатор Cisco 2621, прокси-сервер, серверы БД, 1С, IP-телефонии, 3 коммутатора Cisco 2948 и 8 подсетей отделов. Внешний канал Интернет провайдера до 50 Мбит/с, каналы от Cisco 2621 до прокси-сервера, от 4-х серверов до главного коммутатора Cisco 2948_0, от него до коммутаторов Cisco 2948_1 и Cisco 2948_2 – гигабитные. Остальные каналы – 100 Мбит/с.

Результаты имитации внутренней сети компании приведены на рис. 9.

Рис. 9. Результаты имитационного моделирования сети компании При анализе корпоративной распределенной сети компании вначале исследовались высоконагруженные каналы «удаленный офис» «центральный офис». При ширине полосы в 2 Мбит/с от провайдера и максимальной интенсивности трафика 275 пакетов/с загрузка канала составила 91,7 %, а средняя задержка 40,3 мс. Такая задержка удовлетворительна даже для голосового трафика.

Результаты численного моделирования нагрузок на каналы (табл. 4) и имитации совпадают с точностью до долей процента, максимальная относительная погрешность не превышает 2,5 %.

Часть результатов численного моделирования сети компании Узловые характеристики Средняя задержка, с 0,0018 0,00001 0,00001 0,00001 0,00001 0,00001 … 0, Среднее число заявок 12,130 0,033 0,011 0,032 0,011 0,063 … 0, Сетевые характеристики Ср. время ожидания, с Средняя задержка, с Средняя длина очереди Производительность Время расчета: 0,688 с Результаты табл. 4 показывают, что задержки сети до подсетей минимальны, значения нагрузок на каналы свидетельствуют о наличии большого резерва производительности.

При исследовании корпоративной распределенной сети «Энергосбыт», кроме расчета стандартных показателей производительности, были учтены специфические требования к трафику IP-телефонии:

– задержка в среде передачи данных не должна превышать 150 мс;

– потери пакетов не должны превышать 1 %.

В связи с этим была исследована передача данных на приоритетной основе на портах маршрутизаторов узлов, подключаемых к межофисной телекоммуникационной сети, т.е. в точке входа трафика данных в зону сети с ограниченной пропускной способностью. Таким образом, узкое место данной сети – глобальный канал связи с провайдером. При пропускной способности канала в обе стороны в 2 Мбит/с максимальная загрузка (при пиковом значении интенсивности общего входного трафика – 275 пакетов/с) наиболее загруженного канала «удаленный офис» «Центральный офис» составила около 92 %, а задержка – до 40 мс.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Доказана адекватность предложенных математических моделей агрегирования и разрежения потоков имитационным моделированием полученных аналитических выражений на широком классе законов распределений с помощью специально разработанных программ. Относительная погрешность моделей не превышает 5 %.

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

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

Полученные результаты сравнивались с результатами известных методов ТМО и результатами имитационного моделирования. Относительная погрешность метода не превышает 5 %.

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

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

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

9. Разработан программный комплекс «Анализ производительности компьютерных сетей на основе аппроксимативного подхода», в котором реализованы предложенные методы и модели. Для формирования исходных данных для его применения к практическим расчетам использован программный комплекс съема трафика NetFlow Analizer (безотносительно к типам трафика) и PRTG Traffic Grapher (с учетом типа трафика).

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

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

Основное содержание работы

полностью раскрывается Статьи в изданиях, рекомендованных ВАК РФ 1. Бахарева, Н. Ф. Моделирование трафика в компьютерных сетях с помощью потоков событий / Н. Ф. Бахарева // Известия вузов. Приборостроение. – 2010. – Т. 53, № 12. – С. 13–22.

2. Бахарева, Н. Ф. Анализ временных характеристик непуассоновского трафика / Н. Ф. Бахарева, И. В. Карташевский // Электросвязь. – 2010. – № 11. – С. 26–28.

3. Бахарева, Н. Ф. Программная система анализа производительности компьютерных сетей на основе аппроксимационного подхода / Н. Ф. Бахарева // Инфокоммуникационные технологии. – 2010. – Т. 8, № 3. – С. 54–60.

4. Бахарева, Н. Ф. Программная реализация математических операций мультиплексирования и демультиплексирования потоков для сетевых моделей / Н. Ф. Бахарева // Вестник Самарского государственного аэрокосмического университета им. С. П. Королева. – 2009. – № 4. – С. 171–185.

5. Бахарева, Н. Ф. Уравнения равновесия потоков в сетевых моделях на основе математических операций мультиплексирования и демультиплексирования / Н. Ф. Бахарева // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2009. – № 4. – С. 12–25.

6. Бахарева, Н. Ф. Анализ производительности сетевых структур методами теории массового обслуживания / Н. Ф. Бахарева // Научно-технические ведомости СПбГПУ. – 2009. – № 3. – С. 25–34.

7. Бахарева, Н. Ф. Двумерная диффузионная аппроксимация системы массового обслуживания общего вида и расчет ее характеристик / Н. Ф. Бахарева // Научно-технические ведомости СПбГПУ. – 2009. – № 2. – С. 7–14.

8. Бахарева, Н. Ф. Обобщенная двумерная диффузионная модель массового обслуживания типа GI/G/1 / Н. Ф. Бахарева, В. Н. Тарасов // Телекоммуникации. – 2009. – № 7. – С. 2–8.

9. Бахарева, Н. Ф. Аппроксимативная модель массового обслуживания общего вида и расчет ее характеристик / Н. Ф. Бахарева, В. Н. Тарасов // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2009. – № 3. – С. 47–58.

10. Бахарева, Н. Ф. Анализ и расчет непуассоновских моделей трафика в сетях ЭВМ / Н. Ф. Бахарева, И. В. Карташевский, В. Н. Тарасов // Инфокоммуникационные технологии. – 2009. – Т. 7, № 4. – С. 61–66.

11. Бахарева, Н. Ф. Декомпозиция сетей массового обслуживания без ограничений на длину очереди / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Научно-технические ведомости СПбГПУ. – 2008. – № 2. – С. 31–36.

12. Бахарева, Н. Ф. Декомпозиция сетей массового обслуживания при избыточных и неоднородных потоках / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Научно-технические ведомости СПбГПУ. – 2008. – № 2. – С. 9–13.

13. Бахарева, Н. Ф. Моделирование мультисервисной сети Центробанка РФ / Н. Ф. Бахарева, А. Л. Коннов // Инфокоммуникационные технологии. – 2008. – Т. 6, № 1. – С. 76–79.

14. Бахарева, Н. Ф. Проектирование и моделирование мультисервисной сети кафедры вуза / Н. Ф. Бахарева, А. Л. Коннов // Инфокоммуникационные технологии. – 2008. – Т. 6, № 3. – С. 132–138.

15. Бахарева, Н. Ф. Управление нагрузкой на сети ЭВМ распознаванием и моделированием трафика / Н. Ф. Бахарева, Ю. А. Ушаков // Инфокоммуникационные технологии. – 2008. – Т. 6, № 3. – С. 56–62.

16. Бахарева, Н. Ф. Программная система распознавания трафика и прогнозирования характеристик мультисервисной сети / Н. Ф. Бахарева, Ю. А. Ушаков // Инфокоммуникационные технологии. – 2008. – Т. 6, № 4. – С. 42–50.

17. Бахарева, Н. Ф. Организация интерактивной системы вероятностного моделирования стохастических систем / Н. Ф. Бахарева, В. Н. Тарасов // Известия Самарского научного центра РАН. – 2003. – № 1. – С. 119–126.

18. Бахарева, Н. Ф. Проблема совершенствования методов моделирования сложных систем / Н. Ф. Бахарева, В. Н. Тарасов // Вестник Оренбургского государственного университета. – 2002. – № 5. – С. 162–169.

19. Бахарева, Н. Ф. Программно реализованная марковская модель массового обслуживания с переменными параметрами поступления и обслуживания для анализа сложных систем / Н. Ф. Бахарева, В. Н. Тарасов // Вестник Оренбургского государственного университета. – 2002. – № 3. – С. 166–170.

20. Бахарева, Н. Ф. Непрерывные диффузионные модели массового обслуживания и методика расчета их характеристик / Н. Ф. Бахарева, В. Н. Тарасов // Вестник Оренбургского государственного университета. – 2002. – № 2. – С. 199–204.

Свидетельства о регистрации программ для ЭВМ 21. Бахарева, Н. Ф. Анализ производительности компьютерных сетей на основе аппроксимативного подхода. Свидетельство об официальной регистрации программы для ЭВМ № 2010613539, Роспатент, М., 28.05.2010.

22. Бахарева, Н. Ф. Агрегирование и разрежение потоков событий методом Монте Карло. Свидетельство об официальной регистрации программы для ЭВМ № 2010613562, Роспатент, М., 31.05.2010.

23. Бахарева, Н. Ф. Интерактивная система вероятностного моделирования стохастических систем. Свидетельство об официальной регистрации программы для ЭВМ № 2004610070, Роспатент, М., 05.01.2004.

24. Бахарева, Н. Ф. Интерактивная программная система вероятностного моделирования вычислительных систем на основе двумерной диффузионной аппроксимации – PROBMOD. Свидетельство о регистрации программного средства УФАП ГОУ ОГУ № 167 от 19.06.2006.

25. Бахарева, Н. Ф. Исследование и моделирование трафика в компьютерных сетях / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Труды 9-й Всерос.

межвуз. науч.-практ. конф. – Самара : СамГТУ, 2010. – С. 6–9.

26. Бахарева, Н. Ф. Исследование компьютерных сетей методом декомпозиции на подсети / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Наука и образование: фундам. основы, технологии, инновации : тр. Междунар. конф. – Оренбург : ОГУ, 2010. – С. 220–224.

27. Бахарева, Н. Ф. Анализ производительности корпоративной сети ОГУ в системе OPNET Modeler / Н. Ф. Бахарева, В. Н. Тарасов, А. Л. Коннов // Новые технологии в промышленности, науке и образовании : тр. 2-й Всерос. науч.-практ.

конф. – Оренбург : ВТУ, 2010. – С. 284–288.

28. Бахарева, Н. Ф. Исследование сети кампуса в системе OPNET Modeler / Н. Ф. Бахарева, В. Н. Тарасов, А. Л. Коннов // Проблемы техники и технологии телекоммуникаций: матер. XI Междунар. науч.-техн. конф. – Уфа, 2010. – С. 151–153.

29. Бахарева, Н. Ф. Исследование производительности компьютерных сетей на основе анализа их трафика / Н. Ф. Бахарева, В. Н. Тарасов, А. Л. Коннов // Перспективные информационные технологии для авиации и космоса (ПИТ– 2010) : избранные тр. Междунар. конф. – Самара : СГАУ, 2010. – С. 259–263.

30. Бахарева, Н. Ф. Математические операции с потоками событий как с моделями трафика в компьютерных сетях / Н. Ф. Бахарева // Цифровая обработка сигналов и ее применение : докл. 12-й Междунар. конф. – М., 2010. – С. 295–297.

31. Бахарева, Н. Ф. АРМ проектировщика мультисервисных сетей связи / Н. Ф. Бахарева, С. Л. Гавлиевский // Проблемы техники и технологий телекоммуникаций (ПТиТТ–2009) : матер. Х Междунар. науч.-техн. конф. – Самара :

ПГУТИ, 2009. – С. 125–127.

32. Бахарева, Н. Ф. Моделирование компьютерных сетей для анализа их производительности / Н. Ф. Бахарева, В. Н. Тарасов // Проблемы техники и технологий телекоммуникаций (ПТиТТ–2009) : материалы Х Междунар. научнотехнич. конф. – Самара : ПГУТИ, 2009. – С. 143–144.

33. Бахарева, Н. Ф. Анализ производительности компьютерных сетей методом декомпозиции / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Труды VIII Всерос. Межвуз. науч.-практ. конф. – Самара : СамГТУ, 2009. – С. 6–9.

34. Бахарева, Н. Ф. Проектирование сетей связи с заданными характеристиками / Н. Ф. Бахарева, В. Н. Тарасов // Труды IV Всерос. науч.-практ. конф. – Оренбург : ОГУ, 2009. – С. 127–134.

35. Бахарева, Н. Ф. Математические модели мультиплексирования и демультиплексирования потоков в моделях компьютерных сетей / Н. Ф. Бахарева // Проблемы управления и моделирования в сложных системах : тр. ХI Междунар.

конф. – Самара : СНЦ РАН, 2009. – С. 167–178.

36. Бахарева, Н. Ф. Математические модели мультиплексирования и демультиплексирования потоков / Н. Ф. Бахарева // Труды Российского науч.-техн.

общ. радиотехники, электрон. и связи им. А. С. Попова. Серия «Цифровая обработка сигналов и ее применение». – Вып. ХI-1. – М., 2009. – С. 209–212.

37. Бахарева, Н. Ф. Исследование компьютерных сетей методами теории массового обслуживания / Н. Ф. Бахарева, В. Н. Тарасов // Проблемы управления и моделирования в сложных системах : тр. Х Междунар. конф. – Самара : СНЦ РАН, 2008. – С. 181–91.

38. Бахарева, Н. Ф. Двумерная диффузионная аппроксимация управляемой системы массового обслуживания общего вида GI/G/1 / Н. Ф. Бахарева, В. Н. Тарасов, Ю. А. Ушаков // Проблемы управления и моделирования в сложных системах : труды Х Междунар. конф. – Самара : СНЦ РАН, 2008. – С. 192–199.

39. Бахарева, Н. Ф. Анализ сетевых структур методами массового обслуживания / Н. Ф. Бахарева // Проблемы техники и технологий телекоммуникаций :

IX Междунар. науч.-техн. конф. – Казань, 2008. – С. 110–112.

40. Бахарева, Н. Ф. Приближенный расчет сетей массового обслуживания на уровне двух первых моментов распределений интервалов поступления и обслуживания / Н. Ф. Бахарева, В. Н. Тарасов // Управление созданием и развитием систем, сетей и устройств телекоммуникаций : тр. науч.-практ. конф. – СПбГПУ, 2008. – С. 51–60.

41. Бахарева, Н. Ф. Уравнения равновесия потоков в сетях массового обслуживания на уровне двух первых моментов распределений интервалов поступления и обслуживания / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Управление созданием и развитием систем, сетей и устройств телекоммуникаций : тр.

науч.-практ. конф. – СПб. : СПбГПУ, 2008. – С. 163–172.

42. Бахарева, Н. Ф. Вероятностно-временные модели трафика в компьютерных сетях / Н. Ф. Бахарева // Труды XIV Рос. науч. конф. проф.-препод. состава, науч. сотрудников и аспирантов. – Самара : ПГАТИ, 2007. – С. 122–123.

43. Бахарева, Н. Ф. Исследование процессов функционирования ЛВС на имитационных моделях с целью ее оптимизации / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов // Перспек. инф.-технол. в научных исслед., проектир. и обучении :

тр. науч.-техн. конф. с междунар. уч. – Самара : СГАУ, 2006. – Т. 1. – С. 208–215.

44. Бахарева, Н. Ф. Выбор системы моделирования для расчета сглаживающего буфера / Н. Ф. Бахарева // Современ. информац. технологии в науке, образовании и практике : материалы Всерос. науч.-практ. конф. – Оренбург :

ОГУ, 2005. – С. 6–13.

45. Бахарева, Н. Ф. Расчет параметров телекоммуникационных систем с учетом эффекта самоподобия / Н. Ф. Бахарева // Современные информационные технологии в науке, образовании и практике : материалы Всерос. науч.-практ.

конф. – Оренбург : ОГУ, 2004. – С. 82–84.

46. Бахарева, Н. Ф. Современные методы и средства моделирования вычислительных систем в структуре дисциплины «Компьютерное моделирование» / Н. Ф. Бахарева // Современные информационные технологии в науке, образовании и практике : материалы Всерос. науч.-практ. конф. – Оренбург : ОГУ, 2004. – С. 8–16.

47. Бахарева, Н. Ф. Технологии Hot Desk компании Sun Microsystems как способ организации высокопроизводительных систем / Н. Ф. Бахарева, В. Н. Тарасов // Современные информационные технологии в науке, образовании и практике : материалы Всерос. науч.-практ. конф. – Оренбург : ОГУ, 2005. – С. 6–13.

48. Бахарева, Н. Ф. Разработка и внедрение математического и программного обеспечения вычислительной техники и автоматизация учебного процесса / Н. Ф. Бахарева, В. Н. Тарасов // Отчет НИР № г. р. 01950006416 инвентарный № 02200403823. – Оренбург : ОГУ, 2004. – 141 с.

49. Бахарева, Н. Ф. Особенности реализации интерактивной системы вероятностного моделирования вычислительных и телекоммуникационных сетей / Н. Ф. Бахарева // Современные информационные технологии в науке, образовании и практике : материалы рег. научн.-практ. конф. – Оренбург : ОГУ, 2003. – С. 67–70.

50. Бахарева, Н. Ф. Алгоритм функционирования интерактивной системы вероятностного моделирования стохастических систем / Н. Ф. Бахарева // Современные аспекты компьютерной интеграции машиностроительного производства : материалы Всерос. науч.-практ. конф. – Оренбург : ОГУ, 2003. – С. 185–186.

51. Бахарева, Н. Ф. Интерактивная система вероятностного моделирования сложных систем // Современные информационные технологии в науке, образовании и практике : материалы рег. научн.-практ. конф. – Оренбург : ОГУ, 2002. – С. 44–49.

52. Проектирование и моделирование сетей ЭВМ в системе OPNET Modeler : учеб. пособие / Н. Ф. Бахарева, А. Л. Коннов, В. Н. Тарасов, Ю. А Ушаков. – Изд. 2-е, перераб. – Самара, 2008. – 233 с. Рекомендовано ГОУ ВПО МГТУ им. Н. Э. Баумана в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 230105 «Программное обеспечение ВТиАС».

53. Компьютерное моделирование вычислительных систем. Теория, алгоритмы, программы : учеб. пособие / Н. Ф. Бахарева, В. Н. Тарасов. – Изд. 2-е, перераб. – Самара, 2009. – 208 с. Рекомендовано ГОУ ВПО МГТУ им. Н. Э. Баумана к использованию в образовательных учреждениях, реализующих образовательные программы ВПО по специальностям направления «Информатика и вычислительная техника».

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

МАССОВОГО ОБСЛУЖИВАНИЯ

ДЛЯ ИССЛЕДОВАНИЯ КОМПЬЮТЕРНЫХ СЕТЕЙ

Специальность 05.13.15 – Вычислительные машины, Подписано в печать 29.08.2011. Формат 60841/16.

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