Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод рельефов

 

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

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

В момент пуска сети формирование ее рельефа начинается с некоторого узла , где N - число УК на се­ти, являющегося инициатором. В этом случае говорят, что начинается построение а -рельефа.

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

При формировании рельефа из УК инициатора во всех исхо­дящих из него направлениях передается цифра 1. Эта единица на соседних с УК инициатором узлах заносится в матрицу по координатам (n, т 1), где п - номер УК инициатора, а m 1 - но­мер ветви, по которой поступила единица.

Для примера рассмотрим сеть, изображенную на рис. 6.3, а. Пусть в каждом УК отведена область памяти для формирова­ния матрицы R (рис. 6.3, б), и пусть узлом инициатором являет­ся . В этом случае цифра 1 будет занесена в матрицы и .

Далее процесс построения рельефа протекает следующим образом. Все УК, в которые поступила цифра 1, передают по всем исходящим направлениям, за исключением того направле­ния, по которому поступила 1, цифру 2. Эта цифра во всех УК, в которые она поступила, заносится в матрицу по координа­те (n, m 2), где т2 - номер ветви, по которой поступила цифра 2. Для рассматриваемого примера цифра 2 будет занесена в мат­рицы .

Теперь УК, на которые поступила цифра 2, передают по ис­ходящим направлениям цифру 3 и т. д. При этом должны со­блюдаться следующие правила:

1. Если в УК поступили одинаковые цифры с двух и более направлений, данный УК инициирует передачу цифры на единицу больше поступившей по всем без исключения исходящим на­правлениям. Например, в цифра 2 поступает с направлений, идущих от и . В этом случае цифра 3 с передается по всем исходящим направлениям.

 

Рис. 6.3

 

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

3. Инициация передачи цифр по всем направлениям на каж­дом УК происходит 1 раз после поступления первой цифры по порядку. Например, при передаче цифры 3 на с она заносится в матрицу по соответствующим координатам, а инициация передачи следующей по порядку цифры уже не происходит, так как ранее была осуществлена передача цифры 2.

Таким образом, для рассматриваемого примера будет сфор­мирован А -рельеф. Аналогичным образом строятся рельефы для всех остальных узлов сети. Считается, что рельеф сети сформи­рован, если построены все а -рельефы (а =1, 2,..., N).

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

Пусть требуется установить соединение от к (см. рис. 6.7, а). В этом случае на происходит обращение к строке матрицы рельефов со­ответствующей (см. рис. 6.3, б). Соединение устанавливается по вет­ви, которой соответствует минималь­ное число в этой строке. Для рассмат­риваемого примера это ветвь. На процесс поиска оптимального пу­ти повторяется. В данном случае бу­дет выбрана ветвь . Если в этой ветви нет свободных каналов, то вы­бирается ветвь, которой соответствует следующее по порядку число, т е. ветвь , и т. д.

 

Рис. 6.4

 

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

Пусть требуется установить со­единение от к . На вы­бирается ветвь . Теперь пусть в ветви нет ни одного свободного канала, тогда вызов согласно матри­це перенаправляется по ветви . Если в ветви тоже нет свободных каналов, то согласно матрице вы­зов должен быть направлен обратно на. Это первый тип «петли». При соответствующей ситуации данный вызов может «блуждать» в сети по такой петле: Следовательно, в этом случае вызов дважды попадает в. Это второй тип «петли».

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

Таким образом, соединения на сети должны, устанавливаться в соответствии со сформированными матрицами рельефов без образования «петель». Следует отметить, что, поскольку ситуация на сети непрерывно меняется (одни направления перегру­жаются, а нагрузка в других направлениях уменьшается; кроме того, могут выйти из строя каналы связи, возникнуть повреждения в отдельных направлениях связи и УК), появляется необходимость в коррекции рельефа сети. Рассмотрим процесс обме­на служебной информацией между управляющими устройствам (УУ) соседних узлов , и (рис. 6.4, а) при коррекции рельефа сети связи.

Пусть в хранится матрица рельефов , (см. рис. 6.4, б), и пусть поступил сигнал начала передачи служебной информа­ции о рельефах на соседние УК. Тогда УУ считает из ЗУ, в котором хранится матрица , элементы – первой строки и найдет минимальный из них.

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

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

 

Эти элементы образуют вектор

.

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

Если в ветви, например, отсутствуют каналы или она повреждена, то при вычислении элемента ,принимаем .

<== предыдущая лекция | следующая лекция ==>
Волновой метод | Игровой метод
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 1842; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.024 сек.