автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Формализация методов разработки алгоритмического обеспечения систем коммутации

«« 011,

13 ®С'

На правах рукописи

ЦУПРИКОВ Андрей Леонидович

ФОРМАЛИЗАЦИЯ МЕТОДОВ РАЗРАБОТКИ АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ СИСТЕМ КОММУТАЦИИ

Специальность 05.12.14. - Сети, узлы связи и распределение информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

САНКТ-ПЕТЕРБУРГ 1998

Работа выполнена в Санкт-петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч - Бруевича

Научный руководитель - д.т.н., проф. А.Н. БЕРЛИН

Официальные оппоненты:

д.т.н., проф. Дьшарский Я.С. к.т.н. Ткачман И.Н.

Ведущее предприятие

диссертационного совета К 118.01.01 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186 СПб, наб. р. Мойки, 61.

С диссертацией можно ознакомиться в библиотеке университета.

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

Автореферат разослан 1998 г.

АО «ИНТЕЛТЕХ»

Защита диссертации состоится

заседании

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Создание новых сетей связи, равно как и модернизация старых, основывается в настоящее время на внедрении цифровых систем передачи и обработки информации. Подобные системы, уже в случае их использования только в отдельных звеньях сети, позволяют обеспечить предоставление ряда услуг, до этого являвшихся недоступными, а введение в эксплуатацию цифровых сетей, как междугородных так и местных оказывает существенное влияние уже на саму инфраструктуру общественной формации.

Как известно любая сеть связи состоит из трех основных компонентов: систем коммутации, систем передачи и каналов связи. Наиболее сложным элементом в составе сети являются системы коммутации. При этом с увеличением «интеллектуальности» сети увеличиваются требования, предъявляемые к ее компонентам и в первую очередь к системам коммутации.

На сегодня, основной задачей, решаемой в процессе создания систем коммутации является разработка программного обеспечения. Как показано в ряде источников и как признают сами разработчики, этап создания алгоритмического и программного обеспечения является наиболее сложным и трудоемким, занимая до 90% ресурсов всего проекта.

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

На сегодня можно констатировать, что практически каждая крупная фирма, занимающаяся созданием систем связи имеет собственную технологию для разработки программного обеспечения, стоящуюся на использовании различных инструментальных систем, таких как система NBS Национального бюро стандартов США, система ITU-T PANDORA, системы RNIN, S DT, SPIDER, EWS, SQUIGGLES и т.д. Из отечественных систем молено выделить ПРАНАС и АРХИТЕКТОР. Каждая из систем использует определенный язык формального описания. Основными из которых являются SDL, LOTOS, ESTELLE, PSL, RSL, SA, COSY, из отечественных языков наибольшую известность получили SDL/PLUS и ОСА.

Вместе с тем, вопросам математического описания алгоритмических процессов систем работающих в реальном режиме времени посвящено гораздо меньше исследований (А.Н. Берлин, В.Н. Агафонов, И.В. Вельбицкий, В.В. Липаев, В.Е. Котов, J. Piterson, M. Alford). Что связано с рядом факторов, основными из которых являются:

• существовавшая до последнего времени аппаратная база налагала жесткие требования на программное обеспечение, делая его в ряде случаев ориентированным не па абстрактное

решение тех или иных алгоритмических задач, а на решение этих задач с учетом специфики той или иной аппаратной среды;

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

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

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

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

Методы исследования. Решение поставленных задач осуществлялось с использованием • методов теории вычислимости и теории конечных автоматов.

Научная новизна работы заключается в следующем:

• проведено исследование принципов построения алгоритмического обеспечения систем коммутации и показано, что процесс обслуживания вызова узлом коммутации может быть описан математической моделью Расширенного Конечного Автомата (РКА) с использованием того или иного класса вычислимых функций;

• получена универсальная функция для функций описывающих работу конечных автоматов;

• в результате исследования способов представления универсальной функции для конечных автоматов сделан вывод о целесообразности использования табличной формы представления (универсальной таблицы);

• разработана методика перехода от описания КА в виде БОЬ-диаграмм к его описанию в форме универсальной таблице;

• разработан алгоритм обработки универсальной таблицы.

Практическая ценность проведенных исследований заключается в следующем.

Предложенная методика представления алгоритмического обеспечения систем

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

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

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

Основные положения, выносимые на защиту:

1. Предложенная модель представления алгоритмического обеспечения систем коммутации.

2. Методика перехода от описания алгоритмического обеспечения систем коммутации в виде БОЬ-диаграмм к его описанию в форме универсальной таблицы. .

3. Функциональное описание алгоритмов работы узла коммутации с использованием класса вычислимых функций (МНР-операторов).

4. Разработанный алгоритм обработки универсальной таблицы.

5. Принципы организации вычислительного процесса., системы коммутации, алгоритмическое обеспечение которой строится на основе метода универсальной программы.

6. Принципы организации вычислительного процесса тестирования ситуаций взаимодействия протоколов сигнализации, алгоритмическое обеспечение которого строится на основе метода универсальной программы.

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

Апробация результатов работы. Результаты работы обсуждались и были одобрены на 49, 50, 51, 52, 53 научно-технических конференциях профессорско-преподавательского состава Государственного университета телекоммуникаций. По результатам диссертации опубликовано 10 работ.

Личный вклад автора. Основные научные положения, теоретические выводы и рекомендации, содержащиеся в работе, получены автором самостоятельно.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и 4 приложений.

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

Во введении обосновывается актуальность темы исследования, сформулированы цели и задачи работы, перечислены основные результаты диссертации, определена практическая

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

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

; алгоритмического обеспечения различных систем коммутации.

5 На основании анализа решаемых в процессе разработки задач приводится обобщенная

- ■ "

; схема разделения технологии на этапы.

I В соответствии с этой схемой выделяется шесть основных технологических этапов:

!

! - спецификация и планирование системы;

- системное проектирование; . - детальное проектирование;

■ '..",■ -кодирование;

- отладка программного обеспечения; .

"*эксплуатация и сопровождение программного обеспечения. / " , . ' '

Первые три из которых относятся непосредственно - к разработке алгоритмического обеспечения, на четвертом и пятом выполняется переход от алгоритмического обеспечения к

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

■ составе сети. ',■'..-.

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

' Поэтому первоочередной задачей, решаемой в процессе разработки алгоритмического обеспечения является создание формальной спецификации, описывающей поведение системы. Основными формализмами, использующимися при этом являются математические модели расширенного конечного автомата (РКА), сетей Петри, диалоговых матриц, функциональных отношений М1, алгоритмических операторов М2 и т.д. Как показано в ряде источников, математическая модель РКА наиболее широко используется для получения описаний, допускающих автоматическую обработку.

■ .. Математическая модель РКА допускает несколько эквивалентных способов задания, основными из которых являются аналитический, графический и матричный.

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

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

характеризует разнообразие интеллектов разработчиков, а также их желание иметь собственные средства нежели действительную необходимость.

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

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

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

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

Рисунок 1. Математическая модель работы конечного автомата при обслуживании нескольких вызовов.

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

- состояние процесса в момент времени Ъ; Х(1) = {х,, х2, х,,... х„} XI - х„ - входной сигнал;

= {аь а2, в* ... ат} а1 - а„- решаемая задача; У(^ = {у1,у2,у1, ...Ук} у 1 - ук - выходной сигнал; Б^-и) - состояние процесса в момент времени ^ь j - номер вызова, обслуживаемого системой. Н, М, Э - функции, определяющие работу автомата.

В соответствии с приведенной моделью проектирование алгоритмического обеспечения сводится к описанию функций Н, в, М.

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

Вместе с тем этот подход имеет следующие недостатки:

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

• алгоритм, определенный в терминах языка спецификаций, для его последующей автоматической трансляции в прикладную программу на конкретном языке программирования требует наличия транслятора, который является уникальным для каждой пары <язык спецификаций - язык программирования^ Здесь следует заметить, что разработка подобных трансляторов с одной стороны является достаточно сложной, а следовательно дорогостоящей операцией, а с другой стороны зачастую изменение версии одного из компонентов пары требует создания нового транслятора либо внесения серьезных изменений в уже существующий.

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

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

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

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

команда обнуления Z(n). Эта команда заставляет машину заменить содержимое R„ на 0, не затрагивая другие регистры;

команда прибавления единицы S(n). Под действием этой команды МНР увеличивает содержимое регистра на 1, не изменяя содержимого других регистров;

команда переадресации Т(ш,п). Ответом МНР на эту команду является замена содержимого R„ содержимым Rm, при этом все другие регистры ( включая R,„) не изменяют своего содержимого;

команда условного перехода J(m,n,q). Под действием этой команды сравниваются значения регистров Rm и R„, и если их содержимое равно, то осуществляется переход к выполнению q-й команды. Если содержимое регистров не равно, то выполняется следующая за данной команда.

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

Универсальной называется программа вычисляющая универсальную, для данного класса функций, функцию. Универсальной функцией для n-местных вычислимых функций называется (n+1 )-местная функция ^', определяемая соотношением:

y/ff (е, х,, х2,..., х„) = (х,, х2,..., XfJ.

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

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

Универсальная функция для описания конечных автоматов является трехместной и в качестве аргументов использует параметры - состояние, X - входной сигнал, е^ - кодовое число функции. Сама функция имеет вид:

Результатом вычисления являются N51 - следующее состояние, У - выходной сигнал или сигналы.

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

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

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

I \ I 51 1 X | ; | д, | т, | ... | д„ I ты | А1 | ... | А5 1 У, | ... | Ук |К81] Рисунок 2. Формат строки универсальной таблицы.

■ где

] - номер строки в таблице;

1 - номер строки внутри блока соответствующего определенной паре [Б!, X];

41 - Чи - условия определяющее условные переходы или циклы;

Ш1 - шц - строка внутри блока на которую должен быть осуществлен переход если соответствующее условие выполняется.

Универсальная таблица для описания работы конечного автомата строится в результате объединения блоков, описывающих его поведение для каждой из пар [Б!, X].

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

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

Так как обработчик ЭВМ системы коммутации работает только со структурой таблицы и не предполагает знания о ее содержимом, то обслуживание различных таблиц может производиться одним и тем же алгоритмом, использующим в качестве параметров информацию о структуре данной таблицы. Функциональное выражение для алгоритма обработчика универсальной таблицы, определенное в терминах МНР-операторов, имеет вид: (Г, №) = /и (X, 51) где

где

\ может принимать значения на промежутке 0¡,1) ; г принимает значения на промежутке О, К ;

У = (20), Л,, д1), ад, ШдЗ), ад, 3(1Хд1), д2->):

;о = (2(п), ад, гр), д]->3((д„&д„ш), о, д2), ЗД, 3(п, N+1, дЗ), 3(Ц,д1), д2->Б(0, 3(Ц д1),

чЗ->);

/„/ = (Т(Щ, Т(п,п1 д1->3((д„&д^,0,д2), 5(п), 3(п, N+1, дЗ), 3(и,д1), 3(Ц,д1),

д3->3(г,яя4'), 3(Ц,д7), д4->3(М51„,-\д5), 3(1,щ7), д5->3(тт'-',дб), ;=/'+т„, ?б->ад, 17->);

го = 0;

,= у(гЛя1), од, я1->г(г)); л® =

где

] = (20). Л„ ад, ШдЗ), д!->3(Х,Хмд2), ад, д2->);

I = (ЗД, гГиЛ ЭД, д1->Щ(2„&йшдМ2). ад, д5->Цп№1,дЗ), 3(Щ1), д2->3(1), 3(и,д1),

д3->3(Ш, '-',д4), Щ1,дб), д4->Ы+тп 3(Ц,д5), д6->). Разработанный алгоритм обработчика универсальной таблице представлен в диссертационной работе.

Во-вторых, представление алгоритмов систем коммутации в математическом виде после его описания с использованием формального языка, конструкции которого более удобны для разработчика, позволяет упростить процесс трансляции в язык программирования, и отказаться от дорогостоящих трансляторов <язык спецификации - язык программирования^ заменив их трансляторами типа <язык спецификаций - математическая функция> и <математическая функция - язык программирования:». Действительно, функциональное выражение, определяющее алгоритм, может быть транслировано в прикладную программу на том или ином языке программирования, при условии, что в последнем определены базовые функции класса, на котором ведется описание алгоритма. В диссертационной работе представлена разработанная

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

Методика перехода от SDL-диаграммы к универсальной таблице состоит из следующих этапов:

1) декомпозиция SDL-диаграммы. На этом этапе осуществляется разделение SDL-диаграммы, на участки, которые в последующем будут описываться в универсальной таблице как одна функция A, Y или Q;

2) кодирование SDL-диаграммы. На этом этапе каждой задаче, условию и сигналу ставится в соответствие некоторая переменная;

3) функциональное описание SDL-диаграммы. На этом этапе алгоритм, представленный SDL-диаграммой описывается в терминах МНР-операторов;

4) нумерация функционального описания. На этом этапе МНР-описание участков алгоритма определенных на этапе 1, кодируется с использованием той или иной системы нумерации;

5) формирование отдельных блоков. На этом этапе осуществляется построение отдельных блоков с использованием кодовых чисел, полученных на предыдущем этапе;

6) формирование универсальной таблицы. На этом этапе осуществляется объединение отдельных блоков в таблицу.

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

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

и

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

Разработка отдельных модулей велась в соответствии со следующими этапами:

1. Определение и функциональных зависимостей. На этом этапе каждый выходной сигнал алгоритма определяется как некоторая функция от входных сигналов.

2. Определение форматов представления информации и переменных. На этом этапе информация, с которой работает алгоритм представляется в определенном формате, с которым связывается ряд переменных.

3. Графическое описание алгоритмов и определение задач. Здесь алгоритм описывается в терминах языка SDL и производится разделение алгоритма на отдельные задачи в соответствии с правилами, определенными в главе 2.

4. Описание алгоритма в терминах МНР-операторов.

5. Представление алгоритмов в форме таблицы.

6. Определение настраиваемых параметров, разграничение собственных переменных алгоритма и переменных вызова, обрабатываемых алгоритмом.

Математические выражения, для всех рассмотренных алгоритмов приведены в диссертационной работе.

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

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

Функциональное выражение для алгоритма простого сканирования имеет следующий вид:

{(Uh .... (Ш =faJA,B)

где

(ij) - координаты объекта, изменившего свое состояние;

А - массив, отражающий состояние сканируемых объектов в момент времени t;

В - массив, отражающий состояние сканируемых объектов в момент времени t+1;

МАЛ) = (Z(i), Z(j), Z(n), q2->J(a¡1,b¡i,ql), T((ij)m (ij)), S(n), T(b4,aJ, ql->S(j), J(j,J+l),q2), S(i),Z(j),J(U+l,q2))

Алгоритм сканирования по флажку функционально выражается в следующем виде:

№)о.....ОМ =МЛВ,С)

где

С - массив, отражающий количество циклов сканирования в течении которых Существует изменение. -- ■ , ■

МА.В,С) = (Z(i), Z&, Z(n), q2->J(a¡¡,b¡j,ql), Jfc^Cl.q}), S(C¡Í), Jfi.i.ql), q3->T((i,j)„,(ij)), S(n), m.j.a.j), Z(c,¡), ql->S(¡), J(i,J+ J),q2), S(i), ZQ), J(i,I+l,q2))

где

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

Алгоритм сканирования по флажку имеет следующий вид: {fl.Uh 0J.M 'МАЛ)

где

t. - тип изменения состояния;

МАЛ,С) = (Zfi), т 2(П). q2->J(a:j,b¡j,ql), J(a»0,q3), T((i,j,t)„,(i,j,l)), J(i,i,q4), q3-> Т((ЩШМ q4->S(n), Т(Ъфа,;, ZfcJ, ql->S(j), J(jJ+l),q2), SO), Z(¡), J(U+í,q2))

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

Ко второй группе относятся алгоритмы приема номера и приема и передачи информации По соединительным линиям. В диссертационной работе получены функциональные выражения для алгоритма приема номера от дискового номеронабирателя.

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

Алгоритм пересчета номера применяется, при наличии на станции различных систем нумерации одного и того же объекта для пересчета номера объекта из одной системы нумерации в другую. В работе получены функциональные выражения для алгоритмов прямого и двухступенчатого пересчета. •■ '■

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

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

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

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

При работе узла коммутации в каждый момент времени существует как правило несколько вызовов. За каждым обслуживаемым вызовом закрепляется процесс. Под прЬцессом будем понимать область памяти, отводимую для обслуживания вызова. Процесс может находится в одной из трех очередей: . . ', ■

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

- очередь процессов "ожидающих выполнения", в этой, очереди находятся процессы,, в которых определено значение входного сигнала' и которые должны быть обслужены в соответствии с парой [Б^ X];

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

Модель, отражающая обслуживание нескольких процессов представлена на рисунке 3.

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

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

В диссертационной работе в рассматривается алгоритм установления местного соединения, для которого приводится универсальная таблица.

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

Четвертая глава посвящена вопросам использования принципа универсального алгоритма при разработке программного обеспечения для тестирования ситуаций взаимодействия систем сигнализации У5.2 <-> КиР-Л. Структурная схема проектирования с указанием соответствующих документов, приведена на рисунке 4.

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

Рисунок 4 Этапы проектирования и разрабатываемые документы ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

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

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

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

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

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

Описана организация вычислительного процесса строящегося в соответствии с принципом универсального алгоритма для систем коммутации с централизованным управлением.

Определены этапы проектирования и описаны принципы организации вычислительного процесса тестирования взаимодействия протоколов систем сигнализации, реализуемого в соответствии с принципом универсального алгоритма.

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Цуприков А.Л. Сравнение систем нумераций//Сб.науч.тр.завед.связи/ СПбГУТ.-СПб, 1996.

2. Цуприков А.Л. Использование рекурсивных функций для описания алгоритмов функционирования АТС//49 НТК:Тез.докл./ СПбГУТ.-СПб,1996.

3. Цуприков А.Л. Унификация программного интерфейса узлов коммутации //50 НТЮТез.докл./ СПбГУТ.-СПб,1997.

4. Цуприков А.Л. Представление алгоритмов работы систем коммутации с помощью таблиц//51 НТК.'Тез.докл./ СПбГУТ.-СПб, 1997.

5. Цуприков А.Л. Методы построения и обработки алгоритмических таблиц. //51 НТК:Тез.докл./ СПбГУТ.-СПб, 1997.

6. Цуприков А.Л. Математическое определение функций, описывающих работу расширенного конечного автомата//52 НТК:Тез.докл./ СПбГУТ.-СПб, 1998.

7. Цуприков А.Л. Функциональное описание основных алгоритмов работы узла коммутации//52 НТК'.Тез.докл./ СП6ГУТ.-СП6Д998.

8. Цуприков А.Л. Организация вычислительного процесса узла коммутации с централизованным управлением//52 НТЮТез.докл./ СПбГУТ.-СПб, 1998.

9. Цуприков А.Л. Использование универсальных таблиц при организации вычислительного процесса тестирования протоколов систем сигнализации //53 НТК: Тез .докл./ СПбГУТ.-СПб,1998.

10. Цуприков А.Л. Проверка корректности протокольных реализаций, строящихся на использовании метода универсальной таблицы//53 НТЮТез.докл./ СПбГУТ.-СПб,1998.

Государственный комитет по связи и информатизации Российской Федерации. САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМЕНИ ПРОФ. М.А. БОНЧ-БРУЕВИЧА

На правах рукописи УДК 621.395.34

ЦУПРИКОВ АНДРЕЙ ЛЕОНИДОВИЧ

ФОРМАЛИЗАЦИЯ МЕТОДОВ РАЗРАБОТКИ АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ СИСТЕМ КОММУТАЦИИ

05.12.14. - Сети, узлы связи и распределение информации

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук профессор А.Н. Берлин

Санкт-Петербург 1998

Содержание

Стр.

Введение...............................................................................................................4

1. Методы разработки программного обеспечения систем, работающих в реальном режиме времени.....................................................10

1.1 Технологические этапы разработки программного обеспечения..............10

1.2 Инструментальные средства проектирования программного обеспечения больших систем........................................................................14

1.3 Математические модели систем телекоммуникаций..................................18

1.4 Математические методы представления алгоритмических задач.............22

Выводы...................................................................................................................29

2. Использование таблиц для описания конечных автоматов.........................30

2.1 Определение табличных форм......................................................................30

2.2 Алгоритм обработчика универсальной таблицы.........................................41

Выводы..................................................................................................................44

3. Описание алгоритмического обеспечения узла коммутации

с использованием метода универсальных таблиц........................................46

3.1 Описание основных алгоритмов работы узла коммутации........................46

3.1.1 Алгоритм сканирования..............................................................................47

3.1.2 Алгоритм выдачи периферийных команд.................................................57

3.1.3 Алгоритм пересчета.....................................................................................63

3.1.4 Алгоритм приема номера............................................................................69

3.1.5 Алгоритм анализа номера и выбора направления....................................78

3.1.6 Алгоритм поиска промежуточных путей..................................................83

3.1.7 Алгоритм таймера........................................................................................91

3.2 Описание организации вычислительного процесса

системы коммутации......................................................................................94

3.3 Описание алгоритма обслуживания вызова с использованием

универсальной таблицы.................................................................................100

Выводы..................................................................................................................113

4. Использование метода универсальной программы при разработке

программного обеспечения протоколов систем сигнализации...................115

4.1 Описание объекта исследования...................................................................116

4.2 Определение этапов разработки и задач, решаемых на

каждом из этапов............................................................................................117

4.3 Описание организации вычислительного процесса....................................123

Выводы..................................................................................................................133

Заключение............................................................................................................134

Литература.............................................................................................................137

ПРИЛОЖЕНИЕ 1..................................................................................................144

ПРИЛОЖЕНИЕ 2..........................................................................162

ПРИЛОЖЕНИЕ 3............................................................................198

ПРИЛОЖЕНИЕ 4............................................................................218

ВВЕДЕНИЕ

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

Как известно любая сеть связи состоит из трех основных компонентов: систем коммутации, систем передачи и каналов связи. Наиболее сложным элементом в составе сети являются системы коммутации. При этом с увеличением «интеллектуальности» сети ужесточаются требования, предъявляемые к ее компонентам и в первую очередь к системам коммутации.

На сегодня, основной задачей, решаемой в процессе создания систем коммутации является разработка программного обеспечения. Как показано в ряде источников и как признают сами разработчики, этап создания алгоритмического и программного обеспечения является наиболее сложным и трудоемким, занимая до 90% ресурсов всего проекта/1, 2, 14, 19, 26, 28, 50, 52, 67/.

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

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

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

Описанию языков спецификаций, равно как и средств их поддержки посвящен ряд работ различных авторов /3, 4, 6, 8, 21, 38, 47, 75/.

Вместе с тем, вопросам математического описания алгоритмических процессов систем работающих в реальном режиме времени посвящено гораздо меньше исследований /5, 6, 16/. Что связано с рядом факторов, основными из которых являются:

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

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

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

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

Объектом исследования диссертационной работы является технология разработки программного обеспечения систем телекоммуникаций.

Предметом исследования являются математические методы описания алгоритмического обеспечения систем телекоммуникаций.

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

Состояние проблемы и задачи исследования. Технология разработки программного обеспечения больших систем, к которым относятся в частности системы коммутации, является объектом многочисленных исследований как отечественных И.В. Вельбицкий , Я.М. Бардзинь , В.В. Липаев ,А.А. Серебровский, В.А. Манохин, так и зарубежных О. Haugen, М. Hils, В. Boehm , А. Olsen, R. Braek специалистов. Основными направлениями исследования здесь является разработка инструментальных средств проектирования и методики их применения. Результат этих исследований отражены не только в публикациях, но и легли в основу создания ряда международных стандартов.

С другой стороны количество исследований в области математического определения алгоритмов также достаточно велико. Здесь можно выделить работы A.A. Маркова, А.И. Мальцева, Р. Петер, Р. Гудстайн, Н. Катленд, Э. Хамби. Однако большинство исследований в этой области носит теоретический характер.

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

В соответствии с указанной целью в работе поставлены и решены следующие задачи:

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

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

3. Описание, в соответствии с определенной ранее методикой основных алгоритмов работы системы коммутации.

4. Разработка правил организации вычислительного процесса по обслуживанию вызовов системой коммутации.

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

6. Разработка программных продуктов для систем телекоммуникаций в соответствии с определенными методами.

Научная новизна работы заключается в следующем:

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

2. Получена универсальная функция для функций описывающих работу конечных автоматов;

3. В результате исследования способов представления универсальной функции для конечных автоматов сделан вывод о целесообразности использования табличной формы представления (универсальной таблицы);

4. Разработана методика перехода от описания КА в виде 8ВЬ-диаграмм к его описанию в форме универсальной таблице;

5. Разработан алгоритм обработки универсальной таблицы.

Практическая ценность проведенных исследований заключается в следующем.

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

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

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

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

телекоммуникационных систем, о чем имеются соответствующие акты.

Апробация результатов работы. Результаты работы обсуждались и были одобрены на научно-технических конференциях профессорско-преподавательского состава Государственного университета телекоммуникаций. По результатам диссертации опубликовано 10 работ в открытой печати и специальных изданиях.

Личный вклад автора. Основные научные положения, теоретические выводы и рекомендации, содержащиеся в работе, получены автором самостоятельно.

Структура и объем работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы и 4 приложений.

Основные положения, выносимые на защиту:

1. Предложенная модель представления алгоритмического обеспечения систем коммутации.

2. Методика перехода от описания алгоритмического обеспечения систем коммутации в виде 8БЬ-диаграмм к его описанию в форме универсальной таблицы.

3. Функциональное описание алгоритмов работы узла коммутации с использованием класса вычислимых функций (МНР-операторов).

4. Разработанный алгоритм обработки универсальной таблицы.

5. Разработанный алгоритм обслуживания вызовов системой коммутации строящийся на основе алгоритма обработки универсальной таблицы.

6. Разработанный алгоритм организации вычислительного процесса тестирования систем сигнализации.

Глава 1. Методы разработки программного обеспечения систем, работающих в реальном режиме времени.

1.1 Технологические этапы разработки программного обеспечения

Создание программного обеспечения больших систем является трудоемким и сложным процессом. Для управления ходом разработки больших программных продуктов выделяют ряд этапов, составляющих цикл разработки программного обеспечения./9, 11, 19, 24, 26, 27/. В общем виде модель разделения технологической цепочки на этапы представлена на рисунке 1.1.

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

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

Рисунок 1.1 Основные этапы технологической цепочки разработки программного

обеспечения.

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

На этапе определения спецификаций, обычно объединяемым с этапом анализа требований, осуществляется точное описание функций, осуществляемых с помощью ЭВМ. Здесь задается структура входных и выходных данных или правила приведения уже имеющихся данных к новому формату. Отражение этих вопросов осуществляется в формальных спецификациях, которые представляют собой документ, отражающий предлагаемую реализацию системы с помощью вычислительных средств. Указанный документ является основополагающим в процесса последующей разработки. Чем подробнее составлены спецификации, тем меньше вероятность возникновения ошибок. В соответствии со спецификациями данные для тестирования должны предъявляться на ранних этапах разработки системы. Это способствует проведению объективного тестирования, поскольку на данные не может оказать влияние конкретная реализация системы. Так как функциональные спецификации описывают принятое решение в целом, данный документ можно использовать для начальных оценок временных затрат, числа специалистов и других ресурсов, необходимых для проведения работ.

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

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