Диссертация (Математическое и программное обеспечение балансировки вычислительных заданий для распределенных вычислительных комплексов на основе прогнозных моделей), страница 7

В данном случае авторами, на основе проведённого анализапредполагается,чтовсеалгоритмыбалансировкинагрузкидляраспределённых систем можно разделить на два типа: контентно-зависимыеиконтентно-независимые.Прииспользованииконтенто-зависимыхалгоритмов балансировка нагрузки производится путём анализа содержимогозапроса, передаваемого на узел комплекса, и, в зависимости от его типа,передача происходит на тот узел системы, который обрабатывает данный типзапроса.1.4 Алгоритмы балансировки нагрузки, применяемые впромышленных системахОдними из первых разработанных и программно реализованныхалгоритмов[59,60],получившихнаибольшеераспространениевпромышленных комплексах, стали алгоритм балансировки, со случайнымраспределениемзадач(англ.randomizedloadbalancingalgorithm),циклический алгоритм (англ.

Round-Robin), средневзвешанный циклическийалгоритм (англ. Weighted Round-Robin Scheduling), алгоритм выбора41наименее загруженного узла (англ. Least-Loaded), алгоритм наименьшегоколичества соединений (англ. Least-Connection).Циклический алгоритм балансировки нагрузки является одним изпервых предложенных алгоритмов для решения данной проблемы, которыйбыл подробно рассмотрен Клейнроком в [61]. Основная идея алгоритма,применительно к данной задаче, заключается в том, что вместо ожиданияполногозавершениявыполнениязадачинавычислительномузле,программный балансировщик осуществляет переход к следующей задаче ираспределяет её на следующий узел.

Данное действие происходитнеоднократно, до тех пор, пока не будут обработаны все задачи. Часто, взарубежной литературе, данный метод называют алгоритмом квантования повремени (англ. time-slicing) [62]. На рисунке 1.7 представлена обобщённаясхема, иллюстрирующая процесс балансирования нагрузки на основециклического алгоритма.Рисунок 1.7 — Демонстрация работы алгоритма ROUND Robin42Случайныйалгоритмбалансировкинагрузкиоснованнавероятностном распределении заданий по узлам распределённого комплекса,в отличие от детерминированного подхода в циклическом алгоритме.

Вданном методе i-ая задача может быть обработано на узле с вероятностью p.Среди динамических алгоритмов балансировки выделяются: Алгоритмвзвешенного наименьшего количества соединений (англ. Weighed LeastConnection Algorithm, WLCA), алгоритм выбора наименее загруженного узла(англ.

Least-Loaded), алгоритм наименьшего количества соединений (англ.Least-Connection).Алгоритм взвешенного наименьшего количества соединений (англ.Weighed Least Connection Algorithm, WLCA) основан на направлении(перенаправлении) задач на узлы с наименьшим количеством текущихсоединений. Учёт количества активных соединений и формированиерасписания обработки задач происходит в режиме реального времени. Врезультате чего, данный метод можно отнести к классу динамическихстратегий распределений заданий в РВК. Псевдокод алгоритма представленниже [63]S = {S0, S1, ..., Sn-1}; // множество вычислительных узлов РВКW(Si); //вес узла SiC(Si); //число активных подключенийCSUM = Σ C(Si) (i=0, 1, ..

, n-1); // сумма числа активныхподключенийfor (m = 0; m < n; m++){ if (W(Sm) > 0){ for (i = m+1; i < n; i++){ if (C(Sm)*W(Si) > C(Si)*W(Sm))m = i;} return Sm; }43} return NULL;}При использовании алгоритма Leasted Loaded выбор узла для передачиданных осуществляется по критерию минимальной загрузки его ресурсов[111]. Схожим действием с данным методом обладает метод Least Connected(наименьшее количество соединений).

При использовании этого метода, узелвыбирается с наименьшим количеством соединений (TCP/IP,UDP). Примерработы алгоритма Leasted Loaded представлен на рисунке 1.8.Рисунок 1.8 — Механизм работы алгоритма Leasted Loaded [111]Большинство последующих работ по решению задачи балансировкипотоков было направлено на улучшение перечисленных выше алгоритмов.Так, например, в [64] было предложено улучшение алгоритма наименьшегоколичества соединений, за счёт постоянного пересмотра веса узла системы.Так как вес узла для алгоритма WLCA задаётся априорно и не изменяется вовремени, то это может приводить к недооценке возможной нагрузки.

Для44решения данной задачи авторы предлагают модернизировать алгоритм,путём введения методики (см. формулу (1.1)) расчёта переменного среднеговеса узла РВКW j  ( pmem  Qmem  Rmem ) 2  ( pcpu  Vcpu  Rcpu ) ,где(1.1)Rmem – скорость памяти без нагрузки,Rcpu – скорость ЦПУ при простое,Qmem – объём памяти,Vcpu – производительность ЦПУ,pmem и pcpu – коэффициенты.Проведённые экспериментальные исследования автором данногометода балансировки вычислительной нагрузкой, показывают повышениепроизводительности системы при просмотре потокового видео.Как уже было сказано, динамические методы обладают рядомзначительных преимуществ, по сравнению со статическими, и являютсянаиболеепривлекательнымидляпроведенияисследований.Однако,большинство существующих методов, которые были рассмотрены выше,обладают и рядом недостатков.

Так, ряд исследователей [43, 65, 66],выявляют неполноту существующих методов балансировки вычислительнойнагрузки.Действительно, существующие подходы обладают низкимуровнем адаптации к возникающей нагрузке, при их использовании всовременных гетерогенных вычислительных комплексах, а также реагируюттолько на возникшую нагрузку, что часто приводит к дисбалансувычислительной нагрузки всей системы. В результате чего, остро встаётвопрос создания методов балансировки вычислительной нагрузки, которыебыли бы лишены указанных недостатков.451.5. Прогностический подход к балансировке нагрузки враспределённых вычислительных комплексахОдним из перспективных [43,67,112] направлений современныхисследованийвобластибалансировкивычислительнойнагрузкивраспределённых комплексах, является создание методов реализующихпрогностическуюстратегиюбалансировкивычислительнойнагрузки.Методы прогнозирования сетевого трафика и вычислительной нагрузки вкомпьютерных системах развились в конце 20 века, как одно из направленийдисциплины «теория телетрафика» [68].

Прогнозирование телетрафика былонеобходимо при проектировании компьютерных систем для предварительнойпроверки адаптивности распределённой системы или сети к возможнойнагрузке.Применительно к решению данной задачи был разработан и активноиспользовался ряд методов [65]:1. Методы на основе ARIMA модели.2. Нейронные сети.3. Модель на основе фильтра Калмана.4. Методы на основе модели сглаживания.Методикапрогнозированиятелетрафикатакжеопределенаврекомендациях E.506 и E.507 Международного консультационного комитетапо телефонии и телеграфии (англ. ITU-T) [69]. Данные рекомендацииразрабатывались для прогнозирования ISDN сетей и существенно устарели,но часть их может быть использована в современных системах.

Однакоприменение данных методов для прогнозирования телетрафика и уровняузловой нагрузки в современных РВК, освещено в отечественной изарубежной литературе ещё недостаточно полно. Одной из последних работ внаправлении создания прогностических алгоритмов балансировки нагрузкиявляется работа Liu Kun, Xu Gaochao1 и Chen Jingxia [70], в которой они46предложилиперспективныйметодпрогностическойбалансировкивычислительной нагрузки для облачных вычислений, основанный на методеэкспоненциальногосглаживания.Алгоритм,предложенныйданнымиавторами, фактически основан на анализе предыдущих значений узловойнагрузки, которые сформированы в единый временной ряд, и формированиина его основе следующих (прогнозных) значений нагрузки.

Расчёт будущихзначений вычислительной нагрузки осуществляется на основании формулыyt1   * yt  (1   )* yt ,где(1.2)yt1 - прогнозное значение будущей нагрузки в момент времени t+1; * [0,1] - коэффициент сглаживания;y t - прогнозное значение в момент t;y t -актуальное значение нагрузки в момент времени t.Алгоритм [70] балансировки с использованием экспоненциальногометода сглаживания состоит из следующих шагов:1. Сбор и оценка перегрузки узла на основе модели мониторинга.2.

Отправка d предыдущих (d-неопределённое число) и текущегозначений узловой нагрузки в модель прогноза.3. Установка коэффициента сглаживания α=0,3. Расчёт предикатногозначения yt1 на основании экспоненциального метода сглаживания.Расчёт прогнозных значений осуществляется по формуле 1.2.4. Установка коэффициента сглаживания α=0,5.Расчётпредикатного значения d на основании экспоненциального методасглаживания. Расчёт прогнозных значений по формуле 1.2.5.

Установка коэффициента сглаживания α=0,7. Расчёт предикатногозначения d на основании экспоненциального метода сглаживания.Расчёт прогнозных значений по формуле 1.2.476. Сравнение трёх значений и выбор коэффициента сглаживания α, длякоторого расчётное значение минимально.7. РасчётбудущихNзначенийсвыбраннымкоэффициентомсглаживания.Основнымпреимуществомданногометодаявляетсяпростотареализации. Однако данный метод не лишен и некоторых недостатков.Существенным недостатком является необходимость правильного подборатребуемого коэффициента сглаживания и его постоянной корректировки входе работы для каждой РВК, так как от данного коэффициента, напрямуюзависит спрогнозированное значение узловой нагрузки.Также большинство методов, при выполнении прогнозирования,основывается на статистических данных, сбор которых часто затруднён, атакжене учитывает информацию о характере и свойствах возникающейнагрузки, что может привести к недооценке вычислительной нагрузки, атакже к дополнительным накладным расходам.

В частности, свойстванестационарности и самоподобия сетевого трафика и узловой нагрузки всовременных компьютерных системах и сетях с коммутацией пакетов(переход на ISDN, а также последующие развитие сетей NGN), приводят кневозможности применения некоторых методов, разработанных для анализаи прогнозирования временных рядов [71,111].Выводы по 1 главеВ результате проведённого анализа предметной области выявлено, чтобольшинство современных распределённых вычислительных комплексовреализуется на основе различных системных архитектур и может включать всвойсоставразличнымиоборудованиеразличныхфункциональнымипроизводителей,характеристиками.Дляобладающихобеспеченияоптимальной работы всего РВК необходимо обеспечить соответствующийпроцесс балансировки потоков задач, а именно их распределение и48перераспределениепоузламкомплекса.Существенным недостаткомбольшинства существующих подходов к реализации балансировки потокамизадач в распределённых комплексах является их низкая адаптивность квозникающей нагрузке.