Обзор алгоритма распространения информации в социальных сетях

Пусть сервис является объектом для предоставления услуги клиентам cloud сети, основной характеристикой которого является продолжительность обработки запроса tобр. Рассмотрим атомарный сервис ― сервис, реализованный одной программой, установленной на одной виртуальной машине. Если установлено несколько атомарных сервисов на одной физической машине, производительность таких сервисов уменьшается, поскольку доступ сервисов к ресурсам физической машины происходит по методу временного разделения. Поэтому в случае увеличения количества сервисов на одной РМ, рост интенсивности поступления запросов на РМ и увеличения интенсивности поступления запросов на каждый сервис увеличивается продолжительность обслуживания запросов каждым сервисом. В случае уменьшение производительности сервиса система управления переносит этот сервис на другую VM или РМ.

Логическая топология не меняется, но данные проходят по другим физическим каналам. В таком случае общее время передачи сервиса от пользователя к ЦОД и в обратном направлении рассчитываться так:

где: n ― количество запросов;

t_{коммут.} ― время прохождения запроса через систему коммутации;

t_п.к.з. ― время поиска каналов, по которым будет осуществляться передача;

t_обр. ― время обработки запроса, который является суммой времен обработки запроса сервисом, который состоит из k атомарных сервисов:

Поскольку оптимальный путь передачи изменяется, то это приводит к увеличению времени поиска каналов, по которым будет осуществляться передача - t_п.к.з., что, в свою очередь, приведет к увеличению общего времени передачи (рисунок 6).

Время поиска маршрута, мкс

Рисунок 6 – Зависимость времени передачи сервису данных от временни поиска канала, по которому производиться передача

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

Метрика этого алгоритма представляется в виде:

где: К_n ― коэффициенты, которые задает администратор для корректировки композитной метрики;

minC ― минимальное значение пропускной способности на пути следования оптимального маршрута, по которому будут направляться данные;

L ― загруженность каждого звена в сети;

D ― суммарная задержка на интерфейсах;

R ― надежность пути.

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

Предположим, что некоторый интерфейс на выходе, при передаче информации от физического сервера А к виртуальной машине, имеет значение задержки t, до порогового значения задержки Т, то есть t <T. Виртуальная машина с целым программным комплексом в результате воздействия различных факторов мигрирует на физический сервер В. Алгоритм поиска пути по критерию минимального времени прохождения, передавая запрос на предоставление сервиса, анализирует, что такого логического оптимального маршрута уже не существует, поскольку на выходе из интерфейса, в случае передачи по "старому" маршруту, значение задержки t превышает пороговое значение Т (рисунок 7).

Суммарная задержка на интерфейсах, мс

Рисунок 7 – Зависимость времени поиска оптимального маршрута от суммарной задержки на интерфейсах

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

Дано:

· Количество разновидностей медиапланирования - n;

· Количество видов имеющихся ресурсов - m;

· Значение ценовых коэффициентов на единицу медиапланирования j-го вида - , ;

· Запасы ресурсов i-го вида – b_i, ;

· Матрица затрат ресурсов на медиапланирование – А, в какой a_ij- затраты i-го вида ресурса на j-й вид медиапланирования;

· Значение ценовых коэффициентов параметрической составляющей ЦФ для каждого го вида медиапланирования - , .

Переменные:

· - количество медиапланирования.

В матричном виде математическая постановка задачи будет иметь следующий вид.

Целевая функция - максимизировать прибыль от продажи услуг медиапланирования:

(2.4)

Ограничения:

	(2.5)
	(2.6)
.	(2.7)

Данная задача является задачей параметрического программирования с параметром в целевой функции.

Назначением задачи является определение коэффициентов параметрической составляющей задачи, то есть значений вектора.

Для определения коэффициентов, параметрических составляющих задачи (2.4) - (2.7) необходимо применить один из методов оценки неизвестных величин. К таким методам оценки относятся: метод наименьших квадратов (МНК), взвешенный метод наименьших квадратов, метод - оценок и метод наименьших модулей (МНМ) [1]. При разработке комплекса задач для определения вектора применялся МНМ, в нем минимизируется следующая функция (суммарное отклонение):

,

(2.8)

где - неизвестные параметры;

- функция, параметры которой мы оцениваем;

- результаты -го наблюдения .

Задача (2.4) - (2.7) является классической задачей линейного параметрического программирования (ЗЛП) [7], а задача (2.8) может быть сведена к ЗЛП, поэтому решать их будем, используя алгоритмы разработаны для данного класса задач.

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

В основе метода параметрического программирования для ЗПУ с параметром в целевой функции лежат процедуры прямого симплекс-метода с некоторой модификацией, следовательно, для задачи (2.4) - (2.7) будем применять процедуры алгоритма именно этого метода.

Относительно задачи (2.8), то она сводится к задаче линейного программирования, позволит решить ее симплекс-методом.

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

Параметрическое программирование - это метод определения того, как меняется решение задачи с изменением всех компонент вектора коэффициентов ЦФ.

Пусть при задача имеет оптимальное решение . Без потери общности предположим, что в оптимальном решения небазисные переменные имеют номера 1,…, . Запишем преобразованную задачу, соответствующую оптимальному развязку ( )

(2.9)

где

(2.10)

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

(2.11)

При параметрическая составляющая не играет никакой роли. При увеличении от нуля происходит поворот вектора нормали ЦФ , при достижении определенного значения это может привести к изменению оптимума.

Продолжим анализ задачи. При увеличении от нуля общая ЦФ приобретает значение

.

(2.12)

Решение остается оптимальным до тех пор, пока выполняются условия:

.

(2.13)

Обобщим описанный выше метод в виде пошагового алгоритма:

Шаг 0. Найти решение начальной ЗЛП при .

Шаг 1. Если для всех ( - множество индексов небазисных переменных), текущий решение остается оптимальным при всех сколь угодно больших , Стоп. Иначе найти

и соответствующее .

Шаг 2. Если , то мы определили все решения в заранее заданном диапазоне изменения параметра , Стоп.

Шаг 3. Если для всех ( - множество индексов базисных переменных), то при изменении базиса ЦФ становится неограниченным (если в столбце, соответствующей переменной , все коэффициент не положительные, то при всех ЦФ неограниченное сверху), Стоп.

Иначе найти переменную, которую выводим из базиса, с помощью выражения

.

Пусть минимум соответствует индексу .

Шаг 4. Выполнить операцию замещения: ввести в базис переменную , вывести из базиса переменную .

Шаг 5. Перейти на Шаг 1.