авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

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

Pages:   || 2 | 3 |

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

-- [ Страница 1 ] --

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

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

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

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

Автореферат

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

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

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

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

Научный руководитель - доктор технический наук,

профессор Шувалов В.П.

Научный консультант - кандидат технических наук,

доцент Субботин Е.А.

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

Доросинский Л.Г.

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

доцент Егунов М.М.

Ведущая организация - институт математики и механики

Уральского отделения Российской

Академии наук

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

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

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

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

диссертационного совета Д 219.005.01

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

профессор Б.И. Крук

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

Актуальность темы. Быстрый рост трафика и внедрение новых сервисных услуг ставит перед провайдерами задачу, быстро реагировать на эти изменения и адаптироваться к изменяющейся ситуации. И хотя, на первый взгляд, 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г.

  1. Научно-практической конференции «Электронная Россия - стратегия развития реальной инфраструктуры инфокоммуникаций», Екатеринбург, Уралэкспоцентр, 2004г.
  2. Международной научно-практической конференции «Связь-ПРОМ 2005» 2-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2005», Екатеринбург,2005г.
  3. Международной научно-практической конференции «Связь-ПРОМ 2006» 3-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2006», Екатеринбург,2006г.
  4. Международной практической конференции «Современные научные достижения-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, что чрезвычайно важно в условиях меняющегося характера трафика сети. Алгоритм отличается от известных методов распределения многопродуктовых потоков тем, что он рассматривает не каждое в отдельности взятое требование на распределение потоков, а все одновременно заданные в трафик-матрице. На каждом итерационном шаге алгоритма распределяется многопродуктовый поток с интенсивностью ( - повышающий коэффициент, ti,j – трафик) между всеми истоками и стоками. Опишем алгоритм по шагам.

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

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

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

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

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

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

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

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

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

(1)

(2)



Pages:   || 2 | 3 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.