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

AN MANAGEMENT PROTOCOL FOR SPACEFIBRE BASED REAL-TIME NETWORKS WITH NON-BYZANTINE FAULTS

Elena Suvorova

Candidate of Technical Science, Saint-Petersburg State University of Aerospace Instrumentation,

Russia, Saint-Petersburg

Vadim h Polyakov

Doctor of Technical Science, Saint-Petersburg State University of Aerospace Instrumentation,

Russia, Saint-Petersburg

АННОТАЦИЯ

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

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

ABSTRACT

Modern real-time local area networks typically include hundreds of terminal nodes of various types. To ensure the required response time to network events, to ensure network scaling, and to ensure that faults of network managers (nodes) in such networks are mitigated, it is required to use several nodes performing management functions (administrative nodes). But using multiple network manager’s nodes entails the need to use more complex algorithms for managers to interact with other network nodes and with each other. These algorithms are based on mechanisms for reaching consensus between managers when choosing a new configuration. The mathematical foundations of these mechanisms are the same for a number of different applications related to providing shared access to various resources, distributed databases. But the limitations and requirements for algorithms in different systems can vary significantly. Therefore, there are currently quite a large number of different algorithms that provide a solution to this problem. This article proposes an algorithm and protocol focused on use in networks based on the SpaceFibre standard, which ensures the mitigation of non-Byzantine faults, moreover, in different parts of the network, the requirements for the number of mitigated faults may be different, the required response time to events of different types may also be different. Compared with existing algorithms, the proposed algorithm provides these new properties, as well as a reduction in the amount of information transmitted (which entails a shorter execution time for the phases of data exchange of the algorithm), a decrease in buffer memory required for the intermediate storage of transactions.

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

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

Введение

В состав современной локальной вычислительной сети реального времени может быть довольно большое количество (сотни, в ряде случаев - тысячи) узлов-датчиков (сенсоров). Для подключения к сети, реализованной, например, на базе стандарта SpaceFibre, такого большого количества терминальных узлов требуется довольно большое количество маршрутизаторов. Например, при древовидной структуре сети и если используются маршрутизаторы с 8 портами, то для подключения 500 датчиков понадобится более 80 маршрутизаторов.

Чем больше становится сеть, тем больше накладные расходы (количество служебной информации) требуется передавать по сети для контроля ее состояния, управления режимом функционирования. Системный администратор (ПО, выполняющее функции управления сетью) должен опросить устройства для определения их состояния. Затем, после принятия решения о новой конфигурации прислать устройствам новые значения параметров управления. В результате для больших сетей доля служебной информации, так называемой housekeeping информации может приближаться к 40%-50% пропускной способности каналов передачи данных [1, 2, 3, 4, 5]. Поэтому при выборе или разработке алгоритма управления сетью очень важной характеристикой является количество передаваемой служебной информации.

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

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

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

- обеспечивать парирование сбоев и отказов,

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

Регулирование нагрузки достигается благодаря тому, что каждый из администраторов взаимодействует с некоторой частью сетевых узлов. В таких сетях каждый сетевой узел может взаимодействовать с одним или несколькими администраторами [2, 3, 4, 5].

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

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

Схемы администрирования

Типовой процесс администрирования включает в себя:

- фазу сбора информации о текущем состоянии сети (или фазу получения информации о событиях в сети, на которые требуется реакция);

- фазу принятия решения о новой конфигурации;

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

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

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

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

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

Существующие алгоритмы и протоколы достижения консенсуса

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

Можно выделить два основных типа алгоритмов: алгоритмы, ориентированные на наличие ведущего/основного узла (узла-лидера) среди узлов, принимающих решение (в нашем случае, среди узлов - администраторов) и алгоритмы, в которых нет лидера при принятии решения. Наиболее распространённые протоколы, основанные на алгоритмах, относящиеся к первой группе, это PAXOS [6, 7] и RAFT [8]. К реализации второй группы алгоритмов относятся такие протоколы, как EPAXOS [9], Alvin [10], Mencius [11].

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

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

Предлагаемый алгоритм и протокол

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

Было выполнено сравнение систем, для которых были разработаны алгоритмы, рассмотренные в предыдущем разделе и задачей администрирования сети SpaceFibre. На основе этого были выявлены следующие основные отличия:

- разная кратность отказов для разных типов узлов;

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

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

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

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

Одним из требований является обеспечение обработки событий разной критичности. В соответствии с этим для различных типов событий, происходящих в сети, существует возможность определить различные уровни критичности. В соответствии с уровнем критичности для разных типов событий может быть задано разное допустимое время реакции на события. Количество уровней критичности (С) не ограничено. Уровни критичности делятся на две группы: события низкой критичности (множество событий El, количество уровней – Cl) и события высокой критичности (множество событий Eh, количество уровней - Ch). Для реализации предлагаемого протокола сетевые устройства, являющиеся источниками событий высокой критичности должны иметь возможность отправлять администратору сообщения о своем состоянии. Информация о событиях низкой критичности может отправляться самим устройствами или прочитываться администраторами.

Обработка событий низкой критичности осуществляется периодически. Для разных уровней критичности могут быть заданы разные длительности периода. В текущей версии протокола все они должны быть кратными. Выбирается период с наименьшей длиной для наиболее критичных событий в данной группе (Tamin), для остальных периоды (Tai) выбираются кратными этому значению периода (1).

                                                                (1)

Где Lil – целочисленный коэффициент, соответствующий данному уровню критичности.

В предлагаемом протоколе

Предполагается, что для определения текущего состояния сети администраторы выполняют опрос состояния узлов сети с некоторым периодом (в сети может существовать некоторое количество «элементарных» узлов, не имеющих функции отправки информации о изменениях своего состояния администратору). Выбранное значение периода Tai должно быть меньше Tami Период (Ta) может быть определен по формуле (2):

                                                                (2)

Где Tr – требуемое для системы время реакции на события, Tack – время, необходимое для выполнения опроса администраторами, Td – время, необходимое для принятия решения о новой конфигурации, Tconf – время, необходимое для передачи узлам новых параметров конфигурации.

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

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

Для парирования отказов требуемой кратности в сети на этапе проектирования должно быть реализовано соответствующее пространственное резервирование. Предлагаемый протокол ориентирован на парирование ошибок не Византийского типа. В соответствии с этим используется схема обмена информацией, при которой при необходимости парирования N-1 отказов, сетевой узел должен взаимодействовать с N администраторами (в случае N-1 отказов хотя бы один администратор сможет выполнить опрос узла или получить от него информацию о изменении состояния и прислать ему новые параметры конфигурации). Аналогичная схема обмена между устройствами используется во многих стандартах, ориентированных на парирование не Византийских ошибок, например, AFDX [12]. При выборе администраторами решения о конфигурации используется мажоритарная схема. Данная схема широко используется для систем без Византийских ошибок [13].

С учетом выбранных схем, при проектировании сети количество узлов – администраторов  (M) должно быть выбрано таким образом, чтобы выполнялись условия (3), (4):

                                                                                      (3)

                                                                                          (4)

Где Na – кратность отказов узлов администраторов, которые необходимо парировать, Mcs – количество узлов в системе с учетом кратности отказов, которые для них необходимо парировать, R – максимально допустимое количество узлов, управление которыми осуществляется одним узлом администратором.

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

Для определения параметра Mcs может быть использована формула (5):

                                                                                 (5)

Где K – количество типов узлов в системе (без учета узлов - администраторов), Mi – количество узлов i типа, Ni – коэффициент, позволяющий учесть кратность ошибок, которые необходимо парировать для данного типа узлов.

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

Если администраторы выполняют опрос состояния узла, то запросы от разных администраторов будут выполняться в некоторой последовательности. При этом из-за потенциально разного времени передачи ответов по сети, ответ о состоянии, сформированный позднее, может быть получен раньше. Поскольку для принятия решения о новой конфигурации целесообразно использовать более позднюю (более «свежую») информацию о состоянии, для упорядочивания ответов в предлагаемом протоколе в сетевых узлах используются логические часы (часы Лампорта) [14]. В данном случае каждое чтение состояния считается за событие, по которому увеличивается значение счетчика (логических часов). Для обращений от всех администраторов используется общий счетчик. Значение счетчика узел помещает в ответный пакет. После опроса узла администраторы обмениваются между собой (в пределах рассматриваемой подгруппы) полученной статусной информацией. Выбирается информация с наибольшим значением счетчика. Этот вариант статусной информации рассылается всем остальным администраторам и далее используется для принятия решения о новой конфигурации.  

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

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

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

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

Характеристики реализации

Для моделирования работы предложенного протокола, оценки достижимых характеристик были разработаны имитационные модели сетевых узлов и узлов администраторов с использованием языка SystemC (версия 2.1). На базе данных моделей были собраны сети с топологиями толстое дерево и баньян (бабочка, двумерная решетка, тор на базе двумерной решетки), включающие в себя до 512 терминальных узлов. Данные топологии в настоящее время широко используются, поскольку в них достаточно просто обеспечить количество непересекающихся путей передачи данных в соответствии с количеством отказов, которое необходимо парировать.

В сети использовались терминальные узлы двух типов – источники некритичных событий и источники критичных событий и маршрутизаторы, выступающие в роли источников и критичных и не критичных событий. В сети использовалось 3, 5, 7, 9 и 11 администраторов. Каждый из узлов имеет количество портов, равное количеству отказов, которое следует парировать. Для некритичных узлов рассматривалось парирование 1 и 2 отказов. Для критичных узлов 2, 3, 4 отказа. Для администраторов – 1, 2, 3, 4, 5 отказов (соответственно для каждого рассматриваемого количества администраторов). Если для всех узлов выполнялось парирование одинакового количества отказов, то для всех рассмотренных алгоритмов количество передаваемой служебной информации было практически одинаковым. При разном количестве отказов для разных узлов предложенный алгоритм позволил получить выигрыш в десятки раз при количестве узлов до 128 и в сотни раз при большем количестве узлов. (В экспериментах для 90% узлов было определено парирование меньшего количества отказов.)

Заключение

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

- разной кратность отказов для разных типов узлов;

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

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

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

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

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

1. 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.
2. 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.
3. 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.
4. Trúchly P., Kubica J. Communication Networks with Multiple SDN Controllers // International Symposium ELMAR. – 2023. C. 29 – 32
5. Varalakshmi P., Mithesh A., Niveditha B., Rubak Preyan G., Yogeeswar S. Intelligent load balancing in SDN // 8th International Conference on Advanced Computing and Communication Systems (ICACCS). – 2022. V 1, C. 1146 – 1151.
6. Camargos L. J., Schmidt R. M., Pedone F. Multicoordinated paxos // 26th annual ACM symposium on Principles of distributed computing. – 2007. C. 316–317.
7. Lamport L. The Part-Time Parliament // ACM Transactions on Computer Systems. – 1998. C. 558–565.
8. Ongaro D., Ousterhout J. In Search of an Understandable Consensus Algorithm // USENIX Annual Technical Conference. – 2014. C. 1 – 17.
9. Moraru I., Andersen D., Kaminsky M. There is more consensus in egalitarian parliaments // SOSP’13. – 2013. C. 358–372.
10. Turcu A., Peluso S., Palmieri R., Ravindran B. Be general and don’t give up consistency in georeplicated transactional systems // OPODIS’2014, Lecture Notes in Computer Science. – 2014. V. 8878. C. 33–48.
11. Demirbas M. Metadata: Mencius: building efficient replicated state machines for wide-area-networks (WANS) // 8th USENIX Symposium on Operating Systems Design and Implementation. – 2008. C. 369 – 384.
12. Pickles B. Avionics Full Duplex Switched Ethernet (AFDX) // SBS Technologies. 2006. C. 1 –25.
13. Abdullah M. A., Draief M. Majority Consensus on Random Graphs of a Given Degree Sequence // CoRR. – 2012. C. 1 – 12.
14. Fidge C.J.,  Logical Time in Distributed Computing Systems // Computer. – 1991. V. 24, C. 281 – 33.