автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка методики оптимизации распределения ресурсов центров обработки данных в сети интернет

На правах рукописи

Тутова Наталья Владимировна

РАЗРАБОТКА МЕТОДИКИ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ЦЕНТРОВ ОБРАБОТКИ ДАННЫХ В СЕТИ ИНТЕРНЕТ

Специальность 05.13.13 - Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2009

003462946

Работа выполнена на кафедре информационных технологий в экономике и управлении Государственного образовательного учреждения высшего профессионального образования Московский технический университет связи и информатики (МТУСИ).

Научный руководитель:

Официальные оппоненты:

кандидат технических наук, доцент Ворожцов Анатолий Сергеевич

доктор технических наук, профессор Самуйлов Константин Евгеньевич

кандидат технических наук, доцент Зелевич Евгений Павлович

Ведущая организация:

Всероссийский научно-исследовательский институт проблем вычислительной техники и информатизации (ВНИИПВТИ)

Защита диссертации состоится /¿¿марта 2009 г. в часов на заседании совета по защите докторских и кандидатских диссертаций Д 219.001.03 при МТУСИ по адресу: 111024, Москва, ул. Авиамоторная, дом 8а, ауд.

С диссертацией можно ознакомиться в библиотеке МТУСИ.

Автореферат разослан « '/О» — 2009 г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Современный этап развития глобальной сети Интернет характеризуется трансформацией традиционных услуг и бизнес-процессов компаний в электронные, основанные на Web-технологиях, что привело к появлению широкого спектра систем электронного бизнеса, которые стали ключевыми в успехе работы компаний и поддержке их конкурентоспособности. Практически все крупные операторы связи и сервис-провайдеры стали оказывать услуги хостинга в центрах обработки данных (ЦОД), которые предоставляют физические ресурсы для размещения серверов и высокоскоростной доступ в Интернет. Современный процесс предоставления услуг компаниями, владеющими коммерческими ЦОД, характеризуется появлением соглашений о качестве обслуживания (Service Level Agreement— SLA), гарантирующих определенный уровень показателей качества, таких как среднее время ответа на запрос пользователя, максимальное время ответа для заданной доли запросов, коэффициент готовности и др.

Интенсивность запросов к Интернет-приложениям значительно меняется в течение суток, а в периоды пиковых нагрузок, возникающих в случайные моменты времени, может возрастать в несколько раз. Известно также, что в такие периоды значительно уменьшается число электронных платежей в единицу времени, которое в зарубежной литературе называют финансовой пропускной способностью (Revenue Throughput). Центры обработки данных в сети Интернет имеют многозвенную архитектуру, включающую в себя кроме Web-серверов, кластеры серверов приложений и серверов баз данных, число которых может достигать сотен и тысяч. Поэтому выполнение SLA-соглашений является сложной задачей, прямо влияющей на конкурентоспособность компаний. Одним из путей ее решения является оптимальное распределение серверов по кластерам и поиск более эффективного метода управления доступом пользователей к этим ресурсам в периоды пиковых нагрузок.

Современной тенденцией является увеличение числа показателей качества обслуживания, задаваемых в SLA-соглашениях, удовлетворение которых приводит к необходимости использования многокритериального подхода, теория которого развита такими отечественными учеными как Подиновский В.В., Ногин В.Д., Михалевич B.C., Волкович B.JL, Батищев Д.И. и др.

Проблема оптимизации распределения ресурсов ЦОД рассматривалась в работах зарубежных ученых Menasce D., Almeida V. и др. Однако в существующих работах оптимизация проводилась по одному критерию для узкого класса SLA-соглашений. Отсутствует методика распределения ресурсов ЦОД, работающих по SLA-соглашениям различных видов, которая включала бы в себя определение оптимального числа серверов в кластерах по нескольким критериям и эффективный метод управления доступом к таким ресурсам, позволяющий повысить число обслуженных приоритетных пользователей, т.е.

финансовую пропускную способность ЦОД. Поэтому тема диссертационной работы является актуальной.

Цель работы и задачи исследования. Целью диссертационной работы является разработка методики оптимизации распределения ресурсов центров обработки данных по нескольким критериям и обеспечения эффективного управления доступом пользователей к этим ресурсам в периоды пиковых нагрузок.

Поставленная в диссертационной работе цель достигается решением следующих задач:

1. Анализ системы соглашений о качестве обслуживания. Постановка задачи определения оптимального среднего времени ответа по соглашениям о качестве обслуживания.

2. Выбор и разработка моделей центров обработки данных в сети Интернет, отражающих особенности их функционирования.

3. Разработка математических моделей распределения ресурсов центров обработки данных по нескольким критериям для различных видов соглашений о качестве обслуживания.

4. Выбор метода многокритериальной оптимизации распределения ресурсов центров обработки данных в сети Интернет, позволяющего получить оптимальный план размещения серверов не только для длительного времени повышения интенсивности потока запросов, но и в короткие периоды пиковых нагрузок.

5. Разработка алгоритма решения задачи многокритериальной оптимизации распределения ресурсов центров обработки данных.

6. Разработка метода управления доступом пользователей коммерческих сайтов в периоды пиковых нагрузок.

7. Разработка рекомендаций и процедур практической реализации методики оптимизации распределения ресурсов центров обработки данных.

Методы исследования. Для решения поставленных задач использованы методы многокритериальной оптимизации, теории вероятностей и математической статистики, теории массового обслуживания.

Научная новизна работы состоит в разработанной методике оптимизации распределения ресурсов центров обработки данных в сети Интернет, включающей в себя:

1. Модели оптимизации распределения ресурсов центров обработки данных для соглашений о качестве обслуживания как без разделения, так и с разделением запросов на классы, в которых в отличие от известных моделей для оптимального распределения ресурсов используется многокритериальный подход.

2. Модифицированный метод последовательных уступок, сокращающий в несколько раз в зависимости от числа используемых критериев оптимизации время нахождения оптимального решения по сравнению с традиционным методом последовательных уступок, что позволяет использовать его в контуре оперативного управления ресурсами как в нормальном режиме функционирования центров обработки данных, так и в периоды пиковых нагрузок.

3. Усовершенствованный метод управления доступом к коммерческим сайтам, позволяющий повысить финансовую пропускную способность сайтов в периоды пиковых нагрузок до 30% и по сравнению с известным методом исключающий необходимость проведения случайного числа экспериментов по определению момента снижения приоритетов пользователям.

Практическая ценность и реализация результатов работы:

1. Разработанная методика оптимизации распределения ресурсов центров обработки данных позволяет найти оптимальное число серверов в кластерах в зависимости от нагрузки и обеспечить заданный в ЗЬА-соглашениях уровень качества.

2. Программно реализована процедура определения компромиссной уступки, которая положена в основу предложенного модифицированного метода последовательных уступок, позволяющая сократить время решения задачи как минимум в два раза.

3. Разработаны алгоритмы по обработке журналов регистрации запросов с целью получения параметров пользовательских сессий и рекомендации по формированию критериев и систем ограничений задач оптимизации распределения ресурсов центров обработки данных, что позволяет реализовать разработанную методику.

4. Усовершенствован метод управления доступом пользователей к коммерческим сайтам, исключающий необходимость проведения случайного числа экспериментов по определению момента снижения приоритетов пользователям.

Результаты диссертационной работы используются в учебном процессе МТУСИ. Алгоритм расчета оптимального числа серверов используется в текущей деятельности Интернет-провайдера ООО «НФС Телеком», что подтверждено соответствующим актом.

Личный вклад. Основные научные результаты, приведенные в диссертации, получены автором лично.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях: международной научно-технической конференции «Телекоммуникационные и вычислительные

системы», Москва, 2006 г., 2007 г., 2008 г., Московской отраслевой научно-технической конференции «Технологии информационного общества, Москва, 2007 г., 2008 г., международной конференции «Информационные средства и системы», Москва, 2008 г.

Публикации. По теме диссертационной работы опубликовано 10 печатных работ (из них 2 статьи в ведущих рецензируемых научных журналах из перечня, рекомендованного ВАК). Получено свидетельство о государственной регистрации программы для ЭВМ.

Объем и структура работы. Диссертационная работа состоит из введения, 4 • глав, заключения, списка использованных источников и трех приложений. Работа изложена на 182 страницах машинописного текста, включает в себя 38 рисунков и 11 таблиц. В списке использованной литературы 110 наименований.

Основные положения, выносимые на защиту:

1. Методика оптимизации распределения серверов в многозвенной архитектуре центров обработки данных по критериям минимума совокупной стоимости владения серверами и максимума пропускной способности центра обработки данных, обеспечивающая заданное в SLA-соглашениях качество обслуживания.

2. Предложенная модификация метода последовательных уступок по сравнению с традиционным методом сокращает время получения оптимального решения в зависимости от числа используемых критериев в несколько раз, что позволяет включить данный метод в контур оперативного управления ресурсами центров обработки данных.

3. Методика определения длительности пользовательских сессий, которая позволяет аналитически найти их величину, начиная с которой следует ограничивать доступ к сайтам пользователей, что может повысить финансовую пропускную способность центра обработки данных до 30 % .

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность выбранной темы, определена цель и сформулированы решаемые в работе задачи. Перечислены новые научные результаты, полученные при выполнении работы, показаны практическая ценность и апробация работы, описаны внедрение и реализация результатов. Сформулированы основные положения, выносимые на защиту.

В первой главе проанализированы основные тенденции развития центров обработки данных в сети Интернет. Рассмотрены виды хостинга Интернет-приложений в ЦОД, такие как выделенный и совместный хостинг. При выделенном хостинге (dedicated hosting) под каждое приложение отведена совокупность серверов, которые обслуживают только это приложение. В случае

совместного (shared) хостинга, кластеры серверов обслуживают большое количество приложений.

Рассмотрены основные показатели качества, задаваемые в SLA-соглашениях, такие как среднее время ответа на запрос и максимальное время ответа для заданной доли запросов, а также следующие способы задания требований на качество обслуживания в SLA-соглашениях:

• без выделения уровней обслуживания и классов запросов;

• с выделением уровней обслуживания, без разделения запросов на классы;

• без выделения уровней обслуживания, с разделением запросов на классы.

В первой группе SLA-соглашений задается ограничение на среднее время

ответа независимо от вида запросов. Если фактическое значение среднего времени ответа на запрос не превышает заданного в соглашении порогового значения, то сервис-провайдер получает определенный размер вознаграждения, если иначе, то сервис-провайдер выплачивает штраф.

В случае выделения уровней обслуживания, задается несколько пороговых значений среднего времени ответа, при достижении которых изменяется размер вознаграждений и штрафов. Такой вид SLA-соглашений в литературе представляется в виде ступенчатой функции полезности.

В третьей группе SLA-соглашений ограничение на среднее время ответа задается аналогично первой группе, только для нескольких классов запросов.

В работе рассмотрена классификация запросов по функциональному признаку. Например, для коммерческого сайта, под классами запросов понимаются запросы на «Поиск», «Просмотр», «Добавление в корзину», «Оплату» и др. Последовательность таких запросов от одного пользователя за время посещения сайта составляет Web-сессию, которая характеризует его поведение на сайте. Пользователи, которые имеют короткую сессию, заканчивающуюся электронным платежом, называют активными. Они являются наиболее ценными пользователями коммерческих сайтов.

Также в первой главе проведен анализ проблем обеспечения заданного в SLA-соглашениях качества обслуживания, основными из которых являются неравномерность нагрузки в течение суток, наличие периодов пиковой нагрузки, возникающих в случайные моменты времени, а также сложность многозвенной архитектуры современных Интернет-приложений. Рассмотрены методы обеспечения заданного в SLA-соглашениях качества обслуживания, такие как оптимальное распределение серверов по кластерам и управление доступом пользователей сайтов. На основании проведенного обзора работ сформулированы цель и задачи диссертационного исследования, решение которых позволит усовершенствовать управление ресурсами ЦОД в сети Интернет.

Во второй главе на основе анализа известных моделей массового обслуживания применительно к задачам, решаемым в диссертации, развиты модели функционирования центров обработки данных как без разделения, так и

с разделением запросов на классы. В обоих случаях ЦОД моделируется как открытая сеть массового обслуживания с типами улов M/G/1 и дисциплиной обслуживания «разделение процессора». Каждый узел представляет собой кластер серверов (например, Web-серверов, серверов приложений, серверов баз данных). Также было сделано предположение о том, что серверы внутри кластеров являются одинаковыми по производительности. В модели ЦОД без разделения запросов на классы рассматривается общий пуассоновский поток заявок, а во второй модели ЦОД учитываются многоклассовость входного потока, сессии пользователей, а также модели их поведения на коммерческих сайтах.

Полученные модели ЦОД послужили основой для разработки систем ограничений в задачах оптимизации распределения серверов в кластерах, участвующих в обработке запросов. Анализ возможных критериев оптимизации для рассматриваемой предметной области показал, что основными критериями могут быть максимум пропускной способности ЦОД и минимум совокупной стоимости владения (Total Cost of Ownership—TCO) серверами различных кластеров.

С учетом полученных результатов для группы SLA-соглашений без разделения запросов на классы, в которых задается ограничение на среднее время ответа, постановка задачи оптимизации сформулирована следующим образом:

max Fnc{Su...,Sc)= I-^Ч (1)

{х,.....sc>

с=\тт

.min Fm>{Su...,Sc)=YiTCOe-Se- (2)

(-V-A.-I

Tcp = Z-ï-^rït'su, (3)

при ограничениях

"Тс £=1 ^ - дс

?с< с=1.....С, (4)

где С — число кластеров в ЦОД;

— число серверов в кластере с,с= 1,..., С; Р"пс— критерий пропускной способности ЦОД; Ртсо— критерий совокупной стоимости владения серверами ЦОД; ТСОс— совокупная стоимость владения одним сервером кластера с; Тср — среднее время ответа на запрос;

к

— — среднее число посещении запросом кластера с за время его X

нахождения в системе;

X — интенсивность поступления запросов в систему; Хс— интенсивность поступления запросов в кластер с;

— номинальная загрузка кластера с с одним сервером при нагрузке лс; Б™"*— максимальное возможное число серверов в кластере с; тТс — среднее время обработки запроса слабозагруженным сервером кластера с;

* ¡¿а — оптимальное среднее время ответа, определяемое из анализа БЬА-соглашений.

С ограничением на максимальное время ответа для заданной доли всех запросов постановка задачи сформулирована следующим образом:

(5)

№.....sc)

c=\mT

min F.]C0 (Sb..„ sc) = ЪCOc • ; (6)

i-V-Jcl c_|

при ограничениях

Р[Г>К]<£, (7)

?c<5c<5cm";c=l, ...,C, (8)

где ограничение (7) задается в SLA-соглашениях как «вероятность превышения времени ответа на запрос Г величины F должно быть не более с».

Используя неравенство Маркова, ограничение (7) предлагается аппроксимировать следующим выражением:

P[T>V]<Tcp/V, (9)

где Тср - среднее время ответа на запрос, которое можно получить, используя выражение (3).

Для группы SLA-соглашений, в которых задается ограничение на среднее время ответа с разделением запросов на классы, постановка задачи оптимизации распределения серверов в кластерах имеет следующий вид:

тах Fnc(Slt...,Sc)=j£-^— (10)

TS С

л- k=1

min FTC0(S{,...,SC)= ^ТСОс-Sc ; (11)

t5l.....ЛС') c=l

при ограничениях

с=1 А*

9„< с= 1,..., С, (13)

где С—число кластеров ЦОД; К—число классов запросов;

— число серверов в кластере с; Гпс — критерий пропускной способности ЦОД; Ртсо — критерий совокупной стоимости владения серверами ЦОД; ТСОс — совокупная стоимость владения одним сервером кластера с; дс— номинальная загрузка кластера с с одним сервером при нагрузке ).с; /я* — среднее время обработки запроса класса к слабозагруженным сервером кластера с;

— среднее число посещений кластера с запросом класса к за время его

Л

нахождения в системе;

Л* — интенсивность поступления запросов класса к в кластер с;

лк— интенсивность поступления запросов класса к в систему;

Т*и — ограничение на среднее время ответа на запрос класса к, задаваемое

в БЬА-соглашении;

5С|Ш— максимальное возможное число серверов в кластере с. С ограничением на максимальное время ответа для заданной доли всех запросов постановка задачи сформулирована следующим образом:

с 5

тах р//с<5ь...,5С) = 2-Г#-7; (14) .....-11

К к=1

,™п ад=Ъсос • ; (15)

г-5!.....«г/

при ограничениях

Р[1к>Ук]<е\ к=1,...,К, (16)

дс<Яс<Зстах, с= 1,..., С, (17)

где ограничение (16) задается в БЬА-соглашениях как «вероятность превышения времени ответа Т* на запрос класса к величины У* не должна быть более е*».

Для нахождения параметра / приведенного в ограничении (3) проведен анализ ЗЬА-соглашений без разделения запросов на классы. Если в БЬА-соглашениях выделены уровни обслуживания, то строится агрегированная функция полезности по всем соглашениям. Составляющие этой функции: функции вознаграждений (/в) и штрафов (/щ) предлагается аппроксимировать экспоненциальной и степенной функциями соответственно.

Для учета затрат провайдера на обеспечение среднего времени ответа предлагается следующая функция затрат (/з): ' с \2

1з(к,А) =

■ тГг ■ Я с

с

ш - 1т1с

с=1

(18)

где ТСОс— совокупная стоимость владения сервером кластера с, с = 1, ..., С; шгс — среднее время обработки запроса слабозагруженным сервером кластера с, с= 1,..., С;

<7С — номинальная загрузка кластера с с одним сервером при заданной нагрузкеХс,с = \, ...,С,

к¡л — среднее время ответа на запрос в системе.

Тогда функцию прибыли можно определить как:

МЬи) =/вОял) - Ш'эи) +/з(^)). С учетом приведенного критерия постановка задачи нахождения оптимального среднего времени ответа имеет следующий вид:

' (с ^

{'¡¡и )

Н'яи _

*2 «ЯЛ?

Т^ТСОс-тГс ■ цс

с=1 ______

С

С=1 с

(19)

при ограничениях

'ал

/ </шзх

(20)

где аь ¿1 — коэффициенты функции вознаграждений по БЬА-соглашениям; а2, Ь2— коэффициенты функции штрафов по БЬА-соглашениям; ТСОс—совокупная стоимость владения сервером кластера с, с = 1, ...,С; тТс — среднее время обработки запроса слабозагруженным сервером кластера с, с = 1.....С;

(¡с — номинальная загрузка кластера с с одним сервером при заданной нагрузке Хс, с = 1,..., С;

¿'/Л

• минимальное допустимое среднее время ответа на запрос;

ы — максимальное допустимое среднее время ответа на запрос.

Также во второй главе предложен усовершенствованный метод управления доступом пользователей коммерческих сайтов. В основу известного метода положена схема выставления приоритетов пользователям в зависимости от длины их сессий и суммах, накопленных в электронных корзинах. Применение данной схемы в периоды пиковых нагрузок может привести к увеличению финансовой пропускной способности ЦОД до 30% за счет предоставления лучшего качества обслуживания активным, т.е. делающим покупки пользователям. Однако в литературе величину длительности сессии, начиная с которой следует снижать приоритеты пользователям, предлагается определять экспериментальным путем, что может занять продолжительное время и ограничивает применение данного метода в периоды пиковых нагрузок. Поэтому во второй главе предложен альтернативный подход к определению момента снижения приоритетов, путем нахождения аналитического выражения плотности распределения вероятностей длительности сессий и задания вероятности того, что длительность сессии не превысит величины, характеризующей долю активных и пассивных пользователей на сайте.

Плотность распределения вероятности длительности сессий определялась через распределения таких случайных величин, как число поступивших сессий за заданный промежуток времени и число элементарных запросов в сессиях. Обработка статистических данных, представленных в журналах регистрации запросов коммерческих сайтов, показала, что эмпирические распределения числа поступивших сессий за определенный промежуток времени могут быть аппроксимированы законом Пуассона, а числа элементарных запросов в сессиях—логарифмически нормальным законом. Причем длительность элементарного запроса определялась как сумма минимальной длительности загрузки страницы и минимального времени на обдумывание, т.е. времени, прошедшего с момента передачи ответа на запрос пользователю \УеЬ-сервером и до поступления нового запроса на сервер от этого же пользователя.

Выражение, связывающее длительность сессии т, с относительным числом элементарных запросов X и количеством сессий N за период наблюдения Г, имеет вид: N !>,.

Х = (21)

к-Т

где к = — постоянный для данного сайта коэффициент; т0

— длительность элементарного запроса; То — минимальный период наблюдения за реализацией пользовательских сессий.

Используя допущения о том, что длительности сессий, инициируемых различными пользователями, распределены одинаково и независимо, а также не зависят от общего числа сессий за период Т, найдено выражение, связывающее характеристическую функцию числа элементарных запросов <p(t) с характеристической функцией длительности сессий <p\(t), имеющее следующий вид:

(p{t) = е kt , (22)

где X—интенсивность поступления сессий.

Известно, что закон распределения случайной величины может быть представлен рядом Эджворта, первые четыре члена которого составляют А-ряд Шарлье. После выражения начальных моментов распределения относительной длительности сессий через характеристическую функцию числа элементарных запросов, было получено следующее приближенное выражение плотности распределения вероятностей относительной длительности сессий:

3<¡¡¡2 2а,3 i4-3ij: 4a,i3 6a,2s, _3а,4

6 fs. a?Y- 24

л л2 л3_

л

(23)

Д г) = 0,5 + 0,5Ф(г) - ¿^ • —4—+

а£ '

'л2

где г=К1 ^ ;

ъ . _

—~ — относительная длительность г-ои сессии; кТ

.5,, ¿3, — оценки второго, третьего и четвертого центральных моментов распределения числа элементарных запросов;

¿г, — оценка первого начального момента распределения числа элементарных запросов;

А — оценка первого начального момента распределения числа сессий; а,

Д = -4- — оценка первого начального момента распределения относитель-А

ной длительности сессий; . 52 «I2

= —---- — оценка второго центрального момента распределения

Л Л"

относительной длительности сессий. При больших интенсивностях потоков, характерных для крупных сайтов, а также в периоды пиковых нагрузок, значение параметра логарифмически нормального закона распределения числа элементарных запросов а не

превышает 0,1. Данное обстоятельство позволило аппроксимировать логарифмически нормальное распределение нормальным законом. Используя данное предположение, было получено приближенное выражение плотности вероятности длительности сессий, которое позволило по заданной вероятности определить момент снижения приоритетов.

В третьей главе проведен анализ подходов и методов многокритериальной оптимизации с целью выбора метода решения поставленных задач с учетом предметной области. В качестве такого метода выбран метод последовательных уступок. Алгоритм данного метода предусматривает многократное решение задачи при различных величинах уступки, что приводит к относительно большому времени поиска оптимального решения и является основным недостатком этого метода, ограничивающим его применение для оптимизации распределения ресурсов в периоды пиковых нагрузок. Поэтому для эффективного использования метода последовательных уступок как в нормальном режиме эксплуатации ЦОД, так и в периоды пиковых нагрузок, предложен алгоритм одноэтапного определения уступки на основе задаваемого вектора предпочтений.

Процесс решения задачи оптимизации распределения ресурсов ЦОД модифицированным методом последовательных уступок состоит из следующих этапов.

1. На первом этапе задается вектор предпочтений частных критериев:

р = {/>,: р, > 0 V/ = 1 ,...,М , = 1}, (24)

где р,—коэффициент предпочтения г-го критерия (;'= 1,..., М). Производится упорядочение 1фитериев по важности, т.е. критерию с большим коэффициентом предпочтения присваивается первый номер.

2. На втором этапе решается следующая последовательность подзадач:

2.1. Найти максимальные и минимальные значения для каждого критерия в отдельности:

гг'"= пипад, гГ'= тах2,(х), г = \,...,М. (25)

хеХ хеЛ'

2.2. Найти минимальные взвешенные относительные потери (отклонения) частных критериев от своих оптимальных значений ко""".

Для этого критерии приводятся к безразмерному виду с применением монотонных преобразований а>(х):

утих у / ч

ш,{х) = сотх))= ^ £¿,1-1, ...,М. (26)

После этого V" находится решением следующей задачи оптимизации:

ттк0=Хп+] (27)

х

при ограничениях

xeX ,pi <y,(x)-x„+i<0, i= I,..., M. 3. На третьем этапе задача решается в соответствии с алгоритмом метода последовательных уступок, где величина компромиссной уступки определяется следующим образом: .min

4,ол,„р= io_(Zmax1. (28)

Pi

Оптимальное (компромиссное) решение задачи распределения ресурсов ЦОД и соответствующее ему значения критериев — результат решения последней задачи из следующей последовательности подзадач:

3.1. найти Z™M"P — maxZ2(x) при ограничениях (29)

х

¿.min

X6х, z,(x)> z,max (z,max -zrn); P\

3.2. найти Z^m'np = maxZ3(x) при ограничениях (30)

jumin

xeZ, Zj(x) > Z,max -(Z™ ~г,™), Pi

■ min "fl

Z2 (x) > Zf •- (Z2raax - Z2mln ); Pi

З.М. найти ZT"P = maxZM(x) при ограничениях (31)

X

fcif™

x e X, Z, (x) > Z,max - (Z,max - zrm ), Pi

zr (x) > zr™' - (z,max-z™n),r=2,3,...,A/-1,

Pr

где Z,max — максимальное значение г'-го критерия, i = 1,..., М- 1; Z/"m — минимальное значение /-го критерия, / = 1,..., М - 1; Pi — коэффициент предпочтения ;'-го критерия,; = 1,..., М -1;

7 min

«о — одинаковые минимальные взвешенные относительные отклонения критериев от своих оптимальных значений. Схема предлагаемого алгоритма приведена на рис. 1.

Рис. 1. Алгоритм модифицированного метода последовательных уступок.

Кроме этого в третьей главе выполнено теоретическое обоснование приведенной модификации метода последовательных уступок, включающее лемму и две теоремы, вывод которых сделан при условии, что М непрерывно дифференцируемых частных критериев попарно противоречивы и множество допустимых решений задачи выпукло.

Проведено сравнение трудоемкости предложенного и традиционного алгоритмов метода последовательных уступок с различным числом критериев. Показано, что предложенная модификация метода последовательных уступок в несколько раз сокращает время получения оптимального решения по сравнению с традиционным методом, в частности, в 2 раза для двух критериев, в 2,5 раза для трех критериев и в 3 раза для четырех критериев.

Модифицированный метод последовательных уступок реализован программно и зарегистрирован в реестре программ для ЭВМ.

Четвертая глава посвящена разработке методики оптимизации распределения ресурсов центров обработки данных и вопросам ее практической реализации. Из анализа системы БЬА-соглашений известно, что данное множество может быть разделено на две большие группы. В первую входят 8ЬА-соглашения без разделения запросов на классы, а во вторую — с разделением. Поэтому в работе разработаны методики оптимизации распределения серверов по кластерам для этих двух групп БЬА-соглашений.

Методика оптимизации распределения ресурсов ЦОД без разделения запросов на классы состоит из ряда этапов, представленных на рис. 2.

;' 1. Определение среднего времени обработки запроса слабозагруженным сервером кластера с (тТс), с = 1.....С.

2. Определение интенсивности поступления запросов (Лс) в кластер с, с — 1.....С.

.т

! 3. Определение оптимального среднего времени ответа гю ЗЬА-соглашениям

4. Задание вектора предпочтений частных критериев: р = {/>], р2 }■ Расчет числа серверов (5С) в кластере с, с = 1.....С.

Рис. 2. Методика расчета оптимального числа серверов в кластерах без разделения запросов на классы.

На первом этапе при малых величинах нагрузки путем обработки журналов регистрации запросов или с помощью существующих программ по администрированию серверов определяется среднее время обработки запроса сервером в каждом кластере. На втором этапе определяется интенсивность поступления запросов в каждый кластер серверов. На основе анализа БЬА-соглашений на третьем этапе определяется требуемое среднее время ответа на запрос. Если в 8ЬА-соглашениях выделены уровни обслуживания, то определяется оптимальное среднее время ответа путем решения задачи (19-20). На последнем четвертом этапе задаются коэффициенты предпочтения критериям пропускной способности и совокупной стоимости владения р = {ри /%}, после чего с применением модифицированного метода последовательных уступок производится расчет числа серверов в кластерах с использованием модели (1-4). Если в 8ЬА-соглашениях задается также ограничение на максимальное время ответа для заданной доли запросов, то расчет числа серверов в кластерах производится с использованием модели (5-8).

Методика оптимизации распределения ресурсов ЦОД с разделением запросов на классы также состоит из ряда этапов, представленных на рис. 3.

ТГ1. Анализ §1_А-

ГПГПЯ1 мяимй

1.2. Установка соответствия

Определение матрицы вероятностей переходов запроса класса к меяаду кластерами ()

между классами : запросов и —| |

1.3. Обработка журналов регистрации запросов серверов

. .... . ¡'9Ш

Определение среднего времени обработки

) запроса класса к сервером кластера с{тс) Определение матрицы I вероятностей появления ; запроса класса к' после

обработки запроса

класса к (р^ ^

/

2. Обработка журналов регистрации запросов серверов. Определение интенсивностей поступления запросов класса к в кластер с (¿с ).

3. Задание вектора предпочтений частных критериев: р - {Р\, Рг }■ Расчет оптимального числа серверов в кластерах (8С).

Рис. 3. Методика расчета оптимального числа серверов в кластерах с разделением запросов на классы.

На первом этапе исходя из анализа SLA-соглашений определяется число сессий J, которое равно числу сайтов, а также число классов запросов К. Каждому классу запросов ставится в соответствие НТТР-запрос (URL) или группа НТТР-запросов. Определяется матрица вероятностей переходов р'с, с, запроса класса к

(к, = 1,..., К) между кластерами С/ и с} (/' = 1, ..., С, j = 1, ..., С,), поскольку в обработке запроса класса к могут быть по несколько раз задействованы различные компоненты приложения (Web-сервер, сервер приложений, сервер баз данных). Затем определяется среднее время обработки запроса класса к сервером кластера с при малых величинах нагрузки тДля определения интенсивности поступления запросов различных классов из сессии j(j= 1, ...,J) необходимо найти вероятности переходов пользователей по страницам сайтов pJk,k. Для этого строится граф, каждому узлу которого соответствует определенное состояние пользователя на сайте (Просмотр, Поиск и др.). Каждому переходу между узлами графа соответствует вероятность, которая определяется путем обработки журналов регистрации запросов серверов, для чего был разработан соответствующий алгоритм.

На втором этапе с целью нахождения интенсивности поступления запросов класса к в кластер с, определяются следующие параметры:

• интенсивность поступления сессии на сайт j (/,);

• интенсивность поступления запросов класса к из сессии j (\Jk):

к

К = I К'Рк'к + 0 > к = 1, ...,К, 7=1.....j\ (32)

¿'=1

• интенсивность поступления запросов класса к из всех сессий (Хк)'.

= (33)

7=1

• интенсивность поступления запросов класса к в кластер с (А^) определяется решением системы линейных уравнений:

Xj = X Х2Р2 1 х\ = xfpj'j + Х3 Рз2 = X2p2i3 + Х4Р43

\ k _ 1 к -к лс _ Ac-iPc-i,c

На последнем этапе с использованием метода ранжирования задаются коэффициенты предпочтения критериям пропускной способности и совокупной стоимости владения р - {р\, pi}. Затем с применением модифицированного метода последовательных уступок производится расчет числа серверов в кластерах с использованием модели (10-13), если также задается ограничение на

максимальное время ответа для заданной доли запросов, то расчет числа серверов в кластерах производится с использованием модели (14-17).

В связи с тем, что в стандартных журналах регистрации запросов \Veb-серверов сессии явно не отражаются, то для получения параметров сессий разработан и программно реализован алгоритм выделения сессий из журналов регистрации запросов.

Также в четвертой главе разработаны рекомендации по получению плотности вероятности длительности сессий, используемой для обоснования выставления приоритетов пользователям коммерческих сайтов в предложенном методе управления доступом. В частности, приведены рекомендации по определению параметров законов распределений числа сессий и числа элементарных запросов, а также параметров их зависимостей от времени наблюдения.

Предложенная методика оптимизации распределения ресурсов ЦОД может быть реализована программно и включена в контур оперативного управления ресурсами ЦОД.

В заключении приведены основные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана модель оптимизации среднего времени ответа по группе ЭЬА-соглашений с выделением уровней обслуживания, позволяющая найти среднее время ответа, используемое в качестве входного параметра задачи нахождения оптимального числа серверов в кластерах ЦОД без разделения запросов на классы.

2. Разработаны модели оптимизации распределения ресурсов центров обработки данных как без разделения, так и с разделением запросов на классы, позволяющие найти оптимальное число серверов в кластерах ЦОД для БЬА-соглашений, в которых задаются ограничения на среднее время ответа и максимальное время ответа для заданной доли запросов.

3. Путем обработки статистики посещений коммерческих сайтов установлено, что число сессий распределено по закону Пуассона, а число элементарных запросов в сессии подчинено логарифмически нормальному закону.

4. Получено приближенное аналитическое выражение для плотности распределения вероятностей длительности сессий на основе соотношения между характеристическими функциями числа элементарных запросов и длительности сессий.

5. Усовершенствован метод управления доступом пользователей к коммерческим сайтам, позволяющий повысить финансовую пропускную способность сайтов в периоды пиковых нагрузок до 30% и по сравнению с известным методом исключающий необходимость проведения случайного

числа экспериментов по определению момента снижения приоритетов пользователям.

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

7. Предложен модифицированный метод последовательных уступок, сокращающий по сравнению с традиционным методом последовательных уступок время нахождения оптимального решения в несколько раз, в зависимости от числа используемых критериев оптимизации, что позволяет использовать его в контуре оперативного управления ресурсами как в нормальном режиме функционирования центров обработки данных, так и в периоды пиковых нагрузок.

8. Разработаны рекомендации по формированию систем ограничений и критериев поставленных задач, позволяющие найти входные параметры для оптимизации распределения ресурсов центров обработки данных.

9. Разработаны и программно реализованы алгоритмы по определению компромиссной величины уступки в предложенном модифицированном методе последовательных уступок, а также по обработке журналов доступа Web-серверов, позволяющие реализовать методику оптимизации распределения ресурсов центров обработки данных.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Тутова Н.В. Методика оптимизации ресурсов центров обработки данных в сети Интернет // T-comm: Телекоммуникации и транспорт. - 2008. - №6. -

С. 44-46.

2. Ворожцов A.C., Тутова Н.В. Повышение финансовой пропускной способности центров обработки данных в сети Интернет // Естественные и технические науки. - 2008. - №6. - С. 262-266.

3. Ворожцов A.C., Тутова Н.В. Тенденции развития и проблемы повышения эффективности сетей электронного бизнеса // Международный форум информатизации (МФИ-2006): Труды конференции «Телекоммуникационные и вычислительные системы». - М.: МТУСИ, 2006 - С. 237.

4. Тутова Н.В., Ворожцов A.C. Модели оптимизации технологий обработки данных в сетях электронного бизнеса // Труды Московского технического университета связи и информатики. - М.: «ИД Медиа Паблишер», 2007. -

С. 249-254.

5. Тутова Н.В., Ворожцов A.C. Методика оценки оптимальных параметров качества центров электронной коммерции // Международный форум информатизации (МФИ-2007): Труды конференции «Телекоммуникационные и вычислительные системы». - М.: МТУСИ, 2007 - С. 74-75.

6. Ворожцов A.C., Тутова H.B. Оптимизация ресурсов центров обработки данных в сетях электронного бизнеса // Труды Московского технического университета связи и информатики: - М.: «ИД Медиа Паблишер», 2008. -Т.1.-С.133-136.

7. Ворожцов A.C., Тутова Н.В. Оптимальное распределение ресурсов центров обработки данных в сетях электронного бизнеса // Труды XVI международной научно-технической конференции «Информационные средства и технологии»,-М.: Издательский дом МЭИ, 2008. -Т. 1- С. 71-77.

8. Ворожцов A.C., Тутова Н.В. Об одном методе повышения доходности web-узлов электронного бизнеса // Международный форум информатизации (МФИ-2008): Труды конференции «Телекоммуникационные и вычислительные системы». - М.: МТУСИ, 2008. - С. 308.

9. Ворожцов A.C., Тутова Н.В. Методика повышения доходности web-узлов в периоды пиковых нагрузок // Международный форум информатизации (МФИ-2008): Труды конференции «Телекоммуникационные и вычислительные системы». - М.: МТУСИ, 2008. - С. 310.

Ю.Тутова Н.В. Практическая реализация технологии оптимизации ресурсов центров обработки данных в сетях электронного бизнеса // Международный форум информатизации (МФИ-2008): Труды конференции «Телекоммуникационные и вычислительные системы». - М.: МТУСИ, 2008-С. 309.

11 .Свидетельство о государственной регистрации программы для ЭВМ №2009610173 (Россия). «Программа для решения линейных многокритериальных задач оптимизации модифицированным методом последовательных уступок» / Тутова Н.В., Ворожцов A.C. Правообладатель ГОУ ВПО МТУСИ //Зарегистрировано в Реестре программ для ЭВМ 11 января 2009г., заявка №2008614859 от 23 октября 2008 г.

Подписано в печать 02.02.09. Формат 60x84/16. Объем 1,4 усл.п.л.

_Тираж 100 экз. Заказ 40._

ООО «Инсвязьиздат». Москва, ул. Авиамоторная, 8.

Введение.

Глава 1. Анализ проблем повышения эффективности управления ресурсами центров обработки данных в сети Интернет.

1.1. Основные понятия и тенденции развития сети Интернет.

1.1.1. Основные тенденции.

1.1.2. Кластерная обработка данных.

1.1.3. Хостинг.

1.1.4. Соглашения о качестве обслуживания.

1.2. Сложность современных Интернет-приложений.

1.2.1. Многозвенная архитектура Интернет-приложений.

1.2.2. Характеристика нагрузки ЦОД.

1.3. Проблемы управления ресурсами центров обработки данных.

1.3.1. Проблема планирования и распределения ресурсов ЦОД.

1.3.2. Проблема управления доступом пользователей в периоды пиковых нагрузок.

1.3.3. Проблема выполнения SLA-соглашений.

1.4. Постановка задачи исследования.

Глава 2. Постановки задач оптимизации распределения ресурсов центров обработки данных в сети Интернет.32 f

2.1. Разработка моделей массового обслуживания в центрах обработки данных в сети Интернет.

2.1.1. Модель массового обслуживания в центрах обработки данных без разделения запросов на классы.

2.1.2. Модель массового обслуживания в центрах обработки данных с учетом сессий и классов запросов.

2.2. Математические постановки задач оптимального распределения ресурсов центров обработки данных.

2.2.1. Математическая постановка задачи нахождения оптимального среднего времени ответа по SLA-соглашениям.

2.2.2. Выбор критериев оптимизации.

2.2.3. Математическая постановка задачи оптимизации распределения ресурсов центров обработки данных без разделения запросов на классы

2.2.4. Математическая постановка задачи оптимизации распределения ресурсов центров обработки данных с разделением запросов на классы

2.3. Управление доступом пользователей к ресурсам ЦОД.

2.3.1. Модель поведения пользователей коммерческих сайтов.

2.3.2. Определение плотности распределения вероятностей длительности сессий.

2.3.3. Схема выставления приоритетов пользователям коммерческих сайтов.

2.4. Выводы.

Глава 3. Выбор метода, разработка алгоритмов и программного обеспечения оптимизации распределения ресурсов центров обработки данных в сети Интернет.

3.1. Анализ подходов и методов решения многокритериальных задач принятия решений.

3.2. Выбор метода решения задач многокритериальной оптимизации распределения ресурсов центров обработки данных.

3.2.1. Разработка требований к методу решения задач оптимизации распределения ресурсов центров обработки данных.

3.2.2. Преимущества и недостатки метода ограничений.

3.2.3. Преимущества и недостатки метода последовательных уступок

3.3. Теоретическое обоснование процедуры определения компромиссной уступки.

3.4. Процедура определения компромиссной уступки.

3.5. Исследование модифицированного метода последовательных уступок для оптимизации распределения ресурсов центров обработки данных.

3.5.1. Сравнение трудоемкости алгоритмов.

3.6. Программная реализация модифицированного метода последовательных уступок.

3.7. Выводы.

Глава 4. Практическая реализация методики оптимизации распределения ресурсов центров обработки данных в сети Интернет.

4.1. Рекомендации по проведению анализа соглашений о качестве обслуживания.

4.1.1. Выделенный хостинг.

4.1.2. Совместный хостинг.

4.2. Методики определения оптимального числа серверов в кластерах.

4.2.1. Методика определения оптимального числа серверов без разделения запросов на классы.

4.2.2. Методика определения оптимального числа серверов с разделением запросов на классы.

4.3. Выбор метода задания коэффициентов предпочтения критериев многокритериальных задач.

4.4. Рекомендации по обработке статистики.

4.4.1. Процедура получения сессий из журналов регистрации запросов Web-серверов.

4.4.2. Процедура получения матрицы вероятностей переходов пользователей по страницам сайта.

4.5. Практическая реализация метода управления доступом пользователей коммерческих сайтов.

4.5.1. Определение параметров плотности распределения вероятностей длительности сессий.

4.5.2. Определение момента снижения приоритетов.

4.6. Выводы.

Актуальность работы. Современный этап развития глобальной сети Интернет характеризуется трансформацией традиционных услуг и бизнес-процессов компаний в электронные, основанные на Web-технологиях, что привело к появлению широкого спектра систем электронного бизнеса, которые стали ключевыми в успехе работы компаний и поддержке их конкурентоспособности. Практически все крупные операторы связи и сервис-провайдеры стали оказывать услуги хостинга в центрах обработки данных (ЦОД), которые предоставляют физические ресурсы для размещения серверов и высокоскоростной доступ в Интернет. Современный процесс предоставления услуг компаниями, владеющими коммерческими ЦОД, характеризуется появлением соглашений о качестве обслуживания (Service Level Agreement—SLA), гарантирующих определенный уровень показателей качества, таких как среднее время ответа на запрос пользователя, максимальное время ответа для заданной доли запросов, коэффициент готовности и др.

Интенсивность запросов к Интернет-приложениям значительно меняется в течение суток, а в периоды пиковых нагрузок, возникающих в случайные моменты времени, может возрастать в несколько раз. Известно также, что в такие периоды значительно уменьшается число электронных платежей в единицу времени, которое в зарубежной литературе называют финансовой пропускной способностью (Revenue Throughput). Центры обработки данных в сети Интернет имеют многозвенную архитектуру, включающую в себя кроме Web-серверов, кластеры серверов приложений и серверов баз данных, число которых может достигать сотен и тысяч. Поэтому выполнение SLA-соглашений является сложной задачей, прямо влияющей на конкурентоспособность компаний. Одним из путей ее решения является оптимальное распределение серверов по кластерам и поиск более эффективного метода управления доступом пользователей к этим ресурсам в периоды пиковых нагрузок.

Современной тенденцией является увеличение числа показателей качества задаваемых в SLA-соглашениях, удовлетворение которых приводит к необходимости использования многокритериального подхода, теория которого развита такими отечественными учеными как Подиновский В.В., Ногин В.Д., Михалевич B.C., Волкович В.Л., Батищев Д.И и др.

Проблема оптимизации распределения ресурсов ЦОД рассматривалась в работах зарубежных ученых Menasce D., Almeida V. и др. Однако в существующих работах оптимизация проводилась по одному критерию для узкого класса SLA-соглашений. Отсутствует методика распределения ресурсов ЦОД, работающих по SLA-соглашениям различных видов, которая включала бы в себя определение оптимального числа серверов в кластерах по нескольким критериям и эффективный метод управления доступом, позволяющий повысить финансовую пропускную способность ЦОД. Поэтому тема диссертационной работы является актуальной.

Цель работы и задачи исследования. Целью диссертационной работы является разработка методики оптимизации распределения ресурсов центров обработки данных по нескольким критериям и обеспечения эффективного управления доступом пользователей к этим ресурсам в периоды пиковых нагрузок.

Для достижения поставленной цели в диссертационной работе решены следующие задачи:

1. Проведен анализ системы соглашений о качестве обслуживания. Сформулирована постановка задачи определения оптимального среднего времени ответа по соглашениям о качестве обслуживания.

2. Выбраны и разработаны модели центров обработки данных в сети Интернет, отражающих особенности их функционирования.

3. Разработаны математические модели распределения ресурсов центров обработки данных по нескольким критериям для различных видов соглашений о качестве обслуживания.

4. Выбран метод многокритериальной оптимизации распределения ресурсов центров обработки данных в сети Интернет, позволяющий получить оптимальный план размещения серверов не только для длительного времени повышения интенсивности потока запросов, но и в короткие периоды пиковых нагрузок.

5. Разработан алгоритм решения задачи многокритериальной оптимизации распределения ресурсов центров обработки данных.

6. Разработан метод управления доступом пользователей коммерческих сайтов в периоды пиковых нагрузок.

7. Разработаны рекомендации и процедуры практической реализации методики оптимизации распределения ресурсов центров обработки данных.

Методы исследования. Для решения поставленных задач использованы методы многокритериальной оптимизации, теории вероятностей и математической статистики, теории массового обслуживания.

Научная новизна работы состоит в разработанной методике оптимизации распределения ресурсов центров обработки данных в сети Интернет, включающей в себя:

1. Модели оптимизации распределения ресурсов центров обработки данных для соглашений о качестве обслуживания как с разделением, так и без разделения запросов на классы, в которых в отличие от известных моделей для оптимального распределения ресурсов используется многокритериальный подход;

2. Модифицированный метод последовательных уступок, сокращающий в зависимости от числа используемых критериев оптимизации в несколько раз время нахождения оптимального решения по сравнению с традиционным методом последовательных уступок, что позволяет использовать его в контуре оперативного управления ресурсами как в нормальном режиме функционирования центров обработки данных, так и в периоды пиковых нагрузок;

3. Усовершенствованный метод управления доступом к коммерческим сайтам, позволяющий повысить финансовую пропускную способность сайтов в периоды пиковых нагрузок до 30% и по сравнению с известным методом исключает необходимость проведения случайного числа экспериментов по определению момента снижения приоритетов пользователям.

Практическая ценность и реализация результатов работы:

1. Разработанная методика оптимизации ресурсов центров обработки данных позволяет найти оптимальное число серверов в кластерах в зависимости от нагрузки и обеспечить заданный в SLA-соглашениях уровень качества.

2. Программно реализована процедура определения компромиссной уступки, которая положена в основу предложенного модифицированного метода последовательных уступок, позволяющая сократить время решения задачи как минимум в два раза.

3. Разработаны алгоритмы по обработке журналов регистрации запросов с целью получения параметров пользовательских сессий и рекомендации по формированию критериев и систем ограничений задач оптимизации распределения ресурсов центров обработки данных, что позволяет реализовать разработанную методику.

4. Усовершенствован метод управления доступом пользователей к коммерческим сайтам, исключающий необходимость проведения случайного числа экспериментов по определению момента снижения приоритетов пользователям.

Результаты диссертационной работы используются в учебном процессе МТУСИ. Алгоритм расчета оптимального числа серверов используется в текущей деятельности Интернет-провайдера ООО «НФС Телеком», что подтверждено соответствующим актом.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях: международной научно-технической конференции «Телекоммуникационные и вычислительные системы», Москва, 2006 г., 2007 г., 2008 г., московской отраслевой научно-технической конференции «Технологии информационного общества, Москва, 2007 г., 2008 г., международной конференции «Информационные средства и системы», Москва, 2008 г.

Публикации. По теме диссертационной работы опубликовано 10 печатных работ (из них 2 статьи в ведущих рецензируемых научных журналах из перечня, рекомендованного ВАК). Получено свидетельство об официальной регистрации программы для ЭВМ.

Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка использованных источников и приложения. Работа содержит 170 страниц машинописного текста, содержит 36 рисунков и 20 таблиц. В списке используемой литературы 107 наименований.

4.6. Выводы

1. Разработана методика проведения анализа соглашений о качестве обслуживания для выделенного и совместного хостинга, позволяющая определить максимальное допустимое среднее время ответа на запрос в ЦОД для различных видов SLA-соглашений.

2. Разработаны методики оптимизации распределения серверов по кластерам в зависимости от нагрузки, позволяющие обеспечить заданный в SLA-соглашениях уровень качества для SLA-соглашений как без разделения, так и с разделением запросов на классы.

3. Разработаны рекомендации по формированию критериев и систем ограничений задач оптимизации числа серверов в кластерах, позволяющие найти входные параметры разработанных моделей ЦОД и тем самым реализовать методику оптимизации распределения ресурсов.

4. В качестве метода задания коэффициентов предпочтения частным критериям оптимизации выбран метод ранжирования.

5. Разработаны и программно реализованы алгоритмы по обработке журналов регистрации запросов серверов, что позволяет реализовать методику оптимизации распределения ресурсов ЦОД, в том числе в контуре оперативного управления.

6. Разработаны рекомендации по определению параметров законов распределений числа сессий и числа элементарных запросов, получению на их основе приближенного выражения плотности распределения вероятностей длительности сессий, а также по определению момента снижения приоритетов в методе управления доступом пользователей к коммерческим сайтам.

Заключение

Исследования, приведенные в диссертации, посвящены вопросам оптимального распределения ресурсов центров обработки данных в сети

Интернет. Основные результаты исследований заключаются в следующем:

1. Разработана модель оптимизации среднего времени ответа по группе SLA-соглашений с выделением уровней обслуживания, позволяющая найти среднее время ответа, используемое в качестве входного параметра задачи нахождения оптимального числа серверов в кластерах ЦОД без разделения запросов на классы.

2. Разработаны модели оптимизации распределения ресурсов ЦОД без разделения и с разделением запросов на классы, позволяющие найти оптимальное число серверов в кластерах ЦОД для SLA-соглашений, в которых задаются ограничения на среднее время ответа и максимальное время ответа для заданной доли запросов, без разделения и с разделением запросов на классы.

3. Путем обработки статистики посещений коммерческих сайтов установлено, что число сессий распределено по закону Пуассона, а число элементарных запросов в сессии подчинено логарифмически нормальному закону.

4. Получено приближенное аналитическое выражение для плотности вероятности длительности сессий на основе соотношения между характеристической функцией числа элементарных запросов и характеристической функцией длительности сессии.

5. Усовершенствован метод управления доступом пользователей к коммерческим сайтам, позволяющий повысить финансовую пропускную способность сайтов в периоды пиковых нагрузок до 30% и по сравнению с известным методом исключает необходимость проведения случайного числа экспериментов по определению момента снижения приоритетов пользователям.

6. Предложена и теоретически обоснована модификация процедуры определения компромиссной уступки, основанная на использовании коэффициентов предпочтений частных критериев в качестве априорной информации о предпочтениях ЛПР.

7. Предложен модифицированный метод последовательных уступок, сокращающий по сравнению с традиционным методом последовательных уступок время нахождения оптимального решения в несколько раз, в зависимости от числа используемых критериев оптимизации, что позволяет использовать его в контуре оперативного управления ресурсами как в нормальном режиме функционирования центров обработки данных, так и в периоды пиковых.

8. Разработаны рекомендации по формированию систем ограничений и критериев поставленных задач, позволяющие найти входные параметры для оптимизации распределения ресурсов центров обработки данных.

9. Разработаны и программно реализованы алгоритмы по определению компромиссной величины уступки в предложенном модифицированном методе последовательных уступок, а также по обработке журналов доступа Web-серверов, позволяющие реализовать методику оптимизации распределения ресурсов центров обработки данных.

1. Абезгауз Г.Г., Тронь А.П., Копенкин Ю.Н., Коровина И.А. Справочник по вероятностным расчетам.—М.: Воениздат, 1966.

2. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов: основы теории. — М.: Наука, 1990.

3. Алексунин В.А., Электронная коммерция и маркетинг в Интернет, 2007.

4. Анохин А. М., Глотов В. А., Павельев В.В., Черкашин A.M. Методы определения коэффициентов важности критериев. Автоматика и телемеханика, №8, 1997—С.3-35.

5. Батищев Д.И. Методы оптимального проектирования. — М.:Радио и связь, 1984. —248 с.

6. Батищев Д.И., Шапошников Д.Е., Многокритериальный выбор с учетом индивидуальных предпочтений — ИПФ РАН. Нижний Новгород, 1994. — 92 с.

7. Батищев Д.И., Шапошников Д.Е. Решение многокритериальных задач методом идеальной точки // Модели и алгоритмы оптимизации в автоматизированных системах. Воронеж, ВПИ, 1989 - С.48-53.

8. Бенайюн Р., Ларичев О.И., Де Монгольфье Ж., Терни Ж. Линейное программирование с многими критериями. Метод ограничений. // Автоматика и телемеханика, 1971, №8—С. 103-115.

9. Борисов А.Н., Вилюмс Э.Р., Сукур Л .Я. Диалоговые системы принятия решений на базе мини-ЭВМ: Информационное, математическое и программное обеспечение. — Рига: Зинатне, 1986 195 с.

10. Ю.Борисов А.Н., Левченков А.С. Методы интерактивной оценки решений.— Рига: Зинатне, 1982 139 с.

11. Вентцель Е.С. Введение в исследование операций. — М.:Советское радио, 1964.

12. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. —М.:Радио и связь, 1981. — 328 с.

13. Вол один Б.Г.и др. Сборник задач по теории вероятностей, математической статистики и теории случайных функций. — М.: «Наука», 1965.

14. М.Ворожцов А.С., Тутова Н.В. Методика повышения доходности web-узлов в периоды пиковых нагрузок // Тезисы докладов конференции «Телекоммуникационные и вычислительные системы» Международной Академии информатизации, М.: МТУСИ. - 2008. - С. 310.

15. Ворожцов А.С., Тутова Н.В. Об одном методе повышения доходности web-узлов электронного бизнеса // Тезисы докладов конференции «Телекоммуникационные и вычислительные системы» Международной Академии информатизации, М.: МТУСИ. - 2008. - С. 308.

16. Ворожцов А.С., Тутова Н.В. Оптимальное распределение ресурсов центров обработки данных в сетях электронного бизнеса // Труды XVI МНТК «Информационные средства и технологии». Том 1. М.: Издательский дом МЭИ. - 2008. - С. 71 - 77.

17. Ворожцов А.С., Тутова Н.В. Оптимизация ресурсов центров обработки данных в сетях электронного бизнеса // Московская отраслевая научно-техническая конференция «Технологии информационного общества»: Тез. докл. М.: Инсвязьиздат. - 2007. - С. 194.

18. Ворожцов А.С., Тутова Н.В. Оптимизация ресурсов центров обработки данных в сетях электронного бизнеса // Труды Московского технического университета связи и информатики: -М.: «ИД Медиа Паблишер», 2008. -Т.1.-С. 133-136.

19. Ворожцов А.С., Тутова Н.В. Повышение финансовой пропускной способности центров обработки данных в сети Интернет // Естественные и технические науки. 2008. - №6. - С. 262-266.

20. Воронцов Ю.А. Технико-экономическое обоснование эффективности проектов информационных систем. —М.: Инсвязьиздат, 2008. —367 с.

21. Воронцов Ю.А., Бобков А.Е. Многокритериальная оптимизация параметров информационных систем// Труды Московского технического университета связи и информатики: — М.: «ИД Медиа Паблишер», 2008. — Т.1.-С. 154-158.

22. Гермейер В.Б. Введение в теорию исследования операций. — М.: Наука, 1971.—383 с.

23. Даргейко Л.Ф. Метод ограничений в линейных задачах векторной оптимизации. // Кибернетика и вычислительная техника, №13, 1986—С. 87-93.

24. Джоффрион А., Дайер Дж., Файнберг А. Решение задач оптимизации при многих критериях на основе человеко-машинных процедур // Вопросы анализа и процедуры принятия решений. — М.:Мир, 1976. — С.126-145.

25. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. —М.:Наука, 1982.

26. Емельянов С.В., Наппельбаум Э.Л. Логика рационального выбора // Техническая кибернетика. — М.: ВИНИТИ, 1977. —Т. 8. —С. 5-101.

27. Жуковин B.C. Модели и процедуры принятия решений. — Тбилиси: Мецниереба, 1981.- 118 с.29.3уховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. — М., 1964.

28. Кини Р.Л., Райфа X. Принятие решения при многих критериях: замещения и предпочтения / Пер. с англ. — М.: Радио и связь, 1981. 560 с.

29. Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979.

30. Клейнрок Л. Вычислительные системы с очередями. — М.: Машиностроение, 1979.

31. Краснощеков П.С. Математические модели в исследовании операций. — М.:Наука, 1984.

32. Ларичев О.И. Объективные модели и субъективные решения. М.:Наука, 1987, — 144 с.

33. Макаров И.М., Виноградская Т.М., Рубчинский А.А., Соколов В.Б. Теория выбора и принятия решений. — М.: Наука, 1982 328 с.

34. Меркурьев В.В., Молдавский. Семейство сверток векторного критерия для нахождения точек множества Парето. // Автоматика и телемеханика, №1, 1979 —С. 110-121.

35. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. М.: Наука, 1982 —286 с.

36. Ногин В.Д. Обобщенный принцип Эджворта-Парето и границы его применимости // Экономика и математические методы, 2005, т. 41, № 3. — С. 128-134.

37. Пашкеев С.Д. и др. Машинные методы оптимизации в технике связи. М.: Связь, 1976.-272 с.

38. Подиновский В.В. Аксиоматическое решение проблемы оценки важности критериев в многокритериальных задачах // Современное состояние теории исследования операций / Под ред. Н.Н. Моисеева. — М.:Наука, 1979 —С.117- 145.

39. Подиновский В.В. Введение в теорию важности критериев. — М.: Физматлит, 2007. — 64 с.

40. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений // Многокритериальные задачи принятия решений. — М.: Машиностроение, 1978. С.48-92.

41. Подиновский В.В., Гаврилов В.М., Оптимизация по последовательно применяемым критериям. —М.: Советское радио, 1975 —192 с.

42. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. — М.: Физматлит, 2007.

43. Прохоров А.В., Ушаков В.Г., Ушаков Н.Г. Задачи по теории вероятностей: Основные понятия. Предельные теоремы. Случайные процессы. М.: Наука, 1986.

44. Смирнов Н.В., Дунин-Барковский И.В. Курс теории вероятностей и математической статистики для технических приложений. — М.: Наука,1965.-512 с.

45. Tax X. Введение в исследование операций. В 2-х кн. Пер. с англ. —М.: Мир 1985.

46. Тихонов В.И. Статистическая радиотехника. — М.: Советское радио,1966. -678 с.

47. Тутова Н.В. Методика оптимизации ресурсов центров обработки данных в сети Интернет. // T-comm: Телекоммуникации и транспорт, 2008, №6 — С. 44-46.

48. Тутова Н.В., Ворожцов А.С. Модели оптимизации технологий обработки данных в сетях электронного бизнеса // «Труды Московского технического университета связи и информатики». М.: МТУСИ. — 2007-С. 249 - 254.

49. Феллер В. Введение в теорию вероятностей и ее приложения. Том 1. — М.: Мир, 1964.

50. Феллер В. Введение в теорию вероятностей и ее приложения. Том 2. — М.: Мир, 1964.

51. Фишберн П.С. Теория полезности для принятия решений / Пер. с англ-М.: Наука, 1977.-352 с.

52. Штойер. Р. Многокритериальная оптимизация: теория, вычисления, приложения. — М.:Наука, 1992.

53. Экенроде Р.Т., Взвешенные многомерные критерии, книга «Статистическое измерение качественных характеристик» под ред. проф. Е.М. Четыркина. -М.:1970.

54. Abdelzaher, Т., Shin, К. G., Bhatti, N. Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach. IEEE Transactions on Parallel and Distributed Systems 13, 1 (Jan. 2002).

55. Arlitt, M., Jin, T. Workload Characterization of the 1998 World Cup Web Site. Tech. Rep. HPL-1999-35R1, HP Labs, 1999.

56. Arlitt M., Williamson C. Web server Workload Characterization: the search for invariants, in Proc. 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Philadelphia, May 1996.

57. Barford P., Crovella M. Generating Representative Web Workloads for Network and Server Performance Evaluation, in Proc. 1998 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, Madison, July 1998.

58. BEA White Paper: Evaluating Total Cost of Ownership for Application Platform Suites II, 2003 BEAHPvsIBMTCO.pdf.

59. Coello C. A., A Comprehensive survey of Evolutionary-based Multiobjective Optimization Techniques.

60. Cohon J.L. Multiojective Programming and Planning — New York: Academic Press, 1978.

61. Cecchet E., Chanda A., Elnikety S., Marguerite J., Zwaenepoel W. "A Comparison of Software Architectures for E-business Applications". In Proc. of 4th Middleware Conference, Rio de Janeiro, Brazil, June, 2003.

62. Chandra, A., Gong, W., and Shenoy, P. Dynamic Resource Allocation for Shared Data Centers Using Online Measurements. In Proceedings of Eleventh International Workshop on Quality of Service (IWQoS 2003) (June 2003).

63. Chaudhuri K., Kothari A., Swaminathan R, Tarjan R, Zhang R, Zhou Y. Server Allocation Problem for Multi-Tiered Applications, HP Laboratories Technical Report, HPL-2004-151, September 8, 2004.

64. Cherkasova, L., Phaal P. Session based admission control: a mechanism for improving performance of commercial web sites. — HP laboratories Technical Report, HPL-98-119, 1998.

65. Doyle, R., Chase, J., Asad, O., Jin, W., and Vahdat, Amin. Model-Based Resource Provisioning in a Web Service Utility. In Proceedings of the Fourth USITS (Mar. 2003).

66. Elnikety S., Nahum E., Tracey J., Zwaenepoel W. A Method for Transparent Admission Control and Request Scheduling in E-Commerce Web Sites. — 13th International Conference on World Wide Web (WWW'04) , New York, USA, 2004.—C. 276-286.

67. Fielding R., Gettys J., Mogul J., Frystyk-Nielsen H., Masinter L., Leach P., Berners-Lee Т., "RFC 2616 Hypertext Transfer Protocol - HTTP/1.1", June 1999.

68. Goodchild A. et al. Business Contracts for B2B. Proceedings of ISD 2000.

69. Greunz M. et al. Supporting Market Transaction through XML Contracting Containers. Proceedings of the Americas Conference on Information Systems (AMCIS) 2000.

70. Hamadi Y., Continuous Resources Allocation in Internet Data Centers, Microsoft Research Ltd.

71. Java 2 Platform, Enterprise Edition (J2EE). http://java.sun.com/j2ee/.

72. John H. Mathews, Kurtis D. Fink. Numerical Methods Using Matlab. 4th Edition, Prentice-Hall Inc., 2004, chap. 8.

73. Kamra, A., Misra, V., and Nahum, E. Yaksha: A Controller for Managing the Performance of 3-Tiered Websites. In Proceedings of the Twelfth IWQoS (2004).

74. Keller et al. Managing Dynamic Services: A Contract Based Approach to a Conceptual Architecture. Proceedings of NOMS 2002.

75. Kelly F. P. Reversibility and Stochastic Networks. John Wiley & Sons, New York, 1979.

76. Levy, R., Nagarajarao, J., Pacici, G., Spreitzer, M., Tantawi, A., and Youssef, A. Performance Management for Cluster BasedWeb Services. In IFIP/IEEE Eighth International Symposium on Integrated Network Management (2003), vol. 246, pp. 247-261.

77. Lin W., Liu Z., Xia С. H., Zhang L., Optimal capacity allocation for Web systems with end-to-end delay guarantees, Performance Evaluation 62 (2005), c. 400^416

78. Liu Z., Niclausse N., Jalpa-Villanueva C. Web traffic modeling and performance comparison between HTTP 1.0 and HTTP 1.1. In E. Gelenbe, editor, Systems Performance Evaluation: Methodologiesand Applications, pages 177-189. CRC Press, 2000.

79. Liu Z., Squillante M.S., Wolf J.L., Optimal Control of Resource Allocation in e-Business Environments with Strict Quality-of-Service Performance Guarantees, CDC 2002.

80. Menasce, D. A., Almeida V. A. F. CHALLENGES IN SCALING EBUSINESS SITES. Proc. 2000 Computer Measurement Group Conference, Orlando, FL, December 10-15, 2000.

81. Menasce, D. A., Almeida V. A. F., Capacity Planning for Web Performance: metrics, models, and methods, Prentice Hall, Upper Saddle River, NJ, 1998.

82. Menasce, D. A., Almeida V. A. F., Dowdy L. W., Capacity Planning and Performance Modeling: from mainframes to client-server systems, Prentice Hall, Upper Saddle River, NJ, 1994.

83. Menasce, D. A., Almeida V. A. F., Fonseca R, Mendes M. A., A Methodology for Workload Characterization of E-commerce Sites, Proc. Of ACM E-COMMERCE 99, Denver, Colorado.

84. Menasce, D. A., Almeida V. A. F., Fonseca R, Mendes M. A., Business-oriented resource management policies for e-commerce servers, Performance Evaluation 42 (2000), c. 223-239.

85. Pacifici G., Spreitzer M., Tantawi A., Youssef A., Performance Management for Cluster Based Web Services, IBM TJ Watson Research Center, TechReport, May 13, 2003.

86. Powell M.J.D. A view of algorithms for optimization without derivatives. Department of Applied Mathematics and Theoretical Physics, Cambridge, 2007.

87. Ranjan, S., Rolia, J., Fu, H., and Knightly, E. QoS-Driven Server Migration for Internet Data Centers. In Proceedings of the Tenth International Workshop on Quality of Service, Miami, FL, 2002.

88. Rolia J., Zhu X., Arlitt M., Andrzejak A. Statistical Service Assurances for Applications in Utility Grid Environments. Tech. Rep. HPL-2002-155, HP Labs, 2002.

89. Salle M., Boulmakoul A. Integrated Contract Management. Proceedings of HPOVUA Workshop2002.

90. Salle M., Bartolini C., Management by Contract, HP Laboratories, HPL-2003-186, 2004.

91. Santos, Cipriano, Xiaoyun Zhu, Harlan Crowder. 2002, A Mathematical Optimization Approach for Resource Allocation in Large Scale Data Centers, HP Laboratories Technical Report, HPL-2002-64.

92. Tophosts.com: http://www.tophosts.com/showcases/managed/.

93. Treese, G. W. and L. C. Stewart, Designing Systems for Internet Commerce, Addison Wesley, Reading, MA, 1998.

94. Urgaonkar В., Dynamic Resource Management in Internet hosting Platforms, Ph.D., University of Massachusetts Amherst, 2005

95. Voigt, Т., Tewari, R., Freimuth, D., and Mehra, A. Kernel Mechanisms for Service Differentiation in Overloaded Web Servers. — In Proceedings of USENIX Annual Technical Conference, June 2001.

96. W3C Web page, "Logging in W3C httpd", http://www.w3.org/Daemon/User/Config/Logging.html.

97. Willareal В., Karvan M.H., Zionts S. A branch and bound approach to interactive multicriteria integer linear programming // Paper presented at Joint National Meeting TIMS/ORSA Washington, D.C., 1980.

98. Zhang L., Ardagna D., SLA Based Profit Optimization in Web Systems— 13th International Conference on World Wide Web (WWW'04) , New York, USA, 2004.—pp. 462-463.

99. Zhang A., Santos P., Beyer D., Tang H.-K., Optimal Server Resource Allocation Using an Open Queueing Network Model of Response Time, HP laboratories Technical Report, HPL-2002-301, October 21, 2002.

100. Zionts S. Multiple Criteria Decision Making for Discrete Alternatives with Ordinal Criteria/ Working Paper №299, School of Management. — New York: State University of New York at Buffalo, 1977.

101. Zona Research, Inc. The Need for Speed II. Zona Market Bulletin, (5), April 2001 http://www.keynote.com/downloads/Zona Need For Speed.pdf110. http://plato.la.asu.edu/topics/problems/nlores.html