Алгоритм DESYNC. Достоинства и недостатки

Алгоритм DESYNC. Достоинства и недостатки.
Часть1.

Вашему вниманию предлагается оригинальный алгоритм (DESYNC: ftp://ftp.deas.harvard.edu/techreports/tr-18-06.pdf), который может быть использован для распределения нагрузки между группами узлов, подключенных к одному и тому же групповому каналу.

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

Экспериментальные исследования [1] показали ощутимое снижение потери сообщений в условиях конкурентной среды с 58% до 1%, так же как и 25% увеличение пропускной способности.

1.      Основные принципы.

1.1. Представим себе полносвязную сеть («клику»), которая включает в себя n узлов. Будем считать, что любой узел такой «клики» - X_i, может рассматриваться как некий генератор синхросигналов, выдаваемых с частотой - ω, которая определяется соотношением (1):

ω = 1 / T

(1)

где T – длительность цикла, разделяющего синхросигналы, которые выдаются одним и тем же узлом.

Фаза, на которой находится каждый конкретный узел X_i, может быть определена величиной ϕ _i(t), которая может принимать значения от 0 до 1, причём значения ϕ_i(t) определяются
отдельно для каждой вершины, то есть число индексов i будет зависеть от числа вершин в «клике» и определяться неравенством (2):

  1.2. Вычисление величины ϕ_i(t) в каждом узле X_i, должно осуществляться автономно, с помощью собственных «внутренних часов», причём в момент времени, когда величина ϕ_i(t) достигнет единицы, узел X_i выдаёт в сеть синхросигнал, после чего приравнивает ϕ_i(t) нулю.

Значение величины ϕ_i(t) должно всегда соответствовать доле интервала времени T, которое прошло после установки ϕ_i(t) в ноль. Например, значение ϕ_i(t)=0.75 соответствует тому, что узел X_i отсчитал 75% времени T.

1.3. Все узлы «клики» способны слышать синхросигналы от своих «соседей» и использовать эту информацию для «подгона» или «осаживания» величин ϕ_i(t) таким образом,  чтобы  моменты выдачи синхросигналов разными узлами не совпадали по времени, но передавались поочерёдно – в порядке возрастания  значений индексов i.

Более того, процедуры коррекции фаз должны стремиться к тому, чтобы интервал времени Δ_i(t) между выдачей синхросигнала любым узлом X_i-1 и выдачей синхросигнала следующим за ним узлом X_i – интервал Δ_i(t), равнялся интервалу Δ_i*(t), который определяется соотношением (3):

Δi*(t) = T / n

(3)

Если условие (3) выполняется для всех вершин «клики», то процесс коррекции фаз ϕ_i(t) может считаться завершённым. В противном случае – сеть должна считаться полностью или частично рассинхронизированной.

1.      Механизмы коррекции фазы.

1.1.Суть механизма коррекции фаз в DESYNC заключается в следующем:

1)      поскольку каждый узел «клики» - X_i способен установить факт передачи синхросигнала от любого узла X_jГ^-1X_i, то он способен получать информацию от узлов X_i-1 и X_i+1, первый из которых выдал синхросигнал перед синхросигналом от X_i, второй – вслед за синхросигналом от X_i;

2)  наблюдая за эфиром, любой узел X_i может получить информацию о фактах передачи синхросигналов всеми узлами «клики»;

3) имея такую информацию узел X_i способен вычислить среднюю точку между выдачей синхросигнала узлом X_i-1 и выдачей синхросигнала узлом X_i+1; Для этого достаточно воспользоваться выражением  (4):

где Φ_i-1(t) и  Φ_i+1(t) – фазы приёма синхросигналов от узлов X_i-1 и X_i+1, по «местному времени» узла X_i;  

4)      после того, как значение Φ_mid(t) определено, узел X_i может скорректировать свою фазу, заменяя ϕ_i(t) на величину ϕ_i^*(t), которая определяется с помощью формулы (5):

где α – параметр, который отвечает неравенству (6):

Этот параметр позволяет ограничить  колебания фазы при её коррекции - чем ниже  значение α - тем незначительней «коррекционный эффект»;

5)      коррекция фазы осуществляется сразу после получения синхросигнала от X_i+1.

2.2.       В принципе, для вычисления Φ_mid(t), достаточно воспользоваться выражением (4).. Но, возможно и более  рациональное решение. Величина Φ_mid(t) может быть определена с помощью выражения (7):

где

- Δ_i – текущее значение величины ϕ_i(t)  в момент получения последнего синхросигнала от всех соседей X_i (до момента времени, когда ϕ_i(t)=1);

- Δ_i+1 - значение величины ϕ_i(t) в момент получения первого синхросигнала от любого соседнего узла, принятого после момента выдачи синхросигнала узлом X_i.

 2.3. Такое решение может быть проиллюстрировано следующими примерами.

Предположим, что последовательность выдачи синхросигналов узлами X_i-1 , X_i  и X_i+1 соответствует временной диаграмме, которая представлена на рисунке 1:

Рисунок 1

Допустим, что синхросигнал от узла X_i-1 принят в тот момент времени, когда «часы» узла X_i показывают ϕ_i(t)=0.7. Эта величина фиксируется в памяти узла X_i.  Тогда, в момент времени, когда узел X_i будет выдавать «собственный» синхросигнал, он может установить, что Δ_i(t)=0.7.

Аналогичным образом, после получения синхросигнала от X_i+1, может быть установлена величина Δ_i+1. Предположим, что Δ_i+1=0.3. Тогда, имея  Δ_i(t)=0.7 и Δ_i+1=0.3 с помощью выражения (8) можно получить:

Φ_mid(t) = ϕ_i(t) + {[Δ_i+1 - Δ_i(t)] / 2} = 1 + (0.3 – 0.7) / 2 = 1 – 0.2 = 0.8

Предположим, что заданный параметр α=0.5. В таком случае, пользуясь формулой (5), можно получить: 

ϕ_i^*(t) = (1- α) ϕ_i(t) + α Φ_mid(t) = 0.5x0.3 + 0.5x0.8 = 0.55

что соответствует  «подгону» фазы ϕ_i(t), - поскольку установка ϕ_i^*(t) будет осуществлена при ϕ_i(t)=Δ_i+1=0.3, то  текущее значение ϕ_i(t) будет увеличено.      

Аналогичным образом, может быть осуществлено «осаживание» фазы ϕ_i(t).

Такое событие произойдёт в том случае, если после измерения величин Δ_i и Δ_i+1 выяснится, что эти величины  отвечают неравенству (8):  

Δi+1 > Δi

(8)

Например, при Δ_i(t)=0.3, Δ_i+1=0.7 и α=5, будем иметь:  

Φ_mid(t) = 1 + (0.7 – 0.3) / 2 = 1.2

Округлив эту величину по модулю 1, получим Φ_mid(t) = 0.2, и, при α=0.5, будем  иметь:

ϕ_i^*(t) = (1- α) ϕ_i(t) + α Φ_mid(t) = 0.5x0.7 + 0.5 x 0.2 = 0.36

Таким образом, коррекция фазы будет осуществлена при ϕ_i(t)=Δ_i+1=0.7, следовательно, текущее значение ϕ_i(t) будет уменьшено.

Мы продолжим обсуждение темы в следующей части.

Возможная структура управления в самоорганизующихся системах связи

Исходя из приведенного примера, можно сделать следующие выводы:

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

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

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

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

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

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

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

Возможный подход к решению задач управления и «самоорганизации».

1) Задача управления системой разбивается на несколько подзадач или слоев:

● управление ресурсами канального и физического уровней;

● управление ресурсами сетевого уровня;

● управление безопасностью;

● прочие

2) Каждая из этих подзадач решается в какой-то степени автономно, однако все подзадачи должны быть подчинены одной и той же цели - поддержке высокого уровня надёжности и живучести системы. Эти задачи взаимосвязаны и взаимозависимы: например, несоответствие радиочастот и маршрутов у абонентов одного и того же канала приведёт к невозможности передачи/приёма пакетов по этому каналу, использование топологии системы, в составе которой указаны «неорганизованные» каналы приведёт к неверному расчету маршрутов.

3) Получив все настроечные данные, система «самоорганизуется»: на основании исходных данных каждая станция способна, как рассчитать все необходимые маршруты, так и «перерасчитать» их, в случае спонтанной реконфигурации системы. Для обеспечения такой возможности может использоваться протокол динамической маршрутизации, обеспечивающий широковещательную рассылку информации об изменениях состояний связей (типа OSPF или OLSR).

4) Управление ресурсами системы должно осуществляться централизовано: администратором системы со специально выделенного автоматизированного рабочего места (АРМ). Для эффективного управления системой, АРМ должно обеспечивать:

● наглядную интерпретацию текущей топологии системы и её ресурсов;

● оценку возможности дистанционной доставки служебной (настроечной) информации оборудованию при осуществлении манёвров частотами, каналами и т.д.;

● оценку последствий возможных решений администратора системы (потери/восстановления топологической связности и т.п.);

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

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

Примеры самоорганизующихся сетей и их сравнительная оценка

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

Рассмотрим систему, которая представляет собой канал коллективного доступа - подсистему Z^* и совокупность маршрутизаторов, которые определяют маршруты между каждой парой абонентов этого канала - подсистему Z^**:

Рисунок 1

Предположим, что в этой системе используется статическая маршрутизация, (сеть типа ad hoc) то есть маршруты заданы таким образом, что каждой паре абонентов X_i и X_j соответствует единственный (непосредственный) маршрут X_i - X_j. При таких условиях подсистема Z^** может находиться в единственном состоянии и, следовательно, H(Z^**)=0. Если в процессе эксплуатации системы, условия радиослышимости в канале меняются, то H(Z^*)>0. Но подсистема Z^** никак не реагирует на эти изменения, поэтому H₀=H₁, и R=H₀-H₁=0. Следовательно, система предельно неорганизованна.

Допустим теперь, что подсистема Z^** построена таким образом, что каждому непосредственному маршруту X_i - X_j, (кроме маршрутов от X_k) ставиться в «жесткое» соответствие единственный обходной маршрут вида X_i – X_k - X_j (X_k – некая общая «точка доступа», вариант построения сети ad hoc):

Рисунок 2

В данном случае, энтропия H(Z^**) не может равняться нулю, поскольку подсистема Z^** реагирует на изменение состояний радиолучей – отказ основного маршрута приводит к использованию обходного маршрута.

Попытаемся оценить уровень организации такой системы. Действуем поэтапно, в соответствии с выражениями (3.2) – (3.6).

1) Будем считать, что вероятность отказа любого радиолуча в канале равна P. Тогда

H(Z*)= - Cmj {Pj (1- P)m-j log2[ Pj (1- P)m-j]

(3.1)

где

m – общее число радиолучей в радиосети, равное

m = n(n-1)/2

(3.2)

n – общее число маршрутизаторов, включая «точку доступа».

2) Если считать, что каждый маршрутизатор (кроме точки доступа) выбирает обходной или основной маршрут с равной вероятностью (по принципу «орёл – решётка»), то

H(Z**) = log2 2(n-1)(n-2)/2 = (n-1)(n-2)/2

(3.3)

3) Общее число ситуаций в Z^*, которым соответствует однозначная реакция подсистемы Z^**, ограничено. Действительно (см. рисунок 2), если абонент X_i намерен передать пакет X_j, то он воспользуется обходным маршрутом X_i – X_k - X_j только в том случае, если вышел из строя радиолуч X_i - X_j. Аналогичным образом, абонент X_j воспользуется обходным маршрутом X_j – X_k – X_i только при отказе радиолуча X_i - X_j и т.д.

И вообще, однозначное соответствие состояния подсистемы Z^**состоянию сети Z^* возможно только тогда, когда изменения состояний радиолучей будут происходить только в пределах подмножества E₁ (на рисунке 2 эти лучи выделены жирными линиями). Причем в любой из таких ситуаций P(Z_j^*|Z_k^**)=1.

Изменения структуры вне E₁ на поведение системы не влияют, так как любая неудачная попытка передачи пакета по основному маршруту между любыми X_iE₁ всегда приводит к передаче того же пакета по обходному маршруту (независимо от состояния радиолуча X_i - X_k) Поэтому:

H (Z*|Z**) =CLk Pk(1-P)L-k {-Cn-1j Pj(1-P)n-(j+1) log2 [Pj(1-P)n-(j+1))]}

(3.4)

где L = (n-1)(n-2)/2 – число радиолучей в E₁.

Графики зависимостей Н(Z^*) и R от величины P (для сети, включающей в себя 8 маршрутизаторов), приведены на рисунке 3.

Рассматривая эти графики, нетрудно заметить, что рассматриваемая система далека от совершенства: RН(Z^*) только при весьма надежных каналах связи (P0.05).

Рисунок 3

Но, при определённых условиях, уровень организации такой системы может быть признан достаточно высоким. Например, если радиолучи, связывающие абонентов сети с общей «точкой доступа», обладают достаточно высокой надежностью – с вероятностью отказа =0.15, а остальные каналы менее надежны – с P0.5, то

H(Z*)= -CLk Pk log2[Pk(1-P)L-k] - Cn-1j  j(1-)n-(j+1) log2[ j(1-)n-(j+1)]	(3.5)
H (Z*|Z**) =CLk Pk(1-P)L-k {-Cn-1j  j(1-)n-(j+1) log2 [j(1-)n-(j+1))]}	(3.6)

и величина R сопоставима с H(Z^*) даже при P=0.5 (см. рисунок 4).

Отметим что в данном случае, степень организации системы увеличивается за счёт уменьшения энтропии H(Z^*), которое, в свою очередь, достигается за счёт повышения надежности части радиолучей. Очевидно, что при их стопроцентной надёжности (то есть при =0) величина H(Z^*) станет равной R, и уровень организации в системе может считаться идеальным.

Теперь предположим, что все элементы системы «сверхнадежны». Тогда, система, после завершения этапа её развертывания, будет описываться «железобетонным» графом, который всегда соответствует заранее известному «замыслу системы». Очевидно, что такая система не способна к адаптации, (она просто не нужна), а какая либо информация об её состоянии – бесполезна, поскольку H(Z^*)=H(Z^**)=0. Но, к сожалению, построить такие простые и надёжные сети (тем более, в полевых условиях) далеко не всегда возможно.

Рисунок 4

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

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

Поэтому, есть основания предполагать, что высокоорганизованные протоколы маршрутизации могут найти применение только в высокоскоростных сетях (типа wi-fi). В низкоскоростных УКВ-сетях более целесообразна реализация алгоритмов типа ad-hoc.