Лекции 11-12. Основы метода контуров, обеспечивающего расчет производительности ВС (1153087), страница 2

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

Текст из файла (страница 2)

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

9.2).Рис. 9.2 Модель узла ВСКаждый узел при обработке осуществляет задержку сообщений и поэтомумоделируется одноканальной системой массового обслуживания M/M/1/ (см.рис.9. 3).M / M / 1 / tt0Рис. 9.3 Параметры модели узлаОсновными параметрами сообщений являются :интенсивность поступления сообщений и интенсивность обслуживания  сообщений в узле.Интенсивность поступления  сообщений равна усредненному количествусообщений, поступающих на вход узла в единицу времени.Интенсивность обслуживания  сообщений в узле равна усредненномуколичеству сообщений, обслуженных в единицу времени.Основными характеристиками узлов, как систем массового обслуживанияявляются:время обслуживания t 0 сообщений узлом: t 0 = 1/  (9.11)время задержки t i сообщений в системе i (в узле и очереди наобслуживание) :t i = 1/(  -  ) (9.12)коэффициент загрузки  i узла i :  =  / (9.13)количество сообщений ni в системе обслуживания (в узле и очереди наобслуживание) ni =  /(  -  ) =  i t i (формула Литтла) (9.14)количество сообщений li в очереди на обслуживание:li = 2 /  (  -  ) (9.15)Рассматриваемая модель учитывает стационарный, установившийсяпроцесс передачи и обслуживания заявок.

Если обслуживающая системасодержит несколько узлов с явно выраженными входом и выходом, то такаясистема называется открытой системой, а интенсивность входящих сообщенийравна интенсивности выходящих сообщений. (см. рис.9.4)Количество сообщений в открытой системе определяется по формулеЛиттла (9.16)Рис.9.4 Открытая системаЕсли обслуживающая система содержит несколько узлов, а потоксообщений с выхода последнего узла поступает на вход первого узла , то такаясистема называется замкнутой системой, а интенсивность потока сообщенийявляется неизвестной величиной, зависящей от параметров и структурысоединения узлов. (см.

рис. 9.5 )Рис.9.5 Замкнутая системаДля замкнутой системы применение формул (9.4 – 9.5), выведенных дляодноканальной системой массового обслуживания M/M/1/  , приводит принебольших количествах сообщений (n= 1- 10) к значительным погрешностям.Для уменьшения погрешности при расчете характеристик замкнутых системнеобходимо использовать коэффициент  i ограниченности очереди: = ( − 1)/ , где  i = 0 |=1 ,  i = 1 |=∞ ,тогда соотношения (9.4 – 9.5) преобразуются к следующему виду:- количество сообщений в замкнутой системе обслуживания (в узле и вочереди на обслуживание)ni =  /(  i -   ) =  i t i (формула Литтла)- количество сообщенийli(9.16)в очереди на обслуживание к узлу i в замкнутойсистеме обслуживания:2li =  /(  i-  )(9.17)В вычислительных сетях можно выделить потоки сообщений, каждый изкоторых в установившемся режиме имеет свой путь прохождения через узлысети и свои параметры обслуживания в узлах.Такой условно выделенный путь движения сообщений назван контуром q ,q  1, Q , Контуры могут быть разомкнутыми (см.рис.

9.4 и 9.7) игдезамкнутыми (см. рис.9.5, 9.6)(A)k1k2k3(B)Рис. 9.6Двухфазный замкнутый контурt21t1111k2k1qq22Рис. 9.7Узлы обслуживают несколько контуровРазомкнутый контур - это путь потока идентичных сообщений от входа всеть через промежуточные узлы к выходу из сети.Замкнутый контур - это путь потока идентичных сообщений от узлаисточника до обслуживающего узла и обратно.Фаза контура -это часть контура, в которой каждый узел только один разобслуживает сообщение.Пример 9.1 (рис.

9.6)(A)k1k2k3(B)k2(A).:замкнутыйконтурсодержитузлы:Пример 9.2 (рис 9.6): Фаза  =1 содержит узлы: (A)k1k2k3(B).Фаза = 2 содержит узлы: (B)k2(A).В реальных сетях в стационарном режиме сообщения с выхода одного узламогут поступать на входы различных узлов. При моделировании такиепереходы от узла i к узлу j оцениваются вероятностью pi , j переходасообщений (см.

рис 9.8).P120K1P13121324K2P3445K434K535K3P35Рис.9.8 Контур с вероятностями переходаВероятности pi , j перехода позволяют для разомкнутых контуров выразитьинтенсивность  ij потока сообщенийинтенсивность o потокаинтенсивности.Базовуюсообщенийинтенсивностьлюбого перехода через базовуюикоэффициентai, jбазовой o потока сообщений обычнопредставляет поток сообщений, поступающий на вход узла. Коэффициент a i , jбазисной интенсивности, показывает, какая часть базисной интенсивностипереходит от узла i к узлу j.i, j =  0 a i , j (9.18)Пример 9.3 (рис. 9.8)a12 = p12 : a13 = p13 : a24 = p12 p24 = p12 : a34 = p13 p34: a35 = p13 p35:a45 = (a24 + a34)p45 = a24 + a34.Линейные уравнения.Линейные уравнения являются одной из составных частей аналитическоймодели метода контуров.

Составление и последующее их совместное решениепозволяет для потоков каждого контура q определить коэффициенты a ijбазовой интенсивности.В основу составления линейного уравнения положено условие, что дляустановившегося процесса движения сообщений одного контура q количествовходящих в узел i сообщений равно количеству сообщений его покидающих ипоступающих на вход следующего узла j (см. рис.

9.9).Контурk=1,nqkiqKipijq,ijqк узлу jРис.9.9 Схема к системе линейных уравненийТогда для каждого контура q, каждого узла i  q и для каждой дуги ijможно записать:i , j , q = pi , j , qNk 1(9.19)k ,i , qПример 9.4. (см. рис. 9.8)Система линейных уравнений имеет вид:12 = p12  0 ;35 = p35 13 ;13= 24 = p 24 12 ;p13  0 ; 45 = p45 ( 2434 = p34 13 ;34 ).+В результате решения системы линейных уравнений - получаем:a12=p12 ;a13=p13 ;a 24= p12p24 ;a 34=p13 p34 ;a 35=p13=p35 ;a 45=p12+p13 p34Нелинейное уравнениеНелинейные уравнения также являются частью аналитической моделиметода контуров.

Каждое нелинейное уравнение составляется для одногоконтура. Составление и последующее их совместное решение позволяет дляпотоков всех контуров сети определить базовые интенсивности.  0 q .Основу составления каждого нелинейного уравнения составляет условие,что для установившегося процесса движения сообщений одного контура qколичество сообщений в контуре не изменяется и равно сумме математическихожиданий сообщений рассматриваемого контура во всех узлах сети. Тогда длякаждого контура можно записать:nq =niq , где k i  q(9.20)kiПример 9.5 (см.рис.9.10.)Рассматриваемая система содержит два терминала (k1 k2 ), коммутатор (k3 )и сервер (k4 ), обслуживающих два замкнутых контура.1K1K3K4K22Рис.

9.10Система с двумя двухфазными контурамиКонтур q = 1 содержит в своем составе узлы: k1k3k4k3(k1 ; перваяфаза  = 1 содержит узлы k1—k3—k4..; вторая фаза  = 2 содержит узел k3Контур q= 2 содержит в своем составе узлы: : k2k3k4k3(k2 ; первая фаза = 1 содержит узлы k2—k3—k4..; вторая фаза  = 2 содержит узел k3.Система нелинейных уравнений, составленная для системы, котораяпредставлена на рис. 9.10, на основании (9.16) и (9.20) может быть записана вследующем виде:2n               2 2 1111111n   222где2323132414222  2        23(9.21)2124412  nq   1q  nqqОпределение функциональных характеристик.Каждый узелобслуживанияiвычислительной сети характеризуется временемсообщений,котороезависитотобъема z iзаданийti0ипроизводительности wi узла:ti0 = z i / wi(9.22)Если узел моделирует компьютер, то объем z i заданий измеряется воперациях, а производительность wi узла измеряется в операциях в секунду.Если узел моделирует аппаратуру связи, то объем z i заданий измеряется вбитах, а производительность wi узла измеряется в битах в секунду.После того, как определены интенсивности потоков сообщений каждогоконтура q в каждом узле i вычислительной сети можно определить основныехарактеристики вычислительной сети.ssСреднее время t q доставки сообщений контура q в разомкнутой сети: t q =ti ,q, где i  q(9.23)iСреднее время отклика t id,q сообщений замкнутого контура q, содержащегоn q сообщений, каждое из которых генерируется узлом i :t id,q = ( n q / i,q ) - ( 1/  i,q )Коэффициент  i загрузки узлаi =i, q(9.24)i:(9.25)qСтадии метода контуров.Изложенные основные определения позволяют сформулировать следующиеэтапы метода контуров:- Описание структуры вычислительной сети,- Описание функциональной схемы вычислительной сети,- Представление графовой модели вычислительной сети,- Составление линейных уравнений баланса,- Составление нелинейных уравнений баланса,- Решение линейных уравнений баланса,- Решение нелинейных уравнений баланса,- Определение функциональных характеристик вычислительных сетей.Структуравычислительнойсетиопределяеттакиеосновныехарактеристики, как количество N узлов сети и наличие связей между узлами,задаваемых матрицей связей S  ‖ ‖, как показано на рис.9.1.Переход к функциональной схеме вычислительной сети отражаеттребования проектировщика-исследователя к степени детализации построениямодели, т.е.

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

Приналичииузлов, имеющих идентичные интенсивностиiобслуживания,вводятся типы m узлов обслуживания.Составление линейных уравнений баланса выполняется в соответствиипояснениями, изложенными в разделе 9.2. и записывается в виде соотношения(9.19).Нелинейные уравнения баланса составляются в соответствии пояснениями,изложенными в разделе 9.2, и записываются в виде соотношения (9.20).Решение системы линейных уравнений баланса направлено на определениекоэффициентов a i , j базисной интенсивности для чего, в зависимости отразмерности сети могут использоваться(подстановки или итеративные методы ).различныеметодырешенияРешение системы нелинейных уравнений баланса ставит своей цельювычисление базисных интенсивностей для замкнутых контуров.

Для систем небольшой размерности целесообразно использовать метод дихотомии или методтангенсов, изложенные в разделе 10. Выбор метода решения для сетей большойразмерности требует дополнительного анализа специфических особенностейкаждой исследуемой сети.Самоконтроль знанийКонтрольные вопросы1. Какие условия являются главными для рассмотрения компоненты сети вкачестве узла?2. Какие характеристики трафика являются известными (заданными) длязамкнутых и разомкнутых контуров?3. Почему для замкнутых систем обслуживания с узлами M/M/1 и M/G/1необходимо вводить коэффициент ограниченности очереди? В каком диапазонеон изменяется?4. Сколько фаз может иметь контур?5. Почему уравнения (9.19) называют линейным, а уравнение (9.20)(9.21) нелинейным?Контрольные задания1. Разомкнутая система обслуживания А имеет интенсивность входного потока и время обслуживания t 0A Разомкнутая система обслуживания В состоит издвух последовательно-соединенных узлов и имеет время обслуживания вкаждом узле t0B = t0A /2.

Для одинаковой интенсивности входного потока определить, какая система имеет большее время обслуживания? Может ли t Aбыть равным t B ?2. Разомкнутая система обслуживания C состоит из двух параллельносоединенных узлов, входной поток сообщений с равными вероятностямипоступает на входы каждого узла, который имеет время обслуживания t0C = t0A .Определить время обслуживания t C и сравнить с t A и t B (см.

предыдущее задание1).3. Определить время пребывания сообщений в системе (см.рис. 9.4.), если =1(1/с), а коэффициенты загрузки 1 = 2 = 3 =0,8.4. Определить время пребывания сообщений в системе (см.рис. 9.7.), если 1=1(1/с), 2 =2(1/с), 3 =3(1/с), 1 =7(1/с), 2 =8(1/с). Определить коэффициентызагрузки 1 и 2 . Какое получится решение при 1 =6(1/с), и почему?5.

Определить интенсивность потоков для системы, представленной на рис.9.10, если она обслуживает:а) только контур q1,б) только контур q2.Сравните результаты этой задачи с предыдущими заданиями 5 и 6..

Характеристики

Список файлов лекций