Software & Systems

Одной из основных и наиболее трудно решаемых задач разработки распределенных тренажерных систем на основе технологии DCOM (модель клиент-сервер) является задача оптимального распределения серверных компонентов (служб) по узлам локальной вычислительной сети (ЛВС). При фиксированном числе рабочих станций работу между ними можно распределить по-разному. В связи с этим встает задача определения такого распределения служб, при котором обеспечивается равномерная загрузка рабочих станций при ограниченной пропускной способности каналов связи.

Пусть имеется n серверных служб, которые формируют определенный трафик для каждого рабочего места тренажерного комплекса, и m рабочих станций. Имеются данные о мощностях узлов сети и об объеме формируемого серверной службой трафика. Также известна загрузка j-го узла сети i-й серверной службой. Загрузка j-го узла сети основным процессом (рабочее место) одинакова и равна Т. Кроме того, на начальном этапе задается точность ∆. Необходимо так распределить серверные службы по узлам сети, чтобы минимизировать суммарную загрузку всего программного комплекса.

Данные задачи представляются в виде таблицы, где – мощность i-го узла, ;  – сетевой трафик службы, ; – загрузка j-го узла сети i-й серверной службой; ∆ – точность, причем  и .

Поскольку на одном компьютере могут одновременно работать несколько процессов, то загрузка i-го узла представляется в виде уравнения:

,                                                      (1)

где I – множество индексов, расположенных в i-м узле серверных служб.

Необходимо учитывать ограничение на количество передаваемых по сети данных, поэтому определим:

,                                                    (2)

где Bi – суммарный трафик расположенных в i-м узле серверных служб; B – максимально допустимый трафик.

Тогда целевая функция примет вид:

, где ,  – мощность работы i-го узла.

Рассмотрим общую схему метода решения подобных задач. Пусть задача А состоит в нахождении такого элемента р* конечного множества Р, на котором достигается минимум функции F(X), определенной на этом множестве: .

Элементы множества Р, среди которых производится поиск, называются планами задачи А, а план р* – оптимальным планом задачи А.

Метод построения последовательности планов [1,2] применим к задаче А, если выполняются следующие условия:

1) можно найти конечное расширение R множества Р(PÌR) и функцию Q(X) (миноранту), определенную на R, такую что Q(X);

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

Если существует такое натуральное число k, при котором ,  , то  – оптимальный план задачи А.

Схема работы метода ψ решения задачи A:

1) конструируется конечное расширение R исходного множества Р;

2) на множестве R задается функция Q(X), являющаяся минорантой функции F(X) на множестве Р;

3) формируется итеративный (но конечный) алгоритм φ, который на каждом шаге с номером k определяет оптимальный план  задачи минимизации функции Q(X) на множестве , образованном из расширения R путем исключения предыдущих оптимумов . Таким образом, алгоритм φ определяет последовательность оптимумов  миноранты Q(X) на последовательности вложенных друг в друга множеств ;

4) на каждом k-м шаге метода ψ проверяется выполнение критерия оптимальности. Если критерий выполняется, то процесс обрывается и  есть оптимальный план исходной задачи А. В противном случае переходим к (k+1)-му шагу метода ψ.

Вспомогательную задачу минимизации миноранты Q(X) на множестве R будем называть задачей . На предварительном этапе работы алгоритма строим функции , решая уравнения:

если  и , то ;

если  или , то этот случай не рассматриваем.

Пусть задача  состоит в минимизации сепарабельной функции

,                      (3)

заданной на множестве R векторов , удовлетворяющих условиям , где b>0,  – целые числа. Здесь ω – операция сложения или умножения. Для этого следует воспользоваться следующим функциональным уравнением:

,   (4)

где , причем  для . Здесь  – оптимальное значение функционала задачи , в которой индекс n и параметр b заменены соответственно на k и z. Введем некоторые необходимые определения и обозначения. План  задачи  назовем h-оптимальным, если  , и будем обозначать его .

Таким образом,  – h-опти­мальный план задачи , если  – оптимальный план задачи минимизации функции (3) при условиях .

Непосредственно из определения h-оптималь­ного плана следует, что  , где  , то есть  – множество всех тех планов задачи , у которых .

Теперь можно сформулировать процедуру построения последовательности  планов задачи  следующим образом.

Алгоритм φ

1-й шаг: cреди множества  всевозможных (n-1)-оптимальных планов , … ,  находим такой план  , что .

k-й шаг (k=2,3,…): множество  преобразуем во множество  по следующему правилу. Оставляем без изменения все планы множества , кроме плана , который заменяем множеством , состоящим из следующих планов:

Далее находим такой план, что  , и переходим к следующему шагу.

Для решения функционального уравнения (4) необходимо знать значения функций  в промежуточных точках . Так как все типы данных задачи целочисленные (биты, секунды), то в качестве промежуточных точек будем брать лишь целые числа 1,…,b. Но и в этом случае при больших значениях b и при высокой точности (скажем, ∆=1) объем информации, которую необходимо вычислить, а главное, хранить, весьма велик. Все это делает актуальной проблему сокращения количества таких точек до числа, которое приемлемо при машинной реализации.

Список литературы

1. Емиличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. - М., 1981.

2. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование - М., 1969.