Методы поэтапной структурной отимизации магистральных корпоративных сетей

На правах рукописи

Бугров Дмитрий Анатольевич

МЕТОДЫ ПОЭТАПНОЙ СТРУКТУРНОЙ ОТИМИЗАЦИИ

МАГИСТРАЛЬНЫХ КОРПОРАТИВНЫХ СЕТЕЙ

05.13.01 – Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Нижний Новгород

2007

Работа выполнена на кафедре «Электронные вычислительные сети и машины» Нижегородского государственного технического университета

Научный руководитель – кандидат технических наук, доцент Семашко Алексей Владимирович.

Официальные оппоненты:

Доктор технических наук, профессор Крылов Владимир Владимирович

Кандидат технических наук, доцент Хранилов Валерий Павлович

Ведущая организация:

ОАО «Правдинское конструкторское бюро»

Защита диссертации состоится: 13 сентября 2007 г. в 15.00 на заседании диссертационного совета Д212.165.05 Нижегородского государственного технического университета, по адресу: 603600, Н.Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в научно-технической библиотеке Нижегородского Государственного Технического Университета.

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

Автореферат разослан «___» __________ 2007 г.

Ученый секретарь

диссертационного совета Э.С. Соколова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Работа направлена на повышение эффективности процессов модернизации и преобразования магистральных сетей связи. В настоящее время телекоммуникационные сети являются неотъемлемой частью жизнедеятельности человека, в современной мировой экономике эта отрасль имеет очень высокие темпы развития. Активно идет процесс создания сетей следующего поколения NGN, способных преодолеть архитектурные ограничения, свойственные традиционным сетям связи (телефонным, мобильным, передачи данных). Это достигается за счет реорганизации и оптимизации существующей сетевой архитектуры, выделения нового уровня управления услугами, слияния телекоммуникационных и информационных технологий, использования открытых протоколов. Все активнее используют информационные технологии в своей деятельности крупные организации. Огромное внимание при этом уделяется развитию сетей, основанных на цифровых технологиях передачи пакетов. Развитие ISDN услуг, IP телефонии и АТМ технологий ведет к слиянию телефонных сетей и передачи данных. Одни и те же каналы связи используются для передачи разнотипного трафика. Значительный объем информации приходит из публичных сетей, например, с Web-серверов, создавая при этом большой межсетевой трафик. Как следствие – резкое возрастание количества информации, передаваемой по магистральным линиям корпоративных сетей, перегрузка активного сетевого оборудования, отказы различных участков сети. Также наблюдается постоянный рост количества абонентов корпоративных сетей, вызывающий дополнительную нагрузку на магистральную сеть. Это связано как с общим увеличением числа компьютеризированных рабочих мест, пользующихся стандартными сервисами корпоративных сетей, так и с предоставлением новых сетевых услуг, генерирующих дополнительный трафик. Таким образом, в процессе эксплуатации корпоративной сети регулярно возникает задача модернизации и преобразования структуры существующей магистральной сети. Исследования в данном направлении ведутся в рамках различных правительственных программ по развитию связи и телекоммуникаций. Большое внимание задачам структурной оптимизации сетей уделяют производители оборудования, операторы связи, научно – исследовательские центры.

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

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

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

Цель работы: Повышение эффективности модернизации магистральных корпоративных сетей связи путем структурной оптимизации телекоммуникационных сетей.

Состояние рассматриваемых вопросов. Проблемой оптимизации корпоративных сетей занимались многие российские и зарубежные ученые: Иванова К.И., Кульгин М.В., Таненбаум Э., Шварц М., Янбых Г.Ф. и др. Тем не менее, задача оптимизации магистральных корпоративных сетей достаточно подробно не изучалась и для ее решения в настоящее время применяются эмпирические методы. Основной недостаток существующих методов состоит в том, что оптимизация магистральных корпоративных сетей проводится для одного периода времени, не учитывая длительности и этапности реализации проекта магистральной сети, и существование ограничений для каждого этапа. Кроме того, существующие алгоритмы поиска оптимальных и квазиоптимальных структур магистральных сетей не учитывают архитектурных особенностей современного сетевого оборудования и дискретности изменения пропускной способности каналов связи.

Задачи работы:

1. Формирование математической модели магистральной корпоративной сети для оптимизации структуры сети.
2. Разработка алгоритма позволяющего проектировать квазиоптимальные структуры магистральной корпоративной сети связи.
3. Поиск минимальной по стоимости структуры магистральной корпоративной сети при заданных ограничениях на ее технические характеристики.

Основные положения, выносимые на защиту:

1. Разработанная математическая модель магистральной корпоративной сети позволяет осуществлять структурную оптимизацию сети.
2. Адаптация генетического алгоритма для решения рассматриваемого класса задач позволяет улучшить характеристики сходимости алгоритма.
3. Синтезированный алгоритм оптимизации структуры магистральной корпоративной сети позволяет находить квазиоптимальный план поэтапной модернизации магистральной корпоративной сети.

Научная новизна диссертационной работы заключается в следующем:

1. Разработана математическая модель магистральной сети, которая, в отличие от известных, достаточно полно учитывает основные архитектурные особенности современного сетевого оборудования.
2. Впервые сформулирована и формализована задача поиска оптимального плана поэтапной модернизации структуры магистральной корпоративной сети по критерию стоимости при заданных ограничениях на ее технические характеристики.
3. Для решения задачи поиска оптимального плана поэтапной модернизации магистральной корпоративной сети применен и модифицирован генетический алгоритм. Новый способ кодирования хромосом позволяет описывать изменение структуры сети в течение нескольких временных периодов.
4. На основе модифицированного генетического алгоритма получен метод, позволяющий формировать квазиоптимальный план поэтапной модернизации магистральной корпоративной сети в течение нескольких временных периодов.

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

Практическая ценность:

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

Теоретическая значимость. Адаптация генетического алгоритма для решения задач подобного типа.

Сведения о внедрении. Результаты диссертационной работы были внедрены в следующих организациях:

- ООО «Волготрансгаз», г. Нижний Новгород. Для оптимальной расстановки коммутационного и оконечного оборудования в узлах связи применена программная реализация на базе разработанного алгоритма, в результате, полученная структура сети оказалась более дешевой и более надежной по сравнению с первоначальным вариантом проекта.

- ЗАО «СтартТелеком», г.Москва. Разработанный метод использован при создании рабочего проекта сети беспроводного широкополосного доступа WiMax, что позволило оптимально распределить финансовые ресурсы по времени, и минимизировать общую стоимость проекта.

- ООО «Кометех», г. Санкт-Петербург. Материалы диссертационной работы использованы в учебном процессе краткосрочных курсов повышения квалификации.

- ОАО «Волгателеком», г. Нижний Новгород. Разработанный метод использовался в процессе проектирования транспортной сети на основе волоконно-оптических линий связи, что позволило сократить затраты на модернизацию и повысить надежность сети.

- ООО «Оптические транспортные сети», г. Нижний Новгород. При разработке рабочего проекта «Транспортная сеть ОАО «ВымпелКом» II очередь» использована программная реализация предложенного метода.

- Программная реализация разработанного метода внедрена в учебный процесс НГТУ.

Публикации результатов. Результаты диссертации опубликованы в 10 работах, из них три статьи, материалы трех конференций, тезисы четырех докладов, в том числе 1 работа в издании рекомендованном ВАК.

Апробация результатов диссертации.

Диссертационная работа неоднократно рассматривалась на научных семинарах Института радиотехники и информационных технологий Нижегородского государственного технического университета, заседаниях технического совета ООО «Волготрансгаз», результаты работы обсуждались на семи научно-технических региональных и международных конференциях.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, библиографического списка и четырех приложений. Общий объем работы без приложений составляет 145 страниц текста, 36 иллюстраций. Библиографический список включает 118 наименований отечественных и зарубежных авторов.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 посвящена постановке задачи оптимизации магистральных корпоративных сетей. Кратко описываются наиболее распространенные сетевые технологии, используемые при проектировании корпоративных сетей в настоящее время. Описаны линии передачи, используемые при создании сетей связи: волоконно-оптические кабели, медные кабели, беспроводные технологии. Выделены их основные характеристики. Перечислены типы коммутационных устройств, которые используются в корпоративных сетях. Описаны оконечные устройства. Выделены основные этапы проектирования магистральных сетей, определены их характерные особенности. Описаны основные топологии построения корпоративных сетей. Рассмотрены три главных критерия эффективности магистральных сетей – производительность, надежность и стоимость. В качестве критерия оптимизации предложено использовать критерий суммарных затрат на модернизацию магистральной корпоративной сети. Определены входные и выходные данные в задаче оптимизации магистральной корпоративной сети.

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

С учетом особенности сетей и их основных критериев функционирования, в п. 2.2. сформулирована задача оптимального проектирования структуры корпоративной магистральной сети. Структура представляется в виде ненаправленного графа. Все параметры модели разбиты на три группы – входные параметры, выходные параметры, управляющие параметры.

Входные параметры – это исходные данные, задаваемые перед проектированием сети. К ним отнесены следующие параметры:

1. n – общее число узлов связи магистральной сети.

2. Предполагаемое изменение во времени матрицы тяготения F(t). Элементы матрицы описывают интенсивность информационных потоков между узлами сети для всех временных этапов модернизации.

3. Множество используемых типов линий связи (физических сред передачи) с их характеристиками. Наиболее часто используемые в магистральных сетях типы линий связи описаны в п.1.3. Собственные линии связи, прокладываемые организацией – владельцем сети, характеризуются высокой стоимостью прокладки, и низкой стоимостью владения. Арендуемые линии связи характеризуются нулевой стоимостью прокладки, и высокой стоимостью владения.

4. Множество интерфейсов подключения сетевых устройств U={ui}, элементы множества описывают возможные интерфейсы подключения коммутационных устройств, оконечных устройств, линий связи друг с другом.

5. Модельный ряд оконечных и коммутационных устройств: ,

M = {mi}.

6. Матрица возможности строительства новых линий связи P’(t), которая показывает возможность прокладки новых линий связи определенного типа между узлами связи в каждый временной период модернизации.

7. Матрица длины линий связи между различными узлами сети L. Она используется для расчета стоимости создания новых линий связи, и для проверки возможности применения сетевых интерфейсов между отдельными узлами сети при ограничении на максимальную длину канала связи.

8. Описание абонентских подключений к узлам связи, показывает количество каналов связи с определенным интерфейсом, используемых для подключения сетей доступа к коммутационным устройствам узлов связи в каждый временной период модернизации. Характеризуется временным рядом матриц A(t), размерностью nnu, показывающих общее количество портов с определенным интерфейсом, используемых для абонентских подключений в каждом узле связи.

9. Описание исходной структуры магистральной корпоративной сети осуществлено при помощи матриц коммутационных H(0) и оконечных устройств M’(0), установленных в узлах связи магистральной сети и матрицы проложенных линий связи P(0), в начальный момент времени.

10. План маршрутизации информационных потоков в магистральной сети в начальный момент времени:

S(0)={sij},

где sij – цепь ребер графа Г, ведущая из вершины i в вершину j.

Выходные параметры – это оценочные характеристики надежности, быстродействия, стоимости корпоративной магистральной сети. В качестве основных выходных параметров модели рассматривались следующие:

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

В общем виде затраты, которая несет организация - владелец сети во время проведения преобразований, складываются из следующих основных позиций:

• затраты на прокладку новых магистральных линий связи Eлс;
• затраты на аренду подключаемых линий связи и на обслуживание действующих каналов связи Eэлс;
• затраты на закупку нового коммутационного оборудования Eку;
• затраты на закупку нового оконечного оборудования Eоу;
• затраты на обслуживание коммутационных устройств Eэку.

Затраты за каждый период проведения модернизации сети - E(t), необходимо привести к одному временному периоду. В силу этого затраты приведены к начальному моменту времени, для чего они умножены на коэффициент дисконтирования с нормой дисконта r: , где .

Здесь Eлс(t) – затраты за временной период t на прокладку новых линий связи; Eку(t) – затраты за временной период t на закупку новых коммутационных устройств; Eоу(t) – затраты за временной период t на закупку новых оконечных устройств; Eэлс(t) – затраты в течение временного периода t на эксплуатацию действующих каналов связи и затраты на аренду линий связи; Eэку(t) – затраты в течение временного периода t на эксплуатацию установленных коммутационных устройств.

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

Для оценки производительности используется средняя задержка передачи пакета данных.

Управляющие - это параметры, которые можно менять в процессе поиска решения, влияя тем самым на выходные показатели. К ним относятся: