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

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

3.      Позитивные свойства  алгоритма и его недостатки

3.1. С точки зрения пользователя, алгоритм DESYNC весьма удобен, поскольку он не требует подготовки каких либо настроечных данных, например таких, как размер сети, её топология или её исходное состояние.

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

Это объясняется тем, что, при использовании алгоритма DESYNC, узлы сети определяют моменты передачи собственных синхросигналов автономно,  опираясь лишь на  показания собственных «часов», ход которых корректируется в моменты приёма «синхросигналов» от соседей. При этом  данный алгоритм игнорирует такие атрибуты узлов, как идентификаторы (адреса) соседних узлов, их число, статус и т.п.  

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

3.3. Использование данного алгоритма обеспечивает «справедливое» деление временных интервалов между узлами -  в стационарном режиме (в независимости от числа узлов) интервалы времени между передачами очередных синхросигналов – T / n будут распределены равномерно.

Эта особенность может оказаться полезной при случайных сбоях и временных потерях радиослышимости – если число абонентов в сети невелико, то случайные сбои, которые могут спровоцировать резкие скачки фаз, далеко не всегда приведут к коллизиям. Такие события будут всегда приводить к увеличению длин интервалов T / n, что увеличивает шансы на успех  при возврате элементов сети к прежнему состоянию.  Вообще, любая подобная ситуация может рассматриваться как «штатная».

 3.4. Однако следует отметить, что использование рассматриваемого протокола эффективно только в том случае, если топология сети отвечает условию (9):

то есть сеть является «кликой».

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

Допустим, что сеть состоит из трёх узлов и её топология соответствует графу, который изображён на рисунке 2:

Рисунок 2

Представим себе, что в сети работают только два узла – X_a и X_b, и моменты выдачи «синхросигналов» этими узлами, соответствуют временному циклу, представленному на рисунке 3:

Рисунок 3

Теперь представим себе, что, после очередной коррекции фазы в узле X_b, к сети подключился узел X_с,  и следующий цикл T будет соответствовать рисунку 4:

Рисунок 4

Такая ситуация приведёт к сдвигу фазы узла X_b, причём «новая» фаза этого узла будет стремиться к середине интервала времени между выдачей «синхросигналов» от узла X_a (воспринимаемого как узел X_b-1) и X_с (воспринимаемого как узел X_b+1).

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

1)      узел X_c зафиксирует длину интервала Δ_с(t), воспринимая  X_b  как источник «синхросигнала» от  мнимого  узла X_c-1;

2)      узел X_a  зафиксирует либо длину интервала Δ_a(t), либо длину интервала Δ_a+1(t)  (в последнем случае процедуры коррекции фазы в узле X_a будут выполнены, но фаза этого узла практически не изменится).

Далее, последовательность событий может развиваться по следующему сценарию:

- получив  следующий «синхросигнал» от X_b, узел X_с сдвинет свою фазу так, что момент выдачи «синхросигнала» X_c  в следующем цикле будет смещён в сторону X_a, (см. рисунок 5):

Рисунок 5

- если узел X_a воспринимает «синхросигнал» от X_b как сигнал от источника X_a+1, то он также сдвинет свою фазу, но в противоположенную сторону – навстречу X_с (см. рисунок 6):

Рисунок 6

- возникает коллизия, в результате чего узел X_b перестанет воспринимать сигналы от своих соседей и будет менять свою фазу только за счёт погрешности собственных «часов»;

- однако «дрейф» фазы X_b не улучшит сложившуюся ситуацию, поскольку узлы X_a и X_c будут всегда стремиться занять один и тот же слот.

Возможны другие (может и более благополучные) сценарии, но приведённого примера вполне достаточно, чтобы убедиться в том, что использование алгоритмов DESYNC в сетях, не отвечающих условию (9), не имеет смысла.

Алгоритм 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) будет уменьшено.

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