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

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

На правах рукописи ЧУКАРИН Алексей Валерьевич

УДК 519.17

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ К РЕШЕНИЮ ЗАДАЧИ МАРШРУТИЗАЦИИ В ЦИФРОВЫХ СЕТЯХ

Специальность 05.13.17 - теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2004

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

Научный руководитель -кандидат физико-математических наук, доцент К.Е. Самуилов

Официальные оппоненты: доктор технических наук, профессор С.Н. Степанов кандидат физико-математических наук, А.Н. Виноградов

Ведущая организация: Институт проблем информатики Российской Академии наук

Защита диссертации состоится «_»_2004 г. в

_час._мин. на заседании диссертационного совета К 212.203.08

в Российском университете дружбы народов

Адрес: 115419, Москва, ул. Орджоникидзе, 3

С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов по адресу: 117198, Москва, ул. Миклухо-Маклая, д.6

Автореферат разослан «_».

2004 г.

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

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

кандидат физико-математических наук,

доцент

В .А. Кокотушкин

fdt)4-4 21183

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

Актуальность проблемы

В последние годы развитие телекоммуникационных сетей обусловлено интенсивным внедрением новых технологий, которые позволили предоставлять, пользователям широкий спектр современных услуг. При этом едва ли не основную роль в предоставлении; новых услуг играет стандартизованная-- на международном уровне система общеканальной сигнализации №7 (ITU-T Signaling System No.7). Например, эта система обеспечивает управление соединениями пользователей и передачу данных для предоставления услуг в сотовых и интеллектуальных сетях ( G S M И IN), а также используется в IP-телефонии для организации шлюзов между сетями Internet и сетями с коммутацией каналов. Более того, любая цифровая сеть обязательно включает в себя: сеть, сигнализации, которая, по сути, является сетью передачи данных с коммутацией пакетов. Поэтому при построении цифровой: сети требуется решение задачи расчета маршрутов в сети сигнализации, отличительной особенностью которой является использование принципов статической, а не адаптивной маршрутизации.

В задачах маршрутизации возникает целый комплекс проблем, при решении которых применяются методы теории вероятностей, теории систем и сетей массового обслуживания, теории графов и теории телетрафика. Теоретические основы решения фундаментальных и прикладных задач в этой области созданы известными российскими и зарубежными учеными, такими как Башарин Г.П., Бочаров П.П., Вишневский В.М., Жожикашвили В.А., Лазарев В.Г., Наумов В.А., Нейман В.И., Степанов С.Н., Харкевич А.Д., Шнепс-Шнеппе М.А., ШоргинСЯ., IversenV.B., Gelenbe Е., Kelly F.P., KleinrokL., Kuhn P., RossK-W.. Schwartz M. H

др.

Модели, возникающие при анализе функционирования сетей сигнализации, в достаточной мере исследованы, но решение задачи маршрутизации известно только для некоторых частных случаев и, в основном, по работам зарубежных специалистов, таких как HishamR., Klein W., KraussL., Rufa G., Lemp K.H.,. Probst A. Исключением является монография Самуйлова К.Е , где содержатся постановки задач и заложены основы математических методов -анализа и расчета параметров качества функционирования сетей сигнализации.

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

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

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

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

//• to

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

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

Результаты, выносимые на защиту, состоят в следующем:

- исследованы графовая модель сети сигнализации и ограничения, на параметры задачи маршрутизации;

- разработаны метод и алгоритмы для построения графов маршрутов, использующие кликовые разбиения;

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

- разработанные методы применены к решению задачи анализа и коррекции ошибок маршрутизации;

- разработанные алгоритмы реализованы в программном средстве, предназначенном; для расчета маршрутных таблиц сетей сигнализации.

Реализация результатов работы. Результаты исследований используются в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов направления "Прикладная математика и информатика", в курсовых и дипломных работах. Алгоритмы и программные средства были использованы при расчете сети сигнализации Московской области.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:

- XXXVИ-XXXIX. научных, конференциях факультета физико-математических наук Российского университета дружбы народов (Москва, 2001,2002,2003);

- научной сессии Российского научно-технического общества радиотехники,, электроники, и, связи им.. А.С. Попова (Москва, 2002);

- консультационном семинаре по - реализации решений ОКС 7 региональных и корпоративных сетей на примере сети Московской области в ОАО «Гипросвязь» (Москва, 2003);

7-й международной, конференции ConTEL-2003 (Загреб, Хорватия, 2003);

- семинаре- кафедры, систем телекоммуникаций Российского университета дружбы народов (Москва, 2003);

- семинаре Института проблем информатики Российской академии наук (Москва, 2004);

Публикации. По теме диссертации опубликовано 7 работ.

Структура и объем диссертации Диссертация состоит из

введения, трех глав, заключения, списка литературы: из 80

наименований:. Диссертация содержит 129- страниц текста,- 66 рисунков, 11 таблиц.

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

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

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

Раздел 1.3 посвящен анализу ограничений на маршрутизацию в терминах теории графов. Вводится неориентированный- граф , множество вершин которого соответствует узлам, а множество дуг- звеньям рассматриваемой сети. Множество вершин графа представимо в виде Т = ТХ\^У1> где: — множество вершин,

соответствующих оконечным узлам, а - множество. вершин, соответствующих, транзитным узлам сети: Заметим, что. узлы являются оконечными, если в них' генерируются и принимаются пакеты данных, называемые сигнальными сообщениями: Узлы, выполняющие только функции, маршрутизации, называют транзитными. Говорят, что пара оконечных узлов находится в

сигнальном отношении, ели эти узлы обмениваются сигнальными сообщениями. Поэтому в терминах теории графов для каждой пары вершин- (w,v)' ИЗ заданного множества необходимо

построить множество 3!{u,v) маршрутов, которые. начинаются : в вершине и и заканчиваются в вершине v графа G. В силу того, что сигнальные отношения являются двусторонними, то влечет

(у,и)е&. Определим множество

Ф и

(u,v)ea

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

Пусть - - орграф , содержащий

все. маршруты.: графа G- в- вершину- v,, т.е.. Beet маршруты; из множества:.

(2)

Ограничения на маршрутизацию на графе маршрутов делятся на, три группы. Сформулируем, первую группу ограничений, касающихся структуры, и длины маршрута. На основании ограничений этой группы, строятся графы G¥<, v, е Тх. Для;каждой

пары х вершин (u,v)e5£ должны. быть построены; маршруты,. такие что, во-первых, число промежуточных вершин любого маршрута ограничено заданным значением величины Т, а, во-вторых, любой маршрут является простой, цепью графа G, причем, его промежуточные вершины, если, такие найдутся, принадлежат множеству , В диссертационной работе эти ограничения занумерованы римскими цифрами (i) и (ii).

Вторая группа (ограничения (iii) и (iv)) связана с взвешиванием графа маршрутов и вычислением весов ребер графа,, т.е. определением значений весовой функции 'p(u.v) для каждого ребра

графа G^. Во-первых, для любой вершины веУ<\{»(} должна

найтись, по крайней мере, одна вершина уе D' (и) такая, что

, где множество является образом вершины и на

графе . Во-вторых, для любых вершин-

таких, что , должна найтись,-по крайней-мере, одна

вершина ytel?(u) такая, что p(u,yt) = р{и,уг)+1 .Особенностью такого взвешивания является наличие наперед заданного множества весов 9'={I,...,/>}, причем каждый, элемент этого множества соответствует приоритету выбора направления передачи в сети сигнализации. Обозначим ориентированный

взвешенный граф, который должен быть построен с учетом ограничений!(ш) и (iv).

Третья группа (ограничения ■ (v),(vi) И (vii)) сформулирована в терминах реберной раскраски графа маршрутов. Для использования данных ограничений необходимо построить мультиграф G,t

на взвешенном орграфе . В силу свойств

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

Введем обозначения, необходимые для формулировки ограничений, на. раскраску ребер мультиграфа. G¥|. Пусть. D(u) • -образ вершины и, а В(и,х) - множество ребер мультиребра (и,х). Пронумеруем все ребра мультиребра (и,х), начиная с 0 по номер

ЛГ(и,х)-1, где Л^(«,х)=|В(и,*)|, и представим множество В(и,х) в виде:

В(и,х) = {¿„(ц,*),^,*)....., где запись Ь,(и,х) обозначает

ребро с номером 1 мультиребра (и,х), /е Л(и, х) = {0,..., Щи,х) -1}. Перенумеруем также все мультиребра, исходящие из вершины и, и обозначим а(и,х) номер мультиребра (и,х), т.е. а(и,х) е {0,...,^(и)-1}, где </(и)=|£>(и)|.

Для раскраски ребер графа <5„( введем множество с<? пронумерованных цветов, начиная с номера 0, т.е.:

*? = {0,1,...,2"-1}. (3)

Обозначим Щи,х)£г& множество цветов для . раскраски мультиребра (и,х) и заметим, что для любой вершины, и; должны выполняться соотношения:

Щ„,х)Г)Щи,у)=0, хФу, х,>»бДн),- (4)

<&= у Щи,х)„ (5)

><0(>)

Для раскраски: ребра Ь,(и,х) введем множество цветов ЧР/Си.хУеЩи.х). В силу того, что цвета, используемые для раскраски ребер с разными номерами, совпадать не должны, то имеют место следующие соотношения:

Щи,х)С]%(и,х) = 0, 1*т, 1,теЛ(и,х), (6)

I) (7)

В диссертации уточнены ограничения;, при- которых осуществляется раскраска ребер мультиграфа- . Эти ограничения ослабляют ограничения (VI) и (уп) и имеют следующий вид:

(VI*) тах\Щи,х)|- ¡^(ы, £ 1, хФу, х,уьй(и), т.е. количество

цветов,-, используемых для» раскраски мультиребер;

исходящих из вершины и, должно отличаться:не более, чем на единицу;

т.е.

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

Более подробно ограничения на маршрутизацию исследуются и, иллюстрируются примерами в разделе 1.3.

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

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

Свойство 1. Число. клик разбиения -должно быть минимально среди всех возможных разбиений.

Свойство 2. Количество вершин в наибольшей клике разбиения должно быть максимально среди всех возможных разбиений.

Свойство 3. Если существует несколько разбиений, удовлетворяющих свойствам 1 и 2, и в каждом из этих разбиений несколько наибольших клик, то выбирается разбиение, в котором таких клик больше.

В диссертационной работе показано, что свойство 3 может быть. ослаблено. В разделе 2.1 получены алгоритмы построения графов маршрутов сети с учетом ограничений (i),.(¡i) и свойств кликовых разбиений. Ниже приведен. алгоритм построения графа G, маршрутов в вершину с использованием кликового разбиения.

Алгоритм 2.4 (алгоритм построения графа С, по. кликовому

разбиению).

Шаг 1. Начальные построения.

1.1. Построить кликовое разбиение Q подграфа, порожденного множеством вершин , по алгоритму 2.3.

1.2. Выбрать вершину v,ef¡, положить /(v,) = 0 и считать эту метку постоянной.

1.3. Положить , и считать эти метки временными.

Шаг 2. Построение фронта волны первого порядка.

2.1. Построить фронт волны 1-го порядка вершины v,

2.2. Изменить t(vj)~l для всех vy и считать эти метки

постоянными.

2.3. Построить множество ребер

ШагЗ. Построение фронтов волны высоких порядков.

3.1. Цикл от А = 1.до тех пор, пока существуют /(v)=oo или к>Т.

3.2. Построить множество

3.3. Для всех вершин t{y^ = k, vyeV¡ построить фронт, волны

-113.4; Осуществить проверку для всех \т е Ш'^.

3.4.1: Если у.еТ^у,}, то = ч^'*0 1){(у.,уу):уу еШ^},

/(ум)=пип(/(у„),А+1) и если метка была временная, то считать эту метку постоянной.

3.4.2. Если у„ еТ^ и '(у.)=®. то

^|) = ^ы)и{(у.,уу):у/еЛ^}, г(у„)=*+1 и считать эту

метку постоянной.

3.4.3. Если; Vте.Тг и /(уя)=А+1 и V._, то;

'= и{(у.,уу):уу е ЯГ,'}, метка /(у.) не меняется.

3.4.4. Если; у. е^ и г(у.) = *+1 и у.е, то; • =^1")и{(у»,уу):у; е Я^'}, метка /(у.) не меняется.

3.4.5. Во всех других случаях не изменяется, метка вершины /(у.) не меняется.

Шаг4. Построение графа Ог ).

4.1. Построить множество вершин V'= У у/.

'('/Н

4.2. Построить множество ребер = .

4.3. Построить ^=Д \{(у„,уу):у.е^.УубТ^,(у,,у.)«55г|.

4.4. Построить Г = Г\{у.:у.€^,(у(,у.)й&}.

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

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

Раздел 2.3 посвящен разработке методов раскраски ребер и мультиребер мультиграфа 0< маршрутов, построенного с помощью

методов и алгоритмов предыдущих разделов. В' этом разделе получены алгоритмы раскраски: любого числа, мультиребер, исходящих из одной вершины, и любого числа ребер, содержащихся в одном мультиребре. Для реберной раскраски мультиграфа маршрутов введем два типа множеств пронумерованных цветов с,(£) = {£,£ + 1,.»,£+2'-1} (8)

и

с,{1,т) = {1, ¿+2\...Д + 2"(2'-1)}1 (9)

где / = 0,Я и т = 0,Я-1. Наиболее важные свойства этих

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

Лемма 2.1. Если даны два множества с,(£) и <,(¿+2'), то их объединение будет множеством цветов того же типа, причем

Лемма 2.2. Если даны два множества с,(£,т) и сД£+2'*",т)„ то их объединение будет множеством того же типа, причем -

см(1,т)=с1{Ь,т)ис1{1+2"*',т). (11)

Лемма 2.3. Объединение множеств второго типа р,{1,т),

1 = !,! + 2"-1 является множеством первого типа и имеет место

формула

В разделе 2.3 показано, что первый элемент множества

ЧЩи,х) определяется по формуле

где %.= 2"-

- количество - мультиребер, раскраски цветов, а 1(/<;г) - индикаторная1

которых содержат

функция. Раскраска мультиребра (и,х) графа* (3^ вычисляется по-формуле

а раскраска ребра мультиребра (и,х) имеет вид.

Теорема 2.1. Раскраска мультиребер и ребер мультиграфа по

формулам (14) и (15) удовлетворяет ограничениям (у), (у1*) и (уц*) задачи маршрутизации..

Глава 3 посвящена применению полученных в диссертации теоретических. результатов к расчету маршрутизации в сети сигнализации. В разделе 3.1 исследованы ошибки маршрутизации, которые могут возникать в реальных сетях по различным причинам

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

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

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

и степень связности сети, т.е. ат(0)1. Влияние перечисленных параметров на производительность программного средства проиллюстрировано графиком на рис. 1.

В разделе 3.3 производится анализ процесса построения маршрутов и процесса верификации маршрутизации. Каждый из процессов описан на языке ИМЬ для наиболее полного и

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

время расчета, сек

______

10 10" 10*. 10' -М-ио.'И-ю.

----И«100,|г,|»0'

Рис.1. Производительность программного средства..

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

Основные результаты диссертации отражены в следующих

опубликованных работах:

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

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

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

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

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

6. Chukarin A., Samouylov К. Tool for the Routing Planning in a Large-scale Signaling Network // Proc: 7th Int. Conf. on Telecommunications, ConTEL 2003, Zagreb.-June 2003, Pp 579-586.

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

Подписано в печать,^/ «¿У^У, Формат 60x84/16. Тираж^^экз. Усл. печ. л. -/ . Заказ ^

Типография Издательства РУДН 117923, ГСП-1, г. Москва, ул. Орджоникидзе, д. 3

РНБ Русский фонд

2004-4 21183

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

ВВЕДЕНИЕ

ГЛАВА 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. Разработано программное средство и реализован расчет маршрутных таблиц сети сигнализации.

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.