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

Мухамадиева З. Б. Алгоритмы оптимальной структуры компьютерной сети // Молодой ученый. — 2015. — №22. — С. 29-30.



 

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

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

 

При выборе структуры компьютерных сетей решаются следующие задачи: заменять сетевое оборудование или физические каналы связи, изменить полную структуру компьютерной сети или заменить часть оборудования сети и т. д. В данной статье описывается алгоритм, который позволяет оптимизировать такой процесс, как инновация сети по следующим параметрам: конфигурация, пропускная способность и стоимость оптимизации. На сегодняшний день имеется достаточно много распределенных компьютерных сетей, которые охватывают большие площади и обслуживают большое количество абонентов сети. Основная черта эксплуатации таких компьютерных сетей — это соединение пакетных систем передачи данных и мультимедийных сетей. Данная тенденция приводит к резкому возрастанию объема информации, который передаётся по сети. Хотя изначально сеть предназначалась для передачи только одного типа трафика. Эта же тенденция приводит и к перегрузке сетевого оборудования, и к отказам различных участков сети. Постоянно растущий объем трафика и несовершенство существующих компьютерных сетей делают задачу оптимизации существующей сети актуальной. Типовая задача оптимизации сети, выглядит следующим образом. Начальные условия следующие: действующие сети, которые являются источниками и потребителями трафика; информация об объёме трафика между абонентами; имеющиеся узлы связи, в которых находится коммуникационное оборудование; возможность создания новых физических линий связи; доступное коммутационное сетевое оборудование [2]. Допустим, инновация компьютерной сети будет состоять в том, чтобы установить новое коммутационное оборудование, заменить старое оборудование, перераспределить информационные потоки. При этом при всём нужно будет учитывать некоторые ограничения на качество связи и надежность линий связи. При этом также нужно будет учитывать предполагаемый рост трафика, возможность подключения новых узлов связи, прокладку новых линий связи. При осуществлении оптимизации компьютерной сети сначала необходимо составить план оптимизации и развития сети. Планирование происходит, исходя из ограничений на характеристики качества надежности сети и качество связи, а также на предполагаемое количество новых узлов связи и предполагаемый рост трафика. Таким образом, инновация сети сводится к поиску оптимальной структуры компьютерной сети [4]. При решении данной задачи возникают трудности, связанные с ростом времени выбора оптимальной структуры при увеличении числа узлов сети. А в компьютерной сети большой размерности поиск оптимального решения осуществить невозможно за приемлемое время. Таким образом, необходимо разработать алгоритм выбора оптимального решения. Задача оптимизации, с математической точки зрения, сводится к тому, чтобы найти максимум или минимум целевой функции от многих переменных, на функциональные связи и значения которых наложены определенные ограничения. Подобная оптимальная задача оптимизации сети сводится к задаче нелинейного целочисленного программирования. Целевая функция и ограничения являются нелинейными выражениями. В этих выражениях имеются целочисленные переменные. Трудности в решении целочисленных и комбинаторных задач оптимизации привели к созданию большого количества методов и алгоритмов их решения. Существующие методы решения подобных задач делятся на два класса. Первый класс составляют методы, приводящие к нахождению оптимального решения, но на практике такие методы не могут быть применимы. Так как они требуют недопустимо большое количество операций. Второй класс составляют методы, которые не всегда приводят к нахождению оптимального решения. Но такие методы используют приемлемое количество операций [1]. Данные методы являются общими, их обычно применяют при небольшой размерности задачи. В основном, применяются методы сокращенного перебора. Приемы перебора «ветвей и границ» или «неявного» перебора состоят в том, чтобы найти частное решение, представленное в виде дерева выбора. Подобные алгоритмы используют организацию выбора с возвращением. Иногда процесс выбора организован по-другому. Для того чтобы реализовать такие методы требуется большое количество машинного времени и огромный объем оперативной памяти. Поэтому в этом направлении работы ведутся в сторону выбора таких способов, которые позволили бы сократить число операций и объём необходимых ресурсов. И такие способы найдены. Это делается за счет отказа от выбора глобального экстремума [3]. Однако и такие методы не подходят для задач сети с большой размерностью. Методы эволюционного моделирования показывают хорошие результаты при решении задач нелинейной целочисленной оптимизации. Для решения описанной задачи будет использован один из методов эволюционного моделирования, а именно генетический алгоритм. Генетический алгоритм, обычно используется для решения задач оптимизации и моделирования путём случайного подбора, а также комбинирования и вариации искомых параметров. В сетях связи часто в качестве критерия оптимизации применяется стоимость самой оптимизации. Естественно, её необходимо минимизировать, надежность и требования к задержке пакета определяются в качестве ограничений [4]. Для определения используемых моделей оконечного оборудования и сетевых устройств необходимо определить, как распределяются информационные потоки в сети. На каждом временном интервале выбирается случайным образом какое-то количество оконечных устройств на линиях связи. Фиксируется при этом пропускная способность каналов связи с выбранными оконечными устройствами. Считается неограниченной сверху пропускная способность других каналов. На полученной структуре решается затем задача распределения потоков. Затем для полученного распределения вычисляются оставшиеся незафиксированные оконечные устройства так, что пропускная способность будет больше требуемой пропускной способности канала связи. Эффективность работы представленного генетического алгоритма зависит от правильного выбора его параметров, а именно вероятностей применения генетических операторов. Методы отбора в следующие поколения также влияют на эффективность алгоритма. Выбор мощности популяции и момент окончания выбора решения оказывают своё влияние на эффективность алгоритма. Если эти параметры неправильно определить, то увеличится время выбора или ухудшится качество найденного решения. Полученный алгоритм может быть использован для проведения оптимизации компьютерной сети.

 

Литература:

 

  1.                Иванова Т. И. Корпоративные сети связи [Текст]. — М., 2001. — 282с.
  2.                Коханович Г. Ф., Чуприн В. М. Сети передачи пакетных данных [Текст]. — К.:«МК-Пресс», 2006. — 272с.
  3.                Мусина А. А. Модернизация компьютерной сети. Статья с конференции. 2015г 213–215 стр.
  4.                Филимонов А. Построение мультисервисных сетей Ethernet [Текст]. — CПб.:БХВ- Петербург, 2007. — 592с.

Обсуждение

Социальные комментарии Cackle