Методы анализа пропускной способности информационных сетей

Курс для 1 семестра ИМО Методы анализа пропускной способности информационных сетей Из dic.academic.ru: МЕТОД (от греч. methodos - теория, учение) - совокупность приемов или способов познания и освоения действительности, направленных на выполнение определенной цели. АНАЛИЗ (от греч. analysis - разложение) - метод научного исследования (познания) явлений и процессов, в основе которого лежит изучение составных частей, элементов изучаемой системы. Информационная сеть хранения и передачи данных. сеть, предназначенная для обработки, Пропускная способность сети – максимальное количество информации, которая может быть обработана в единицу времени. Курс_Методы анализа пропускной способности информационных сетей Страница 1 ►Пропускная способность сети – это максимально допустимая скорость обработки трафика, которая определяется стандартами сети. Она показывает, какой максимальный объем может быть передан в единицу времени (чаще всего в секунду). Чаще всего она измеряется в бит / сек (в современных сетях - в кило-, мега- или гигабит/с), однако также допустимо характеризовать пропускную способность сети по количеству пакетов, переданных в единицу времени пакетов/с. Эта величина не зависит от загруженности сети, так как отражает именно максимально возможную скорость. Фактически, пропускная способность показывает, с какой скоростью выполняются внутренние сетевые операции, такие, как передача пакетов с данными (в случае видеонаблюдения под данными понимается цифровой поток видео) по сети через все коммуникационные узлы. Пропускная способность зависит от качеств и характеристик физической среды, то есть от наличия, например, медного кабеля или же оптического волокна. Еще один параметр, отвечающий за скорость передачи видео потока по сети, - это технология передачи данных (например, Ethernet). Скорость передачи видео зависит не только от пропускной способности сети, но и от степени ее сжатости, так как при сжатии уменьшается объем передаваемых данных. Курс_Методы анализа пропускной способности информационных сетей Страница 2 ►Большинство технических систем, в том числе вычислительные системы и сети, описываются в терминах дискретных случайных процессов с использованием вероятностных методов. При этом широкое применение находят математические модели, отражающие структурно-функциональную организацию исследуемых систем, построенные на основе моделей теории массового обслуживания, анализ которых может проводиться аналитическими, численными и статистическими методами. В качестве аналитических методов используются вероятностные методы теории массового обслуживания, в качестве численных – методы теории марковских случайных процессов, в качестве статистических – методы имитационного моделирования. Существует значительное количество типов сетей и, соответственно, методов расчета их пропускной способности (как теоретических, так и экспериментальных). ►В рамках данного курса мы сосредоточился на нескольких: - в серии практических работ (ПР) 1 семестра будут изучены аналитические методы расчета (на основе теории массового обслуживания с использованием математического макета MathCad); - в ПР 2 семестра будут изучены имитационные методы расчета (с использованием пакета мат. моделирования); - в итоговом домашнем задании Вы примените эти методы для оценки пропускной способности взаимодействия с сетью своего компьютера. Курс_Методы анализа пропускной способности информационных сетей Страница 3 Оглавление Лекции 1 1. Основные понятия ....................................................................................................................................... 6 1.1. Система массового обслуживания ................................................................................................ 6 1.2. Сеть массового обслуживания........................................................................................................ 9 1.3. Поток заявок ......................................................................................................................................... 10 1.4. Длительность обслуживания заявок ......................................................................................... 13 1.5. Стратегии управления потоками заявок ................................................................................. 14 2. Классификация моделей массового обслуживания .................................................................. 16 2.1. Базовые модели ................................................................................................................................... 16 2.2. Сетевые модели ................................................................................................................................... 20 3. Параметры и характеристики СМО ................................................................................................... 26 3.1. Параметры СМО ................................................................................................................................... 26 3.2. Обозначения СМО (символика Кендалла) .............................................................................. 27 3.3. Режимы функционирования СМО................................................................................................ 30 3.4. Характеристики СМО с однородным потоком заявок ........................................................ 32 4. Параметры и характеристики СеМО ................................................................................................. 36 4.1. Параметры СеМО................................................................................................................................. 36 4.2. Режимы функционирования СеМО ............................................................................................. 37 4.3. Характеристики СеМО ...................................................................................................................... 39 Курс_Методы анализа пропускной способности информационных сетей Страница 4 Лекция 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДИСКРЕТНЫХ СИСТЕМ Изучение процессов, протекающих в дискретных системах со стохастическим (случайным) характером функционирования, проводится в рамках теории массового обслуживания (ТМО) и теории случайных процессов (ТСП). При этом многие модели реальных систем строятся на основе моделей массового обслуживания (ММО), которые делятся на: ► модели в виде систем массового обслуживания (СМО) и ► модели в виде сетей массового обслуживания (СеМО), представляющих собой математические объекты, терминах соответствующего математического аппарата. Курс_Методы анализа пропускной способности информационных сетей описываемые в Страница 5 Рис.1. СМО 1. Основные понятия 1.1. Система массового обслуживания Система массового обслуживания (СМО) – математический (абстрактный) объект, содержащий один или несколько приборов П (каналов), обслуживающих заявки З, поступающие в систему, и накопитель Н, в котором находятся заявки, образующие очередь О и ожидающие обслуживания (рис.1). Заявка (требование, запрос, вызов, клиент) – объект, поступающий в СМО и требующий обслуживания в обслуживающем приборе. Совокупность заявок, распределенных во времени, образуют поток заявок. Обслуживающий прибор или просто прибор (устройство, канал, линия) – элемент СМО, функцией которого является обслуживание заявок. В каждый момент времени в приборе на обслуживании может находиться только одна заявка. Курс_Методы анализа пропускной способности информационных сетей Страница 6 Обслуживание – задержка заявки на некоторое время в обслуживающем приборе. Длительность обслуживания – время задержки (обслуживания) заявки в приборе. Накопитель (буфер) - совокупность мест для ожидания заявок перед обслуживающим прибором. Количество мест для ожидания определяет ёмкость накопителя. Заявка, поступившая на вход СМО, может находиться в двух состояниях: ■ в состоянии обслуживания (в приборе); ■ в состоянии ожидания (в накопителе), если все приборы заняты обслуживанием других заявок. Заявки, находящиеся в накопителе и ожидающие обслуживания, образуют очередь заявок. Количество заявок, ожидающих обслуживания в накопителе, определяет длину очереди. Дисциплина буферизации (ДБ) - правило занесения поступающих заявок в накопитель (буфер). Дисциплина обслуживания (ДО) - правило выбора заявок из очереди для обслуживания в приборе. Приоритет – преимущественное право на занесение (в накопитель) или выбор из очереди (для обслуживания в приборе) заявок одного класса по отношению к заявкам других классов. Курс_Методы анализа пропускной способности информационных сетей Страница 7 Таким образом, СМО включает в себя: ● заявки, проходящие через систему и образующие потоки заявок; ● очереди заявок, образующиеся в накопителях; ● обслуживающие приборы. Существует большое многообразие СМО, различающихся структурной и функциональной организацией. Разработка аналитических методов расчета характеристик функционирования СМО предполагает наличие ряда предположений, ограничивающих множество исследуемых СМО. Далее при рассмотрении СМО, если не оговорено другое, будем использовать следующие предположения: ● заявка, поступившая в систему, мгновенно попадает на обслуживание, если прибор свободен; ● в приборе на обслуживании в каждый момент времени может находиться только одна заявка; ● после завершения обслуживания какой-либо заявки в приборе очередная заявка выбирается на обслуживание из очереди мгновенно, то есть, другими словами, прибор не простаивает, если в очереди есть хотя бы одна заявка; ● поступление заявок в СМО и длительности их обслуживания не зависят от того, сколько заявок уже находится в системе, или от каких-либо других факторов; ● длительность обслуживания заявок не зависит от скорости (интенсивности) поступления заявок в систему. Курс_Методы анализа пропускной способности информационных сетей Страница 8 1.2. Сеть массового обслуживания Сеть массового обслуживания (СеМО) – совокупность взаимосвязанных СМО, в среде которых циркулируют заявки (рис.2,а). Основными элементами СеМО являются узлы (У) и источники заявок (И). Узел сети представляет собой систему массового обслуживания (СМО). Источник (И) – генератор заявок, поступающих в сеть и требующих определенных этапов обслуживания в узлах сети. Для упрощенного изображения СеМО используется граф СеМО. Граф СеМО – ориентированный граф, вершины которого соответствуют узлам СеМО, а дуги отображают переходы заявок между узлами (рис.2,б). Переходы заявок между узлами СеМО, в общем случае, могут быть заданы в виде вероятностей передач. Путь движения заявок в СеМО называется маршрутом. Рис.2. Сеть массового обслуживания Курс_Методы анализа пропускной способности информационных сетей Страница 9 1.3. Поток заявок Совокупность событий распределенных во времени называется потоком. Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок, в общем случае, необходимо задать интервалы времени между соседними моментами и поступления заявок с порядковыми номерами – начальный момент времени). , соответственно Основной характеристикой потока заявок является его интенсивность – среднее число заявок, проходящих через некоторую границу за единицу времени. Величина определяет средний интервал времени между двумя последовательными заявками. ►Поток, в котором интервалы времени между соседними заявками принимают определенные заранее известные значения, называется детерминированным. ►Если при этом интервалы одинаковы ( для всех ), то поток называется регулярным. Для его описания достаточно задать интенсивность потока или значение интервала . ►Поток, в котором интервалы времени между соседними заявками - случайные величины, называется случайным. Для его описания задают законы распределений всех интервалов . Курс_Методы анализа пропускной способности информационных сетей Страница 10 ►Случайный поток, в котором все интервалы между заявками независимы в совокупности и описываются функциями распределений называется потоком с ограниченным последействием. ►Случайный поток, в котором все интервалы одному и тому же закону распределены по , называется рекуррентным. ►Поток заявок называется стационарным, если интенсивность и закон распределения интервалов между последовательными заявками не меняются со временем. В противном случае поток заявок является нестационарным. ►Поток заявок называется ординарным, если в каждый момент времени может появиться только одна заявка. Если в какой-либо момент времени может появиться более одной заявки, то имеем неординарный или групповой поток заявок. ►Поток заявок называется потоком без последействия, если заявки поступают независимо друг от друга, то есть момент поступления очередной заявки не зависит от того, когда и сколько заявок поступило до этого момента. Курс_Методы анализа пропускной способности информационных сетей Страница 11 ►Стационарный ординарный поток без последействия называется простейшим. Интервалы времени между заявками в нем распределены по экспоненциальному закону с функцией распределения (ФР): , где (1) - параметр, представляет интенсивность потока заявок. ►Простейший поток часто называют пуассоновским, поскольку число заявок , поступающих за некоторый заданный промежуток времени распределено по закону Пуассона: , , (2) где - вероятность поступления ровно заявок за некоторый фиксированный интервал времени ; - интенсивность потока заявок. Здесь - дискретная случайная величина, принимающая целочисленные значения: а и - параметры закона Пуассона. Следует отметить, что пуассоновский поток, в отличие от простейшего, может быть: • стационарным, если интенсивность не меняется со временем; • нестационарным, если интенсивность потока зависит от времени. В то же время, простейший поток, по определению, всегда является стационарным. Курс_Методы анализа пропускной способности информационных сетей Страница 12 1.4. Длительность обслуживания заявок Длительность обслуживания - время нахождения заявки в приборе чаще случайно и описывается функцией или плотностью распределения. Для неоднородной нагрузки длительности обслуживания заявок разных классов могут различаться законами распределений или только средними значениями. При этом обычно предполагается независимость длительностей обслуживания заявок каждого класса. ►Предположение, что длительность обслуживания заявок распределена по экспоненциальному закону существенно упрощает выкладки, а процессы, протекающие таких системах являются марковскими. Величина, обратная средней длительности обслуживания характеризует среднее число заявок, которое может быть обслужено за единицу времени, и называется интенсивностью обслуживания: ►Во многих случаях для произвольного закона распределения длительности обслуживания заявок получены аналитические зависимости. При этом для определения средних значений характеристик обслуживания, часто достаточно задать математическое ожидание и дисперсию D=σ2 или коэффициент вариации длительности обслуживания = σ/b. Время , оставшееся до завершения обслуживания заявки, находящейся в приборе, от момента поступления некоторой заявки в систему, и учитывающее, что на момент поступления в системе может и не оказаться заявок, то есть учитывающее простои системы, называется временем дообслуживания. Его матожидание , (4), где – интенсивность простейшего потока заявок, поступающих в систему. Курс_Методы анализа пропускной способности информационных сетей Страница 13 1.5. Стратегии управления потоками заявок Стратегия управления потоками заявок в моделях массового обслуживания задается в виде: ♦ дисциплины буферизации (ДБ) и ♦ дисциплины обслуживания (ДО). ДБ и ДО могут быть классифицированы по следующим признакам: • наличие приоритетов между заявками разных классов; • способ (режим) вытеснения заявок из очереди (для ДБ) и назначения заявок на обслуживание (для ДО); • правило вытеснения или выбора заявок на обслуживание; • возможность изменения приоритетов. Одна из возможных классификаций дисциплин буферизации в соответствии с перечисленными признаками представлена на рис.3. БВЗ – без вытеснения заявок ВЗДК - с вытеснением заявки данного класса ВЗНК - с вытеснением заявки самого низкоприоритетного класса ВЗГК - с вытеснением заявки, принадлежащей группе низкоприоритетных классов ВСЛ – вытеснение случайное ВПЗ – вытеснение последней заявки ВДЗ – вытеснение «долгой» заявки Рис.3. Классификация дисциплин буферизации Курс_Методы анализа пропускной способности информационных сетей Страница 14 Часто ёмкость накопителя в моделях предполагается неограниченной, несмотря на то, что в реальной системе соответствующая ёмкость ограничена. Такое предположение оправдано в тех случаях, когда вероятность потери заявки в реальной системе из-за переполнения ограниченной ёмкости накопителя меньше 10-3, поскольку в этом случае ДБ практически не влияет на характеристики обслуживания заявок. На рис. 4 представлена классификация дисциплин обслуживания заявок в соответствии с теми же признаками, что и для ДБ. Рис.4. Классификация ОПП – обслуживание в порядке поступления ООП – обслуживание в обратном порядке ОСП – обслуживание в случайном порядке ОЦП - обслуживание в циклическом порядке дисциплин обслуживания ОП – с относительными приоритетами АП – с абсолютными приоритетами СП – со смешанными приоритетами ЧП – с чередующимися приоритетами ОР – обслуживание по расписанию Курс_Методы анализа пропускной способности информационных сетей Страница 15 2. Классификация моделей массового обслуживания 2.1. Базовые модели При моделировании реальных систем с дискретным характером функционирования широкое применение находят базовые модели в виде СМО, которые могут быть классифицированы (рис.5): ● по числу мест в накопителе; ● по числу обслуживающих приборов; ● по количеству классов заявок, поступающих в СМО. Накопитель неограниченной ёмкости будем изображать, как на рис.5 а, и накопитель ограниченной ёмкости – как на рис.5 б. Рис.5. Классификация базовых моделей (СМО) Курс_Методы анализа пропускной способности информационных сетей Страница 16 1. По числу мест в накопителе СМО делятся на системы: ● без накопителя, в которых заявка, поступившая в систему и заставшая все обслуживающие приборы занятыми обслуживанием более высокоприоритетных заявок, получает отказ и теряется; такие системы называются СМО с отказами; ● с накопителем ограниченной ёмкости, в которых поступившая заявка теряется, если она застает накопитель заполненным до конца (СМО с потерями); ● системы с накопителем неограниченной ёмкости, в которых для любой поступившей заявки всегда найдется место в накопителе для ожидания (СМО без потерь). Предположение о неограниченной ёмкости накопителя может использоваться для моделирования реальных систем, в которых вероятность потери заявки из-за переполнения накопителя ограниченной ёмкости меньше 10-3. Курс_Методы анализа пропускной способности информационных сетей Страница 17 2. По количеству обслуживающих приборов СМО делятся на: • одноканальные (рис.5,а, б, г), содержащие один прибор П; • многоканальные (рис.5,в), содержащие K обслуживающих приборов П1,...,ПK (K 1). В многоканальных СМО обычно предполагается, что все приборы идентичны и равнодоступны для любой заявки, то есть при наличии нескольких свободных приборов поступившая заявка с равной вероятностью может попасть в любой из них на обслуживание. Рис.5. Классификация базовых моделей (СМО) Курс_Методы анализа пропускной способности информационных сетей Страница 18 3. По количеству классов заявок, поступающих в СМО, различают: • системы с однородным потоком заявок (рис.5,а, б, в); • системы с неоднородным потоком заявок (рис.5,г). Однородный поток заявок образуют заявки одного класса, а неоднородный поток представляет собой поток заявок нескольких классов. В СМО, представляющей собой абстрактную математическую модель, заявки относятся к разным классам в том случае, если они в моделируемой реальной системе различаются хотя бы одним из следующих факторов: ■ длительностью обслуживания; ■ приоритетами. Рис.5. Классификация базовых моделей (СМО) Курс_Методы анализа пропускной способности информационных сетей Страница 19 2.2. Сетевые модели массового обслуживания (СеМО) В зависимости от структуры и свойств исследуемых систем их моделями могут служить СеМО различных классов. Одна из возможных классификаций сетевых моделей приведена на рис. 6. Далее поясним это. Рис.6. Классификация сетевых моделей (СеМО) Курс_Методы анализа пропускной способности информационных сетей Страница 20 1. В зависимости от характера процессов обслуживания заявок в сети СеМО делятся на: ● стохастические, в которых процессы поступления и/или обслуживания заявок носят случайный характер, то есть интервалы времени между поступающими заявками и/или длительности их обслуживания в узлах представляют собой случайные величины, описываемые соответствующими законами распределений; ● детерминированные, в которых интервалы времени между поступающими заявками и длительности их обслуживания в узлах являются детерминированными величинами. 2. По виду зависимостей, связывающих интенсивности потоков заявок в разных узлах, СеМО делятся на: ● линейные, если эти зависимости линейные; ● нелинейные, если эти зависимости являются нелинейными. В линейных СеМО, как это следует из определения, интенсивность потока заявок в узел j связана с интенсивностью потока заявок в узел i линейной зависимостью: где - коэффициент пропорциональности, показывающий, во сколько раз отличаются интенсивности потоков заявок в узел j и в узел Курс_Методы анализа пропускной способности информационных сетей . Страница 21 Поскольку указанная зависимость справедлива для любой пары узлов, это выражение можно записать в несколько ином виде и выразить интенсивность поступления заявок во все узлы через одну и ту же интенсивность, например, через интенсивность потока заявок, поступающих в СеМО из источника заявок: В последнем выражении коэффициент (5) пропорциональности показывает, во сколько раз интенсивность потока заявок в узел отличается от интенсивности источника заявок, и называется коэффициентом передачи (его значение больше нуля). Коэффициент передачи можно трактовать как среднее число попаданий заявки в данный узел за время ее нахождения в сети. Например, если коэффициент передачи узла СеМО равен 3, то это означает, что любая заявка за время нахождения в сети в среднем 3 раза побывает на обслуживании в данном узле. Значение коэффициента передачи, равное 0,25, будет означать, что в среднем только одна заявка из четырёх попадёт на обслуживание в данный узел, а три другие обойдут данный узел стороной. В нелинейных СеМО интенсивности потоков заявок в узлах связаны более сложными нелинейными зависимостями, что значительно усложняет их исследование. Курс_Методы анализа пропускной способности информационных сетей Страница 22 3. По числу циркулирующих в сети заявок различают СеМО: ● разомкнутые; ● замкнутые; ● замкнуто-разомкнутые. ● Разомкнутая (открытая) СеМО (РСеМО) содержит один или несколько внешних независимых источников заявок, которые генерируют заявки в сеть независимо от числа заявок, находящихся в сети (рис.7,а). В РСеМО одновременно может находиться любое число заявок, в том числе, и сколь угодно большое, то есть от 0 до бесконечности. С РСеМО связана внешняя среда, из которой поступают заявки в сеть и в которую они возвращаются после обслуживания в сети. Внешняя среда в РСеМО обозначается как нулевой узел "0", и РСеМО, в этом случае, изображается в виде рис.7,б. ● Замкнутая (закрытая) СеМО (ЗСеМО) не содержит независимых внешних источников заявок и характеризуется тем, что в ней циркулирует постоянное число заявок М (рис.7,в). На графе ЗСеМО из физических соображений, связанных с конкретным представлением процесса функционирования исследуемой реальной системы, обычно выделяется особая дуга, отображающая процесс завершения обслуживания заявок в сети и мгновенного формирования новой заявки с такими же параметрами обслуживания, что и завершившая обслуживание. Курс_Методы анализа пропускной способности информационных сетей Страница 23 Эта трактовка позволяет рассматривать завершившую обслуживание заявку как новую, поступившую в сеть из зависимого источника заявок. По аналогии с РСеМО на выделенной дуге ЗСеМО отмечается условная точка "0", рассматриваемая как нулевой узел и трактуемая иногда как фиктивная СМО с нулевой длительностью обслуживания или как зависимый источник заявок, генерирующий заявки только в момент поступления некоторой заявки на его вход. Рис.7. Виды СеМО Выделение нулевого узла в ЗСеМО преследует двоякую цель: во-первых, достигается однозначность в представлении и математическом описании РСеМО и ЗСеМО; во-вторых, обеспечивается возможность определения временных характеристик ЗСеМО относительно выделенного узла "0". Курс_Методы анализа пропускной способности информационных сетей Страница 24 4. По типу циркулирующих заявок различают СеМО: ● однородные, в которых циркулирует один класс заявок (однородный поток заявок); ● неоднородные, в которых циркулирует несколько классов заявок (неоднородный поток заявок), различающихся хотя бы одним из следующих факторов: ■ длительностями обслуживания в узлах; ■ приоритетами; ■ маршрутами. Маршруты заявок разных классов задаются путем указания номеров классов заявок на соответствующих дугах сети (рис.7,г). Курс_Методы анализа пропускной способности информационных сетей Страница 25 3. Параметры и характеристики СМО 3.1. Параметры СМО Для описания СМО используются три группы параметров: •структурные; •нагрузочные; •функциональные параметры (управления). ►К структурным параметрам относятся: • количество обслуживающих приборов К=1 и К>1 для одно/многоканальной СМО; • количество k и ёмкости накопителей Ej (i=1…k); • способ взаимосвязи накопителей с приборами (матрица связей). ►Нагрузочные параметры СМО включают в себя: • количество поступающих в систему классов заявок Н=1 для однородного и Н>1 для СМО с неоднородным потоком; • закон распределения интервалов времени между поступающими в систему заявками класса или первые два момента распределения (в виде интенсивности и коэффициента вариации интервалов); • закон распределения длительности обслуживания заявок класса или, как минимум, первые два момента распределения, в качестве которых обычно используются средняя длительность или интенсивность обслуживания и коэффициент вариации . Задание двух первых моментов оказывается достаточным характеристик обслуживания заявок на уровне средних значений. для оценки ►Функциональные параметры задаются в виде стратегий управления потоками заявок в СМО, определяющих правила занесения заявок разных классов в накопители ёмкости и выбора их из очереди на обслуживание. Курс_Методы анализа пропускной способности информационных сетей Страница 26 3.2. Обозначения СМО (символика Кендалла) Для компактного описания систем массового обслуживания часто используются обозначения, предложенные Д. Кендаллом, в виде 4-х букв: A/B/N/L , где А и В - задают законы распределений интервалов времени между моментами поступления заявок в систему и длительности обслуживания заявок в приборе; N - число обслуживающих приборов в системе (N 1, 2,...,); L - число мест в накопителе, которое может принимать значения 0,1,2…(при отсутствии - накопитель имеет неограниченную ёмкость). Для задания А и В используются следующие обозначения: G (General) - произвольное распределение общего вида; М(Markovian) - экспоненциальное (марковское) распределение; D (Deterministik) - детерминированное распределение; U (Uniform) - равномерное распределение; Еk (Erlangian) - распределение Эрланга k-го порядка (с k последовательными одинаковыми экспоненциальными фазами); hk (hipoexponential) - гипоэкспоненциальное распределение k-го порядка (с k последовательными разными экспоненциальными фазами); Нr (Hiperexponential) - гиперэкпоненциальное распределение порядка r (с r параллельными экспоненциальными фазами); g (gamma) - гамма-распределение; Р (Pareto) - распределение Парето и т.д. Курс_Методы анализа пропускной способности информационных сетей Страница 27 Примеры (раскрыть): М/М/1 – . M/G/3/10 – . D/Е2/7/0 – Курс_Методы анализа пропускной способности информационных сетей Страница 28 Примеры: М/М/1 - одноканальная СМО с накопителем неограниченной ёмкости, в которую поступает однородный поток заявок с экспоненциальным распределением интервалов времени между последовательными заявками (простейший поток) и экспоненциальной длительностью обслуживания заявок в приборе. M/G/3/10 - трёхканальная СМО с накопителем ограниченной ёмкости, равной 10, в которую поступает однородный поток заявок с экспоненциальным распределением интервалов времени между последовательными заявками (простейший поток) и длительностью обслуживания заявок, распределённой по закону общего вида. D/Е2/7/0 - семиканальная СМО без накопителя (ёмкость накопителя равна 0), в которую поступает однородный поток заявок с детерминированными интервалами времени между последовательными заявками (детерминированный поток) и длительностью обслуживания заявок в приборе, распределённой по закону Эрланга 2-го порядка. Для обозначения более сложных СМО дополнительно могут использоваться обозначения, описывающие неоднородный поток заявок и приоритеты между заявками разных классов. Курс_Методы анализа пропускной способности информационных сетей Страница 29 3.3. Режимы функционирования СМО СМО может работать в следующих режимах: • установившемся или стационарном, когда вероятностные характеристики системы не изменяются со временем; • неустановившемся, когда характеристики системы изменяются со временем, что может быть обусловлено: ■ началом работы системы, когда значения характеристик функционирования, меняясь со временем, стремятся в пределе к стационарным значениям (переходной режим); ■ нестационарным характером потока заявок и обслуживания в приборе (нестационарный режим). Кроме этого, в некоторых системах, например в СМО с накопителем неограниченной ёмкости, неустановившийся режим функционирования может быть обусловлен перегрузкой системы, когда интенсивность поступления заявок превышает интенсивность обслуживания, и система не справляется с возлагаемой на нее нагрузкой (режим перегрузки). При этом характеристики функционирования СМО с течением времени растут неограниченно. В частности, длина очереди перед прибором с течением времени становится всё больше и в пределе стремится к бесконечности. Курс_Методы анализа пропускной способности информационных сетей Страница 30 ►Обычно исследование СМО с накопителем неограниченной ёмкости проводится в предположении о существовании установившегося режима, непременным условием которого является требование отсутствия перегрузок, для чего необходимо, чтобы интенсивность поступления заявок была меньше, чем интенсивность обслуживания. Это требование записывается для одноканальных СМО в виде условия: или . Для многоканальных СМО аналогичное условие имеет вид: или , где K – число обслуживающих приборов, а значение представляет собой суммарную интенсивность обслуживания заявок в K-канальной СМО. ►В СМО с накопителем ограниченной ёмкости превышение интенсивности поступления заявок над суммарной интенсивностью обслуживания не приводит к неограниченному росту длины очереди, что обусловлено . Следовательно, в СМО с накопителем ограниченной ёмкости перегрузки не приводят к работе системы в неустановившемся режиме, а приводят лишь к росту числа потерянных заявок. При этом потеря части поступающих в систему заявок при наличии накопителя ограниченной ёмкости может рассматриваться как один из механизмов борьбы с перегрузками. Курс_Методы анализа пропускной способности информационных сетей Страница 31 3.4. Характеристики СМО с однородным потоком заявок Характеристики систем со стохастическим характером функционирования являются случайными величинами и описываются законами распределений. На практике при моделировании часто ограничиваются определением только средних значений (математических ожиданий), реже – определением двух первых моментов этих характеристик. В качестве основных характеристик СМО с однородным потоком заявок используются следующие величины: ● нагрузка системы: ; (6) ● коэффициент загрузки или просто загрузка системы, определяемая как доля времени, в течение которого система (для одноканальной СМО – прибор) работает, т.е. выполняет обслуживание заявок; загрузка рассчитывается как отношение среднего времени Tр работы одного прибора многоканальной СМО, к общему времени наблюдения T: ; (7) ♦ время Tp для СМО с K обслуживающими приборами определяется путём усреднения времени работы по всем приборам: где Ti - время работы прибора подставляя последнее Очевидно, что 0 1; , ; выражение в (7) Курс_Методы анализа пропускной способности информационных сетей получим: Страница 32 • коэффициент простоя системы: ; • вероятность потери заявок: (8) , (9) где Т- время работы системы (наблюдения за ней); N(T), Nп(T) - число заявок, поступивших в систему, и потерянных заявок за время Т; • вероятность обслуживания заявки, то есть вероятность того, что поступившая в систему заявка будет обслужена: , (10) где N0(T) - число обслуженных в системе заявок за время Т, причем и ; • производительность системы, представляющая собой интенсивность потока обслуженных заявок, выходящих из системы: (11) Для СМО с накопителем неограниченной ёмкости, при условии отсутствия перегрузок, вероятность потери заявок и, следовательно, производительность системы совпадает с интенсивностью поступления заявок в систему: • интенсивность потока потерянных (не обслуженных) заявок из-за ограниченной ёмкости накопителя: (12) Очевидно, что сумма интенсивностей потоков обслуженных и потерянных заявок должна быть равна интенсивности входящего в систему потока заявок: Курс_Методы анализа пропускной способности информационных сетей Страница 33 • среднее время ожидания заявок в очереди: w, • среднее время пребывания заявок в системе, складывающееся из времени ожидания w и времени обслуживания b: u w b (13) ● средняя длина очереди заявок: ; (14) ● среднее число заявок в системе (в очереди и на обслуживании в приборе): (15) Нагрузка и загрузка являются важнейшими характеристиками СМО, определяющими качество функционирования системы. Нагрузка представляет собой интегральную оценку, объединяющую два нагрузочных параметра: ■ частоту использования ресурса (прибора СМО), задаваемую в виде интенсивности  поступления заявок в СМО, и ■ время использования этого ресурса в виде средней длительности b обслуживания заявок в СМО. Нагрузка показывает количество работы, которую необходимо выполнить в системе. Если значение нагрузки y <1, то заданная нагрузка может быть выполнена одним обслуживающим прибором, то есть одноканальная СМО будет работать без перегрузки. Если y >1, то реализация заданной нагрузки в одноканальной СМО приведет к режиму перегрузки, т.е. с течением времени всё большее число заявок будет оставаться не обслуженным, и в случае накопителя неограниченной емкости очередь заявок будет расти неограниченно. Курс_Методы анализа пропускной способности информационных сетей Страница 34 В этом случае для того чтобы система работала без перегрузок необходимо использовать многоканальную СМО, количество приборов которой должно быть больше, чем значение нагрузки: K > y. Для любой СМО (с накопителем ограниченной и неограниченной ёмкости) загрузка системы может быть рассчитана через нагрузку: где K – число обслуживающих приборов в СМО; заявок. Т.о. (16) – вероятность потери , если СМО работает без перегрузки, и , если СМО перегружена. Загрузка системы, в отличие от нагрузки, определяется через интенсивность только обслуженных заявок, поскольку потерянные заявки не обслуживаются в приборах и не загружают систему. Зависимости (14, 15), связывающие значения временных (w, u) и безразмерных (l, m) характеристик, известны как формулы Литтла и вместе с формулой (13) представляют собой фундаментальные зависимости, справедливые для широкого класса моделей массового обслуживания. Из (15) можно получить зависимость, связывающую среднее число заявок в системе со средней длиной очереди заявок: откуда следует, что нагрузка характеризует среднее число заявок, находящихся на обслуживании. Курс_Методы анализа пропускной способности информационных сетей Страница 35 4. Параметры и характеристики СеМО 4.1. Параметры СеМО Для описания линейных разомкнутых и замкнутых однородных экспоненциальных СеМО используется совокупность параметров: ● число узлов в сети: n; ● число обслуживающих приборов в узлах сети: ● матрица вероятностей передач: , где – вероятность передачи заявки из узла i в узел j; ● интенсивность источника заявок, поступающих в разомкнутую СеМО (РСеМО), или число заявок M в замкнутой СеМО (ЗСеМО); ● средние длительности обслуживания заявок в узлах сети: Для линейных СеМО элементы матрицы вероятностей передач должны удовлетворять условию: (24) Это условие отражает тот факт, что любая заявка, покинувшая некоторый узел, обязательно (с вероятностью 1) перейдёт в какой-то узел, включая тот же самый или нулевой. Переход заявки в нулевой узел означает, что заявка покинула сеть. ►В случае неэкспоненциальных разомкнутых СеМО дополнительно необходимо задать законы распределения или вторые моменты интервалов времени между поступающими в разомкнутую сеть заявками и длительностей обслуживания заявок в узлах сети. Курс_Методы анализа пропускной способности информационных сетей Страница 36 4.2. Режимы функционирования СеМО СеМО, как и СМО, может работать в установившемся и неустанновившемся режимах. Последний может быть связан: (переходной режим), ▪с ▪с началом работы системы нестационарным характером потока заявок и обслуживания в приборе (нестационарный режим) и ▪с перегрузкой системы (режим перегрузки). При использовании предположения о стационарности входящего потока заявок и длительностей обслуживания заявок в узлах условие существования установившегося режима совпадает с условием отсутствия перегрузок. Рассмотрим это условие для разомкнутой и замкнутой СеМО. ►Очевидно, что перегрузки в разомкнутой СеМО отсутствуют, если каждый узел сети работает без перегрузок. Если же хотя бы один из узлов сети не справляется с нагрузкой, то длина очереди в этом узле начнет увеличиваться до бесконечности и, следовательно, суммарное число заявок в РСеМО будет расти неограниченно. Таким образом, для того чтобы в разомкнутой СеМО не было перегрузок, необходимо отсутствие перегрузок во всех узлах РСеМО, то есть загрузка любого узла должна быть строго меньше единицы: Курс_Методы анализа пропускной способности информационных сетей Страница 37 Из этого неравенства имеем: Это условие может быть записано также в следующем виде: (25) Полученное условие налагает ограничение сверху на интенсивность поступления заявок в РСеМО из внешнего источника. Узлы, в которых указанное условие не выполняется, являются перегруженными. С течением времени это приводит к неограниченному росту числа заявок в сети, которые скапливаются в перегруженных узлах, имеющих накопители неограниченной ёмкости. ► Для замкнутых СеМО дело обстоит иначе. Т.к. в них циркулирует постоянное число заявок, то в узлах сети не могут образовываться очереди бесконечной длины, поэтому в ЗСеМО всегда существует установившийся режим. Даже если в сети имеется очень «медленный» узел, в котором по сравнению с другими узлами слишком долго обрабатываются заявки, то это может привести только к тому, что все заявки будут постоянно скапливаться в очереди перед данным узлом, однако их количество будет всегда конечно и в пределе равно числу циркулирующих в сети заявок. Загрузка такого «медленного» узла будет близка к 1, т.к. постоянное наличие очереди перед этим узлом обусловливает непрерывную работу приборов узла. Такой узел обычно представляет собой так называемое «узкое место» сети. Курс_Методы анализа пропускной способности информационных сетей Страница 38 4.3. Характеристики СеМО Характеристики СеМО делятся на два класса: ● узловые, описывающие эффективность отдельных узлов СеМО; ● сетевые, описывающие функционирование СеМО в целом. ►Состав узловых характеристик СеМО, работающей в стационарном режиме, такой же, как и для СМО, и для узла включает в себя следующие характеристики: ● нагрузка узла: ● загрузка узла: , причем ● коэффициент простоя узла: ● время ожидания заявок в узле: ● время пребывания заявок в узле: ● длина очереди заявок узле: ● число заявок в узле (в очереди и на обслуживании): В приведенных формулах использован тот факт, что в линейных СеМО интенсивность поступления заявок в любой узел связана с интенсивностью источника соотношением (5). Курс_Методы анализа пропускной способности информационных сетей Страница 39 На основе узловых характеристик рассчитываются сетевые характеристики СеМО: • суммарная нагрузка во всех узлах, характеризующая среднее число заявок, одновременно находящихся на обслуживании во всех узлах сети: где - нагрузка узла j, причем • суммарная загрузка всех узлов СеМО, характеризующая среднее число параллельно работающих узлов сети: где – загрузка узла j, причем • среднее число заявок, находящихся в очередях всех узлов сети и ожидающих обслуживания: (26) где l j – - средняя длина очереди заявок в узле j; • среднее число заявок, находящихся в сети: (27) где mj - среднее число заявок в узле j, причём для замкнутых сетей это выражение может быть использовано для проверки правильности проведенных расчетов, так как для них число заявок М в сети задано; ● среднее время ожидания заявок в сети: (28) где – среднее время ожидания заявок в узле j; – коэффициент передачи для узла j, показывающий среднее число попаданий заявки в узел j за время её нахождения в сети. Курс_Методы анализа пропускной способности информационных сетей Страница 40 – представляет собой суммарное (полное) время ожидание заявки в узле j за время её нахождения в сети; • среднее время пребывания заявок в сети: (29) где Uj - среднее время пребывания заявок в узле j; Uj = α Uj – суммарное (полное) время пребывания заявки в узле j за время её нахождения в сети; • производительность замкнутой СеМО , определяемая как интенсивность потока заявок, проходящих через выделенный нулевой узел замкнутой сети, и представляющая собой среднее число заявок, обслуженных в ЗСеМО за единицу времени; производительность ЗСеМО может быть рассчитана на основе выражения (5), из которого следует: (30) Следует отметить, что для сетевых характеристик СеМО выполняются те же фундаментальные соотношения, что и для СМО, а именно: (31) (32) (33) (34) где – суммарное время обслуживания заявки во всех узлах за время ее нахождения в сети. Выражения (31) и (32) представляют собой формулы Литтла для расчёта сетевых характеристик СеМО. Курс_Методы анализа пропускной способности информационных сетей Страница 41 Из (32) может быть получена ещё одна важная формула для расчёта производительности ЗСеМО: (35) Для неоднородной СеМО перечисленные характеристики определяются как для каждого класса в отдельности, так и для объединенного (суммарного) потока заявок. Курс_Методы анализа пропускной способности информационных сетей Страница 42