Содержание к диссертации
Введение
ГЛАВА 1. Анализ задачи маршрутизации на графе сети сигнализации
1.1. Требования к маршрутизации 12
1.2. Граф сети сигнализации 15
1.3. Ограничения маршрутизации 19
1.4. Постановка задачи исследований 33
ГЛАВА 2. Методы построения маршрутов и вычислительные алгоритмы
2.1. Метод построения графа маршрутов 36
2.2. Методы и алгоритмы построения взвешенного мультиграфа маршрутов 61
2.3. Раскраска ребер мультиграфа 76
ГЛАВА 3. Анализ процесса построения маршрутов и средства для вычислений
3.1. Методы анализа ошибок маршрутизации 89
3.2. Программные средства 100
3.3. Процессы построения и верификации маршрутов 105
3.4. Численный анализ 114
Заключение 122
Список источников 123
- Ограничения маршрутизации
- Методы и алгоритмы построения взвешенного мультиграфа маршрутов
- Раскраска ребер мультиграфа
- Процессы построения и верификации маршрутов
Введение к работе
Современные цифровые сети связи строятся, исходя из рекомендаций международных и национальных организаций по стандартизации в области телекоммуникаций [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 года, появляются публикации, где к решению задачи маршрутизации в сетях сигнализации применяется графовый подход [38-42,59-61,67-69,76,77]. Это объясняется тем, что к этому времени в США, Канаде, Японии и ряде стран Европы построены и функционируют сети, использующие цифровое оборудование со скоростью передачи 56 и 64 Кбит/сек. Эти сети имеют в своем составе большое число транзитных узлов, а решение задачи маршрутизации в таких сетях требует применения достаточно сложного математического аппарата. В ряде случаев, ввиду большой размерности сети (маршрутные таблицы содержат десятки тысяч записей) расчет маршрутов становится невозможным без создания специализированных программных средств. В работе [59] рассматриваются вопросы расчета и анализа производительности сети сигнализации в интеллектуальных сетях связи. Статья [61] посвящена разработке метода планирования сети ОКС 7, основанного на структурированном подходе, с учетом требований к показателям качества функционирования цифровой сети. Аспекты, рассматриваемые в работе [67], известным немецким специалистом В. Кляйном связаны с расчетом и проектированием сетей сигнализации большой размерности. В том числе, рассматриваются методы оценки параметров качества обслуживания в сети сигнализации. Достаточно глубоко проработанный подход, основанный на применении теории графов к проектированию сети сигнализации, впервые был представлен в работе [68]. В этой статье рассматривается сеть со специфической структурой иерархического типа, а основной результат заключается в синтезе графа сети с одновременным построением маршрутов без циклов и петель с заданным числом транзитных узлов. Статья [69] посвящена разработке алгоритмического подхода при создании программного средства для планирования сети сигнализации. Эта работа выполнена специалистами из исследовательского центра компании Siemens AG и
отличается тем, что в ней впервые был строго формализован процесс расчета маршрутов для реализации в программном средстве. В [76] описана методика выявления и локализации ошибочных записей в таблицах маршрутизации сети сигнализации, а также сделана попытка формализовать процесс поиска ошибок. В перечисленных публикациях задача маршрутизации в сети сигнализации решается в частных случаях. Исключением является монография Самуйлова К.Е. [36], где заложены основы математических методов анализа и расчета параметров качества обслуживания в сети сигнализации, в том числе, впервые в общем виде сформулирована задача маршрутизации на графе этой сети.
Известные на сегодняшний день модели и методы требуют модификации и развития в направлении ослабления ограничений на параметры задачи маршрутизации, что, в свою очередь, требует разработки соответствующих вычислительных алгоритмов. Поэтому актуальной является задача разработки методов расчета и анализа маршрутизации на графе сети сигнализации произвольной структуры с произвольно заданным набором параметров маршрутизации. Актуальным приложением в этой области является расчет маршрутных таблиц для узлов сети и их верификации, что обуславливает необходимость разработки новых алгоритмов и их реализацию в программных средствах.
В связи с изложенным, целью диссертационной работы является развитие методов и вычислительных алгоритмов для расчета маршрутизации в сети сигнализации, анализ результатов применения этих методов, а также реализация программного средства, предназначенного для расчета маршрутных таблиц узлов сети и их верификации. Перейдем к общей характеристике полученных в диссертации результатов и одновременно продолжим обзор литературы.
Диссертация состоит из 3 глав. Первая глава посвящена анализу постановки задачи маршрутизации на графе сети сигнализации, сформулированной в [36]. В разделе 1.1 приводится схема процесса планирования сети сигнализации, а также определяются ограничения на
маршрутизацию в сети сигнализации. В разделе 1.2 строится граф сети сигнализации, и вводятся основные понятия и определения, необходимые для построения маршрутов на графе сети, а также рассматривается пример соответствия введенных обозначений параметрам сети сигнализации.
Ограничения маршрутизации
В разделе 1.4 формулируется постановка задачи диссертационной работы, которая заключается в разработке аналитических методов и вычислительных алгоритмов для расчета маршрутов на графе сети сигнализации с учетом сформулированных в разделе 1.3 ограничений на маршрутизацию.
Глава 2 диссертационной работы посвящена решению поставленной задачи в части разработки методов построения маршрутов и вычислительных алгоритмов. В разделе 2.1 разработан модифицированный метод построения графа маршрутов [38], основанный на кликовом разбиении подграфа, построенного на множестве транзитных узлов сети. Исследования в области кликовых покрытий и разбиений проводились, например, в работах [18,34,49,58]. В предложенном в диссертации методе используется подход, при котором кликовое разбиение осуществляется только для подграфа, описывающего транзитную часть сети сигнализации [51]. Получены алгоритмы построения графов маршрутов в сети с произвольной структурой с учетом всех ограничений первой группы, а также показаны примеры применения алгоритмов.
Как указывалось выше, при расчете маршрутизации сети сигнализации, необходимо учесть правила расчета приоритета выбора направления передачи. Для этого в разделе 2.2 применяется метод и алгоритм взвешивания ребер графа маршрутов [36]. Этот метод позволяет учесть все ограничения второй группы на расчет маршрутов и получить необходимые значения весов для каждого ребра. Далее, необходимо определить количество ребер, содержащихся в каждом мультиребре графа сети. Эта задача решена в работах [2,36], а в диссертации предлагается модификация этих методов для увеличения пропускной способности сети при заданной структуре и величинах потоков между вершинами, а также для изменения структуры сети путем удаления вершин и ребер, незадействованных при пропуске потоков.
Раздел 2.3 посвящен разработке методов раскраски ребер и мультиребер мультиграфа, полученного с помощью методов и алгоритмов предыдущих разделов главы 2. В этом разделе предлагаются формулы, по которым осуществляется раскраска любого числа мультиребер, исходящих из одной вершины, и любого числа ребер, содержащихся в одном мультиребре, что развивает методы, предложенные в [36,40,56]. Результаты данного раздела получены с учетом методов, известных по статьям [10,22,43,46], посвященным реберным раскраскам.
Результаты главы 2 диссертации, имеют прикладное значение и используются при проектировании и расчете маршрутизации в сетях сигнализации. Они были использованы при расчете сети сигнализации Московской области [37]. Следует отметить, что в реальных сетях, по целому ряду причин объективного и субъективного характера, могут возникать ошибки маршрутизации. Для выявления таких ошибок международные и национальные организации по стандартизации предлагают наборы тестов [48,64,65], которые применяются в системах управления сетью. Однако эти проверки являются весьма ресурсоемкими и отрицательно сказываются на производительности сети. В диссертационной работе предлагается метод выявления и исправления ошибок маршрутизации, основанный на применении результатов главы 2.
Последняя третья глава посвящена применению полученных в диссертации теоретических результатов к расчету маршрутизации в сети сигнализации, проведена классификация возможных ошибок маршрутизации, а также приведен численный пример маршрутизации. В разделе 3.1 излагается метод поиска и исправления ошибок маршрутизации, основанный на графовых моделях предыдущей главы. Разработан процесс верификации маршрутизации и анализируются часто встречающиеся на практике примеры нахождения и последующего исправления ошибок всех классов. В разделе 3.2 приводится описание программного средства, разработанного на языке C++ с использованием классов MFC и алгоритмов второй главы диссертационной работы. Произведен анализ производительности программного средства, в зависимости от значений параметров сети сигнализации.
В разделе 3.3 проведен анализ процесса построения маршрутов и процесса верификации маршрутизации. Каждый из процессов описан на языке UML для наиболее полного и адекватного воспроизведения поведения системы [4,9,12,16,72]. В заключительном - четвертом разделе главы 3 разработан численный пример маршрутизации, который показывает применение методов и программного средства для расчета маршрутных таблиц сети сигнализации.
Таким образом, в диссертационной работе решаются перечисленные ниже актуальные задачи. 1. Исследование и анализ графовой модели сети сигнализации и ограничений на построение графов маршрутов. 2. Разработка метода и вычислительных алгоритмов, использующих кликовые разбиения, для построения маршрутов на графе сети сигнализации с произвольной структурой. 3. Разработка метода и вычислительного алгоритма для реберной раскраски мультиграфов маршрутов с произвольным числом ребер и мультиребер. 4. Применение разработанных методов и алгоритмов к расчету маршрутных таблиц сети сигнализации. Классификация ошибок маршрутизации и разработка методов коррекции ошибок. 5. Разработка программного средства для расчета маршрутных таблиц, реализующего разработанные алгоритмы, и его применение к расчету сетей сигнализации.
Методы и алгоритмы построения взвешенного мультиграфа маршрутов
В данном разделе предложены метод и алгоритм построения взвешенного графа маршрутов Gv =\Y\ \ ДЛя того, чтобы были выполнены ограничения (iii) и (iv) на маршрутизацию из раздела 1.3. Напомним, что множество Р = \\,...,Р] является множеством значений, которые может принимать весовая функция p(u,v) для каждого ребра (w,v)e. /v.. Вообще говоря, множество $Р является общим для всех графов Gv., v, є Т{ . Как уже было отмечено выше (см. раздел 1.2) образ вершины и на графе G обозначается через D (и). Отметим также два типа вспомогательных множеств. Во-первых, это множество D p(u), соответствующее всем тем вершинам х множества D (и), для которых вес ребра (и,х) равен р, т.е. р(и,х) = р. Очевидно, что (w)c D (u), причем равенство достигается только в том случае, если вес всех ребер р(и,х), xeD {u) одинаковый, и, в силу ограничения (iii), р(и,х) = \, xeD (w). Вторым вспомогательным множеством является F {u), соответствующее всем таким вершинам у множества D (и), для которых вес ребра (и,у) больше значения р, т.е. р(и,у) р. Очевидно таюке, что F {u) = F p_x{u)\D p{u). Это следует из формулы (1.13), где F0 (и) = /) («). Используя введенные обозначения, сформулируем алгоритм взвешивания ребер ориентированного графа Gv , полученные в [36]. Идея алгоритма заключается в следующем. Последовательно рассматриваются все вершины графа Gv . Для каждой вершины и строится множество FQ (и) = D (и). Функция р принимает начальное значение 1. Общая итерация алгоритма такова. Необходимо найти все кратчайшие маршруты из вершины и в вершину v,, проходящие через вершины х, принадлежащие множеству F p_x (и). Наиболее простым способом является применение алгоритма восстановления кратчайшего пути в ориентированном графе [26,33,58] для всех пар вершин jce ., (и) и v,. Затем, основываясь на полученных результатах, нужно построить множество D p(u) и определить значение весовой функции р(и,х) для всех вершин х є D p{u), где р{и,х)-р. После этого, нужно по формуле (1.13) построить множество F (u) и, если полученное множество F p (и) - 0, то завершить работу с рассматриваемой вершиной и перейти к следующей. Если же множество F p{n) - непусто, то увеличить р = р + \ и, если р Р, то совершить следующую итерацию алгоритма, а если р Р, то так же, как и в случае пустоты множества F {u), завершить рассмотрение вершины и и перейти к работе со следующей вершиной. Итерации должны быть продолжены, пока существуют вершины, служащие началом невзвешенных ребер.
Алгоритм 2.5 (алгоритм взвешивания ребер графа маршрутов Gv ). Шаг 1. Задание начальных значений. 1.1. Выбрать вершину ueV \{vt], являющуюся началом невзвешенных ребер. 1.2. Построить множество F0 (и) = D (и). 1.3. Определить р = 1. Шаг 2. Вычисление весов ребер. 2.1. Найти кратчайшие маршруты из вершины и в вершину v(, проходящие через вершины множества F p_\ (и). 2.2. Построить множество D p{u). 2.3. Вычислить р(и,х) = р, хєD p(и). Шаг 3. Проверка выполнения условий. 3.1. Построить множество F p(u). 3.2. Если множество і (м) = 0 и существует вершина, служащая началом невзвешенных ребер, то перейти к шагу 1.1. 3.3. Если множество F u)-0 и все вершины просмотрены, то завершить работу алгоритма. Увеличить р = р + \ и, если р Р, то перейти к шагу 2.1. Иначе, если существует непросмотренная вершина, то перейти к шагу 1.1. Иначе завершить работу алгоритма. Рассмотрим пример применения алгоритма к взвешиванию графа, показанного на рис.2.5. Пусть Р = 2, т.е. 3і = {1,2}. Начнем рассмотрение с вершины v2. Образ этой вершины ) (v2) представляет собой множество вершин D1 (v2) = {v6, v7, v9}. Следовательно, F0 (v2) = {v6, v7, v9}. Определим p = \. Перечислим маршруты из v2 в v,, проходящие через вершину v6 - это будет (v2,v6,v,), через вершину v7 - (v2,v7,v6,v,) и (v2»v7»vio vi) и чеРез вершину v9 - (v2,v„v6,v,) и (v2,v9,v10,v,). Среди полученных маршрутов кратчайшим является (v2,v6,v,), проходящий через v6. Таким образом, D (v2) = {v6}, а значение функции /?(v2,v6) = l. Множество (v2) = {v7,v9}. Это множество непустое, следовательно, продолжаем взвешивать ребра, исходящие из v2. Увеличим р = р +1 = 2, и так как р Р, то, на основании полученных маршрутов, проходящих из вершины v2 через v7 и v9 в вершину v,, можем утверждать, что все эти маршруты равны по длине, следовательно, 2( ) = ( 9} а значение функции р (v2, v7) = р (v2, v9) = 2 . Множество F2 (v2) = 0, поэтому необходимо выбрать следующую вершину для взвешивания ребер из нее исходящих. Таким образом, процедура повторяется для всех вершин графа Gv . Результат работы алгоритма показан на рис.2.17.
Однако, предложенный подход к взвешиванию ориентированного графа Gv не единственный. Предположим, например, что каждую вершину и каждое ребро графа характеризует дополнительная весовая функция ft (v) или co(u,v), ставящая в соответствие выбранному элементу некоторое действительное число. Для простоты изложения пусть это число будет из интервала [0,1], где 0 характеризует абсолютную ненадежность, а 1 - абсолютную надежность вершины или ребра. В таком случае, очевидно, что подход к определению длины маршрута и последующему взвешиванию ребер, предложенный в алгоритме 2.5, становится не самым адекватным для решения поставленной задачи. И, если на шаге 2.1 алгоритма длина маршрута определялась количеством задействованных в нем ребер и, исходя из этого, назначался вес ребрам кратчайших маршрутов, то при использовании дополнительной весовой функции длину маршрута целесообразно вычислять по-другому. Предлагается традиционный [28,29,59] способ вычисления длины маршрута произведением значений дополнительных весовых функций всех элементов, в него входящих. При этом возникает некоторая сложность, заключающаяся в выборе метода ранжирования маршрутов по весу из множества SP. Рассмотрим несколько вариантов таких методов.
Раскраска ребер мультиграфа
Как методы расчета маршрутизации главы 2, так и методы анализа и выявления ошибок маршрутизации раздела 3.1 весьма затруднительно применять при расчете маршрутизации графа, соответствующего сети большой размерности. Считается [13,36,44,80], что сеть имеет большую размерность, если количество оконечных узлов измеряется сотнями, транзитных узлов - десятками, а сигнальных отношений - тысячами. В таком случае, общее число записей в маршрутных таблицах может доходить до 10000 и более, поэтому численное решение задачи маршрутизации практически невозможно в отсутствии специализированных программных средств. Такое программное средство было создано для решения широкого круга задач, связанных с проектированием и расчетом сетей сигнализации, а также анализа производительности этих сетей.
Сформулируем основные спецификации и требования к программному средству. Существует две группы требований. Во-первых, это группа общих требований. Программное средство должно иметь общецелевое предназначение, т.е. обеспечивать проектирование, осуществление дополнений к проектам и проведение исследований. Программа должна быть гибкой и масштабируемой для обеспечения реализации всех особенностей и тонкостей решения конкретной задачи, а таюке - полностью модульной, т.е. предоставлять множество открытых интерфейсов для добавления необходимой функциональности. Во-вторых, программное средство должно отвечать некоторым системным требованиям, таким как наличие механизмов взаимодействия, с базами данных, что требуется для импорта и экспорта существующих данных; оптимизированные алгоритмы и программные решения, для максимальной программной производительности, а также простота использования, обеспечиваемая ясными и понятными интерфейсами пользователя и интегрированными логическими процессами.
Программное средство написано на языке C++ с использованием классов MFC. Оно реализовано для платформы семейства операционных систем Windows NT, поскольку объектная ориентированность и удобство этих систем обеспечивают достаточную гибкость и надежность, учитывая приведенные выше ограничения. Программное средство предоставляет широкие возможности для решения задач, возникающих при планировании сети сигнализации. Наиболее полезными из которых являются ввод и редактирование данных о сети сигнализации, расчет маршрутизации, сигнальной нагрузки и емкостей пучков звеньев сигнализации, разделение сигнальной нагрузки и расчет кодов селекции звена сигнализации, создание маршрутных таблиц, проверка маршрутизации и анализ производительности сети.
Структура программного средства состоит из четырех основных блоков, как показано на рис.3.13. Ниже приводится их краткое описание. Графический интерфейс пользователя (ГИП) обеспечивает взаимодействие пользователя со всеми возможностями, предоставляемыми программным средством. Пользователю с помощью ГИП легко создавать сеть, управлять этой сетью, решать возникающие задачи, рассчитывать маршрутизацию или сигнальную нагрузку, а таюке работать со всеми другими функциями программного средства. Механизмы взаимодействия с базами данных не являются одним из специальных вычислительных модулей. Это системные методы, интегрированные в программное средство для выполнения требований, сформулированных выше. Взаимодействие с базами данным осуществляется посредством XML. Набор вычислительных модулей программного средства представляет собой библиотеки функций, необходимые при решении различных задач сетевого проектирования или расчета. Такими задачами являются, например, расчет маршрутизации, разделение сигнальной нагрузки, проверка корректности маршрутизации, анализ производительности и ряд других. Ядро программного средства является его основной частью. Оно обеспечивает управление структурой сети, работу с диском, т.е. сохранение и загрузку проекта, реализацию системных функций, интерфейсы ко всем другим структурным блокам программы и другим подсистемам. Пример работы программного средства показан на рис.3.14. На этом рисунке приводится одно из представлений ГИП, в данном случае - это графическая диаграмма сети. Изображенная сеть состоит из 8 транзитных узлов и 6 оконечных узлов. Некоторые оконечные узлы могут образовывать, так называемые, кластеры [16,19,36,44], по принципу их связности с транзитными узлами. Пользователь программного средства обладает возможностью просмотра и работы со списками пунктов сигнализации всех типов, пучков звеньев сигнализации и другими. Пользователь может управлять структурой сети через систему специальных меню и других элементов ГИП. На основной панели программного средства размещен набор кнопок быстрого доступа к просмотру, печати и экспорту полученных результатов. Программное средство было протестировано на ПК с производительностью процессора, эквивалентной 1 ГГц, для определения скорости проведения расчетов с различной структурой сети и изменяющимся параметром сетевой связности. Отметим, что расчет маршрутизации включает в себя все проверки на корректность маршрутизации. Было установлено, что программная производительность зависит, в основном, от трех параметров. Этими параметрами являются количество сигнальных отношений, соответствующее в терминах теории графов мощности множества количество транзитных узлов, соответствующее \У 2\, и степень связности сети, что соответствует K(G) . Очевидно, что i% CMTJ" J, поскольку 91 х %. Влияние перечисленных параметров на производительность программного средства проиллюстрировано на рис.3.15.
Процессы построения и верификации маршрутов
На этапе проектирования программного средства, описанного в предыдущем разделе, были разработаны основные процессы с использованием языка UML [9,72], реализованные затем в программе. Такой подход предназначен для моделирования последовательных и одновременных фаз вычислительного процесса. Для этого проектирования был использован один из наиболее распространенных и удобных типов диаграмм - диаграммы действий. Причина этого в том, что с помощью таких диаграмм можно наглядно моделировать функционирование системы. При моделировании некоторых специфических особенностей программного средства использовались и другие типы UML-диаграмм.
Поведенческие аспекты использования программного средства моделировались с помощью диаграмм действий, как это показано на рисунках ниже. Проанализируем основные детали базового процесса сетевого планирования [36,56], фрагмент которого изображен на рис.3.16.
Сеть сигнализации состоит из пунктов сигнализации различных типов, которые соединены пучками звеньев сигнализации. Все пункты сигнализации и пучки звеньев образуют структуру сети. В рамках этой структуры должны быть рассчитаны маршруты между парами узлов, находящихся в сигнальных отношениях. Когда пользователь создает заново или вносит изменения в структуру сети программное средство должно обеспечивать контроль корректности манипуляций, им осуществляемых, с помощью соответствующих алгоритмов. Все такие алгоритмы включены в реализацию действия «Создание/изменение структуры сети» базового процесса сетевого планирования.
Этот элемент диаграммы действий спроектирован на основе результатов, полученных в главе 2. Все вычисления, благодаря эффективным алгоритмам, «прозрачны» для пользователя. Проектировщик сети должен лишь указать ограничения расчета, такие как максимально допустимое число переприемов на маршрутах Т, максимальный приоритет выбора направления передачи Р и количество битов кода селекции звена сигнализации Н.
Структура сети может быть изменена добавлением, модификацией или удалением элементов сети, таких как пункт или звено сигнализации. Такие изменения направлены на улучшение и оптимизацию структуры сети и внесение соответствующих изменений в маршрутизацию.
Этот этап предназначен для реализации алгоритмов решения одной из важнейших задач сетевого планирования - верификации маршрутизации. Он включает в себя набор тестов для проверки маршрутизации на отсутствие циклов и петель, доступности пунктов сигнализации, реализации сигнальных отношений, корректности распределения битов поля селекции звена сигнализации, а также выполнения правил присвоения приоритетов выбора направления передачи.
Диаграмма, показанная на рис.3.16, расположена на самом высоком уровне абстракции при моделировании функционирования программного средства. Для построения более точных моделей поведения системы необходимо разработать диаграммы действий более низких уровней абстракции. Рассмотрим 2 наиболее важных из таких диаграмм. Во-первых, это диаграмма действий процесса построения маршрутов, изображенная на рис.3.17 со всеми основными деталями. Во-вторых, таким процессом является процесс верификации маршрутизации, показанный на рис.3.18.
Процесс построения маршрутов является линейным без циклов и ветвлений. Такая линейная структура получена, благодаря тому, что в основе каждой фазы процесса лежит строгий математический метод и вычислительный алгоритм. Приведем краткое описание основных действий, составляющих процесс построения маршрутов. Проанализируем также, какие методы и алгоритмы главы 2 используются при этих действиях. Действие «Выделение в транзитной сети полносвязных подсетей».
Эта фаза процесса расчета маршрутов соответствует использованию алгоритма 2.1 раздела 2.1, для случая полносвязного графа транзитной сети, или алгоритма 2.3 того же раздела, в случае существования кликового разбиения графа транзитной сети. На этом этапе происходит начальная обработка исходных данных.
