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

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

Оценивая эффективность работы сети, чаще всего выбирают такие критерии, как производительность и надежность, для которых в свою очередь необходимо выбрать конкретные показатели оценок, к примеру, время реакции на запрос, коэффициент готовности [1], пропускную способность канала связи, задержку передачи и т. д.

Как правило, под оптимизацией сети понимают некоторый промежуточный вариант, при котором требуется выбрать такие значения параметров сети, чтобы показатели ее эффективности существенно улучшились.

Производительность сети можно измерить с помощью временных показателей, оценивающих задержку, вносимую сетью при выполнении обмена данными по каналу связи между рабочими станциями [3].

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

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

Надежность сетей как распределенных систем во многом определяется надежностью кабельных систем, коммутационной аппаратуры и аппаратуры передачи данных. При эксплуатации компьютерной сети по фактическому состоянию [2], потерю производительности сети можно предсказать, располагая определенной накопленной статистикой, и на этой основе обеспечить достаточно эффективное управление техническим состоянием компьютерной сети предприятия.

Один из подходов наиболее эффективного управления компьютерной сетью — использование принципов индивидуального прогнозирования технического состояния основных блоков компьютерной сети, на этой основе предполагается осуществлять заранее замену блока с предотказным техническим состоянием [3].

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

Самовосстанавливающие системы — это системы с неограниченным резервированием. Переход к системам с неограниченным резервированием позволяет существенно повысить надежность элементов компьютерной сети и самой сети в целом, однако при этом система усложняется по архитектуре, объемам обрабатываемой информации и стоимости, включая дополнительное оборудование и программное обеспечение. В связи с этим возникает задача оптимального проектирования сети [4].

В качестве параметров, характеризующих структуру и быстродействие компьютерной сети, объем циркулирующей информации и стоимость сети и ее обслуживания в целом, можно рассмотреть буферную память на узлах маршрута (m), среднюю по сети пропускную способность (v) и общую стоимость компьютерной сети предприятия (s) в зависимости от количества входящих в нее узлов. Таким образом, для решения задачи необходимо спроектировать самовосстанавливающуюся самонастраивающуюся систему контроля технического состояния компьютерной сети, состоящей из n элементов (узлов), так, чтобы надежность всей системы была наибольшей, а контролируемые параметры m, v, s были ограничены некоторыми величинами M, V, S [4]. Пусть каждый элемент системы имеет свои надежность p_i, объем используемой буферной памяти на узлах маршрута m_i, обеспечивает скорость передачи данных, равную v_i, и стоимость s_i. Тогда надежность всей системы будет равна Р=, а ненадежность Q=1P=1.

Так как величина, то в произведении можно пренебречь, где k2, и перейти к приближенному равенству .

Цель задачи — найти такие рациональные пути резервирования различных элементов сети, при которых будет выполнено условие Q > Q_доп.

Не ограничивая общности, предположим, что каждый элемент дублируется l раз, образуя узел. Тогда по формуле для ненагруженного резерва Q_нр(t) = Q₁(t)Q₂(t)•••Q_n(t) найдем. Одновременно с этим параметры m, v и s увеличиваются:

компьютерный сеть прогнозирование виртуальный.

,. (1).

Выразим показатель резервирования через показатели надежности и исходных и резервируемых элементов:

(2).

где .

Подставим выражение (2) в формулы (1), получим:

, ,.

а ограничения по объему буферной памяти на узлах маршрута, пропускной способности и стоимости можно записать в виде следующих неравенств:

, (3).

где, , .

Пусть — коэффициент веса каждого узла при отказе системы в целом. Тогда уровень ненадежности запишется в виде:

.

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

. (4).

Следуя последним рассуждениям, можно сделать вывод, что Q будет минимальным при тех неотрицательных результатах решения системы (4), при которых будет минимально Q*. Из выражения (4) видно, что минимум Q* совпадает с максимумом функции. Следовательно, задача оптимального проектирования самовосстанавливающейся системы (с неограниченным резервом) сводится к задаче линейного программирования, которая формулируется следующим образом.

Имеется система g линейных алгебраических уравнений с неизвестными :

(5).

и линейная функция.

.

Требуется найти такое неотрицательное решение, при котором линейная функция F принимает минимальное (максимальное значение).

Согласно теории линейного программирования можно выделить следующие этапы решения данной задачи:

Неравенства (3) приводятся к системе равенств.

.

(6).

.

где дополнительные неизвестные, удовлетворяющие условию ?0.

Решения системы (6) удовлетворяют и неравенству (3).

Все неотрицательные решения поставленной задачи линейного программирования 0 образуют выпуклое множество G, т. е. любая линейная комбинация решений является также решением.

Линейная функция F достигает своего максимума (минимума) только в крайних точках множества G, т. е. в таких точках, координаты которых являются положительными составляющими вектора B (b₁, b₂, …, b_g), разложенного по векторам e₁, e₂, …, e_g, принятых в качестве базиса: B₀=x₁e₁+x₂ e₂+ …+x_ge_g.

Каждой крайней точке множества G соответствует свой базис e_i, а число базисов не может быть больше .

Эффективным алгоритмом решения данной задачи (перебора всех крайних точек и отыскания экстремума) является симплексный метод.

Итак, имеется система n уравнений с n неизвестными (5). Запишем эту систему в виде:

АХ = В,.

. (7).

Обозначим через А₁(а₁₁, а₂₁, …, а_g1), А₂(а₁₂, а₂₂, …, а_g2), …, А_n(а_1n, а_2n, …, а_gn) и B₀(b₁, b₂, …, b_g) векторы-столбцы соответствующих матриц, тогда система (7) запишется в виде:

Требуется выполнение условия b_i > 0 для всех компонент вектора B₀, иначе нужно изменить знак у соответствующего уравнения. Необходимо найти все возможные базисные неотрицательные решения.

Базисное решение задается компонентами вектора в пространстве линейно независимых векторов, число которых определяется рангом исходной матрицы (т.е. максимальное число линейно независимых столбцов матрицы исходного уравнения). Матрица имеет ранг g, если хотя бы один определитель квадратной матрицы g-го порядка не равен нулю, а все определители матриц (g+1)-го порядка равны нулю. Таким образом, взяв из матрицы, А неособую квадратную матрицу наивысшего порядка (в рассматриваемом случае порядка g) и перенумеровав ее столбцы, получим искомый базис е₁, е₂, …, е_g.

Решая систему, разложим вектор В₀ в базисе е₁, е₂, …, е_g, затем отыщем положительные коэффициенты этого разложения. Полученные коэффициенты будут искомым решением, то есть координатами первой крайней точки множества G, а общее количество базисных решений равно .

Максимум линейной формы F будет обеспечивать набор из g векторов, выбранных из совокупности n векторов А₁, А₂, …, А_g, А_g+1, …, А_n. Так как F представляет собой гиперплоскость, «привязанную» к тому же началу, что и совокупность векторов А₁, А₂, …, А_n, то подстановка координат крайних точек в уравнение для F покажет, что эта плоскость проходит именно через эти точки. Отсюда можно определить все возможные расстояния крайних точек от плоскости F = 0. Наибольшее расстояние даст максимальное значение, а наименьшее — минимальное.

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

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

Библиографический список

• 1. Петриченко Г. С. Оценка качества корпоративных сетей при различных способах эксплуатации / Г. С. Петриченко, Н. Ю. Нарыжная, Л. М. Крицкая // Научный журнал КубГАУ [Электронный ресурс]. — Краснодар: КубГАУ, 2006. — № 19(03). — Шифр Информрегистра: 420 600 012 039. Режим доступа: http://ej.kubagro.ru/2006/03/17/
• 2. Петриченко Г. С. Выбор метода прогнозирования сложных систем АСУ в зависимости от ее модели // Г. С. Петриченко, Н. Ю. Нарыжная, Л. М. Крицкая // Научный журнал КубГАУ [Электронный ресурс]. — Краснодар: КубГАУ, 2005. — № 14(06). — Шифр Информрегистра: 140 506 014. Режим доступа: http://ej.kubagro.ru/2005/06/14/
• 3. Петриченко Г. С., Нарыжная Н. Ю., Дудник Л. Н. Диагностика и прогнозирование технического состояния компьютерной сети. Краснодар: Издательский Дом — ЮГ, 2010. — 188 с.
• 4. Петриченко Г. С., Нарыжная Н. Ю. Оптимизационное моделирование в повышении надежности компьютерной сети предприятия (статья) // Информатика: проблемы, методология, технологии: материалы XIII Международной научно-методической конференции, Воронеж, 7−8 февраля 2013 г. Т.3. / Воронежский государственный университет; Торгово-промышленная палата Воронежской обл.; НОЦ «Волновые процессы в неоднородных средах». — Воронеж: Издат.-полиграф. центр ВГУ, 2013. — С. 39−43.