Содержание к диссертации
Введение
1. Постановка задачи исследования 12
2. Аналитические модели корпоративной вычислительной сети (КВС) 17
2.1 Вычислительная сеть с многими потоками запросов как открытая сеть системы массового обслуживания (СМО) 17
2.2 Исследование работы центра обработки данных (ЦОД) в неустановившемся режиме работы 30
2.3 Регрессионные модели стоимости мэйнфреймов 36
3. Имитационные модели корпоративной сети 41
3.1 Закон распределения вероятностей случайной величины - времени реакции ЦОД 41
3.2 Имитационное моделирование корпоративной сети
3.3. Входные потоки в корпоративной сети 68
3.4. О количестве реализаций статистической модели 74
4. Проектирование расположения ЦОД на железнодорожном участке 80
4.1 Выбор расположения ЦОД методом полного перебора 80
4.2 Поиск способов размещения ЦОД в корпоративной сети методом случайного поиска 87
Заключение 100
Литература 102
- Вычислительная сеть с многими потоками запросов как открытая сеть системы массового обслуживания (СМО)
- Регрессионные модели стоимости мэйнфреймов
- Входные потоки в корпоративной сети
- Поиск способов размещения ЦОД в корпоративной сети методом случайного поиска
Вычислительная сеть с многими потоками запросов как открытая сеть системы массового обслуживания (СМО)
Проблемы, связанные с разработкой структуры технического обеспечения автоматизированной системы управления (АСУ) отраслью, схожие с проблемами, возникающими при размещении ЦОД в корпоративной сети ОАО «РЖД», были описаны в работе [7]. В ней рассматриваются методики определения числа вычислительных центров (ВЦ), комплектации оборудования, алгоритмы оптимального синтеза структуры сети передачи данных. Однако в далеком 1974-ом году сеть Интернет не существовала, и методы построения АСУ отраслью были совершенно иными, нежели принципы организации современных облачных систем.
Так, ещ в работе [9] формулируются общие принципы построения критерия оптимальности системы. Однако в начале 70-х годов прошлого века основное внимание уделялось сроку окупаемости, приведенным затратам и полным затратам. Рекомендовалось в качестве одной из составляющих критерия оптимальности использовать функцию стоимости надежности комплекса. В монографии [10] предлагается в качестве критерия оптимизации использовать приведенные затраты на создание и эксплуатацию сети. При этом ставится задача оптимального размещения взаимосвязанных вычислительных комплексов в информационно-вычислительной сети как задача нелинейного программирования. Для решения задачи используется метод ветвей и границ [11]. В последующее десятилетие рекомендуется, чтобы критерий эффективности работы вычислительного комплекса учитывал, прежде всего, среднее время ответа системы на запрос, поступивший от пользователя из внешней среды. В работе [12], в которой рассматривались вопросы оптимального проектирования автоматизированных информационных систем (АИС), отмечалось, что нужно минимизировать время реакции АИС при минимизации затрат на технические средства АИС. Таким образом, задача ставилась как задача многокритериальной оптимизации. Ряд методов решения задач оптимального синтеза систем рассматривался в работе [13].
В работе [14] датся формулировка производительности вычислительного комплекса, системы (ВС) и вычислительной сети как основного показателя качества функционирования ВС, отображающего «свойства рабочей нагрузки -задач, решаемых вычислительной системой. С производительностью тесно связана такая характеристика качества обслуживания пользователей, как время ответа, т. е. время пребывания задач в системе» [14]. Этот факт отмечается и в диссертационной работе [15], посвященной вопросам повышения эффективности центров обработки данных (ЦОД).
В настоящее время количество работ, посвященных вопросам построения аналитических и имитационных моделей вычислительных систем, сетей и комплексов, весьма велико. В силу того, что вычислительные сети являются типичными системами массового обслуживания, в которых возникают разнообразные очереди, естественным является привлечение теории массового обслуживания (ТМО) для построения моделей вычислительных сетей.
Практически все аналитические модели опираются на фундаментальную статью Джексона [16], опубликованную в 1957 году. В ней показывается, что результаты, полученные для систем массового обслуживания (СМО) типа МУМУт/оэ, можно применить при расчете стационарного (установившегося) режима работы разомкнутой (открытой) сети СМО, в которой на входе имеется простейший поток с интенсивностью 0 , случайным образом распределяемый между СМО с вероятностями p0j, и где после окончания обслуживания в /-той СМО запрос случайным образом направляется в СМО с номером у с вероятностью pij, причм pi,i = 0, /=0,1,2,3,…,и,y=0,1,2,3,…,w, п - число СМО, образующих сеть. Вероятности переходов задают, по определению Вишневского В.М. [17], маршрутную матрицу, согласно которой в сети двигаются запросы. Другими словами, производится декомпозиция сети на п СМО, каждая из которых обрабатывает потоков запросов с интенсивностью, определяемой системой уравнений (1.1).
Примеры расчета сетей СМО приводятся в книге Кофмана и Крюона [18] по теории систем массового обслуживания. Задача управления потоками в информационно - вычислительных системах на основе приоритетов, приписываемых запросам в системе, ставится в работе [19].
Дальнейшее развитие теоремы Джексона привело к построению различных моделей сетей СМО, в которых имелось несколько классов запросов [20].
В 1967 году теорема, аналогичная теореме Джексона, была доказана и для стационарного режима работы замкнутых сетей СМО. Это работа Гордона и Ньювелла [21], а в 1973 году Бузеном был предложен весьма эффективный алгоритм вычисления характеристик замкнутой сети СМО без перебора всех возможных состояний замкнутой сети [22]. Применение алгоритма Бузена можно найти в современной работе по ЦОД [15]. Нестационарный режим работы замкнутой системы был исследован в работе [23].
Регрессионные модели стоимости мэйнфреймов
Центр обработки данных, работающий в составе сложной системы -корпоративной сети, при предположении о том, что случайные потоки запросов в сети имеют экспоненциальное распределение между моментами поступления запросов, а также при экспоненциальном распределении времени обработки запросов, можно представить как автономно функционирующую систему массового обслуживания типа МШ1/Ю. Условное обозначение М/М/1/ означает пуассоновский входной поток, экспоненциальное распределение времени обслуживания, одно обслуживающее устройство, тип СМО -разомкнутая. Тогда смену состояний СМО можно представить графом состояний [37], представленном на рисунке 2.3 (Si, i=0,1,2,3, … - состояние СМО, при котором в СМО находится i запросов):
На рисунке 2.3 символом Л обозначена интенсивность потока событий -моментов поступления запросов на обработку, в котором длительности интервалов между моментами наступления событий имеют экспоненциальное распределение с плотностью распределения вероятностей:
Время, за которое производные от вероятностей состояний становятся равными 0, есть время, в течение которого ЦОД работает в неустановившемся режиме. Поэтому, решив систему уравнений (2.12) и построив графики изменения вероятностей состояний как функции времени, можно ответить на вопрос о том, как долго, после включения ЦОД, устанавливается стационарный режим работы.
Систему уравнений (2.12) можно решить численно, применив один из известных методов численного решения систем дифференциальных уравнений. Наиболее зарекомендовавшим себя является метод Рунге - Кутта 4-го порядка [38]. Выполним расчет, использовав значения средних времен - времени интервалов во входном потоке и времени обслуживания, взятых из реальных измерений в корпоративной сети ОАО «РЖД».
Результаты решения системы дифференциальных уравнений Колмогорова для указанных значений Л и № приведены на рисунке 2.4 (приведены лишь функции p0(t ) и p 1(t ) с тем, чтобы не загромождать рисунок). Вероятность отсутствия запросов в системе p0 для установившегося режима работы вычисляется по формуле [37] - (2.15):
На рисунке 2.5 прямая, параллельная оси х, представляет из себя установившееся значение средней численности запросов в системе, равное 0,0385, к которому асимптотически стремится функция времени П() .
Результаты, приведенные на рисунках 2.4 и 2.5, показывают, что переходной процесс в ЦОД практически завершается уже после 1.5 секунд после начала интегрирования системы дифференциальных уравнений, описывающих процесс обработки запросов.
При решении различных задач эффективной работы корпоративных вычислительных сетей, в которых основными обрабатывающими узлами являются мэйнфреймы (большие ЭВМ), в качестве одной из составляющих показателя эффективности вычислительной сети (критерия эффективности) используется стоимость мэйнфрейма. Данные о стоимости мэйнфреймов приводятся на Интернет-странице с адресом: http://www.topgun-t ech.com/resource-center/zseries-library
Данные приведены в виде таблиц, содержащих различные характеристики мэйнфреймов, в частности, производительность мэйнфреймов в MIPs (Million Instructions Per Second, быстродействие в миллион операций в секунду), число процессоров, стоимость мэйнфрейма в долларах, что затрудняет вычисление стоимости при реализации алгоритмов решения задач проектирования КВС. Применение метода регрессионного анализа [39], [40] позволяет получить аналитические зависимости стоимости мэйнфрейма от производительности и числа процессоров. Теоретические аспекты регрессионного анализа подробно рассмотрены в учебном пособии [41]. В работе [42] приводятся тексты программ на языке Бэйсик для решения задач аппроксимации экспериментальных данных.
Входные потоки в корпоративной сети
Центр обработки данных работает при случайном потоке запросов на обработку и случайном времени выполнения поступающих запросов. Исследования, проведенные ранее, позволяют представить ЦОД как систему массового обслуживания типа Ml Ml 1 / 00 . Это условное обозначения СМО означает простейший входной поток, экспоненциальное распределение времени обслуживания, одно обслуживающее устройство, бесконечный входной поток, при котором вероятность поступления нового запроса не зависит от того, сколько уже имеется запросов в системе. Расчет времени реакции ЦОД - времени от момента поступления запроса в систему из внешней среды - многочисленного коллектива пользователей по модели Ml Mill GO достаточно хорошо согласуется с экспериментальными данными, поэтому искать ответ на вопрос соответствия работы ЦОД с требованиями стандарта ITIL следует, используя разнообразные модели СМО.
Исследования, выполненные во времена создания самых первых человеко-машинных систем, в которых человек решал разнообразные задачи в режиме диалога с машиной, показал, что у пользователя возникают отрицательные эмоции в том случае, если время ответа превышает 2 секунды [44], [45]. Стандарт ЦОД указывает на величину допустимого значения времени реакции как на величину, согласованную с заказчиком системы.
В силу того, что время реакции ЦОД - величина случайная, оценивать на модели время реакции можно лишь как среднее значение. Для этого необходимо использовать методы теории массового обслуживания и имитационного моделирования для получения вероятности того, что время ответа превысит наперед заданную величину максимально допустимого времени реакции, определенную стандартами. Если применить модель M/M/1/оо , то тогда закон распределения вероятностей случайной величины - времени пребывания запроса в СМО, определяемой как сумма случайных времен - времени пребывания в очереди и собственно времени обслуживания, может быть определен, исходя из следующих соображений.
Если запрос поступает в СМО и застает е свободной с вероятностью pо , то тогда время пребывания в СМО есть случайная величина, имеющая экспоненциальное распределение с параметром М - параметром времени обслуживания, так как имеет место обслуживание собственно поступившего запроса.
Если запрос поступает в СМО и застает в ней один запрос на обслуживании с вероятностью p\, то тогда время пребывания в СМО есть случайная величина, представляющая из себя сумму двух экспоненциальных величин с параметром М - параметром времени обслуживания. Первая - остаток времени дообслуживания того запроса, что был на обслуживании в момент поступления, вторая -обслуживание вновь поступившего запроса. Из курса теории вероятности известно [46], что в случае экспоненциального распределения остаток времени дообслуживания имеет то же самое экспоненциальное распределение с тем же самым параметром И . Следовательно, распределение времени пребывания в СМО в этом случае есть распределение Эрланга 2-го порядка [47]. Если запрос поступает в СМО и застает в ней і запросов (один запрос на обслуживании, (/-7) в очереди) с вероятностью pi , то тогда время пребывания в СМО есть случайная величина, представляющая из себя сумму ( +7)-ой экспоненциально распределенных случайных величин с параметром М -параметром времени обслуживания. Первая - остаток времени дообслуживания того запроса, что был на обслуживании в момент поступления, остальные -обслуживание запросов, выбранных из очереди и вновь поступившего запроса. И дообслуживание, и обслуживание принятых на обслуживание запросов из очереди есть случайные величины, имеющее экспоненциальное распределение с одним и тем же параметром М . Следовательно, распределение времени пребывания в СМО в этом случае есть распределение Эрланга (7+7)-го порядка.
Распределение Эрланга с порядком V = (/ +1) и с параметром М имеет плотность распределения вероятностей [47]: Суммирование проводится от 1 до бесконечности потому, что СМО М/М/1/со имеет бесконечный входной поток, следовательно, теоретически имеет место ненулевая вероятность нахождения сколь угодно большого количества запросов. Вероятности Pi , i= 0,1,2,3,… вычисляются по формулам, приводимым в монографиях по теории массового обслуживания [47]. Однако когда речь идт о поступлении запроса в систему, то следует говорить об условных вероятностях А ,/= 0,1,2,3,… того, что запрос встретит там і запросов в момент поступления. В случае замкнутых СМО эти условные вероятности отличаются от стационарных вероятностей нахождения СМО в состоянии /, где і - число запросов в системе. Однако, как показано в работе [48], для СМО М/М/1/со вероятности Д совпадают со стационарными вероятностями нахождения СМО в состоянии і.
Нетрудно видеть, что использовать громоздкую формулу (3.2) плотности распределения вероятностей случайной величины - времени нахождения запроса в СМО для вычисления вероятности того, что случайная величина превысит наперед заданную величину, довольно сложно при инженерных расчетах, так как необходимо выполнить численное интегрирование (3.2). Поэтому применим метод имитационного (статистического) моделирования [49], [50]. При моделировании была использована общецелевая система моделирования дискретных сложных систем GPSS [51], [52]. При моделировании предполагалось, что единица модельного времени соответствует 1000 миллисекундам реального времени.
Совокупность операционных блоков и команд, описывающих работу СМО на языке GPSS, выглядит достаточно просто и представлена на рисунке 3.1.
Среднее время выполнения запроса в мэйнфрейме ЦОДа составляет 0.0189 секунд для мэйнфрема с производительностью 5939 Mips. В модели за единицу времени принято 0.1 миллисекунды, поэтому первый параметр блока GENERATE, имитирующего простейший поток запросов в СМО, равен 1890 единицам модельного времени, а первый параметр блока ADVANCE, имитирующего время обслуживания, равен 189 единицам модельного времени. При таких параметрах коэффициент загрузки обслуживающего устройства с именем CMO1 теоретически должен быть равен 0.1.
Поиск способов размещения ЦОД в корпоративной сети методом случайного поиска
Значения случайной величины – интервалов между моментами поступления на поездов на станцию Лоста Северной ж.д. (код единой сетевой разметки 300003). Результаты расчетов показывают, что коэффициенты вариации случайной величины для различных дней наблюдения близки к 1, что соответствует экспоненциальному закону распределения вероятностей [40]. Доверительная вероятность принятия гипотезы об экспоненциальном распределении мала, и это можно объяснить тем, что при прохождении поездов имеет место минимально возможный интервал между поездами, равный 4 минутам.
Так как установление закона распределения входного потока запросов в мэйнфрейм ЦОДа не позволило однозначно определить теоретическое распределение, был обработан log-файл, в котором пишутся все моменты наступления событий. Результаты обработки были записаны в файл. Моменты, полученные при обработке выборки:
Вероятность принятия гипотезы об экспоненциальном распределении равна 0.621 при уровне значимости 0.05. Входной поток запросов характеризуется как: случайный - его события происходят в случайные моменты времени; однородный - все заявки потока с точки зрения обслуживания являются равноправными; ординарный - вероятность появления двух или более заявок в течение бесконечно малого интервала времени практически равна нулю по сравнению с вероятностью появления одного события на этом интервале, что объясняется способом прима сообщений - в строгой последовательности один за другим; потоком без последствия - вероятность поступления новых запросов не зависит от того, сколько уже имеется запросов в системе, как в состоянии обработки, так и в состоянии ожидания. Кроме того, случайные величины – длительности интервалов между событиями во входном потоке имеют экспоненциальное распределение. Это позволяет в дальнейшем при построении моделей считать входной поток запросов в ЦОД пуассоновским.
Так как результаты предыдущих работ дают основание считать и времена обработки запросов на мэйфреймах случайными величинами, имеющими экспоненциальное распределение [45], можно считать корпоративную вычислительную сеть сетью систем массового обслуживания с экспоненциальными входными потоками и экспоненциальными временами обслуживания.
В работе [56] отмечается, что статистическое моделирование есть воспроизведение на ЭВМ функционирования вероятностной модели некоторого объекта материального мира. При этом целью моделирования является оценивание средних характеристик модели. Алгоритм, позволяющий получить оценки интересующих исследователя величин при заданном уровне надежности, должен быть оптимальным с точки зрения критерия, в качестве которого выбирают количество вычислений, необходимых для достижения заданной точности .
Процесс переработки в ЭВМ данных в ходе моделирования есть имитация элементарных явлений, составляющих реальный процесс, поэтому имеется прямая аналогия между натурным экспериментом реального объекта (в нашем случае корпоративной вычислительной сети) и машинным экспериментом [57], [58]. В силу этого для определения числа реализаций модели (или длины реализации в единицах модельного времени) требуется применять оценки ошибок измерений, разработанные для исследования реальных систем [56].
При анализе эффективности работы сложной системы при натурных наблюдениях возможны ошибки трех видов: систематические, случайные и промахи, когда исследователь допускает нелепые ошибки по тем или иным причинам в ходе наблюдения за реальной системой. При имитационном моделировании программа тщательно тестируется, поэтому промахи можно отбросить.
Систематические ошибки возникают при измерениях одним и тем же методом и с помощью одних и тех же приборов. При имитационном моделировании принцип накопления статистических выборок в ходе выполнения программы моделирования един, поэтому можно говорить о том, что систематическая ошибка возникает только потому, что нужны данные об установившемся (стационарном) режиме работы исследуемой системы, а пуск модели происходит в тот момент, когда нет ни одного запроса на обслуживании в устройствах, таких, как каналы передачи данных, процессоры, коммутаторы, ни в очередях к устройствам. Систематическая ошибка при моделировании устраняется тем, что в ходе моделирования в течение некоторого начального интервала модельного времени статистика не накапливается.
Случайные ошибки при вычислении выборочных оценок средних и дисперсий таких величин, как времена нахождения на обслуживании и в очереди, а также численности запросов в устройствах и очередях, возникают из-за конечного времени выполнения программы моделирования. Конечный объем выборок конкретных реализаций указанных случайных величин, что вычисленные выборочные средние и дисперсии могут отличаться от их генеральных значений. Поэтому нужно перед запуском модели указывать в качестве исходных данных, сколько раз нужно воспроизвести розыгрыш случайных ситуаций, чтобы накопленные выборки позволили произвести вычисления с заданной точностью.
Выборочное среднее, вычисленное по выборке конечного объема N, является случайной величиной х с генеральной дисперсией СГХ = Sx /N , причем распределение вероятностей случайной величины х - нормальное [47]. За наиболее вероятное значение измеряемой величины принимают е среднее арифметическое значение [59].
Однако для инженерных расчетов такая точность излишняя, достаточно принять интервал в х , тогда доверительная вероятность равна 0.95. Так как среднеквадратическое отклонение обратно пропорционально числу измерений, рекомендуется добиваться его уменьшения путем увеличения числа реализаций статистической модели. Однако возникает вопрос: а каковы разумные пределы числа реализаций модели? Алгоритм расчета необходимого числа реализаций при проведении эксперимента описан в [40].
