Расчет и анализ производительности WAN

ЛЕКЦИИ 15-16 РАСЧЕТ И АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ WAN 12.1. Постановка задачи. В процессе проектирования распределенной вычислительной сети WAN (Wide Area Network) разработчики задают различные структуры вычислительных сетей, а также возможные направления информационных потоков и для этих вариантов определяют временные характеристики для оценки каждого варианта функционирования WAN. Решаемая в настоящем разделе задача формулируется следующим образом. Для исследуемой WAN заданы: ̅̅̅̅̅̅ - типы 𝑚 устройств, где 𝑚 = 1, 𝑀, - количество 𝑁𝑚 устройств разных типов, - структура 𝑆 связей между устройствами, - интенсивности 𝜇𝑚 обслуживания, - контура 𝑞 потоков заявок, где 𝑞 = ̅̅̅̅̅ 1, 𝑄, - количество 𝑛𝑞 заявок в каждом замкнутом контуре 𝑞, - вероятности 𝑝𝑖,𝑗,𝑞 перехода заявок контура 𝑞 из обслуживающего узла 𝑖 в узел 𝑗. Необходимо рассчитать такие характеристики WAN, как средние времена 𝑑 откликов 𝑡𝑖,𝑞 сообщений каждого замкнутого контура 𝑞 и коэффициенты 𝜌𝑖 загрузки для каждого узла 𝑖. В последующих разделах для математической формулировки поставленной задачи и ее решения используется метод контуров, все шаги которого иллюстрируются единым учебным примером расчета характеристик для простейшей WAN. Математическая формулировка задачи предусматривает выявление всех узлов сети, обслуживающих сообщения, введение всех символьных обозначений для обслуживающих узлов, их характеристик и параметров WAN, и последующую запись всех необходимых линейных и нелинейных уравнений. Для выполнения этих преобразований применяют первые пять этапов метода контуров Описание структуры WAN иллюстрируется примером 12.1, представленным на рис. 12.1. Пример 12.1. Структура WAN содержит: Host (1H, 2H), которые в режиме удаленного доступа через каналы (1K - 12K) связи, коммуникационные контроллеры (1C 5C) обслуживают в диалоговом режиме рабочие станции (1S - 60S), которые объединены в три группы (1GS - 3GS). 1H 1C ХОСТ (H) 2C 3C КАНАЛ (K) 1GS ГРУППА СТАНЦИЙ(GS) 4C 5C КОНТРОЛЛЕР(C) 2H 2GS 3GS Рис. 12.1. Структура исследуемой WAN При составлении функциональной структуры проектировщик выделяет те обслуживающие устройства, которые имеют существенное влияние на временные оценки функционирования WAN. Определяются типы 𝑚 обслуживающих узлов. В функциональной структуре, которая представлена на рис.12.2, выделены три типа обслуживающих узлов H, K, S и задается количество узлов Nm каждого типа. Пример 12.2. В рассматриваемой WAN задаем интенсивности 𝜇𝑚 обслуживания, где 𝑚 = 1 для (H), 𝑚 = 2 для (K), 𝑚 = 3 для (S). Принимаем, что задержки на обслуживание в контроллерах (C) учитываются параметрами соответствующих каналов K, поэтому на рис. 12.2 представлены только точки коммутации сообщений (1C - 5C). В рассматриваемом примере количество обслуживающих узлов различных типов m соответственно равны: 𝑁1 = 2, 𝑁1 = 12, 𝑁3 = 60. При составлении графовой модели сначала вводится единая нумерация всех ̅̅̅̅̅ обслуживающих узлов. Каждый узел обозначается стрелкой 𝑘𝑖 , где 𝑖 = 1, 𝑁 и 𝑁 = ∑𝑚 𝑁𝑚 . Затем описывают состав узлов в каждом контуре 𝑞 и значения вероятностей 𝑝𝑖,𝑗,𝑞 перехода сообщений каждого контура 𝑞 от узла 𝑖 к узлу 𝑗. Введенная нумерация позволяет ввести символьные обозначения и записать все исходные данные для расчета характеристик. Графовая модель примера 12.2. приведена на рис. 12.3 Пример 12.3. Графовая модель рассматриваемой WAN содержит узлы 𝑘1 , 𝑘2 , которые моделируют хосты (H) и обслуживают сообщения с интенсивностью 𝜇1 = 10 • 1⁄𝑠. Узлы 𝑘3 - 𝑘4 моделируют каналы (𝐾) и обслуживают сообщения с интенсивностью 𝜇2 = 6 • 1⁄𝑠. Узлы 𝑘15 , - 𝑘64 , моделируют станции (S) и обслуживают сообщения с интенсивностью 𝜇3 = 0,333 • 1⁄𝑠. В рассматриваемом варианте узлы обслуживают три замкнутых контура ̅̅̅̅). Сообщения 𝑞 = 1 обслуживаются узлами 𝑘1 , 𝑘3 , 𝑘8, , (𝑘45 - 𝑘64 ), 𝑘9 , 𝑘4 , (𝑞 = 1,3 что соответствует предоставлению ресурсов хост (1H) для станций (31S - 50S) . Сообщения 𝑞 = 2 обслуживаются узлами 𝑘2 , 𝑘13 , 𝑘11 , (𝑘15 - 𝑘44 ), ((𝑘12 ), (𝑘10 , 𝑘14 )),что соответствует предоставлению ресурсов хост (2H) для станций (1S 30S). 1H 1C 4K 1S 3K 30S 3C 2K 1K 5K 10K 9K 8K 51S 2C 60S 5C 6K 7K 12K 11K 4C 2H 31S 50S Рис. 12.2 Функциональная модель WAN Сообщения 𝑞 = 3 обслуживаются узлами 𝑘1 , 𝑘5 , 𝑘10, , (𝑘55 , - 𝑘64 ), ((𝑘7 ), (𝑘11 , 𝑘6 )),что соответствует предоставлению ресурсов хост (1H) для станций (51S - 60S) . В связи с тем, что не используются полудуплексные каналы связи, при описании контуров достаточно одной фазы. Для точного описания контуров необходимо задавать для каждого контура 𝑞 вероятности 𝑝𝑖,𝑗,𝑞 , перехода сообщений из 𝑘𝑖 в 𝑘𝑗 : - для 𝑞 = 1 заданы следующие значения: 𝑝1,3,1 = 𝑝3,8,1 = 𝑝45,9,1 = . . = 𝑝64,9,1 = 𝑝9,4,1 = 𝑝4,1,1 = 1,0; 𝑝8,45,1 = . . . = 𝑝8,64,1 = 0,05. Рис. 12. 3 Графовая модель WAN - для 𝑞 = 2 заданы следующие значения: 𝑝2,13,2 = 𝑝13,11,2 = 𝑝10,14,2 = 𝑝14,2,2 = 𝑝12,2,2 = 1,0; 0,033; 𝑝15,10,2 = . . . = 𝑝44,10,2 = 0,5. - для 𝑝11,15,2 = . . . = 𝑝11,44,2 = 𝑞 = 3 заданы следующие значения: 𝑝1,5,3 = 𝑝5,10,3 = 𝑝11,6,3 = 𝑝6,1,3 = 𝑝7,1,3 = 1,0; 𝑝10,65,3 = . . . == 𝑝10,74,3 = 0,1; 𝑝65,11,3 = . . . = 𝑝74,11,3 = 0,1; 𝑝65,7,3 = . . . = 𝑝74,7,3 = 0,5. Составление линейных уравнений баланса выполняется для интенсивности 𝜆𝑖,𝑞 потока сообщений контура q для каждого узла 𝑖 с использованием соотношений раздела 9. Для замкнутых контуров WAN в качестве базисной интенсивности 𝜆0,𝑞 принимается интенсивность 𝜆𝑖,𝑞 в хостмашине для соответствующего контура. 𝜆0,𝑞 = 𝜆𝑖,𝑞 , 𝑖 ∈ 𝐻𝑞 Пример 12.4. Запишем рассматриваемой WAN. (12.1) линейные уравнения для контура 𝑞=2 𝜆0,2 = 𝜆2,2 ; 𝜆13,2 = 𝑝2,13,2 𝜆2,2 ; 𝜆11,2 = 𝑝13,11,2 𝜆13,2 ; 𝜆15,2 = 𝑝11,15,2 𝜆11,2 ; 𝜆44,2 = 𝑝11,44,2 𝜆11,2 ; 𝜆10,2 = 𝑝15,10,2 𝜆15,2 + 𝑝16,10,2 𝜆16,2 + … + 𝑝44,10,2 𝜆44,2 ; 𝜆12,2 = 𝑝15,12,2 𝜆15,2 + 𝑝16,12,2 𝜆16,2 + … + 𝑝44,12,2 𝜆44,2 ; 𝜆14,2 = 𝑝10,14,2 𝜆10,2 ; (12.2) Для каждого контура 𝑞 составляется нелинейное уравнение баланса. Пример 12.5. Для контура 𝑞 = 2 рассматриваемой WAN нелинейное уравнение баланса имеет следующий вид. 𝑛2 = + 𝜆2,2 𝜆10,2 𝜆11,2 + + + 𝜇2 − 𝛾12 𝜇10 − 𝛾10 (𝜆10,2 + 𝜆10,3 ) 𝜇11 − 𝛾11 (𝜆11,2 + 𝜆11,3 ) 𝜆12,2 𝜆13,2 𝜆14,2 𝑛2 𝜆15,2 + + + (12.3) 𝜇12 − 𝛾12 𝜆12,2 𝜇13 − 𝛾13 𝜆13,2 𝜇14 − 𝛾14 𝜆14,2 𝜇15 − 𝛾15 𝜆15,2 Каждое слагаемое соответствует одному из узлов, входящих в рассматриваемый контур. Коэффициент 𝛾𝑖 ограниченности очереди вычисляется по соотношению (9.4). Последнее слагаемое в (12.3) учитывает функционирование узлов 𝑘15 - 𝑘44 , которые соответствуют станциям 𝑆 первой группы 1GS и обладают идентичными характеристиками обслуживания сообщений. Таким образом, соотношения вида (12.2) и (12.3) составляют основу математической модели функционирования WAN. 12.2. Расчет производительности WAN. Записанная математическая модель функционирования WAN обеспечивает переход к вычислению функциональных характеристик. Алгоритм вычисления состоит из следующих шагов. 1. Задаются численные значения для исходных данных, к которым относятся 𝑀, 𝑁𝑚 , 𝜇𝑚 , 𝑄, 𝑛𝑞 , 𝑝𝑖,𝑗,𝑞 . 2. Для каждого контура 𝑞 решаем систему линейных уравнений вида (12.2). В связи с тем, что контура в WAN обычно имеют несложную форму, целесообразно при вычислении значений 𝑎𝑖,𝑗 присваивать 𝜆0,𝑞 = 0 и использовать метод подстановки. 3. Для каждого узла 𝑘𝑖 по соотношению (9.4) вычисляются значения 𝛾𝑖 Следует подчеркнуть, что если станция обслуживает в диалоговом режиме одно сообщение, то 𝛾𝑖 = 0. 4. Система нелинейных уравнений содержит 𝑄 уравнений вида (12.3). Решение системы нелинейных уравнений можно производить итеративно, как описано в разделе 7. Для шага 𝑠 = 0 диапазон рассчитываемой интенсивности 𝜆0,𝑞 базисного потока сообщений для уравнений контура 𝑞 находится в интервале между 0 и (1⁄ ), то есть 0 ≤ 𝜆0,𝑞 ≤ (1⁄ ) (∑𝑖∈𝑞 1⁄𝜇𝑖 ) (∑𝑖∈𝑞 1⁄𝜇𝑖 ) Результатом итеративного расчета являются 𝜆0,𝑞 для 𝑞 = ̅̅̅̅̅ 1, 𝑄 . 5. По вычисленным 𝑎𝑖,𝑞 и 𝜆0,𝑞 для каждого контура 𝑞 и каждого узла ki по соотношениям (08) и (03) определяем 𝜆𝑖,𝑞 и 𝜌𝑖,𝑞 . Затем вычисляем для каждого 𝑑 контура 𝑞 время ответа 𝑡𝑖,𝑞 в диалоговом режиме и коэффициенты 𝜌𝑖 загрузки узлов. Пример 12.6. Для рассматриваемой WAN приведем результаты расчета характеристик 1) Все численные значения исходных данных, которые необходимы для выполнения расчетов, приведены в примере 12.2 при описании графовой модели. 2) Значения вычисленных 𝑎𝑖,𝑞 приведены в таблице 12.1 3) Значения вычисленных 𝛾𝑖 приведены в таблице 12.1 4) Значения вычисленных 𝜆0,𝑞 равны: 𝜆01 = 3,973 • 1⁄𝑠; 𝜆02 = 4,691 • 1⁄𝑠; 𝜆03 = 1,913 • 1⁄𝑠 5) Значения вычисленных 𝜆𝑖,𝑞 и 𝜌𝑖,𝑞 приведено в таблице 12.1, 𝑑 6) Значения вычисленных характеристик время ответа 𝑡𝑖,𝑞 в диалоговом режиме при функционировании WAN равны: 𝑑 𝑑 𝑑 𝑡45,1 = 2,034 • 𝑠, 𝑡15,2 = 3,395 • 𝑠, 𝑡65,3 = 2,227 • 𝑠. 7) Коэффициенты 𝜌𝑖 загрузки узлов равны. 𝜌1 = 0,5886, 𝜌2 = 0,4691, 𝜌3 = 0,663, 𝜌4 = 0,663, 𝜌5 = 0,3222, 𝜌6 = 0,1611, 𝜌7 = 0,1611, 𝜌8 = 0,663, 𝜌9 = 0,663, 𝜌10 = 0,7132, 𝜌11 = 0,9431, 𝜌12 = 0,391, 𝜌13 = 0,782, 𝜌14 = 0,391. Таблица 12.1 Контур 𝑞=1 Контур узе л 1 3 𝑎𝑖𝑞 1,0 1,0 𝛾𝑖 0,975 4 8 9 45-64 1,0 1,0 1,0 0,05 0,95 0,95 0,95 0,95 0,0 𝜆𝑖,𝑞 3,973 3,973 3,973 3,973 3,973 0,198 6 𝜌𝑖,𝑞 0,397 3 0,663 0,663 0,663 0,663 0,595 8 узе л 2 10 11 12 13 14 15-44 𝑎𝑖𝑞 1,0 0,5 1,0 0,5 1,0 0,5 0,033 3 𝛾𝑖 0,967 0,975 0,975 0,967 0,967 0,967 0,0 𝜆𝑖,𝑞 4,691 2,346 4,691 2,346 4,691 2,346 0,156 4 𝜌𝑖,𝑞 0,469 1 0,391 0,782 0,391 0,782 0,391 0,469 1 𝑞=2 Контур узе л 1 5 6 7 10 11 65-74 𝑎𝑖𝑞 1,0 1,0 0,5 0,5 1,0 0,5 0,1 𝑞=3 𝛾𝑖 0,975 0,9 0,9 0,9 0,975 0,975 0,0 𝜆𝑖,𝑞 1,913 1,913 0,966 5 0,966 5 1,913 0,966 5 0,191 3 𝜌𝑖,𝑞 0,191 3 0,322 2 0,161 1 0,161 1 0,322 2 0,161 1 0,573 9 Самоконтроль знаний Контрольные вопросы 1. Что является одинаковым и в чем состоят различия в описании структуры и функциональной схемы WAN? 2. В чем состоят отличия графовой модели от схемы функционирования WAN? 3. Почему контроллеры отсутствуют в функциональной и графовой моделях ? 4. Каким образом осуществляется описание контуров WAN? 5. Каким образом результаты решения уравнений (12.2) учитываются в системе нелинейных уравнений (12.3)? 6. В чем состоит главная трудность при практическом решении методом дихотомии системы нелинейных уравнений для WAN? Контрольные задания 1. Используя данные из примеров 12.1 - 12.3, составьте и решите системы линейных уравнений для q = 1 и q = 3. 2. Используя данные из примеров 12.1 - 12.3, составьте и решите системы нелинейных уравнений для q = 1 и q = 3. 3. На основании анализа результатов расчета (см. табл. 12.1 примера 12.6) найдите перегруженный участок рассматриваемой WAN. 4. Как можно изменить трассы контуров, чтобы, не ухудшая время ответа пользователям, сократить количество каналов связи в рассматриваемой WAN? 5. Какое предельное количество пользователей в каждой группе WAN могут обслужить ресурсы сети при времени ответа, не превышающем 3 секунды?