Содержание к диссертации
Введение
ГЛАВА 1. Анализ существующих подходов к отказоустойчивой маршрутизации 11
1.1. Структурная и функциональная организация матричного мультиконтроллера 11
1.2. Методы и алгоритмы отказоустойчивой маршрутизации 14
ГЛАВА 2. Построение оболочки самоорганизации 26
2.1. Среда самоорганизации мультиконтроллера с размещением резерва по периметру 3 26
2.1.1. Функции среды самоорганизации 26
2.1.2. Алгоритм репродуцирования программы поведения мультиконтроллера 39
2.2. Среда самоорганизации мультиконтроллера с гибким размещением столбца резервных элементов 44
2.2.1. Механизм самоорганизации мультиконтроллера 44
2.2.2. Клеточный алгоритм самоорганизации мультиконтроллера 45
2.2.3. Функциональная организация среды самоорганизации мультиконтроллера 50
ГЛАВА 3. Разработка коммуникационной среды самоорганизации обменных взаимодействий 53
3.1. Среда самоорганизации обменных взаимодействий при неизвестном начальном состоянии элементов микроконтроллерной среды 53
3.1.1. Модель конфигурированной среды с отказавшими элементами 53
3.1.2. Содержательное описание поиска при неизвестном начальном состоянии среды 55
3.1.3. Функции маршрутизатора коммуникационной среды 56
3.1.4. Параллельный алгоритм самоорганизации маршрута передачи сообщения в конфигурированной среде 62
3.1.5. Функциональная организация маршрутизатора 73
3.1.6. Пример самоорганизации маршрута при отказах 89
3.2. Среда самоорганизации обменных взаимодействий при известном начальном состоянии элементов микроконтроллерной сети 91
3.2.1. Содержательная характеристика метода поиска 91
3.2.2. Параллельный алгоритм самоорганизации маршрута в конфигурированной среде с отказавшими элементами 95
3.2.3. Пример поиска программного модуля в конфигурированной коммуникационной среде 99
3.3. Алгоритм маршрутизации с локальной информацией об отказах 101
ГЛАВА 4. Моделирование и исследование алгоритмов отказоустойчивой маршрутизации 105
4.1. Исследование маршрутизации при неизвестном начальном состоянии среды 105
4.2. Исследование маршрутизации при известном начальном состоянии среды 111
4.3. Сравнительная оценка характеристик маршрутизации 134
4.4. Выводы к главе 137
Заключение 138
Список использованных источников 139
- Методы и алгоритмы отказоустойчивой маршрутизации
- Среда самоорганизации мультиконтроллера с гибким размещением столбца резервных элементов
- Среда самоорганизации обменных взаимодействий при известном начальном состоянии элементов микроконтроллерной сети
- Исследование маршрутизации при известном начальном состоянии среды
Методы и алгоритмы отказоустойчивой маршрутизации
Отказы, возникающие в сети мультиконтроллера, могут препятствовать доставке сообщений, если сеть не обеспечивает отказоустойчивую маршрутизацию [23-25]. Известные способы обеспечения данной отказоустойчивости обычно основаны на выделении вокруг отказавшего элемента определённой области,включающей, в том числе, и работоспособные элементы, и последующем её обходе [26-28]. Один из таких подходов [29] требует наличия у каждого коммуникационного элемента МК информации об отказе или работоспособности собственных линков [30-33] (ограниченной отказовой информации). Отказ узла сети представляется как отказ всех его линков [34, 35]. Каждый линк формирует одну сторону квадрата или треугольника [36], другие стороны которого образуют обходной путь, если линк откажет. Для примера возьмём фрагмент гексагональной сетки [37], приведённый на рис. 1.5.
Если линк от узла 18 к узлу 0 откажет, сообщение может обойти отказавший линк, используя любой путь: 18-7-0 или 18-11-0. Это может происходить рекурсивно, т.е. если линк от узла 18 к узлу 7 тоже отказал, то обходом может быть 18-6-7-0.
Сообщение передаётся в одном из двух режимов: свободном, когда нет отказов, и режиме обхода, когда путь блокирован отказами. Маршрутизация осуществляется в каждом узле следующим образом:1) если сообщение передаётся в режиме обхода, и если узел ближе к месту назначения, чем узел, где оно вошло в режим обхода, то сообщение устанавливается в свободный режим;2) если сообщение передаётся в свободном режиме, то выбирается множество линков вдоль кратчайших путей к месту назначения;3) если сообщение передаётся в режиме обхода, то выбирается линк, непосредственно расположенный против часовой стрелки за линком, по которому сообщение поступило в узел;4) если все выбранные линки неисправны, осуществляется переход к шагу 5. Если сообщение находится в режиме обхода, вошло в режим обхода в этом узле, а позже покинуло этот узел по выбранному линку - сообщение зациклено и останов. В противном случае, сообщение передаётся по какому либо выбранному исправному линку;5) если все линки, выходящие из данного узла уже выбраны и проверены, то работа алгоритма останавливается. В противном случае выбирается линк, расположенный против часовой стрелки от множества ранее выбранных линков и осуществляется переход к шагу 4.
Длину пути маршрутизации можно значительно сократить, если учитывать форму отказовых областей [38, 39]. Обычно их подразделяют [40-43] на выпуклые и невыпуклые (рис. 1.6). Один из подходов [44], основанный на таком разделении, оперирует с отказовым статусом соседних линков и узлов.
Заголовок передаваемого пакета содержит 4 поля:- двухбитовый флаг направления (DF), который принимает следующиезначения:0 - пересечение по короткому пути вдоль X;1 - пересечение по длинному пути вдоль X;10 - пересечение по короткому пути вдоль Y;11 - пересечение по длинному пути вдоль Y.- двухбитовое поле RT определяет одну из 3 таблиц ремаршрутизации;- флаг PF - для предотвращения тупиковых ситуаций;- бит F показывает, что сообщение встретило хотя бы один отказ и будет ремаршрутизировано. сообщение идёт от узла X к узлу Y, то формат сообщения должен быть следующий:[D(x,y), (с,, с2, ..., с„), сообщение], где D(x,y) - расстояние по Хеммингу между узлами X и Y, (сь с2, ..., сп) - координатная последовательность различных битов адресов узлов.Процесс маршрутизации состоит в следующем:- текущий узел в текущей DRB-группе передаёт сообщение первичному и дополнительному узлам той же DRB-группы;- если первичный узел способен передать сообщение дальше, то он становится текущим узлом следующей DRB-группы;- если передача первичным узлом невозможна, то текущим узлом становится дополнительный узел DRB-группы;- процесс повторяется до тех пор, пока сообщение не достигнет адресата. Недостатком данного метода является то, что в случае отказа первичного и дополнительного узлов текущей DRB-группы процесс маршрутизации прекращается.
Другой вариант двухфазной маршрутизации (т.е. маршрутизации, использующей обратную трассировку), использует дополнительные виртуальные каналы [46-48], встроенные в каждом направлении над физическими каналами [49]. Отказы здесь подразделяются на 2 вида: отказ всего процессорного элемента с маршрутизатором или потеря физической связи [50]. Также как и в случае с DRB-группами, в процессе маршрутизации рассматривается определённый сегмент матрицы мультиконтроллера. Фактически, на каждом шаге продвижения алгоритм отслеживает состояние близлежащих узлов и линков, формулируя наиболее предпочтительное направление передачи сообщения, основываясь на установленных приоритетах и сложившейся отказовой ситуации.
Преимуществом вышеописанных методов является то, что они не требуют проведения предварительного сбора информации об отказовой ситуации в сети. Однако при наличии большого числа отказов начинаются значительные потери времени, вызванные резким удлинением пути маршрутизации. Сокращения дан 21ного пути можно добиться, предварительной настройкой коммуникационного слоя мультиконтроллера, т.е. записью в его память частичной или полной информации об отказовой ситуации в сети [51, 52]. Одним из таких подходов является концепция расширенных уровней предосторожности [53]. Отказовая информация собирается специальным целочисленным или бинарным вектором, связанным с каждой вершиной. Вектор - 4-х элементный: (Е, S, W, N), где Е обозначает расстояние от этого узла к ближайшему отказовому блоку на «востоке» от него. Аналогичным образом заданы и элементы S, W и N. Символ «-» используется, если в соответствующем направлении нет отказа. Узел с вектором (-, -, -, -) называется безопасным.
Если принять за узел источника (i j"), а за узел назначения - (ij), то условие существования минимального пути будет выглядеть следующим образом:
Среда самоорганизации мультиконтроллера с гибким размещением столбца резервных элементов
В качестве слоя самоорганизации однородной среды процессорных элементов примем матрицу из пхт элементов. Каждая ячейка слоя самоорганизации настраивает соответствующий ей процессорный элемент (ПЭ) с ФА (ij) на один из алгоритмов функционирования: собственный (ij), верхний (/+1,/), нижний (/-\j), правый (/,/+1), левый (ij-\) в зависимости от отказов или изменения алгоритмов функционирования верхнего (i+lj)-ro, нижнего (i-lj)-ro, правого (ij+\)-ro и левого (y-l)-ro ПЭ.
Алгоритм функционирования (i j ), на который настроена (ij)-n ячейка будем называть ВА (ij)-u ячейки. Первоначально (при отсутствии отказов) все ПЭ, за исключением резервных, имеют ВА равный ФА. Резервными являются ПЭ ]т/2[-го столбца (где ][ - операция округления до большего целого), которые первоначально имеют ВА=(0,0), т.е. не выполняют никакого алгоритма функционирования.
При возникновении отказов ПЭ множество взаимодействующих ячеек слоя самоорганизации перенастраивает работоспособные ПЭ (в том числе и резервные) на новые ВА. Взаимодействие ячеек осуществляется сигналамиX J = {xu,X\2,x{3,xl4}, X l = {х21,х22,х23,х24} потенциальных и реальных перемещений, поступающими от (ij)-u. ячейки однородной среды физическим соседям. Сигналы потенциальных перемещений от (ij)-vi ячейки информируют соседние ячейки о возможности перенастройки (ij)-ro ПЭ на один из соответствующих алгоритмов функционирования. Сигнал реального перемещения от (ij)-R ячейки информирует одну из соседних ячеек о её перенастройке на (ij)-ii алгоритм.
При отсутствии отказов выработка сигналов потенциальных перемещений инициируется резервными элементами по всем направлениям. Остальные элемен ты вырабатывают сигналы потенциальных перемещений во всех направлениях при поступлении хотя бы с одного направления.
При возникновении отказов ПЭ выработка сигналов потенциальных перемещений от них прекращается. Каждый отказавший ПЭ инициирует сигнал реального перемещения в одном из 4-х направлений [76, 77], начиная с приоритетного. Работоспособные ПЭ инициируют сигнал реального перемещения только при поступлении такого сигнала от соседей. Резервные элементы не инициируют сигналы реальных перемещений.
При поступлении в один ПЭ двух и более сигналов реальных перемещений возникает конфликтная ситуация, т.к. каждый ПЭ может выполнять только один алгоритм функционирования. Конфликтная ситуация разрешается путём блокирования выдачи сигналов потенциальных перемещений по направлению прихода менее приоритетных сигналов реальных перемещений. При этом ПЭ, вырабатывающие эти сигналы реальных перемещений, вырабатывают их и в других направлениях. Приоритет направлений для ПЭ, расположенного слева от резервного элемента: вправо, вверх, вниз, влево. Для ПЭ, расположенного справа: влево, вверх, вниз, вправо.- формирование достижимостиконфликтная ситуация: приоритет при перераспределении отдаётся отказавшим элементам, расположенным в левой части матрицы. Т.е., если на входы 5 и 8 ячейки одновременно поступают единичные сигналы, тона выходе сигнал х4у+ принимает значение логической единицы, a xj/ - логического нуля. Таким образом, ячейка отказавшего элемента, расположенного слева, получит единичный сигнал потенциального перемещения, разрешающий перераспределение вправо.1. Предложены графовые модели среды мультиконтроллера, обеспечивающие её самоорганизацию и маршрутизацию в ней сообщений.2. Сформулирован клеточный алгоритм репродуцирования программы поведения мультиконтроллера с размещением резервных элементов по периметру, позволяющий строить маршруты восстановления из отказавших узлов матрицы с помощью виртуальной ретрансляции их программных модулей.3. Разработан клеточный алгоритм самоорганизации мультиконтроллера с гибким размещением столбца резервных элементов, основанный на взаимодействии ячеек среды при помощи сигналов потенциальных и реальных перемещений.4. Представлена функциональная организация ячейки мультиконтроллера с гибким размещением столбца резервных элементов
Распределённая система представляет собой матрицу из пхт модулей, причём п-я строка и т-й столбец являются резервными. Каждый модуль (ij) (где/ = 1,« - номер строки, j = \,т - номер столбца матрицы, содержащих модуль) может выполнять как собственный алгоритм функционирования, так и алгоритм функционирования трёх соседних модулей - верхнего (i-lj)-ro, левого (/j/-l)-ro, и левого по диагонали (/-1,/-1 )-го, в случае их отказов или изменения алгоритмов функционирования. Местоположение модуля (ij) в матрице определятся его ФА. Наряду с ФА для идентификации модулей системы используется так называемый логический адрес (ЛА). Модуль (ij) имеет ЛА (fj ), если он реализует алгоритм модуля с ФА (/ г/ )- При отсутствии отказов резервные модули не задействованы (они не имеют собственных алгоритмов функционирования), ФА и ЛА всех модулей совпадают. При возникновении отказов отдельных модулей распределенная система перестраивается [78].
Аппаратурная перестройка системы заключается в отключении отказавших модулей путем перекоммутации [79-82] их информационных входов и выходов. При этом нижний информационный вход отказавшего модуля коммутируется с его правым информационным выходом, левый информационный вход коммутируется с нижним информационным выходом, верхний информационный вход коммутируется с левым информационным выходом и правый информационный вход коммутируется с верхним информационным выходом (рис. 3.1).
Программная перестройка системы осуществляется путем изменения алгоритмов функционирования модулей по следующим правилам:
Среда самоорганизации обменных взаимодействий при известном начальном состоянии элементов микроконтроллерной сети
Каждый микроконтроллер помимо ФА, состоящего из вертикальной и горизонтальной составляющих, имеет и логический адрес - адрес того программного модуля, который в данный момент выполняется в этом микроконтроллере. Очевидно, что в отличии от физического адреса, логический адрес микроконтроллера может меняться.
Передача сообщения осуществляется между программными модулями, поэтому при передаче необходимо адресоваться не по физическому адресу, а по логическому. Исходной информацией для выбора направления передачи служит физический адрес. Т.е. первоначально сообщение передаётся по физическому адресу и, если в данном микроконтроллере не обнаружено соответствующего логического адреса, то сообщение начинает перемещаться по всем элементам данного столбца, а потом (если потребуется) и по элементам соседнего столбца.
Процесс маршрутизации начинается после реконфигурации матрицы и состоит из двух этапов:- перемещение сообщения от одного МК к другому МК.
Этап сбора информации о положении отказов в системе [89, 90] делится на два шага:1) в каждом МК формируется сообщение с полем данных, в разрядах которого записаны нули. Данное сообщение посылается вправо по строке самому себе. Каждый работоспособный МК выставляет единицу в поле данных в соответствующем ему разряде и посылает сообщение далее. Таким образом, за счёт транзитной передачи сообщения [91, 92] через отказавшие элементы в соответствующих им разрядах остаются нули. По достижению сообщением исходного узла поле данных переписывается в регистр достижимости МК (рис. 3.23); 2) на втором шаге в каждом работоспособном МК формируется сообщение, в поле данных которого записывается регистр достижимости данного МК. После этого сообщение посылается по столбцу вниз. На каждом шаге передачи вычисляется дизъюнкция содержимого поля данных сообщения и регистра достижимости текущего элемента (результат дизъюнкции записывается в поле данных сообщения). По достижению источника поле данных сообщения инвертируется, после чего вычисляется дизъюнкция поля данных сообщения и регистра достижимости источника. Результат записывается в регистр достижимости источника (рис. 3.24).
Второй шаг сбора информации о положении отказов необходим для предотвращения ситуации, когда в одном столбце откажут все элементы. В этом случае в соответствующем разряде регистра достижимости будет записана единица и при передаче сообщения произойдёт его переход в следующий столбец (рис. 3.25).
Просмотр двух соседних столбцов возможен двумя способами:- сообщение «пробегает» по всем элементам одного столбца, а затем, если требуется, делает шаг вправо на соседний столбец и просматривает его элементы; - изначально в источнике формируется два сообщения (одно для первого столбца, другое для соседнего), которые двигаются к соответствующим столбцам и просматривают их элементы.
Использование первого способа нецелесообразно в большем ряде случаев. Связано это с тем, что не всегда сообщение может перейти в соседний столбец.Рдссмотрим возможные случаи отказов двух рядом стоящих элементов. Из приведённых на рис. 3.26 случаев, только в первом возможен переход в соседний столбец. Во втором случае переход невозможен, т.к. произошёл отказ в элементе первого столбца. В третьем случае сообщение проскочит нужный столбец. Четвёртый случай совмещает третий и второй.
Указанных недостатков лишён способ, когда формируются и передаются два сообщения. При этом нет необходимости делать шаг вправо на соседний столбец - для этого предназначено своё сообщение. Очевидно, что в данном случае необходимо предусмотреть возможность уничтожения сообщения просмотревшего все элементы столбца, но не нашедшего адресата.
Алгоритм самоорганизации маршрута опишем СПП. Стоит отметить, что СПП предназначена для обработки больших наборов данных, которые организованы в виде -мерных решёток. Она действует над клеточным пространством,имеющим вид декартовой решётки, в каждом узле которой расположена клетка (клеточный автомат), обладающая именем в виде набора координат узла и состоянием. Связи каждой клетки с другими определяются алгоритмом обработки данных. Набор исходных данных соответствует совокупности начальных состояний клеток. Система параллельных подстановок действует в итеративном режиме. Каждая итерация (выполнение набора применимых подстановок) вырабатывает промежуточный набор данных. Заключительное состояние совокупности клеток (в этом состоянии ни одна подстановка не применима) соответствует результату
Исследование маршрутизации при известном начальном состоянии среды
Исследуем алгоритм маршрутизации с известным начальным состоянием среды на тех же отказовых ситуациях, что и представленные в разделе 4.1. Необходимо отметить, что процесс передачи сообщений в «кольце» осуществляется попути за счёт проскока через отказавший модуль:При этом в нижней части экрана программы можно наблюдать состояние регистров достижимости элементов любой строки (в данном случае -- второй). Программная модель позволяет вручную задавать направление смещения приёмника - вправо, вниз или по диагонали.
Также по минимальному пути осуществляется маршрутизация и в случае с расположением приёмника правее и ниже относительно источника со смещением источника и приёмника вправо (рис. 4.23-4.29). Сообщение сначала достигает нужного столбца, затем передаётся вниз по вертикали, и, в конце концов, входит в «
Количество посылаемых сообщений может быть как одно, так и два (ву -ый иу+1-ый столбцы). Если посылается 2 сообщения, то одно из них достигает адресата, а другое уничтожается (рис. 4.30-4.35). При этом:
В случае если сообщение не может напрямую попасть в искомый столбец (рис. 4.36-4.41), то оно передаётся вниз по столбцу до тех пор, пока в соответствующем бите регистра достижимости текущего модуля не встретится «единица». Это означает, что в данной строке матрицы есть «вход» в искомый столбец.
С помощью разработанных программных моделей были проведены исследования различных алгоритмов маршрутизации на одинаковых отказовых ситуациях. На рис. 4.42 представлены графики зависимостей вероятности достижения сообщением модуля-приёмника от числа отказов в сети. Здесь: 1 - маршрутизация для невыпуклых областей; 2 - маршрутизация с использованием расширенных уровней предосторожностей (от узла назначения к источнику); 3 - маршрутизация с использованием расширенных уровней предосторожностей (смешанный подход); 4 - двухфазная маршрутизация; 5 - маршрутизация при неизвестном начальном состоянии среды (раздел 4.1) 6 - маршрутизация с использованием регистра достижимости (раздел 4.2). - маршрутизация с использованием регистра достижимости; 2 - маршрутизация при неизвестном начальном состоянии среды. Данный показатель характеризует то, насколько маршрут передачи сообщения в присутствии отказов близок по длине к маршруту в безотказовой ситуации, т.е. во сколько раз он отличается от минимального. Как видно из графиков, метод маршрутизации с известным начальным состоянием среды (с использованием регистров достижимости) осуществляет передачу сообщения практически по минимальному пути даже при большом количестве отказов. 1. Разработаны программные модели для реализации алгоритмов машрути-зации с известным и неизвестным начальными состояниями мультимик-роконтроллерной среды. 2. Проведены исследования работы разработанных программных моделей при: - различных формах отказовых ситуаций: - различном расположении источника и приёмника относительно друг друга; - различном количестве отказов; - различных вариантах смещения источника и приёмника при реконфигурации после отказа. 3. Получены и приведены результаты исследований наиболее современных из известных алгоритмов маршрутизации на аналогичных отказовых ситуациях. 4. Предложены показатели длины и эффективности маршрутизации, позволяющие дать точную сравнительную оценку вышеперечисленным параметрам обмена сообщениями в сети микроконтроллеров. 5. Показаны существенные преимущества разработанных методов маршрутизации по сравнению другими известными алгоритмами. В диссертационной работе решена научно-техническая задача разработки высокоэффективных аппаратных и алгоритмических средств отказоустойчивой самоорганизации обменных взаимодействий в мультиконтроллере. При решении задачи в диссертационной работе получены следующие результаты: 1. Разработан подход к поиску абонента в мультиконтроллере по его логическому адресу, учитывающий метод самоорганизации. 2. Получены локальные правила маршрутизации в сети с отказавшими элементами, позволяющими передавать сообщение между абонентами, изменяющими свои позиции в мультиконтроллере при восстановлении логической структуры. 3. Созданы клеточные алгоритмы маршрутизации, реализующие композиции правил обхода отказавших ячеек, выбора направлений передачи сообщения, поиска в допустимой области, сбора минимальной глобальной информации и ассоциативного поиска допустимой области расположения абонента. 4. Синтезирована структурно-функциональная организация клеточной отказоустойчивой среды маршрутизации мультиконтроллера. 5. Разработана структурно-функциональная организация клеточной среды восстановления логической структуры отказоустойчивого мультиконтроллера. с гибким размещением области резервных элементов. 6. Проведены исследования и выполнен сравнительный анализ разработанных алгоритмов маршрутизации, показавший высокую эффективность полученных решений.
Похожие диссертации на Клеточные алгоритмы и среды отказоустойчивой маршрутизации самоорганизующегося мультиконтроллера
