An analytical approach to the synthesis of regular structures of fault-tolerant systems.pdf Проблема синтеза отказоустойчивых сетей связи представлена в научной литературедостаточно широко. Наиболее распространенный подход к решению этой проблемысостоит в генерации случайных сетей с последующей режекцией не отвечающихзаданным критериям вариантов. В качестве критериев при этом используют такиеобщеупотребимые показатели, как диаметр, связность, коэффициент кластеризациии т. п. Известные [1] исследования устойчивости вычислительных сетей и систем к случайномуи/или преднамеренному удалению вершин из их структур свидетельствуюто большей устойчивости регулярных структур. При этом ни в теории сетей и систем,ни в фундаментальной ее основе - теории графов проблематика генерации структуры(графа) с заданными коммуникативными свойствами систематическими методами, исключающиминеобходимость перебора, практически не исследована. Связано это было,по-видимому, с отсутствием аппарата описания графов, позволяющего максимальноформализованно производить их анализ и преобразования.В данной работе впервые сформулирован аналитический подход к решению проблемысинтеза регулярных графов заданного порядка n и степени s. Подход основан напредложенной автором формализации описания графа G(V, E) его проекциями P(v0),v0 E V , и состоит в построении базовой проекции остовного дерева генерируемогографа, в анализе этой проекции и выявлении с ее помощью нижней границы диаметраd(G) и верхней границы обхвата g(G), а также в последующем доопределениинеизвестных ребер графа другими его проекциями в соответствии с требуемыми значениямипоказателей. Таким образом, поиск недостающих в остовном подграфе реберподобен решению системы уравнений, в качестве которой использовано множествопроекций генерируемого графа.Проекция P(vi) графа G(V, E) представляет собой многоуровневую конструкцию,на нулевом уровне которой расположена ракурсная вершина vi E V ; порожденное еюединственное подмножество первого уровня содержит все вершины окружения N (vi),а каждый к-й уровень (к > 1) представляет собой совокупность подмножеств вершин,каждое из которых порождено вершиной (к - 1) -го уровня и является окружениемэтой вершины без техего вершин, что ей предшествуют. Таким образом, отношение«предшествования вершины/порождения подмножества» фактически моделирует отношениесмежности соответствующей вершины с вершинами соответствующего подмножества.Формальная запись этих отношений в скобочном описании двух произвольновзятых соседних уровней проекции графа имеет вид {a {bl'"""'bj} , ... , a{ci'"""'ci}}. Здесьвершины a1 и ai одного из подмножеств произвольно взятого уровня предшествуют исмежны вершинам порожденных ими подмножеств {b1, . . . , bj} и {c 1, ... , q }.Для конкретизации числа к уровней в проекции добавим в ее обозначение соответствующийиндекс - Pk(w). Тогда P0(w) = w. Продолжив описание до 1-го уровня,получим P1 (w) = wVwj. Здесь множество вершин Vwj = N (w) является окружениемвершины w и состоит из s(w) вершин, где s(w) = deg(w) -степень вершины w. Такимобразом, j -я вершина (i - 1)-го уровня проекции порождает на следующем i-м уровнеподмножество Vj С V вершин. Подмножеству Vj поставим в соответствие множествопредшествующих ему вершин Vj С V , включенных в маршрут M (v0,vi-1;j ) из ракурсной вершины v0 в вершину vi - \,j. Подмножества вершин i-го уровня, число которыхравно числу вершин (i - 1)-го уровня, получаем вычитанием из окружений вершин(i-1)-го уровня всех предшествующих им в проекции вершин из V j: Vj = N (vi-1,j)\Vj.Из проекции единичного куба (n = 8, s = 3)P (0) = 0{1{4{2'7} ,5{3'7}},2{4{1'7>,6{3,7>},3{5{1,7} 6{2,7}'} }видно, что его диаметр равен 3. В работе показано, что минимальное значение эксцентриситетаe(v0) корневой вершины проекции P(v0) для пары (n, s) достигается прие- 1 е1 + s Е (s - 1)i- < n ^ 1 + s E (s - 1)* . Это означает, что для 4 < n ^ 10 и s = 3i=1 i=1могут быть получены более компактные (с d = 2 ) графы, базовая проекция которыхимеет видP (0) = 0{1{2'3'4'Б'6,7}2 ,2{1,3,4,Б,6,7}2 ,з{1,2,4,5,6,7}2 }Доказано утверждение о том, что обхват g графа не превышает удвоенного эксцентриситетаего проекции, поэтому значение d = 2 в генерируемом графе с n = 8, s = 3может быть обеспечено как с g = 3, так и с g = 4. Применение подхода показанов работе на примере генерации таких графов, их минимальные полные проекции исоответствующие им графы приведены на рис. 1.g = 3 P (0) = 0{1{2{5},4{6'7}},2{1{4},5{6,7}} ,з{6{4,5},7{4,5}}}g = 4 P (0) = 0{1{4{3,6},5{6,7}},2{6{4,5},7{3,5}},3{4{1,6},7{2,5}}}Рис. 1. Единичный куб (а), граф с n = 8, s = 3, g = 3 (б) и граф с n = 8, s = 3, g = 4 (в)Обобщенное изложение последовательности действий в процессе синтеза дано напримере синтеза графа той же степени, что и ранее рассмотренные, но большего порядка.Показано, что применение сформулированного подхода не ограничено рассмотреннымив работе случаями синтеза регулярных графов: подход может быть с успехомиспользован для решения более общих сетевых задач, включая задачи масштабированияи наращивания структуры системы. Внедрение же аналитических методов решенияэтих задач в теорию и практику построения отказоустойчивых систем существенноповысит их оптимальность, реактивность и предсказуемость.

Скачать электронную версию публикации