Содержание к диссертации
Введение
ГЛАВА 1. Проблема совершенствования методов моделирования компьютерных систем 9
1.1 Примеры компьютерных систем, требующих моделирования 9
1.1.1 Компьютерные сети: анализ производительности и проектирование 9
1.1.2 Телекоммуникационные сети: анализ задержки 20
1.1.3 Конвергенция компьютерных и телекоммуникационных сетей 25
1.2 Существующие методы и модели анализа производительности компьютерных сетей 27
1.3 Обзор и точностной анализ известных аппроксимаци-онных методов 31
1.4 Постановка проблемы, цели и задачи исследования 41
1.5 Выводы 44
ГЛАВА 2. Теоретическое решение проблемы. Разработка метода расчета стохастических сетей на основе обобщенной двумерной диффузионной модели систем массового обслуживания (СМО) 45
2.1 Обобщенная двумерная диффузионная модель систем массового обслуживания (CMO)GI/G/l/co с бесконечной очередью и GI/G/1/m с конечной очередью и потерями 45
2.2 Обоснование уравнений баланса потоков в сетевой модели в случае однородного трафика 54
2.3 Модификация уравнений баланса потоков в случае неоднородного трафика 59
2.4 Модификация уравнений баланса потоков в случае избыточного трафика 62
2.5 Выводы 66
ГЛАВА 3. Определение основных показателей производительности сетевых моделей 67
3.1 Определение узловых и сетевых характеристик в случае однородного трафика 67
3.2 Определение характеристик сетевой модели в случае неоднородного трафика 70
3.3 Алгоритм расчета характеристик СМО GI/G/1/w с бесконечной очередью 72
3.4 Модификация алгоритма в случае СМО GI/G/1/ra с конечной очередью и потерями 80
3.5 Выводы 83
ГЛАВА 4. Организация интерактивной системы вероятностного моделирования стохастических сетей на основе разработанных методов 84
4.1 Структура программной системы 84
4.2 Функциональные возможности системы 92
4.3 Инструкция пользователя 96
4.4 Результаты проведенных расчетов и их анализ 106
4.4.1 Расчеты одиночных узлов сети 106
4.4.2 Применение программной системы к решению задач проектирования каналов связи и буферов 111
4.5 Выводы 121
Заключение 122
Список использованной литературы 123
Приложения 134
- Компьютерные сети: анализ производительности и проектирование
- Обобщенная двумерная диффузионная модель систем массового обслуживания (CMO)GI/G/l/co с бесконечной очередью и GI/G/1/m с конечной очередью и потерями
- Определение узловых и сетевых характеристик в случае однородного трафика
- Структура программной системы
Введение к работе
Несмотря на то, что объем знаний в такой динамической области как информационные технологии, быстро устаревает, остается такой пласт базовых знаний по решению задач анализа и синтеза в области компьютерных сетей, который еще и пополняется. Эти базовые знания заложили такие авторы, как L. Kteinrock, D. Ferrari, S. Golestani, Гнеденко Б.А., Цыбаков Б.С, Липаев В.В., Майоров С.А. и многие другие.
Независимо от того, какие технологии будут применять в локальных и глобальных сетях через 5-Ю лет, распределенные системы обработки данных (РСОД) еще долго будут существовать, и данные будут передаваться на основе коммутации пакетов, которые в будущем могут быть названы и иначе.
Актуальность проблемы. Проектирование компьютерных сетей, как и любой другой сложной системы, начинается с этапа системного проектирования и предполагает создание математической модели сети и исследование этой модели на ЭВМ. Достижения в области РСОД, сопровождаемые развитием информационных технологий, возросшие стоимости проектирования и самой проектируемой сети предъявляют повышенные требования к качеству проектных решений, в особенности к точности определения пропускных способностей каналов, времени задержки сообщений (пакетов), объемов памяти буферов и др. Одним из плодотворных подходов к оценке этих важнейших конструктивных показателей служит вероятностное моделирование, которому посвящены монографии вышеуказанных авторов. При таком моделировании компьютерные системы (сети ЭВМ и телекоммуникационные системы) представляются в виде совокупности ресурсов, использование которых осуществ-
ляется в порядке очереди в соответствии с заданной дисциплиной.
Достоверность результатов вероятностного моделирования с использованием теории массового обслуживания или теории очередей равно как и других методов зависит во многом от адекватности применяемых моделей реальным системам. Существенные результаты в этой области с разработкой и исследованием моделей двумерной диффузионной аппроксимации процессов функционирования систем массового обслуживания (СМО) получены в работах /64,67/ и др. Разработке вероятностных моделей трафика и методов анализа задержки в телекоммуникационных сетях посвящены работы /62,103,109/и др.
Другие известные методы из теории экспоненциальных сетей, а также приближенные методы на основе СМО не позволяют учитывать такие особенности как: широкий диапазон изменения параметров трафика, наличие избыточных потоков, обусловленные возможными ограничениями на ресурсы системы, неоднородность трафика и др.
По мнению известного специалиста в области математического моделирования сложных систем чл.-корр. РАН Павловского Ю.Н, разработка интерактивных систем моделирования, а в перспективе — интегрированной интерактивной системы, объединяющей экспертные, оптимизационные, имитационные и вероятностные системы является актуальной проблемой. Тогда математическое моделирование как технология все более будет походить на производственную технологию.
Объект исследований. Объектом исследований диссертационной работы являются сети ЭВМ и телекоммуникационные сети.
Предмет исследований. В диссертационной работе предметом исследований являются показатели производительности компью-
терных систем.
Целью данной работы является разработка интерактивной системы вероятностного моделирования компьютерных систем на основе метода обобщенной двумерной диффузионной аппроксимации, ориентированной на автоматизацию их системного проектирования.
Цель работы достигается решением следующих задач:
разработать и исследовать обобщенную модель двумерной диффузионной аппроксимации систем массового обслуживания (СМО);
разработать алгоритмы решения задачи анализа производительности сетевых моделей СМО типа GI/G/1/oo с бесконечной очередью и GI/G/1/m с конечной очередью и потерями на уровне средних значений и дисперсий распределений временных параметров трафика сети;
разработать интерактивную программную систему вероятностного моделирования сетевых моделей для определения их показателей производительности, ориентированную как на разработчиков и проектировщиков вычислительных систем, так и на учебный процесс по таким дисциплинам как: «Компьютерное моделирование», «Сети ЭВМ и телекоммуникации», «Анализ производительности вычислительных систем».
Методы исследования. Для решения поставленных задач использован аппарат теории вероятностей, теория сетей массового обслуживания, используемая в рамках теории вычислительных систем, теория марковских процессов, аналитическое и численное решение уравнений в частных производных в областях со сложными границами, объектно-ориентированное программирование.
Научная новизна работы заключается:
1) в разработке и исследовании обобщенной диффузионной мо-
дели систем, адекватно отображающей процессы функционирования компьютерных и телекоммуникационных сетей на уровне средних значений и дисперсий распределений вероятностей параметров трафика и времени обслуживания с учетом ограничений на их ресурсы;
в разработке методов расчета индексов производительности сетевых моделей таких систем;
в развитии разработанных методов на сетевые модели с неоднородным трафиком;
4)в исследовании изменчивости задержки сообщений для различных фрагментов сетей.
Практическая ценность работы заключается в разработанных
методике расчетов показателей производительности сетевых моделей компьютерных сетей с учетом ограничений на ресурсы сети и неоднородности трафика;
интерактивной системе вероятностного моделирования компьютерных систем как для специалистов в области сетевых технологий, так и для студентов специальностей направления подготовки «Вычислительная техника и информатика».
Результаты исследований, полученные в диссертационной работе внедрены и используются в ПО «Стрела», АО «Инвертор», СП Информэнергосвязь «Оренбургэнерго» г.Оренбург и в учебном процессе в Оренбургском государственном университете и в Поволжской государственной академии телекоммуникаций и информатики г.Самара.
Апробация работы. Основные научные положения и результаты диссертационной работы докладывались и обсуждались на:
- региональной научно-практической конференции с международным участием «Современные информационные технологии в науке, образовании и практике» (Оренбург, 2003);
региональной научно-практической конференции с международным участием «Современные информационные технологии в науке, образовании и практике» (Оренбург, 2002);
всероссийской научно-практической конференции «Современные аспекты компьютерной интеграции машиностроительного производства» (Оренбург, 2003);
IV всероссийской научно-технической конференции «Методы и средства измерений физических величин» (Н.Новгород, 1999).
Структура и объем диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных на 133 страницах машинописного текста, содержит 32. рисунка, П, таблиц, список литературы из 113 наименований, приложения на 49 страницах и 5 актов о внедрении.
Публикации. По результатам проведенных исследований опубликовано 10 работ.
На защиту выносятся:
Обобщенная диффузионная модель систем массового обслуживания различных типов(СМО GI/G/1/oo с бесконечной очередью и GI/G/1/ra с конечной очередью и потерями), адекватно отображающая процессы функционирования таких систем на уровне средних значений и дисперсий распределений параметров трафика.
Методика и алгоритм определения индексов производительности сетевых моделей компьютерных систем с учетом ограничений на ресурсы систем и неоднородности трафика сети.
Расчетные формулы для анализа задержки пакетов и других характеристик сети с учетом вышеуказанных особенностей.
Интерактивная программная система моделирования сетевых моделей компьютерных сетей с целью оценки их индексов производительности.
Компьютерные сети: анализ производительности и проектирование
При анализе работы сети сетевые составляющие времени реакции позволяют оценить производительность отдельных элементов сети и выявить узкие места, чтобы в дальнейшем выполнить модернизацию и повысить общую производительность ее работы.
Скорость передачи трафика может быть: - средней, вычисляемой как частное от деления общего объема переданных данных на время передачи, причем за длительный промежуток времени; - мгновенной (выбирается маленький промежуток времени); - максимальной - наибольшая скорость в течение периода наблюдения, которая позволяет оценить работу сети во время пиковых нагрузок.
При проектировании, настройке и оптимизации компьютерной сети используются средняя и максимальная скорость.
Пропускная способность не является пользовательской характеристикой в отличие от времени реакции и скорости передачи данных, так как она говорит о скорости выполнения внутренних операций сети - передачи пакетов данных между узлами сети через различные коммуникационные устройства. Она непосредственно характеризует качество выполнения основной функции сети - транспортировки сообщений и поэтому чаще используется при анализе производительности сети.
Пропускная способность не зависит от загруженности сети и имеет постоянное значение, определяемое используемыми в сети технологиями и характеристиками физической среды передачи. На разных участках сети, где используется несколько разных технологий, пропускная способность может быть различной. Для анализа и настройки сети необходимо знать эту характеристику для отдельных элементов, так как пропускная способность любого составного пути в сети будет равна минимальной для составляющих элементов маршрута /57/.
Максимальная задержка передачи и вариация задержки характеризуют качество работы сети. С точки зрения пользователя сети, задержки пакетов, порождаемых файловой службой, службой элек тронной почты и службой печати (обычно от сотни миллисекунд до нескольких секунд) мало влияют на качество этих служб. Но такие же задержки для мультимедийного трафика приводят к значительному снижению качества предоставляемой пользователю информации - возникновению эффекта «эха», искажению изображения и т.д. Пропускная способность и задержки передачи являются независимыми параметрами. Сеть может обладать высокой пропускной способностью, но вносить значительные задержки при передаче каждого пакета. При высокой пропускной способности 2 Мбит/с канала связи, образованного геостационарным спутником, задержка передачи всегда составляет не менее 0,24 с, так как она определяется скоростью распространения электрического сигнала и длиной канала /57/.
Особую сложность представляет совмещение в одной сети компьютерных данных традиционного и мультимедийного трафика так, чтобы не ущемлять интересы одного из типов трафика. К этой цели наиболее близки сети на основе технологии ATM. При передаче мультимедийного трафика под качеством обслуживания понимают величину задержки пакетов не более N мс, причем вариация задержки не более М мс на определенном временном интервале. Для традиционного компьютерного трафика нужны гарантии средней полосы пропускания и расширения ее на небольших интервалах времени до некоторого максимального уровня для быстрой передачи пульсаций /57/.
Если рассмотреть сеть с технологией ATM (Asynchronous Transfer Mode - режим асинхронной пересылки), которая ориентирована на работу с информацией различного типа, в том числе с аудио и видеоинформацией, можно отметить, что задержки при обработке данных сокращены, дисперсия задержек снижена. Служба класса А технологии ATM ориентирована на создание соединения и поддерживает постоянную скорость передачи битов и временные соотношения между отправлением и получением информации.
Однако, как отмечается в работе /62/, вследствие статистического мультиплексирования, различные пакеты одного и того же потока, проходя через узлы сети, могут встречать в них очереди различной длины и ожидать передачи из узла разное время. Это приводит к явлению джиттера, когда различные пакеты одного и того же потока испытывают разную задержку передачи по сети.
Возникает задача устранения джиттера применением сглаживающего буфера так чтобы, характеристика его: объем памяти, как можно меньше ухудшала среднюю задержку передачи информации в сети. «Интерактивная система вероятностного моделирования стохастических систем», реализованная в данной диссертационной работе может применяться для расчета буфера, если представить этот узел в схеме, как узел с ограниченной емкостью. Для мультимедийного трафика предъявляются жесткие требования к синхронности передаваемых сообщений, а трафик компьютерных данных импульсивный и характеризуется неравномерной интенсивностью поступления сообщений в сеть при отсутствии жестких требований к синхронности их доставки.
Обобщенная двумерная диффузионная модель систем массового обслуживания (CMO)GI/G/l/co с бесконечной очередью и GI/G/1/m с конечной очередью и потерями
Проектирование компьютерных сетей, как и любой другой сложной системы, начинается с этапа системного проектирования и предполагает создание математической модели систем и исследование этой модели на ЭВМ. Достижения в области РСОД, сопровождаемые развитием информационных технологий, возросшие стоимости проектирования и самой проектируемой системы предъявляют повышенные требования к качеству проектных решений, в особенности к точности определения пропускных способностей каналов, времени задержки сообщений (пакетов), объемов памяти буферов и др.
Как показывает анализ известных методов математического моделирования сложных систем и компьютерных сетей, функционирование которых можно описывать стохастическими сетевыми моделями, при произвольных законах распределения входного потока и времен обслуживания, не существует точных методов их расчета. Известные приближенные модели из-за неполной их адекватности имеют большую погрешность, и тем самым не позволяют анализировать режимы малой и средней загрузки сетей, учитывать неоднородность случайных потоков и произвольный закон распределения входного трафика, широкий диапазон изменения параметров трафика, наличие избыточных потоков, обусловленное возможными ограничениями на ресурсы системы (СМО типа GI/G/1/m) и др.
Поэтому встает вопрос о правомерности применения традиционных методов моделирования для анализа производительности системы в целом и приходится привлекать метод имитационного моделирования. Обладая универсальностью, он относится к трудо емким и дорогим методам исследования и имеет ограниченную эффективность (произведение дисперсии ошибки на время составления модели и расчета на ЭВМ).
В процессе проектирования обычно отсутствует подробная информация о законах распределения вероятностей параметров потоков, а имеются данные лишь о средних или средних значениях и дисперсиях этих распределений, что затрудняет моделирование, в том числе и имитационное.
Поэтому разработка метода расчета компьютерных сетей на основе обобщенной двумерной диффузионной модели систем массового обслуживания, который для всего диапазона загрузки от 0,1 до 0,9 дает равномерную приемлемую погрешность, позволит анализировать производительность в тех случаях, когда применение других приближенных методов либо дает ограниченную эффективность, либо затруднено, либо из-за неполной адекватности модели имеет большую погрешность.
Целью данной работы является разработка интерактивной системы вероятностного моделирования компьютерных систем на основе метода обобщенной двумерной диффузионной аппроксимации, ориентированной на автоматизацию их системного проектирования.
Цель работы достигается решением следующих задач: 1) разработать и исследовать обобщенную модель двумерной диффузионной аппроксимации систем массового обслуживания (СМО); 2) разработать алгоритмы решения задачи анализа производительности сетевых моделей СМО типа GI/G/ІЛ» с бесконечной очередью и GI/G/1/m с конечной очередью и потерями на уровне средних значений и дисперсий распределений временных параметров трафика сети; 3) разработать интерактивную программную систему вероятностного моделирования сетевых моделей для определения их показателей производительности, ориентированную как на разработчиков и проектировщиков вычислительных систем, так и на учебный процесс по таким дисциплинам как: «Компьютерное моделирование», «Сети ЭВМ и телекоммуникации», «Анализ производительности вычислительных систем» и др.
Определение узловых и сетевых характеристик в случае однородного трафика
Интерактивная система вероятностного моделирования компьютерных сетей на основе метода обобщенной двумерной диффузионной аппроксимации позволяет проводить анализ и проектировать компьютерные сети, учитывая ограничения на ресурсы, неоднородность трафика сети и произвольный закон поступления и обслуживания заявок.
Система может использоваться, когда в процессе проектирования сети отсутствует подробная информация о законах распределения вероятностей параметров потоков, а имеются данные лишь о средних значениях и дисперсиях этих распределений. Она решает следующие задачи: - расчет характеристик качества функционирования различных компонент компьютерных сетей, включая оценку вероятностно-временных характеристик узлов коммутации и маршрутизации; - анализ производительности сетей; - анализ буферной памяти узлов; - определение потоков отказов и загрузки линий связи при передаче данных. Входные данные: - матрица вероятностей перехода заявок {Ру}; - Хо\ - интенсивность входного потока в / узел; - C\oi - коэффициент вариации входного потока заявок в і; - Vi - быстродействие /-ого узла; - т; — трудоёмкость обработки заявки /-м узлом; - Сц, - коэффициент вариации времени обработки; - классы узлов; - размер буфера, для узлов с ограниченной емкостью. В случае неоднородного трафика данные задаются для каждого типа трафика. Выходные данные для каждого узла сети: - среднее количество заявок, прошедших за период занятости У; - средняя длина периода простоя /; - среднее время ожидания W ; - средняя длина очереди N ; ч - среднее количество заявок N ; - среднее времени между заявками в выходном потоке т ; - дисперсия этого времени D ; зых - вероятности qu того, что на периоде занятости поступило к заявок; - для узла с ограниченной емкостью: а) интенсивность потока отказов Хотк; б) дисперсия D времени между заявками в потоке отказов. В случае неоднородного трафика характеристики рассчитываются для каждого типа трафика. Выходные данные для сети: - среднее время ожидания заявки в сети WQ\ - среднее время пребывания заявки в сети ; - общая длина всех очередей в сети общее количество заявок в сети. С На рисунке 15 приведена функциональная схема системы, на которой представлены основные функциональные возможности системы и ресурсы, необходимые для их реализации. 1. Расчет характеристик сети с однородным трафиком. Ввод информации возможен из файла данных и с клавиатуры. Вывод информации осуществляется на экран и в файл Rezl.TXT. 2. Расчет характеристик сети с неоднородным трафиком. Ввод информации для каждого класса аналогичен пункту 1. Вывод узловых и сетевых характеристик по классам трафика и характеристик сети возможен как в файл Rez2.TXT , так и на экран. 3. Расчет характеристик узла сети с однородным трафиком с конечной очередью и потерями. Вводится информация о номере узла и размере буфера, вероятности q k = \,kk, индекс кк, AI, Bl, А2, В2. Вывод результатов возможен в файл и на экран. 4. Расчет характеристик сети с однородным трафиком с избыточными и разреженными потоками. Входные данные берутся из оперативной памяти. Результаты расчета записываются в файл или/и отображаются на экране. 5. Расчет характеристик сети с неоднородным трафиком с избыточными и разреженными потоками. Ввод и вывод информации аналогичен пункту 4.
Структура программной системы
Графики, приведенные на рисунках 25-32, позволяют рассчитать необходимые объемы памяти для буферных накопителей при ограничениях на вероятность потери и на время задержки сообщения в узле коммутации. При этом значения объемов, выраженные в единицах от сообщений, можно пересчитать в единицы от бит умножением значений объемов на среднюю длину сообщения.
Из вышеприведенных графиков видно, что при увеличении объема буфера среднее время ожидания W стремится к времени ожидания СМО в случае с бесконечной очередью (пунктирная линия на рисунке 32).
Указанная методика и полученные результаты по расчету объемов требуемой памяти буферных накопителей наряду с методами анализа моделей СМО являются основанием для ОКР при проектировании перспективных высокопроизводительных узлов коммутации. 1. Разработан алгоритм интерактивной программной системы вероятностного моделирования компьютерных сетей на основе обобщенной двумерной диффузионной модели (СМО типа GI/G/1/oo и GI/G/1/m), позволяющий рассчитывать сети с однородным и неоднородным трафиком. 2. Описаны функциональные возможности системы, модули и основные процедуры со спецификациями входных и выходных параметров. 3. Представлена подробная инструкция работы с интерактивной системой. 4. В работе проведены вычислительные эксперименты с целью оценки точности разработанных алгоритмов и программной системы, а также - расчеты по решению задачи выбора необходимых объемов буферных накопителей при заданном качестве обслуживания. Основные выводы и результаты диссертационной работы сводятся к следующему: 1. На основе анализа точности существующих методов, а также возможностей программных систем анализа производительности компьютерных сетей, обоснована необходимость разработки более эффективных методов и программных средств исследования сетей, учитывающих такие их особенности, как широкие диапазоны изменения параметров трафика, наличие ограничений на объемы буферных накопителей, неоднородность потоков и др. 2. Предложена и исследована обобщенная диффузионная модель системы массового обслуживания, учитывающая ограничения на ресурсы системы и позволяющая производить расчеты характеристик таких систем на уровне средних и дисперсий распределений времен поступления и обслуживания. 3. Получены уравнения баланса потоков в сетевых моделях на уровне средних и дисперсий распределений времен между заявками, которые совместно с методом двумерной диффузионной аппроксимации процессов функционирования СМО позволяют декомпозировать сеть на отдельные узлы как в случае однородного, так и неоднородного трафика. 4. Реализована интерактивная система вероятностного моделирования для расчета показателей эффективности функционирования сети для широкого диапазона параметров распределений трафика и времени обслуживания в узлах сети. 5. Предложенная методика расчета характеристик сетевых моделей и программная система моделирования могут быть использованы в проектировании высокопроизводительных узлов коммутации систем передачи данных.
Похожие диссертации на Интерактивная система вероятностного моделирования компьютерных сетей на основе метода двумерной диффузионной аппроксимации
