АЛГОРИТМ АДМИНИСТРИРОВАНИЯ ДЛЯ СЕТЕЙ РЕАЛЬНОГО ВРЕМЕНИ НА БАЗЕ SPACEFIBRE С ВИЗАНТИЙСКИМИ ОТКАЗАМИ

АННОТАЦИЯ

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

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

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

ABSTRACT

In modern real-time local area networks, a logically and physically distributed management scheme is used to ensure the fault mitigation, to ensure the required response time to events, and the possibility of scaling the network, in which several management nodes are used in the network.

Errors that occur in the nodes of such a network may relate to the so-called Byzantine ones. Moreover, such errors can occur in the absence of intentional influences. Currently, there are several different algorithms for Byzantine errors mitigation in distributed computing systems. But their implementation is either associated with high overhead, or does not allow for deterministic execution time. These algorithms also do not provide for the possibility of mitigation different numbers of errors for different types of nodes, for different types of events. This entails unnecessary overhead costs. This article proposes a protocol for real-time networks based on the SpaceFibre standard, in different parts of which it is required to mitigate a different number of faults. It allows us to transfer via the network less service information than for algorithms that provide deterministic execution time and use less memory to store transaction queues.

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

Keywords: SpaceFibre; dynamic reconfiguration; real-time networks; management in local area networks; fault mitigation; Byzantine faults.

Введение

Многие терминальные и сетевые узлы современных локальных вычислительных сетей реального времени являются довольно сложными (комплексными) устройствами. Вследствие этого в ходе их функционирования могут происходить сбои и отказы, приводящие не только к невыполнению этими узлами требуемых функций, но и к их не правильному выполнению. Во втором случае результаты получаются в пределах допустимого времени, определить их некорректность с использованием простых алгоритмов зачастую не представляется возможным. Аналогичные ошибки могут происходить и, напротив в «примитивных» узлах, в которых необходимость экономии приводит к невозможности использования различных механизмов защиты. Такого рода ошибки относятся к Византийским ошибкам, хотя и не являются по своей природе следствием преднамеренных воздействий [1, 2, 3, 4, 5]. Наличие этих ошибок необходимо учитывать при выполнении администрирования сетей. Особенно критичными становятся такие ошибки для больших вычислительных сетей [1, 3, 4]. Для управления такими сетями, как правило, используется несколько системных администраторов, что позволяет обеспечивать устойчивость к сбоям и отказам, требуемое время реакции на события в сети и возможности по масштабированию сети [6, 7, 8, 9]. Вследствие Византийских ошибок администраторы могут по-разному видеть состояние сети, и, вследствие этого, принимать разные (противоречивые) решения даже в тех случаях, когда все они функционируют корректно [1, 4, 5, 10].

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

Реализация механизмов парирования Византийских ошибок требует существенно больших накладных расходов, чем реализация парирования не Византийских ошибок. Во многих алгоритмах требуется чтобы соотношение количества корректно функционирующих узлов к количеству узлов с ошибками было больше, чем в отсутствии Византийских ошибок. Требуется обмен большим количеством сообщений между узлами. Количество этапов обмена, после которых вычисляются промежуточные решения, может быстро возрастать с увеличением количества ошибок, которые необходимо парировать.  Сообщения содержат дополнительную информацию, что увеличивает их длину. Соответственно, увеличивается нагрузка на сеть и время реакции на события в сети [1, 3, 4, 5].

Эти параметры являются существенными и для задач обеспечения доступа к распределенным ресурсам и для задач администрирования. В настоящее время существует несколько алгоритмов и протоколов, обеспечивающих парирование Византийских ошибок. Но, в них для сокращения количества сообщений и времени выполнения используются различные особенности (специфика) классов систем, для которых они разработаны. Это делает их не применимыми для задачи администрирования сетей реального времени на базе стандарта SpaceFibre. Далее в статье приводятся требования к алгоритму администрирования сети реального времени на базе стандарта SpaceFibre в сети с Византийскими ошибками, существующие алгоритмы доступа к распределённым ресурсам в сетях с Византийскими ошибками, показываются причины, из-за которых они не применимы для рассматриваемого класса сетей, предлагается алгоритм администрирования, удовлетворяющий существующим требованиям.

Византийские ошибки, не являющиеся следствиями преднамеренных вредоносных воздействий, в сети SpaceFibre

Исходно понятие Византийских ошибок связывалось с преднамеренными вредоносными воздействиями на сеть. Например, это могло быть использование вредоносного программного обеспечения (ПО) на некоторых терминальных, сетевых узлах. Функциональность такого ПО исходно была направлена на приведение сети в некорректное, недопустимое состояние. Это достигалось, например, за счет перегрузок сети трафиком, внешне имеющим признаки корректного, предоставлением не корректной информации, о текущем состоянии узлов [1, 3]. Долгое время считалось, что сбои и отказы в аппаратной части и непреднамеренные ошибки, допускаемые при разработке ПО могут приводить только к ошибкам, связанным с потерей функциональности (crash-stop failure model) [11]. Например, узел может перестать отвечать на запросы или выдавать на выходы информацию с некорректной структурой.

В настоящее время из-за роста сложности (комплексности) терминальных узлов сбои и отказы довольно часто являются причиной Византийских ошибок [1, 11]. Второй причиной Византийских ошибок являются производственные дефекты в простых, дешевых терминальных узлах. В тех случаях, когда для терминальных узлов (например, датчиков) надо снизить стоимость изготовления, время изготовления, площадь (размеры), это может достигаться за счет использования более дешевых технологий, исключения механизмов парирования ошибок [1, 11]. Далее в данной статье мы будем рассматривать Византийские ошибки только такого типа (Византийские ошибки, не являющиеся следствием преднамеренных вредоносных воздействий.) Такие Византийские ошибки могут являться проявлением отказов типа «константный 0», «константная 1», а также ошибок вызванных взаимовлиянием сигналов (victim - aggressor) и «запаздывания», происходящего, например, вследствие перегрева отдельных областей СБИС в ходе работы.

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

В тех случаях, когда кодирование используется, оно не обеспечивает 100% гарантии отсутствия ошибок, поскольку они могут быть внесены в процессе выполнения кодирования, декодирования. Для борьбы с такого рода ошибками может использоваться пространственное резервирование, например, мажоритарные схемы. Но, их реализация связана с очень большими накладными расходами, и они также не обеспечивают полного исключения ошибок [1, 3, 4].

Византийские ошибки, возникающие на управляющих сигналах, могут приводить, например, к тому, что корректный объект данных будет отправляться в сеть не один, а несколько раз (постоянно). Для парирования таких ошибок могут использоваться мажоритарные схемы, но как было отмечено выше, они не обеспечивают 100% результата [1, 3, 4].

Поэтому во многих случаях, когда вероятность таких ошибок в исходной схеме не велика, а допустимые накладные расходы ограничены, предпочтительным оказывается парирование Византийских ошибок на системном уровне [1, 2, 3, 5].

Применительно к передаче через транзитные сетевые узлы (маршрутизаторы SpaceFibre) в общем случае пакет транспортного уровня не изменяется – если что-то было искажено при передаче через транзитный маршрутизатор, то это будет выявлено принимающим терминальным узлом за счет ошибки контрольной суммы (CRC), ошибки уровня структуры пакета транспортного уровня или аварийного конца пакета (EEP). В стандарте SpaceFibre существуют механизмы, позволяющие исключить перегрузку сети (монополизацию использования ресурсов сети) одним из потоков данных [12]. Они позволяют парировать Византийские ошибки, приводящие к перегрузке сети передачей множества копий корректного объекта данных. Таким образом, при транзитной передаче по сети SpaceFibe необходимо парирование только не Византийских ошибок, источниками Византийских ошибок могут становиться только терминальные узлы.

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

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

В соответствии с этим алгоритм должен обладать следующими характеристиками:

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

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

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

В основе алгоритмов и протоколов, обеспечивающих доступ к распределённым сетевым ресурсам в системах Византийскими ошибками лежит группа моделей, связанных с достижением Византийского соглашения, консенсуса, интерактивной согласованности (interactive consistency) [1, 3, 4, 5]. Под задачей достижения консенсуса обычно понимается задача, в которой должно быть принято решение об одном значении. В отличие от задачи Византийского соглашения в данном случае нет лидера, единственного, имеющего исходное значение – все решающие узлы имеют некоторое исходное значение. (В ряде источников задача Византийского соглашения называется задачей консенсуса с одном лидером.) Задача достижения интерактивной согласованности – задача, в которой принимается решение о некотором векторе значений, в котором каждому решающему узлу соответствует один элемент [1, 3].

Задача достижения Византийского соглашения, консенсуса, интерактивной согласованности считается решенной, если выполняются следующие условия [1, 3]:

- все корректно функционирующие узлы договорились до одинакового решения или вектора решений (причем не определено понятие правильное/не правильное это решение, важно, что оно одно и то же);

- в случае наличия лидера если лидер функционирует корректно, то должно быть принято решение, исходно предложенное лидером;

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

- процесс решения является не бесконечным.

Исходно для решения так называемой задачи византийских генералов был разработан oral message algortm (OM) [13]. При выполнении этого алгоритма один из узлов является лидером. Он рассылает остальным узлам некоторое значение (например, true или false), по поводу которого необходимо принять общее решение. Далее, каждый из узлов, получивших значение, посылает его всем остальным узлам (те, в свою очередь делают тоже самое). Если узел функционирует корректно, то он рассылает то значение, которое получил. Если узел функционирует не корректно, то он может разослать части узлов то значение, которое получил, а другой части узлов – некоторое другое значение. Лидер также может функционировать не корректно. Он может исходно разослать разным узлам различные значения. В итоге должно быть принято значение, которое было разослано большему количеству узлов. При выполнении этого алгоритма нет понятия правильного/не правильного решения. Некоторое (потенциально любое из исходно имеющихся решений) должно быть принято всеми корректно функционирующими узлами (цель алгоритма в принятии единого решения) [1, 13]. Для этого осуществляется несколько раундов обмена сообщениями между узлами. После каждого раунда узел принимает новое промежуточное решение (новый выбор значения), которое он рассылает другим узлам в следующем раунде.

Если в системе имеется N узлов, принимающих решение, и необходимо парировать Nb византийских ошибок (византийские ошибки могут возникать в Nb узлах, рассылка нескольких разных искаженных значений считается за соответствующее число ошибок), то для достижения консенсуса должно выполняться следующее условие [1, 13]:

                                                                               (1)

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

В настоящее время существует группа алгоритмов Byzantine fault tolerant concencus (BFT). Часть из этих алгоритмов ориентирована на наличие явно выделенного лидера (для балансировки нагрузки для разных транзакций могут использоваться разные лидеры), например, RAFT [14], BFT_smart [15]. В случае, если в лидере выявляется ошибка, может быть выбран новый лидер. Но на это требуется дополнительное время. Для того, чтобы запрос от клиента в этом случае не был потерян, он может поступать не только к лидеру, но и ко всем остальным решающим узлам. Схема взаимодействия для BFT-smart представлена на рисунке 1. В фазе протокола Request поступает запрос от клиента. Но в следующей фазе PRE-Prepare команда на начало выполнения запроса всем решающим узлам рассылается от лидера. Если решающий узел (не лидер) получил запрос от клиента и в течении некоторого заданного времени после этого не получил команду от лидера, то он инициирует процедуру выбора нового лидера. Если большая часть остальных узлов не получила команду, то выбирается новый лидер, который управляет процессом выполнения запроса от клиента. Если же команда была не получена отдельным узлом (это могло произойти, из-за ошибок в сети, не связанных с функционированием лидера), то такой узел в фазе Prepare начинает функционировать по получению информации о других узлов. В фазе Prepare каждый из решающих узлов посылает всем остальным (в том числе и себе) решение выполнять/не выполнять транзакцию. Если решение выполнять транзакцию получено кворумом (некоторым заданным количеством узлов), то на следующем фазе Commit транзакция выполняется во всех решающих узлах (во всех узлах кворума). После этого источнику запроса посылается ответ о выполнении транзакции. Размер кворума может конфигурироваться, но он должен включать в себя больше половины решающих узлов.

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

Рисунок 1. Схема взаимодействия между клиентом, основным сервером и репликами в BFT-smart

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

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

Как можно видеть из рисунка 1, даже при небольшом количестве решающих узлов, количество сообщений, которыми они обмениваются, достаточно велико. В некоторых алгоритмах, например, phase-king [17] количество сообщений, которыми обмениваются узлы, снижается (зависимость между количеством узлов, принимающих решение, и количеством сообщений полиномиальная), но при этом ухудшается соотношение между количеством парируемых Византийских ошибок и количеством узлов, принимающих решение. Оно определяется следующей формулой:

                                                                                         (2)

В рамках еще одного подхода, разработанного Alexandre Maurer [18] сеть разделяется на несколько отдельных зон. Управление зонами осуществляется по отдельности. В каждой зоне имеется отдельная группа решающих узлов. Такая группа существенно меньше, чем могла бы быть общая группа для всей сети. это позволяет существенно сократить количество передаваемых сообщений, время, необходимое для выполнения алгоритма. Достигается масштабируемость сети за счет увеличения количества зон. Но при этом у администраторов отсутствует целостное видение сети. Для устранения этого недостатка требуется выстраивание следующего уровня иерархии управления. А при использовании этого уровня выигрыш по характеристикам, полученный исходно, теряется.

В других алгоритмах, например, алгоритмах, используемых в blockchain [1, 3] используется схема peer-to-peer, в которой явный лидер отсутствует. Но такая схема приводит к существенному увеличению количества передаваемых по сравнению с алгоритмами с одним лидером. Это делает их не подходящими для администрирования, поскольку большая часть сетевых ресурсов должна быть выделена на решение функциональных задач.

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

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

Предлагаемый алгоритм администрирования

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

В данном алгоритме используется схема администрирования, аналогичная предложенной нами в [19]. События делятся на группы Eh – высокоприоритетные, обрабатываемые апериодически и El – низкоприоритетные, обрабатываемые периодически. Это позволяет обеспечить разное требуемое время реакции на разные типы событий. Узлы, являющиеся источниками высокоприоритетных событий должны иметь возможность самостоятельно передавать сообщения о них администраторам. Для парирования ошибок, каждый узел взаимодействует с несколькими администраторами параллельно. Количество администраторов, к которым должен быть подключен узел типа i (Nai) выбирается в соответствии с кратностью Византийских и не византийских ошибок, которые необходимо парировать. Для этого используется следующая формула:

                                                            (3)

Где Nb – количество ошибок Византийского типа, которые необходимо парировать, Nn – количество ошибок не Византийского типа, которые необходимо парировать.

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

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

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

2. Фиксация текущего состояния (хранится до шага 2 следующего периода конфигурации)

3. Всем администраторам в ответ отправляется состояние, зафиксированное на шаге 2 (если до конца очередного периода конфигурации поступают запросы от других администраторов, то им рассылается это же значение)

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

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

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

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

Узел-администратор после получения ответа на запрос о состоянии или после получения сообщения о событии от терминального узла, рассылает эту информацию остальным администраторам, которые работают с этим узлом (не всем администраторам системы) – выполняется алгоритм консенсуса. В отличие от алгоритмов типа RAFT, BFT-smart, в этом процессе нет лидера, поэтому не возникает проблема недетерминированного времени выполнения этого этапа в случае отказа лидера. Поскольку сообщениями обмениваются не все администраторы, а относительно небольшая их подгруппа, то количество сообщений, обмен которыми выполняется, не столь велико, как пи использовании алгоритмов peer-to-peer.

После того, как консенсус достигнут, принятое решение отправляется каждым администратором всем остальным администраторам. В этом случае также не используется лидер. Каждый из администраторов выполняет обновление своей базы данных по достижении кворума принятых сообщений. Значение кворума задается параметрически, с учетом количества ошибок, которые необходимо парировать для этого типа узлов. Это позволяет для каждого типа узлов парировать требуемое количество ошибок. (Если для данного типа узлов не требуется парирование Византийских ошибок, то для кворума может быть определено значение один – обновление по первому  успешно принятому сообщению, схема, аналогичная используемой в AFDX.)

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

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

Новые параметры отправляются узлу каждым из администраторов, с которым он связан. Узел применяет эти параметры, если получен кворум сообщений от администраторов. Размер кворума задается в соответствии с количеством ошибок, которые необходимо парировать для данного типа узлов. (Если для узлов не требуется парировать Византийские ошибки, то размер кворума может быть установлен в 1.) Это позволяет исключить использование лишней памяти для хранения этих сообщений.

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

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

Оценка характеристик реализации

Оценка достижимых характеристик предложенного алгоритма была выполнена на имитационных моделях сетей, разработанных с использованием языка SystemC (версия 2.1). Было осуществлено моделирование сетей с топологиями толстое дерево и баньян (бабочка, двумерная решетка, тор на базе двумерной решетки). Данные топологии широко используются в сетях реального времени, в которых необходимо пространственное резервирование для парирования отказов, поскольку в них достаточно просто формировать непересекающиеся пути передачи данных с одинаковыми (сходными) характеристиками. Исследуемые сети включали в себя до 1024 терминальных узлов двух типов – источников не критичных событий и источников критичных событий. В сети использовалось 5, 7, 9, 11, 13 узлов администраторов. Рассматривались варианты, при которых для всех узлов парируется один Византийский отказ, для некритичных узлов парируется один византийский отказ, для критичных узлов парируется два Византийских отказа, Византийские отказы парируются только для терминальных узлов, Византийские отказы парируются только для администраторов, для некритичных терминальных узлов парируется 1 или 2 не Византийских отказа, для критичных узлов парируется один Византийский отказ. В экспериментах около 90% узлов считалось узлами – источниками низкоприоритетных событий.

По сравнению с алгоритмами peer-to-peer данный алгоритм позволил получить выигрыш по количеству передаваемых сообщений в десятки раз при количестве узлов до 128 и в сотни раз при большем количестве узлов. Особенно существенный выигрыш (почти на 3 порядка) был получен для систем, в которых для большинства терминальных узлов не требовалось парирование Византийских отказов. По сравнению с алгоритмами с использованием лидера проигрыш по количеству сообщений не превысил 1,2 раза для случая, когда требовалось парирование Византийских ошибок во всех узлах. Если парирование византийских ошибок требовалось не во всех узлах и в случае моделирования ситуации отказа лидеров, то был получен выигрыш по количеству сообщений в десятки раз.

Заключение

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

- поддержку разной кратности Византийских и не Византийских ошибок для узлов разных типов

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

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

Благодарности

Работа выполнена при финансовой поддержке Министерства науки и высшего образования Российской Федерации, соглашение № FSRF-2023-0003, "Фундаментальные основы построения помехозащищенных систем космической и спутниковой связи, относительной навигации, технического зрения и аэрокосмического мониторинга".

Список Литературы

1. Zhong W., Yang C., Liang W., Cai J., Chen L., Liao J., Xiong N. Byzantine Fault-Tolerant Consensus Algorithms: A Survey // Electronics. – 2023. – 12 c.
2. Gagol A., Lesniak D., Straszak D., Swietek M. Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes // 1st ACM Conference on Advances in Financial Technologies. – 2019. – C. 214–228.
3. Malkhi D., Nayak K., Ren L. Flexible byzantine fault tolerance // ACM SIGSAC Conference on Computer and Communications Security. – 2019. – C. 1041–1053.
4. Hao X., Yu L., Zhiqiang L., Zhen L., Dawu G. Dynamic practical byzantine fault tolerance // IEEE Conference on Communications and Network Security (CNS). – 2018. – C. 1–8.
5. Kapitza R., Behl J., Cachin C., Distler T., Kuhnle S., Mohammadi S.V., Schröder-Preikschat W., Stengel K. CheapBFT: Resource-efficient Byzantine fault tolerance // 7th ACM European Conference on Computer Systems. – 2012. – C. 295–308.
6. Angel J., Keziah A., Saritakumar N. A Survey on Software Defined Networks:Technical Challenges, Recent Advances and Security Issues // International Journal of Engineering Research & Technology (IJERT). – 2017. № 5. – C. 1 – 10.
7. Ferrer A. J., Marquès J. M., Jorba J. Towards the decentralised cloud: Survey on approaches and challenges for mobile, ad hoc, and edge computing // ACM Computing Surveys. – 2019. № 6. – C. 1 – 36.
8. Xiao J., Pan X., Liu J., Wang J., Zhang P., Abualigah L. Load Balancing Strategy for SDN Multi-controller ClustersBased on Load Prediction // The Journal of supercomputing. – 2023. № 1. – C. 1 – 24.
9. Trúchly P., Kubica J. Communication Networks with Multiple SDN Controllers // International Symposium ELMAR. – 2023. – C. 29 – 32.
10. Camargos L. J., Schmidt R. M., Pedone F. Multicoordinated paxos // 26th annual ACM symposium on Principles of distributed computing. – 2007. – C. 316–317.
11. Kevin R., Driscoll K., Hall B., Sivencrona H., Zumsteg P. Byzantine Fault Tolerance, from Theory to Reality // Computer Safety, Reliability, and Security. – 2003. – C. 235-248.
12. SpaceFibre - Very high-speed serial link. ECSS-E-ST-50-11C. // ESA-ESTEC. Noordwijk, The Netherlands, 2019. – 233 p.
13. Lamport L., Shostak R., Pease M. 1982. The Byzantine Generals Problem // ACM Trans. Program. Lang. Syst. – 1982. – C. 382-401.
14. Ongaro D. In Search of an Understandable Consensus Algorithm // USENIX ATC ’14 Presentation. – 2014. – 18 c.
15. Bessani A., Sousa J., Alchieri E. P. State machine replication for the masses with BFT-SMART // 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). – 2014. – 8 c.
16. Moraru I., Andersen D. G., Kaminsky M. There is more consensus in egalitarian parliaments // Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13. – 2013. – С. 358–372.
17. Lenzen C. Sheikholeslami S. A Recursive Early-Stopping Phase King Protocol // ACM Symposium on Principles of Distributed Computing (PODC ’22). – 2022. – 10 с.
18. Maurer A., Sébastien Tixeuil S. On Byzantine Broadcast in Planar Graphs // International Symposium on Distributed Computing. – 2021. – 12 c.
19. Суворова Е. А., Поляков В. Б. Протокол администрирования для сетей реального времени на базе SpaceFibre с не византийскими отказами // Вопросы технических и физико-математических наук в свете современных исследований LXXVIII. – 2024. – C. 17 – 30.
20. Lamport L. The Part-Time Parliament // ACM Transactions on Computer Systems. – 1998. – C. 558–565.