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

• Автор: Чукарин, Алексей Валерьевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 129 с. : ил.

ГЛАВА 1. ГЛАВА 2. ГЛАВА 3. Цы. Ми ребро с номером 1 мульгиребра м,х

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


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