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

Размещено на http://www.allbest.ru/

Удк 621.382

UDC 621.382

Кубанский государственный технологический университет, Краснодар, Россия

ПРИМЕНЕНИЕ ОПТИМИЗАЦИОННОГО МОДЕЛИРОВАНИЯ В РЕШЕНИИ ЗАДАЧ, ОЦЕНКИ ЭФФЕКТИВНОСТИ РАБОТЫ КОМПЬЮТЕРНОЙ СЕТИ

APPLICATION OF OPTIMIZATION MODELING AT DECISION OF TASKS, EVALUATION OF THE EFFECTIVENESS OF A COMPUTER NETWORK

Петриченко Григорий Семенович к.т.н., профессор

Нарыжная Наталья Юрьевна к.т.н.

Аннотация

В статье предлагаются решение задачи оптимального проектирования компьютерной сети на основе применения принципов самоорганизации

Ключевые слова: КОМПЬЮТЕРНАЯ СЕТЬ, ПРОИЗВОДИТЕЛЬНОСТЬ, ОПТИМИЗАЦИЯ, ЭФФЕКТИВНОСТЬ, НАДЕЖНОСТЬ, ГОТОВНОСТЬ, ОЦЕНКА

In the article, we have offered the solution of the problem of optimum design of a computer network on the basis of application of the principles of self-organization

Keywords: COMPUTER NETWORK, PERFORMANCE, OPTIMIZATION, EFFICIENCY, RELIABILITY, AVAILABILITY, ASSESSMENT

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

Оценивая эффективность работы сети, чаще всего выбирают такие критерии, как производительность и надежность, для которых в свою очередь необходимо выбрать конкретные показатели оценок, к примеру, время реакции на запрос, коэффициент готовности [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). - Шифр Информрегистра: 0420600012\0039. Режим доступа: http://ej.kubagro.ru/2006/03/17/

2. Петриченко Г.С. Выбор метода прогнозирования сложных систем АСУ в зависимости от ее модели // Г.С. Петриченко, Н.Ю. Нарыжная, Л.М. Крицкая // Научный журнал КубГАУ [Электронный ресурс]. - Краснодар: КубГАУ, 2005. - №14(06). - Шифр Информрегистра: 0140506014. Режим доступа: http://ej.kubagro.ru/2005/06/14/

3. Петриченко Г.С., Нарыжная Н.Ю., Дудник Л.Н. Диагностика и прогнозирование технического состояния компьютерной сети. Краснодар: Издательский Дом - ЮГ, 2010. - 188 с.

4. Петриченко Г.С., Нарыжная Н.Ю. Оптимизационное моделирование в повышении надежности компьютерной сети предприятия (статья) // Информатика: проблемы, методология, технологии: материалы XIII Международной научно-методической конференции, Воронеж, 7-8 февраля 2013 г. Т.3. / Воронежский государственный университет; Торгово-промышленная палата Воронежской обл.; НОЦ «Волновые процессы в неоднородных средах». - Воронеж: Издат.-полиграф. центр ВГУ, 2013. - С. 39-43.

1.Petrichenko G.S. Ocenka kachestva korporativnyh setej pri razlichnyh sposobah jekspluatacii / G.S. Petrichenko, N.Ju. Naryzhnaja, L.M. Krickaja // Nauchnyj zhurnal KubGAU [Jelektronnyj resurs]. - Krasnodar: KubGAU, 2006. - №19(03). - Shifr Informregistra: 0420600012\0039. Rezhim dostupa: http://ej.kubagro.ru/2006/03/17/

2.Petrichenko G.S. Vybor metoda prognozirovanija slozhnyh sistem ASU v zavisimosti ot ee modeli // G.S. Petrichenko, N.Ju. Naryzhnaja, L.M. Krickaja // Nauchnyj zhurnal KubGAU [Jelektronnyj resurs]. - Krasnodar: KubGAU, 2005. - №14(06). - Shifr Informregistra: 0140506014. Rezhim dostupa:

http://ej.kubagro.ru/2005/06/14/

3.Petrichenko G.S., Naryzhnaja N.Ju., Dudnik L.N. Diagnostika i prognozirovanie tehnicheskogo sostojanija komp'juternoj seti. Krasnodar: Izdatel'skij Dom - JuG, 2010. - 188 s.

4.Petrichenko G.S., Naryzhnaja N.Ju. Optimizacionnoe modelirovanie v povyshenii nadezhnosti komp'juternoj seti predprijatija (stat'ja) // Informatika: problemy, metodologija, tehnologii: materialy XIII Mezhdunarodnoj nauchno-metodicheskoj konferencii, Voronezh, 7-8 fevralja 2013 g. T.3. / Voronezhskij gosudarstvennyj universitet; Torgovo-promyshlennaja palata Voronezhskoj obl.; NOC «Volnovye processy v neodnorodnyh sredah». - Voronezh: Izdat.-poligraf. centr VGU, 2013. - S. 39-43.

Размещено на Allbest.ru