Применение теории графов к решению задачи маршрутизации в цифровых сетях тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Чукарин, Алексей Валерьевич

• Чукарин, Алексей Валерьевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Чукарин, Алексей Валерьевич

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ

ВВЕДЕНИЕ

ГЛАВА 1. Анализ задачи маршрутизации на графе сети сигнализации

1.1. Требования к маршрутизации

1.2. Граф сети сигнализации

1.3. Ограничения маршрутизации

1.4. Постановка задачи исследований

ГЛАВА 2. Методы построения маршрутов и вычислительные алгоритмы

2.1. Метод построения графа маршрутов

2.2. Методы и алгоритмы построения взвешенного 61 мультиграфа маршрутов

2.3. Раскраска ребер мультиграфа

ГЛАВА 3. Анализ процесса построения маршрутов и средства для вычислений

3.1. Методы анализа ошибок маршрутизации

3.2. Программные средства

3.3. Процессы построения и верификации маршрутов

3.4. Численный анализ 114 ЗАКЛЮЧЕНИЕ 122 СПИСОК ИСТОЧНИКОВ

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ

С = (V, Щ - граф сети сигнализации

- множество вершин источников и адресатов

Т2 - множество промежуточных вершин всех маршрутов

- мультиграф сети сигнализации

91 - множество пар вершин графа О, соответствующее множеству пар «источник-адресат»

1(и,у) - маршрут из вершины и в вершину V

- число промежуточных вершин маршрута

- множество маршрутов из вершины и в вершину V Я? {у) - множество всех маршрутов в вершину V

- множество всех маршрутов графа О

-{Т1 ^ ' граф маршрутов в вершину V,

2 - кликовое разбиение графа ( {1,.,Р} - множество весов графа маршрутов

Б' (и) - образ вершины и на графе С у)) - фронт волны порядка т вершины V. и, у) - поток из вершины и в вершину у графа С

Э =[Т1 | " мультиграф маршрутов в вершину V,

С - пропускная способность ребра мультиребра графа б

Ф(и,х) - суммарный поток по мультиребру (и,х) графа С и) ~ поток через вершину и графа < с

§ - множество цветов для раскраски мультиграфа (}у с6(и,х) - множество цветов для раскраски мультиребра (и,х) (и,х) - множество цветов для раскраски / -го ребра мультиребра (и,х)

В{и,х) - множество ребер мультиребра (и,х)

Л{и,х) - множество номеров ребер мультиребра {и,х)

Ь,(и,х) - ребро с номером / мультиребра (и,х)

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

Современные цифровые сети связи строятся, исходя из рекомендаций международных и национальных организаций по стандартизации в области телекоммуникаций [44,48,64,65]. К этим сетям, в первую очередь, относятся цифровая сеть с интеграцией служб (ЦСИС), интеллектуальная сеть связи (ИСС) и сеть сотовой подвижной связи (ССПС) в стандарте GSM (Global System for Mobile Communication). В цифровых сетях для управления процессами установления и разъединения соединений пользователей применяется общеканальная система сигнализации №7 (ОКС 7) [2,13,36,62,63,73], которая относится к классу систем передачи данных с коммутацией пакетов. Кроме того, ОКС 7 отвечает за передачу большого объема информации, хранящейся в специализированных базах данных (БД) сети. Примерами таких БД в сетях GSM являются, так называемые, реестры данных об абонентах (Home Location Register, HLR, и Visiting Location Register, VLR), а в интеллектуальных сетях - узлы баз данных (Service Data Point, SDP). Требования стандартов [64,65] к передаче такого рода данных являются крайне жесткими, в первую очередь, это касается своевременной доставки данных по сети ОКС 7. Число пользователей сетей ISDN (Integrated Services Digital Network), IN (Intelligent Network) и GSM за последнее десятилетие возросло в десятки раз, что обусловило возросшую нагрузку на сети ОКС 7. Следует отметить, что ОКС 7 является также основой сетей следующего поколения, например, сетей UMTS (Universal Mobile Telecommunications System).

Таким образом, цифровая сеть обязательно включает в себя сеть сигнализации, основной задачей которой является надежная и своевременная передача пакетов данных, которыми обмениваются коммутационные станции и узлы баз данных в процессе управления соединениями. Сеть сигнализации является базовым элементом любой цифровой сети связи [36,52,73,79].

Согласно принципам организации передачи данных, сеть сигнализации является сетью пакетной коммутации, в которой используются принципы статической маршрутизации [64]. Узлы сети сигнализации необходимо различать с точки зрения их функциональности. Узлы, где генерируются и принимаются сигнальные сообщения, будут называться оконечными, а узлы, выполняющие только функции маршрутизации, - транзитными. Говорят, что пара оконечных узлов находится в сигнальном отношении, если эти узлы обмениваются данными [48,65]. Для передачи сообщений из узла-источника в узел-адресат и наоборот должны быть организованы маршруты как в прямом, так и в обратном направлениях, причем каждый маршрут может иметь в своем составе транзитные узлы. Поэтому между узлами, находящимися в сигнальном отношении, требуется построить множество маршрутов в каждом направлении. Для того, чтобы рассчитывать такие маршруты необходимо применение методов теории графов [3,8,10,17,23,26,32,58], а также теории телетрафика [5,24,27,57,70,75], теории сетей массового обслуживания [7,12,21,31,53], теории исследования операций [15,29,35,46,50] и теории алгоритмов [1,14,25,30,46,78].

Решению задачи маршрутизации посвящен ряд работ, которые условно можно разделить на две группы. К первой из них относятся работы, опубликованные в 1970-1980-х годах [4,6,7,55,66]. В этих и некоторых других публикациях рассматриваются вопросы расчета сетей сигнализации, построенных на базе аналогового, а не цифрового оборудования. Отличительной особенностью таких сетей является низкая скорость передачи (не более 4,8 Кбит/сек), а также малое число транзитных узлов, что значительно упрощает решение задачи маршрутизации. Тем не менее, среди упомянутых публикаций следует отметить обзор [7] и статью [4], где представлены результаты разработок в области анализа и расчета междугородной сети ОКС 7 бывшего СССР (в настоящее время сеть ОКС 7 ОАО «Ростелеком»). Отметим, что только в статье [66] сделана попытка формализовать задачу в терминах теории графов и лишь для одного из частных случаев.

Начиная с 1990 года, появляются публикации, где к решению задачи маршрутизации в сетях сигнализации применяется графовый подход [3842,59-61,67-69,76,77]. Это объясняется тем, что к этому времени в США, Канаде, Японии и ряде стран Европы построены и функционируют сети, использующие цифровое оборудование со скоростью передачи 56 и 64 Кбит/сек. Эти сети имеют в своем составе большое число транзитных узлов, а решение задачи маршрутизации в таких сетях требует применения достаточно сложного математического аппарата. В ряде случаев, ввиду большой размерности сети (маршрутные таблицы содержат десятки тысяч записей) расчет маршрутов становится невозможным без создания специализированных программных средств. В работе [59] рассматриваются вопросы расчета и анализа производительности сети сигнализации в интеллектуальных сетях связи. Статья [61] посвящена разработке метода планирования сети ОКС 7, основанного на структурированном подходе, с учетом требований к показателям качества функционирования цифровой сети. Аспекты, рассматриваемые в работе [67], известным немецким специалистом В. Кляйном связаны с расчетом и проектированием сетей сигнализации большой размерности. В том числе, рассматриваются методы оценки параметров качества обслуживания в сети сигнализации. Достаточно глубоко проработанный подход, основанный на применении теории графов к проектированию сети сигнализации, впервые был представлен в работе [68]. В этой статье рассматривается сеть со специфической структурой иерархического типа, а основной результат заключается в синтезе графа сети с одновременным построением маршрутов без циклов и петель с заданным числом транзитных узлов. Статья [69] посвящена разработке алгоритмического подхода при создании программного средства для планирования сети сигнализации. Эта работа выполнена специалистами из исследовательского центра компании Siemens AG и отличается тем, что в ней впервые был строго формализован процесс расчета маршрутов для реализации в программном средстве. В [76] описана методика выявления и локализации ошибочных записей в таблицах маршрутизации сети сигнализации, а также сделана попытка формализовать процесс поиска ошибок. В перечисленных публикациях задача маршрутизации в сети сигнализации решается в частных случаях. Исключением является монография Самуйлова К.Е. [36], где заложены основы математических методов анализа и расчета параметров качества обслуживания в сети сигнализации, в том числе, впервые в общем виде сформулирована задача маршрутизации на графе этой сети.

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

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

Диссертация состоит из 3 глав. Первая глава посвящена анализу постановки задачи маршрутизации на графе сети сигнализации, сформулированной в [36]. В разделе 1.1 приводится схема процесса планирования сети сигнализации, а также определяются ограничения на маршрутизацию в сети сигнализации. В разделе 1.2 строится граф сети сигнализации, и вводятся основные понятия и определения, необходимые для построения маршрутов на графе сети, а также рассматривается пример соответствия введенных обозначений параметрам сети сигнализации.

Заключение диссертации по теме «Теоретические основы информатики», Чукарин, Алексей Валерьевич

Выход

Рис.3.16. Диаграмма действий фрагмента базового процесса сетевого планирования.

Действие «Коррекция структуры сети».

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

Действие «Верификация маршрутизации».

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

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

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

Рис.3.17. Диаграмма действий процесса построения маршрутов.

Действие «Выделение в транзитной сети полносвязных подсетей».

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

Действие «Расчет маршрутизации к каждому ПС».

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

V,. е т.е. для всех узлов сети сигнализации, являющихся оконечными. Для этого используется алгоритм 2.1 при полносвязном графе транзитной сети или алгоритм 2.4 раздела 2.1 при построении орграфов Су по кликовому разбиению графа транзитной сети. Построение графов маршрутов осуществляется с учетом ограничений (¡) и (и) раздела 1.3.

Действие «Расчет нумерации пучков звеньев сигнализации».

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

Действие «Расчет приоритетов пучков звеньев».

Для каждого пучка звеньев сигнализации должно быть определено значение приоритета выбора направления передачи к каждому пункту сигнализации назначения. Эти приоритеты определяются как для основной маршрутизации, так и для альтернативной, в случае отказов сетевых элементов. Для этой фазы реализован алгоритм 2.5 - алгоритм взвешивания ребер графа маршрутов раздела 2.2, учитывающий ограничения (Ш) и (¡у) раздела 1.3 на построение маршрутов.

Действие «Расчет сигнальной нагрузки».

На этой фазе процесса построения маршрутов рассчитываются сигнальные нагрузки на каждое сигнальное отношение между взаимодействующими узлами и нагрузки на каждый пучок звеньев. Для этого используются соответствующие методы раздела 2.2, с помощью которых определяются значения этих нагрузок и емкости пучков. При расчетах используются формулы (2.11) и (2.12) раздела 2.2 соответственно.

Действие «Расчет нумерации звеньев в пучках».

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

Действие «Расчет разделения нагрузки».

Данное действие включает в себя алгоритм расчета кодов селекции звена сигнализации. Что в терминах теории графов соответствует раскраске ребер и мультиребер мультиграфа <5„ . Эта раскраска осуществляется по алгоритму 2.6 раздела 2.3 и формулам (2.18) и (2.19), учитывающим ограничения на маршрутизацию (у) - (уи), в случае с1(и) = 2к(и) и N(и,х) = . И по формулам (2.24) и (2.25) того же

раздела, с учетом ограничений (у), (у1*) и (уп*), при (¡{и)* 2к{-и\ а

Ы{и,х)ф2к{и'х).

Действие «Составление маршрутных таблиц».

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

Рассмотрим теперь процесс верификации маршрутизации, применяемый при контроле данных маршрутизации во избежание ошибок, связанных с нарушением ограничений маршрутизации (¡) - (уи) раздела 1.3 или (у1*) и (уп*) раздела 2.3. Проанализируем основные действия, составляющие процесс, показанный на рис.3.18.

Рис.3.18. Диаграмма действий процесса верификации маршрутизации.

Действие «Поиск и исправление ошибок первого класса».

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

Действие «Поиск и исправление ошибок второго и третьего классов».

Эта фаза предназначена для выявления и корректировки ошибок, связанных с наличием маршрутов излишней длины, а также циклов и петель на маршрутах. Т.е., она касается нарушений ограничений маршрутизации (i) и (ii) раздела 1.3. Если такие ошибки были найдены, то после их исправления необходимо еще раз провести первое действие процесса, если же ошибок не было обнаружено, то осуществляется переход к следующему действию процесса верификации.

Действие «Поиск и исправление ошибок четвертого класса».

На рассматриваемой фазе осуществляется поиск ситуаций, связанных с неправильным расчетом приоритетов выбора направления передачи пучкам звеньев. Эти ситуации относятся к нарушениям ограничений (iii) и (iv) раздела 1.3. В случае обнаружения таких ошибок и их исправления необходимо еще раз вернуться ко второму действию процесса, иначе процесс подразумевает переход к последнему действию при верификации.

Действие «Поиск и исправление ошибок пятого класса».

Заключительная фаза процесса верификации маршрутизации предназначена для поиска и исправления ошибок, связанных с неправильным расчетом кодов селекции звена сигнализации. В разделе 3.1 это ошибки пятого класса, касающиеся некорректной раскраски ребер и мультиребер мультиграфа маршрутов, т.е. нарушающие ограничения (v) - (vii) раздела 1.3 или (vi*) и (vii*) раздела 2.3. После поиска и исправления таких ошибок, при их наличии, процесс верификации маршрутизации завершается.

На рис.3.19 показан фрагмент данных маршрутной таблицы узла «ПС-2» сети, изображенной на рис.3.14 раздела 3.2. Данные были экспортированы из программного средства в формат электронной таблицы Microsoft® Excel. Таблица включает в себя все данные, необходимые для реализации маршрутных таблиц. В столбцах «А» и «В» («G» и «Н») хранится информация о названии и специальных кодах исходящего (конечного) пункта сигнализации. В столбце «С» хранится номер пучка звеньев, вычисленный при действии «расчет нумерации пучков звеньев сигнализации» процесса построения маршрутов см. рис. 3.17). В столбце «Б» хранится номер звена в пучке, рассчитанный во время действия «расчет нумерации звеньев в пучках». Результаты действия «расчет приоритетов пучков звеньев» того же процесса отображены в столбце «Е». И, наконец, столбец «Б» предназначен для результатов, полученных при расчете разделения нагрузки.

Е2 Microsoft Excel - Маршрутные таблиц w-xis ; Jolxll Файл Правка Вид Вставка Формат Сервис Данные Окно Справка Adobe PCF --SX D е*У и а а 9- * ^ 8- I « . О. - % -г - п 1\ &ШЯ 100* • © -:: % % Щ „ АЛ! '10 'В I u:f , Л I tS It : ' -3» ' А -„ А8 ' f* ПС-2

А | В | С | 0 | Е | Р | в | Н | 1 |3 ~

1 Исходящий пункт Код 1 Пучок ЗС ЗС Приоритет Биты поля СЗС Пункт назначения Код 1

2 |

3 4 ПС-2 ПС-2 12 10 1 ОХХХ ПС-1 11

5 ПС-2 12 0 0 1 1ХХХ ПСИ 11

6 7 ПС-2 ПС-2 12 12 3 2 0 2 ОХХХ ПСИ 11! 0 2 1ХХХ ПСИ 11

ПС-2 12 3 0 1 00ХХ ПС-3 13

Э 10 ПС-2 ПС-2 12 12 1 о 0 101ХХ 0 1 10ХХ ПС-3 13 ПС-3 13

11 ПС-2 .12 2 0 1 11.ХХ ПС-3 13

12 13 ПС-2 ПС-2 12 12 3 1 0 1: 0 1 оохх 01ХХ ПС-4 14 ПС4 14

14 ПС-2 12 0 0 1 10XX ПСИ 14

15 16 ПС-2 ПС-2 12 12 2 3 0 1 0 1 11XX оохх ПСИ 14 ПС-5 15

17 ПС-2 12 .1 0 1 01ХХ ПС-5 15

18 19 ПС-2 ПС-2 12 12 0 2 0 1 0 1 юхх 11XX ПС-5 ПС-5 15 15

20 ПС-2 12 3 0 1 ОХХХ ПС-6 16

21 22 ПС-2 ПС-2 12 12 2 1 0 1 0 2 1ХХХ ОХХХ ПС-6 ПС-6 16 16

23 ПС-2 12 0 0.2 1ХХХ ПС-6 16

ЗА . «I.I >1Г Sum =29 /, jn 4 ► И|\Маршрутные таблицы/ Готово

Рис.3.16. Пример результатов расчета маршрутной таблицы.

В последнем разделе диссертации приведем пример применения методов и алгоритмов, полученных в главе 2, к расчету маршрутизации сети.

3.4. Численный анализ

В заключение рассмотрим пример применения методов главы 2 к расчету маршрутизации сети с помощью программного средства и проанализируем полученные результаты. В качестве примера возьмем сеть, показанную на рис.3.20. Эта сеть состоит из четырех оконечных и четырех транзитных узлов. Зададим максимальное значение Т = 2 числа транзитных пунктов на маршрутах и значение Р = 2 числа приоритетов выбора направлений передачи. Определим значение Я = 2 количества битов кода селекции звена сигнализации. Будем считать, что оконечные узлы находятся в сигнальных отношениях по принципу «каждый-с-каждым». Одйп Реда-стировамие §ил Проект Функции Верификация Результаты Отчеты £>кно £гтраька а р & & а & х и; е; а;> я ? Ц о □ □ / щ> [| > & # п а

На Проект в Ц&СетьОКС?

Структура сети Пункты сигнализации • Пучм звеньев сигнализации Й У2 Диаграммы Структура сети 1 ПМКПН

3сясеть 3

Автоупорядамить д]

20

ЕШЭ

Обо^ачемия.

J 'Я

Ш - <ластер Ю с-<| -5ТР й -»/г? пс-з|

1ТПС-41

5Р 1 уроеив Г & 2 уровне

Рис.3.20. Окно программного средства с примером структуры сети.

Для сети, изображенной на рис.3.20, построим граф С с множеством вершин Т = У[[)У2, где множество вершин, соответствующих оконечным узлам - T-'i" = {Vj, v2, v3, v4} и множество вершин, соответствующих транзитным узлам - '¥г = {v5,v6,v7,vg} (см. рис. 3.21), и определим множество 9i = [J соответствующее парам узлов, i*J находящихся в сигнальных отношениях.

Рис.3.21. Пример графа О .

Построим графы маршрутов , / = 1,4. Очевидно, что свойствам 1-3, которым должно удовлетворять кликовое разбиение 0 (см- раздел 2.1), соответствует, например, разбиение = Воспользуемся этим разбиением, применяя алгоритм 2.4 построения орграфа маршрутов О^. В результате получим изоморфные графы , г = 1,4, один из которых -граф в - показан на рис.3.22.

Рис.3.22. Пример графа Gv = (Т\У/У[).

Взвесим ребра графа О и построим граф С . Аналогично будут получены все остальные графы (?„ / = 2,4. Воспользуемся для этого алгоритмом 2.5 взвешивания ребер графа маршрутов , изложенным в разделе 2.2. Т.к. значение Р = 2, то множество ^ = {1,2}. Начнем рассмотрение с вершины у2 . Образ этой вершины на графе О^ представляет собой множество -О'(уг) = • Следовательно, у2) = |у6,у7} . Определим р = 1. Тогда, поскольку из вершины у2 в вершину у, проходят всего 2 маршрута - (у2^6,у,) и (у2,у7,у6,у,), очевидно, что Ц'^2) = {у6}, а />(у2,у6) = 1. По алгоритму 2.5 получаем (у2) = {у7} • Следовательно, А» (у2) = {} и Р (у2' у7) = 2 • Аналогичная процедура осуществляется для всех вершин множества V1, кроме самой вершины у,. В результате получаем граф ^,[{1,2}], показанный на рис.3.23.

Этому графу соответствует маршрутизация к узлу «ПС-1», которая рассчитана в программном средстве, как показано на рис.3.24. На этом рисунке пучки, используемые с первым приоритетом, т.е. соответствующие ребрам с весом 1, показаны тонкими линиями, а пучки звеньев, используемые с приоритетом 2, соответствующие ребрам с весом 2, изображены толстыми серыми линиями. у4

Рис.3.23. Пример графа С^ [{1,2}].

-!0|х| Файл Ре датирование Вид Проект Функции Верификзиия Результаты Отчеты £кно Справка -|в|х| в о й э у а ■ .г «> .;>. её я * поасэ /

Проект В ИЛ Сеть ОКС7 Й Щ Структура сети . Пуню ы сигнализации Пучки хммьев сигнализации Й-Щ^ Диаграммы 1 ^ Структура сети ПМКПН Выберите пункт назначения: |пс-1 "] [ 1ш>э] [ПС-41 | 1ТПС-21 л л

1 1ПС-21 | 1тпс^1 1ПС-31 . 1ТПС-11 ж »Л 1 ±1

Готово | 1 1 ! //

Рис.3.24. Окно программного средства с примером маршрутизации в направлении узла «ПС-1».

Графы , / = 2,4 строятся аналогично графу и, поскольку, исходные графы , / = 2,4 были изоморфны графу , то и взвешенные графы также изоморфны.

Зададим матрицу потоков (см. таблицу 3.1), согласно которой будет рассчитано количество ребер в мультиребрах графа С по формулам (2.11) и (2.12) раздела 2.2. Будем считать, что пропускная способность одного ребра С = 0,2.

ЗАКЛЮЧЕНИЕ

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

1. Проведено исследование и анализ графовой модели сети сигнализации и ограничений на построение графов маршрутов.

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

3. Разработаны метод и вычислительный алгоритм для реберной раскраски мультиграфов маршрутов с произвольным числом ребер и мультиребер.

4. Разработанные методы и алгоритмы применены к расчету маршрутных таблиц сети сигнализации. Проведена классификация ошибок маршрутизации и разработаны методы коррекции ошибок.

5. Разработано программное средство и реализован расчет маршрутных таблиц сети сигнализации.

Список литературы диссертационного исследования кандидат физико-математических наук Чукарин, Алексей Валерьевич, 2004 год

1. Адельсон-Велъский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы. -М.: Наука, 1975.

2. Аджемов A.C., Кучерявый А.Е. Система сигнализации ОКС №7. -М.: Радио и связь, 2002.

3. Асаное М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы, матроиды, алгоритмы. Ижевск: НИЦ "РХД", 2001. -288 стр.

4. Башарин Г.П., Белов С.И., Дедоборщ В.Г., Ефимушкин В.А., Куренков Б.Е., Петров А.Ф. Система автоматизированного проектирования сети общих каналов сигнализации // Электросвязь.- 1987. №5. - С.21-25.

5. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях-М.: Наука, 1989.

6. Башарин Г.П., Кокотушкин В.А., Наумов В.А. О методе эквивалентных замен расчета фрагментов сетей связи // Изв. АН СССР. «Техн. Кибернетика». 1979. - №6.

7. Башарин Г.П., Самуйлов К.Е. Методы анализа производительности систем сигнализации по общему каналу // Итоги науки и техники. «Электросвязь» Т.16. М.: ВИНИТИ, 1986.

8. Бородин О.В. Структурная теорема о плоских графах и ее приложение к раскраске // М.: Дискретная математика, 1992. №1.- С.60-65.

9. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Бином, Изд. 2-е. Пер. с англ.- 1998.

10. Визинг В. Г. Интервальная раскраска инциденторов ориентированного мультиграфа // Дискретный анализ и исследование операций, 2001. Серия 1, том 8. - №2. - С.40-51.

11. Висков A.B., Чукарин A.B. К разработке программного обеспечения многопротокольной коммутации с использованием меток // Сб. «Системы телекоммуникаций и моделирования сложных систем». М.: ПАИМС. 2001. - С.29-34.

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

13. Голъдштейн Б.С. Сигнализация в сетях связи. М.: Радио и связь, 1997.

14. Грин Д., Кнут Д. Математические методы анализа алгоритмов // Пер. с англ. М.: Мир, 1987.

15. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. —М.: Мир, пер. с англ. 1998.

16. Дорф И.Г., Жарков М.А., Наумов В.А., Самуйлов К.Е. Метод расчета междугородной сети ОКС с использованием декомпозиции // Электросвязь. 1992. -№8.

17. Евстигнеев В.А. Применение теории графов в программировании. -М.: Наука, 1985.

18. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, ГРФМЛ, 1990.

19. Ефимушкин В.А., Жарков М.А., Полищук В.П., Самуйлов К.Е. Выбор структуры построения междугородной сети ОКС 7. // В сб. научных трудов ЦНИИС. М., 1998.

20. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988.

21. Зверович Н.Э. Сильные к-раскраски графов // М.: Дискретная математика, 2001. №1. - С.78-89.

22. Зыков A.A. Основы теории графов. М.: Наука, ГРФМЛ, 1987.

23. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.

24. Кормен Т., Лейзерсон Ч, Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.

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

26. Лагутин B.C., Степанов С.Н. Телетрафик мультисервисных сетей связи. М.: Радио и связь, 2000.

27. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

28. Лозовану Д.Д., Трубин В.А. Задача о минимаксном пути в сети и алгоритм ее решения // М.: Дискретная математика, 1994. №2. -С.138-144.

29. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

30. Нейман В.И. Структура систем распределения информации. -М.: Радио и связь, 1983.

31. Нефедов В.Н., Осипова В.А. Курс дискретной математики. -М.: Изд. МАИ, 1992.

32. Оре О. Теория графов. М.: Наука, ГРФМЛ, 1980.

33. Орлович ЮЛ. Покрытия кликами, факторы и графы с изоморфными окружениями вершин // Дискретный анализ и исследование операций, 2002. Серия 1, том 9. - №2. - С.48-90.

34. Самарский A.A. Введение в численные методы. М.: Наука, ГРФМЛ, 1987.

35. Самуйлов К.Е. Методы анализа и расчета сетей ОКС 7. М.: Изд-во РУДН, 2002.

36. Самуйлов К.Е., Полищук В.П., Чукарин A.B. Схема сети ОКС-7 Московской области // Вестник связи. 2002. - №10.

37. Самуйлов К.Е., Чукарин A.B. К расчету плана маршрутизации сети системы сигнализации №7 // Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 2001.

38. Самуилов К.Е., Чукарин A.B. Метод построения плана маршрутизации сигнальных сообщений в сети ОКС 7 // M.: LVII Конф. РНТОРЭС. 2002. -Том 1, С.34-36.

39. Самуйлов К.Е., Чукарин A.B. Метод раскраски ребер мультиграфа в задаче выбора направлений передачи сигнальных сообщений // Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 2002.

40. Самуйлов К.Е., Чукарин A.B. О применении теории графов к решению задачи маршрутизации сигнальных сообщений в цифровых сетях связи // Вестник РУДН. Серия Прикладная и компьютерная математика. 2002. — №1, С.40-50.

41. Самуйлов К.Е., Чукарин A.B. Применение алгоритма фронта волны для построения графа плана маршрутизации сигнальных сообщений // Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 2002.

42. Стеценко О.П. Об одном виде раскраски ребер графа в предписанные цвета // М.: Дискретная математика, 1997. №4. -С.92-93.

43. Схема междугородной сети сигнализации №7 (ОКС 7) России на 2005 год. М.: Гипросвязь, 1998.

44. Taxa Х.А. Введение в исследование операций. М.: ИД «Вильяме», изд. 6-е. Пер. с англ. - 2001.

45. Таилкинов В. А. Об одном алгоритме раскраски ребер мультиграфов // Дискретный анализ и исследование операций, 2000. Серия 1, том 7. - №3. - С.72-85.

46. Теория графов // Сб. статей, АН УССР, Ин-т математики. Киев. -1977.-216 стр.

47. Технические спецификации на подсистему передачи сообщений (МТР) для национальной сети России. М.: Минсвязи РФ, 1994.

48. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

49. Черкасский Б.В. Быстрый алгоритм построения максимального потока в сети // СБ. трудов ВНИИ систем, исслед. 1970. - №3. -С.90-96.

50. Чукарин A.B. Об одной задаче построения кликовых разбиений графа цифровой сети связи // Сб. «XXXIX Всероссийская научная конференция по проблемам математики» М.: РУДН. 2003. - С.54.

51. Шварц М. Сети связи: протоколы, моделирование и анализ. В 2-х ч. Ч. I, II: Пер. с англ. М.: Наука, 1992.

52. Шнепс М.А. Системы распределения информации. Методы расчета. -М.: Связь, 1979.

53. Шнепс-Шнеппе М.А. Управление нагрузкой интеллектуальной сети связи // Электросвязь. 2002. -№11.

54. Choi J.Y., Lee H.H., Oh D.G., Kim J.T., Bahk H.G. A Study on the Capacity of CCITT No.7 Common Channel Signaling in Switching System // Proc.: Tencon 87, Seoul, South Korea. 1987. - Pp.541-545.

55. Chukarin A., Samouylov K. Tool for the Routing Planning in a Large-scale Signaling Network // Proc.: 7th Int. Conf. on Telecommunications, ConTEL 2003, Zagreb. June 2001.

56. Distel R. Graph Theory. NY.: Springer-Verlag ed. - 2000.

57. Girao R., Silva S., Lavrador A., Gomes T. Dimensioning Signalling Links (SS7) in INs // Proc.: 3rd Nat. Conf. on Telecommunications, ConfTele2001, Foz. April 2001.

58. Gradischnig K.D., Kramer S., Tuxen M. Loadsharing A key to the reliability for SS7-networks // Proc.: Int. Conf. on Digital Networks, DRNC 2000, Berlin. - September 2000.

59. Hisham R., El-Hadidi M.T, Structured Approach for Planning Signalling System No.7 Networks // Proc.: 2nd Symposium on Computer and Communications, ISCC '97. 1997.

60. IEEE Communications Magazine. 1990. - V.28, No.7, July.

61. IEEE Journal on Selected Areas in Communications. 1994. - V.12, No.3, Apr.

62. ITU-T Recommendation E.7xx Series // ITU-T White Book, November, 1998.

63. ITU-T Recommendation Q.7xx Series // Geneva, July, 1995.

64. Klein W. Routing planning in a large-scale signaling network // Teletraffic Science for New Cost-Effective Systems: Networks and Services, ITC-12, 1989.

65. Klein W., Kleinewillinghofer-Kopp R. Performance Analysis of a Large-Scale Common Channel Signalling Network // Proc.: Teletraffic and Datatraffic, ITC-13. 1991. -Pp.73-78.

66. Krauss L., Rufa G. On the design of a hierarchical SS7 network: a graph theoretical approach // IEEE Journal on Selected Areas in Communications. 1994. V.12. - No.3, Apr.

67. Lemp K.H., Probst A., Schmceller M. Powerful Planning Tool for Signaling Network // Siemens AG, Telecom Report International. -1994. -No.4.

68. Martikainen O., Naoumov V., Samouylov K. Signalling System No. 7 Portable Software Implementation // Proc. Int. Teletraffic Seminar «Digital Commun. Network Management», St.-P., 1993.

69. Martikainen O., Naoumov V., Samouylov K. Telecommunication Signalling // Wiley Encyclopedia of Electrical and Electronics Engineering. V.l (John .G. Webster, Editor), John Wiley & Sons, 1999.

70. Martikainen O., Nikitin A., Zhidovinov M., Samouylov K. UMLDraw a Toolkit for Telecommunications Services Software Modeling // ConTEL'99, Zagreb, Croatia. - 1999.

71. Modarressi A.R., Skoog R. A. Signaling system No. 7: A Tutorial I I IEEE Communication Magazine. 1990. V.28. - No.7, July.

72. Naoumov V., Samouylov K., Chukarin A. An Approach to MPLS System Design // Proc. of «Intelligent Networks 2001: Services, Interfaces, Specifications». M.: MAX Press, 2001.

73. Nielsen B.F., Andersen A.M. Traffic models of the Message Transfer Part of Signalling System № 7 // Proc. of St.Petersburg International Teletraffic Seminar, LONIIS, 1995, St.Petersburg, Russia.

74. Roch H., Glitho R.J. Isolating Faulty Routing Tables in SS7 Networks: Present and Future // IEEE Communications Magazine, May 1996.

75. Samouylov K. A Graph Theoretical Approach to the SS7 Network Routing Plan Design // St.-P.: LONIIS, SUT by prof. Bonch-Bruevich, ITC Sponsored Regional International Teletraffic Seminar «Telecommunication Network and Teletraffic Theory», 2002.

76. Herbert S. Wilf Algorithms and Complexity // A.K.Peters, Ltd.; 2nd edition. -2002.

77. Willmann G., Kuhn P.J. Performance Modeling of Signaling System No.7 // IEEE Communication Magazine. 1990. V.28. - No.7, July.

78. Zharkov M., Samouylov K., Shaparev V. Basic Principles for Russian SS#7 Toll Network Design // ConTEL'97, Croatia, Zagreb, ITA. 1997. V.15. - No.1-3.