Основы метода контуров, обеспечивающего расчет производительности ВС

ЛЕКЦИИ 11-12 ОСНОВЫ МЕТОДА КОНТУРОВ, ОБЕСПЕЧИВАЮЩЕГО РАСЧЕТ ПРОИЗВОДИТЕЛЬНОСТИ ВС Оценка производительности вычислительных сетей (ВС) чрезвычайно актуальна. Производительность ВС необходимо оценивать: - при разработке аппаратных средств, являющихся компонентами ВС, (серверов, коммуникационных узлов, каналов связи), - при разработке сетевого и прикладного программного обеспечения, - при проектировании вычислительных сетей, - для обеспечения эффективной эксплуатации ВС, - для обеспечения качественного обслуживания сетевых абонентовпользователей, - для модернизации и развития ВС. Любое расширение, добавления состава услуг (защита информации, мультимедийные технологии и т.д) увеличивают загрузку сетевых средств и влияют на производительность ВС. Указанные обстоятельства требуют: - переходить от качественных оценок производительности к количественным; - разрабатывать методы, которые обеспечивают применение теоретических моделей для решения задач практики. - разрабатывать методы, которые позволят производить целенаправленное экспериментальное определения табличных (справочных, нормативных) сетевых параметров и характеристик. Методологические трудности определения сетевых характеристик состоят в том, что: - с одной стороны, каждая вычислительная сеть организации, корпорации, предприятия обладает своими особенностями, - с другой стороны, пока ВС не введена в эксплуатацию очень трудно определить количественно ее параметры, которые тесно связаны с составом сетевого сервиса, с составом и объемом информационных баз данных, интенсивностью трафика обмена данными. Вычислительные ресурсы для решения задачи обычно предоставляются локально, а сетевые ресурсы распределены по обслуживаемой территории, используются избирательно и поэтому нельзя измерить количественно и обосновать все требуемые сетевые характеристики. Указанные трудности приводят к тому, что вновь созданную ВС приходится сразу же модернизировать. При этом, обнаруженные недостатки видны и понятны, а вот путей и способов их устранения может быть множество, но без гарантии обеспечения успеха. 1 Основные определения. Понятие производительность вычислительных сетей. Сетевые технологии постоянно совершенствуются, что приводит к росту количества пользователей, увеличению объема трафика, необходимости повышения ответственности за доставку каждого сообщения. Мультимедийные технологии предоставляют пользователям широкий спектр информационных уcлуг, но предъявляют повышенные требования к технико-экономическим показателям, которые ужесточаются с ростом сложности вычислительных сетей (ВС) и увеличением количества пользователей Целью создания теории производительности вычислительных сетей (ТП ВС) является разработка теоретических основ для расчета вероятностновременных характеристик функционирования отдельных узлов, фрагментов и вычислительных сетей в целом, которые позволяют учитывать технические характеристики аппаратных средств, влияние используемых стеков протоколов, сегментацию сообщений и работу пользователей в диалоговом режиме. Вычислительная сеть (ВС) - это техническая система, содержащая компьютеры, соединенные устройствами коммуникации и каналами связи, которая обеспечивает дистанционное выполнение информационновычислительных работ пользователей. ВС – это сложная система, поэтому эффективность функционирования каждой из них невозможно оценить одной величиной, и необходимо использовать набор характеристик. К основным характеристикам эффективности функционирования ВС следует отнести: производительность, надежность, конфиденциальность обслуживания и стоимость. Производительность ВС как системы, обслуживающей пользователей, должна оцениваться общим количеством информационно-вычислительных работ, которые выполняют все устройства, входящие в состав ВС. Информационно-вычислительные работы, выполняемые ВС, отличаются большим разнообразием, которое определяется количеством пользователей, их требованиями и возможностями устройств, составляющих ВС Производительность устройств, выполняющие обработку в ВС, определяется техническими и программными средствами процессоров, коммуникационных устройств и каналов связи. К параметрам, характеризующим производительность технических средств ВС, обычно относят: тактовую частоту процессора, время выполнения операции сложения, время выполнения регистровой операции, время обработки эталонных запросов. К параметрам, характеризующим производительность программных средств, обычно относят: количество операций, скорость выполнения программы, частоту использования программы. К параметрам, характеризующим производительность каналов связи, относят скорость передачи данных. Основная проблема оценки производительности ВС состоит в необходимости выявления и формирования основных параметров, которые влияют на производительность ВС и имеют количественную оценку, а также вывод расчетных соотношений, позволяющих рассчитывать требуемые показатели производительности ВС. Следовательно, для определения производительности ВС необходимо создание модели, содержащей набор параметров, отражающих особенности функционирования ВС с точки зрения ее производительности. Для описания производительности ВС необходимо определить единицу обработки. В процессе дистанционного обслуживания на абонентском компьютере формируется заявка с запросом на обработку, который по каналам связи передается как сообщение. Обработка заявки в каждом компьютере производится в соответствии с программой обслуживания, заданной абонентом (например, видом обработки, оговоренным в списке меню). В соответствии с типом программы для обработки заявки компьютер выполняет определенное количество вычислительных операций. Обработка сообщения в устройствах коммутации и в каналах связи в первую очередь зависит от объема сообщения, измеряемого, например, в битах. Вычислительные сети выполняют функции передачи и обработки данных и осуществляют преобразование заявки в сообщение и наоборот. Для обозначения функционально связанных заявок и сообщений будем использовать термин транзакция, который соответствует перемещающемуся объекту и должен определяться двумя параметрами: объемом данных и количеством вычислительных операций, необходимыми для обработки. Следовательно, в качестве обслуживаемых единиц работы, определяющих производительность ВС, будем рассматривать транзакции различных типов. Для обработки транзакции в канале связи и в коммутирующем устройстве требуется выделение ресурса пропускной способности на время, необходимое для передачи содержащегося в транзакции объема данных. Для обработки транзакции в компьютере требуется выделение вычислительного ресурса на время выполнения необходимого количества вычислительных операций. Таким образом, обработку транзакции любой формы (в форме заявки или сообщения) можно характеризовать инвариантной характеристикой - временем нахождения транзакции в обслуживающем узле. Производительность ВС с точки зрения пользователя должна характеризовать скорость обработки транзакции рассматриваемого типа. С точки зрения администратора сети производительность ВС должна отражать способность всех ресурсов ВС обрабатывать транзакции с оговоренной (допустимой) скоростью обслуживания. В качестве единицы измерения производительности может использоваться как время, в течение которого обрабатывается транзакция, так и интенсивность, оценивающая количество транзакций, обработанных в единицу времени. Однако, следует отметить, что наличие в ВС транзакций различных типов может приводить к неоднозначности этих оценок. Поэтому для рассматриваемой ВС, должны быть известны: состав, связи и характеристики обслуживающих узлов, а также зафиксировано, какие абоненты инициируют транзакции, какого типа и по каким маршрутам движутся транзакции. Наличие разных потребностей и применение различной степени декомпозиции при описании процессов обработки транзакций в ВС приводит к необходимости использования нескольких оценок производительности ВС, образующих систему понятий производительности ВС, к которым в первую очередь можно отнести: - производительность элементов ВС, - производительность ВС, - характеристиками транзакций ВС, - комплексную производительность ВС, - рабочую производительность ВС, - пиковую производительность ВС, - предельную производительность ВС для рассматриваемого типа транзакций при пиковой нагрузке. Производительность элементов ВС оценивается: - множеством интервалов времени, которые затрачивает каждый элемент каждого обслуживающего узла при обработке транзакции соответствующего типа, - множеством интенсивностей обработки каждым элементом каждого обслуживающего узла транзакции соответствующего типа. Производительность узлов ВС оценивается: - множеством интервалов времени, которые затрачивает каждый обслуживающий узел при обработке транзакции соответствующего типа, - множеством интенсивностей обработки каждым обслуживающим узлом транзакции соответствующего типа. Транзакции ВС характеризуются, - типом каждого потока транзакций - интенсивностью каждого потока транзакций - маршрутом каждого потока транзакций Комплексная производительность ВС оценивается: - множеством интервалов времени, которые затрачивает при обработке транзакции каждого рассматриваемого типа соответствующий набор обслуживающих узлов, множеством интенсивностей обработки транзакций каждого рассматриваемого типа соответствующим набором обслуживающих узлов. Комплексная производительность фактически характеризует способность ВС обслуживать транзакции одного типа при полном отсутствии внешнего трафика. Рабочая производительность ВС оценивается: - множеством интервалов времени, которые затрачивает при обработке транзакции каждого рассматриваемого типа соответствующий набор обслуживающих узлов при известном соотношении типов транзакций, составляющих рабочий трафик, множеством интенсивностей обработки транзакций каждого рассматриваемого типа соответствующим набором обслуживающих узлов при известном соотношении типов транзакций, составляющих рабочий трафик. Пиковая производительность ВС оценивается: - множеством интервалов времени, которые затрачивает при обработке транзакций каждого рассматриваемого типа транзакции соответствующий набор обслуживающих узлов при известном соотношении типов транзакций, составляющих пиковый трафик нагрузки, множеством интенсивностей обработки транзакций каждого рассматриваемого типа соответствующим набором обслуживающих узлов при известном соотношении типов транзакций составляющих пиковый трафик нагрузки. Предельная производительность рассматриваемого типа транзакций при пиковой нагрузке оценивается: - множеством интервалов времени, которые затрачивает при обработке транзакций каждого рассматриваемого типа соответствующий набор обслуживающих узлов при известном соотношении типов транзакций, составляющих пиковый трафик нагрузки, и предельной нагрузке в одном из обслуживающих узлов ВС. множеством интенсивностей обработки транзакций каждого рассматриваемого типа соответствующим набором обслуживающих узлов при известном соотношении типов транзакций, составляющих пиковый трафик нагрузки, и предельной нагрузке в одном из обслуживающих узлов ВС. 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 в замкнутой системе обслуживания: 2 li =  /(  i -  ) (9.17) В вычислительных сетях можно выделить потоки сообщений, каждый из которых в установившемся режиме имеет свой путь прохождения через узлы сети и свои параметры обслуживания в узлах. Такой условно выделенный путь движения сообщений назван контуром q , q  1, Q , Контуры могут быть разомкнутыми (см.рис. 9.4 и 9.7) и где замкнутыми (см. рис.9.5, 9.6) (A) k1 k2 k3 (B) Рис. 9.6 Двухфазный замкнутый контур t21 t11 1 1 k2 k1 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 0 K1 P13 12 13 24 K2 P34 45 K4 34 K5 35 K3 P35 Рис. 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,n q kiq Ki pijq,ijq к узлу j Рис. 9.9 Схема к системе линейных уравнений Тогда для каждого контура q, каждого узла i  q и для каждой дуги ij можно записать: i , j , q = pi , j , q N  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 = p12 p24 ; 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 ), обслуживающих два замкнутых контура. 1 K1 K3 K4 K2 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   1 1 1 1 1 1 1 n      2 2 2 где 2 3 2  3 1 3  2 4 1 4 2 2   2  2         2 3 (9.21) 2 1 2 4 4 1 2     nq   1   q     n q q Определение функциональных характеристик. Каждый узел обслуживания i вычислительной сети характеризуется временем сообщений, которое зависит от объема z i заданий ti0 и производительности wi узла: ti0 = z i / wi (9.22) Если узел моделирует компьютер, то объем z i заданий измеряется в операциях, а производительность wi узла измеряется в операциях в секунду. Если узел моделирует аппаратуру связи, то объем z i заданий измеряется в битах, а производительность wi узла измеряется в битах в секунду. После того, как определены интенсивности 𝜆𝑖𝑞 потоков сообщений каждого контура q в каждом узле i вычислительной сети можно определить основные характеристики вычислительной сети. s s Среднее время t q доставки сообщений контура q в разомкнутой сети: t q = t i ,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.