АГЕНТНЫЕ МОДЕЛИ ДИНАМИЧЕСКОГО ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ СЕТЕВЫХ РЕСУРСОВ СИСТЕМЫ GRID
 

Данное направление исследований посвящено разработке имитационных моделей проблемных ситуаций, возникающих перед брокерами ресурсов сетей Grid.
Многие системы управления ресурсами Grid, такие как Legion, Condor, AppLeS PST, NetSolve, PUNCH, XtremWeb и т. д., используют, как правило, лишь простые схемы распределения, настраиваемые системными параметрами функции стоимости. Цель таких схем – увеличение пропускной способности системы и её загруженности с точки зрения уменьшения времени выполнения задач, а не увеличение рентабельности ресурсов сетей в целом.
Как справедливо отмечается в [2], внимание, как правило, не концентрируется на изменениях цены использования ресурса. А это означает, что значимость выполнения всех приложений в любое время одинакова. В реальности, однако, это не совсем так. Ведь значимость всё же должна возрастать с приближением срока выполнения прикладной задачи. И тогда, на уровне внутрисистемного менеджмента, между владельцами и пользователями сетей Grid (архитектура которых в последнее время становится всё более децентрализованной) могут возникать нетривиальные взаимоотношения, связанные с распределением и динамическим перераспределением ресурсов. Для решения подобных задач в [1] предлагается использовать опыт, накопленный при разработке экономико-математических методов и моделей.
До последнего времени поведение сетей Grid практически не рассматривалось с точки зрения их экономической эффективности. Действительно, рыночная модель распределения ресурсов характеризуется, прежде всего, тем, что цена каждого ресурса определяется потребностями в нем пользователей, а также его доступностью. Тогда пользователь Grid начинает конкурировать с другими пользователями, а владельцы ресурсов – с другими владельцами. Подобная способность ценовых механизмов подменять локальные решения по управлению некоторыми глобальными экономическими характеристиками может эффективно применяться при организации вычислений в больших системах распределения ресурсов, таких, как Grid или Internet.
Для описания подобных систем, состоящих из множества разнородных субъектов с различными целями, подходят так называемые агентные модели. Если попытаться посмотреть на глобальные вычислительные сети с этой точки зрения, то в первую очередь можно отметить следующее. В системе Grid действуют два основных типа субъектов: поставщики ресурсов и их потребители. И те, и другие имеют собственные стратегии. Потребители ресурсов применяют стратегии решения своих прикладных задач в зависимости от требуемого времени и наличного бюджета. Поставщики используют стратегию получения наибольшей выгоды от вложенных средств и стараются максимизировать использование своих ресурсов. Желательно было бы построить модель, описывающую поведение такой системы с учётом интересов конкурирующих субъектов. В [2] выделяется и третий тип субъекта – брокер ресурсов. Однако собственных целей он не имеет, и его функции заключаются в поиске поставщиков ресурсов, удовлетворяющих запросам пользователей.
Модели с похожими свойствами уже строились ранее, правда, для описания лишь экономических явлений. Так, например, в работе [3] была построена имитацион-ная модель самоорганизации торговых сетей. В этой модели рассматривался однопро-дуктовый рынок, на котором действовали агенты двух основных типов:
торговцы-поставщики и потребители товара. Там присутствовали и агенты третьего типа, так на-зываемые производители, но собственных целей они не имели и самостоятельно не действовали. Функции производителей сводились к предоставлению всем обращаю-щимся к ним покупателям любого запрошенного количества товара по фиксированной цене. Таким образом, торговцы испльзовали стратегию получения наибольшей прибы-ли, а потребители стремились максимизировать потребление товара.
Поставщики ресурсов Grid по своему поведению очень похожи на торговцев из модели [3], а потребители ресурсов при этом вполне аналогичны потребителям товара.
Далее предпринимается попытка реализовать эту модель средствами AnyLogic™.
Как и в исходной математической модели, представлены агенты трех типов – конечные потребители (потребители вычислительных ресурсов), торговцы (активные поставщики ресурсов) и производители (владельцы ресурсов).
Цель конечных потребителей – потребить необходимое количество ресурсов с минимальными затратами. Цель поставщиков ресурсов – поставить требуемое количество ресурсов, при необходимости, привлекая к этому владельцев ресурсов. Владельцы ресурсов могут предоставлять их в зависимости от своих возможностей и текущей конъюнктуры спроса на ресурсы. Все агенты размещены на плоскости и имеют координаты (x, y). Учитывается воздействие торговых расстояний – некоторой характеристики, влияющей на издержки при потреблении и поставке ресурсов и зависящей от физического расстояния между агентами и качества инфрастуктуры.
В модели изменения состояний экономических агентов подразделяются на быстрые и медленные. Быстрые решения принимаются агентами в каждый момент времени и могут меняться скачками. Медленные решения формируются по наблюдениям за быстрыми, являются непрерывными и по сути увеличивают значение показателя, характеризующего экономический интерес агента. У конечного потребителя таким показателем служит потребление, а у торговца – чистая прибыль. Ниже демонстрируется фрагмент модели поведения конечного потребителя.
Итак, потребитель обладает следующими внутренними характеристиками: потребность в ресурсах, расходы в единицу времени на поиск ресурсов, заработная плата, среднее время потребления единицы ресурсов, скорость адаптации профиля предпочтений. Выбор поставщика ресурсов осуществляется на основе профиля предпочтений, определяющего вероятность обращения к тому или иному поставщику ресурсов. Конечный потребитель может находиться в одном из трех состояний – состоянии работы, подключения ресурсов и потребления ресурсов.
Ниже описана последовательность смены состояний конечного потребителя, а соответствующий стейтчарт представлен на рис. 1.
1. Потребитель обменивается информацией с ближайшим потребителем или торговцем.
2. Если есть необходимость, потребитель меняет состояние. Время нахождения в каждом состоянии – это реализация случайной величины, распределенной по пуассоновскому закону с соответствующей частотой.
Например, частота для времени нахождения в состоянии работы определяется по формуле:

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


Большое влияние на поведение агентов оказывает процесс обмена информацией. Исследовались две модели информационного обмена. В "кластерной" модели ближай-шие соседи обменивались наиболее "свежей" информацией о ценах и вероятностях на-личия ресурсов у поставщиков. Если на схеме размещения агентов нарисовать эти ин-формационные связи, получится граф, распадающийся на связные куски. Каждый такой связный подграф представляет собой кластер покупателей, внутри которого информа-ция распространяется быстро. Пример такого графа представлен на рис. 2. Конечные потребители изображены в виде квадратиков, причем состоянию работы соответствует зеленый цвет, состоянию подключения ресурсов соответствует красный цвет, состоя-нию потребления соответствует синий цвет. Поставщики изображены в виде кружков, желтый цвет которых соответствует свободному состоянию, а серый – состоянию по-ездки за товаром. Владельцы ресурсов изображены в виде треугольников. Линиями между собой соединены ближайшие соседи, между которыми происходит быстрый об-мен информацией.

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

 
назад

вперед