автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка и исследование алгоритмов оптимизации сетей с многопротокольной коммутацией по меткам

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

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ ОПТИМИЗАЦИИ СЕТЕЙ С МНОГОПРОТОКОЛЬНОЙ КОММУТАЦИЕЙ ПО МЕТКАМ

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

Автореферат Диссертации на соискание ученой степени кандидата технических наук

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

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

Защита состоится « 10 » ноября 2006 г.в КО часов в ауд.625 на заседании диссертационного совета Д 219.005.01 при ГОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики» по адресу: 630102, Новосибирск, ул. Кирова,Йб.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «СибГУТИ»

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

Официальные оппоненты: - доктор техшгческнх наук, профессор

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

Ведущая организация - институт математики и механики Уральского отделения Российской Академии наук

Автореферат разослан « Ц ючл^ 2006 г.

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

диссертационного совета Д 219.005.01 кандидат технических наук, профессор

Б.И. Крук

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

отказоустойчивости трактов, а также обеспечении заданного уровня QoS с учётом дифференцированного обслуживания (DifíServ).

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

Разработанные алгоритмы оптимизации использованы прп составлении проекта модернизации мультисервисной сети связи ОАО

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

Материалы диссертационной работы вошли: в учебное пособие «Телекоммуникационные системы и сети», том 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.ru snauka.com/SNP/Tecnic .htm:

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

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

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

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

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

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

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

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

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

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

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

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

транспортировать множество других протоколов. MPLS - это одни из шагов на пути эволюционного развития сети Интернет в сторону упрощения ее инфраструктуры, путем интеграции функций второго (коммутация) и третьего (маршрутизация) уровней. С ее помощью можно решать следующие задачи: -интеграцию ATM и Frame Relay с IP;

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

традиционных маршрутов;

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

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

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

Технология MPLS постоянно совершенствуется в направлении адаптации к условиям передачи трафика в сетях, обеспечивая поддержку QoS, В решении этих задач неоценимый вклад внесли такие исследователи как Вишневский В.М., Awduche D.O., Malcolm J.,Agogbua J„0'DeII M., McMamis J., M.S.Garey, D.S.Johnson, G.Comuejols, M.L.Fisher, B.Fortz, R.\Vidyono,H др.

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

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

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

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

^ ~ повышающий коэффициент, t¡j - трафик) между всеми истоками и стоками. Опишем алгоритм по шагам.

Шаг 1. Рассматриваемая топология. Топология сети на каждом итерационном шаге состоит из ребер еЕ, пропускная способность (С) которых отлична от нуля: c(et) > 0 и коэффициент использования ребра р(ек) < 1. В начале работы алгоритма потоки отсутствуют: Шаг 2 .Распределение потоков. Для каждого требования на распределение потока в трафик-матрице находится наикратчайший путь от источника v, к потребителю v;c учетом весов ребер v(et). Для поиска наикратчайшего пути используется алгоритм Дейксгра, так как он является наиболее простым из существующих, и соответствует всем необходимым требованиям.

Если путь от V| к для некоторого ненулевого элемента трафик-

матрицы > ® отсутствует, алгоритм продолжает свою работу с шага 3.

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

определяется из уравнения — = шах---L где - коэффициент

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

счете, для ребер достигается значение^е*^ —Такие ребра не обладают больше свободной пропускной способностью c(et) = 0, они исключаются из топологии - графа и не учитываются больше на последующих шагах выполнения алгоритма.

ШагЗ. Проверка на выполнение критерия минимального разреза. Если нет пути от истока vt к стоку v, для некоторого требования на распределение потока г„, то существует разрез S = (Vü, V2), состоящий из всех, не располагающих больше свободной пропускной способностью ребер. При этом минимальный разрез определяется либо через два комплиментарных множества вершин, либо как множество ребер, которые связывают некоторую вершину из множества источников V0 с определенной вершиной из множества потребителей Гг; таким образом, получаем: S = {(vjt,v„)e « Vz* v„ б Vq] . Для того чтобы выяснить, израсходована ли уже пропускная способность минимального разреза, определяют

пропускную способность разреза Cs = ^Гс(е) и сравнивают ее с суммой всех

t>¡ >

интенсивностей потоков fs = £ X х , которые должны пересекать разрез

в соответствии с трафик-матрицей. В случае выполнения равенства fs = Cs минимальный разрез найден, и алгоритм прекращает свою работу.

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

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

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

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

(1) V, eV0 л v„ еVQ

(2) уЛтГж л v„sVz

В случае (1) можно найти такие три вершины, две во множестве истоков 11 °Дна вершина во множестве стоков v., е Vz, дуть, вдоль которого определена часть рассматриваемого требования на распределение потока tb,, проходит сначала вершину v„, затем ребро разреза, потом вершину v„ (ила несколько вершин во множестве стоков V2) и оттуда, в конечном счете, пересекая разрез в обратном направлении через ребро, возвращается во множество истоков Vg через вершину v,2.

Для перенаправления потока проверяется, есть ли свободный путь между вершинами v(1 и v?3 внутри множества вершин-истоков VQ. Если такой путь между вершинами i>3, и vfJ существует, то можно освободить дополнительную пропускную способность разреза, перенаправив поток или его часть на этот путь. Аналогичным образом рассматривается случай (2) с одной лишь только разницей в том, что свободный путь, на который будет перенаправляться поток, необходимо искать внутри множества вершин-стоков Vz между вершинами vrf и v;J.

Для второго случая ( vt <= Ve л v,eVz) поток будет пересекать разрез три и более раз.

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

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

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

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

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

з I в в т в в »

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

Для проведения комплексной оценки алгоритмов введем интегральный параметр и. Полагаем, что он прямо пропорционален сложности алгоритма и получаемому этим алгоритмом весу дизайна ЬЭР. В данном случае

используем значения весов дизайна ЬБР, полученных в предыдущем шаге. *

ив*=0(—и = 0(4п*)х£1 соответственно для эвристического алгоритма

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

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

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

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

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

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

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

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

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

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

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

резервных путях: ?(«,) = где N^ - общее число запросов.

"в

После расчета всех решается задача оптимизации, с учетом

резервирования пропускной способности для различных классов трафика и

обеспечения отказоустойчивости. Дня резервирования полосы пропускания, введем одномерный массив ограничений пропускной способности (ВС) ВС = [ВС0, ВС],..., ВС7].

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

F- (3)

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

Необходимо удостоверится, что переменные xl (уХззачения пропускной способности части тракта eh предназначенной для наложенной сети MPLS для разных классов обслуживания сети) являются положительными (рисунок 4) {1}, также нужно удостовериться, что после разделения запроса более чем на один маршрут, общая величина запроса остается такой же {2}, кроме того, полагаем, что общая пропускная способность для СТ|) тракта ё-, задается суммой всех частей трафика, относящихся к СТ„, который маршрутизируется по ei {3}, и полагаем, что общая пропускная способность физического тракта Срь(е\) задается суммой всех существующих классов трафика СТ„ на данном тракте {4}, и в конечном счете, принимаем ограничения пропускной способности заданные с помощью модели Русской Матрешки {5}.

Задано G<V.Eи N

Найти

Минимизировать

При условии {1} o,vn,r

{3} 2>:(/.л-с,<«()

WJj«,)

(4} ¡£г<«()-С.(«>)-С„(«() Р-0

{5} ^Ся{е,)йБСг.С^е,)

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

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

представляет собой множители Лагранжа, которые необходимо найти с помощью предложенного алгоритма. Если все <5,- равны нулю и все ограничения (рисунок 4) не нарушены, тогда найдено оптимальное решение задачи. Если ограничения не выполняются, тогда необходимо увеличить значения 6t для того, чтобы увеличилась их значимость в новой целевой функции К Далее покажем, как найти значения ¿¡, для достижения наилучших результатов.

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

г

2 х'лл-вс,-g X /(ед 'х'ЛЖ (5)

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

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

Значение xJ*J)k представляет собой решение подзадачи Лагранжа при S = . Переменная Qk представляет собой длину шага при k-ой итерации.

^ ^»-g ^ ил

el

x*\Fm-<; (0*я

\1 Zx%i)-BC;± 1Ие,Ы(и)

(7)

В выражениях (б), (7) рца верхний предел оптимального значения целевой функции, а ^ является скалярной величиной, выбранной между 0 и

2. Верхняя граница является значением целевой функции любого

известного подходящего решения задачи оптимизации. После начала работы алгоритма возможно изменение данного значения для создания

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

Величины МАХ и 6 являются постоянными и обозначают, соответственно, максимальное число шагов и наименьшее значение Л^. Оба

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

Задано (з,°л,х^к = 1)

1. в*„ рассчитывается с использованием 6 и 7 2- рассчитывается с использованием 4 и 5

3. Перейти на шаг 6, если выполняется одно из следующих условий:

• Общее число шагов равно МАХ=] 50

• Хк =я

4. Если не уменьшается за 4 шага, то необходимо уменьшить Л* в 2 раза;

5. к = £+1, перейти на шаг 1.

6. Используем значения, полученные для ^(1,/), и рассчитываем С, (е,) и С^ (е,) следующим образом: С„(е,)= ][>;(/, У)

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, Екатеринбург, УрТИСИДООЗг,- с.148-152.

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

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

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

бЛ5удыллина Н.В., Алгоритм оптимизации телекоммуникационных сетей с многопротокольной коммутацией по меткам// Труды Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск^005г.- с .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. Xsl 74, с 136 - 142

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

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

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

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

Лицензия ЛР_020475, январь 1998 г. Подписано в печать /I.

Формат бумаги 62x84 1/16, отпечатано на ризографе, шрифт № 10,

Изд. л. 1, заказ Ш . тираж — 100 экз, СибГУТИ 630102, г. Новосибирск, ул. Кирова, 86.

Введение

Глава 1. Принципы построения сетей с использованием технологии 12 MPLS и задачи их оптимизации

1.1 .Определение основных целей и задач исследования. Общие понятия.

1 ^.Преимущества MPLS

1.3 .Проблемы распределения трафика и безопасности в сетях MPLS

1.4.Формирование трафика

1.5.Управление трафиком

1.6. Обеспечение QoS (качество услуг) 39 1.7.0бзор методов оптимизации трафика в IP/MPLS сетях 42 1.8.Выводы

Глава 2. Разработка метода распределения многопродуктовых потоков 49 2.1 .Модель для оптимизации 5 О

2.2.Цели оптимизации

2.3.Методы оптимизации

2.4.Принцип максимального потока (минимального разреза)

2.5.Линейное программирование 60 2.6.Эвристический метод определения оптимального дизайна

2.7.Сравнение алгоритмов поиска оптимального дизайна

2.8.Выводы

Глава 3. Оптимизация сетей IP/MPLS с дифференциальным обслуживанием

3.1 Формулировка задачи оптимизации

3.2 Эвристический алгоритм оптимизации

3.3 Метод повторной оптимизации 90 3.4.Численный пример 90 3.5.Выводы

Глава 4. Программы для оптимизации распределения потоков трафика в сетях IP/MPLS

4.1. Описание среды разработки программы

4.2. Назначение программы для определения оптимального дизайна LSP

4.3. Описание программного модуля для определения оптимального дизайна 104 4.4 Испытания сети IP\MPLS 110 4.5.Выводы 115 Основные результаты работы 116 Библиографический список литературы 117 Приложения

Как отмечалось в [57] основным принципом работы протоколов маршрутизации в сетях с коммутацией пакетов, вот уже долгое время является выбор маршрута на основе топологии сети без учета информации о текущей загрузке. Для каждой пары «адрес источника - адрес назначения» такие протоколы выбирают единственный маршрут, не принимая во внимание информационные потоки, протекающие через сеть. В результате все потоки между парами конечных узлов идут по кратчайшему маршруту (в соответствии с некоторой метрикой). Выбранный маршрут может быть более рациональным, например, если в расчет принимается номинальная пропускная способность канала связи или вносимые ими задержки, либо менее рациональным, если учитывается только количество промежуточных маршрутизаторов между исходным и конечным узлами.

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

С этой целью на сетях связи осуществляется внедрение новых сетевых технологий, таких как, многопротокольная коммутацией по меткам (Multiprotocol Label Switching, MPLS), которая обеспечивает гарантированную среднюю пропускную способность в соответствии с принципами инжиниринга трафика [29,12-24,57]. Наряду с этим, необходимо предусмотреть чтобы, сети были спроектированы с учетом необходимых методов оптимизации, которые позволят провайдерам максимально эффективно использовать имеющуюся инфраструктуру.

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

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

Обзор работ. Задачи, оптимизации при условии, что берется более или менее реальная сеть и оптимизация осуществляется по нескольким параметрам, относятся к классу сложных задач. Их решение с учетом ограничений требует большого объема вычислительных ресурсов и времени на реализацию. Поскольку выбор путей осуществляется в процессе работы сети, поэтому время вычислений оптимальных путей является основополагающим фактором. Вопросом оптимального распределения трафика посвящено множество работ, и задача чаще всего формулируется следующим образом - требуется найти путь, обеспечивающий минимальную стоимость при наличии определенных ограничений. Решению такого рода задач посвящены работы как российских ученых [27-28,40,43,45,48,58-61], так же и зарубежных [1,22,26,29-36,39,41,46,5256,62-95]. Учитывая актуальность вышеизложенной проблемы, диссертационная работа посвящена исследованиям в этой области и разработке новых более эффективных методов и алгоритмов оптимизации.

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

Так Хемди A. Таха рассматривает фундаментальные основы для понимания математического моделирования методов исследования операций в теории массового обслуживания. Вишневский В.М. рассмотрел алгоритмы выбора оптимальных потоков и определения оптимальных маршрутов в сетях передачи данных по критерию средней задержки. R.Widyono, предложил метод, маршрутизации, который позволяет определять оптимальный путь с самой низкой возможной стоимостью без влияния на задержки. Авторы R.Hassin, D.H.Lorenz, F.Orda, Danny Raz,Yuva Shavitt дали полностью полиномиальную схему аппроксимации по времени для проблемы пути с Минимальной Стоимостью и Ограниченной Задержкой. Kenji Ishida, Kitsutaro Amano предложили распределенный алгоритм, в котором узлы всегда выбирают наименьший по стоимости путь, пока не будут выполнены требования по задержке. Далее Shigang Cheng и Klara Nahrstedt, предлагают алгоритм для поиска пути, который удовлетворяет двум требованиям в полиномиальном времени, а Liang Guo и Ibrahim Matta, соответствующий путь, находят основанный на единственной стоимости нескольких метрик с разными коэффициентами веса.

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

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

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

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

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

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

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

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

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

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

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», Екатеринбург^006г.

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 наименований.

Основные результаты работы

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

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

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

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

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

1. Hakim Badis, Khaldoun А1 Agha. "A Distributed Algorithm for Multiple-Metric Link State QoS Routing Problem", Globecom 2003.

2. Шринивас Вегешна. "Качество обслуживания в сетях IP". Пер.с англ.-Москва, Санкт-Петербург, Киев, 2003.

3. Столингс В. "Современные компьютерные сети". Пер.с англ.- Москва, Санкт-Петербург, Нижний Новгород, Воронеж, Ростов-на-Дону, Екатеринбург, Самара, Киев, Харьков, Минск; Изд.-во «Питер», 2003.

4. Лукацкий А.С. "Неизвестная VPN", Компьютер Пресс. № 10.-октябрь,2001.

5. Олифер В.Г., Олифер Н.А. "Виртуальные частные сети на основе MPLS", Журнал сетевых решений LAN. № З.-март 2002.

6. Mannie Е. (ed.). "Generalized Multi-Protocol Label Switching Architecture", IETF Internet Draft, work in progress, draft-ietf-ccamp-gmplsarchitecture-07.txt, May 2003.

7. Kompella K. et al. "Routing Extensions in Support of Generalized MPLS", IETF Internet Draft, work in progress, draft-ietf-ccamp-gmpls-routing-09.txt.- October 2003.

8. Berger L. (Ed.). "Generalized Multi-Protocol Label Switching (GMPLS) Signaling Functional Specification", IETF Request for Comments, RFC 3471. -January 2003.

9. Rousseau B. and Papadimitriou D. "GMPLS. The Telecommunication holy grail or pragmatic means of raising carrier profitability? " Alcatel strategy White Paper, 2003.

10. Interfaces for the Optical Transport Network (OTN), ITU-T G.709,2003.

11. Алленов O.M. "Технология GMPLS: методы защиты и восстановления. Вестник связи. № 9.-сентябрь 2002.

12. Гольдштейн А.Б.,Гольдштейн Б.С. "Технология и протоколы MPLS", BHV, «БХВ-Санкт-Петербург»,2005.13. http://zxcv.stsland.ru/200 l05multiservice/index.htm

13. Дж.Ирвин, Д.Харль, "Передача данных в сетях: Инженерный подход". Учебное пособие. Пер.с англ.- «БХВ- Санкт-Петербург»,2003.

14. Олифер В., Олифер Н., Петрусов. Д., "ATM и MPLS: враги или союзники? ". Журнал сетевых решений LAN.№12.- декабрь 2002.

15. Марка Лассерре, "Межсоединение локальных сетей посредством MPLS", Журнал сетевых решений LAN. №1.-январь 2004.

16. Величко В.В., Субботин Е.А., Шувалов В.П., Ярославцев А.Ф., "Телекоммуникационные системы и сети т.З. Мультисервисные сети". Учебное пособие. М.: Горячая линия Телеком, 2005.

17. Сергей Орлов. "Перекресток миров". Журнал сетевых решений LAN.№5.-май 2004.

18. Будылдина Н.В, Шувалов В.П. "Телекоммуникационные сети с многопротокольной коммутацией по меткам". Построение и оптимизация. Монография. М.: УрТИСИ ГОУ ВПО СибГУТИ, 2005.

19. E.Rosen. RFC 2702. "Multiprotocl Label Switching Architecture".- September 2000.

20. SYRUS SYSTEMS-MPLS/ "Аттестационные и эксплуатационные испытания", http://www.syrus.ru/index.cgi

21. Awduche D.O., Malcolm J.,Agogbua J.,ODell M., McManus J., RFC "Requirements for Traffic Engineering over MPLS".//IFTF Draft,drifi-ietf-mpls-traffic-eng-00.txt. October 1998.

22. Соболев Д.В. "Защищенная телекоммуникационная сеть оператора связи на базе технологии IP-MPLS для построения корпоративной сети". Аналитический информационный журнал. Документальная электросвязь. №13.-август 2004.

23. Захватов М.А. "Вопросы безопасности в VPLS сетях". Аналитический информационный журнал. Документальная электросвязь.№ 13.-август 2004.

24. Нормативная рекомендация RFC 1918- частное адресное пространство.2000.

25. Alpar Juttner, Balazs Szviatovszki, Ildiko Mecs, Zsolt Rajk. "Lagrange Relaxation Based Method for the QoS Routing Problem", IEEE INFOCOM 2001.

26. Вишневский В.М., Ливнер Е.В., Федотов Е.В. "Математические модели исследования алгоритмов маршрутизации в сетях передачи данных".Информационные процессы,- Том 1, №2, 2001.

27. Поляк Б.Т. "Введение в оптимизацию".- М: Наука, 1983.

28. Kehang Wu and Douglas S. "Reeves Link Dimensioning and LSP Optimization for MPLS Networks Supporting DiffServ EF and BE traffic classes",2004.

29. Alpar Juttner, Balazs Szviatovszki,Aron Szentesi, Daniel Orincsay, Janos Harmatos "On-demand optimization of label switched paths in MPLS networks", IEEE 2000.

30. A. Feldmann and J. Rexford, "IP Network Configuration for Intradomain Traffic Engineering," IEEE Network, vol. 15, no. 5, pp. 46-57, September/ October 2001.

31. Christofides, N.: "Graph Theoriy- An Algorithmic Approach". New York: Academic Press, 1975

32. Franzke, Martin; Haftlinger, Gerhard; Schnitter, Stefan: "Performance and Applicability of MPLS-based Traffic Engineering Methods",2002.

33. Haftlinger, Gerhard; Schnitter, Stefan: "Optimized Traffic Load Distribution in MPLS Networks". In: Telecommunications Network Design and Management, Kluwer Akad. Publ, 2002.

34. Neuman, Klaus; Morlock, Martin: "Operations Research". Miinchen Wien: Carl HanserVerlag, 1993.

35. Э. Майника "Алгоритмы оптимизации на сетях и графах". М.: Наука, 1981.37. http://program.rin.ru/razdel/html/973.html "Оценка времени исполнения".38. http://algolist.manual.ru/maths/graphs/shortpath/ "Задача о кратчайших путях".

36. Haftlinger, Gerhard; Schnitter, Stefan: "Impact of Traffic Characteristics and Engineering on QoS in MPLS-based IP platforms", 2002.

37. Вишневский B.M. "Теоретические основы проектирования компьютерных сетей". М.: Техносфера,2003.

38. Мину М. "Математическое программирование. Теория и алгоритмы". Пер.с фр.-М.: Наука, 1990.

39. Fratta L., Gerla M., Kleinrock L. "The Flow Deviation Method: An Approach to Store-and-Forward Communication Networks", vol.3, 1973.

40. Тихомиров B.M. "Рассказы о максимумах и минимумах". М.: «Наука» Главная редакция физико-математической науки, 1986.44. http://www.opu.Odessa.ua/konsp/MMXTP/RAZDEL5/glava53 .htm.

41. Краснов M.JI и др. "Вариационное исчисление". Избранные главы высшей математики для инженеров и студентов Вузов. М.: «Наука», 1973.

42. Хемди А.Таха "Введение в исследование операций". Пер.с англ.-Издательский дом «Вильяме». Москва-Санкт-Петербург-Киев,2005.

43. Кристофидес Н. "Теория графов. Алгоритмический подход": Пер.с англ. -М.:, Мир, 1978.

44. Мизин И.А., Богатырев В.А., Кулешов А.П. "Сети коммутации пакетов". -М.:Радио и связь, 1986.

45. Олифер В., Олифер Н. "Новые технологии и оборудование 1Р-сетей".-СПб.,2000.

46. Шварц М. "Сети ЭВМ. Анализ и проектирование": Пер.с англ.-М.: Радио и связь, 1981.

47. Вивек Олвейн, CCIE™. "Структура и реализация современной технологии MPLS". Пер.с англ.- Издательский дом «Вильяме». Москва-Санкт-Петербург-Киев,2004.

48. М. L. Fisher "The Lagragian Relaxation Method for Solving Integer Problems, Management Science", vol. 27, no.l, pp. 1-18, January 1981.

49. R. K. Ahulja, T. L. Magananty, and J. B. Orlin Network Flows: "Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, New Jersey", 1993.

50. B.Fortz and M.Thorup, "Internet Traffic Engineering by Optimizing /OSPF/ Weights" in Proceedings oflEEEINFOCOM'OO, Israel, 2000.

51. G. Cornuejols, M. L. Fisher, and G. L. Nemhauser, "Location of Bank Accounts to Optimize Float": An Analytic Study of Exact and Approximate Algorithms, Management Science, vol. 23, no. 8, April 1977.

52. F.Le Faucheur, "Rassian Dolls Bandwidth Constraints Model for Diff-servware MPLS Traffic Engineering", IETF Internet Draft, Work in Progress, March 2004.

53. Олифер В.Г., Олифер Н.А., "Компьютерные сети". Принципы, технологии, протоколы. -3-е издание.- Питер,2006.

54. Зайченко Ю.П. "Задачи проектирования структуры распределенных вычислительных сетей". Автоматика, 1981,№3, с.35-44.59. .Федотов Е.В. "Определение оптимальных маршрутов в сети пакетной коммутации". В сборнике. Сетевая обработка информации. М.:МДНТП,1990.

55. Зайченко Ю.П., Гонта Ю.В. "Структура и оптимизация сетей ЭВМ".-Киев: Техника, 1986.

56. Бочаров П.П. "Сеть массового обслуживания с сигналами со случайной задержкой"// Автоматика и телемеханика. №9 -сентябрь 2002.

57. M.S.Garey, D.S.Johnson, "Computers and Intractability": Guaide to the Theory of NP-Completeness'W.H.Freeman, New York, 1979.

58. R.Widyono, "The design and evaluation of routing algorithms for realtimechannels".Technical Report TR-94-024,University of California at Berkeley',June 1994.

59. L. Georgiadis, R. Guerin, V. Peris and R. Rajan, "Efficient Support of Delay and Rate Guarantees in an Internet", IBM T.J.Watson Research Center, 1999.

60. A.K. Parekh and R.G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks The Multiple Node Case", IEEE/ACM Transactions on Networking, 1(3): June 1993.

61. A.K. Parekh and R.G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks The Multiple Node Case", IEEE/ACM Transactions on Networking, 2(2):137-150, April 1994.

62. R. Szab.o, P. Barta, J. B.r.o, F. N.emeth, C-G. Perntz, "Non Rate-Proportional Weighting of Generalized Processor Sharing Schedulers" GLOBECOM'99, December 1999.

63. R. L. Cruz, "A Calculus for Network Delay", IEEE Transactions on Information Theory, vol.37, no. 1, pp.114-141, January 1991.

64. S. Rampal, R. Guerin, "Flow Grouping For Reducing reservation Requirements for Guaranteed Delay Service", July 1997

65. Stefan Savage, Andy Collins, Eric Hoffman, Thomas Anderson, 'The End-to-End Effects of Internet Path Selection"ACM SIGCOMM '99. September 3,1999.

66. Roch A. Guerin, et al., "QoS Routing mechanisms and OSPF Extensions", Internet Engineering Task Force, Internet Draft, December 1998, (Work in Progress).

67. Guerin Roch A.; Orda Ariel, "QoS routing in networks with inaccurate information: theory and algorithms" IEEE/ACM-Transactions-on-Networking. vol.7, no.3; June 1999.

68. G. Apostolopoulos, R. Gu.erin and S. Kamat, "Implementation and Performance measurements of QoS routing extensions to OSPF" in Proceedings of INFOCOM'1999, New York, March 1999.

69. S. Shenker, C. Partridge, R. Gu.erin, "Specification of guaranteed quality of service" Request For Comments (Proposed Standard) RFC2212, Internet Engineering Task Force, September 1997.

70. Zheng Wang and Jon Crowcroft, "Bandwidth-Delay based routing algorithms", IEEE GlobeCom'95, Singapore, November 1995.

71. Funda Ergun, Rakesh Sinha, Lisa Zhang, "QoS Routing with Performance-Dependent Costs" IEEE INFOCOM'2000 , March 2000.

72. Hussein F. Salama, Douglas S. Reeves and Yannis Viniotis, "A Distributed Algorithm for Delay-Constrained Unicast Routing", IEEE INFOCOM'97, Kobe, Japan, April 1997.

73. W.C.Lee, et al. "Multi-Criteria Routing subject to Resource and Performance Constraints", ATM Forum 94-0280, March 1994.

74. C. Pornavalai, G. Chakraborty and N. Shiratori, "Routing with multiple QoS requirements for supporting multimedia applications", Journal of High Speed Networks, 1998.

75. Kenji Ishida and Kitsutaro Amano, "A Delay-Constrained Least-Cost Path Routing Protocol and the Synthesis Method", IEEE 1998.

76. Shigang Cheng and Klara Nahrstedt, "On finding multi-constrained paths" ICC'98, Atlanta, Georgia, 1998.

77. Jeffrey Jaffe, "Algorithms for finding path with multiple constraints", Networks, vol. 14, pp.95-116,1984.

78. David Blokh and George Gutin, "An approximation algorithm for combinatorial optimization problems with two parameters", 1995.

79. Ravindra K. Ahuja, Tomas L. Magnanti and James B. Orlin, "Network Flows" PRENTICE HALL, Upper Saddle River, New Jersey 07458,1993.

80. H. de Neve, P. van Mieghem, "A multiple quality of service routing algorithm for PNNI", IEEE ATM'98 Workshop, pp.306-314, Fairfax, Virginia, May 1998.

81. Liang Guo and Ibrahim Matta, "Search Space Reduction in QoS Routing" Technical Report NU-CCS-98-09, October 1998.

82. Atsushi Iwata, et al. "ATMRouting Algorithms with Multiple QoS Requirements for Multimedia Internetworking", IEICE Trans. Commun., vol.E79-B, August 1996.

83. M. Held and R. Karp, "The traveling salesman problem and minimum spanning trees", Operations Research 18, pp.l 138-1162, 1970.

84. M. Held and R. Karp, "The traveling salesman problem and minimum spanning trees, Part II. ", Mathematical Programming 6,1971.

85. R. Hassin, "Approximation schemes for the restricted shortest path problem", Mathematics of Operations Research, 17(1): Feb 1992.

86. D.H. Lorenz and A. Orda, "QoS routing in networks with uncertain parameters", IEEE/ACM Transactions on Networking, 6(6), Dec 1998.

87. Danny Raz and Yuval Shavitt, "Optimal Partition of QoS requirements with Discrete Cost Functions", INFOCOM 2000 .

88. Dean H. Lorenz, Ariel Orda, Danny Raz, and Yuval Shavitt, "Efficient QoS Partition and Routing of Unicast and Multicast", IW QoS 2000, June 2000.

89. J. Boyle et al., "Applicability Statement for Traffic Engineering with MPLS", IETF, RFC 3346, August 2002.

90. Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Alg, StdCtrls, Menus, Grids, ExtCtrls, Simplex, Spin, ComCtrls, TeEngine, Series, TeeProcs, Chart, jpeg; type

91. Private declarations} public1. Public declarations} end;const MAXCOST=32768;

92. WeightPlus=l; //------------//

93. WeightMinus= 1; // — Веса — // WeightMoves= 1; II Операций - //

94. WeightCompare=l; //------------//var frmMain: TfrmMain;

95. Net:TNet; // — Структура сети-------//

96. Traffic:TTraffic; // ~ Трафик-матрица-------//

97. Count: integer; //-- Размерность матриц —II Thread:THandle; // — ID трэда выполнения ~ //

98. TotalCount : Longword; //-----------------------//

99. CountPlus : Longword; //-----------------------//

100. CountMinus : Int64; // -- Счетчики операций ~ //

101. CountMoves : Longword; //-----------------------//

102. CountCompare : Longword; //-----------------------//

103. Count:=5; //Размер матриц по умолчанию 5x5btSetClick(frmMain); //Применение размеров1. Chartl .Visible:=false;1. Chart2.Visible:=false;

104. AssignFile(F,,simplex.opc');1. Reset(F);

105. Read(F,SimplexCompareVector); CloseFile(F);

106. AssignFile(F,'heuristic.opc'); Reset(F);

107. Read(F,HeuristicCompare Vector); CloseFile(F); end;---------------------------------//1. — Трэд симплексного алгоритма ~ // И.---------------------------------Цprocedure SimplexPart; var

108. CountResult; // ~ Записывается показания счетчиков после выполнения симплекса ~ // OperationCompareVectorf 1 . :=TotalCount;

109. SimplexCompareVectorcount.:=(SimplexCompareVector[count]+OperationCompareV ector[l]) div 2;

110. SimplexCompareVectorcount+20. :=SimplexCompareVector[count+20]+1; SimplexCompareVector[]:=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0);

111. SimplexCompareVector0.:=0;SimplexCompareVector[l]:=0;SimplexCompare Vector [2]:=0;

112. SimplexCompareVector3.:=0;SimplexCompareVector[4]:=0;SimplexCompareVector[ 5]:=0;

113. SimplexCompareVector6.:=0;SimplexCompareVector[7]:=0;SimplexCompareVector[ 8]:=0;

114. SimplexCompareVector9.:=0;SimplexCompareVector[ [11]:=0;

115. SimplexCompareVector12.:=0;SimplexCompare Vector or[14]:=0;

116. SimplexCompareVectorl 5 or[17.:=0;

117. SimplexCompareVector 18 or[20.:=0;

118. SimplexCompareVector21 or[23.:=0;

119. SimplexCompareVector24 or[26.:=0;

120. SimplexCompareVector27 or[29.:=0;

121. SimplexCompareVector30 or[32.:=0;

122. SimplexCompareVector33 or[35.:=0;

123. SimplexCompareVector36 or[38.:=0;

124. SimplexCompareVector39 AssignFile(F,'simplex.opc'); Rewrite(F);