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

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

Автореферат

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

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

Оптимизации сетей с многопротокольной коммутацией по меткам

05.12.13 Системы, сети и устройства телекоммуникаций

Будылдина Надежда Вениаминовна

Новосибирск 2006

Работа выполнена на кафедре «Передача дискретных сообщений и метрологии» в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики»

Научный руководитель - доктор технический наук, профессор Шувалов В.П.

Научный консультант - кандидат технических наук, доцент Субботин Е.А.

Официальные оппоненты: - доктор технических наук, профессор Доросинский Л.Г.

-кандидат технических наук, доцент Егунов М.М.

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

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

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

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

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

Вопросам оптимального распределения трафика посвящено множество работ и задача чаще всего формулируется следующим образом - требуется найти кратчайший путь, обеспечивающий минимальную стоимость при наличии определенных ограничений. Решению такого рода задач посвящены работы как российских ученых Вишневского В.М., Бочарова П.П, Зайченко Ю.П., Гонта Ю.В., и др., так и зарубежных Хемди А.Таха, M.S.Garey, D.S.Johnson, G.Cornuejols, M.L.Fisher, B.Fortz. и др.

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

Цель работы. Целью диссертационной работы является разработка алгоритмов оптимизации сети с многопротокольной коммутацией по меткам (MultiProtocol Label Switching, MPLS), обеспечивающих повышение производительности за счет более эффективного распределения ресурсов пропускной способности магистральных каналов связи между набором заданных путей с коммутацией по меткам (Label Switched Path, LSP), перераспределения нагрузки между LSP в условиях изменения трафика в сети. В рамках выше изложенного решаются следующие задачи:

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

2. Разработка, на основе использования метода неопределенных множителей Лагранжа, алгоритма оптимизации модифицированной функции затрат, которая включает ограничения пропускной способности для каждого класса обслуживания (при предоставлении дифференцированных услуг), а также коэффициенты отказоустойчивости трактов, которые используются для уточнения значений пропускной способности резервных LSP.

3. Разработка программ для автоматизации расчетов по оптимизации распределения потоков трафика.

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

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

Объект исследования. Объектом исследования являются сети c многопротокольной коммутацией по меткам и их оптимизация.

Научная новизна:

В процессе исследования получены следующие результаты:

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

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

3. Созданы программы определения оптимального дизайна LSP методами линейного программирования и предлагаемого эвристического, выбора кратчайшего пути с использованием алгоритма Дейкстра, программы расчета коэффициентов отказоустойчивости трактов.

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

Результаты диссертационной работы использованы при постановке курсов лекций по дисциплинам «Системы документальной электросвязи », «Передача дискретных сообщений», «Протоколы компьютерных сетей и сетевые операционные системы» в ГОУ ВПО «СибГУТИ».

Разработанные алгоритмы оптимизации использованы при составлении проекта модернизации мультисервисной сети связи ОАО «Уралсвязьинформ» для оптимизации потоков при изменяющейся нагрузке.

Материалы диссертационной работы вошли: в учебное пособие «Телекоммуникационные системы и сети», том 3. Мультисервисные сети (гл.4. Многопротокольная коммутация по меткам.), в учебное пособие «Технологии глобальных компьютерных сетей»; монографию «Телекоммуникационные сети с многопротокольной коммутацией по меткам. Построение и оптимизация».

Апробация работы. Основные положения работы докладывались на следующих конференциях и семинарах:

1. Научно-практической конференции «Электронная Россия-стратегия развития г. Екатеринбурга и Уральского региона» в рамках выставки URALNET - сетевые технологии и решения, Екатеринбург, Уралэкспоцентр,2003г.

2. Международной научно-практической конференции «Связь-ПРОМ 2004»

1-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2004», Екатеринбург,2004г.

3. Научно-практической конференции «Электронная Россия - стратегия развития реальной инфраструктуры инфокоммуникаций», Екатеринбург, Уралэкспоцентр, 2004г.

4. Международной научно-практической конференции «Связь-ПРОМ 2005» 2-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2005», Екатеринбург,2005г.

5. Международной научно-практической конференции «Связь-ПРОМ 2006» 3-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2006», Екатеринбург,2006г.

6. Международной практической конференции «Современные научные достижения-2006», Белгород,2006г. http://www.rusnauka.com /SND/Tecnic.htm;

7. Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск,2005г.

Основные результаты выносимые на защиту:

1.Эвристический алгоритм определения оптимального дизайна LSP в сетях MPLS;

2.Методика расчета коэффициентов отказоустойчивости трактов, которые используются для уточнения значений пропускной способности резервных LSP;

3.Алгоритм оптимизации маршрутов с учетом ограничений по классам обслуживания потоков трафика, в основу которого положен метод неопределенных множителей Лагранжа;

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

Публикации. Основные результаты работы были отражены в 16 печатных работах в том числе в монографии и двух учебных пособиях.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Содержит 124 страницы основного текста, 6 таблиц, 27 рисунков, включает в себя 5 приложений на 89 листах. Список литературы составляет 96 наименований.

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

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

В первой главе рассмотрены особенности и способы управления трафиком в сетях с многопротокольной коммутацией по меткам (MultiProtocol Label Switching, MPLS) и представлены пути совершенствования технологии MPLS, дан обзор методов оптимизации IP/MPLS сетей, сформулированы задачи оптимизации сетей IP/MPLS.

Цель использования многопротокольной коммутации по меткам (MultiProtocol Label Switching, MPLS) состоит, прежде всего, в более эффективном использовании пропускной способности магистральных каналов связи, а также в построении современной сетевой инфраструктуры на основе оптических технологий для организации высокоскоростной магистральной сети и единой системы сигнализации, позволяющей объединять различные типы сред и систем передачи информации. Данная технология позволяет ускорить продвижение IP - пакетов и сохранить гибкость, характерную для IP сетей, с помощью механизмов управления трафиком и принципов поддержания качества обслуживания, применяющихся в сетях АТМ. Важно и то, что MPLS может использоваться не только с АТМ, но и с любой другой технологией канального уровня. MPLS использует и развивает концепцию виртуальных каналов, используемых в сетях Х.25, Frame Relay, объединяя ее с техникой выбора путей на основе информации о топологии и текущей загрузке сети, получаемой с помощью протоколов маршрутизации сетей IP. MPLS - это технология быстрой коммутации пакетов в многопротокольных сетях, основанная на использовании меток. «Многопротокольность» в названии технологии означает, что MPLS - инкапсулирующий протокол и может транспортировать множество других протоколов. MPLS - это один из шагов на пути эволюционного развития сети Интернет в сторону упрощения ее инфраструктуры, путем интеграции функций второго (коммутация) и третьего (маршрутизация) уровней. С ее помощью можно решать следующие задачи:

-интеграцию ATM и Frame Relay с IP;

-ускоренное продвижение пакетов внутри сети оператора вдоль кратчайших традиционных маршрутов;

-создание виртуальных частных сетей (VPN);

-выбор и установление путей со сбалансированным распределением загрузки ресурсов (Traffic Engineering, TE).

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

Технология MPLS постоянно совершенствуется в направлении адаптации к условиям передачи трафика в сетях, обеспечивая поддержку QoS. В решении этих задач неоценимый вклад внесли такие исследователи как Вишневский В.М., Awduche D.О., Malcolm J.,Agogbua J.,ODell M., McManus J., M.S.Garey, D.S.Johnson, G.Cornuejols, M.L.Fisher, B.Fortz. R.Widyono,и др.

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

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

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

Предлагаемый эвристический алгоритм, позволяет производить быстрое изменение дизайна LSP, что чрезвычайно важно в условиях меняющегося характера трафика сети. Алгоритм отличается от известных методов распределения многопродуктовых потоков тем, что он рассматривает не каждое в отдельности взятое требование на распределение потоков, а все одновременно заданные в трафик-матрице. На каждом итерационном шаге алгоритма распределяется многопродуктовый поток с интенсивностью ( - повышающий коэффициент, t_i,j - трафик) между всеми истоками и стоками. Опишем алгоритм по шагам.

Шаг 1. Рассматриваемая топология. Топология сети на каждом итерационном шаге состоит из ребер , пропускная способность (С) которых отлична от нуля: и коэффициент использования ребра . В начале работы алгоритма потоки отсутствуют:

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

Если путь от к для некоторого ненулевого элемента трафик-матрицы отсутствует, алгоритм продолжает свою работу с шага 3.

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

,

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

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

Шаг 4. Перенаправление путей потоков, которые пересекают разрез в двух направлениях. В случае, если , пропускная способность разреза, возможно используется:

Либо для требований на распределение потоков , истоки (или стоки ) которых не принадлежат множеству вершин источников (или множеству вершин потребителей ).

Либо для потоков, которые на своем пути от источника во множестве к потребителю во множестве много раз пересекают разрез (проходят через несколько ребер разреза).

Первый случай может быть разбит на два подпункта:

многопротокольный коммутация метка сеть

(1)

(2)

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

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

Для второго случая () поток будет пересекать разрез три и более раз.

Сравним алгоритмы поиска оптимального дизайна. Существует несколько параметров, по которым можно проводить сравнение алгоритмов оптимизации сетей MPLS. В данном случае сравнение мы будем проводить по сложности алгоритмов, по полученному весу дизайна LSP и по интегральному параметру, производящему комплексную оценку алгоритмов (время - качество).

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



Рисунок 1 - Сравнение сложности алгоритмов

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

Далее сравним веса полученного дизайна LSP. Для этого выберем некоторые графы с размерностью n от 3 до 10. И применим к ним метод линейного программирования и эвристический алгоритм. Далее сравним веса дизайнов LSP, полученных двумя этими методами (Рисунок 2).

Рисунок 2 - Сравнение веса дизайна LSP, полученного эвристическим алгоритмом (E1) и методом линейного программирования (S1)

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

и

соответственно для эвристического алгоритма и метода линейного программирования (Рисунок 3).

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

Рисунок 3 - Комплексная оценка

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

В третьей главе рассмотрены вопросы выбора оптимальных путей (LSP) с дифференциальным обслуживанием трафика при наличии нескольких ограничений. Решение поставленной задачи предлагается осуществить путем использования метода неопределенных множителей Лагранжа. Задача разбита на две части. В первой решается вопрос, связанный с необходимостью перенаправления потоков при выходе из строя ранее выбранного пути. Это приводит к увеличению нагрузки на «резервные» пути и, следовательно, к необходимости увеличения пропускной способности «резервных» путей на величину определенную так называемым коэффициентом отказоустойчивости. Во второй части, с учетом результатов полученных в первой, решается задача выбора квазиоптимальных путей.

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

1.Для каждого запроса между парой узлов, топологии сети, необходимо:

- Запустить алгоритм Дейкстра и определить наиболее короткий путь между источником и получателем запроса.

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

Для трактов (е_i), формирующих новый выбранный путь, увеличить счетчик использования на единицу: U(е_i)_c = U(е_i)_c + 1.

2. Для каждого тракта необходимо рассчитать соответствующий коэффициент отказоустойчивости г() как функцию его использования в резервных путях:

,

где - общее число запросов.

После расчета всех г() решается задача оптимизации, с учетом резервирования пропускной способности для различных классов трафика и обеспечения отказоустойчивости. Для резервирования полосы пропускания, введем одномерный массив ограничений пропускной способности (ВС) ВС = [ВС₀, ВС₁,…, ВС₇].

Определим следующую целевую функцию:

F = , (3)

где C_ph(е_i) - общая пропускная способность тракта е_i.

Необходимо удостоверится, что переменные (i,j)(значения пропускной способности части тракта е_i, предназначенной для наложенной сети MPLS для разных классов обслуживания сети) являются положительными (рисунок 4) {1}, также нужно удостовериться, что после разделения запроса более чем на один маршрут, общая величина запроса остается такой же {2}, кроме того, полагаем, что общая пропускная способность для CT_n тракта е_i задается суммой всех частей трафика, относящихся к CT_n, который маршрутизируется по е_i {3}, и полагаем, что общая пропускная способность физического тракта C_ph(е_i) задается суммой всех существующих классов трафика CT_n на данном тракте {4}, и в конечном счете, принимаем ограничения пропускной способности заданные с помощью модели Русской Матрешки {5}.

Задано
Найти
Минимизировать
При условии	{1}
	{2}
	{3}
	{4}
	{5}

Рисунок 4 - Формулировка задачи оптимизации планирования

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

Алгоритм оптимизации на основе множителей Лагранжа, основан на минимизации измененной целевой функции

,

где д_i представляет собой множители Лагранжа, которые необходимо найти с помощью предложенного алгоритма. Если все д_i равны нулю и все ограничения (рисунок 4) не нарушены, тогда найдено оптимальное решение задачи. Если ограничения не выполняются, тогда необходимо увеличить значения д_i для того, чтобы увеличилась их значимость в новой целевой функции F. Далее покажем, как найти значения д_i, для достижения наилучших результатов.

Для начала необходимо устранить ограничения {4} и {5} при помощи включения их в другие ограничения и целевую функцию. Далее необходимо ослабить условия ограничения {2} и {3} при помощи включения их в новую целевую функцию. Если найденное решение не удовлетворяет ограничениям, то необходимо увеличить коэффициенты при ограничениях (при помощи увеличения значения соответствующего множителя) в измененной целевой функции, приближая тем самым решение к оптимуму. Далее более подробно опишем предложенный эвристический алгоритм. В предлагаемом алгоритме оптимизации, на основе множителей Лагранжа, для решения вышеописанной задачи для поиска множителей Лагранжа используется метод субградиентной оптимизации. Пусть и будут любыми исходными значениями. При использовании субградиентной оптимизации, определим значения и следующим образом:

(4)

(5)

Выражение обозначает среднее значение пропускной способности для всех путей между парой узлов (i,j), маршрутизируемых по физическому тракту .

В данных выражениях запись []⁺ означает положительную часть , которая равна max(,0).

Значение (i,j)^k представляет собой решение подзадачи Лагранжа при . Переменная представляет собой длину шага при k-ой итерации.

(6)

(7)

В выражениях (6), (7) верхний предел оптимального значения целевой функции, а является скалярной величиной, выбранной между 0 и 2. Верхняя граница является значением целевой функции любого известного подходящего решения задачи оптимизации. После начала работы алгоритма возможно изменение данного значения (), для создания лучшего решения (то есть менее затратного). На рисунке 5 представлен алгоритм оптимизации, на основе множителей Лагранжа. После нахождения множителей Лагранжа, для каждого физического тракта рассчитывается . Последним шагом является расчет .

Величины МАХ и являются постоянными и обозначают, соответственно, максимальное число шагов и наименьшее значение . Оба эти значения используются как условия остановки алгоритма оптимизации, на основе множителей Лагранжа.

Задано
1.	рассчитывается с использованием 6 и 7
2.	рассчитывается с использованием 4 и 5
3.	Перейти на шаг 6, если выполняется одно из следующих условий:
	· Общее число шагов равно MAX=150
	·
	·
4.	Если не уменьшается за 4 шага, то необходимо уменьшить в 2 раза;
5.	, перейти на шаг 1.
6.	Используем значения, полученные для , и рассчитываем и следующим образом:
7.	Возврат

Рисунок 5 - Алгоритм оптимизации на основе множителей Лагранжа

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

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

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

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

Для проверки контроля параметров качества в сети IP\MPLS использовался метод имитации трафика, а также программы определения коэффициента отказоустойчивости связи для определения запаса устойчивости сети при увеличении потока передаваемой информации или в случае неисправности трактов сети. Результаты теста показали положительный результат.

Представленная в диссертации методика может быть использована при развертывании опытной зоны или пуско-наладочных испытаний нового сегмента, что позволяет выяснить все потенциально возможные «узкие места», минимальный разрез в сети, которые могут возникнуть в сети через 1 -2 года после начала эксплуатации. При эксплуатации, в случае внедрения новых услуг, изменения плана маршрутизации и т.д. любые изменения в структуре трафика могут привести к негативным последствиям на сети. Используя разные классы обслуживания и измеряя коэффициенты отказоустойчивости связи, можно посмотреть реакцию сети на изменение структуры трафика, или увеличения объема передаваемой информации в сети, а также в случае возникновения неисправности трактов.

Результаты проверок качества телефонной связи и реализации дополнительных услуг на базе оборудования Softswitch ОАО «Уралсвязьинформ» г.Екатеринбурга, представлены в протоколах, хранящихся в ОАО ««Уралсвязьинформ». Краткие выводы, которые можно сделать по результатам испытаний сводятся к следующему:

1. С увеличением нагрузки на линию, сеть работает устойчиво и перераспределяет трафик менее, чем за 50 мс;

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

3. Потерь вызовов на линии связи так же не наблюдалось.

В заключении - сформулированы основные результаты, полученные в работе:

1. Рассмотрены алгоритмы оптимизации сетей MPLS и существующие подходы к решению задачи оптимизации (определения оптимального дизайна LSP), а также предложен эвристический метод пропорционального распределения потоков, который позволяет получить квазиоптимальный дизайн LSP.

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

3. Разработаны программы, которые позволяют автоматизировать процесс оптимизации распределения потоков трафика с использованием симплекс-метода и эвристического метода. Эти программы могут быть использованы в маршрутизаторах на сетях IP/MPLS.

4. На основе использования метода неопределенных множителей Лагранжа разработан алгоритм оптимизации поиска пути коммутации по меткам (LSP), с учётом ограничений по пропускной способности на каждый класс обслуживания и также коэффициентов отказоустойчивости трактов, которые используются для уточнения значений пропускной способности каждого тракта, с учетом появления неисправностей в LSP.

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

Публикации по основным результатам диссертации

1. Будылдина Н.В. Технология MPLS (MultiProtocol Label Switching). Теория, техника и экономика сетей связи. Сборник научно-технических и методических трудов, Выпуск 1, 2003, Екатеринбург, УрТИСИ,2003г.- с.148-152.

2.Будылдина Н.В. Развитие технологий маршрутизации MPLS в сетях передачи данных. Материалы научно-практической конференции «Электронная Россия-стратегия развития г. Екатеринбурга и Уральского региона» в рамках выставки URALNET- сетевые технологии и решения, Екатеринбург, Уралэкспоцентр,2003г.- с.18-20.

3. Клестов В.В., Будылдина Н.В. Использование технологии обобщенной многопротокольной коммутации по меткам (GMPLS) в мультисервисных сетях. Сборник научно-технических и методических трудов, «Теория, техника и экономика сетей связи» Выпуск 3, 2004, Екатеринбург, УрТИСИ,2004г.- с.127-130.

4. Будылдина Н.В. Мультипротокольные сети на основе MPLS (MultiProtocol Label Switching)//Научные труды международной научно-практическаой конференции «Связь-ПРОМ 2004» в рамках 1-го ЕВРО-АЗИАТСКОГО МЕЖДУНАРОДНОГО ФОРУМА «Связь-ПРОМЭКСПО 2004», Екатеринбург ЗАО «Компания Реал-Медиа»,2004г.- с.18-23.

5.Будылдина Н.В. Многопротокольная коммутация по меткам//Научно-практическая конференция «Электронная Россия-стратегия развития реальной инфраструктуры инфокоммуникаций», Екатеринбург, Уралэкспоцентр, 2004г.- с.48-54.

6.Будылдина Н.В., Алгоритм оптимизации телекоммуникационных сетей с многопротокольной коммутацией по меткам// Труды Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск,2005г.- с.62-64.

7.Будылдина Н.В. Основные достоинства, обуславливающие распространение GMPLS. Теория, техника и экономика сетей связи. Сборник научно-технических и методических трудов, Выпуск 4, Екатеринбург, УрТИСИ,2005г.- с.12-19

8.Н.В.Будылдина Перспективы использования технологии многопротокольной коммутации меток на сетях «Уралсвязьинформ»//Труды Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск,2005г.- с.58-62.

9.В.В.Величко, Е.А.Субботин, В.П.Шувалов и др. Телекоммуникационные системы и сети. Учебное пособие. Мультисервисные сети. Том 3. гл.4.Многопротокольная коммутация по меткам. Москва, горячая линия-Телеком,2005г.- с.100-124.

10.Будылдина Н.В. Внедрение технологии многопротокольной коммутации меток на сетях в Уральском регионе. Международная научно-практическая конференция «Связь-ПРОМ 2005» 2 ЕВРО-АЗИАТСКОГО МЕЖДУНАРОДНОГО ФОРУМА «Связь-ПРОМЭКСПО 2005», Екатеринбург,УрТИСИ.2005 г.- с.61-65.

11. Будылдина Н.В. Оптимизация коммутируемых по меткам трактов //Труды учебных заведений связи /СПбГУТ. СПб, 2006. №174, с 136 - 142

12.Будылдина Н.В. Определение оптимального дизайна LSP в сетях с многопротокольной коммутацией меток. Международная практическая конференция «Современные научные достижения - 2006», Белгород, 2006 г. http://www.rusnauka.com/SND/Tecnic.htm

13.Будылдина Н.В. Технологии глобальных компьютерных сетей. Учебное пособие. Екатеринбург, УрТИСИ, 2006г.- 264 с.

14.Будылдина Н.В., Шувалов В.П. Построение коммутируемого пути по меткам (LSP) в сетях MPLS. Материалы 3 Международной научно-практической конференции «Связь-ПРОМ 2006». 3-его ЕВРО-АЗИАТСКОГО МЕЖДУНАРОДНОГО ФОРУМА «Связь-ПРОМЭКСПО 2006», Екатеринбург, ЗАО «Компания Реал-Медиа, 2006г.- с.145-148.

15.Будылдина Н.В., Шувалов В.П. Основные задачи управления трафиком в сетях MPLS. Материалы 3 Международной научно-практической конференции «Связь-ПРОМ 2006» 3 -его ЕВРО-АЗИАТСКОГО МЕЖДУНАРОДНОГО ФОРУМА «Связь-ПРОМЭКСПО 2006», Екатеринбург, ЗАО «Компания Реал-Медиа,2006 г.- с.151-153.

16.Будылдина Н.В., Шувалов В.П. Телекоммуникационные сети с многопротокольной коммутацией по меткам. Построение и оптимизация. Монография, Екатеринбург, 2006г.-287 с.

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