В одном из предыдущих материалов мы сказал о статических методах балансировки нагрузки в облаке IaaS-провайдера.
Сегодня следующий шаг — динамические методы: «пчелиный» и «муравьиный» алгоритмы, а также подход Biased Random Sampling. 
/Фликр/ Куинн Домбровски / CC BY-SA
Динамические методы балансировки, в отличие от статических, учитывают в своей работе текущий состояние всей системы и реагировать на изменения в ней.
Часто информация о нагрузке на узлы хранится в таблице состояний, из которой черпают информацию системы распределения нагрузки.
Динамическое распределение нагрузки — выполненный мониторинг
Смещенная случайная выборка
Для реализации этого подхода сеть кажется в виде виртуального ориентированного графа, вершинами которого являются все серверы.В допуск запрос на выполнение задачи, балансировщик нагрузки назначает его вершине (узлу), полустепень которой равна хотя бы единице.
Когда узел получает задачу, процессор начинает ее выполнять и параллельно сигнализирует об уменьшении количества доступных вычислительных ресурсов, уменьшая поступающую полустепень.
Когда задача «решена», узел увеличивает этот показатель, сообщая об освобождении ресурсов.
Выбор стартовой вершины для выполнения задачи сделанный случайный (следовательно, случайная выборка); последующие задачи назначаются соседним узлам, которые также выбираются в случайном порядке.
Этот метод балансировки нагрузки полностью децентрализован и поэтому подходит для облачных сетей.
В том числе географически распределенных.
Ученые из Ливерпуля выяснили, что Biased Random Sampling, дополнительно учитывающая географическое распределение узлов в сети, позволяет снизить задержку при передаче данных на 22%.
В тесте с 512 узлами, расположенными в радиусе тысячи километров, средняя задержка составила примерно 70 мс (в эксперименте с сетью, не учитывавшей географическое распределение узлов, этот показатель составил 92,5 мс).
Алгоритм оптимизации муравьиной колонии
Впервые это понятие было введено представлен в начале девяностых.Она черпает вдохновение из поведения муравьев.
Муравей всегда способен найти путь от источника пищи к муравейнику, даже если обычный путь оказался «закрыт».
Для этого эти насекомые отмечают маршрут специальными феромонами.
Считается, что чем сильнее этот «запах», тем ближе источник пищи.
В контексте балансировки нагрузки в телекоммуникационных сетях это выглядит так.
Сеть представляется в виде графа, и из всех возможных узлов выбирается главный, имеющий наибольшее количество соседей.
Коммутационные станции отображаются в узлы графа, а линии связи между ними — в ребра.
Каждый узел содержит «таблицу феромонов», в которой собираются данные об используемых ресурсах и доступной мощности: объеме памяти, количестве процессоров и т. д. Периодически с каждого узла запускаются муравьи, которые отправляются в случайные узлы-приемники.
«Насекомые» перемещаются между узлами, руководствуясь таблицей феромонов.
Эта таблица обновляется каждый раз, когда к ней обращается муравей.
Муравьи имеют возраст, равный длине пройденного пути.
Муравьи также задерживаются в узлах, перегруженных вызовами.
Те насекомые, которые выбирают более короткий и менее перегруженный путь, влияют на вероятность выбора этого маршрута последующими муравьями в большей степени, чем муравьи, выбирающие наихудший путь с точки зрения длины и загруженности.
Это связано с тем, что первые муравьи прибывают в приемный узел раньше и моложе.
Новые запросы отправляются по кратчайшим незагруженным маршрутам.
Это позволяет сбалансировать ресурсы за счет разгрузки узлов на «плотных» направлениях в сети.
Один из вариантов этого алгоритма использует Фреймворк для P2P-приложений Anthill. Эта система представляет собой самоорганизующуюся сеть связанных между собой «муравейников» — узлов, способных выполнять вычисления и обрабатывать данные.
Структура сети муравейника
Когда узел получает запрос от приложения, он запускает автономный агент — ant — для выполнения задачи.
Он перемещается по сети от узла к узлу, пока не выполнит запрос.
При движении муравьи «несут» с собой информацию о запросе, результате и другие метаданные.
Муравьи не общаются друг с другом напрямую; вместо этого они оставляют информацию, необходимую для решения проблемы, менеджерам ресурсов, расположенным в узлах, которые они посещают. Например, муравей, реализующий службу поиска, может таким образом оставлять информацию о маршрутизации, которая поможет другим муравьям найти путь к узлам, содержащим нужные им данные.
Подобную форму непрямого общения используют настоящие муравьи – она называется стигмергия .
Алгоритм оптимизации «Пчела» (добыча медоносных пчел)
Первые статьи, описывающие метод пчелиного роя, были опубликовано в 2005 году.Он основан на моделировании поведения пчел при поиске нектара.
В ульях живут так называемые пчелы-разведчики, которые находясь в поиске луга с цветами.
Найдя источник пищи, они возвращаются в улей, чтобы рассказать о нем другим, используя специальный «танец виляния».
/Фликр/ Нерегулярный блог - Дедал / CC BY-SA
Этим танцем пчела сообщает, насколько хорош нектар на поляне и как далеко он находится.
После этого на ее призыв откликаются кормящие пчелы, летят за разведчиком, собирают «урожай» и возвращаются в улей с «добычей».
Затем пчела-собиратель может сделать одно из следующих действий: стать праздным собирателем, оставив текущий источник нектара, продолжить сбор его самостоятельно или позвать на помощь нескольких других праздных пчел.
Эта модель используется для балансировки нагрузки следующим образом.
Первым делом рассчитанный определяется текущая нагрузка на виртуальные машины и их состояние (сбалансировано, выгружено, перегружено) в зависимости от установленных ими пороговых значений.
Если нагрузка на ВМ небольшая, то все новые задачи будут отправляться на нее.
Если в системе есть перегруженные виртуальные машины, каждая из них может принимать возьмите на себя роль разведчика или собирателя.
При обработке запроса виртуальный сервер вычисляет некую величину, аналогичную «качестве» луга с цветами, которое демонстрирует танец пчел.
Одним из способов оценки этого значения может быть время, необходимое процессору для его завершения.
Затем сервер «рекламирует» эту задачу всей системе, как будто размещая ее на доске объявлений — таким образом сервер берет на себя роль разведчика.
Другие серверы могут просматривать эту доску объявлений и обрабатывать размещенные там запросы, становясь собирателями.
Другие материалы из корпоративного блога 1cloud:
- Балансировка нагрузки: трудности прогнозирования
- Безопасность данных в облаке: угрозы и методы защиты
- Чем отличается сеть от подсети: где граница?
- Как создать компьютерную лабораторию в облаке
-
10 Бесплатных И Крутых Шрифтов
19 Oct, 24 -
Космонавтика-2018 - Обзор Миссий И Запусков
19 Oct, 24 -
Умпутун Против Бобука
19 Oct, 24 -
Николай Гоголь
19 Oct, 24 -
Топ-6 Оптимизаций Для Netty
19 Oct, 24
