Применение теории графов к решению задачи маршрутизации в цифровых сетях

Применение теории графов к решению задачи маршрутизации в цифровых сетях

Автор: Чукарин, Алексей Валерьевич

Шифр специальности: 05.13.17

Научная степень: Кандидатская

Год защиты: 2004

Место защиты: Москва

Количество страниц: 129 с. ил.

Артикул: 2618202

Автор: Чукарин, Алексей Валерьевич

Стоимость: 250 руб.

ГЛАВА 1. ГЛАВА 2. ГЛАВА 3. Цы. Ми ребро с номером 1 мульгиребра м,х
программного средства, разработанного на языке С с использованием классов МРС и алгоритмов второй главы диссертационной работы. Произведен анализ производительности программного средства, в зависимости от значений параметров сети сигнализации. В разделе 3. Каждый из процессов описан на языке иМЬ для наиболее полного и адекватного воспроизведения поведения системы 4,9,,,. В заключительном четвертом разделе главы 3 разработан численный пример маршрутизации, который показывает применение мегодов и программного средства для расчета маршрутных таблиц сети сигнализации. Таким образом, в диссертационной работе решаются перечисленные ниже актуальные задачи. Исследование и анализ рафовой модели сети сигнализации и ограничений на построение графов маршрутов. Разработка метода и вычислительных алгоритмов, использующих кликовые разбиения, для поароения маршрутов на графе сети сигнализации с произвольной структурой. Разработка метода и вычислительного алгоритма для реберной раскраски мультиграфов маршрутов с произвольным числом ребер и мультиребер.


В этом разделе диссертации доказываются леммы о выполнении свойства коммутативности подмножеств множества маршрутов и о принадлежносги маршрутов графу. Используются методы, основанные на применении понятия фронта волны 3,. Вторая группа ограничений на расчет маршрутов графа связана с взвешиванием графа маршрутов и вычислением весов ребер графа. Особенностью такого взвешивания является наличие множества весов , каждый элемент которого соответствует приоритету выбора направления передачи в сети сигнализации. Третья группа ограничений расчета маршрутизации сформулирована в терминах реберной раскраски графа маршрутов. Раскраска графа маршрутов учитывает одну из основных отличительных особенностей задачи маршрутизации для сетей сигнализации, которая заключается в требовании к равномерному распределению потоков по звеньям сечи. В настоящее время известны работы, например 8,,,,,,,,,, в которых предлагаются различные методы раскраски ребер графа. Однако решаемая задача имеет особенность, заключающуюся в необходимости такой раскраски ребер мультиграфа, что каждому ребру может быть приписано множество цветов. Болес
подробно эти ограничения излагаются и иллюстрируются примерами в разделе 1. Методы построения ограничений маршрутизации основаны на работах ,,. В разделе 1. Глава 2 диссертационной работы посвящена решению поставленной задачи в части разработки методов построения маршрутов и вычислительных алгоритмов. В разделе 2. Исследования в области кликовых покрытий и разбиений проводились, например, в работах ,,,. В предложенном в диссертации методе используется подход, при котором кликовое разбиение осуществляется только для подграфа, описывающего транзитную часть сети сигнализации . Получены алгоритмы построения графов маршрутов в сети с произвольной структурой с учетом всех ограничений первой группы, а также показаны примеры применения алгоритмов. Как указывалось выше, при расчете маршрутизации сети сигнализации, необходимо учесть правила расчета приоритета выбора направления передачи. Для этого в разделе 2. Этот метод позволяет учесть все ограничения второй группы на расчет маршрутов и получить необходимые значения весов для каждого ребра. Далее, необходимо определить количество ребер, содержащихся в каждом мультиребре графа сети. Эта задача решена в работах 2,, а в диссертации предлагается модификация этих методов для увеличения пропускной способности сети при заданной структуре и величинах потоков между вершинами, а также
для изменения структуры сети путем удаления вершин и ребер, незадейсгвованных при пропуске потоков. Раздел 2. В этом разделе предлагаются формулы, по которым осушесгвлястся раскраска любого числа мультиребер, исходящих из одной вершины, и любого числа ребер, содержащихся в одном мультиребре, что развивает методы, предложенные в ,,. Результаты данного раздела получены с учетом методов, известных но статьям ,,,, посвященным реберным раскраскам. Результаты главы 2 диссертации, имеют прикладное значение и используются при проектировании и расчете маршрутизации в сетях сигнализации. Они были использованы при расчете сети сигнализации Московской области . Следует отметить, что в реальных сетях, по целому ряду причин объективного и субъективного характера, могут возникать ошибки маршрутизации. Для выявления таких ошибок международные и национальные организации по стандартизации предлагают наборы тестов ,,, которые применяются в системах управления сетью. Однако эти проверки являются весьма ресурсоемкими и отрицательно сказываются на производительности сети. В диссертационной работе предлагается метод выявления и исправления ошибок маршрутизации, основанный на применении результатов главы 2. Последняя третья глава посвящена применению полученных в диссертации теоретических результатов к расчету маршрутизации в сети сигнализации, проведена классификация возможных ошибок маршрутизации, а также приведен численный пример маршрутизации. В разделе 3. Разработан процесс верификации маршрутизации и анализируются часто встречающиеся на практике примеры нахождения и последующего исправления ошибок всех классов. В разделе 3.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.189, запросов: 244