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

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

двумя заданными точками (входом и выходом) коммутационного поля (поиск «точ­ка-точка»);

точкой и группой точек коммутационной системы (поиск «точка-группа»);

двумя группами точек (поиск «группа-группа»);

группой и одной точкой (поиск «группа-точка»).

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

- линейное искание, т.е. поиск определенной линии в соответствии с принятой адресной
информацией (например, по номерам двух абонентских комплектов);

-свободное искание, т.е. выбор промежуточных линий к любому свободному и доступ­ному выходу (например, к любому приемнику набора номера);

групповое искание, при котором на первом этапе происходит выбор группы выходов, а на втором отыскивается любой свободный выход в этой группе (например, при исходя­щей связи, когда поиск проводится в одном из нескольких направлений соединения).

Рис. 16 Структурная схема алгоритма поиска путей

Во всех системах с программным управлением рассматриваемый алгоритм осуществля­ет действия по поиску одной из всех свободных и доступных линий между двумя заданны­ми точками. Такой способ называется обусловленным исканием «от конца к концу».

В заявке на работу алгоритма поиска промежуточных линий (рис. 16) задаются сле­дующие параметры: данные адреса первой точки (или группы точек); тип поиска и мар­шрут. Необходимый тип поиска может быть выбран из перечня, приведенного выше.

Выбор маршрута необходим в том случае, когда поиск ведется в пределах различных блоков. Например, между двумя точками блоков абонентских линий (БАЛ) при местной связи или между точкой и группой точек в блоке соединительных линий (БСЛ) при транзитной связи и т.д. Маршрут указывает на комбинации такого поиска (БАЛ-БАЛ, БАЛ-БСЛ и т.д.). Результат поиска путей содержит координаты промежуточных линий (информация о заданных конечных точках переносится из входной заявки), признак «путь найден», а при занятости — «путь не найден». Кроме этих двух наиболее часто встречаю­щихся признаков возможно занесение таких признаков как «путь найден с учетом катего­рии». Например, в сотовых сетях в случае приоритетной связи при полуавтоматическом соединении от АМТС.

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

Кроме того, современные цифровые коммутаторы могут изменять соотношения между входами и выходами, и поиск может проводиться через различное число звеньев. Поэтому при формировании команд увеличивается количество признаков типа поиска (например, до 16), а результат поиска формируется и передается в процессор самим коммутационным полем. Но от этого логическое содержание процесса не меняется, несмотря на незначитель­ное различие процессов эксплуатации.

Для настройки модуля, реализующего поиск путей, необходимы следующие данные:

число линий между звеньями коммутационной системы;

число направлений соединения и число линий в них;

таблица (или граф) связей в соответствии с группообразованием;

размерность и число коммутаторов (соединителей) по каждому звену.

Для поиска промежуточных линий организуются массивы памяти, отражающие различ­ные элементы коммутационной системы. Как уже указывалось, массивы памяти тесно свя­заны с оборудованием, состояние которого они отображают. При этом значению 0 обычно приписывается состояние линии «занято», а 1 — «свободно». На рис. 2.84 изображен мас­сив, отражающий состояние выходов матричных соединителей звеньев А (для выходов зве­на В и выходов D структура массива одна и та же).

Рис. 17 массив состояния выходов матричных соединителей

Выходы коммутационной системы должны отражать состояние соединительных линий к другим станциям и обеспечивать возможность перераспределения этих линий в различ­ных направлениях. На рис. 18, а изображен один из способов организации памяти направ­лений. Согласно этому способу, в каждое из 16-разрядных слов можно записать данные о состоянии восьми линий. У каждой линии могут быть четыре состояния «свободно/заня­то» и «заблокировано/разблокировано». В массиве памяти для отображения этих состояний для каждой линии отведено два двоичных разряда.

Рис. 18 Способ организации памяти направлений:

В каждое 16-ти битовое слово можно записать данные о состоянии восьми линий:

с – свободен; з – занят; б – блокирован; р – разблокирован.

Все слова, отражающие состояния линий одного направления, компонуются в один из подмассивов. Для всех подмассивов направления организуется массив базовых адресов (рис. 18, б), где указывается начало и конец подмассива каждого направления, включая та­кие устройства станции, как приемники набора, частотные приемопередатчики и т.п. Каж­дому номеру канала в направлении ставится в соответствие номер, записанный в массиве позиционных адресов (блока, матрицы, выхода звена D).

Рис. 19 Алгоритм поиска промежуточных линий (общая часть)

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

В первую очередь анализируется заявка и определяется тип поиска (операторы 3-5). Если в типе указана группа точек (оператор 4), то из них выбирается одна (оператор 6), и искание проводится между двумя точками.

В дальнейшем проводится поиск линий между двумя точками. Если линия не будет най­дена (оператор 10), то проверяется тип поиска (оператор 13). Если поиск групповой, то ана­лизируется, можно ли осуществить еще одну попытку поиска с другой точкой в группе. Это возможно, если число попыток не превысило максимально заданное (оператор 14). Если ли­нии найдены, то по результату поиска уточняется состояние промежуточных линий, коррек­тируется и формируется результат в виде координат промежуточного пути (операторы 11 и 12). Во всех случаях на выходе алгоритма формируется признак (оператор 12), имеющий значение «путь найден» или «путь не найден».

Принцип обусловленного искания заключается в последовательном определении общей свободности участков путей по графу доступности (рис. 20, б), с помощью которого изо­бражаются все доступные пути между двумя точками. Граф называется последовательно-параллельным, если любые его два участка включены либо последовательно, либо парал­лельно. Четырехзвенная схема группообразования без расширения и сжатия показана на рис. 20, а. Она содержит звенья, обозначенные буквами А, В, С, D, каждое из которых образовано с помощью восьми коммутаторов. Каждый коммутатор имеет восемь входов и восемь выходов. Кружки на рис. 20, б соответствуют соединителям звеньев А, В, С, D, а дуги — промежуточным линиям между ними. На каждой дуге указано состояние линии (О — занято, 1 — свободно). В рассматриваемом графе для примера показано, что соедине­ние от абонента 0 из звена А может пройти по 8 соединительным линиям звена В (в примере счет линий начинается от 0, и п1 = 7); далее п2 путями последующего звена ведет только од­на линия (в примере n1 = п2 = 7) к соединителям звена С и т.д. Этот граф называется односвязным, так как от каждого соединителя предыдущего звена к определенному соедините­лю последнего звена ведет только одна линия.

Рис. 20 Четырехзвенная схема группообразования и соответствующий ей граф

Задача сводится к нахождению путей в графе между двумя точками, отмеченными толь­ко единицей (свободными по всем звеньям). Процедура поиска реализуется путем логиче­ского перемножения слов в памяти, отражающих состояние линий, образующих один путь от точки до точки. Поскольку в некоторых звеньях один выход ведет к нескольким входам последующего звена, а его состояние кодируется одним битом, то это состояние обычно «размножается», т.е. образуется новое слово, где каждый бит повторяется столько раз под­ряд, сколько имеется линий, доступной данной, в последующем звене. Так, на рис. 20 од­ной из свободных промежуточных линий звена А доступны восемь линий звена В. Поэтому ее состояние (равное 1) представляется в виде восьмиразрядного слова 11111111 (размно­жение), а совместная свободность пути от входа звена А к выходу звена В определяется как логическое произведение этого слова на слово состояний выходов звена В.

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

На рис. 2.88 показан пример алгоритма поиска промежуточных путей. В алгоритме по­сле запуска его центральной программой оператор 2 позволяет определить состояния выхо­дов, доступных данному абонентскому комплекту (выходы матричного соединителя звена А). Оператор 3 проводит «размножение» этой информации: МАB: = 8OSAB (О — оператор раз­множения). После этого определяются свободность и доступность промежуточного пути по любой линии между звеньями А и В к любому выходу звена В (оператор 4).

Дальнейшие действия (операторы 5 и 6) повторяют предыдущую процедуру, но только со стороны звена D. По номеру комплекта (он либо задан в заявке, либо предварительно выбран из группы — направления) определяется номер байта состояний (SCD) в массиве (МCD). Затем состояния этого байта логически «размножаются» (оператор 6), формируя массив (Mj). Далее вычисляется массив результата Мрез (оператор 7), с помощью которого определяются свобод­ные и доступные с двух сторон линии между двумя выходами звена В и входами звена С, на­пример, со стороны абонентского комплекта и выхода со станции. После этого массив анализи­руется и из него выбирается одна из таких линий. Любая из выбираемых линий характеризует­ся наличием 1 в результирующем массиве. (На рис. 21 выбирается первая левая единица.)

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

О- оператор размножения

В простейшем случае процесс выбора — это поиск первой левой единицы (оператор 8). Часто применяют более сложный выбор. Одним из таких случаев является выбор по счетчи­ку, который указывает начало поиска. В этом случае поиск начинается с единицы, номер которой указывает начало поиска и ведется по циклу.

Оператор 9 формирует один из признаков «путь найден» или «путь не найден» (Mрез = 0). В первом случае производится расшифровка результирующего слова для формирования координат найденного промежуточного пути. Для этого по местоположению найденной единицы определяются номера соединителей и их входов в каждой матрице каждого звена (оператор 10). На рис. 21показан поиск между двумя комплектами (местная связь), поэто­му процесс повторяют для второй части пути до абонента В (операторы 12-13). Если вторая половина пути просмотрена, то алгоритм закончен. Если поиск групповой, то при отсутст­вии путей меняют оконечный комплект и поиск повторяют. Еще раз следует напомнить, что здесь рассмотрен только простейший алгоритм. В реальных станциях в настоящее время применяются пространственно-временные коммутаторы, в которых выход представляет со­бой групповые тракты по 32 и более каналов. Тогда ребра графа превращаются в пучки ли­ний, и поиск несколько усложняется. Все станции без исключения применяют обходные на­правления, что требует повторов поиска в другом направлении.

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