ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ ОТКАЗОУСТОЙЧИВОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
УДК 004.738
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ ОТКАЗОУСТОЙЧИВОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
Предложена оценка надежности распределенных вычислительных систем, предусматривающих перераспределение запросов при изменениях потоков запросов, отказах и отключениях узлов системы, объединяемых в совокупность кластеров. Предложена и решена задача оптимизации процесса перераспределения запросов между кластерами с учетом его влияния на задержки обслуживания и надежность системы. Ключевые слова: оптимизация, надежность, перераспределение запросов, кластер, отказоустойчивость.
Введение
Повышение отказоустойчивости, надежности и производительности распределенных вычислительных систем, объединяющих в единую систему множество отдельных кластеров [1–3], достигается в результате динамического перераспределения запросов [4–7] между ними с учетом изменений загруженности кластеров, отказов и временных отключений их узлов.
В распределенной инфраструктуре [1–3], консолидирующей множество ресурсов, объединенных в кластеры, перераспределение запросов (нагрузки) может осуществляться между узлами как одного, так и различных кластеров, соединенных через сеть. При перераспределении запросов между кластерами увеличиваются издержки на взаимосвязь через сеть, но возрастают возможности балансировки загрузки и адаптации к отказам и отключениям узлов, что обусловливает актуальность оптимизации процесса распределения запросов [8, 9].
Задача оптимизации системы
Объектом исследования является распределенная вычислительная система (рис. 1), включающая M локальных кластеров и общедоступный кластер, объединяющий m серверов.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
77
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ …
Рис. 1. Структура распределенной системы
В результате перераспределения запросов от локальных кластеров в общедоступный кластер обеспечивается сбалансированность нагрузки узлов системы и устойчивость системы к отказам и перегрузкам серверов локальных кластеров. Перераспределение запросов от некоторого локального кластера, содержащего в исходном (до отказов) состоянии n серверов, в общедоступный кластер осуществляется через N резервированных коммутационных узлов (маршрутизаторов или коммутаторов) [9].
При оптимизации структуры определяется число (кратность резервирования) серверов в локальных кластерах n и в общем кластере m, а также число коммутационных узлов N, обеспечивающие наибольшую надежность системы P при заданных ограничениях на стоимость построения системы s. При оценке надежности системы, в отличие от [9], где условие работоспособности системы сформулировано как требование сохранения в каждой подсистеме хотя бы одного узла, в предлагаемой работе учитываются нижние ограничения на число узлов в подсистемах, при которых не возникают перегрузки соответствующих кластеров.
При оптимизации процесса распределения запросов с учетом возможности отказов и отключений узлов общедоступного кластера будем считать заданными средние времена выполнения запросов в серверах кластеров и в коммутационных узлах v0 , v1, их интенсивности отказов λ0 , λ1, и восстановлений μ0 ,μ1 . Будем считать известными вероятности r нахождения во включенном состоянии серверов общедоступного кластера. Оптимизация проводится при заданной интенсивности потока запросов λ , поступающего в локальный кластер и при необходимости перераспределяемого через сеть в общедоступный кластер, на который от других кластеров системы через сеть дополнительно направляется поток запросов с интенсивностью Λ = βλ.
При оптимизации структуры будем считать стоимости серверов локальных и общедоступного кластера, а также стоимость коммутационных узлов соответственно равными с0 , с1, с2.
В результате оптимизации процесса распределения потока запросов, поступающего в локальный кластер, ищется их доля, перераспределяемая через сеть в общедоступный кластер, при которой минимизируется среднее время пребывания запросов T.
Отличие предлагаемой задачи оптимизации распределения запросов от [9] заключается в учете возможностей отказов, восстановлений и отключений серверов общедоступного кластера в процессе функционирования. Учет возможности отключения серверов общедоступного кластера обусловлен тем, что предоставляемые им услуги по обслуживанию внешних для него запросов могут проводиться в фоновом режиме и поэтому могут отбрасываться при высокой нагрузке серверов, при решении важных для владельца кластера (сервера) задач, при профилактическом обслуживании или временных отключениях узлов по другим причинам.
Оценка надежности системы Определим вероятность работоспособности системы для локального кластера из n серверов с учетом возможности использования в качестве резерва ресурсов m серверов общедоступного кластера, связь с которым обеспечивается через N коммутационных узлов. Предположим, что пропускная способность каждого коммутационного узла достаточна, чтобы не ограничивать возможности перераспределения запросов, т.е. если исправен хотя бы один коммутационный узел, то запросы могут перераспределяться в общедоступный кластер, но для реализации такого пе-
78 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
рераспределения в локальном кластере должен быть исправен хотя бы один вычислительный узел. С учетом этих условий вероятность работоспособности системы составляет
P
(1
P1 )
n ia
Cni
p0i
(1
p0
)ni
nm
P1
jb
Cj mn
d
j Cmj
p0j (1 p0 )nm j ,
(1)
N
где dj = 1, если j ≤ m, иначе j = 0; P1 CNi p1i (1 p1 )N i – вероятность исправности коммутационной i 1
подсистемы, при этом из соображений отсутствия перегрузки кластеров значения а и b определяются как
ближайшие целые, бóльшие λv0 и λ 1 β v0 .
Надежность узлов определим по коэффициентам готовности, вычисляемым для серверов и коммутационных узлов соответственно как [10, 11]
p0 μ0 / λ0 μ0 ; p1 μ1 / λ1 μ1 .
Формула (1) не учитывает возможность случайных временных отключений серверов общедоступного кластера, с учетом доступности серверов с вероятностью r имеем
P
(1
P1
)
i
n a
Cni
p0i (1
p0
)ni
P1
n i 1
Cni
p0i (1
p0
)ni
m jb
Cmj
p2j (1
p2 )m j ,
где p2 rp0 . Для систем критического применения, не допускающих наличие узлов, отказ которых может
вызвать отказ системы, в качестве базовых средств вычислений используются резервированные вычислительные комплексы [12]. Простейшая структура дублированного вычислительного комплекса (ДВК), скомплектованная из двух связанных через адаптер сопряжения (АС) полукомплексов, включающих процессоры (П) и модули памяти (М), представлена на рис. 2, а. Модель надежности ДВК, допускающего возможность совместной работы процессора и модуля памяти разных полукомплексов, сводится к хорошо изученной в теории надежности модели мостиковой схемы [10, 11], приведенной на рис. 2, б.
Надежность (коэффициент готовности) ДВК, в соответствии с моделью по рис. 2, б, вычисляется как
p0 pa (1 (1 pp )2 ) (1 (1 pM )2 ) 1 pa (1 (1 pp pM )2 ) ,
где при заданных интенсивностях отказов λ p , λM , λa и восстановлений μ p ,μM ,μa процессора, памяти и
адаптера сопряжения соответственно имеем pp μ p / λ p μ p , pM μM / λM μM , pa μa / λa μa .
В случае невозможности совместной работы процессоров и модулей памяти разных полукомплексов надежность ДВК вычислим как
p0 (1 (1 pp pM )2 ) .
ПМ
12
АС 5 АС
ПМ а
34
Процессоры Память б
Рис. 2. Структура (а) и модель надежности (б) ДВК
Для ДВК с ограниченным восстановлением (одновременный ремонт нескольких узлов невозможен) коэффициент готовности определяется как сумма вероятностей работоспособных состояний, для нахождения которых процесс отказов и восстановлений представляется марковским процессом, при этом составляется граф переходов и уравнения Чепмена–Колмогорова, в результате решения которых и определяются искомые вероятности. При оценке вероятностей работоспособных состояний и коэффициента готовности ДВК по рис. 2, а, могут использоваться результаты, полученные в [13].
Оптимизация структуры
При оптимизации структуры рассматриваемой вычислительной системы ищется число серверов n в локальных кластерах, число серверов m в общедоступном кластере и кратность резервирования N коммутационных узлов, обеспечивающие максимум надежности системы, P max P(т, n, N , g, λ), при огра-
т,n,N ,g
ничении стоимости s ее реализации Mc0n c1N c2m s , и условия стационарности функционирова-
ния узлов (отсутствия перегрузки узлов).
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
79
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ …
Поиск максимума P может основаться на переборе, реализуемом с использованием средств системы компьютерной математики Matchcad-15.
Целью оптимизации структуры может быть минимизация среднего времени пребывания запросов в системе [14] при ограничении средств s на ее построение, T min T (т, n, N , g, λ), при этом среднее
т,n,N ,g
время пребывания запросов в системе вычисляется [9] как
T
g
1
v0 gλv0
n
1
g
1
1
2v1
g β 2λv1
N
1
1
v0
g β λv0
m
,
(2)
где (1 – g) – средняя доля запросов, перераспределяемых через сеть от локального кластера в общедос-
тупный. При поиске оптимального g необходимо учитывать условие стационарного режима функциони-
рования узлов (условие отсутствия перегрузки узлов) [9]:
gλv0 n
1
1
g β 2λv1
N
1
1
g
m
β
λv0
1.
(3)
При необходимости оптимизация может быть проведена по мультипликативному критерию
r(т, n, N , g, λ) max P(т, n, N ) / T (т, n, N , g, λ). т,n,N ,g
Оптимизация процесса перераспределения запросов
При заданной структуре системы (сформированной при рассмотренной выше структурной оптимизации) проведем оптимизацию процесса распределения запросов с учетом возможности отказов и отключений исправных узлов общедоступного кластера с вероятностью (1 – r). Оптимизация проводится
при заданной средней интенсивности потока запросов λ , поступающего в локальный кластер и при необходимости перераспределяемого через сеть в общедоступный кластер.
g
0,7
=1 0,6
0,5
=0,5 0,4
0 0,2 0,4 0,6 0,8 1 1,2 , 1/с
Рис. 3. Оптимальная доля запросов, перераспределяемых через сеть
В результате оптимизации процесса распределения потока запросов, поступающего в локальный кластер, ищется их доля, перераспределяемая через сеть в общедоступный кластер, при которой минимизи-
руется среднее время пребывания запросов T. T min T (т, n, N , g, λ), где при модернизации (2) и (3) имеем g
T
g
1
v0 gv0
n
1
g
1
1
2v1
g β 2v1
Nc
1
1
v0
g β v0
mc
,
gv0 n
1
1
g 2v1
Nc
1
1
g v0
mc
1
при математических ожиданиях числа коммутационных узлов Nc и доступных исправных серверов общедоступного кластера, вычисляемых как
80 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
Nm
Nc iCNi p1i (1 p1 )N i , mc jCmj p2j (1 p2 )m j , i 1 j 1
gv0 n
1
1
g
Nc
β
2v1
1
1
g β v0
mc
1.
Для примера проведем оптимизацию процесса распределения запросов при n = 8 шт., N = 5 шт., m = 23 шт.; v0 = 10 c, v1 = 1 c, r = 0,8; λ0 = λ2 = 10–4 1/ч, λ1 = 0,5·10–4 1/ч; µ0 = µ1 = µ2 = 1 1/ч. Результаты поиска оптимальной доли (1 – g), распределяемых через сеть в общедоступный кластер запросов, в зависимости от интенсивности входного потока запросов λ 1/с представлены на рис. 3 при β = 0,5 и β = 1. Рост доли неперераспределяемых запросов g при незначительной интенсивности λ потока запросов объясняется влиянием дополнительных задержек при передаче запросов через сеть, а при значительной интенсивности λ – перегрузкой общедоступного кластера.
Заключение
Поставлены и решены задачи оптимизации структуры вычислительной системы и процесса перераспределения через сеть потока запросов от локальных кластеров в общедоступный кластер с учетом возможностей отказов, восстановлений и отключений серверов общедоступного кластера. Перераспределение запросов реализуется с целью минимизации среднего времени пребывания запросов при адаптации системы к отказам узлов и изменениям потока запросов.
Предложены модели надежности и массового обслуживания вычислительных систем динамического перераспределения запросов (нагрузки) между кластерами, которые могут быть использованы при оценке надежности и выборе рациональных вариантов организации перераспределения запросов в системах с объединением вычислительных ресурсов в локальные и общедоступные кластеры, связанные через сеть.
Работа выполнена на кафедре вычислительной техники НИУ ИТМО в рамках НИР «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем распределенной архитектуры».
Литература
1. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы. – СПб: Питер. – 2003. – 877 с.
2. Clark T. The New Data Center. New technologies are radically reshaping the data center. – Brocade Bookshelf. San Jose, 2010. – 156 p.
3. Кармановский Н.С., Гатчин Ю.А., Терентьев А.О., Федоров Д.Ю., Беккер М.Я. Информационная безопасность при облачных вычислениях: проблемы и перспективы // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 1 (71). – С. 97–102.
4. Богатырев В.А. К повышению надежности вычислительных систем на основе динамического распределения функций // Изв. вузов. Приборостроение. – 1981. – № 8. – С. 62–65.
5. Богатырев В.А. Распределение заданий в многомашинных вычислительных системах // Изв. вузов. Приборостроение. – 1986. – № 5. – С. 43–47.
6. Богатырев В.А. Надежность функционально-распределенных резервированных структур с иерархической конфигурацией узлов // Изв. вузов. Приборостроение. – 2000. – № 4. – С. 67–70.
7. Богатырев В.А. Надежность вычислительных систем с функциональной реконфигурацией на основе перераспределения задач // Информационные технологии. – 2001. – № 7. – С. 22–27.
8. Богатырев В.А., Богатырев С.В. Объединение резервированных серверов в кластеры высоконадежной компьютерной системы // Информационные технологии. – 2009. – № 6. – С. 41–47.
9. Bogatyrеv V.A., Golubev I.Y., Bogatyrеv S.V. Optimization and the Process of Task Distribution between Computer System Clusters // Automatic Control and Computer Sciences. – 2012. – V. 46. – № 3. – P. 103– 111.
10. Гуров С.В., Половко А.М. Основы теории надежности. – СПб: БХВ-Петербург, 2006. – 704 с. 11. Черкесов Г.Н. Надежность аппаратно-программных комплексов. – СПб: Питер, 2005. – 479 с. 12. Bogatyrеv V.A. Exchange of Duplicated Computing Complexes in Fault tolerant Systems // Automatic Con-
trol and Computer Sciences. – 2011. – V. 46. – № 5. – P. 268–276. 13. Богатырев В.А., Башкова С.А., Беззубов В.Ф., Голубев И.Ю., Котельникова Е.Ю., Полякова А.В. На-
дежность дублированных вычислительных комплексов // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 6. – С. 74–78. 14. Алиев Т.И. Основы моделирования дискретных систем. – СПб: СПбГУ ИТМО, 2009. – 363 с.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
81
АЛГОРИТМ И ПРОГРАММА ПОИСКА И ИССЛЕДОВАНИЯ М-МАТРИЦ
Богатырев Владимир Анатольевич Богатырев Анатолий Владимирович Голубев Иван Юрьевич Богатырев Станислав Владимирович
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, Vladimir.bogatyrev@gmail.com
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, gangleon@gmail.com Vladimir.bogatyrev@gmail.com
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, www.golubev@mail.ru
– ООО «Айти Хаус», главный инженер; Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, realloc@gmail.com Vladimir.bogatyrev@gmail.com
82 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
УДК 004.738
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ ОТКАЗОУСТОЙЧИВОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
Предложена оценка надежности распределенных вычислительных систем, предусматривающих перераспределение запросов при изменениях потоков запросов, отказах и отключениях узлов системы, объединяемых в совокупность кластеров. Предложена и решена задача оптимизации процесса перераспределения запросов между кластерами с учетом его влияния на задержки обслуживания и надежность системы. Ключевые слова: оптимизация, надежность, перераспределение запросов, кластер, отказоустойчивость.
Введение
Повышение отказоустойчивости, надежности и производительности распределенных вычислительных систем, объединяющих в единую систему множество отдельных кластеров [1–3], достигается в результате динамического перераспределения запросов [4–7] между ними с учетом изменений загруженности кластеров, отказов и временных отключений их узлов.
В распределенной инфраструктуре [1–3], консолидирующей множество ресурсов, объединенных в кластеры, перераспределение запросов (нагрузки) может осуществляться между узлами как одного, так и различных кластеров, соединенных через сеть. При перераспределении запросов между кластерами увеличиваются издержки на взаимосвязь через сеть, но возрастают возможности балансировки загрузки и адаптации к отказам и отключениям узлов, что обусловливает актуальность оптимизации процесса распределения запросов [8, 9].
Задача оптимизации системы
Объектом исследования является распределенная вычислительная система (рис. 1), включающая M локальных кластеров и общедоступный кластер, объединяющий m серверов.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
77
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ …
Рис. 1. Структура распределенной системы
В результате перераспределения запросов от локальных кластеров в общедоступный кластер обеспечивается сбалансированность нагрузки узлов системы и устойчивость системы к отказам и перегрузкам серверов локальных кластеров. Перераспределение запросов от некоторого локального кластера, содержащего в исходном (до отказов) состоянии n серверов, в общедоступный кластер осуществляется через N резервированных коммутационных узлов (маршрутизаторов или коммутаторов) [9].
При оптимизации структуры определяется число (кратность резервирования) серверов в локальных кластерах n и в общем кластере m, а также число коммутационных узлов N, обеспечивающие наибольшую надежность системы P при заданных ограничениях на стоимость построения системы s. При оценке надежности системы, в отличие от [9], где условие работоспособности системы сформулировано как требование сохранения в каждой подсистеме хотя бы одного узла, в предлагаемой работе учитываются нижние ограничения на число узлов в подсистемах, при которых не возникают перегрузки соответствующих кластеров.
При оптимизации процесса распределения запросов с учетом возможности отказов и отключений узлов общедоступного кластера будем считать заданными средние времена выполнения запросов в серверах кластеров и в коммутационных узлах v0 , v1, их интенсивности отказов λ0 , λ1, и восстановлений μ0 ,μ1 . Будем считать известными вероятности r нахождения во включенном состоянии серверов общедоступного кластера. Оптимизация проводится при заданной интенсивности потока запросов λ , поступающего в локальный кластер и при необходимости перераспределяемого через сеть в общедоступный кластер, на который от других кластеров системы через сеть дополнительно направляется поток запросов с интенсивностью Λ = βλ.
При оптимизации структуры будем считать стоимости серверов локальных и общедоступного кластера, а также стоимость коммутационных узлов соответственно равными с0 , с1, с2.
В результате оптимизации процесса распределения потока запросов, поступающего в локальный кластер, ищется их доля, перераспределяемая через сеть в общедоступный кластер, при которой минимизируется среднее время пребывания запросов T.
Отличие предлагаемой задачи оптимизации распределения запросов от [9] заключается в учете возможностей отказов, восстановлений и отключений серверов общедоступного кластера в процессе функционирования. Учет возможности отключения серверов общедоступного кластера обусловлен тем, что предоставляемые им услуги по обслуживанию внешних для него запросов могут проводиться в фоновом режиме и поэтому могут отбрасываться при высокой нагрузке серверов, при решении важных для владельца кластера (сервера) задач, при профилактическом обслуживании или временных отключениях узлов по другим причинам.
Оценка надежности системы Определим вероятность работоспособности системы для локального кластера из n серверов с учетом возможности использования в качестве резерва ресурсов m серверов общедоступного кластера, связь с которым обеспечивается через N коммутационных узлов. Предположим, что пропускная способность каждого коммутационного узла достаточна, чтобы не ограничивать возможности перераспределения запросов, т.е. если исправен хотя бы один коммутационный узел, то запросы могут перераспределяться в общедоступный кластер, но для реализации такого пе-
78 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
рераспределения в локальном кластере должен быть исправен хотя бы один вычислительный узел. С учетом этих условий вероятность работоспособности системы составляет
P
(1
P1 )
n ia
Cni
p0i
(1
p0
)ni
nm
P1
jb
Cj mn
d
j Cmj
p0j (1 p0 )nm j ,
(1)
N
где dj = 1, если j ≤ m, иначе j = 0; P1 CNi p1i (1 p1 )N i – вероятность исправности коммутационной i 1
подсистемы, при этом из соображений отсутствия перегрузки кластеров значения а и b определяются как
ближайшие целые, бóльшие λv0 и λ 1 β v0 .
Надежность узлов определим по коэффициентам готовности, вычисляемым для серверов и коммутационных узлов соответственно как [10, 11]
p0 μ0 / λ0 μ0 ; p1 μ1 / λ1 μ1 .
Формула (1) не учитывает возможность случайных временных отключений серверов общедоступного кластера, с учетом доступности серверов с вероятностью r имеем
P
(1
P1
)
i
n a
Cni
p0i (1
p0
)ni
P1
n i 1
Cni
p0i (1
p0
)ni
m jb
Cmj
p2j (1
p2 )m j ,
где p2 rp0 . Для систем критического применения, не допускающих наличие узлов, отказ которых может
вызвать отказ системы, в качестве базовых средств вычислений используются резервированные вычислительные комплексы [12]. Простейшая структура дублированного вычислительного комплекса (ДВК), скомплектованная из двух связанных через адаптер сопряжения (АС) полукомплексов, включающих процессоры (П) и модули памяти (М), представлена на рис. 2, а. Модель надежности ДВК, допускающего возможность совместной работы процессора и модуля памяти разных полукомплексов, сводится к хорошо изученной в теории надежности модели мостиковой схемы [10, 11], приведенной на рис. 2, б.
Надежность (коэффициент готовности) ДВК, в соответствии с моделью по рис. 2, б, вычисляется как
p0 pa (1 (1 pp )2 ) (1 (1 pM )2 ) 1 pa (1 (1 pp pM )2 ) ,
где при заданных интенсивностях отказов λ p , λM , λa и восстановлений μ p ,μM ,μa процессора, памяти и
адаптера сопряжения соответственно имеем pp μ p / λ p μ p , pM μM / λM μM , pa μa / λa μa .
В случае невозможности совместной работы процессоров и модулей памяти разных полукомплексов надежность ДВК вычислим как
p0 (1 (1 pp pM )2 ) .
ПМ
12
АС 5 АС
ПМ а
34
Процессоры Память б
Рис. 2. Структура (а) и модель надежности (б) ДВК
Для ДВК с ограниченным восстановлением (одновременный ремонт нескольких узлов невозможен) коэффициент готовности определяется как сумма вероятностей работоспособных состояний, для нахождения которых процесс отказов и восстановлений представляется марковским процессом, при этом составляется граф переходов и уравнения Чепмена–Колмогорова, в результате решения которых и определяются искомые вероятности. При оценке вероятностей работоспособных состояний и коэффициента готовности ДВК по рис. 2, а, могут использоваться результаты, полученные в [13].
Оптимизация структуры
При оптимизации структуры рассматриваемой вычислительной системы ищется число серверов n в локальных кластерах, число серверов m в общедоступном кластере и кратность резервирования N коммутационных узлов, обеспечивающие максимум надежности системы, P max P(т, n, N , g, λ), при огра-
т,n,N ,g
ничении стоимости s ее реализации Mc0n c1N c2m s , и условия стационарности функционирова-
ния узлов (отсутствия перегрузки узлов).
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
79
ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАПРОСОВ МЕЖДУ КЛАСТЕРАМИ …
Поиск максимума P может основаться на переборе, реализуемом с использованием средств системы компьютерной математики Matchcad-15.
Целью оптимизации структуры может быть минимизация среднего времени пребывания запросов в системе [14] при ограничении средств s на ее построение, T min T (т, n, N , g, λ), при этом среднее
т,n,N ,g
время пребывания запросов в системе вычисляется [9] как
T
g
1
v0 gλv0
n
1
g
1
1
2v1
g β 2λv1
N
1
1
v0
g β λv0
m
,
(2)
где (1 – g) – средняя доля запросов, перераспределяемых через сеть от локального кластера в общедос-
тупный. При поиске оптимального g необходимо учитывать условие стационарного режима функциони-
рования узлов (условие отсутствия перегрузки узлов) [9]:
gλv0 n
1
1
g β 2λv1
N
1
1
g
m
β
λv0
1.
(3)
При необходимости оптимизация может быть проведена по мультипликативному критерию
r(т, n, N , g, λ) max P(т, n, N ) / T (т, n, N , g, λ). т,n,N ,g
Оптимизация процесса перераспределения запросов
При заданной структуре системы (сформированной при рассмотренной выше структурной оптимизации) проведем оптимизацию процесса распределения запросов с учетом возможности отказов и отключений исправных узлов общедоступного кластера с вероятностью (1 – r). Оптимизация проводится
при заданной средней интенсивности потока запросов λ , поступающего в локальный кластер и при необходимости перераспределяемого через сеть в общедоступный кластер.
g
0,7
=1 0,6
0,5
=0,5 0,4
0 0,2 0,4 0,6 0,8 1 1,2 , 1/с
Рис. 3. Оптимальная доля запросов, перераспределяемых через сеть
В результате оптимизации процесса распределения потока запросов, поступающего в локальный кластер, ищется их доля, перераспределяемая через сеть в общедоступный кластер, при которой минимизи-
руется среднее время пребывания запросов T. T min T (т, n, N , g, λ), где при модернизации (2) и (3) имеем g
T
g
1
v0 gv0
n
1
g
1
1
2v1
g β 2v1
Nc
1
1
v0
g β v0
mc
,
gv0 n
1
1
g 2v1
Nc
1
1
g v0
mc
1
при математических ожиданиях числа коммутационных узлов Nc и доступных исправных серверов общедоступного кластера, вычисляемых как
80 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
В.А. Богатырев, А.В. Богатырев, И.Ю. Голубев, С.В. Богатырев
Nm
Nc iCNi p1i (1 p1 )N i , mc jCmj p2j (1 p2 )m j , i 1 j 1
gv0 n
1
1
g
Nc
β
2v1
1
1
g β v0
mc
1.
Для примера проведем оптимизацию процесса распределения запросов при n = 8 шт., N = 5 шт., m = 23 шт.; v0 = 10 c, v1 = 1 c, r = 0,8; λ0 = λ2 = 10–4 1/ч, λ1 = 0,5·10–4 1/ч; µ0 = µ1 = µ2 = 1 1/ч. Результаты поиска оптимальной доли (1 – g), распределяемых через сеть в общедоступный кластер запросов, в зависимости от интенсивности входного потока запросов λ 1/с представлены на рис. 3 при β = 0,5 и β = 1. Рост доли неперераспределяемых запросов g при незначительной интенсивности λ потока запросов объясняется влиянием дополнительных задержек при передаче запросов через сеть, а при значительной интенсивности λ – перегрузкой общедоступного кластера.
Заключение
Поставлены и решены задачи оптимизации структуры вычислительной системы и процесса перераспределения через сеть потока запросов от локальных кластеров в общедоступный кластер с учетом возможностей отказов, восстановлений и отключений серверов общедоступного кластера. Перераспределение запросов реализуется с целью минимизации среднего времени пребывания запросов при адаптации системы к отказам узлов и изменениям потока запросов.
Предложены модели надежности и массового обслуживания вычислительных систем динамического перераспределения запросов (нагрузки) между кластерами, которые могут быть использованы при оценке надежности и выборе рациональных вариантов организации перераспределения запросов в системах с объединением вычислительных ресурсов в локальные и общедоступные кластеры, связанные через сеть.
Работа выполнена на кафедре вычислительной техники НИУ ИТМО в рамках НИР «Разработка методов и средств системотехнического проектирования информационных и управляющих вычислительных систем распределенной архитектуры».
Литература
1. Таненбаум Э., Ван Стеен М. Распределенные системы. Принципы и парадигмы. – СПб: Питер. – 2003. – 877 с.
2. Clark T. The New Data Center. New technologies are radically reshaping the data center. – Brocade Bookshelf. San Jose, 2010. – 156 p.
3. Кармановский Н.С., Гатчин Ю.А., Терентьев А.О., Федоров Д.Ю., Беккер М.Я. Информационная безопасность при облачных вычислениях: проблемы и перспективы // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 1 (71). – С. 97–102.
4. Богатырев В.А. К повышению надежности вычислительных систем на основе динамического распределения функций // Изв. вузов. Приборостроение. – 1981. – № 8. – С. 62–65.
5. Богатырев В.А. Распределение заданий в многомашинных вычислительных системах // Изв. вузов. Приборостроение. – 1986. – № 5. – С. 43–47.
6. Богатырев В.А. Надежность функционально-распределенных резервированных структур с иерархической конфигурацией узлов // Изв. вузов. Приборостроение. – 2000. – № 4. – С. 67–70.
7. Богатырев В.А. Надежность вычислительных систем с функциональной реконфигурацией на основе перераспределения задач // Информационные технологии. – 2001. – № 7. – С. 22–27.
8. Богатырев В.А., Богатырев С.В. Объединение резервированных серверов в кластеры высоконадежной компьютерной системы // Информационные технологии. – 2009. – № 6. – С. 41–47.
9. Bogatyrеv V.A., Golubev I.Y., Bogatyrеv S.V. Optimization and the Process of Task Distribution between Computer System Clusters // Automatic Control and Computer Sciences. – 2012. – V. 46. – № 3. – P. 103– 111.
10. Гуров С.В., Половко А.М. Основы теории надежности. – СПб: БХВ-Петербург, 2006. – 704 с. 11. Черкесов Г.Н. Надежность аппаратно-программных комплексов. – СПб: Питер, 2005. – 479 с. 12. Bogatyrеv V.A. Exchange of Duplicated Computing Complexes in Fault tolerant Systems // Automatic Con-
trol and Computer Sciences. – 2011. – V. 46. – № 5. – P. 268–276. 13. Богатырев В.А., Башкова С.А., Беззубов В.Ф., Голубев И.Ю., Котельникова Е.Ю., Полякова А.В. На-
дежность дублированных вычислительных комплексов // Научно-технический вестник СПбГУ ИТМО. – 2011. – № 6. – С. 74–78. 14. Алиев Т.И. Основы моделирования дискретных систем. – СПб: СПбГУ ИТМО, 2009. – 363 с.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
81
АЛГОРИТМ И ПРОГРАММА ПОИСКА И ИССЛЕДОВАНИЯ М-МАТРИЦ
Богатырев Владимир Анатольевич Богатырев Анатолий Владимирович Голубев Иван Юрьевич Богатырев Станислав Владимирович
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, доктор технических наук, профессор, Vladimir.bogatyrev@gmail.com
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, gangleon@gmail.com Vladimir.bogatyrev@gmail.com
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, www.golubev@mail.ru
– ООО «Айти Хаус», главный инженер; Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, аспирант, realloc@gmail.com Vladimir.bogatyrev@gmail.com
82 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)